The Segmented LRU with Compressed Ghost Entries: Fitting More Eviction History Into Less RAM

2026-07-21

SLRU with ghost entries remembers what it evicted so it can promote returning keys faster. But ghost lists eat memory — a 1M-entry ghost list holding 32-byte keys plus pointers costs ~48 MB just to remember things you already threw away. Compressed ghost entries fix that by storing fingerprints instead of full keys.

The idea: a ghost entry doesn't need to reconstruct the original key. It only needs to answer "have I seen this key before?" with acceptable false-positive rates. So instead of storing the key, store a 4-byte or 8-byte hash fingerprint. Your 48 MB ghost list shrinks to 4–8 MB, and you can now remember 6–12× more evictions in the same RAM budget.

How it works in an SLRU cache:

Real-world example: Cassandra's row cache historically used simple LRU and suffered on scan-heavy workloads that flushed hot rows. Switching to an SLRU variant with compressed ghost lists let it remember ~10× more eviction history in the same JVM heap — enough that a hot row briefly displaced by a table scan gets promoted back to protected the moment it's re-read, instead of restarting probation. Hit rate improved 15–25% on mixed OLTP+analytics workloads without raising cache size.

Rule of thumb for sizing: ghost list capacity should equal 2× to 4× the segment it shadows. With 64-bit fingerprints and a false-positive rate of n / 2^64, even a 100M-entry ghost list has FP probability ~5 × 10⁻¹². Practically zero. If you use 32-bit fingerprints for extra compression, cap ghost size at ~100K entries or FP rate climbs above 1-in-40K — noticeable on high-QPS caches.

Tradeoff: you lose the ability to iterate ghost keys or inspect them for debugging. If eviction telemetry matters — say, you want to log "which keys are churning?" — keep a small uncompressed sample alongside the compressed list. The fingerprints answer the hot-path question; the sample answers the diagnostic one.

Key Takeaway: Ghost entries only need to answer "seen before?" — replace full keys with hash fingerprints to remember 6–12× more eviction history in the same RAM.

All newsletters