Commentary: lru-cache

LFU beats LRU by 11 points — until the popular set shifts once, and LFU falls to 4.16% and never comes back. A study guide for lru_cache.py.

cd lru-cache
python3 demo.py            # the aha (§6)
python3 test_lru_cache.py  # pins every number this page quotes

1. Orientation

This toy implements two cache eviction policies — LRU (least recently used) and LFU (least frequently used) — each in O(1) per operation, and feeds them byte-identical request traces.

On a stationary popularity distribution, LFU wins comfortably, which is what everyone expects: frequency is more information than recency, so a policy that uses it should do better. Then the popular set shifts once. Same code, same capacity, same 90/10 traffic shape, twenty hot keys swapped for twenty different ones. LRU doesn't notice. LFU falls from 87.21% to 4.16% and never recovers — not in the 20,000 requests that follow, and not in 400,000.

By the end you should be able to:

• draw the two data structures from memory, and say why each gives O(1) eviction without ever scanning the cache;
• explain why LFU's collapse is arithmetic, not a bug — and compute, from the residents' access counts alone, exactly how many hits a new hot key would need to earn a slot;
• name the boundary condition where LRU is the one that goes to zero and a coin flip beats it;
• recognise, from a hit-rate graph alone, which of these two failure modes a cache in front of you is having.

The last one is the payoff. "Our cache hit rate fell off a cliff and never came back" is a production incident, and its cause is usually one of the two shapes on this page.

2. The problem this mechanism exists to solve

A cache is a bet: that a small fast store, holding a fraction of a large slow store, can serve most of the requests. The bet is only good if the fraction you keep is the fraction you'll be asked for. Since capacity is finite and the request stream is not, every cache must continuously answer one question:

That decision is the eviction policy, and it is the whole cache. Everything else — the hash map, the memory layout, the wire protocol — is bookkeeping. The theoretically perfect answer is known and useless: Bélády's MIN algorithm evicts the item whose next use is furthest in the future, which requires knowing the future. Every real policy is a heuristic that guesses at MIN from the past, and they differ in which summary of the past they keep:

• Recency. "You were used recently, so you'll be used again soon." Cheap, adapts instantly to change, and remembers nothing about how often you were useful. This is LRU.
• Frequency. "You were used a thousand times, so you're valuable." Uses strictly more information, is optimal when popularity never changes, and has no way to notice that the world moved on. This is LFU.

These pull against each other, and the tension is not academic. A cache that weights recency is fooled by a one-off scan; a cache that weights frequency is fooled by yesterday's hits. The observation this toy is built to force:

3. Background you need

None of it is deep, but the commentary leans on all of it.

The two that carry the result are the first and the third — not because the collapse is a data-structure bug, but the opposite: both structures are correct and O(1), and the failure is entirely in the ordering they compute. If you internalise one row, take the third: min_count and the buckets are what make LFU's arithmetic visible, and once you can see the counts, the collapse in §6 is not surprising at all — it is subtraction.

4. The mental model

Before any code. Both caches answer "which resident dies?", but they keep different summaries of the past, and the summary is the policy.

The slogan, before you read a line of code:

• LRU remembers only an order. It has no idea whether k7 was used once or a million times. That information was thrown away — and throwing it away is what lets LRU change its mind for free.
• LFU remembers a score, and the score is cumulative. It is strictly more information. But there is no term in it for when, and nothing in the structure ever decreases a count.

Everything in §6 follows from that last clause.

5. Reading the source

166 lines, two classes, no imports. Read them in this order.

5.1 The determinism decision, in the docstring

"""Two cache eviction policies, side by side: LRU (least-recently-used) and
LFU (least-frequently-used). Both expose the same interface — get(key) and
put(key, value) — and both count hits, misses and evictions.

Neither reads a clock nor an RNG. Eviction order is a pure side effect of the
data structure: for LRU, position in a doubly linked list; for LFU, an
integer count plus insertion order within a count. Same trace, same numbers,
every run.
"""

The most consequential decision in the toy is the one it doesn't make: there is no clock in this file, and no randomness. "Least recently used" sounds like it needs timestamps, and plenty of real implementations use them (Redis stores a 24-bit clock per object). This one doesn't: position in a list is the timestamp, with the ordering and none of the arithmetic.

