Design a Distributed Cache

1Clarifying the requirements#

Agree on what you are building before drawing a single box. A good two minutes here saves you from designing the wrong system for fifteen. Here is roughly how that opening goes.

Candidate: Are we building the cache itself, like Memcached, or a caching layer on top of an existing store?

Interviewer: The cache itself. Treat it like a product other teams will call over the network. They put bytes in, they get bytes out.

Candidate: Is it a simple key value store, or do I need lists, counters, sets, that kind of thing?

Interviewer: Start with key value. Opaque byte values up to maybe 1 MB. If you finish early we can talk about richer types.

Candidate: What is the consistency bar? If a client writes a key and immediately reads it, must it see the new value?

Interviewer: Good question. We want read your writes for a single client against a single key. Across replicas we can tolerate a short window of staleness. Losing cached data on a crash is acceptable, it is a cache, not the source of truth.

Candidate: Scale? And is this one region or global?

Interviewer: Assume one large region for the core design. Call it a few hundred thousand clients and millions of requests per second at peak. Mention multi region at the end.

What those answers just told me:

• The interview is about partitioning and hot keys, not CRUD. Key value only, 1 MB values, millions of ops/sec in one region.
• "Read your writes per key" plus "tolerate replica staleness" is the interviewer handing me the exact consistency seam to defend.
• "Lossy on crash" is permission to skip durability entirely, which unlocks async replication and fast writes.

Functional requirements

• GET(key) returns the value or a miss.
• SET(key, value, ttl) stores a value with an optional expiry.
• DELETE(key) removes a key.
• Values are opaque blobs up to 1 MB, keys up to 250 bytes.
• Per key TTL and automatic expiry.
• Eviction when memory fills (we will use LRU style).

Non functional requirements

• Read latency p99 under 1 ms inside the datacenter, p50 under 300 microseconds.
• Throughput: millions of ops per second across the cluster, horizontally scalable.
• Availability target 99.99 percent. A node dying must not take down the cluster.
• Read your writes for a single client on a single key.
• Durability explicitly not required. Data can be lost on crash.
• Adding or removing nodes should move a small fraction of keys, not reshuffle everything.

2Back-of-the-envelope estimation#

Size this so the component choices are grounded in arithmetic, not vibes. Narrate the numbers, because the interviewer is scoring how you get there, not just the answer.

Traffic.

• Say 300,000 active clients, and at peak the fleet drives 3 million cache operations per second.
• Caches are read heavy, so assume a 9 to 1 read to write split.
• Reads: 2.7M ops/sec.
• Writes: 0.3M ops/sec.

Working set and storage.

• Suppose we cache 2 billion distinct objects, average value 4 KB, average key 40 bytes.
• Per entry metadata (TTL, LRU pointers, hashtable slot) is maybe 60 bytes.

per entry  = 4096 + 40 + 60  ~ 4.2 KB
total data = 2e9 * 4.2 KB    ~ 8.4 TB

• 8.4 TB of hot data. No single box holds that, so we shard regardless of anything else.
• If each node carries 128 GB usable RAM for data:

nodes for data = 8.4 TB / 128 GB ~ 66 nodes

• Round up and add headroom: call it ~90 primary nodes.
• Add one replica each and we are near 180 machines. That is the cluster.

Per node load.

• 3M ops / 90 primaries ~ 33K ops/sec per primary on average.
• Modern in memory stores do hundreds of thousands of ops/sec per core, so CPU is not the wall.
• The wall is network and tail latency under hot keys. Hold that thought.

Bandwidth.

• Reads dominate: 2.7M reads/sec * 4 KB ~ 10.8 GB/sec of value payload leaving the tier.
• Spread over 90 nodes that is ~120 MB/sec per node, comfortable on a 10 Gbps NIC (1.25 GB/sec).
• But a single hot node serving a viral key could saturate that NIC on its own. Another flag for later.

3Core APIs#

Clients talk to the cache over a thin binary protocol in practice, shown here as HTTP-ish for clarity.

• In a real interview I say out loud that the wire format is a custom TCP protocol with pipelining.
• HTTP header overhead would murder the 1 ms latency budget.
• Showing the HTTP shape is a readability choice, not a design one.

GET /v1/cache/{key}
-> 200 {"value": "<base64 blob>", "ttl_remaining_ms": 48213}
-> 404 (cache miss)

PUT /v1/cache/{key}
Body: {"value": "<base64 blob>", "ttl_ms": 300000}
-> 204 No Content

DELETE /v1/cache/{key}
-> 204 No Content

Batching matters a lot at this QPS:

{
  "op": "MGET",
  "keys": ["user:91:profile", "user:91:prefs", "product:552:price"]
}

Why batching is not optional:

• A single MGET fans out to several shards and comes back in one round trip. That is how you keep p99 sane.
• Chatty clients that do one GET per key, each paying a full round trip, are the number one cause of latency complaints I see in review.
• A candidate who designs the perfect server and never mentions batching has not run one of these in production.

