01. Distributed Cache — High-Level Design¶

~16 min read · Part 2 of 4 (Overview → HLD → LLD → Q&A)

This file turns the solutioning narrative into concrete boxes and the paths between them. Read the architecture top to bottom, follow a write and a read through it, then watch what happens when the node in our scenario dies mid-peak.

Architecture¶

        ┌────────────────────────────────────────────────┐
        │              application fleet                  │
        │   ┌──────────┐   ┌──────────┐   ┌──────────┐    │
        │   │ smart     │  │ smart     │  │ smart     │    │  cache client library
        │   │ client    │  │ client    │  │ client    │    │  holds the ring + a tiny
        │   └────┬──────┘  └────┬──────┘  └────┬──────┘    │  hot-key local cache
        └────────┼──────────────┼──────────────┼──────────┘
                 │  hash(key) → node (consistent hashing on the ring)
     ┌───────────┼──────────────┼──────────────┼───────────┐
     ▼           ▼              ▼              ▼            ▼
 ┌────────┐  ┌────────┐   ┌────────┐   ┌────────┐     ┌────────┐
 │ node 1 │  │ node 2 │   │ node 3 │   │  ...   │     │node 100│    cache tier
 │ primary│  │ primary│   │ primary│   │        │     │ primary│    (in-memory shards)
 │  +repl │  │  +repl │   │  +repl │   │        │     │  +repl │
 └────────┘  └────────┘   └────────┘   └────────┘     └────────┘
     │  async replication (primary → replica on another node/AZ)
     │
     │            ┌──────────────────────────┐
     └───────────▶│  cluster coordinator      │  membership, health, slot map,
                  │  (gossip or Raft-based)   │  failover election
                  └──────────────────────────┘
                                │  on miss / writes
                                ▼
                        ┌────────────────┐
                        │  origin store   │  system of record
                        │  (SQL / NoSQL)  │  provisioned ~150k QPS
                        └────────────────┘

Reading it top to bottom: the application fleet does not talk to a proxy that "knows where keys live" — instead each app process embeds a smart client that holds a copy of the ring and computes the owning node itself, so a GET is one network hop straight to the right node with no lookup tax. The cache tier is 100 nodes, each a primary for its slice of the keyspace and a replica for some other node's slice. A cluster coordinator tracks membership and health and runs failover elections, but it sits off the data path — clients route without consulting it on every request. The origin store is the slow source of truth the whole tier exists to shield; the only traffic that reaches it is cache misses and the writes the application sends directly.

Components¶

Smart client (routing library). Embedded in every app process. It holds the ring (node list plus their virtual-node positions), hashes each key to find the owning node, and sends the request there directly. It also keeps a small local (L1) cache of the very hottest keys to absorb hot-key traffic before it leaves the box. When the coordinator reports a topology change, the client refreshes its ring. Putting routing in the client, not a middle proxy, removes a network hop and a scaling bottleneck from the hot path — the trade is that clients must be kept in sync on topology, which the coordinator handles.

Cache node. A single-threaded (per core) in-memory store — the Redis/Memcached process. It owns a set of key slots as primary, serves reads and writes for them, and asynchronously ships changes to its replica on another node. It also holds slots as a replica for some other primary. Each node independently enforces the eviction policy and per-key TTLs against its memory budget. Single-threaded execution per shard is deliberate: it makes every operation atomic without locks, which is what lets CAS and INCR be correct and cheap.

Cluster coordinator. The control plane. It maintains authoritative cluster membership, health-checks nodes, decides when a node is dead, and promotes that node's replica to primary. It publishes the slot map (which node owns which slots, and where replicas live) that clients cache. Redis Cluster does this with gossip plus a majority vote among primaries; other systems use a Raft/ZooKeeper-backed controller. The key property is that it is consulted on change, not on every request, so it never becomes a throughput ceiling.

Replication link. The asynchronous stream from each primary to its replica(s). It carries the write stream so a replica can be promoted warm. Because it is async, a replica lags the primary by a bounded amount (typically well under a second), and a failover can lose exactly that lag's worth of writes — accepted, per the durability non-goal.

Origin store. The database of record behind the cache. It is not part of the cache tier, but every design decision here is ultimately about keeping its load flat: at steady state it sees the ~100k QPS of misses, and the failure modes below are mostly about making sure it never sees much more.

