Chapter 10 of 33

Cache Strategies & Eviction Policies

In the previous chapter, Caching, we learned what a cache is, where it lives and why it helps. Two practical questions were left open:

  1. How do the cache and the database stay in step? When the application reads, who loads the cache? When it writes, which one is updated first: the cache, the database, or both?

  2. What happens when the cache is full? Memory is limited, so some entry must be thrown out. Which one?

The answers to the first question are called caching strategies (or caching patterns). The answers to the second are eviction policies. Both are favourite interview topics, and "implement an LRU cache" is one of the most frequently asked coding questions in product-company interviews.

A caching strategy defines how reads and writes flow between the application, the cache and the database. An eviction policy decides which entry to remove when the cache runs out of space.


Part 1: Caching Strategies

1. Cache-Aside (Lazy Loading)

The application manages the cache itself. The cache does not know the database exists. This is the most common pattern, and it is what our get_product function did in the previous chapter.

READ                                         WRITE
1. App reads key from cache                  1. App writes the new value to the DB
2. HIT  → return it                          2. App DELETES the key from the cache
   MISS → 3. App reads from DB                  (the next read will reload it)
          4. App stores the value in cache
          5. Return it

        ┌─────┐  1,4  ┌───────┐
        │ App │──────→│ Cache │
        └──┬──┘       └───────┘
           │ 3 (only on a miss)
           ▼
        ┌──────┐
        │  DB  │
        └──────┘

Pros: only data that is actually requested gets cached; if the cache goes down, the app still works (just slower); any data model can be cached.

Cons: every miss costs three steps (cache, database, cache write); the first request after expiry is slow; the app code is responsible for keeping the cache correct.

Why delete on write instead of update?

If two requests update the same row at nearly the same time, "write DB then update cache" can leave the cache with the older value, depending on which request reaches the cache last. Deleting is safer: the next read loads whatever is in the database. Deleting is also cheaper when the cached value is expensive to compute and might not even be read again.

The race condition you should know about

Even delete-on-write has a rare race. Follow this timeline carefully:

Time  Request R (reader)                     Request W (writer)
 t1   cache MISS for key
 t2   reads OLD value from DB
 t3                                          writes NEW value to DB
 t4                                          deletes key from cache
 t5   puts OLD value into cache   ← stale until TTL expires!

The reader's slow path overlapped with the writer. Common mitigations:

  • Always use a TTL, so a stale entry cannot live forever.

  • Delayed double delete: delete the key after the write, then delete it again a short time later (for example 500 ms) to catch a racing reader.

  • Versioned values: store a version number with each value and refuse to overwrite a newer version with an older one.

  • Invalidate from the database's change log: a separate process reads the database's committed changes (change data capture) and deletes cache keys after each commit.

2. Read-Through

The application talks only to the cache. On a miss, the cache itself loads the data from the database (using a loader function you configure), stores it and returns it.

  App ──read──→ Cache ──(miss: cache loads it)──→ DB

The behaviour is like cache-aside, but the loading logic lives inside the cache layer or library (for example, a loading cache in Caffeine, or a caching layer built into a data access library). Application code becomes simpler: it just calls cache.get(key).

3. Write-Through

Every write goes to the cache and to the database synchronously, as part of the same operation. The write is reported successful only after both are updated.

  App ──write──→ Cache ──write (same request)──→ DB
                   ↑ caller waits until both succeed

Pros: the cache is always up to date with the database for written keys, so reads after writes are fresh and fast.

Cons: higher write latency (two writes per operation); data that is written but never read still occupies cache space. Usually combined with read-through so the cache is the single access point.

4. Write-Behind (Write-Back)

Writes go to the cache, and the call returns immediately. The cache writes the changes to the database later, asynchronously, often in batches.

  App ──write──→ Cache ──→ (queue) ──later, batched──→ DB
                   ↑ returns immediately

Pros: very fast writes; many updates to the same key can be merged (100 view-count increments become one database write); smooths out write spikes.

Cons: risk of data loss if the cache node fails before flushing; the database is temporarily behind; more complex to build correctly. Suitable for counters, analytics and metrics, not for payments.

This is the same idea as the write-back policy in CPU caches that you may have studied in computer organisation, where a modified ("dirty") block is written to memory only when it is evicted.

5. Write-Around

Writes go directly to the database, skipping the cache. The cache gets filled only when the data is read (usually via cache-aside or read-through).

Use it when written data is unlikely to be read soon, for example log entries, archived records or bulk imports. It keeps the cache from filling up with data nobody asks for. The cost: the first read after a write is always a miss.

