Distributed Caches Explained: Consistent Hashing, Eviction & the Thundering Herd

Intuition: the question that separates senior from staff

“Design a distributed cache” shows up at exactly the interviews where “I’d add Redis” is not an answer — Meta, Google, Amazon, Apple. The interviewer is not testing whether you know a cache exists. They are testing whether you can reason about placement, failure, full memory, and expiry stampedes, in that order. By the end of this guide you will derive all four, and know how the real systems build them.

Start with the arithmetic that makes the cache inevitable. Your database answers a read in 10 milliseconds. Traffic is 10,000 reads per second. Little’s law says the database must sustain 10,000 × 0.01 = 100 concurrent reads — one hundred open connections doing nothing but reads, before a single write. Now put a cache in front with a 95% hit rate: only 500 reads per second reach the database, and the concurrent load drops to 5. The cache does not just make reads fast; it divides your database load by twenty.

And the workload is on your side. Reads are wildly skewed: roughly 80% of reads ask for the same 1% of data. Cache the hot 1% and you capture most of the win; the other 99% barely matters. This skew is why a small box of RAM can front a huge database — and why every design decision below is about managing the hot keys.

Four questions structure the whole design, and they arrive in interview order. Placement: with many cache boxes, which box owns which key? Failure: a box dies at 2am — what breaks? Full memory: RAM is finite — what gets thrown away? Expiry: a hot key’s TTL fires — what stops a thousand requests from stampeding the database at once? Answer those four and you have designed a distributed cache.

How the four pieces work

Consistent hashing: the ring

One cache box is a bottleneck and a single point of failure, so you run N of them — and now every key needs an owner. The naive rule is hash(key) mod N. It works until the fleet changes: add a ninth box and N changes, so nearly every key remaps to a different box. Your cache effectively empties itself on every scaling event — a full fleet of cold misses slamming the database at once.

The ring fixes it. Hash both the keys and the nodes onto a circle. Each key belongs to the first node clockwise from its position. Add a node and it only steals the keys in its own arc — about 1/N of the keyspace. Remove one and only its arc’s keys move, to the next node clockwise. The rest of the fleet never notices.

This is the design Amazon’s Dynamo paper made canonical: DeCandia et al. partition data with consistent hashing, where each key’s coordinator is the first node clockwise and the next N−1 nodes on the ring form the key’s preference list of replicas. In practice each physical node claims many points on the ring — virtual nodes — so arcs stay even and a beefy box can simply claim more of them.

Replication: plan for failure

At fleet scale, failure is not an emergency — it is the normal case. So every key lives three times: on its home node plus the next two nodes clockwise. One node dies at 2am and the other two copies answer; no data is lost, no pager goes off, and the dead node’s arc is absorbed by its clockwise neighbor until a replacement joins the ring.

Writes go to all three replicas; reads need only one. The cost is straightforward: three times the RAM for the guarantee that a single dead box is a non-event. This is the same preference-list idea as the ring section — placement and replication are one mechanism, not two.

Eviction: when memory fills up

RAM is finite, so the cache needs a rule for what gets thrown away. Three classic policies: LRU tosses the least recently used key, LFU tosses the least frequently used, and TTL stamps an expiry on every key so stale data dies on its own. Most production caches run LRU plus TTL together — recency handles the skew, expiry bounds the staleness.

Redis makes the choice one config line, maxmemory-policy: allkeys-lru, allkeys-lfu, volatile-lru and volatile-ttl (which only evict keys that have a TTL), and noeviction. Worth knowing cold: noeviction is the default — a fresh Redis used as a cache does not evict at all; when memory fills, writes fail with an out-of-memory error. For a cache, set allkeys-lru; Redis’s own docs call it the good default when a small subset of keys gets most of the traffic.

The thundering herd — and request coalescing

Here is the trap the interview is really about. A hot key carries 1,000 reads per second and its TTL expires. In one instant, a thousand requests miss the cache and slam the database with the same query — the spike the cache existed to prevent, arriving all at once. The database that was comfortably serving 500 reads per second is suddenly asked for 1,000 identical ones.

The fix is request coalescing: the first request through does the database fetch while the other 999 wait on its result. One query, not a thousand. The alternative is serve-stale: keep serving the expired value while a background refresh rebuilds it — slightly stale answers, zero spike. Facebook’s Memcached paper describes the same idea as leases: only the client holding the lease performs the database fetch, and everyone else waits rather than stampeding.

Consistency: delete, don’t update

On a write, do you update the cached copy or delete it? Delete it. Write the new value to the database, delete the cache key, and let the next read re-fetch and re-populate. Updating the cached copy in place risks a race where a stale write lands after a fresh one; invalidation has no such race — a deleted key can never serve a lie. This pattern is called cache-aside, and it is the default answer unless the interviewer asks for something stronger.

Cold start: warm it before it takes traffic

A new node joins the ring knowing nothing — every key in its arc misses until it fills. If it takes full traffic immediately, those misses become a mini thundering herd. So warm it first: pre-load the hottest keys (the top 1% you already know about), or let it shadow traffic and fill gradually before it serves real reads. The interviewer asks this right after you say “add a node, only 1/N keys move” — the moved keys still have to be fetched from somewhere.

Two systems that live on this

This is not textbook theory. The largest cache fleets on earth run exactly these four mechanisms — here is how two of them map the ideas onto production reality.

Work the cache by hand

Interviewers trust candidates who do the arithmetic out loud. Here is the full cache design reduced to five lines of math you can reproduce on a whiteboard.

The ring, the eviction, and the singleflight — in Python

Three mechanisms, thirty lines each. The ring decides placement, the OrderedDict decides eviction, and the in-flight map decides that one request rebuilds while the rest wait.

import hashlib
from collections import OrderedDict
from threading import Lock, Event


class ConsistentHashRing:
    """Keys walk the ring to the first node clockwise."""
    def __init__(self, nodes, replicas=100):
        self.ring = {}
        for node in nodes:
            for i in range(replicas):  # virtual nodes
                self.ring[self._hash(f"{node}:{i}")] = node
        self.sorted = sorted(self.ring)

    @staticmethod
    def _hash(key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def node_for(self, key):
        h = self._hash(key)
        for point in self.sorted:
            if point >= h:
                return self.ring[point]
        return self.ring[self.sorted[0]]  # wrap around


class LRUCache:
    """OrderedDict: front is hot, back is evicted."""
    def __init__(self, capacity):
        self.store = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.store:
            return None
        self.store.move_to_end(key, last=False)
        return self.store[key]

    def put(self, key, value):
        self.store[key] = value
        self.store.move_to_end(key, last=False)
        if len(self.store) > self.capacity:
            self.store.popitem(last=True)  # evict coldest


class CoalescingCache:
    """One rebuild per key; everyone else waits on it."""
    def __init__(self, capacity):
        self.cache = LRUCache(capacity)
        self.inflight = {}
        self.lock = Lock()

    def get(self, key, loader):
        hit = self.cache.get(key)
        if hit is not None:
            return hit
        with self.lock:
            if key in self.inflight:
                event = self.inflight[key]
                owner = False
            else:
                event = Event()
                self.inflight[key] = event
                owner = True
        if owner:
            value = loader(key)          # the one DB query
            self.cache.put(key, value)
            with self.lock:
                del self.inflight[key]
                event.set()
            return value
        event.wait()                       # the 999 wait here
        return self.cache.get(key)

The pattern has a name in Go’s standard library — singleflight — and the idea ports anywhere: a per-key in-flight marker turns a thousand duplicate queries into one.

How this gets asked

Six prompts drawn from how Meta, Google, Amazon, and Apple actually probe this topic — each with the answer shape, the follow-up, and the trap.

Takeaways

• Do the read math first. 10,000 reads/sec × 10 ms = 100 concurrent connections — the cache divides database load, not just latency.
• The ring owns placement. First node clockwise; topology changes move only 1/N keys. Virtual nodes keep arcs even.
• Replicate 3x and sleep. Home node plus the next two clockwise — a dead node at 2am is a non-event.
• Set your eviction policy on purpose. LRU + TTL is the default answer; Redis’s default noeviction evicts nothing — change it.
• Coalesce the herd. One request rebuilds the expired hot key; the rest wait. Or serve stale and refresh behind.
• Delete, don’t update. Cache-aside invalidation can never serve a lie; a stale in-place update can.