Scan-resistant eviction
LRU evicts the entry that was used longest ago. A scan that reads 1 million other keys can push out 1,000 hot keys, and the hit ratio falls. LFU evicts the entry that is used least often, so the hot keys stay.
See it on the board
The same traffic runs on two boards. The simulator measured both when this page was built.
| Measure | Goal | LRU eviction | LFU eviction |
|---|---|---|---|
| Hit ratio (Hot) | at least 90% | 43.2% Fail | 99.749% Pass |
| p99 latency (Hot) | under 150 ms | 2.7 s Fail | 23 ms Pass |
| Monthly cost | 54 USD/mo | 54 USD/mo | |
| Error rate | 51.4% | 0.3% |
Key numbers
| Number | Value |
|---|---|
| Default cache size | 0.25 GB |
| Memory overhead for each cache key | 60 bytes |
| Reads per second, one cache | 100,000 ops/s |
LFU during the scan · hot reads hit 90% · 500 reads/s to the database
How it works
A cache has a limited size. When it is full, each new entry pushes an old one out. The eviction policy decides which one leaves.
Least recently used (LRU) removes the entry that was used longest ago. It works well when recent use predicts future use. It has a weakness: a scan. A scan reads many keys once each, for example a nightly report. Each scanned key becomes the most recent entry. It pushes out the older keys, including the hot ones that users read all day.
In the mini board a 2 MB cache serves 1,000 hot keys at 5,000 reads/s. From 0:20 to 0:50 a nightly scan reads one million other keys. With LRU, the scan flushes the hot keys. The hot-read hit ratio falls to 43 percent, and the database takes the reads.
Least frequently used (LFU) counts how often each entry is read, and it removes the entry with the lowest count. A scanned key is read once, so its count is low, and it leaves first. The hot keys have high counts, so they stay. The hit ratio of the hot reads stays above 90 percent through the scan.
LFU has a cost too. Old popular keys can stay after they stop being popular, so a good LFU lets the counts decay over time.
In the levels you choose the policy that keeps the hot keys through a scan.