LRU

LRU evicts the key that was used longest ago. Every hit moves a key to the front of a recency list. Eviction takes from the back. The bet is that recency predicts reuse, that a key touched recently will be touched again soon, and on most real workloads that bet pays.

It is the default answer for a reason: it is simple, it adapts immediately to changes in what is popular, and it is hard to beat by a large margin. It is also easy to beat by a small one, which is what most of the other policies in this domain are for.

When to use it

• As the default, unless you have a specific reason not to. On the canonical Zipf trace, LRU captures most of the achievable hit rate.
• When the popular set changes over time. LRU forgets at exactly the right rate: a key that stops being used drains out on its own.
• When you need behaviour that is easy to reason about during an incident. “It keeps what you touched most recently” is a sentence an on-call engineer can hold in their head at 3am, which is not nothing.
• When entry metadata must stay small: two links per entry and no counters.

When not to use it

• When scans pass through the cache. A sequential sweep of fresh keys is, to LRU, a stream of very recent keys, so it evicts the entire working set to cache data it will never see again. This is LRU’s defining failure, and it is why SIEVE, S3-FIFO, ARC and 2Q exist. The scan-heavy benchmark trace exists to show it.
• Under heavy concurrency. Every hit is a write to shared list state, so reads contend on a lock or on atomics. CLOCK and SIEVE approximate LRU without writing on the hit path.
• When popularity is strongly skewed and stable. LRU discards a key used a thousand times because a one-hit wonder arrived more recently. LFU and W-TinyLFU will keep it.
• On workloads where the working set is larger than the cache. LRU then evicts each entry just before it is reused, and the hit rate collapses towards zero: the pathological case, a loop over capacity + 1 keys, gives LRU exactly zero hits where FIFO would give some.

How it works

A hash map from key to slot, and a doubly linked list over slots in recency order.

onAccess(key, hit):
    if hit:  move slot(key) to front
    else:    slot = allocate(); link slot at front

evict():
    slot = tail
    unlink slot; forget its key
    return key

The links are two Int32Arrays indexed by slot rather than pointers between objects, so a hit is a handful of array writes and allocates nothing.

Parameters

Complexity

O(1) time for access and eviction. O(n) space: one map entry plus two 32-bit links per entry.

C memory: 46.8 bytes per entry at capacity 1000, measured with pb_cache_lru.memory_bytes: 8 for the key, 8 for the two list links, 4 for the free-slot stack, and about 27 for the hash table, which is sized at twice the entry count so probe chains stay short. That is nearly six times FIFO’s 8.0 bytes, and the hash table is most of the difference: knowing where a key is costs more than remembering the order it arrived in.

The cost that matters operationally is not the time bound but the write on hit: every read mutates the list, which is why LRU scales badly across cores and why the CLOCK family exists.

Source

Folklore. The idea is older than the literature that analyses it. Bélády’s 1966 paper on optimal replacement already treats LRU as the known practical alternative.

Related: FIFO is LRU without the move-to-front. CLOCK approximates LRU with one bit per entry and no write on hit. LFU makes the opposite bet, on frequency rather than recency. ARC and 2Q balance the two.

Notes

No patents.

“LRU” in the wild often means an approximation, because exact LRU’s write-on-hit is expensive at scale: sampled LRU in Redis, CLOCK in operating systems, segmented LRU in CDNs. This entry is exact LRU: the reference point those approximations are measured against.