4High-level design#

The core idea, stated plainly:

• Clients do not guess which node holds a key.
• A smart client library hashes the key onto a ring and talks to the owning shard directly.
• No central coordinator sits in the read path.

Here is the whole system.

The pieces.

• Smart client library. Lives inside the app server. Holds the hash ring and node list, picks the owning shard, sends the request straight there. One network hop. If a node is down it fails over to the replica.
• Consistent hash ring. Maps keys to shards so adding or removing a node moves only 1/N of keys, not all of them. This is the mechanism that satisfies the "small fraction of keys move" requirement.
• Shard (primary plus replica). Each shard is an in memory store. Primary serves reads and writes. Replica gets async updates and takes over on failure.
• Membership and config service. The one place that knows which nodes exist and owns the ring version. Built on a small Raft group or ZooKeeper. It is NOT in the request path. Clients cache the ring and refresh only on change, so a brief config outage does not stop reads or writes.

The deliberate choice: client side routing over a proxy tier.

• The alternative (an mcrouter or Twemproxy style box) is operationally simpler and lets you run dumb clients.
• The cost is one extra hop and a whole tier you have to scale and keep alive.
• At millions of ops/sec I lean smart client to save the hop, and keep the proxy option in my back pocket for polyglot services that cannot embed our library.

5Data model#

The cache has no SQL tables, but each node keeps internal structures, and the metadata is where the clever bits live. An interviewer who sees last_access and version knows you thought about eviction and replica ordering before they even asked.

Per node in memory entry.

Cluster membership record (held by the config service, cached by clients).

Why ring_version is load bearing.

• Every request carries the client's known version.
• A shard can reject or redirect if the client is working off a stale ring after a topology change.
• That stops a client from happily writing to a node that no longer owns the key, which is the kind of silent correctness bug that is miserable to debug in production.

6Deep dives#

6.1 Partitioning: consistent hashing with virtual nodes#

Start with why the obvious thing fails.

• Naive hashing is shard = hash(key) % N.
• Change N and almost every key remaps. Add one node to a 90 node cluster and you churn ~99 percent of the cache.
• That is a thundering herd of misses hammering the backing store the instant you scale out, which is exactly when you are already under load. Unacceptable.

Consistent hashing fixes this.

• Hash both keys and nodes onto the same 2^32 ring.
• A key belongs to the first node clockwise from it.
• Add a node and only the keys between it and its predecessor move. Remove a node and its keys fall to the next one.
• Either way you touch ~1/N of keys, roughly 1 percent in our 90 node cluster instead of 99.

Raw consistent hashing still has a flaw, so add vnodes.

• With only 90 points on the ring, the arcs are uneven and some nodes own far more than their share.
• Each physical node registers ~200 virtual nodes, spreading its ownership into 200 small arcs.
• Load evens out, and when a node dies its load scatters across many neighbors instead of dumping entirely on one unlucky successor.

Rebalance gradually, never big bang.

• When I move vnodes, I warm the new owner before cutting traffic to it, so we do not flash a cold shard into a miss storm.
• A big-bang reassignment is how you turn a routine scale-out into a 2am page.

6.2 The hot key problem#

This is the part that separates a good answer from a great one, and it is the signature hard part of this question.

• Consistent hashing balances keys, not traffic.
• One key goes viral (say a product price on a flash sale) and every request for it lands on one shard.
• That shard's CPU and NIC saturate while 89 others sit idle.
• Our 120 MB/sec per node budget evaporates when one key does 500K reads/sec, which is 2 GB/sec against a 1.25 GB/sec NIC.
• The node is underwater and consistent hashing cannot help, because the heat is on a single point on the ring.

How I defend against it, in layers:

1. Client side micro cache. The smart client keeps a tiny in process LRU, a few thousand entries, with a sub second TTL. A truly hot key gets answered inside the app process with zero network hops. This alone absorbs most of the storm, because the hottest keys are hot everywhere at once.
2. Hot key detection and replication. The owning shard samples access frequency with a count min sketch, which is cheap and bounded in memory. When a key crosses a threshold, the config service promotes it to a "replicated hot key": copies land on several nodes and the client is told it may read any of them. Reads for that key spread across, say, 10 nodes, cutting per node load by 10x.
3. Request coalescing on miss. When a hot key expires and 50K requests miss at once, you do not want 50K calls stampeding the database. The shard collapses concurrent misses for the same key into one backend fetch and fans the single result back out to all 50K waiters. This is the single most important anti stampede trick, and the one candidates forget most often.

Here is the hot key read path end to end.

6.3 Replication and consistency#

Each shard has one primary and one or more replicas in another rack or availability zone.

• Writes go to the primary, which applies locally and streams the change to replicas asynchronously.
• I pick async because synchronous replication would add a round trip to every write and blow the latency budget.
• We agreed losing data on crash is fine, so paying for durability we were told we do not need would be a self-inflicted wound.

