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
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
- Einziger, Friedman and Manes. TinyLFU: A Highly Efficient Cache Admission Policy. arXiv:1512.00727v2, sections 2.1 and 4.
- Caffeine authors. SegmentedLruPolicy.java, commit 5227a98b51e02b4d4fbfc2b0e33c362a138f51b1, record/onHit/onMiss/evict.
- Johnson and Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994, section 2.
- Hesela. Segmented LRU: capacity rules, hand-traced states and executable tests.
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.