The cache has space limitation, and different cache elimination strategies will be adopted to deal with the cache full load in different situations. There are three common cache flushing strategies:
- FIFO (First In, First Out)
- LFU (Least Frequently Used)
- LRU (Least Recently Used)
FIFO
First in, first out. If the cache capacity is full, the earliest data added to the cache is removed preferentially. It can be implemented internally using queues.
In simple terms: if a piece of data is in the cache first, it should be discarded first.
LFU
The core idea of weeding out data based on its historical access frequency is that “if data has been accessed multiple times in the past, it will be accessed more often in the future.”
Therefore, the elimination strategy of LFU is actually: if a data is rarely used in the recent period, it is also very unlikely to be used in the future, so elimination is preferred.
LRU
At present, least recently used is one of the most commonly used cache algorithms and design schemes. Its removal strategy is “when the cache (page) is full, the latest and longest unused data will be removed first”. It is easy to design and use and applies to a wide range of scenarios.
At first glance, it seems that LFU and LRU are not very different. In fact, the difference between LFU and LRU is mainly based on different criteria. LFU is based on the number of access times, while LRU is based on the number of time not accessed.
Here’s an example:
-
There’s data: 1,2,3,4
-
Cache size is 2: []
-
I went to 1,2,1
-
The cache should now be [1(2), 2(1)] (the number of accesses in parentheses)
-
Now I want to access 3 again, at which point I need a cache elimination strategy
-
FIFO should be well understood, first in, first out, I first access 1, then access 2, so the cache becomes [3(1).2(1)]
-
The cache becomes [3(1),1(2)].
-
LRU we want to see which data has not been accessed for the longest time, because the last time I accessed 1, so I eliminate 2, cache becomes [3(1),1(2)]