That buys the thing this whole page depends on. Run demo.py twice and diff it — the output is byte-identical, including a hit rate quoted to two decimal places, because the caches are pure functions of the trace. The only RNG in the toy lives in demo.py behind an explicitly seeded random.Random(SEED), so even the traces are fixed. A cache whose behaviour depends on wall-clock timing can't have a commentary written about it, because no number in it would be checkable.

5.2 Node, and why there are two of them that hold nothing

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        # Sentinel head and tail. They hold no data; they exist so _unlink
        # and _push_front never have to check for None neighbours, which is
        # where every hand-written linked list goes wrong.
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

Two nodes that are never in self.map and never hold a key. They are pure overhead in memory and pure profit in code: with sentinels, every node in the list has a real prev and a real next, always. No first-element case, no last-element case, no empty-list case.

Compare the two versions of the same operation. Without sentinels, removing a node is (this block is not from the source — it's the code the sentinels delete):

if node.prev is None:      # it was the head
    self.head = node.next
    if self.head is not None:
        self.head.prev = None
else:
    node.prev.next = node.next
    ...                    # and the mirror image for the tail

With them, it is §5.3. That is the entire argument for two wasted objects, and it is why Node.__init__ defaults both key and value to None: a sentinel is exactly a node that is never in the map.

5.3 _unlink and _push_front — four lines that are the whole policy

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

_unlink never searches for the node — it is handed the node, by the hash map, and splices it out in constant time. This is the whole reason the list is doubly linked. In a singly linked list you cannot remove a node you're standing on, because you can't reach its predecessor without walking from the head, and that walk is O(n). The prev pointer costs 8 bytes per entry and buys the O(1) that makes LRU practical at all.

Note also what _push_front does not do: it doesn't touch self.map. The map holds identity ("where is this key?"), the list holds order ("who dies next?"), and the two are updated independently. Every operation below is some combination of these four lines.

5.4 LRUCache.get — the read that mutates

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            self.misses += 1
            return None
        self.hits += 1
        self._unlink(node)
        self._push_front(node)
        return node.value

Two lines in a read path rewrite four pointers. That's the policy: without them you have a cache that evicts in insertion order — FIFO — and a get that tells you nothing about the future. I ran that variant rather than asserting it:

Deleting two lines from a read costs 4.6 points on the Zipf trace and 7.9 on the hot/cold one. Load-bearing.

It is also the line with the highest production cost in the file. A read that writes is a read that needs a lock, that dirties a cache line, that cannot be served from a read-only replica. This is precisely why Redis does not do it — it stamps a per-object clock and samples a handful of keys at eviction time instead, trading exactness for never having to maintain a global order.

5.5 LRUCache.put — eviction is just "read the tail"

        if len(self.map) >= self.capacity:
            victim = self.tail.prev
            self._unlink(victim)
            del self.map[victim.key]
            self.evictions += 1
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

There is no eviction algorithm. There's no scan, no comparison, no priority queue — the victim is wherever the tail happens to point, and it is correct because every get has been maintaining the invariant all along. The cost of LRU is paid on every read, so that eviction is free. That trade is the design, and §6.5 is the bill.

del self.map[victim.key] is why Node stores its own key. The node knows its position; only the key can find its map entry. Drop that field and the victim is unreachable in the map, and you leak an entry per eviction.

The comparison is >=, not >. With > the cache holds capacity + 1 entries — I checked, and it does exactly that:

A quiet one-key overrun. It would never show up in a hit-rate graph; it shows up in an out-of-memory kill six months later.

5.6 LFUCache.__init__ — three dicts instead of a list

    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}
        self.counts = {}
        self.buckets = {}  # count -> {key: None}, insertion-ordered
        self.min_count = 0

The naive LFU stores a count per key and, on eviction, calls min(counts, key=counts.get) — O(n) per eviction, which the ARC paper politely records as LFU's "logarithmic implementation complexity" even in its better forms. buckets removes the scan: all keys sharing a count live in one bucket, min_count names the lowest occupied bucket, and eviction is "take something out of buckets[min_count]."

Each bucket is a dict used as an insertion-ordered set — Python dicts have preserved insertion order since 3.7, so next(iter(bucket)) is the key that arrived at that count first. That makes the tie-break deterministic, which matters: at capacity 20 with a 1000-key Zipf trace, ties at low counts are constant, and an arbitrary tie-break would make every number on this page irreproducible. Two alternative rules, run against the same traces:

