Cache Replacement Policies¶

Why the policy matters¶

Every storage engine has caches — the buffer pool, the block cache, the table cache, the OS page cache under all of them. When a cache is full and a new item must be admitted, the replacement policy decides what to evict. Because a miss can cost 1000x a hit (an SSD read versus a memory access; see Memory Hierarchy and CPU Cache), small differences in hit ratio dominate performance.

Worked example. Hit cost 100 ns (in-memory block, already decompressed), miss cost 100 µs (SSD read + decompress).

Hit ratio	Average access time	Relative
90%	0.9 × 0.1 + 0.1 × 100 = 10.1 µs	1x
95%	0.95 × 0.1 + 0.05 × 100 = 5.1 µs	~2x faster
99%	0.99 × 0.1 + 0.01 × 100 = 1.1 µs	~9x faster

Going from 90% to 99% cuts the miss rate by 10x, so latency improves almost 10x. Always reason in terms of miss rate.

Measured comparison¶

The numbers in this page come from a simulation written in Go: 100,000 distinct keys accessed with a Zipf distribution (skew 0.9, so a minority of keys gets most requests), a cache of 5,000 entries (5% of keys), 2 million requests. The second workload interleaves one-time sequential scans (keys never seen again) arriving in bursts of 20,000 — like a full-table scan or a compaction reading through the cache — which made up 23.4% of its requests. Go's math/rand Zipf generator only supports skew above 1, so the simulation samples from a precomputed CDF with binary search.

Policy	Zipf only	Zipf + scans	Hit ratio on the Zipf requests in the scan workload
LRU	51.4%	38.5%	50.2% (scan pollution)
CLOCK	52.6%	39.2%	51.1%
2Q (simplified)	58.1%	44.4%	57.9% (unaffected)
S3-FIFO	59.8%	45.7%	59.7% (unaffected)

Scan requests can never hit (each key is used once), so the overall hit ratio in the second workload is bounded by the share of non-scan requests. LRU and CLOCK also lose ground on the regular traffic because the scans push hot keys out; the scan-resistant policies lose almost nothing. Even without scans, frequency-aware policies beat LRU by 6–8 points here — a ~15% lower miss rate.

The baseline: Belady's optimal (OPT)¶

The theoretically optimal policy evicts the item whose next use is furthest in the future. It is impossible online (it needs the future), but it is computable from a recorded trace and serves as the upper bound for evaluating real policies on that trace.

LRU: least recently used¶

Evict the item not accessed for the longest time. Implementation: a doubly linked list in recency order plus a hash map from key to list node, both O(1):

type entry[K comparable, V any] struct {
    key   K
    value V
}

type LRU[K comparable, V any] struct {
    capacity int
    ll       *list.List                // front = most recent
    index    map[K]*list.Element
}

func NewLRU[K comparable, V any](capacity int) *LRU[K, V] {
    return &LRU[K, V]{capacity: capacity, ll: list.New(), index: map[K]*list.Element{}}
}

func (c *LRU[K, V]) Get(key K) (V, bool) {
    e, ok := c.index[key]
    if !ok {
        var zero V
        return zero, false
    }
    c.ll.MoveToFront(e) // O(1): relink, no copy
    return e.Value.(*entry[K, V]).value, true
}

func (c *LRU[K, V]) Put(key K, value V) {
    if e, ok := c.index[key]; ok {
        e.Value.(*entry[K, V]).value = value
        c.ll.MoveToFront(e)
        return
    }
    if c.ll.Len() == c.capacity { // evict least recent
        old := c.ll.Remove(c.ll.Back()).(*entry[K, V])
        delete(c.index, old.key)
    }
    c.index[key] = c.ll.PushFront(&entry[K, V]{key, value})
}

container/list elements keep their identity when moved, which is why the map can point at them. The storage engine's block cache is this structure behind a mutex (SSTables and Bloom Filters). In Go, each entry is also two heap objects (the element and the entry) that the GC must track; caches holding millions of entries often switch to index-based lists in one slice to keep pointers out of the heap (Reducing Allocations and GC Pressure).

LRU's weaknesses:

1. Scan pollution. A scan touching more items than the cache holds evicts the entire working set, as measured above.
2. No notion of frequency. An item used 1,000 times an hour ago loses to one used once a second ago.
3. Lock contention. Every hit modifies the shared list, so a concurrent LRU needs a lock even for reads. This is why production caches shard (LevelDB: 16 shards) or move away from strict LRU.

CLOCK: LRU's cheap approximation¶

Frames sit in a circular array with a reference bit. A hit only sets the bit — no list manipulation, no lock needed for the common case. To evict, a "hand" sweeps: a set bit is cleared (second chance), a clear bit means evict. Hit ratio is close to LRU (52.7% vs 51.5% above), and it scales much better under concurrency. A Go implementation is in Buffer Pool and B+Tree.

PostgreSQL's clock sweep generalizes the bit into a usage count from 0 to 5: each access increments it (capped), each sweep pass decrements it, and a buffer is evicted at 0. Frequently used buffers survive several sweeps — a small step toward frequency awareness.

