Admission beats eviction, and the asymmetry is structural

TinyLFU is an admission policy. Its real contribution is not a better eviction rule. It is the observation that the right question is "should this entry ever have come in?" and not "what should I throw out?". The two questions have very different costs.

Why eviction is expensive

Eviction needs O(C) metadata for the C resident entries, updated on every access. That last part is the hidden cost, and in a concurrent system it dominates:

Every read changes the recency list (it moves the entry to the front). So the head of the list is a shared resource that all threads fight over. This is the same kind of coherence cost as false sharing (several cores writing different variables that sit in one CPU cache line, so the line bounces between them) and lock contention in a database. It is the reason for three designs:

• CLOCK: approximate LRU with one bit per page and no list updates;
• Redis: it samples a few random keys and evicts the best candidate among them, rather than keeping an exact order;
• Caffeine (a Java cache library): it puts accesses into a buffer and applies them in batches, off the read path.

Why admission is cheap

Admission needs O(bits) per key across the whole key space, updated approximately. The parts are:

• a count-min sketch: a small table of counters that estimates how often each key has been seen, a few bits per counter (a sketch is a compact, approximate summary);
• a doorkeeper: a Bloom filter (a tiny structure that answers "have I seen this before?") that catches the long tail of keys seen only once;
• periodic halving of all counters.

Total metadata is about ten bits per cache entry for near-optimal decisions.

So: eviction pays exact recency over a bounded set of residents, at a cost proportional to that set, with contention on the read path. Admission pays approximate frequency over an unbounded key space, at a constant total cost, off the critical path. That asymmetry is why admission is the better lever, and why W-TinyLFU is a derived design and not an invented one.

The periodic halving has a useful side effect. It makes the sketch a decaying frequency estimate, which brings recency back into a frequency policy. That answers the classic flaw of plain LFU (least frequently used), which is pollution by items that were once popular and will never return.

W-TinyLFU has three components: a small LRU window for bursty new traffic, a large main region governed by frequency for stable popularity, and a sketch-gated door against one-shot traffic. This is exactly the decomposition that What makes data cacheable demanded: one component per traffic stream (the three-stream split into bursty, stable and one-shot requests). The architecture is not clever. It is matched to the structure of the problem.

Scan resistance, defined exactly

Scan resistance is usually described loosely. Here is a precise definition. Under an admission filter, scanned items never gather enough frequency to pass the gate, so they never enter the main region. Damage is bounded by the window size, independent of scan length. Under LRU the damage is min(scan length, C).

This is the difference between a bounded failure and an unbounded one. It is a difference of kind, not of degree.

Compression: Admission is O(bits) over all keys and off the read path. Eviction is O(C) with contention on the read path. So guard the door, and scan damage falls to one window regardless of scan length.