How each policy decides what to throw away
FIFO — arrival order
The cache is a queue. New keys go to the back, eviction always takes from the front, and a cache hit changes nothing. That last part is the whole story: a key that is requested on every single step still gets evicted on schedule, because FIFO never learns that it is popular.
LRU — recency
Same queue, one change: a hit moves the key to the back. That single rule makes LRU strong on traffic with temporal locality, and it is why LRU became the default in most systems.
Run the cyclic scan pattern and LRU drops to zero. Recency is a prediction, and on a loop the prediction is inverted — the key you just used is the key you will need last, and the one you are about to need is the one LRU has decided to discard.
LFU — frequency
Count every access and evict the smallest counter. On skewed traffic this is excellent, because skew is exactly what counters measure. Its weakness is memory of the wrong kind: a key that was popular yesterday keeps a high count today and refuses to leave, so a workload whose hot set shifts over time slowly fills with keys nobody wants any more.
S3-FIFO — a small queue in front
Most cached objects are requested once and never again. S3-FIFO builds around that observation. New keys enter a small queue holding about 10% of the cache. A key only graduates to the main queue if it is requested again while it is still there. Everything else is evicted quickly, and its identity is remembered in a ghost list so a later reappearance can promote it straight to main.
In the simulator the badge on each slot shows which queue a key is in — S for small, M for main. Watch the hot set migrate into M while one-off keys churn through S without disturbing anything.
What the benchmark showed
These four policies were measured over one million requests per pattern in a companion article, and two results are worth carrying with you. On a cyclic scan, FIFO, LRU and LFU all returned exactly zero hits while random replacement reached 79%. And across the mixed workload, growing the cache from 1% to 5% of the key space gained 18.9 points, while switching from LRU to S3-FIFO at a fixed size gained 9.9. Sizing usually matters more than the policy argument.
Full method, code and raw output: Cache eviction algorithms, measured.
