segmented-lru · research · also SLRU, segmented least recently used

Segmented LRU

Segmented LRU separates probationary and protected residents, promoting a probationary hit and demoting the least-recently-used protected entry when its limit is exceeded.

New entries join probation. A resident probation hit promotes the entry to protected MRU; a protected hit refreshes its order. Overflow demotes the protected LRU entry to probation rather than immediately discarding its payload. The probation LRU supplies eviction victims. [1]

Capacity rules matter: the 2015 description uses fixed-size segments. The pinned simulator instead allows probation to occupy unused protected capacity and evicts only above the total limit. Three slots with a protected limit of two can therefore retain A, B and C during cold fill. [1] [2]

In a constructed A B C A trace, that shared-capacity rule gives one hit; reserving two initially empty protected slots gives zero. Both variants use the same total ceiling. The example isolates capacity semantics, not workload performance. [4]

Full 2Q does not promote a resident A1in hit and keeps nonresident history. Plain SLRU needs no such history. TinyLFU is a separate admission decision; Window TinyLFU combines an admission window with an SLRU main cache. [3] [1]

Relations

related
Least recently used replacement, 2Q replacement, TinyLFU

Limitations

  • A protected entry can later be demoted and evicted; protection is neither pinning nor a guarantee of future hits. [1]
  • A segment fraction is a policy parameter, not a universal optimum. Compare payload, metadata, admission and cold-start rules together. [1, 2]

Citations

  1. Einziger, Friedman and Manes. TinyLFU: A Highly Efficient Cache Admission Policy. arXiv:1512.00727v2, sections 2.1 and 4. (accessed 2026-11-18)
  2. Caffeine authors. SegmentedLruPolicy.java, commit 5227a98b51e02b4d4fbfc2b0e33c362a138f51b1, record/onHit/onMiss/evict. (accessed 2026-11-18)
  3. Johnson and Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994, section 2. (accessed 2026-11-18)
  4. Hesela. Segmented LRU: capacity rules, hand-traced states and executable tests. (accessed 2026-11-18)
Sources & caveats
  • Primary-source synthesis and a constructed sequential state-machine demonstration. The example is not a native Caffeine execution or a reproduction of published benchmarks.
  • The pinned simulator comparison assumes positive protected capacity and always-admit behavior. Production caches can add weights, expiry, asynchronous maintenance and admission filters.
  • The original 1994 SLRU article was not read in full; no invention date or first-publication claim is inferred from later citations.

JSON: /data/terms/segmented-lru.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Segmented LRU. Hesela. 2026-11-18. https://hesela.dev/terms/segmented-lru/