Primary concepts and the hard part
hash % N invalidates ~80% of the cache and stampedes the origin database. This is the canonical consistent-hashing question, and the second probe is hot keys, which consistent hashing does not solve.Requirements
get(key), set(key, value, ttl), delete(key)Ops: 10M/sec Dataset: 1 TB hot working set Nodes: ~100 × 16 GB RAM Avg value: ~1 KB → ~1B keys Key metric: HIT RATE. A drop from 95% → 80% triples origin load.
API / Model
High-level architecture
There is no proxy tier: a smart client library inside each application server routes every request straight to a cache node. The origin database sits behind the nodes and is only read on a miss.
- The application calls the smart client, which hashes the key, such as
user:1234, against its own copy of the ring. Before that, it can answer the hottest keys from its optional tiny L1 cache. - On the consistent hashing ring, the key belongs to the first node clockwise from its hash. Every physical node sits at about 150 virtual node positions, so keys spread evenly and a resize remaps only about 1/N of them.
- The client connects directly to that node, with no proxy hop in between.
- The node finds the key in its hash map and moves the entry to the front of its LRU list, both in O(1). It runs commands on a single thread and evicts from the tail of the list when memory is full.
- On a hit, the value goes straight back to the client.
- On a MISS, the value is read from the origin database and SET back into the same node, so the next read for that key hits.
Two flows run beside the request path. Each node streams writes asynchronously to its own replica, and membership uses gossip in the SWIM style, moving a node through suspicion and confirmation before declaring it dead and changing the ring the clients use. The stampede, penetration and avalanche failure modes all surface at the miss path, as extra load on the origin database.
Same cache at 100x. A billion operations a second is the order of magnitude the largest social networks push through their cache tier. Dashed outlines mark what's new or reshaped compared with today's design.
| Today | At 100x | |
|---|---|---|
| Operations | 10M/sec | 1B/sec |
| Hot data set | 1 TB | 100 TB |
| Keys | ~1B | ~100B |
| Cache nodes | ~100 × 16 GB | ~800 primaries × 128 GB, plus replicas |
| Connections if every host dials every node | ~100k | ~80M |
What changes, and the number that forces it
- Smart clients give way to a local sidecar. The smart client's advantage was one hop. At ~100k application hosts and ~800 nodes, every process dialing every node means ~80M connections, and every ring change has to reach client libraries in every language. A routing proxy on each host keeps the latency argument (one localhost hop, pooled connections to the nodes) while keeping ring logic in one place. This is the shape Meta's mcrouter took: the client-versus-proxy trade-off flips at this size.
- One cluster splits into pools by workload. Tiny hot keys, large values and everything else behave very differently under eviction, and at 100 TB one team's churn evicts another team's data. The sidecar picks a pool by key prefix, and each pool is sized and tuned for its workload.
- A gutter pool catches failed nodes. With ~1,600 nodes, something is always failing. Rehashing a dead node's keys onto its neighbours dumps its load on nodes that may then fail too. Instead, requests whose node is down go to a small gutter pool with short TTLs, and the ring doesn't change until the node is confirmed gone. Values served from the gutter can be a few seconds stale.
- The ring gets an authority. Gossip across ~1,600 nodes converges slowly, and a flapping node triggers remaps back and forth. A config service owns ring membership and rate-limits changes, while gossip only feeds it liveness hints. This is the false-positive cascade follow-up, answered structurally.
- Hot keys are found automatically. At 1B operations/sec some key is always hot, and nobody knows which one in advance. The sidecar samples traffic, flags keys over a threshold and spreads them across several nodes as suffixed copies; the hottest also land in each host's in-process L1.
- Invalidation comes from the database, per region. With hundreds of services writing, the application can't be trusted to delete every affected key. A daemon in each region tails the database's replication stream and deletes keys from it: the change-data-capture answer from the invalidation trade-off, applied everywhere.
- New clusters warm from warm ones. A cold cluster at this size would stampede its database. While cold, it reads misses from a warm cluster first and only then from the origin, until its hit rate catches up.
What stays the same
Consistent hashing with virtual nodes (now inside the sidecar), a cache that's never the source of truth, LRU plus TTL, the stampede, penetration and avalanche fixes, deleting keys rather than setting them on invalidation, and independent clusters per region. Hit rate is still the number everything else serves.
Trade-offs and deep dives
With hash(key) % 4 and a fifth node added, every key's destination changes from % 4 to % 5 — roughly 80% of the cache is suddenly on the wrong node, so 80% of requests miss and hit the database simultaneously. That's not a cache inefficiency, it's a database outage. Consistent hashing bounds the disruption to ~1/N of keys, moving only from the single adjacent node clockwise. Removing a node is equally surgical.
With, say, eight physical nodes placed randomly on the ring, the arcs between them vary enormously, so one node might own 3x its fair share. Placing each physical node at ~150 positions averages out the randomness and produces near-uniform distribution. They also enable weighting — a machine with twice the RAM gets twice the vnodes — and make removal smoother, since the departing node's load spreads across many neighbours instead of dumping entirely on one.
| Smart client | Proxy tier (twemproxy, Envoy) | |
|---|---|---|
| Latency | 1 hop | 2 hops |
| Client complexity | high (ring logic in every language) | thin clients |
| Config rollout | must update every client | update proxies only |
| Failure isolation | client bugs are everywhere | proxy is a contained tier |
Smart clients win on latency, which is the entire point of a cache. Proxies win on operability, especially in polyglot environments where reimplementing ring logic in five languages is a liability. Say which you'd choose and why — for a single-language shop, smart client; for a large polyglot org, proxy.
Hash map plus doubly-linked list gives O(1) for both lookup and reordering: on access, unlink the node and move it to the head; on eviction, drop the tail. Worth being able to sketch, since it's a common coding question in its own right.
Real systems approximate. Redis samples a handful of random keys and evicts the least recently used among them, because maintaining exact LRU ordering costs memory per entry and adds contention. Approximate LRU is nearly as good and much cheaper — a nice example of accepting an approximation where the cost of exactness isn't justified.
LRU is the sensible default (matches temporal locality). LFU handles stable popularity better but suffers cache pollution — something hugely popular last month keeps a high count forever — so it needs aging. TTL-only is right when staleness, not memory, is the binding constraint. Mention that most systems combine: LRU for eviction, TTL for correctness.
This is the follow-up that catches people. The ring distributes keys evenly; it cannot help when one single key receives a million requests per second. All that traffic maps to one node by definition. Mitigations:
- Client-side L1 cache for the hottest keys — a tiny in-process cache absorbs repeat reads before they leave the app server. Cost: per-server copies can briefly diverge.
- Key replication with a suffix — store the value under
key#0..#9and have clients read a random one. Spreads read load across ten nodes; writes must update all ten. - Dedicated nodes for known-hot keys.
Naming the L1 cache as the first-line answer is the practical one, since it requires no cluster changes.
- Stampede/thundering herd: a hot key expires and a thousand concurrent misses hit the database at once. Fix with request coalescing (first miss takes a lock, others wait for its result), probabilistic early expiry, or stale-while-revalidate.
- Penetration: repeated requests for keys that exist nowhere, so the cache never helps. Fix by caching the negative result with a short TTL, and/or a Bloom filter in front to reject definitely-absent keys.
- Avalanche: many keys expire simultaneously (or the cluster restarts cold), dumping full load on the origin. Fix with TTL jitter, cache warming before serving traffic, and a circuit breaker in front of the database so it degrades instead of collapsing.
Being able to name all three and give a fix each is a fast, high-value signal.
A pure cache needs no replication — a lost node means a miss, and the origin repopulates. Add async replicas when you want read scaling or to avoid a cold-start stampede after a node dies. Async replication means replicas can serve stale values; since this is a cache, that's usually fine, but say it rather than glossing over it.
Prefer deleting a key over writing a new value into it. Two concurrent updates writing to the cache can land out of order and leave the older value cached indefinitely; deleting is idempotent and forces a fresh read. For correctness-critical invalidation, drive it from change-data-capture on the database so every write invalidates, including ones made by other services or by hand.
Redis executes commands on one thread, which is why INCR is atomic with no locking and why it's a safe distributed counter. The consequence: one expensive command (KEYS * on a large keyspace) blocks every other client. Never run unbounded commands in production — use SCAN with a cursor instead.
Fragmentation is real: a 16 GB node does not hold 16 GB of values. Use a slab allocator (Memcached's approach) or jemalloc with monitoring. Set maxmemory explicitly with an eviction policy, because the failure mode of not doing so is the OS OOM-killer terminating the node, which is far worse than evicting a few keys.
Possible follow-up questions
MOVED) rather than failing.