CONCEPT Cited by 1 source
LFRU cache eviction (Least Frequently Recently Used)¶
Definition¶
Least Frequently Recently Used (LFRU) is a two-queue cache replacement policy that gives frequently-accessed items a second chance before eviction. (Source: sources/2025-07-08-planetscale-caching.)
One cool one is Least-Frequently Recently Used. This involves managing two queues, one for high-priority items and one for low priority items. The high-priority queue uses an LRU algorithm, and when an element needs to be evicted it gets moved to the low priority queue, which then uses a more aggressive algorithm for replacement.
Shape¶
[ high-priority queue (LRU) ] → demote → [ low-priority queue (aggressive) ] → evict
↑ re-entry on hit ↑ hit can promote back
- Inserted items land in the high-priority queue by default.
- High-priority queue runs standard LRU internally. When the HP queue is full and a new entry arrives, the LRU entry is demoted to the low-priority queue, not evicted.
- Low-priority queue uses a more aggressive replacement policy (FIFO, shorter TTL, or just smaller capacity). Items in the LP queue can still be read; if hit, they can be promoted back to HP.
- Eviction only happens from the LP queue.
Why it's useful¶
Straight LRU treats a rare- one-off access identically to a sustained-high-frequency access. Under scan-polluted or mixed workloads this evicts hot items prematurely:
- One-time sequential scan touches a million pages.
- Each touched page becomes "most-recently-used" briefly.
- Each genuinely-hot page drops to LRU and gets evicted.
LFRU gives genuinely-hot items (those accessed repeatedly across time windows, not just recently) a second-chance queue to live in. Only items that prove cold across both access patterns (recent-but-not-frequent, frequent-but-not- recent) get evicted.
This is effectively recency + frequency combined —
closer in spirit to the LFU family than strict LRU, but
keeping LRU's O(1) core operations.
Relation to other refinements¶
- InnoDB midpoint-insertion LRU is a close cousin: new entries start at the 3/8-from-tail position and only promote to the "young" part of the LRU list on a second access within a window. Same idea (frequency-aware promotion), different mechanism (single list with a midpoint instead of two queues).
- ARC (Adaptive Replacement Cache) is an IBM-origin, patent-encumbered adaptive variant that actively tunes the boundary between the two queues based on recent hit behaviour.
- W-TinyLFU (Caffeine) uses a frequency sketch (Count- Min) to bias admission into a small window cache + a main segmented LRU, explicitly weighting both recency and frequency.
- 2Q (VLDB '94) is the precursor to most of the dual-queue approaches; LFRU descends from it.
Trade-offs¶
| Axis | Plain LRU | LFRU |
|---|---|---|
| Hit rate on scan-mixed workload | Low (scan pollution) | Higher (hot items survive in HP queue) |
| Bookkeeping cost | 1 list + 1 map | 2 lists + 2 maps + promotion/demotion logic |
| Tuning burden | Just cache size | Cache size + HP/LP split ratio + LP policy |
| Cold-start behaviour | Simple | Initial items all fight for HP slots — no meaningful signal yet |
When it's worth the complexity¶
- OLTP workloads with periodic analytical scans (the canonical scan-pollution case).
- Mixed workload caches where a minority of keys are durably hot and the majority are one-off.
- Large caches where the single-LRU ordering is already expensive to maintain under contention.
For pure recency-biased workloads (social feed, session store) plain LRU is often enough and the extra state isn't worth it.
Seen in¶
- sources/2025-07-08-planetscale-caching — Ben Dicken introduces LFRU as a niche-but-useful dual-queue refinement on top of LRU, with the promotion / demotion flow spelled out prosaically.