Worth 2.3 points on the Zipf trace, so it is load-bearing for the numbers — "LFU" alone does not specify a hit rate. It is not load-bearing for the collapse in §6.2, though: all three tie-breaks produce phase 2 = 4.16%, identical to two decimal places. That is a genuinely useful negative result, and I would have guessed wrong: the tie-break decides which of the equally worthless keys revolves through the one free slot, and §6.3 shows why that cannot matter.

5.7 _bump — the line that never decreases

    def _bump(self, key):
        count = self.counts[key]
        bucket = self.buckets[count]
        del bucket[key]
        if not bucket:
            del self.buckets[count]
            # The only bucket that can empty and matter is the minimum one,
            # and the key that just left it went to exactly count + 1.
            if self.min_count == count:
                self.min_count = count + 1
        self.counts[key] = count + 1
        self.buckets.setdefault(count + 1, {})[key] = None

Move one key from bucket c to bucket c+1, and if that emptied the minimum bucket, the new minimum is exactly c+1 — because the key that left went precisely one step up. No search.

The if self.min_count == count guard is doing real work. Raise min_count unconditionally and the cache stops finding its own minimum; eviction then picks victims out of an arbitrary bucket, and LFU degenerates into something notably worse than FIFO:

Load-bearing, and it fails silently — the cache still returns correct values, still respects capacity, and simply throws away the right keys. This is the characteristic bug of hand-rolled LFU.

Now read the whole method again for what is missing: no branch decreases self.counts[key], and nothing here or anywhere in the file has a notion of elapsed time. A count is a lifetime total. That absence is not an oversight; it is the definition of LFU, and it is the aha.

5.8 LFUCache.put — a newcomer is worth 1

        if len(self.values) >= self.capacity:
            bucket = self.buckets[self.min_count]
            victim = next(iter(bucket))
            del bucket[victim]
            if not bucket:
                del self.buckets[self.min_count]
            del self.values[victim]
            del self.counts[victim]
            self.evictions += 1
        self.values[key] = value
        self.counts[key] = 1
        self.buckets.setdefault(1, {})[key] = None
        # A brand-new key has count 1, so the minimum is 1 again. Forgetting
        # this line is the classic LFU bug: min_count drifts upward and the
        # cache evicts a frequently used key while a fresh one sits at 1.
        self.min_count = 1

self.counts[key] = 1 and self.min_count = 1 are the two most important assignments in the file, and between them they produce §6.2 entirely.

Every arriving key is stamped with the lowest possible score and dropped into the lowest bucket — which is also, by definition, the bucket eviction reads from. A new key is admitted directly into the death row it will be taken from on the very next miss. In a stable workload that is exactly right: it is how LFU refuses to let a one-hit wonder displace something valuable. What it costs is §6.

The self.min_count = 1 line is not optional bookkeeping. Delete it and the cache doesn't degrade, it crashes — min_count keeps pointing at a bucket that was deleted:

Load-bearing, loudly, which is the good kind. Compare with §5.7's guard, which is equally load-bearing and silent — a nice illustration that "does it crash?" is uncorrelated with "does it matter?"

6. The demo, and what it proves

demo.py runs three traces. All randomness is a seeded random.Random, so these numbers reproduce exactly.

6.1 The expected result: LFU wins

Trace 1 is stationary Zipf — key i drawn with weight 1/i, 1000 keys, 20,000 requests, capacity 20. Popularity never changes.

python3 demo.py

Exactly the textbook outcome, and worth deriving so it doesn't feel like magic. Under a Zipf-1 distribution over 1000 keys, the 20 most popular keys account for (1 + 1/2 + … + 1/20) / (1 + 1/2 + … + 1/1000) = 3.5977 / 7.4855 = 48.1% of all requests. A cache of 20 that simply identifies and holds those 20 keys forever gets ~48%; LFU gets 43.11%, close to that ceiling and short of it only by the warm-up it spends discovering which keys they are.

LRU can't hold them, because it isn't trying to. Every request for an unpopular key — and 51.9% of requests are for unpopular keys — is promoted to the front and pushes a genuinely popular key one step toward the tail. LRU spends most of its 20 slots on keys it will never see again.

