Skip to content

Eviction Policies (LRU, LFU, FIFO)

1. What is it? (2-3 lines)

Cache Eviction Policies are algorithms used by in-memory storage engines to determine which specific cached key-value items to discard when cache memory capacity reaches its maximum threshold (maxmemory).

2. Why does it exist?

RAM is finite. When a cache fills to 100% capacity, incoming writes fail unless memory is freed. Eviction policies automatically select and purge the least valuable cached items, maximizing the Cache Hit Ratio for subsequent requests.

3. Where is it used?

  • In-Memory Caches: Redis (maxmemory-policy), Memcached, Guava Cache, Caffeine.
  • Operating Systems: OS Page Replacement algorithms (Virtual Memory swap).
  • Database Buffer Pools: PostgreSQL Shared Buffers (Clock Sweep / 2Q), MySQL InnoDB Buffer Pool (LRU list).

4. How does it work? (simple flow)

  • LRU (Least Recently Used): Discards items that have not been accessed for the longest duration. Maintained via a Doubly-Linked List + Hash Map (\(O(1)\) operations). Move to head on access; evict from tail when full.
  • LFU (Least Frequently Used): Discards items with the lowest access frequency count. Uses frequency counters with decay to prevent old hot items from lingering forever.
  • FIFO (First-In, First-Out): Discards the oldest items inserted into the cache regardless of access frequency or recency (Queue).
  • Approximated LRU/LFU (Redis Mechanics): Standard LRU doubly-linked lists consume high memory overhead. Redis uses Approximated LRU/LFU: Samples \(K\) random keys (e.g. \(K=5\)) and evicts the best candidate among the sample!

5. Decision Matrix

Policy Best For Avoid When Hit Ratio Efficiency Memory Overhead
LRU General-purpose web workloads, temporal locality (recently read data will be read again) Sequential scan workloads (scans clear entire cache!) High Medium (Pointers/timestamps)
LFU Frequency locality (hot products stay hot over long windows) Sudden shift in hot items (old hot items linger without decay) High Medium (Frequency counter per key)
FIFO Simple queue-like TTL data where recency/frequency don't matter Real-world web traffic (ignores access frequency) Poor Very Low
W-TinyLFU (Caffeine) Modern high-throughput JVM caching (combines LRU window + TinyLFU frequency filter) Simple micro-scale scripts Highest Low (Count-Min Sketch based)

6. Limitations

  • LRU Scan Pollution: A single SELECT * batch scan can evict all hot keys from an LRU cache (mitigated by 2Q / LRU-2 / W-TinyLFU).
  • Standard exact LFU/LRU requires memory-intensive pointer structures.

7. Common interview questions (10)

  1. How do you implement an \(O(1)\) LRU Cache using a Doubly-Linked List and Hash Map?
  2. How does Redis implement Approximated LRU (maxmemory-policy allkeys-lru) and how does sample size \(K\) affect accuracy?
  3. What is Scan Pollution in LRU caches and how does 2Q (Two-Queue) or LRU-2 fix it?
  4. How does LFU handle frequency counter decay over time to prevent old hot keys from hogging memory?
  5. How does Caffeine Cache's W-TinyLFU eviction algorithm achieve higher hit ratios than standard LRU?
  6. What are the 8 maxmemory-policy eviction settings available in Redis?
  7. What is the difference between allkeys-lru and volatile-lru in Redis?
  8. How does MySQL InnoDB modify the standard LRU algorithm for its Buffer Pool (Midpoint insertion strategy)?
  9. When is FIFO eviction acceptable in production system design?
  10. What happens in Redis when maxmemory is reached and policy is set to noeviction?

8. Common misconceptions

  • Misconception: Redis uses exact LRU linked-list structures. Fact: Redis uses Approximated LRU/LFU by sampling \(K\) keys to save 16-24 bytes of pointer memory per key.
  • Misconception: LRU is always better than LFU. Fact: LFU performs far better when a core set of items is consistently accessed over long timeframes.

10. 30-second cheat sheet

  • LRU: Evicts least recently used (recency). Vulnerable to scan pollution.
  • LFU: Evicts least frequently used (frequency). Needs counter decay.
  • FIFO: Evicts oldest inserted (ignores usage). Lowest hit ratio.
  • Redis Approximated LRU: Samples \(K=5\) random keys \(\to\) Evicts oldest among sample. Zero pointer memory waste!
  • Modern Gold Standard: W-TinyLFU (Caffeine Cache) for JVM; allkeys-lru or allkeys-lfu for Redis.