LRU-K, 2Q and ARC

How do rate estimates, ghost entries and self-tuning improve on recency, and why are they rarely what you run?

LRU-K: estimating rate instead of recency

LRU cannot distinguish two pages that were both referenced one millisecond ago when one of them is referenced every second and the other was touched twice in a burst and will never be seen again. Recency is a one-sample estimator of a rate, and one sample cannot separate a burst from a trend.

LRU-K (O'Neil, O'Neil and Weikum, 1993) keeps the last K reference timestamps of each page. It evicts the page whose K-th most recent reference is oldest. With K = 2 you estimate the inter-arrival interval directly instead of inferring it from a single point. The result is genuinely better hit rates on mixed workloads, and it is scan-resistant almost for free: a scan touches each page once, so every scanned page has an infinitely old second reference and is evicted first.

The correlated reference period

The paper also names a problem that every rate estimator has. A page read twice in quick succession inside one transaction has not shown a high reference rate. It has shown one logical access implemented as two physical ones. LRU-K therefore collapses references inside a short window into one. Any system that estimates a rate from an event stream needs this correction, and most get it wrong at least once.

Why it is not everywhere

Keeping K timestamps per page and choosing the maximum needs a priority queue: O(log N) per eviction, plus history updates on every hit. That puts work back on the hit path, the very thing Clock: chosen for its hit path, not its hit rate was fleeing. The better statistic loses to the cheaper one, on the same machine that made the better statistic possible.

One-line compression: recency is a one-sample rate estimate. LRU-K takes two samples and pays for them on the hit path, which is why it wins on paper and loses on hardware.

---

2Q: and the ratio that justifies ghost entries

2Q (Johnson and Shasha, 1994) reaches LRU-2-like behaviour in constant time with three structures:

• A1in: a FIFO queue for pages seen once;
• A1out: a queue of identifiers only, no page data, for pages that were evicted from A1in;
• Am: an LRU list of pages that proved themselves.

A page referenced again while its identifier sits in A1out is promoted to Am. One-hit wonders drain out of A1in without ever polluting the hot list. That is scan resistance obtained structurally rather than statistically.

The ghost queue

The reusable idea is the ghost queue, and it deserves its own derivation because it generalizes:

A page identifier is ~8–20 bytes. A page is 8,192 bytes. The ratio is ~400–1,000×. You can remember the identity of three orders of magnitude more pages than you can keep. History about what you evicted is almost free relative to the data itself.

Check: 8,192 ÷ 20 ≈ 410, and 8,192 ÷ 8 = 1,024.

Once you notice this, the design follows: track the counterfactual. Ghost entries let the policy observe what it would have hit had it kept more. That is the only way an online policy can get feedback about its own mistakes. It is the same move as a shadow deployment or a holdout group, executed inside a data structure. Any policy that must choose under uncertainty can afford to log the identity of what it discarded.

One-line compression: an identifier is a thousand times smaller than its page, so a policy can afford to remember everything it threw away and learn from it.

---

ARC: self-tuning, and a lesson about adoption

ARC (Megiddo and Modha, 2003) removes the tuning parameter that 2Q still has. It has four lists:

• T1: pages seen once;
• T2: pages seen twice or more;
• B1 and B2: ghost lists (identifiers only) behind T1 and T2.

A target size p for T1 divides the pool between recency and frequency. The adaptation rule is one line:

The policy learns the workload's position on the recency–frequency spectrum from its own misses, continuously, in constant time, with no workload-specific configuration.

What to take away is not the algorithm but this property: a ghost hit is a labelled training example that the policy generates for free. The same pattern appears in another mechanism: a group-commit batch (writing the log for many transactions with one fsync) sizes itself to whoever arrived during the last flush. In both cases the mechanism's own backlog or failure is the signal, so no estimator is needed. This kind of self-tuning is rare. These are the only two genuine instances so far.

Costs and honest caveats

• Roughly 2× the metadata (ghost lists sized comparably to the pool).
• ARC still mutates lists on hits, so the synchronization argument of Clock: chosen for its hit path, not its hit rate applies to it as much as to LRU.
• A non-technical fact that explains a real decision: ARC is patented by IBM. PostgreSQL adopted it in version 8.0, replaced it with 2Q in a minor 8.0 release and moved to clock-sweep in 8.1, with the patent among the reasons. ZFS uses an adapted variant. Algorithm adoption is a legal and operational question as much as a hit-rate question. That is not a mechanism, but it is why the best-known policy is not in the database you use.

One-line compression: ARC lets its own misses tell it where to sit between recency and frequency. It is the rare case of a policy that needs no estimate, because its failures are labelled.