Design a Distributed Cache

Several teams at a company each run their own Redis instance, sized by guesswork. One team's cache fills up and starts evicting hot data; another team's is 90% empty. When a cache machine dies, its team's service floods the database. The platform team is asked to build a shared, distributed cache service: one system, many tenants, capacity that grows by adding machines, and no single machine whose loss takes out a big slice of the cache.

This case study designs that service. It is also how you would answer "design a key-value store" or "design Memcached" in an interview, with the important difference that a cache may lose data, which shapes almost every decision.

• How to scope a cache service and estimate its memory, throughput and node count.
• The design of a single cache node: hash table, TTL expiry and LRU eviction.
• Partitioning with consistent hashing or hash slots, and routing requests.
• Replication, failure detection and failover for a cache.
• Rebalancing when nodes are added or removed.
• Hot keys, stampedes and cold caches.
• What consistency a cache can promise.

Build an in-memory cache service that many internal services use to store and retrieve values by key with low latency. It should scale horizontally, survive node failures without losing large parts of the cache, isolate tenants from each other, and be simple for application teams to use.

Functional requirements

1. get(key), set(key, value, ttl), delete(key), multi_get(keys).
2. incr(key, delta) and compare_and_set(key, expected_version, value) for safe concurrent updates.
3. Per-tenant namespaces and memory quotas.
4. Automatic eviction when memory is full.

Out of scope: cross-region replication, durable storage guarantees, complex data structures beyond counters (a real product such as Redis offers many more).

Non-functional requirements

Data: 1.5 TB of hot data (values plus keys plus metadata overhead)Usable memory per node (assumed instance size, after leaving room for the OS,  fragmentation and replication buffers): 64 GBPrimary nodes for data: 1.5 TB / 64 GB = about 24 nodesWith one replica each: 48 nodesThroughput: 1,000,000 ops/s / 24 primaries = about 42,000 ops/s per primary  (if replicas also serve reads, lower per node)Network: 1,000,000 ops/s x 1 KB average = about 1 GB/s = 8 Gbps aggregate  -> about 0.33 Gbps per primary, well within typical NICs

Conclusions: memory, not throughput, decides the node count (each node is lightly loaded at about 42,000 operations per second, an assumption to confirm with load tests). We need partitioning (no machine holds 1.5 TB in memory) and replication (so a node loss does not drop a 1/24 slice of the cache).

Clients use a library that speaks a compact protocol over persistent TCP connections (an HTTP API would add too much overhead per operation at this latency target):

get(namespace, key)                         -> value, version | MISSmulti_get(namespace, [keys])                -> {key: value | MISS}set(namespace, key, value, ttl_seconds)     -> OK | ERR_TOO_LARGE | ERR_QUOTAdelete(namespace, key)                      -> OKincr(namespace, key, delta, ttl_seconds)    -> new_valuecompare_and_set(namespace, key, expected_version, value, ttl) -> OK | VERSION_MISMATCH

• Namespaces prefix every key (feed:, profile:), map to tenants and carry quotas.
• Versions support optimistic concurrency (article 14) and can help with the stale-set race described in article 09.
• Every set has a TTL (the library enforces a maximum default), so mistakes heal themselves.

Each node keeps, in memory:

Hash table: key -> entryentry = {  value bytes,  expires_at,            for TTL  version,               for compare-and-set  LRU links (prev/next)  or an access clock, for eviction}

• Expiry: checked lazily on access (an expired key is treated as a miss and removed) and actively by a background task that samples keys with TTLs and removes expired ones, so memory is reclaimed even for keys nobody reads.
• Eviction: when memory reaches the node's limit, evict by an LRU or LFU policy. Exact LRU needs a linked list touched on every read; Redis, for example, uses an approximated LRU that samples a few keys and evicts the oldest among them, because it costs much less memory and is close to exact in practice (Key eviction).
• Memory management: many small allocations fragment memory; cache servers typically use allocators or slab-style pools that group values by size. Plan for some overhead beyond raw data size (our 64 GB "usable" figure already assumes this).
• Per-namespace accounting tracks memory per tenant to enforce quotas: when a tenant exceeds its quota, eviction happens within that tenant's keys first.

App servers (clients) ---> one cache server (hash table, TTL, LRU)

A single node is simple and fast, and fine for small workloads. But it holds at most one machine's memory, its throughput is one machine's, and when it fails, every client experiences 100% misses at once.

1. Memory: 1.5 TB does not fit on one node.
2. Availability: one node is a single point of failure, and its failure causes a stampede on the databases behind the cache.
3. Partitioning: with many nodes, how does a client know which node holds a key, and what happens when nodes are added?
4. Hot keys: one very popular key can overload its node.
5. Cold starts: after a failure or restart, a node's keys must be refilled, loading the source of truth.

Spread keys across nodes by hashing. As article 16 showed, hash(key) mod N moves almost every key when N changes, which empties the cache in effect. Two better options:

• Consistent hashing with virtual nodes: each node owns many points on a hash ring; adding a node moves only about 1/N of keys, spread evenly. Amazon's Dynamo paper describes this technique (Dynamo).
• A fixed number of hash slots: hash each key into one of a fixed set of slots, and assign slots to nodes in a small table. Redis Cluster uses 16,384 slots, mapping a key with a CRC16 hash modulo 16,384, and lets clients force related keys into the same slot with "hash tags" (a part of the key in braces) so multi-key operations work (Redis cluster specification). Moving capacity means moving whole slots.

Choice: hash slots (for example 16,384), which make rebalancing a matter of reassigning slots and are easy to reason about.

Redis Cluster combines the first and third: clients cache the map, and nodes reply with redirection responses when a key lives elsewhere, which also handles keys that are mid-migration (Redis cluster specification).

Choice: smart clients with server redirects as the safety net; a proxy tier for languages without a good client.

Each slot range has a primary and at least one replica in a different availability zone.

• Replication is asynchronous (writes are acknowledged by the primary immediately), which keeps latency low; Redis's documentation describes its default replication as asynchronous (Redis replication). The cost: a failover can lose the last few writes, which is acceptable for a cache.
• Failure detection: nodes exchange heartbeats (Redis Cluster uses a gossip-based cluster bus), or a separate coordination service (etcd or ZooKeeper, article 22) tracks membership. A primary is declared failed only when a majority agrees, to avoid splitting the cluster on a single node's network blip.
• Promotion: a replica of the failed primary is promoted and the slot map updated; clients learn the change through redirects or map refreshes.
• Read replicas (optional): serving reads from replicas adds read capacity but returns slightly stale data. Offer it per namespace, as an opt-in.

When adding nodes:

1. Choose slots to move to the new node (for an even spread).
2. For each slot, copy keys from the old owner to the new one while the slot keeps serving.
3. During the move, reads for a key not yet copied are answered by the old owner (or redirected), writes go to the new owner.
4. Switch ownership in the map; clients update.

Because it is a cache, an acceptable simpler alternative is to move the slot without copying and let the new owner warm up through misses, if the source of truth can absorb the extra load. Move slots gradually either way.

A single key can receive more traffic than one node can serve (a celebrity profile, a flash-sale product, article 09):

• Client-side local caching of the hottest keys for a second or two (the largest win).
• Replicating hot keys to several nodes under suffixed keys, read at random.
• Reads from replicas for those keys.
• Detect hot keys by sampling access counts per key on each node and reporting the top ones.

When a node fails or a popular key expires, many clients miss at once and hit the source of truth (article 09):

• Replicas make node failures mostly invisible (only the last few writes are lost).
• Request coalescing in the client library: one load per key per client at a time.
• TTL jitter to avoid synchronised expiry.
• Optional persistence (snapshots or an append-only file) lets a restarted node reload its data instead of starting empty; Redis documents both approaches and their trade-offs (Redis persistence).
• Gradual warm-up: bring replacement capacity in slowly.

A multi_get of 100 keys spans many nodes. The client groups keys by node, sends one request per node in parallel, and merges results; latency is that of the slowest node involved. Keys that are always read together can share a hash tag so they live on one node. Clients keep persistent connection pools and pipeline requests (send several without waiting for each reply) to keep per-operation overhead low.

App servers (smart client: slot map cache, local hot-key cache, coalescing, pipelining)      |  direct to owning primary (redirect if the map is stale)      v+-------------------- 16,384 hash slots over 24 shards --------------------+| Shard 1: primary (zone A) -> replica (zone B)                              || Shard 2: primary (zone B) -> replica (zone C)        ...                   || Shard 24: primary (zone C) -> replica (zone A)                             |+----------------------------------------------------------------------------+      ^ membership, failure detection and slot map: cluster gossip or a consensus storeOperations: per-tenant quotas, metrics, hot-key reports, rebalancing tool

A cache makes weak promises, and callers must be designed for them:

• Data may disappear at any time (eviction, failover, restart). Every read must be able to fall back to the source of truth.
• Data may be stale relative to the source of truth. Callers choose TTLs and invalidation (article 09), and the stale-set race applies; compare_and_set with versions helps.
• Writes may be lost on failover (asynchronous replication). Never use the cache as the only copy of important data.
• Within one key on its primary, operations are atomic and ordered: incr and compare_and_set are safe for counters and optimistic updates.
• Reads from replicas are eventually consistent; opt in only where that is acceptable.

The Facebook memcache paper is a good example of these trade-offs at very large scale: it describes favouring performance and availability over strict consistency, with mechanisms such as leases to reduce stale sets and thundering herds (Scaling Memcache at Facebook).

• Private network only; the cache is never reachable from the internet.
• Authentication and per-tenant access control (for example per-namespace credentials or access-control lists), so one team cannot read another's keys.
• TLS for traffic if sensitive data is cached, or a policy of not caching sensitive data at all (article 09).
• Quotas and rate limits per tenant, against accidental floods.
• No secrets in keys (keys appear in logs and metrics).

"This is a multi-tenant, in-memory cache for about 1.5 TB of hot data and a million operations a second, with p99 under 2 ms in a zone. Memory decides the size: about 24 primary shards of 64 GB, each with an asynchronous replica in another zone.

Keys are hashed into 16,384 slots assigned to shards. Smart clients cache the slot map and talk directly to primaries; a node that receives a key it doesn't own redirects the client. Each node is a hash table with lazy and active TTL expiry and approximated LRU eviction within per-tenant quotas.

Failure detection needs a majority, and a replica is promoted within seconds; we accept losing the last few writes because this is a cache. Adding nodes moves slots gradually. Hot keys are absorbed by short-lived client-side caches and key replication, and stampedes by request coalescing and TTL jitter.

Callers must treat the cache as optional and possibly stale: every read can fall back to the source of truth, and nothing important lives only in the cache."

Memory: 400 GB / 48 GB = 8.3 -> 9 primariesThroughput: 300,000 / 60,000 = 5 primaries

• Next: Design a Notification System: Email, SMS and Push at Scale, the first Level 2 case study.
• Related: article 09 (caching patterns and stampedes) and article 16 (consistent hashing in code).