The Adaptive Replacement Cache (ARC) with Compressed Ghost Lists: Remembering More History in Less Space

2026-07-19

Standard ARC keeps two ghost lists (B1 and B2) that remember keys recently evicted from the resident cache. Those ghosts are what let ARC self-tune between recency and frequency: a hit on a ghost is a signal that ARC guessed wrong and should grow that half. But ghosts aren't free — each ghost entry holds a full key plus list pointers. For a 1M-entry cache with 32-byte keys, ghost overhead alone can push 100+ MB of RAM before you cache a single byte of value.

Compressed ghost lists attack that overhead directly. Instead of storing raw keys in B1 and B2, you store fingerprints — short hashes, typically 8 to 16 bits — in a compact ring buffer or Bloom-filter-style structure. You trade exact ghost-hit detection for a tiny probability of false positives. A false positive means ARC thinks it evicted a key it didn't, and adjusts its target size slightly wrongly. That's a rounding error against the ~10x memory reduction.

Concrete example: A CDN edge cache with 10M object slots was spending 1.2 GB on B1+B2 ghost metadata using 40-byte URL keys. Switching to 16-bit fingerprints stored in two 10M-slot ring buffers dropped ghost memory to 40 MB — a 30x reduction. Hit rate dropped by 0.3 percentage points (from 87.4% to 87.1%) due to fingerprint collisions causing spurious tuning adjustments. That trade-off freed 1.16 GB for actual cached objects, which recovered 2+ percentage points of hit rate. Net win: bigger cache, same tuning intelligence.

Rule of thumb: Size your fingerprint at log2(ghost_capacity) + 4 bits. For a 1M-entry ghost list, use 24 bits (~1 in 16M collision odds per lookup). Below that, tuning noise starts to matter; above it, you're wasting bits.

Watch for:

Compressed ghosts are the reason ARC-family algorithms remain viable at billion-entry scale where naive ghost storage would exceed the cache itself.

Key Takeaway: Replace full-key ghost entries with short fingerprints to shrink ARC's tuning memory by 10-30x, trading a negligible hit-rate loss for a much larger resident cache.

All newsletters