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: Almost never used in production caches. Occasionally useful in streaming/pipeline buffers.

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.
• Default in: Redis (allkeys-lru), Memcached, CPU L1/L2 caches, Linux page cache.

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 (within 10-15% of LRU for many workloads). Zero metadata overhead — no pointers, no counts, no timestamps. No locking contention.
• 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: Complex implementation. Patented by IBM (though the patent has expired).
• Used in: ZFS filesystem, PostgreSQL buffer manager, IBM DB2.

Selecting a Policy

TTL: The Simpler Alternative

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

Redis offers 8 eviction policies you can configure:

maxmemory 4gb
maxmemory-policy allkeys-lru

Interview Tips 💡

1. Default to LRU: "For most use cases, LRU is the right choice because of temporal locality — recently accessed data is likely to be accessed again."
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