Concrete scenario
A scan of one-time report keys evicts frequently reused product records from a fixed memory budget.
Mechanics
LRU favors recent access; LFU favors repeated access; admission policies such as Window TinyLFU, notably used by Caffeine, compare estimated frequency before admitting an item. Redis offers approximate LRU and LFU policies, not Window TinyLFU. Measure item and byte hit rates on a representative trace.
Failure mode
Pure LRU suffers scan pollution, LFU can retain old popularity, and oversized entries can consume capacity even with a good item policy. Sampling-based approximations vary by workload.
Trade-off
More metadata and sophisticated admission can improve hit ratio but consume CPU and memory. TTL, explicit invalidation, entry size, and business value may matter more than recency alone.
Worked example: scan pollution
A 1 GB cache holds 1 million product records of 1 KB each. About 200,000 of them are hot and receive 90 percent of reads, and the cache hit ratio is 92 percent. A nightly export job then reads 2 million distinct order rows through the same cache.
- Pure LRU: each export row becomes the most recently used entry, so after 1 million rows the hot set is gone. For the next few minutes the hit ratio drops towards zero and product reads fall through to the database. At 20,000 reads per second that is about 18,000 extra DB queries per second.
- Window TinyLFU (Caffeine): each export row enters a small admission window, about 1 percent of capacity. To move into the main cache, it must beat the victim's estimated frequency in a Count-Min sketch. Export rows have frequency 1 and hot products have high counts, so the export churns only the window, and the hit ratio stays close to 92 percent.
- Redis allkeys-lfu: uses a logarithmic 8-bit counter with decay (
lfu-log-factor,lfu-decay-time). One-time keys start with a low count and are evicted first.
Policy comparison
| Policy | Metadata cost | Scan resistant | Adapts to shifting popularity | Used by |
|---|---|---|---|---|
| FIFO | Minimal | No | Yes | Simple caches. S3-FIFO research shows FIFO variants can match LRU |
| LRU (exact) | Linked list plus hash map, with a lock on every hit | No | Yes | Many application libraries |
| CLOCK / sampled LRU | A bit or timestamp per entry | No | Yes | OS page caches, Redis allkeys-lru |
| LFU | A counter per entry | Yes | Poorly without decay | Redis allkeys-lfu, which uses decay |
| Segmented LRU / 2Q | Two lists | Mostly | Yes | InnoDB midpoint insertion, memcached segmented LRU |
| W-TinyLFU | Count-Min sketch plus windows | Yes | Yes, through hill climbing | Caffeine, Ristretto |
Practical guidance
- Replay a real access trace through candidate policies before choosing one. Caffeine's simulator and libCacheSim exist for this.
- Cap maximum entry size. One 50 MB value can evict thousands of useful small entries.
- In Redis, set
maxmemoryand an explicitmaxmemory-policy. The default,noeviction, makes writes fail when memory is full.