Cache Eviction Lab

A cache is a small, fast copy of data that lives somewhere slower, and it's always smaller than what it copies. So the moment it's full, every new key that wants in forces a choice: which key already inside should leave? Making that choice is called eviction, and the rule that makes it is the eviction policy. A good policy keeps the keys that will be asked for again, so more requests are hits (answered from the cache) and fewer are misses (sent to the slow source). The share that hit is the hit rate.

Three policies compete here. LRU, least recently used, evicts the key nobody has asked for the longest. LFU, least frequently used, keeps a count of hits for each cached key and evicts the one with the lowest count. W-TinyLFU is the policy behind Caffeine, the Java cache library, and it adds a step the other two lack: before a newcomer may push anyone out, it has to prove it's more popular than the key it would replace. All three get six slots and the same requests, so any difference comes from the rule alone.

W-TinyLFU has more moving parts, so here they are before you meet them. One of its six slots is a window, a tiny LRU that every new key enters first. The other five form the main region, split into two LRU lists: probation, where admitted keys start, and protected, which a key reaches by being hit while in probation. When the window overflows, the key it pushes out is the candidate, and the oldest key in probation is the victim. A count-min sketch, a grid of small counters that estimates how often each key has been requested, scores both. The candidate gets into the main region only if its estimate is strictly higher than the victim's; otherwise the candidate is dropped and the main region doesn't change.

The line at the bottom says what each policy did and why. In the sketch grid, the four counters of the last key are outlined; its estimate is the smallest of the four, because other keys share those counters and can only push them up.

Things to try

1. A loop one key too big

Start with the Loop trace. It reads A, B, C, D, E, F, G in order, then starts over, ten times. That's seven keys for six slots.

LFU also scores 0%. It counts hits only while a key is cached, and a new key starts at 1. Nothing ever hits here, so every count stays at 1, and LFU breaks the tie by evicting the key used longest ago. With every count equal, LFU is LRU.

W-TinyLFU ends at 64%. Step to request 7 and read the gate box. F is the candidate, A is the victim, and the sketch says both have been seen once. One isn't more than one, so F is rejected and the main region keeps A. Ties go to the key already inside. From then on the main region holds five of the seven keys, while the other two take turns in the window and always miss: five hits in every seven requests once warm, and 64% including the warm-up.

2. A scan through a hot set

Switch to Scan. Five keys, A to E, are requested over and over for 40 requests. Then a batch job reads twelve keys, s1 to s12, once each, and the hot keys come back for 30 more requests.

All three caches get 87.5% before the scan, and none gets a single hit during it, since the scan keys are never requested twice. The cost comes afterwards: LRU must miss once on each hot key to bring it back, so it gets 83% over the last 30 requests, against 100% for the other two.

3. When popularity moves

Choose Phase change. A to E are requested for 60 requests, then V to Z take over for the remaining 120, and A to E are never asked for again.

W-TinyLFU recovers, but slowly, and you can watch why. The sketch counts every request, including requests for keys the cache rejected, so V to Z build up counts even while they bounce off the gate. When its count of requests reaches 60, the sketch halves all of its counters and halves that count too, so the next halving comes 30 requests later (the "halves in" figure counts down to it). That's ageing: old popularity decays by half each period, so the first phase's counts shrink while the new keys' counts grow. Step to request 85. X arrives at the gate with an estimate of 5 against B's 4, wins, and B is evicted. That's the first admission of the second phase, and W-TinyLFU ends the phase at 74% against LFU's 20%.

LRU gets 96% over the same stretch. A trace where the hot set jumps all at once and never returns is LRU's best case, because recency is all that matters. A one-slot window is the price W-TinyLFU pays for resisting scans, and section 5.4 of the caching chapter explains how Caffeine adjusts the window size at run time for traces like this one.

4. Skewed traffic

Pick Skewed. It's 150 requests over 16 keys, where key A is twice as popular as B, three times as popular as C, and so on. Most real traffic looks like this. Before you run it, guess the order the three policies finish in.

The final numbers are 57% for LRU, 67% for LFU and 67% for W-TinyLFU. Run it and watch the protected list: A and B reach it early and spend most of the run there, because they're hit often and a rare key can't win a duel against them. LRU loses A whenever six other keys arrive before A's next request, and it misses on A four times over the run against W-TinyLFU's once. LFU does well because popularity never shifts here.

5. Where the small window hurts

Choose Custom and load this trace:

(A B C D E)*4 (X X Y Y Z Z)*3

It's twenty requests that make A to E popular, then a new working set where X, Y and Z each come in pairs. Guess which policy does best on the second part before you step through it.

LRU wins, 79% to 63% for both LFU and W-TinyLFU. In W-TinyLFU, each new key gets its second request while it's still in the window, which is a hit. But only one key fits in the window, and when X is pushed out, its estimate of 2 loses to the victim's 4. Step to request 35: X finally has an estimate of 6, beats the victim, and is admitted, fourteen requests after it first appeared. A bigger window would have kept all three new keys, which is the trade the next section is about.

What this shows

An eviction policy is a bet about the future, and every bet has a trace that beats it. LRU bets on recency, so a loop or a scan defeats it. LFU bets on frequency, so a shift in popularity traps it with yesterday's keys. W-TinyLFU combines the two: the window handles recency, the sketch handles frequency, the gate refuses newcomers that haven't shown they're worth more than the key they'd replace, and halving the counters stops old counts from ruling forever. It loses to LRU when the hot set moves fast and the window is too small to hold the new one.

The design comes from the TinyLFU paper by Gil Einziger, Roy Friedman and Ben Manes, "TinyLFU: A Highly Efficient Cache Admission Policy" (ACM Transactions on Storage, 2017), and the layout and sizes follow Caffeine. To keep every number small enough to check by hand, the lab simplifies in five places:

• The window size is fixed. Caffeine starts with a window of 1% of the cache, which rounds to one slot here, then moves the split between window and main with a hill climber that follows the hit rate. The lab never moves it, which is why experiments 3 and 5 go the way they do.
• The sketch is a plain grid. Caffeine packs its 4-bit counters into 64-bit words and sizes the table to the cache's maximum. Here it's four rows of 16 counters, with each key hashed to one counter per row. The estimate is still the minimum of four counters, each counter still stops at 15, and the first halving still comes after ten counted requests per slot, which is 60 for six slots.
• The ageing arithmetic is rounder. When Caffeine halves, it also corrects its request count for the bits lost by halving odd counters. The lab simply halves the count.
• No random admission. Caffeine lets a candidate with an estimate of 6 or more that loses the duel in anyway, one time in 128, so an attacker can't pin a victim in place by making it look popular. The lab is deterministic and leaves that out.
• No doorkeeper. The paper also describes a doorkeeper, a small filter in front of the sketch so that keys seen only once don't take up counters. The lab leaves it out.

The LFU here is the common textbook version: it counts only while a key is cached and breaks ties by age.

Back to the chapter

This lab goes with Caching, Properly. Section 4, "What to forget first", covers LRU, the scan and loop patterns, and LFU's staleness. Section 5, "Admission: deciding who gets in", builds W-TinyLFU piece by piece, with Caffeine's sketch and admit() code, and section 6 compares the policies on a million requests.