system-design · intermediate

Cache Eviction Policies — LRU, LFU, TTL, and Friends

The Central Question

Consider an in-memory Redis cluster deployed for an e-commerce platform on the CacheLab platform (cachelab.com) provisioned with 64 GB of RAM:

• The platform maintains 10,000,000 product pages, user shopping carts, and active session tokens in memory.
• During a Black Friday promotion, total cached data reaches 64 GB, completely filling available RAM.
• A new incoming request arrives to cache a product record for Product #9941.

If the cache evicts a highly popular product record (such as an iPhone on sale receiving 5,000 QPS), subsequent user requests will miss the cache, slamming the underlying PostgreSQL database with thousands of concurrent queries and triggering a total site outage.

If the cache evicts a cold, rarely accessed record (such as an obscure product description requested once three days ago), database load remains minimal and API latency stays under 2 milliseconds.

The algorithm governing this selection is a Cache Eviction Policy (Replacement Algorithm).

This lesson answers one central question: How do cache eviction algorithms (LRU, LFU, FIFO, W-TinyLFU) manage finite RAM boundaries to maximize hit ratio, eliminate scan pollution, and execute in $O(1)$ time complexity using Hash Maps and Doubly-Linked Lists?

Expiry (TTL) vs. Eviction (Capacity)

Engineers frequently confuse Expiry with Eviction. They are two separate, independent mechanisms operating inside a cache:

flowchart TD
  CacheSpace[Cache Space Management] --> Expiry[1. Time-Based Expiry TTL]
  CacheSpace --> Eviction[2. Space-Based Capacity Eviction]
  
  Expiry --> ExpiryDesc["Triggered by TIME.<br/>Removes items when Time-To-Live expires.<br/>Controls DATA FRESHNESS."]
  Eviction --> EvictionDesc["Triggered by MEMORY CAPACITY.<br/>Removes items when RAM limit is reached.<br/>Controls MEMORY CONSUMPTION."]

Figure 1: Conceptual distinction between Time-Based Expiry (TTL) and Space-Based Capacity Eviction.

Expiry vs Eviction Comparison

Core Eviction Algorithms: LRU, LFU, FIFO, and Random

When RAM reaches capacity, the eviction algorithm evaluates candidate keys to select a victim:

flowchart LR
  Policies[Cache Eviction Taxonomy]
  
  Policies --> LRU[LRU: Least Recently Used]
  Policies --> LFU[LFU: Least Frequently Used]
  Policies --> FIFO[FIFO: First In, First Out]
  Policies --> Random[Random Eviction]
  
  LRU --> LRUDesc[Evicts key untouched for longest time]
  LFU --> LFUDesc[Evicts key with lowest hit counter]
  FIFO --> FIFODesc[Evicts key with oldest creation timestamp]
  Random --> RandomDesc[Evicts a randomly selected key]

Figure 2: Taxonomy of major cache eviction algorithms.

1. LRU (Least Recently Used)

• Principle: Evicts the key that has not been accessed for the longest duration of time.
• Underlying Premise: If data was accessed recently, it is highly likely to be accessed again in the near future (Temporal Locality).
• Data Structure: Implemented using a Doubly-Linked List + Hash Map achieving $O(1)$ lookups, updates, and evictions.

2. LFU (Least Frequently Used)

• Principle: Evicts the key that has been accessed the fewest number of total times ($C_{\text{frequency}}$).
• Underlying Premise: Popular items accessed 10,000 times should remain in RAM even if they were not accessed in the last 2 seconds.
• Drawback: Suffers from Frequency Pollution (historical hot items that become obsolete remain in cache forever because their access count is huge).

LFU Frequency Decay Mechanics

Redis Approximated LRU / LFU Implementation

The Scan Pollution Problem: Why LRU Fails During Sequential Scans

A major vulnerability of basic LRU is Scan Pollution (Sequential Scanning Vulnerability):

sequenceDiagram
    autonumber
    actor BatchJob as Nightly DB Backup / Batch Export
    participant Cache as LRU Cache (Capacity: 1,000 Items)
    
    Note over Cache: Cache contains 1,000 HOT product items (Hit Ratio: 98%)
    BatchJob->>Cache: Read 10,000 rare archival records sequentially...
    Note over Cache: LRU evicts all 1,000 HOT items to store 1,000 cold archival items!
    Note over Cache: RESULT: Hit Ratio collapses from 98% down to 0%! (Scan Pollution)

Figure 3: Sequence diagram demonstrating Scan Pollution wiping out hot items in LRU.

Modern Solutions: W-TinyLFU and ARC (Adaptive Replacement Cache)

• W-TinyLFU: Uses a Count-Min Sketch probabilistic data structure to track key frequencies in a compact space. An incoming item is admitted to the cache only if its frequency is higher than the victim item nominated for eviction. Cold sequential batch reads are denied admission, preserving hot keys in RAM!

Data Structure Deep Dive: $O(1)$ LRU Implementation

To achieve $O(1)$ time complexity for both GET reads and PUT writes, LRU combines a Hash Map with a Doubly-Linked List:

flowchart LR
  subgraph HashMap for O1 Lookup
    Map["Hash Map Key -> Node Pointer"]
  end