If you stop reading here, you have the conventional wisdom: frequency is more information than recency, so use it.

6.2 The flip

Trace 2 has the same shape throughout: 90% of requests to a 20-key hot set, 10% spread uniformly over all 1000 keys. The only thing that happens is that after 20,000 requests, the hot set is replaced by 20 different keys. Same cache objects, same capacity, same code.

In phase 1, LFU beats LRU by 13.3 points — the §6.1 result again. In phase 2, LFU is beaten by 70 points, and the per-window row shows it isn't a transient: ten consecutive windows, no trend, no recovery. LRU's row doesn't move at all; it re-learns the new hot set inside the first 2000-request window and carries on.

The final columns say why. LFU is still holding 19 of the 20 keys that were hot in phase 1 and are never requested again. LRU is holding 19 of the 20 keys that are hot now.

6.3 The derivation: 19 frozen slots and one revolving door

This is the part worth carrying away, and the demo prints the arithmetic rather than asking you to trust it.

Now do the subtraction. A newly hot key arrives, misses, and is admitted at count 1 (§5.8). The weakest incumbent has 851. For the newcomer to outrank anybody, it needs 850 more hits while resident. But min_count is now 1, its bucket contains exactly one key — itself — so the very next miss evicts it. With 90% of traffic spread over 20 hot keys, the probability that the next request is a repeat of the key just admitted is 0.9 / 20 = 4.5%; the other 95.5% of the time, a different key misses and the newcomer is gone.

The demo hand-feeds two requests to make it concrete:

So the cache is not 20 slots. It is 19 frozen slots and one revolving door, and the demo confirms that reading against the full 20,000-request phase:

Nineteen thousand one hundred and sixty-nine evictions, and not one of them touched the nineteen dead keys — their counts crept up by only ~2 apiece, from the trickle of cold traffic. All 19,169 went through a single slot; 869 distinct keys were resident at some point during phase 2, and 850 of them came and went through that one door.

That also derives the 4.16%. Categorising phase 2's 831 hits by where they came from:

796 of the 831 are the revolving door catching a repeat — 796/18070 requests to the new hot set = 4.4%, against the 4.5% predicted above. The other 35 are cold requests that happened to land on one of the 19 fossils. LFU's entire phase-2 hit rate is the probability that a key is requested twice in a row.

Two more runs to close it off. The collapse is caused by the shift and by nothing else — replay phase 2 with the same hot set and LFU is fine:

And "never recovers" means never. Extending phase 2 to 400,000 requests — twenty times the whole trace:

Flat. There is no recovery point to identify, because there is no path to recovery: escaping the revolving door requires 850 consecutive hits on one key without an intervening miss, and its probability is 0.045⁸⁵⁰.

6.4 The same mechanism, visible before the shift

Look again at the phase-1 numbers. LFU got 87.21%, but the ceiling for any 20-slot cache on that trace is 90.18% (18,056 of 20,000 requests go to the hot set, minus 20 compulsory first-touch misses). The 3-point gap looks like warm-up. It isn't:

Nineteen hot keys each missed once. The twentieth, k17, lost the early race for the last slot and spent the entire phase in the revolving door — 593 misses on a key requested 857 times, in a cache that had room for it and never let it back in. And 593/20,000 = 2.97 points, which is the gap: 90.18% − 2.97% = 87.21%. The whole shortfall is one key.

That is the same failure as §6.3, at 1/20th scale, happening while LFU is winning. It also gives the cleanest one-line statement of the difference:

(LRU's phase-1 misses split as 3273 on the 20 hot keys — 163.7 each — and 1938 on cold keys. That's the tax: every cold request evicts something, and with recency ordering the something is whichever hot key has been quietest.)

6.5 The boundary condition: where LRU is the one that fails

The effect above vanishes — and reverses — on a workload with no popularity structure at all. Part 3 of the demo loops over a working set slightly larger than the cache:

Random replacement — a coin flip, no state, no linked list, no counters — gets 92.80%, because it is merely usually wrong instead of always wrong. That's the honest boundary on everything above: recency and frequency are both bets on structure in the request stream, and a scan has none. Redis documents exactly this, recommending allkeys-random "when you expect all keys to be accessed with roughly equal frequency… when your app reads data items in a repeating cycle."

