The Segmented LRU with Ghost Entries and Frequency-Weighted Promotion: When Access Count Should Decide Where You Live

2026-07-22

Plain SLRU splits the cache into a probationary segment (new arrivals) and a protected segment (proven hot). A hit in probation promotes to protected. But "one hit = promotion" is naive: a single accidental re-read can evict something you've touched 50 times. Frequency-weighted promotion fixes this by requiring a hit count threshold before moving up, and the ghost entries remember frequencies of things you've already evicted.

How it works:

Real-world example: A CDN edge node caches image thumbnails. A crawler scans 100,000 unique URLs once each — under plain SLRU, every crawler request promotes something to protected on its second byte-range fetch, polluting the hot segment. With frequency-weighted promotion at T=3, the crawler's URLs never reach protected (they get 1–2 hits then age out of probation). When a genuinely popular thumbnail is evicted during a traffic spike and re-requested an hour later, the ghost entry remembers its count of 12, and it snaps back into protected on the first hit instead of restarting the promotion climb.

Rule of thumb for sizing: Set T = ⌈log₂(probation_size / working_set_size)⌉, clamped to [2, 4]. If your probation holds 10,000 entries and your hot working set is ~1,000, T=3 filters scan traffic without starving legitimate promotions. Ghost list size should be roughly equal to the protected segment — smaller and you forget too fast, larger and the frequency memory itself becomes stale.

Where it hurts: The 4-bit counter per entry plus per-ghost costs 5–8 bytes of metadata beyond the key. On a cache of 10M entries, that's 50–80 MB of overhead. And tuning T wrong in either direction is worse than plain SLRU: too high starves the protected segment; too low reintroduces scan pollution.

Key Takeaway: Promoting on a single hit lets scans poison your hot segment — require a frequency threshold and let ghost entries preserve counts across evictions so proven-hot data snaps back fast.

All newsletters