Cache Eviction — LRU, LFU, FIFO

System Design FundamentalsMidcachingsystem-design

The Question

What are LRU, LFU, and FIFO cache eviction strategies?

What a Strong Answer Covers

• Least" not "Last" for LRU. All three defined.

Senior-Level Answer

Cache eviction policies determine which item is removed when the cache is full and a new item must be inserted. The right policy depends on the access pattern of the workload.

**FIFO (First In, First Out)** evicts the oldest item by insertion order, regardless of access frequency or recency. It is the simplest to implement (a queue) but performs poorly for workloads with a stable working set — an item inserted long ago but accessed frequently will be evicted simply because it was inserted first.

**LRU (Least Recently Used)** evicts the item that was accessed least recently. The intuition is temporal locality: if you used something recently, you are likely to use it again soon. LRU is the most commonly deployed policy (Redis default, CPU hardware caches) because it works well for workloads with a temporal locality pattern. The standard implementation uses a doubly-linked list combined with a hash map, giving O(1) get and put. The limitation is that a single sequential scan (e.g., a large batch job reading unique keys) can flush the entire cache — an effect called **cache pollution**.

**LFU (Least Frequently Used)** evicts the item accessed the fewest times. This suits stable, long-lived working sets where some items are permanently hot (home page, popular product). A naive implementation requires counting accesses per key and finding the minimum — O(log n) with a min-heap. An O(1) implementation exists using two hash maps and a doubly-linked list of frequency buckets (Aho et al.). The weakness of LFU is the **aging problem**: an item accessed 1000 times last week but never since will have a very high count and resist eviction even when it is no longer relevant. LFU-with-decay (dividing counts periodically) or Window-TinyLFU (used by Caffeine, the Java cache, and adopted by Redis's LFU mode) addresses this with a sketch-based frequency estimator plus a recency window.

**LRU vs. LFU in practice**: use LRU for general-purpose caches with temporal locality. Use LFU (or W-TinyLFU) when the access distribution is highly skewed and the hot set is stable — content delivery caches, DNS caches, read-heavy database query caches. Redis supports both (`allkeys-lru` and `allkeys-lfu` maxmemory policies). Memcached uses a segmented LRU variant.

What Separates a 2/3 from a 3/3

Common Mistakes

• Describing LRU with O(n) get — the correct implementation is O(1) using a hashmap + doubly-linked list.
• Not identifying that sequential scans cause LRU cache pollution.
• Missing the LFU aging problem — high-frequency historical items resist eviction even when stale.
• Being unable to recommend a policy given a described workload access pattern.

Follow-Up Questions

• Walk me through the data structures required for an O(1) LRU cache implementation. — HashMap (key → node) for O(1) lookup. Doubly-linked list for O(1) move-to-front (on hit) and remove-from-tail (on eviction). Both operations are O(1) with direct node pointer.
• What is cache pollution and which eviction policy is most vulnerable to it? — Sequential access patterns that flood the cache with one-time-use items, evicting hot items. LRU is most vulnerable because recency alone drives retention. ARC and SLRU are more resistant.
• What is the ARC (Adaptive Replacement Cache) policy and what problem does it solve? — ARC maintains two LRU lists (recent entries and frequent entries) plus ghost lists to adaptively balance recency vs. frequency based on observed hit patterns — self-tuning for workload shifts.
• Redis has multiple maxmemory eviction policies. When would you use volatile-lru vs. allkeys-lru? — volatile-lru only evicts keys with a TTL set — useful when some keys must never be evicted (permanent config). allkeys-lru evicts any key — better for pure caching use cases.

Related Questions

• Redis Caching Patterns
• Vertical vs Horizontal Scaling
• API Versioning
• SLOs vs SLAs
• Availability — Five 9s