lru-k-replacement · research · also LRU-K, LRU-2, Least Recently Used K

LRU-K replacement

LRU-K ranks buffered pages by the age of their Kth most recent reference, using retained history to distinguish repeated use from isolated accesses.

The basic rule evicts the page with the largest backward K-distance; fewer than K known references gives infinite distance. A subsidiary policy resolves ties. Without correlation filtering, K=1 reduces to ordinary LRU. This ranks recent reference history, not lifetime access counts. [1]

A correlated-reference period groups accesses transitively. LAST tracks the latest access while HIST tracks adjusted history. In the 1993 outline, a resident page is eligible for replacement only when t - LAST > period; equality remains protected. At the next uncorrelated reference, history updates contract the completed burst, not just omit its repeated accesses. Retained history can survive payload eviction. Finding that history is not a cache hit. [1]

History storage: keeping access timestamps in page headers would require writing back otherwise clean pages. Discarding history at eviction can misclassify recurring accesses as first references; retained history is not cached payload. [1]

The 1999 optimality result assumes the independent-reference model, steady-state behavior and the same limited K-reference history information. Theorem 3.9 compares LRU-K with m pages against a competitor with m-1 pages. It does not establish superiority on every finite trace or against a future-knowing policy. [2]

2Q is a different design using FIFO and LRU queues with a nonresident history, not another name for LRU-2. Its full version defers main-queue admission until a history hit. [4]

Worked example: with K=2, period 5 and warm history (10,1), resident reads at 14 and 18 extend one burst. A read at 30 produces history (30,18) and backward distance 12. Merely omitting burst reads gives (30,10) and distance 20. Times are abstract ticks, not a measured workload. [5]

Relations

related

Least recently used replacement, Cache admission

Limitations

• Larger K retains more history and can respond more slowly when the access pattern changes. [2]
• Reference-history metadata requires its own retention policy; retaining a timestamp does not retain the page data. [1]
• The 1993 time-out heuristic groups nearby accesses without process identity; temporal proximity does not establish a shared transaction or causal dependence. [1]
• The schematic outline omits I/O latency and victim-search structures; its resident-history arithmetic alone does not measure end-to-end request cost. [1, 4]
• The 1993 paper leaves nonresident-history space budgeting open; 2Q separates resident page slots from remembered identifiers. Equal payload capacity therefore need not mean equal total memory consumption. [1, 4]
• The 1999 Bayesian argument assigns equal prior probabilities to unknown page-to-probability mappings. A policy with known per-page probabilities has different information, not future knowledge; it is outside this limited-history comparison. [2, 3]
• Lemma 3.8 defines steady-state startup after at least m-1 pages have each been referenced K or more times. This is a reference-history condition, not a fixed warm-up duration or a hardware-cache settling time. [2, 3]

Citations

1. O'Neil, O'Neil and Weikum. The LRU-K Page Replacement Algorithm for Database Disk Buffering. SIGMOD 1993, pp. 297-306, sections 2-2.1 and 5. (accessed 2026-11-01)
2. O'Neil, O'Neil and Weikum. An optimality proof of the LRU-K page replacement algorithm. JACM 46(1), 1999, pp. 92-112; Lemma 3.3 and Theorem 3.9. (accessed 2026-10-31)
3. O'Neil, O'Neil and Weikum. Author-uploaded full text of the 1999 LRU-K optimality paper. (accessed 2026-11-02)
4. Johnson and Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994, section 2. (accessed 2026-11-01)
5. Hesela. Constructed LRU-2 correlation example: inputs, states and eligibility probes. (accessed 2026-10-31)

Further reading

6. Hesela. Standalone warm-history LRU-2 arithmetic (Node.js; MIT). (accessed 2026-10-31)
7. Hesela. Boundary checks and independent batch-burst oracle for the LRU-2 example. (accessed 2026-10-31)

JSON: /data/terms/lru-k-replacement.json