Understanding Cache Eviction Strategies Comparison: System Performance

Introduction and Core Concepts

Cache eviction strategies comparison is the systematic evaluation of policies that determine which data to remove from a cache when it reaches capacity. Every cache, whether it is a CPU L1 cache of 32KB or a distributed Redis cluster of 500GB, faces the same fundamental constraint: fast storage is finite. When a new item must be inserted into a full cache, an eviction strategy decides the victim. The choice directly impacts hit rate, latency, throughput, and ultimately system performance and cost.

At its core, caching exploits temporal and spatial locality — the principle that recently or frequently accessed data is likely to be accessed again soon. An effective eviction strategy preserves the working set, the subset of data actively used by an application, while discarding cold data. A poor strategy causes thrashing, where the cache constantly evicts data that is immediately requested again, driving the hit rate toward zero and forcing expensive trips to the backing store such as a database or disk.

Understanding cache eviction strategies comparison matters because no single policy is optimal for all workloads. An LRU (Least Recently Used) policy that excels for web session caching may perform poorly for a recommendation engine with skewed popularity distribution where LFU (Least Frequently Used) is superior. System architects must compare strategies based on access patterns, read/write ratios, memory overhead, implementation complexity, and latency requirements. This comparison enables data-driven decisions that can reduce p95 latency by 40-60%, cut database load by an order of magnitude, and significantly lower infrastructure costs.

This article provides a comprehensive cache eviction strategies comparison, covering how each major strategy works, its implementation in Python, its computational complexity, and its real-world trade-offs. Whether you are designing a browser cache, a database buffer pool, or a CDN edge node, this guide will help you select and tune the right eviction policy for your system's performance goals.

How It Works

All cache eviction strategies operate on the same abstract model: a fixed-capacity store that supports get(key) and put(key, value) operations. On a cache hit, data is returned quickly. On a cache miss, data is fetched from the slower backing store. When a put finds the cache full, the eviction algorithm selects one or more keys to remove. The difference between strategies lies entirely in the selection criteria and the metadata they maintain to make that decision.

Recency-Based Strategies: LRU and MRU

LRU evicts the item that has not been accessed for the longest time. It assumes that if an item has not been used recently, it is unlikely to be used in the near future. LRU is typically implemented with a doubly linked list ordered by access time plus a hash map for O(1) lookups. The head of the list is the most recently used, the tail is the least recently used and is evicted. MRU (Most Recently Used) does the opposite, evicting the most recent item. While counterintuitive, MRU is optimal for workloads like repeated database scans where the most recently accessed page is least likely to be needed again.

Frequency-Based Strategies: LFU and LFU Variants

LFU evicts the item with the lowest access frequency. It maintains a counter per key and removes the least popular item, often breaking ties with LRU. LFU excels when access distribution is highly skewed, such as Zipfian distributions common in web content, social media feeds, and e-commerce catalogs where a small set of hot keys receives 80% of traffic. Its weakness is cache pollution: an item that was very popular in the past but is now cold can linger because its historical high count prevents eviction. Modern variants like Window-TinyLFU address this with decay and admission filters.

Order and Approximation Strategies: FIFO, Random, and Clock

FIFO (First-In, First-Out) evicts the oldest inserted item regardless of access pattern, using a simple queue. It is cheap but blind to locality. Random eviction selects a victim uniformly at random, requiring almost no metadata and surprisingly competitive performance at large scale. Clock, also called Second Chance, is a scalable approximation of LRU designed for operating systems. It arranges cache entries in a circular buffer with a reference bit. A clock hand sweeps around; if the bit is 1, it clears it and gives the page a second chance, if 0, it evicts. This achieves near-LRU hit rates with O(1) amortized cost and no linked list pointer overhead, making it ideal for high-concurrency buffer pools.

Adaptive and Hybrid Strategies: ARC and SLRU

Advanced strategies adapt to changing workloads. ARC (Adaptive Replacement Cache) dynamically balances between recency and frequency by maintaining two lists: T1 for items seen once (recency) and T2 for items seen multiple times (frequency), plus ghost lists that track evicted keys to learn from misses. SLRU (Segmented LRU) divides the cache into a probationary segment and a protected segment. New items enter the probationary segment; only upon a second hit are they promoted to the protected segment. This prevents scan pollution where a one-time sequential scan would otherwise flush the entire cache.

Implementation

