About Cache Eviction Policies

When a cache reaches its maximum capacity and a new item needs to be stored, the cache must decide which existing item to remove (evict). This decision is governed by the eviction policy — a critical system design choice that directly impacts cache hit rate, latency, and overall system performance. Choosing the wrong policy can degrade your cache to little more than wasted memory, while the right policy can dramatically reduce database load and improve response times by orders of magnitude.

The 5 Core Policies — Deep Dive

LRU (Least Recently Used)

Evicts the item that hasn't been accessed for the longest time. LRU exploits temporal locality — the observation that recently accessed data is likely to be accessed again soon.

Time complexity: O(1) for both get and put operations when implemented with a doubly-linked list + hash map. The hash map provides O(1) lookups, while the doubly-linked list maintains access order. On every access, the node is moved to the head. On eviction, the tail node is removed.

Best for: General-purpose caching, web page caches, database buffer pools. Most workloads exhibit temporal locality, making LRU the default choice.

LFU (Least Frequently Used)

Evicts the item accessed the fewest times. LFU is ideal when some items are consistently "hot" — like a viral tweet or a popular product page — because it preserves items with high access counts even if they haven't been accessed very recently.

Time complexity: O(1) with the O(1) LFU algorithm (using a frequency map + doubly-linked list per frequency bucket). Naive implementations are O(log n).

Best for: CDN caches, content with Zipf-distributed access (a few items get most of the traffic), recommendation engines.

FIFO (First In, First Out)

Evicts the oldest inserted item regardless of how often or recently it was accessed. FIFO is the simplest to implement (just a queue) but completely ignores access patterns.

Best for: Situations where simplicity matters more than hit rate — embedded systems, hardware caches with limited logic budget, or when all items have roughly equal access probability.

Random Eviction

Evicts a randomly selected item. Surprisingly, random eviction performs competitively with LRU for uniform access patterns and avoids pathological worst-cases that can plague deterministic policies.

Best for: Uniform access patterns, CPU caches (ARM Cortex uses random replacement), situations where the overhead of tracking access metadata is too high.

TTL (Time-To-Live)

Evicts the item closest to expiration. TTL-based eviction is essential for data that becomes stale — session tokens, API response caches, DNS records. It's often combined with another policy (e.g., LRU + TTL).

Best for: Session stores, DNS caches, any data with a natural expiration (OAuth tokens, rate limit windows, temporary feature flags).

Which Policy to Choose?

Workload Pattern	Best Policy	Why
General web app	LRU	Most web requests have temporal locality
Viral/trending content	LFU	Hot items stay cached despite gaps in access
Session tokens	TTL	Sessions have natural expiration
Scan-heavy (analytics)	LRU-K or ARC	Resists pollution from one-time scans
Embedded/constrained	Random or FIFO	Minimal metadata overhead

LRU Implementation: The Classic Data Structure

The standard LRU cache combines a hash map (for O(1) key lookups) with a doubly-linked list (for O(1) reordering). This is one of the most commonly asked data structure questions in software engineering interviews.

GET(key):
  if key in hashmap:
    node = hashmap[key]
    move node to HEAD of list   ← O(1)
    return node.value           ← cache HIT
  else:
    return null                 ← cache MISS

PUT(key, value):
  if key in hashmap:
    update node, move to HEAD
  else:
    if cache is FULL:
      evict TAIL node           ← least recently used
      remove from hashmap
    create new node at HEAD
    add to hashmap

Production Systems & Configuration

Redis

maxmemory 2gb
maxmemory-policy allkeys-lru    # LRU across all keys
# Other options:
# volatile-lru     — LRU only among keys with TTL
# allkeys-lfu      — LFU across all keys (Redis 4+)
# volatile-ttl     — evict keys with shortest TTL
# allkeys-random   — random eviction
# noeviction       — return error on write (default)

Redis uses an approximated LRU — it samples 5 keys (configurable via maxmemory-samples) and evicts the least recently used among the sample. This is much cheaper than true LRU.

Caffeine (Java / JVM)

Uses the W-TinyLFU algorithm — a hybrid that combines a small LRU "window" with a larger LFU "main" cache, using a Count-Min Sketch for frequency estimation. Achieves near-optimal hit rates with O(1) operations. Used by Spring, Apache Druid, and Neo4j.

Memcached

Uses a slab-based LRU. Memory is divided into slab classes by object size. Each slab class maintains its own LRU list. This avoids fragmentation but can lead to uneven eviction across size classes.

Cache Invalidation Strategies

Phil Karlton famously said: "There are only two hard things in Computer Science: cache invalidation and naming things." Here are the three main strategies:

Write-Through

Write to cache and database simultaneously. Guarantees consistency but adds write latency. Used when you can't tolerate stale reads.

Write-Behind (Write-Back)

Write to cache immediately, asynchronously flush to database. Fast writes but risk data loss if cache node fails before flush. Used by CPU L1/L2 caches and gaming leaderboards.

Cache-Aside (Lazy Loading)

Application checks cache first. On miss, read from DB, populate cache. On write, invalidate cache entry. The most common pattern in web applications. Used by most Redis deployments.

Common Pitfalls

⚡ Cache Stampede (Thundering Herd)

When a popular cached item expires, many requests simultaneously miss and hit the database. Solutions: probabilistic early expiration (refresh before TTL), mutex locks (only one thread rebuilds the cache), or stale-while-revalidate (serve stale data while refreshing in background).

🧊 Cold Start

A fresh cache has zero entries — every request is a miss. Solutions: cache warming (pre-populate from DB on startup), gradual rollout (slowly shift traffic to new cache nodes), or persistent caching (Redis with AOF/RDB for cache survival across restarts).

🗑️ Cache Pollution

One-time scans (e.g., a batch analytics job) can evict frequently-used items from an LRU cache. Solutions: use LRU-K (track K-th access), ARC (Adaptive Replacement Cache — balances recency and frequency), or scan-resistant policies like W-TinyLFU.

Advanced Policies

ARC (Adaptive Replacement Cache): Dynamically balances between LRU and LFU based on workload. Used by ZFS and IBM DB2.
LRU-K: Tracks the K-th most recent access time. LRU-2 is particularly effective at resisting scan pollution. Used by PostgreSQL buffer manager.
W-TinyLFU: Combines a small admission window (LRU) with a main cache (segmented LRU), using a frequency sketch for admission decisions. State-of-the-art for JVM caches.
CLOCK: An approximation of LRU using a circular buffer with reference bits. Used by most OS page replacement algorithms due to low overhead.

Cache Eviction Policies

Access a Key

Run Scenario

Live Hit Rates

Cache State Capacity = 5 items

Related Tools

LRU Cache

How Caching Works

How Redis Works

LSM-Tree vs B-Tree Simulator