That choice has a consequence, and I name it honestly.

• A read from a replica can briefly return a stale value.
• We promised read your writes for a single client on a single key.
• I satisfy that by routing a client's reads and writes for a given key to the same primary by default.
• The client only falls to a replica when the primary is unreachable, and at that point we have already accepted that failover may lose the last few unreplicated writes.
• That is the honest trade, and I would say it to the interviewer in exactly those words rather than pretend the system is stronger than it is.

Ordering with version numbers.

• Every write to a key carries a monotonically increasing version from the primary.
• Replicas apply writes in version order and drop anything older than what they already hold.
• Out of order async delivery cannot resurrect stale data. Without this, a delayed packet could overwrite a newer value with an older one, which is the subtle bug version numbers exist to kill.

On primary failure.

• The config service detects the missed heartbeats, promotes a replica, bumps ring_version, and pushes the new topology to clients.
• The window where writes might be lost is the replication lag, typically single digit milliseconds. For a cache, that is acceptable.

7Bottlenecks and trade-offs#

Walk through what actually breaks and how I answer for it, because an interviewer will push on exactly these.

Hot keys, again.

• Even with micro caching and replication, a single super hot key under a flash sale is the most likely thing to page you.
• The defense is layered and probabilistic, not absolute. There is no magic: you spread the heat, you coalesce the misses, and you accept the micro cache may serve data up to its TTL stale.
• For a price shown to a buyer, 200 ms of staleness is usually fine. For an inventory count that gates a purchase, you bypass the cache on the final check and read the source of truth.
• Knowing which is which is the judgment call.

Topology change during a partition.

• A client with a stale ring may route to the wrong node after a rebalance.
• The ring_version check catches this: the target node sees a mismatched version and returns a redirect.
• Worst case, a few requests get an extra hop while the client refreshes its ring. No data corruption, because the cache is not authoritative and the backing store is still the truth.

The config service as a soft dependency.

• It is tempting to call it a single point of failure. It is not in the read path, so a brief outage means we cannot add or remove nodes, not that reads stop.
• I run it as a 3 or 5 node Raft group across AZs, and clients hold the last known good ring.
• That is the right place to spend consistency budget: topology must be agreed on by everyone, while data need not be.

Memory pressure and eviction.

• When a node fills, LRU evicts the coldest entries.
• But strict global LRU across a shard means updating a linked list on every read, which turns every read into a write and contends hard under concurrency.
• So in practice I use approximate LRU: sample a handful of keys and evict the oldest of the sample, the way Redis does.
• Cheaper, lock friendlier, and the hit rate difference versus exact LRU is tiny. I trade exactness for throughput on purpose, and I say so.

Multi region.

• For a global footprint I run an independent cache cluster per region, each fronting its regional backing store, rather than one stretched cluster.
• Cross region replication for a cache rarely pays: the latency and staleness make it worse than just doing a local miss and fetching from a regional replica of the source of truth.
• I would only replicate cache writes across regions for a small set of hot, read mostly, globally shared keys, and even then async and best effort.

Cold start and warming.

• A freshly added or restarted node is empty, so every request to it misses and hammers the backing store.
• I warm new nodes by shadowing a fraction of live traffic to them before they take real load, or by streaming keys from the node they are taking vnodes from.
• Never flip a cold node to 100 percent traffic, because a cluster of cold misses looks exactly like an outage to your database.

Cost.

• 180 machines with 128 GB RAM each is not cheap. The lever is hit rate.
• A 1 percent drop in hit rate at 2.7M reads/sec is 27K extra reads/sec hitting the database.
• Right sizing TTLs, eviction, and the working set is a cost decision as much as a latency one.
• I put a dashboard on hit rate per key prefix and treat a regression there as an incident, not a nice-to-have.

A cache is allowed to be lossy and briefly stale, so spend the consistency budget on topology agreement and everything else on latency.

8Summary#

The decisions that matter:

• Consistent hashing with ~200 vnodes per node. Scaling moves 1/N of keys and load stays even. This directly answers the hardest requirement, the one I flagged at the start.
• Smart client routing, no coordinator in the hot path. One hop per request, no central bottleneck. A small Raft config service owns topology and stays off the data path.
• Primary plus async replica per shard. Fast writes, failover that may lose a few milliseconds of writes, which is fine for a cache. Read your writes held by pinning a key's reads and writes to its primary.
• Hot keys handled in layers. In process micro cache, frequency triggered key replication, and miss coalescing to stop stampedes. This is where the design earns its keep.
• Approximate LRU and per key TTL for eviction, trading exactness for throughput deliberately.
• Per region clusters for a global story, not one stretched ring.
• The theme across all of it: a cache is lossy and briefly stale by design, so consistency budget goes to topology agreement and everything else goes to latency and throughput.

For how specific companies push on this, see our related guides on Design Memcached, Design a Rate Limiter, and the caching rounds in our company specific interview playbooks.