6. Refresh-Ahead

The cache reloads popular entries before they expire. For example, if an entry has a 60-second TTL and is read after 50 seconds, the cache returns it immediately and starts a background refresh.

Pros: hot keys almost never cause a slow miss, and stampedes on popular keys are avoided. Cons: wasted work if the prediction is wrong, and more load on the database for keys that may not be needed again.

Comparing the Strategies

Strategy

Who loads/writes the DB

Read after write

Write speed

Main risk

Good for

Cache-aside

Application

Miss, then fresh

DB speed

Stale data from races; miss penalty

General purpose, read-heavy apps

Read-through

Cache (on read)

Miss, then fresh

-

Miss penalty

Simplifying app code

Write-through

Cache (sync)

Hit, fresh

Slower

Caching unread data

Data read soon after writing

Write-behind

Cache (async)

Hit, fresh

Fastest

Data loss on cache failure

Counters, metrics, high write rates

Write-around

Application, to DB only

Miss

DB speed

Miss on recently written data

Write-once, rarely read data

Refresh-ahead

Cache (before expiry)

-

-

Wasted refreshes

Very hot keys with predictable reads

In practice, strategies are combined: read-through + write-through, cache-aside + write-around, or cache-aside + refresh-ahead for the hottest keys. In an interview, the safe default answer is: "cache-aside with delete-on-write and a TTL", followed by a sentence on its race condition.


Part 2: Eviction Policies

First, separate two ideas that students often mix up:

  • Expiration removes an entry because its TTL is over (it is too old to trust).

  • Eviction removes an entry because the cache is full and needs space (even though the entry is still valid).

The eviction policy tries to throw out the entry that is least likely to be needed soon, so the hit ratio stays high.

The Common Policies

Policy

Evicts

Strength

Weakness

FIFO (First In, First Out)

The oldest inserted entry

Trivial to implement

Ignores usage: may evict a very popular item

LRU (Least Recently Used)

The entry not accessed for the longest time

Adapts to changing popularity; great general default

A one-time scan of many keys flushes out the hot ones

LFU (Least Frequently Used)

The entry with the fewest accesses

Keeps long-term favourites; resists scans

Old popular items linger; new items get evicted too quickly (needs aging)

MRU (Most Recently Used)

The entry used most recently

Good for cyclic scans larger than the cache

Bad for normal workloads

Random

Any entry at random

No bookkeeping at all

Can evict hot items

TTL-based

The entry closest to expiry

Uses knowledge the app gave

Only as good as the TTLs chosen