subgraph Doubly-Linked List for O1 Ordering
    Head[Head / Most Recently Used] <--> NodeA[Key: A]
    NodeA <--> NodeB[Key: B]
    NodeB <--> Tail[Tail / Least Recently Used]
  end
Map -->|Pointer| NodeA
  Map -->|Pointer| NodeB

Figure 4: $O(1)$ LRU data structure combining Hash Map pointers with a Doubly-Linked List.

• On GET(key): Hash Map resolves node in $O(1)$. Node is moved to the Head (MRU) of the list.
• On PUT(key, val): If at capacity, the node at the Tail (LRU) is evicted in $O(1)$, and the new node is prepended to the Head.

Complete Worked Example: Go Thread-Safe $O(1)$ LRU Cache

Let's inspect a complete Go implementation of an $O(1)$ LRU Cache for the CacheLab platform (cachelab.com).

package main
import (
	"container/list"
	"fmt"
	"sync"
)
type entry struct {
	key   string
	value interface{}
}
type LRUCache struct {
	mu       sync.Mutex
	capacity int
	items    map[string]list.Element
	evictList list.List
}
func NewLRUCache(capacity int) LRUCache {
	return &LRUCache{
		capacity:  capacity,
		items:     make(map[string]list.Element),
		evictList: list.New(),
	}
}
func (c *LRUCache) Get(key string) (interface{}, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
if elem, exists := c.items[key]; exists {
		c.evictList.MoveToFront(elem) // Move accessed node to MRU head
		return elem.Value.(*entry).value, true
	}
	return nil, false
}
func (c *LRUCache) Put(key string, value interface{}) {
	c.mu.Lock()
	defer c.mu.Unlock()
// Update existing key
	if elem, exists := c.items[key]; exists {
		c.evictList.MoveToFront(elem)
		elem.Value.(*entry).value = value
		return
	}
// Evict LRU tail item if at capacity
	if c.evictList.Len() >= c.capacity {
		c.evictOldest()
	}
// Insert new item at MRU head
	ent := &entry{key: key, value: value}
	elem := c.evictList.PushFront(ent)
	c.items[key] = elem
}
func (c LRUCache) evictOldest() {
	elem := c.evictList.Back() // Get LRU tail element
	if elem != nil {
		c.evictList.Remove(elem)
		kv := elem.Value.(entry)
		delete(c.items, kv.key)
		fmt.Printf("[EVICTION] Evicted LRU Key: %s\n", kv.key)
	}
}

Failure Modes and Engineering Mitigations

What You Should Remember

1. Eviction operates on capacity; Expiry operates on time: Expiry (TTL) enforces data freshness; Eviction manages finite RAM bounds.
2. LRU exploits Temporal Locality: LRU evicts items untouched for the longest duration, executing in $O(1)$ time via HashMap + Doubly-Linked List.
3. LFU evicts lowest total frequency: LFU keeps popular items in RAM, but requires frequency decay to prevent historical counter lockups.
4. Use W-TinyLFU to prevent Scan Pollution: Probabilistic admission policies block single-use batch scan items from flushing hot keys out of RAM.
5. Always specify an explicit maxmemory-policy: Avoid noeviction settings that crash writes when RAM reaches capacity.

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

• User feeds receive high bursts of reads following viral post notifications.
• Nightly analytics workers run batch database queries traversing 10,000,000 user records.

1. Evaluate why basic LRU will suffer from Scan Pollution during nightly batch jobs.
2. Formulate the configuration strategy (W-TinyLFU vs LFU with decay) to preserve viral newsfeed hit ratios.

Interactive Self-Assessment

The Hash Map provides O(1) key lookups, while the Doubly-Linked List allows O(1) node re-ordering and tail eviction without shifting arrays.

The Hash Map compresses persistent NVMe SSD disk sectors using Gzip compression.

The Doubly-Linked List automatically updates edge CDN TLS certificates.

Combining Hash Map and Doubly-Linked List doubles the physical hardware clock speed of CPU cores.

It uses a Count-Min Sketch frequency estimator to deny cache admission to low-frequency batch items, preserving hot keys in RAM.

It automatically converts relational database SQL schemas into un-indexed CSV files.

It forces client browsers to update their local hosts DNS configuration.

It downgrades the Linux operating system kernel version during batch jobs.

What to Learn Next

• Distributed Caching & Redis Cluster: Master consistent hashing and Redis cluster partitioning.
• Content Delivery Networks — CDNs & Edge Caching: Learn edge proxy caching and HTTP header mechanics.
• Caching Strategies — Read-Through, Write-Through, Write-Back: Revisit write-through and write-behind cache patterns.

Track: Data, Storage and Messaging

Next: Cache Stampede — When Expiry Melts the Database

Series: Caching

1. Caching 101 — Memory Offloading and Latency Reduction
2. Caching Strategies — Aside, Through, Behind, and Refresh-Ahead
3. Cache Eviction Policies — LRU, LFU, TTL, and Friends (this guide)
4. Distributed Caching — Sharding and High-Availability Clusters
5. Cache Stampede — When Expiry Melts the Database
6. Stale Cache After Write — When Your Own Update Disappears
7. Content Delivery Networks (CDN) — Edge Acceleration and Caching
8. Bloom Filters — Probabilistic Set Membership at Scale

All series

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab