LRU vs LFU
LRU keeps the keys that were used last. LFU keeps the keys that are used most often. When a scan reads 1 million cold keys through a 2 MB cache, LRU pushes out the 1,000 hot keys and LFU keeps them.
LRU during the scan · hot reads hit 43% · 2,850 reads/s to the database
LFU during the scan · hot reads hit 90% · 500 reads/s to the database
Case 1
A 2 MB cache serves 1,000 hot keys. From 0:20 to 0:50 a scan reads 1 million other keys. The hot hit ratio must stay above 90 percent.
| Measure | Goal | LRU | LFU |
|---|---|---|---|
| Hit ratio (Hot) | at least 90% | 84.9% Fail | 99.749% Pass |
| p99 latency (Hot) | under 150 ms | 1.9 s Fail | 23 ms Pass |
| Monthly cost | 48 USD/mo | 48 USD/mo | |
| Error rate | 32.6% | 0.4% |