OPT (Belady's optimal)

The entry whose next use is farthest in the future

Fewest possible misses

Needs the future: impossible in practice; used as a benchmark

Worked Trace: FIFO vs LRU vs LFU vs OPT

Cache capacity = 3. Request sequence: 7 0 1 2 0 3 0 4 2 3 0 3 2 (the same style as page replacement questions in operating systems). Here is the LRU trace step by step; the list is ordered from least recently used (left) to most recently used (right).

Req  Result  Cache (LRU → MRU)   Note
 7   miss    [7]
 0   miss    [7 0]
 1   miss    [7 0 1]
 2   miss    [0 1 2]             evict 7 (least recently used)
 0   HIT     [1 2 0]             0 becomes most recent
 3   miss    [2 0 3]             evict 1
 0   HIT     [2 3 0]
 4   miss    [3 0 4]             evict 2
 2   miss    [0 4 2]             evict 3
 3   miss    [4 2 3]             evict 0
 0   miss    [2 3 0]             evict 4
 3   HIT     [2 0 3]
 2   HIT     [0 3 2]

LRU: 4 hits, 9 misses

The program below runs all four policies on the same sequence (LFU breaks ties between equal counts by evicting the least recently used of them, and an evicted key's count starts again from zero).

from collections import OrderedDict, deque

def fifo(refs, cap):
    cache, order, hits, trace = set(), deque(), 0, []
    for k in refs:
        if k in cache:
            hits += 1; trace.append("H")
            continue
        trace.append("M")
        if len(cache) == cap:
            cache.remove(order.popleft())
        cache.add(k); order.append(k)
    return hits, trace

def lru(refs, cap):
    cache, hits, trace = OrderedDict(), 0, []
    for k in refs:
        if k in cache:
            hits += 1; trace.append("H")
            cache.move_to_end(k)
            continue
        trace.append("M")
        if len(cache) == cap:
            cache.popitem(last=False)        # least recently used is at the front
        cache[k] = True
    return hits, trace

def lfu(refs, cap):
    # evict the lowest count; ties broken by least recently used
    cache, freq, last, hits, trace = set(), {}, {}, 0, []
    for t, k in enumerate(refs):
        if k in cache:
            hits += 1; trace.append("H")
        else:
            trace.append("M")
            if len(cache) == cap:
                victim = min(cache, key=lambda x: (freq[x], last[x]))
                cache.remove(victim)
                del freq[victim]             # count restarts if it comes back
            cache.add(k)
        freq[k] = freq.get(k, 0) + 1
        last[k] = t
    return hits, trace

def opt(refs, cap):
    # Belady: evict the key whose next use is farthest in the future
    cache, hits, trace = set(), 0, []
    for i, k in enumerate(refs):
        if k in cache:
            hits += 1; trace.append("H")
            continue
        trace.append("M")
        if len(cache) == cap:
            def next_use(x):
                rest = refs[i + 1:]
                return rest.index(x) if x in rest else float("inf")
            cache.remove(max(cache, key=next_use))
        cache.add(k)
    return hits, trace

refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print("Requests :", " ".join(map(str, refs)), " (capacity 3)")
for name, fn in [("FIFO", fifo), ("LRU", lru), ("LFU", lfu), ("OPT", opt)]:
    hits, trace = fn(refs, 3)
    print(f"{name:<5}    : {' '.join(trace)}   hits={hits} misses={len(refs) - hits}")

Output:

Requests : 7 0 1 2 0 3 0 4 2 3 0 3 2  (capacity 3)
FIFO     : M M M M H M M M M M M H H   hits=3 misses=10
LRU      : M M M M H M H M M M M H H   hits=4 misses=9
LFU      : M M M M H M H M M M H H H   hits=5 misses=8
OPT      : M M M M H M H M H H M H H   hits=6 misses=7

OPT is the best possible (6 hits). No real policy can beat it, which makes it a useful yardstick: the closer a policy gets to OPT on your workload, the better it is. On this particular sequence LFU beat LRU because key 0 is used often; on other sequences LRU wins. No policy is best for every workload.


Implementing an LRU Cache in O(1)

The classic interview question: design a cache with get(key) and put(key, value), both in O(1) time, that evicts the least recently used entry when full.

The trick is to combine two data structures:

  • A hash map from key to node, for O(1) lookup.

  • A doubly linked list ordered by recency, for O(1) "move to front" and "remove from back". It must be doubly linked so a node can unlink itself without searching for its predecessor.

  HashMap: a → •   b → •   c → •
                │        │        │
                ▼        ▼        ▼
  head ⇄ [a] ⇄ [c] ⇄ [b] ⇄ tail
         most recent   least recent (evicted first)

Here is a complete Java 17 implementation, followed by the shortcut the JDK provides: a LinkedHashMap created in access order with removeEldestEntry overridden.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> {

    // A node of the doubly linked list: most recent near head, least recent near tail
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);   // dummy head
    private final Node<K, V> tail = new Node<>(null, null);   // dummy tail

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            return null;                        // miss
        }
        moveToFront(node);                      // it is now the most recently used
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {                     // update existing key
            node.value = value;
            moveToFront(node);
            return;
        }
        if (map.size() == capacity) {           // full: evict least recently used
            Node<K, V> lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);
            System.out.println("  evicted " + lru.key);
        }
        Node<K, V> fresh = new Node<>(key, value);
        addAfterHead(fresh);
        map.put(key, fresh);
    }

    private void moveToFront(Node<K, V> node) {
        unlink(node);
        addAfterHead(node);
    }

    private void unlink(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addAfterHead(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    @Override
    public String toString() {                  // most recent first
        StringBuilder sb = new StringBuilder("[");
        for (Node<K, V> n = head.next; n != tail; n = n.next) {
            sb.append(n.key).append(n.next != tail ? ", " : "");
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(3);
        cache.put("a", "Apple");
        cache.put("b", "Banana");
        cache.put("c", "Cherry");
        System.out.println("After a, b, c       : " + cache);
        System.out.println("get(a)              : " + cache.get("a"));
        System.out.println("Order now           : " + cache);
        System.out.println("put(d)");
        cache.put("d", "Date");
        System.out.println("Order now           : " + cache);
        System.out.println("get(b)              : " + cache.get("b"));

        // The same behaviour with the JDK: LinkedHashMap in access order
        Map<String, String> jdk = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > 3;
            }
        };
        jdk.put("a", "Apple");
        jdk.put("b", "Banana");
        jdk.put("c", "Cherry");
        jdk.get("a");
        jdk.put("d", "Date");
        System.out.println("LinkedHashMap keys  : " + jdk.keySet() + "  (least recent first)");
    }
}

