Eviction Is a Prediction
A cache with a size limit has to answer one question over and over: when it is full and something new arrives, what goes?
Every policy is a different guess at that, made with no knowledge of the future. Because it is a prediction, the right one depends on what your traffic looks like, and traffic shape is measurable.
Four Policies, Measured
The script is at scripts/labs/eviction/policies.py. It replays 200,000 Zipf-distributed requests over 5,000 keys through LRU, LFU, FIFO and random at four cache sizes.
LFU beat LRU at every size. FIFO and random were indistinguishable from each other. And the scan needed three attempts to measure, because the first two resolutions averaged the effect away.
That gap is larger than the usual advice implies, and it has a simple cause: a Zipf head is defined by frequency, and frequency is exactly what LFU measures. The smaller the cache, the more the policy matters.
The head of a Zipf distribution is the same handful of keys hour after hour. LFU learns that and holds them. LRU evicts a hot key as soon as enough other keys are touched after it, and in a small cache that is a very short period.
The Scan, and Measuring It Honestly
The folklore is that a scan destroys an LRU cache. A nightly export or a crawler touches every key once, which makes each of them look recently used, so LRU should evict the genuinely hot ones.
A brief effect inside a long run is invisible at the wrong resolution. When a measurement shows nothing, check the resolution before believing it.
The effect is real and much smaller than its reputation. LRU's first bucket is 42 percent against its usual 53, and by the third bucket it is back to normal. LFU shows no dip at all.
What Each Policy Actually Costs
FIFO and random produced identical hit rates at every size tested. If you are choosing between them, the measurement says the choice does not matter and you should be looking at LRU or LFU instead.
LFU's strength on stable traffic is exactly its weakness where popularity shifts. This is why Redis calls its policy allkeys-lfu: it uses a probabilistic counter that decays.
The Comparison Nobody Makes
Both lines come from the same measurement. Memory is usually cheaper than an argument about eviction, and it helps more, which is worth knowing before the argument starts.
If your eviction rate is high, your is mostly decorative and tuning it will change very little. Check the eviction rate before spending time on the TTL.
What to Actually Do
Answer the first with a number. Divide your cache size by your distinct key count: at one in five the policies were eleven points apart, and at one in a hundred they were twenty.
Nothing above the fifth line is controversial and all of it is worth more. Teams reach step five first because it is the interesting one, and arrive at a debate about LRU and LFU on a cache with no memory limit set.
Quick Check
Knowledge Check
4 questions - Score 80% to pass
On Zipf-distributed traffic with a cache holding 50 of 5,000 keys, how did LFU compare to LRU?
A nightly batch job walks every key once. What does that actually do to an LRU cache?
Your cache is at 50 entries with LRU and you want a better hit rate. What does the measurement say is worth more?
Why does Redis call its frequency policy allkeys-lfu rather than implementing textbook LFU?