Implementing eviction strategies correctly requires careful handling of metadata updates on both get and put paths. The following Python examples show production-inspired implementations with detailed comments, O(1) operations where possible, and proper handling of edge cases like capacity zero and tie-breaking.

LRU Implementation with OrderedDict

This is the canonical Python LRU implementation. OrderedDict maintains insertion order and allows efficient move-to-end operations. For interview settings, you may be asked to implement the doubly linked list manually to demonstrate pointer manipulation.

from collections import OrderedDict

class LRUCache:
    """LRU Cache with O(1) get and put using OrderedDict."""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # Move to end to mark as recently used
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing key and mark as recent
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # popitem(last=False) removes first item = LRU victim
            self.cache.popitem(last=False)

# Usage:
# cache = LRUCache(2)
# cache.put(1, 1); cache.put(2, 2)
# cache.get(1)  # returns 1, makes key 1 MRU
# cache.put(3, 3)  # evicts key 2

LFU Implementation with Frequency Buckets

An efficient LFU requires O(1) eviction of the least frequent item and O(1) frequency updates. We use a hash map for key-to-value, a hash map for key-to-frequency, and a dictionary of frequency to OrderedDict for tie-breaking by recency.

from collections import defaultdict, OrderedDict

class LFUCache:
    """LFU Cache with O(1) operations and LRU tie-breaker."""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_val = {}
        self.key_to_freq = {}
        self.freq_to_keys = defaultdict(OrderedDict)
        self.min_freq = 0

    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        freq = self.key_to_freq[key]
        # Remove from current freq bucket
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq] and freq == self.min_freq:
            self.min_freq += 1
        # Increase frequency
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = None
        return self.key_to_val[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self.get(key)  # Reuse logic to bump frequency
            return
        if len(self.key_to_val) >= self.capacity:
            # Evict LFU + LRU tie-breaker (first in OrderedDict)
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

FIFO and Random: Lightweight Baselines

FIFO and Random are valuable as baselines and for workloads where metadata overhead must be minimal. FIFO uses a queue to track insertion order, while Random avoids any ordering structure entirely.

from collections import deque
import random

class FIFOCache:
    """FIFO evicts oldest inserted item, ignores access pattern."""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.queue = deque()

    def get(self, key: int) -> int:
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            return
        if len(self.cache) >= self.capacity:
            oldest = self.queue.popleft()
            del self.cache[oldest]
        self.cache[key] = value
        self.queue.append(key)


class RandomCache:
    """Random eviction with O(1) average put via random.choice."""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.keys = []

    def get(self, key: int) -> int:
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            return
        if len(self.cache) >= self.capacity:
            evict = random.choice(self.keys)
            del self.cache[evict]
            self.keys.remove(evict)
        self.cache[key] = value
        self.keys.append(key)

Clock (Second Chance) Approximation of LRU

Clock is widely used in PostgreSQL, MySQL InnoDB, and Linux page cache because it avoids global locks on a linked list. Each entry has a reference bit set on access; the hand clears bits until it finds a victim.

class ClockCache:
    """Clock (Second Chance) approximation of LRU using circular buffer."""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> (value, ref_bit)
        self.clock = []  # list of keys in circular order
        self.pointer = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        value, _ = self.cache[key]
        # Set reference bit to 1 on access
        self.cache[key] = (value, 1)
        return value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = (value, 1)
            return
        if len(self.cache) < self.capacity:
            self.cache[key] = (value, 1)
            self.clock.append(key)
            return
        # Find victim with ref_bit == 0
        while True:
            curr_key = self.clock[self.pointer]
            _, ref = self.cache[curr_key]
            if ref == 0:
                # Evict this key
                del self.cache[curr_key]
                self.cache[key] = (value, 1)
                self.clock[self.pointer] = key
                self.pointer = (self.pointer + 1) % self.capacity
                break
            else:
                # Give second chance
                val, _ = self.cache[curr_key]
                self.cache[curr_key] = (val, 0)
                self.pointer = (self.pointer + 1) % self.capacity

Step-by-Step Example

To make the cache eviction strategies comparison concrete, consider a cache with capacity 3 and the access sequence: put(A), put(B), put(C), get(A), put(D). We will trace how LRU, LFU, and FIFO handle the final insertion of D when the cache is full.

Initial state after put(A), put(B), put(C) is identical for all strategies: cache contains {A, B, C} in insertion order. The next operation get(A) is where divergence begins. For LRU, accessing A moves it to the most-recently-used position. The recency order becomes B (oldest) -> C -> A (newest). For LFU, A’s frequency increments from 1 to 2, while B and C remain at 1. For FIFO, get operations do not affect order at all; the queue remains A -> B -> C.

Now put(D) triggers eviction. LRU evicts B, the least recently used, resulting in cache {C, A, D} and preserving the hot key A. LFU evicts B or C (both frequency 1) using LRU tie-breaker, typically B, resulting in {A, C, D}. FIFO evicts A, the first inserted, resulting in {B, C, D} — ironically evicting the just-accessed hot key. This single example illustrates why FIFO can have pathological hit rates for workloads with hot keys that were inserted early.

Extend the sequence with get(B), get(B), get(C), put(E). Now LFU shines. Frequencies are A:2, C:2, D:1, B:2 after the gets. When E arrives, LFU will evict D (frequency 1), keeping the frequently used keys. LRU, however, would evict A if the gets were interleaved differently, because recency does not capture long-term popularity. This demonstrates the core trade-off: LRU protects recent working sets, LFU protects popular working sets, and the optimal choice depends on whether your workload exhibits temporal locality or skewed popularity.

For a second scenario, imagine a sequential scan of 1000 keys with cache capacity 100. LRU would be disastrous: each new scan key pushes out useful working set entries, and after the scan, the cache contains only the last 100 scan keys which will never be reused — a phenomenon called scan pollution. SLRU or ARC would absorb the scan in the probationary list and protect the hot working set. This is why database buffer pools almost never use pure LRU; they use variants like LRU-K or Clock with admission control.

Complexity Analysis

Performance of cache eviction strategies is measured on two axes: time complexity per operation and space overhead for metadata. Time complexity determines request latency and CPU overhead, while space overhead determines how much of your precious cache memory is wasted on bookkeeping rather than actual data.

LRU with a hash map plus doubly linked list achieves O(1) for both get and put, but requires two pointers per entry (prev, next) plus hash map overhead. Naive LRU using an array or list would be O(n) for eviction due to shifting. LFU’s naive implementation using a heap is O(log n) for updates, but the optimized frequency-bucket approach shown above achieves O(1) amortized time by using hash maps of OrderedDicts, at the cost of higher memory overhead for multiple dictionaries.

FIFO and Random are the cheapest: O(1) time and O(n) space with minimal constants. Clock is also O(1) amortized, though worst-case put can be O(n) when the hand must sweep the entire circular buffer clearing reference bits. ARC and SLRU have O(1) time but maintain ghost lists that double the metadata size, trading memory for adaptability.

The choice impacts tail latency under contention. LRU’s linked list requires global locking or fine-grained locking for move-to-end, creating a bottleneck at high concurrency. Clock and Random avoid this by using per-entry bits or no ordering at all, making them more scalable for multi-threaded caches. This is why modern high-throughput caches like Caffeine and Redis favor TinyLFU and Clock variants over strict LRU.

Space complexity is always O(n) asymptotically, but constant factors matter. For a cache storing 10 million small objects, an extra 16 bytes per entry for LRU pointers consumes 160 MB of RAM. In memory-constrained environments like CPU caches or embedded systems, Random or Clock’s single bit per entry can be the deciding factor.

Variations and Optimizations

Pure strategies are rarely deployed in production. Real systems layer optimizations to handle pollution, adapt to shifting workloads, and reduce overhead. Understanding these variations is essential for a meaningful cache eviction strategies comparison.

SLRU and LRU-K

SLRU (Segmented LRU) splits the cache into probation (e.g., 20%) and protected (80%) segments. New entries enter probation; a hit promotes them to protected. Eviction always targets probation first. This simple two-queue design filters out one-hit wonders and scans. LRU-K generalizes LRU by considering the K-th most recent access time rather than just the last. LRU-2, used in InnoDB, evicts the item whose second-to-last access is oldest, providing better scan resistance than LRU while remaining relatively simple.

TinyLFU and W-TinyLFU

TinyLFU is an admission filter that sits in front of a main cache (often SLRU). It uses a compact sketch (Count-Min Sketch with aging) to estimate frequencies with ~4 bits per entry. On insertion, it compares the candidate’s estimated frequency against the victim’s; only if the candidate is more frequent is it admitted. This prevents pollution without storing full counters. W-TinyLFU, used in Caffeine (Java) and adopted by many high-performance caches, combines a window cache (LRU), a main cache (SLRU), and a TinyLFU filter, achieving near-optimal hit rates across diverse workloads with minimal memory.

ARC: Adaptive Replacement Cache

ARC, invented by IBM, maintains four lists: T1 (recent, seen once), T2 (frequent, seen twice), B1 and B2 (ghost histories for T1 and T2). It adaptively adjusts the target size of T1 vs T2 based on misses in B1 vs B2. If many misses occur in B1, the workload favors recency, so ARC grows T1; if misses in B2 dominate, it favors frequency and grows T2. ARC is scan-resistant and workload-adaptive but is patent-encumbered and more complex to implement correctly. Variants like CAR and CLOCK-Pro provide similar adaptivity with Clock-style efficiency.

Other optimizations include TTL-aware eviction (combining recency with expiration), size-aware eviction (evicting large objects first to maximize number of cached items), and write-aware policies (preferring to evict clean pages over dirty pages to avoid write-back cost). Modern CDN caches often use GD-Size or GDSF, which weight frequency, recency, size, and cost in a single utility function.

Real-World Applications

Cache eviction strategy choice is not academic; it determines the performance and cost of nearly every large-scale system. Different domains exhibit distinct access patterns that favor different policies.

Web servers and CDNs like Cloudflare, Akamai, and Varnish handle content with Zipfian popularity: a few viral assets dominate traffic. LFU and TinyLFU excel here because they keep hot objects pinned. However, CDNs also serve large, infrequently accessed long-tail content, so size-aware variants are critical to avoid caching a single 2GB video at the expense of thousands of small images. Many CDNs use a hybrid: LRU for small objects, LFU for large objects, with TTL as a first-level filter.

Database buffer pools (PostgreSQL shared_buffers, MySQL InnoDB buffer pool, Oracle SGA) cache disk pages. Workloads mix OLTP point lookups (high locality) with OLAP scans (sequential, low reuse). Pure LRU would be thrashed by scans, so databases use Clock, LRU-K, or ARC. PostgreSQL uses Clock Sweep, InnoDB uses a midpoint insertion LRU where new pages are inserted at 3/8 of the list to protect hot pages from scans.

Operating system page replacement manages virtual memory. Linux uses a variant of Clock called LRU with active/inactive lists, while Windows uses Clock with working set trimming. CPU hardware caches (L1/L2/L3) use pseudo-LRU or Tree-PLRU due to hardware constraints — true LRU is too expensive in silicon for 8-way associative caches, so binary tree approximations are used.

Choosing incorrectly has measurable cost. A study of Twitter’s cache fleet showed switching from pure LRU to TinyLFU improved hit rates by 5-10% at same memory, translating to millions of dollars in reduced database load. Conversely, using LFU for a news feed where popularity shifts hourly would retain yesterday’s headlines while evicting breaking news.

Comparison with Alternatives

A thorough cache eviction strategies comparison must weigh hit rate, overhead, and workload fit side by side. The table below summarizes the key dimensions system designers evaluate when selecting a policy. No strategy dominates on all axes; the art is matching the strategy to the workload’s locality profile and the system’s resource constraints.

Hit rate is workload-dependent: LRU wins for recency-heavy workloads, LFU for frequency-heavy, ARC for mixed or shifting workloads. Implementation overhead includes metadata size, CPU cycles per operation, and concurrency scalability. Scan pollution resistance measures how well the strategy protects hot working sets during sequential scans. Adaptivity indicates whether the strategy self-tunes without manual reconfiguration.

For most new systems, the decision tree is: if simplicity and low overhead are paramount and hit rate requirements are modest, start with LRU or Clock. If workload is known to be Zipfian and stable, choose LFU or TinyLFU. If workload is unknown, mixed, or includes scans, invest in ARC or W-TinyLFU. Always benchmark with production traces rather than synthetic uniform random access, as synthetic benchmarks can mislead by favoring Random or FIFO unrealistically.

Common Mistakes and Best Practices

Even with the right strategy, implementation pitfalls can nullify performance gains. The most common mistake is treating cache eviction as a purely algorithmic problem while ignoring system-level concerns like TTL, memory fragmentation, and thundering herd.

A frequent error is using pure LRU without scan protection in a database or analytics system. A single large table scan will evict the entire hot working set, causing a prolonged period of cache misses and database overload after the scan completes. Best practice is to use SLRU, LRU-K, or admission filters to isolate scans. Another mistake is implementing LFU without decay or aging. Without periodic decrement of counters, old popular items become immortal and prevent new hot items from entering. Solutions include halving counters periodically or using TinyLFU’s reset mechanism.

Ignoring object size is another pitfall. Evicting one 10MB object to make room for one 1KB object is wasteful if the goal is to maximize hit count or byte hit rate. Size-aware policies like GD-Size consider size and cost. Similarly, not accounting for write cost — evicting dirty pages that require write-back to disk — can create latency spikes. Prefer evicting clean pages when possible.

Concurrency mistakes include using a single global lock for LRU list updates, which serializes all cache accesses. Use sharded caches, lock-free structures, or Clock which requires only per-entry bits. Finally, failing to monitor hit rate, eviction rate, and working set size leads to misconfigured capacity. Set up metrics and alerts, and use adaptive sizing where possible.

• Do benchmark with real traces: Replay production access logs through different policies using tools like libCacheSim to measure hit rate before deploying.
• Combine TTL with eviction: Use TTL for freshness and eviction for capacity; do not rely on eviction alone to expire stale data.
• Implement admission control: Use a TinyLFU filter or bloom filter to reject one-hit wonders before they pollute the main cache.
• Shard for scalability: Partition cache by key hash to reduce lock contention; each shard can run its own LRU or Clock independently.
• Handle thundering herd: On miss, use single-flight or lease mechanisms so only one thread fetches the backing store while others wait.
• Size your cache correctly: Monitor working set size; a cache smaller than the working set will thrash regardless of strategy. Aim for cache size 10-20% larger than hot working set.
• Test edge cases: Capacity zero, duplicate puts, concurrent gets/puts, and eviction during iteration must be handled without corruption.

Interview Questions

Cache eviction strategies are a staple of system design and data structure interviews. Interviewers test both conceptual understanding and ability to implement O(1) designs under constraints.

Q1: Design an LRU Cache with O(1) get and put. How would you extend it to LFU?

Answer: LRU requires a hash map for O(1) lookup plus a doubly linked list to maintain recency order. On get, move node to head; on put, insert at head and evict tail if over capacity. For LFU, maintain key->freq and freq->OrderedDict maps plus min_freq pointer. On access, move key to next frequency bucket; on eviction, remove from min_freq bucket’s LRU end. Discuss trade-offs: LFU needs more metadata and tie-breaking logic, and naive heap-based LFU is O(log n) not O(1).

Q2: Why does LRU perform poorly for a sequential scan workload, and how would you fix it?

Answer: A scan of N > cache size items will evict all hot working set entries, and the scanned items themselves have no reuse, so hit rate drops to zero — scan pollution. Fixes include SLRU (probation/protected segments), LRU-K (require K hits before promotion), Clock with admission control, or ARC which adaptively balances recency and frequency. Mention that databases use midpoint insertion or TinyLFU filters to mitigate this.

Q3: Compare LRU vs LFU hit rates for a Zipfian distribution. Which would you choose for a CDN?

Answer: Zipfian distribution has a few very hot keys and a long tail. LFU achieves higher hit rate because it pins hot keys regardless of recency gaps, while LRU may evict a hot key if it hasn’t been accessed recently due to interleaving tail accesses. For a CDN serving static assets with stable popularity, LFU or TinyLFU is preferred, often combined with size-aware weighting. Add nuance: if popularity shifts quickly (news), LRU or ARC may be better due to LFU’s inertia.

Q4: What is the Clock algorithm and why is it used in operating systems instead of true LRU?

Answer: Clock approximates LRU with a circular buffer and reference bits. A hand sweeps, clearing bits of recently used pages and evicting the first with bit 0. True LRU requires a doubly linked list with global locking on every access, which is expensive and contention-heavy in kernels handling thousands of page faults per second. Clock provides near-LRU hit rates with O(1) amortized cost, per-page bits, and no global list, making it scalable and hardware-friendly.

Q5: How would you implement a cache that supports both TTL expiration and LRU eviction?

Answer: Combine two mechanisms: a hash map + linked list for LRU, plus a priority queue (min-heap) or timing wheel for TTL expiry, or lazy expiration on access. On get, check if entry expired (current_time > expire_time) and treat as miss if so. A background sweeper thread can proactively evict expired entries to free memory. Discuss trade-offs: eager expiry via heap is O(log n) but frees memory promptly; lazy expiry is O(1) but holds dead entries longer. Mention that Redis uses lazy + periodic active expiry.