The Segmented LRU with Ghost Entries and Frequency-Aware Demotion: When Falling Out of the Hot Segment Should Depend on How Loved You Were

2026-07-23

Standard SLRU with ghost entries tells you two things: which items you recently evicted (via the ghost list) and which items were promoted to the protected segment (via a second hit). But when the protected segment overflows, it demotes the LRU item back to probationary — no matter how frequently that item was accessed while protected. A page hit 500 times gets demoted just as readily as one hit twice. That's information you paid to collect and then threw away.

The pattern: attach a small frequency counter (4 bits is plenty) to each protected-segment entry. Increment on every hit while in protected. When the protected segment needs to demote, don't pick the LRU tail blindly — pick the LRU tail among entries with the lowest frequency. Highly-loved entries get a second chance and re-enter the MRU end of protected with their counter halved (aging). Ghost entries continue to work as before on the probationary side.

Concrete example: A CDN edge cache holds movie thumbnails. A trending trailer gets promoted to protected and racks up 2,000 hits over an hour. Then a burst of overnight batch traffic pulls in 50 new items, promoting them to protected as they hit twice. Vanilla SLRU demotes the trailer because it's now the LRU tail. Frequency-aware demotion sees the trailer's counter (15, saturated) versus the batch items' counters (2–3) and demotes a batch item instead. The trailer stays hot for the morning traffic surge.

Rule of thumb: use 4-bit counters (values 0–15, saturating). Halve all counters in a segment when total promotions exceed the segment size — this ages frequencies so yesterday's hero doesn't monopolize the cache forever. Memory overhead is ~0.5 bytes per protected entry; hit-rate improvement over vanilla SLRU is typically 3–8% on skewed workloads with recurring bursts.

When to reach for it: workloads with both a persistent hot set and periodic bursts of medium-popularity items (CDN, database buffer pools, feed ranking caches). Skip it when your workload is uniformly random (counters just add overhead) or purely recency-driven (plain LRU is fine).

Watch out for: counter saturation hiding true frequency differences — if everything hits 15, you're back to LRU demotion. Aging fixes this, but tune the halving trigger: too frequent and you lose signal; too rare and counters saturate. Also, don't skip aging entirely: without it, an item that was hot last week keeps blocking today's genuinely hot content.

Key Takeaway: When your cache already tracks access frequency, use it to pick whom to demote — not just which position to demote from.

All newsletters