The two textbook eviction policies fail in opposite directions. LRU remembers only recency, so a burst of one-off reads, like a table scan, flushes out keys that are genuinely hot. LFU remembers only frequency, so a key that just became hot gets evicted before it can build up enough count to compete with long-time favorites. Can one policy avoid both?
W-TinyLFU, the policy in the Java cache Caffeine, does it by splitting the cache in two:
- Window: a small LRU region. Every new entry lands here without having to earn it.
- Main: the bulk of the cache. When an entry falls out of the window, it gets in only if its estimated frequency beats that of the main region's eviction candidate. Otherwise it's dropped.
Each failure is handled by the simplest tool that fits. A hot newcomer spends its time in the window collecting hits, so by the time it's evicted from there it can win the admission check. A scan can't do damage, because the window is small and plain LRU: one-off keys churn through it and then lose at the admission check, never touching the main region.
The frequencies don't come from a counter per key, which would cost as much memory as the cache itself. They come from a compact approximate sketch, in the family of a count-min sketch, whose counters are periodically halved so that old popularity fades.
I got to the window myself: first as a grace period protecting new entries from eviction, then, since an unbounded protected set is its own memory leak, as a small pool evicted by LRU. What I hadn't thought of was estimating frequency with a sketch instead of exact counts.
The paper is Einziger, Friedman and Manes, "TinyLFU: A Highly Efficient Cache Admission Policy".