6.6 The numbers are pinned by tests

python3 test_lru_cache.py

test_the_shift_collapses_lfu_and_not_lru asserts the four exact hit counts behind §6.2, and test_lfu_holds_nineteen_frozen_slots_through_the_shift asserts the 19 frozen keys, the 19,169 evictions, and that none of the frozen keys was among them. If someone edits the policy, this page fails loudly instead of rotting quietly.

7. Design decisions and roads not taken

7.1 Why a hand-built linked list rather than OrderedDict

Python ships an LRU cache. OrderedDict.move_to_end(key) plus popitem(last=False) is a five-line LRUCache, and functools.lru_cache is already in the stdlib and faster than anything here. Using either would have deleted the toy: the linked list is the mechanism this toy exists to show. move_to_end is a doubly linked list splice with a nicer name — the one in CPython's OrderedDict — and hiding it behind a method call hides precisely the thing worth understanding, which is that get performs a write of four pointers and that this is where LRU's cost lives (§5.4).

7.2 Why LFU has buckets instead of min(counts)

A one-line eviction — min(self.counts, key=self.counts.get) — would be easier to read and behaviourally identical. It's O(n) per eviction, and in the demo LFU performs 19,169 evictions against 20 residents, so the toy would still finish instantly. It's out for two reasons. First, it would make LFU look more expensive than LRU as a matter of principle, when in fact O(1) LFU is a known and simple structure. Second — and this is the real reason — the buckets are what make the arithmetic visible. min_count and the count buckets are the state the §6.3 derivation reasons over; with a min() call the collapse becomes something you're told rather than something you can read off a dump of the residents.

7.3 Why no aging or decay in LFU, when everyone knows to add it

Because its absence is the toy. Every production LFU has a decay term. Redis exposes it as lfu-decay-time (default: halve the counter every minute) and antirez's own writeup of it says why in one sentence — "a key with a high score needs to see its score reduced over time if nobody keeps accessing it." Adding decay here would move the whole point of the page into a tunable constant.

That said, the cheapest known fix is one line, and not running it would have been a missed opportunity. Admit newcomers at min_count rather than at 1 — a newcomer inherits the score of the key it replaced, which is the trick used by LFU-with-dynamic-aging:

It works, eventually — the last window reaches 86.7% and the cache ends up holding the right keys. But look at the first seven windows: identical to broken LFU. The fix takes ~14,000 requests to bite, against LRU's ~2,000, and the phase-2 average is still 57 points behind LRU. This is why the real answer isn't a patch to LFU (§7.4).

7.4 Why not ARC or W-TinyLFU, which solve exactly this

Because they're the answer to this page, and the page has to pose the question first. Both exist precisely because of the failure in §6:

• ARC (Megiddo & Modha, IBM Almaden, 2003) keeps two lists — one for entries seen once (recency) and one for entries seen more than once (frequency) — plus two ghost lists of recently evicted keys, and moves the boundary between them based on which ghost list is getting hits. It is self-tuning, with no parameters. Their paper names this toy's failure in one sentence: LFU "is oblivious to recent history, and it adapts poorly to variable access patterns by accumulating stale pages with past high-frequency counts, which may no longer be useful." Their OLTP table shows the flip in the wild — at a 1000-page cache, LRU 32.83% and LFU 27.98%.
• W-TinyLFU (Einziger, Friedman & Manes) puts a small LRU window in front of a frequency-based main cache, and sketches frequencies in a Count-Min structure with periodic halving — the decay from §7.3, made cheap enough to run on every key. It's what Caffeine ships.

Both are 10× this toy's budget. Naming them is more useful than half-building one: if you have measured the §6.2 shape in production, those are the two things to reach for.

7.5 Why the values are all 1

Every put in the demo stores the integer 1. The toy is about which key survives, and a realistic value would add serialization, sizing, and cost weighting without changing a single eviction decision. It also removes an ambiguity: get returns None on a miss, and if values could be None the read-through pattern in demo.replay would be wrong.

7.6 Why two classes and no shared base

They share no code. Their only common ground is get/put, and an abstract base class would imply a family resemblance that doesn't exist — one is a linked list, the other is three dicts. RandomCache in demo.py deliberately lives outside lru_cache.py for the same reason: it's a control for §6.5, not a third policy the toy is teaching.

