Cache Eviction Policies

Eviction Policies

Cache memory (RAM) is finite and expensive. A 64GB Redis instance can hold only so much data. When the cache is full and a new item arrives, the cache must decide which existing item to evict to make room. This decision is made by the Eviction Policy, and choosing the right one can dramatically impact your system's hit rate and performance.

1. FIFO (First In, First Out)

The simplest approach. A basic queue — the first item added is the first one removed.

• Logic: Removes the oldest inserted item, regardless of how often or recently it's used.
• Pros: O(1) complexity. Extremely simple implementation — just a queue.
• Cons: Terrible performance for most real-world workloads. It might delete your most popular "Homepage" data just because it was loaded first.
• Use case: Simple queues and some modern cache designs; assess the actual access trace rather than ruling out FIFO by name.

2. LRU (Least Recently Used)

The industry standard. Based on the principle of temporal locality: if you accessed it recently, you'll probably access it again.

• Logic: Tracks the time of the last access. Discards the item that hasn't been used for the longest time.
• Data Structure: Implemented with a Doubly Linked List + Hash Map for O(1) operations.
  • Access: Move the accessed node to the head of the list.
  • Evict: Remove the node at the tail of the list.
  • Insert: Add new node to the head. If capacity exceeded, evict from the tail.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: str):
        if key not in self.cache:
            return None  # Cache miss
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: str, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Evict least recently used (first item)
            self.cache.popitem(last=False)

# Usage
cache = LRUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
cache.get("a")      # Access 'a', moves to end
cache.put("d", 4)   # Evicts 'b' (least recently used)

• Pros: Matches most human behavior (recency bias). O(1) for all operations.
• Cons: Susceptible to scan pollution. If a user requests 1 million random items once (like a batch job), it flushes out all your useful cached items.
• Implementation note: Redis offers approximate LRU when explicitly configured. Its default policy is noeviction; operating-system and CPU replacement policies vary.

3. LFU (Least Frequently Used)

Tracks popularity rather than recency. Items accessed many times are kept; items accessed rarely are evicted.

• Logic: Maintains a count of accesses per key. Discards the item with the lowest count.

• Data Structure: Hash Map + Min-Heap or frequency buckets (doubly linked lists per frequency level).

• Pros: Immune to one-off scan pollution. Keeps "heavy hitters" in cache.

• Cons:

  • Complex: Maintaining accurate counts is expensive.
  • Stagnation: An item that was popular yesterday (viral news article) stays in cache today even if no one reads it anymore. Needs an aging/decay mechanism.
  • Cold start: New items start with count=1 and get evicted immediately before they have a chance to prove popularity.

• Use case: CDN caching (popular assets stay cached), search autocomplete (frequent queries stay warm).

4. LRU-K (Look Back K References)

An evolution of standard LRU. Instead of considering only the most recent access, it considers the Kth most recent access.

• Logic: Track the last K access times. Evict the item whose Kth-to-last access is oldest.
• LRU-2 example: Evict the item whose second-to-last access was longest ago. This naturally filters out one-off accesses.
• Pros: Much better than basic LRU at handling scans. An item accessed only once won't displace a frequently-used item.
• Cons: Requires storing K timestamps per item. Higher memory overhead.

5. Random Replacement

Does exactly what it says. When eviction is needed, randomly pick a key and delete it.

• Pros: Surprisingly effective in practice (effectiveness depends on the workload). Avoids per-key recency/frequency metadata, but the cache still needs indexing and concurrency control.
• Cons: Non-deterministic. Might delete a hot key. Not suitable when cache misses are expensive.
• Used in: Redis (allkeys-random), some CPU cache architectures.

6. ARC (Adaptive Replacement Cache)

A sophisticated hybrid algorithm that automatically tunes between recency (LRU) and frequency (LFU) based on the current workload.

• Logic: Maintains two LRU lists:
  • L1: Items accessed only once recently (recency).
  • L2: Items accessed multiple times recently (frequency).
  • A parameter p dynamically adjusts the size of L1 vs L2 based on which list's evictions are causing more cache misses.
• Pros: Self-tuning. Handles both scan-heavy and frequency-heavy workloads. Often outperforms both LRU and LFU.
• Cons: More lists and bookkeeping than simple LRU.
• Implementation example: OpenZFS uses an adaptive replacement cache. PostgreSQL should not be described as using ARC; its shared-buffer replacement follows a clock-sweep approach.

Selecting a Policy

TTL: Freshness and expiry

Sometimes you don't need a complex algorithm. You use TTL (Time To Live): "Delete everything after N minutes/seconds."

# Redis: Set key with 10-minute TTL
SET session:user123 "data" EX 600

Best for: Session data, OAuth tokens, stock prices, weather data — anything where age determines validity, not usage patterns.

Combining TTL + Eviction: Most production systems use both. TTL removes stale data proactively, while LRU/LFU handles capacity limits reactively.

Redis Eviction Configuration

These are common Redis eviction policies; check the policy set for your installed version:

maxmemory 4gb
maxmemory-policy allkeys-lru

Interview Tips 💡

1. Test recency as a hypothesis: "I would replay the observed access trace with LRU and LFU, then compare hit rate and origin cost at the same memory budget."
2. Know the data structure: "LRU is implemented with a doubly linked list + hash map for O(1) get/put/evict."
3. Mention the scan problem: "LRU is vulnerable to cache pollution from batch scans. LRU-K or ARC solves this."
4. Discuss TTL vs. eviction: "TTL handles freshness, eviction handles capacity. Production systems use both."
5. Redis specifics: "Redis uses approximated LRU (sampling 5 random keys) rather than true LRU to save memory on metadata."

Related Concepts

• Caching Overview — Why we cache and where caches live
• Caching Strategies — Cache-aside, write-through, write-back
• Redis Internals — How Redis implements eviction
• Rate Limiting — Another use of the Token Bucket algorithm

Sources and a design check

Redis key eviction documents policy configuration and approximate algorithms. Test a burst of one-time scan keys against a stable hot set. Compare missed bytes and origin latency as well as hit count: losing one expensive object can matter more than losing many cheap ones.