Primary write path (SET)¶

The application calls SET user:8842 <value> EX 3600. The smart client hashes user:8842, finds the owning primary on the ring, and sends the write there.
The primary applies the write to its in-memory map with the TTL, atomically (single-threaded per shard), and immediately returns OK to the client.
Asynchronously, the primary appends the write to its replication stream; the replica applies it a moment later. The client does not wait for this.
In a look-aside deployment (the common one), the application separately writes the authoritative value to the origin store and then either updates or deletes the cache key. Delete-on-write is usually safer than update-on-write because it avoids caching a value that a concurrent writer is about to change; the next read repopulates from origin.
If memory is over budget on the primary, the write triggers eviction of one or more low-value keys under the node's policy before or after insertion, so the node stays inside its 20 GB envelope.

Primary read path (GET)¶

The application calls GET user:8842. The smart client first checks its tiny L1 local cache; a hit there returns with zero network cost and is how the hottest keys are absorbed.
On L1 miss, the client hashes the key and sends GET to the owning primary.
Cache hit on the primary: the value returns in sub-millisecond time. This is ~99% of reads and the entire reason the tier exists.
Cache miss: the primary returns MISS. The application reads the value from the origin store, then issues a SET to populate the cache for next time (read-through behavior, implemented client-side in look-aside). To stop many concurrent misses on the same key from each hitting origin, the client wraps the miss in single-flight coalescing — one request fetches from origin while the rest wait for its result.
Reads may optionally be served from a replica to spread load, accepting that a replica can be a few milliseconds stale — fine for a cache, and often not worth the added staleness for point reads, so many deployments read only from the primary and use replicas purely for failover.

Storage choices¶

Cache node data: pure in-memory hash table. Chosen for the sub-millisecond point read that is the whole product. No disk on the hot path. Optional background snapshotting or an append-only log exists only to warm a node faster after a restart, never as a durability contract.
Slot map / membership: the coordinator's small strongly-consistent store. This metadata must not disagree across the cluster — two nodes both believing they are primary for a slot is a split-brain — so it lives in a Raft/gossip-with-quorum layer, not in the cache itself. It is tiny (a few KB) and rarely written.
Origin store: whatever the service already uses (SQL or NoSQL). The cache is agnostic to it. The only requirement the cache imposes is that origin reads are idempotent and that the origin can absorb the steady-state miss load (~100k QPS here) plus a safety margin.

Scaling¶

Read path. Reads scale two ways. Horizontally, adding nodes shrinks each node's share of the keyspace and its share of the 10M ops/second; consistent hashing means adding the 101st node pulls only ~1/101 of keys off their current owners rather than reshuffling everything. Vertically for skew, the smart client's L1 cache and hot-key replication (below) absorb concentrated traffic that horizontal scaling cannot touch. The partition key is the cache key's hash, spread over virtual nodes so distinct keys distribute uniformly — traffic skew on a single key is handled by fan-out, not by the partition scheme.

Write path. Writes are cheap and local — one in-memory update plus an async replication append — so per-node write throughput is bounded by the single-threaded shard's op rate (hundreds of thousands/second), not by coordination. There is no global write lock and no cross-node consensus on the data path, so write throughput scales linearly with node count.

Hot keys. One key drawing, say, 1M requests/second lands entirely on its owning node and saturates that node's CPU and NIC while the other 99 sit idle — the classic single-hot-key failure. Defenses stack: the client L1 cache serves the hottest keys locally with a short TTL, cutting most of that 1M before it leaves the app boxes; for what remains, key replication (write the value under flag:x#1 … flag:x#8 and read a random one) fans the reads across 8 nodes, turning 1M/second on one node into ~125k/second on each of eight. Consistent hashing is explicitly not a hot-key defense — it spreads distinct keys, and a hot key is one key.

Rebalancing on scale-out. Adding capacity moves keys, and moving them naively causes misses. The move is done by having the new node's slots served from origin (or backfilled from the old owner's replica) during the handoff so clients see misses that repopulate, rather than errors — a gradual warm-up, not a cliff.

Operational signals¶