8. What's simplified vs. the real thing

• No concurrency. get mutates the list on every hit (§5.4), so two threads reading the same key can corrupt the links and lose entries. Real caches either lock (functools.lru_cache holds a lock across its bookkeeping) or avoid the global order entirely — Caffeine buffers reads in per-thread ring buffers and replays them onto the policy in batches, so a read never blocks.
• No approximation. This LRU is exact, which costs pointer writes on every read and 16 extra bytes per entry. Redis instead stores a per-object clock, samples maxmemory-samples (default 5) keys at eviction time, and evicts the oldest of the sample — no list, no per-read write, and the documented result is "virtually equivalent for an application using Redis." Its LFU is likewise approximate: an 8-bit logarithmic Morris counter rather than the unbounded integers here.
• No memory accounting. Capacity is a count of keys. Real caches limit bytes, so one 10 MB value can evict a thousand small ones, and eviction becomes a loop rather than a single victim.
• No admission policy. Everything that misses is inserted. This is the single biggest gap: modern designs (TinyLFU, S3-FIFO) decide whether a missed key deserves to enter at all, which is what makes them scan-resistant. §6.5's collapse would not happen to a cache that declines to admit a key it has never seen before.
• One process, one shard. Two servers each running this hold two independent caches, so the effective hit rate is worse than one cache of twice the size, and a write to one leaves the other stale. Real fleets shard by key hash so each key has one home.
• No TTLs, no invalidation. Entries leave only by eviction. Production caches must also expire on time and drop keys whose backing data changed — and eviction and invalidation interact badly, since a key can be evicted before its invalidation arrives.

9. Check yourself

Answer before expanding. Every answer is derivable from the source, and every one below was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Megiddo & Modha: Outperforming LRU with an Adaptive Replacement Cache Algorithm (IEEE Computer, 2004) — the paper behind ARC, and the best single source for this page's argument. It states the failure in §6.2 outright: LFU "is oblivious to recent history, and it adapts poorly to variable access patterns by accumulating stale pages with past high-frequency counts, which may no longer be useful." Its OLTP comparison table shows LFU losing to plain LRU on real traces. Start here.
• Wikipedia: Adaptive replacement cache — the shorter version: T1/T2 for recency and frequency, ghost lists B1/B2 of evicted keys, and a target size that slides toward whichever half is taking ghost hits. The trick to take away is the ghost list — remembering what you evicted is how a cache learns that its policy is wrong.
• Redis: Key eviction — a production cache you can read the config of. maxmemory-samples (why Redis has no linked list), lfu-log-factor and lfu-decay-time (the decay this toy deliberately omits), and the allkeys-random recommendation that is §6.5's boundary condition stated as advice.
• antirez: Random notes on improving the Redis LRU algorithm — how Redis's approximated LRU and LFU were actually built and measured, including why counters must decay: "a key with an high score needs to see its score reduced over time if nobody keeps accessing it."
• Einziger, Friedman & Manes: TinyLFU, a Highly Efficient Cache Admission Policy — frequency as an admission decision rather than an eviction one, using a Count-Min sketch with periodic halving. W-TinyLFU adds the small LRU window that handles the workload §6.2 breaks.
• Caffeine wiki: Efficiency — W-TinyLFU measured against ARC and LIRS on real traces. Notes plainly that "in typical workloads LRU is not optimal and may have a poor hit rate in cases like full scans" — §6.5.
• S3-FIFO: FIFO queues are all you need for cache eviction (SOSP '23) — the contrarian result: three FIFO queues, no linked-list reordering on reads, beating LRU by quickly demoting "one-hit wonders." Read it against §5.4, whose promote-on-get is exactly the cost S3-FIFO refuses to pay.
• Wikipedia: Cache replacement policies — the map of the whole space: LRU, LFU, LFUDA, 2Q, LIRS, Bélády's optimal MIN, random replacement. Good for placing any policy you meet.
• Wikipedia: Bélády's anomaly — the formal version of §9 Q4, including why stack algorithms are immune and the result that the anomaly is unbounded for FIFO.
• Python: functools.lru_cache — the stdlib version of half this toy, and the road not taken in §7.1. Note the documented thread-safety caveat: the cache is coherent, but the wrapped function can still be called twice for the same key.