The Segmented LRU with Ghost Entries and Adaptive Segment Sizing: When the Hot/Cold Boundary Should Move With the Workload

2026-07-24

Segmented LRU caches split memory into a probationary segment (new arrivals) and a protected segment (items that earned a second hit). The classic problem: you pick the split at deploy time — say 20% probationary, 80% protected — and pray your workload matches. It never does. Scan-heavy periods want a bigger probationary buffer to absorb one-hit wonders. Steady hot-key workloads want a bigger protected segment to hold the working set. A fixed split leaves hit rate on the table in both directions.

Adaptive segment sizing borrows the idea from ARC: use ghost entries (keys of recently evicted items, no values) as a signal. When you get a ghost hit in the probationary ghost list, that means the probationary segment was too small — grow it, shrink protected. Ghost hit in the protected ghost list? Protected was too small — grow it, shrink probationary. The boundary walks toward whichever segment is losing more entries it shouldn't have.

Concrete example. A product catalog cache holds 100K items. Normally 90% of traffic hits ~5K hot SKUs — the protected segment wants to be huge. Then at 2am a batch reindexer scans every SKU once. With a fixed 80/20 split, the scan floods protected via promotions and evicts hot keys; morning hit rate craters. With adaptive sizing, scan-driven ghost hits accumulate in the probationary ghost list (one-hit items evicted from probationary), the boundary shifts, probationary grows to absorb the scan, protected stays intact. When traffic normalizes, protected-side ghost hits push the boundary back.

Rule of thumb. Adjust by a small fixed step per ghost hit — typically 1 entry, capped at ±90% of total capacity so neither segment starves. If your cache holds N items and you're seeing G ghost hits per second, the boundary moves at G entries/second. For N=100K and G=100/s, adaptation reaches steady state in ~1000 seconds — fast enough for hourly workload shifts, slow enough to ignore noise.

Watch for: ghost list sizes need to roughly equal segment sizes, or you'll under-signal. Don't let the boundary oscillate — add a small dead zone (ignore the first few ghost hits after a boundary move). And measure: if your workload is genuinely stationary, adaptive sizing costs metadata and buys nothing. It pays off when the workload shifts.

Key Takeaway: Let ghost hits on each side of the segment boundary vote on where the boundary should be — the cache learns the right split instead of forcing you to guess at deploy time.

All newsletters