Adding resistance to scans¶

The common idea: a newly inserted item has not proven itself. Keep it on probation; promote it only if it is accessed again.

LRU-K¶

Track the times of each item's last K accesses; evict the item whose K-th most recent access is oldest (items with fewer than K accesses are evicted first). With K=2, a key touched once by a scan has an "infinite" backward K-distance and goes first. Classic in database buffer pools (O'Neil et al., 1993); CMU's BusTub uses it. Costs: storing history, and a priority structure instead of a list.

2Q¶

Two queues plus a ghost list:

• A1in: a small FIFO (≈25%) for first-time items.
• Am: the main LRU for items accessed again.
• A1out: a ghost list of keys (no values) recently evicted from A1in. A miss on a key in A1out means "this was accessed twice within a short window" — it is admitted straight into Am.

Scan items enter A1in, are never re-accessed, and leave via the FIFO without touching Am. Measured: no loss on regular traffic during scans.

Midpoint insertion (InnoDB)¶

InnoDB's buffer pool LRU is split into a young sublist (≈5/8) and an old sublist (≈3/8). New pages are inserted at the midpoint (head of old). A page is promoted to young only if accessed again after innodb_old_blocks_time (default 1000 ms) — so the rapid repeated accesses of a single scan do not promote its pages. RocksDB's LRU cache has a similar high-priority pool for index and filter blocks.

Adding frequency¶

ARC (adaptive replacement cache)¶

ARC (Megiddo & Modha, IBM, 2003) keeps two LRU lists — T1 for items seen once recently, T2 for items seen at least twice — plus ghost lists B1 and B2 of their recently evicted keys. A hit in ghost list B1 means "T1 was too small," so ARC grows T1's target size; a hit in B2 grows T2's. It adapts between recency and frequency to the workload with no tuning parameter. Used in ZFS (as the ARC), and historically limited elsewhere by an IBM patent (expired).

TinyLFU and W-TinyLFU¶

TinyLFU separates admission from eviction: when the cache is full, a new item is admitted only if its estimated frequency is higher than the frequency of the eviction victim. Frequencies are tracked approximately for all recently seen keys — including ones not in the cache — in a Count-Min sketch (a few small counter arrays indexed by different hashes; estimate = minimum counter), periodically halved so old popularity decays. W-TinyLFU adds a small LRU window (≈1%) in front so new bursty items get a chance. It is the policy of Caffeine (Java), which reports near-optimal hit ratios across many traces.

S3-FIFO¶

S3-FIFO (Yang et al., SOSP 2023) uses only FIFO queues:

• S: a small FIFO (10%) for new items.
• M: a main FIFO; items carry a 2-bit access counter, and eviction works like CLOCK (re-insert if counter > 0, decrementing it).
• G: a ghost FIFO of keys evicted from S.

On eviction from S, an item accessed again while in S moves to M; otherwise it is dropped (key remembered in G). The paper's insight is that most objects in real caches are accessed only once ("one-hit wonders"), so quickly filtering them out matters more than precise recency ordering. FIFO queues need no reordering on hit, so the design is lock-free-friendly. In the simulation above, it had the best hit ratio of the four.

Summary¶

Policy	Hit-path work	Scan resistant	Frequency aware	Notable use
LRU	Move node to head (needs lock)	No	No	Simple caches; LevelDB block cache (sharded)
CLOCK / clock sweep	Set a bit / bump a counter	Partly	Slightly (usage count)	PostgreSQL buffers, OS page replacement
LRU-K	Record timestamp	Yes	Yes	Database buffer pools
2Q / midpoint LRU	Queue moves	Yes	Weakly	InnoDB, RocksDB priority pools
ARC	List moves	Yes	Yes, adaptive	ZFS
W-TinyLFU	Sketch increment	Yes	Yes	Caffeine
S3-FIFO	Counter increment	Yes	Weakly	Newer caches; research
HyperClockCache	Atomic counter in a lock-free hash table	Partly	Clock-based	RocksDB (since 7.x)

Concerns beyond the policy¶

• Size-aware caching. Blocks have different sizes. Capacity must be measured in bytes (each entry carries a "charge"), and a policy that counts entries can be fooled by many large objects.
• Pinning. Entries in use cannot be evicted; they must be excluded from the victim search (see the in-use list in SSTables and Bloom Filters).
• Admission control for known-cold reads. The cheapest scan resistance is not to insert at all: fill_cache = false for compaction and full scans.
• Double caching. An engine block cache above the OS page cache holds hot data twice; see Linux I/O Stack and Page Cache.

Common pitfall¶

Tuning cache size while ignoring the policy, or evaluating a policy on synthetic uniform traffic. With uniformly random keys every policy has the same hit ratio (cache size ÷ data size), so nothing appears to matter; with real skewed traffic plus periodic scans, the measured gap between LRU and a scan-resistant policy was over 6 points of hit ratio — the same effect as a substantially larger cache. Evaluate on a recorded trace of the real workload, compare against Belady's OPT on that trace to see how much headroom exists, and only then decide whether to buy memory or change the policy.