The healthy signal is hit ratio, which should sit near 99% and stay flat; a launch that concentrates traffic on a few keys should if anything raise it. The first metric to degrade under trouble is origin QPS — when it climbs off its ~100k baseline while the app's request rate is steady, the cache is failing to absorb something (a node lost its warm data, a hot key expired, an eviction storm cleared the working set), and it is the leading indicator of a stampede forming. The misleading metric is average cache latency: it stays flat because 99% of ops are fast hits, hiding a miss path that has quietly gone from a 1 ms cache read to a 50 ms origin read — watch p99 and the miss-latency distribution, not the mean. The graph an experienced operator opens first during an incident is origin QPS overlaid with per-node hit ratio: a single node's hit ratio cratering while origin QPS spikes points straight at that node's data going cold (a failover, an eviction, a restart), which is exactly the scenario below.

Failure modes and resilience¶

Node death at peak (the threaded scenario). Node 42 dies while the cluster is doing 10M ops/second. Consistent hashing means only its ~1% of keys need a new owner, and virtual nodes spread that 1% across the 99 survivors (~1,010 extra ops/second each — invisible). The danger is the origin: if those keys land cold, 100k ops/second of misses hit a database already at 100k, pushing it to 200k past its 150k ceiling. The resolution is warm replica promotion — the coordinator promotes node 42's replica, which already holds those keys, so they are hits from the first request and the origin never moves. Any residual cold reads (keys written to the primary but not yet replicated when it died) are caught by single-flight coalescing, so at most one origin read happens per distinct key, not one per request. The two together are why "no stampede reaches origin" holds.
Coordinator failure. If the control plane is down, the data path keeps serving from clients' cached ring — reads and writes continue — but automatic failover and topology changes pause until it recovers. Run the coordinator as a replicated quorum (odd number, majority to act) so a single coordinator node loss changes nothing.
Split-brain / network partition. A partition can leave two sides each thinking they own a slot. Resolve with a quorum rule: only the majority side may promote a replica or accept writes for contested slots; the minority side stops serving those slots rather than diverge. This trades availability on the minority side for consistency of ownership — the correct trade for a cache, where a stalled slot self-heals but a split-brain corrupts.
Eviction storm. A sudden influx of new keys (a cache flush, a bad deploy that changes key names) forces mass eviction and drops the hit ratio, spiking origin load. Mitigations: alarm on hit-ratio drop, cap the rate of new-key admission, and use LFU so a burst of one-hit keys cannot evict the durable hot set.
Thundering herd on a hot-key expiry. A hot key's TTL fires and thousands of concurrent reads miss at once. Mitigations: single-flight coalescing, probabilistic early expiration (refresh a hot key slightly before its TTL so it never actually expires under load), and serving the stale value while one request refreshes.
Replica lag on failover. Because replication is async, promoting a replica can lose the last sub-second of writes. Accepted per the durability non-goal — the origin is authoritative and the lost writes reappear on the next read-through.

Where this shows up in production¶

Redis Cluster — partitions the keyspace into 16,384 hash slots mapped onto nodes, exactly the consistent-hashing-with-fixed-buckets idea, and uses gossip plus a primary majority vote to promote a replica on node death.
Memcached (client-side consistent hashing) — the server nodes are dumb; the client (ketama hashing) owns the ring and routing, the pattern behind the smart-client box here, which is why adding a Memcached node moves only that node's share of keys.
Amazon ElastiCache / DynamoDB Accelerator (DAX) — managed Redis/Memcached and a write-through cache in front of DynamoDB, showing the look-aside-versus-write-through choice as a product knob.
Facebook's memcache tier (the "leases" paper) — the canonical hot-key and thundering-herd defense: a lease token lets exactly one client refill a hot key on miss while others wait, which is single-flight coalescing at fleet scale.
Twitter / Nighthawk — a Redis-based cache with client-side hot-key detection and local caching, the L1-in-the-client pattern for absorbing a viral tweet's key.
Netflix EVCache — Memcached replicated across AZs so a whole zone can fail with the cache staying warm, the availability-not-durability use of replication taken to the AZ level.
DynamoDB's internal partitioning — virtual-node-style key distribution so that adding capacity or losing a storage node reshuffles a bounded fraction of the keyspace, not all of it.
Consistent hashing itself (Amazon Dynamo paper) — the origin of the ring-with-virtual-nodes design that made "lose a node, move 1/N of keys" the default expectation for every cache and datastore since.