Output:

After a, b, c       : [c, b, a]
get(a)              : Apple
Order now           : [a, c, b]
put(d)
  evicted b
Order now           : [d, a, c]
get(b)              : null
LinkedHashMap keys  : [c, a, d]  (least recent first)

After get(a), the key a moved to the front, so when d arrived the least recently used key was b, not a. Both get and put do a constant number of hash map and pointer operations: O(1) time, O(capacity) space. In Python, collections.OrderedDict with move_to_end gives the same structure, and functools.lru_cache applies it to function results.


Implementing an LFU Cache in O(1)

LFU is harder: we must find the least frequent key quickly and update counts in O(1). The standard solution keeps:

  • a map key → value and a map key → count;

  • for each count, an ordered set of keys with that count (oldest first, to break ties by LRU);

  • the current minimum count. A new key always has count 1, so after an insertion the minimum is 1; after a key's count goes up, the minimum only increases if that key's old bucket became empty.

from collections import defaultdict, OrderedDict


class LFUCache:
    """O(1) LFU cache. Ties between equally frequent keys are broken by LRU."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}                              # key -> value
        self.freq = {}                                # key -> use count
        self.buckets = defaultdict(OrderedDict)       # count -> keys (oldest first)
        self.min_freq = 0

    def _touch(self, key):
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None

    def get(self, key):
        if key not in self.values:
            return None
        self._touch(key)
        return self.values[key]

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.values:
            self.values[key] = value
            self._touch(key)
            return
        if len(self.values) == self.capacity:
            victim, _ = self.buckets[self.min_freq].popitem(last=False)
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.values[victim]
            del self.freq[victim]
            print(f"  evicted {victim}")
        self.values[key] = value
        self.freq[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1                             # a new key always has count 1


cache = LFUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
for _ in range(3):
    cache.get("a")              # a used 4 times in total
cache.get("b")                  # b used 2 times
print("counts:", cache.freq)
print("put d")
cache.put("d", 4)               # c has the lowest count (1): evicted
print("put e")
cache.put("e", 5)               # d has count 1 now: evicted
print("counts:", cache.freq)

Output:

counts: {'a': 4, 'b': 2, 'c': 1}
put d
  evicted c
put e
  evicted d
counts: {'a': 4, 'b': 2, 'e': 1}

Notice the second eviction: the brand-new key d was thrown out immediately, because its count (1) was the lowest. This is LFU's well-known weakness: new items struggle to survive, while items that were popular long ago keep high counts. Real LFU implementations add aging (counts decay over time) to fix this.


Eviction in Real Systems

Approximate LRU and LFU in Redis

Exact LRU needs extra pointers per key, which is costly when a server stores hundreds of millions of keys. Redis therefore uses an approximation: when it needs to evict, it samples a few keys at random (5 by default, set by maxmemory-samples) and evicts the best candidate among them, keeping a small pool of good candidates between evictions. With 10 samples the result is very close to true LRU.

Redis LFU (available since Redis 4.0) uses a tiny probabilistic logarithmic counter per key (a Morris counter fitting in 8 bits) that decays over time, controlled by lfu-log-factor (default 10) and lfu-decay-time (default 1 minute). This gives LFU with aging at a very small memory cost.

The eviction behaviour is chosen with maxmemory-policy once memory use reaches maxmemory:

Policy

Behaviour when memory is full

noeviction (default)

Evict nothing; commands that add data return an error

allkeys-lru

Approximate LRU over all keys (a good general choice for a pure cache)

allkeys-lfu

Approximate LFU over all keys

allkeys-random

Random key

volatile-lru / volatile-lfu / volatile-random

Same, but only among keys that have a TTL set

volatile-ttl

Among keys with a TTL, the one closest to expiring

allkeys-lrm / volatile-lrm

Least recently modified (only writes refresh a key; reads do not). Added in Redis 8.6

If a volatile-* policy is chosen and no keys have a TTL, Redis behaves like noeviction. A common production mistake is using Redis as a cache with the default noeviction policy and then seeing write errors when memory fills up.

Smarter Policies

  • Segmented LRU: new keys enter a "probation" segment and move to a "protected" segment only when accessed again, so one-time scans cannot flush the hot set. Memcached uses a segmented LRU design.

  • ARC (Adaptive Replacement Cache): balances recency and frequency automatically by tracking both, and adapts to the workload. Used, for example, in the ZFS file system.

  • W-TinyLFU: admits a new entry only if its estimated frequency (from a compact frequency sketch) beats the entry it would replace. It is used by the popular Java library Caffeine and gives hit ratios close to optimal on many workloads.


Choosing a Policy

Workload

Good choice

General web cache, popularity changes over time

LRU (or approximate LRU)

Stable set of long-term favourites (popular products, static reference data)

LFU with aging

Occasional large scans mixed with hot keys

Segmented LRU, ARC or W-TinyLFU

All keys accessed about equally, or cyclically

Random (or MRU for strictly cyclic scans)

The app knows which entries matter least

TTL-based (short TTLs on unimportant keys)


Common Mistakes

  • Confusing eviction with expiration. Eviction is about space; expiration is about freshness.

  • Updating the cache on write instead of deleting it in cache-aside, which allows concurrent writers to leave an older value in the cache.

  • Using write-behind for critical data. A cache crash before the flush loses acknowledged writes.

  • Implementing LRU with a singly linked list or an array. Removing from the middle then costs O(n); interviewers expect a hash map plus a doubly linked list.

  • Forgetting the minimum-frequency update in LFU: reset it to 1 on every insertion of a new key.

  • Running Redis as a cache with noeviction, or with a volatile-* policy when keys have no TTL.

  • Assuming one policy is always best. Measure the hit ratio on your real workload.


Interview Questions

1. Explain cache-aside. Why is it the most popular strategy?

The application checks the cache; on a miss it reads the database and populates the cache; on a write it updates the database and deletes the cache entry. It is popular because it is simple, caches only what is actually read, works with any database, and the system still works (more slowly) if the cache fails.

2. Compare write-through and write-behind.

Write-through writes to the cache and the database synchronously, so data is safe and the cache is fresh, but writes are slower. Write-behind writes to the cache and flushes to the database asynchronously, giving very fast, batched writes but risking data loss if the cache fails before flushing, and leaving the database temporarily behind.

3. Describe a race condition in cache-aside that leaves stale data.

A reader misses and reads the old value from the database. Before it writes that value to the cache, a writer updates the database and deletes the cache key. The reader then stores the old value, which stays until the TTL expires. Mitigations: TTLs, delayed double delete, versioned values, or invalidation driven by the database change log.

4. Design an LRU cache with O(1) get and put.

Use a hash map from key to node and a doubly linked list ordered by recency. On get: look up the node, move it to the front. On put: update and move to front if present; otherwise, if full, remove the node at the tail (and its map entry), then insert the new node at the front. Every step is O(1).

5. Capacity 3, requests 1 2 3 4 1 2 5 1 2 3 4 5. How many misses with LRU? With FIFO?

LRU: 10 misses (the only hits are the 8th and 9th requests, 1 and 2, right after 5 is loaded). FIFO: 9 misses (hits on the 8th, 9th and 12th requests: 1, 2 and 5). This is the classic sequence for Belady's anomaly: with capacity 4, FIFO gets 10 misses, more than with capacity 3. LRU never shows this anomaly; with capacity 4 it drops to 8 misses.

6. Why does Redis use approximate LRU instead of exact LRU?

Exact LRU needs a linked list with extra pointers for every key, which costs significant memory when storing hundreds of millions of keys. Redis samples a few keys (5 by default) and evicts the oldest among them, keeping a pool of candidates; this is close to true LRU in practice at much lower cost.

7. What is LFU's main weakness and how is it fixed?

Counts only grow, so items that were popular long ago stay forever, while new items (count 1) are evicted almost immediately. Fixes include aging (decaying counts over time, as in Redis LFU), and admission policies such as W-TinyLFU.


Summary

  • Cache-aside: app loads on miss and deletes on write. The default choice; remember its race condition and use TTLs.

  • Read-through and write-through move the logic into the cache layer; write-through keeps the cache fresh at the cost of slower writes.

  • Write-behind is fastest but can lose data; write-around avoids caching write-only data; refresh-ahead keeps hot keys warm.

  • Eviction (cache full) is not expiration (TTL over).

  • Policies: FIFO, LRU, LFU, MRU, Random, TTL; OPT is the unreachable ideal used as a benchmark.

  • LRU in O(1) = hash map + doubly linked list. LFU in O(1) = count buckets + minimum count.

  • Redis uses approximate LRU/LFU; choose maxmemory-policy deliberately (the default is noeviction).

Strategies decide how data gets into the cache; eviction decides how it leaves. Get both right and the cache stays small, fresh and full of exactly what users ask for.