Cache fills up. Something has to go. The question is: which thing?

LRU (Least Recently Used) evicts whatever was accessed longest ago. Simple, intuitive, fast to implement with a doubly-linked list and hash map. LFU (Least Frequently Used) evicts whatever was accessed least often. More accurate in theory, more expensive in practice.

The LFU decay problem tripped me up: new items start with zero frequency. A fresh key that’s about to become hot looks identical to a stale key nobody cares about. Without a decay mechanism, items that were popular months ago but irrelevant now cling to the cache while useful new entries get evicted immediately. Redis’s volatile-lfu policy uses a probabilistic counter with logarithmic decay to address this, but it’s not obvious until you read the internals.

TTL (Time To Live) is technically orthogonal to LRU/LFU, not a replacement. You can run LRU with TTLs. The TTL evicts based on age regardless of access pattern; LRU evicts based on recency.

graph TD A[Cache Full] --> B{Eviction Policy?} B -->|LRU| C[Evict least recently accessed key] B -->|LFU| D{Frequency + Decay check} D --> E[Evict lowest-frequency key] B -->|TTL expiry| F[Evict expired keys first] C --> G[New key inserted] E --> G F --> G style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style D fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style E fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style F fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style G fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

At Oracle we ran a config cache with LRU. Midnight batch jobs would scan tens of thousands of config records, which were all accessed briefly and then never again. That scan pattern churned through the LRU list and displaced the hot session keys that morning traffic relied on. Every day at 8 AM, response times jumped from 30ms to 400ms for about 20 minutes while the cache warmed back up. Switching to volatile-lfu with decay stopped the churn. The batch scan keys aged out quickly; the high-frequency session keys stayed put.

LRU is the safe default. LFU is worth it if you have scan-heavy workloads polluting your hot set.

What I’m Learning#

Most Redis deployments I’ve seen use allkeys-lru without thinking about it. Have you ever debugged a cache eviction problem that turned out to be a policy mismatch?