A distributed cache spreads cached data across many machines so the cache can hold more, serve more and survive a machine dying. The hash map on each node is the easy part. The hard parts sit between the nodes: how a client finds the node that owns a key, what happens when nodes join, leave or fail, and how stale copies get cleaned up across servers and regions.
Picture it first: a mithai shop at Diwali
In Diwali week, one counter can’t serve a busy mithai shop: the boxes don’t fit, one clerk can’t pack fast enough, and if that clerk falls ill the shop stops. So the owner opens eight counters and splits the sweets: kaju katli at counter 3, soan papdi at counter 6.
Customers must now find the right counter. The shop can print a board at the entrance, post a helper at the door who carries orders to the right counter, or let you ask any clerk, who says “kaju katli is at counter 3” so you go straight there next time.
Each counter has an assistant with a copy of its stock list who takes over if the clerk faints, though the last few sales may be missing from the copy. If a counter shuts with no stand-in, its customers rush the kitchen. And when a ninth counter opens, a sensible owner moves a ninth of the sweets to it rather than renumbering everything.
Map it back: counters are cache nodes (shards). The board, the door helper and the redirecting clerk are client-side hashing, a proxy tier and a server-side cluster. The assistant is an asynchronous replica, the kitchen is the database, and moving only a ninth is consistent hashing or slot migration.
Why one cache node stops being enough
You distribute a cache for four reasons. Work out which one binds, because each has a different fix.
- Memory. The hot working set doesn’t fit in one node’s RAM.
- Operations per second. One node’s CPU can’t keep up; Redis runs every command on one main thread.
- Network bandwidth. The NIC saturates before the CPU, usually because values are large.
- Availability. One node is a single point of failure; if the database can’t cope without the cache, losing it is an outage.
Take a Swiggy-style app caching menus and restaurant pages at dinner peak:
- Memory: a 300 GB working set. A 32 GB node keeps about 25% back for fragmentation, snapshots and replica buffers (ElastiCache’s default reserve), leaving 24 GB. 300 ÷ 24 = 12.5, so 13 shards.
- Throughput: 1.2M reads/s. If your load test shows 100,000 ops/s per node at an acceptable p99, that is 12 shards.
- Bandwidth: menus average 10 KB. 1.2M × 10 KB = 12 GB/s ≈ 96 Gbit/s. Keep each 10 Gbit/s NIC under half full for bursts, replication and resharding: 96 ÷ 5 ≈ 20 shards.
- Availability: one replica per shard, in another zone: 40 nodes.
Bandwidth wins. Compress menus to 3 KB and bandwidth needs about 6 shards (28.8 ÷ 5), memory about 4 (90 GB), and throughput’s 12 binds instead. Fix one constraint and the next one binds.
In the interview
Name the binding constraint out loud: “Memory says 13 shards and ops say 12, but 10 KB values push 96 Gbit/s, so bandwidth sets 20.” It shows you sized the cluster instead of guessing; the method is in back-of-envelope estimation.
Where the cache lives
In-process (local). A map inside each app process: about 100 ns per hit, no network, no extra fleet. But 200 pods means 200 copies, each filled and invalidated separately and cold after every deploy. It suits small, hot, rarely changing data such as config.
Remote shared cache. A Redis or Memcached fleet every app server shares: one copy per key that survives deploys and scales on its own, at the price of a network hop. The Redis latency guide puts a 1 Gbit/s round trip at about 200 µs; Facebook measured a median of 333 µs and a p95 of 1.135 ms per memcache request under production load, including routing and deserialisation.
Two-tier (near cache). A small L1 in each process in front of the shared L2. It soaks up hot keys and cuts L2 traffic, but each L1 copy can lag until its TTL runs out or an invalidation arrives. Redis 6 added server-assisted client-side caching (“tracking”): the server remembers which keys a connection read and sends an invalidation when one changes, or notifies subscribers of a key prefix in broadcasting mode. If that connection drops, the client must flush its L1.
Sidecar. A cache agent or proxy beside each app process: Facebook runs mcrouter on every web server, and Envoy can front Redis Cluster so apps use a plain client. You gain language-neutral routing and pooled connections, and pay a local hop and one more process per host (sidecar, ambassador and service mesh).
Partitioning: three ways to find the right node
Every router needs a key-to-node function that moves few keys when membership changes. Consistent hashing puts nodes and keys on a ring and gives each key to the next node clockwise, so adding a node moves only about 1/(N + 1) of the keys; virtual nodes even out the slices. Redis Cluster uses a fixed table of hash slots instead. The bigger choice is where the function runs.
Client-side hashing
The client library holds the server list and hashes each key straight to a server. Memcached was built for this: Facebook’s memcached servers never talk to each other, and its client handles serialisation, compression, routing and batching. EVCache shards with ketama, a consistent-hashing scheme written for memcached clients.
You gain one hop and simple servers. You pay in coordination: every client, in every language, must hash identically and hold the same server list, or one key ends up on two nodes. And every client process connects to every node.
A proxy tier
Clients send plain cache commands to a proxy that routes them. Facebook’s mcrouter handles almost 5 billion requests per second at peak, with consistent hashing by default, pooled connections, failover and replicated pools. Twemproxy was built mainly to cut connections to cache servers, and Envoy’s Redis proxy shards with ketama and supports hash tags.
You gain thin clients in any language, one place to change topology, and few connections per node. You pay an extra hop (Facebook’s gets over UDP straight to memcached were about 20% faster than over TCP via mcrouter) and a proxy fleet on the availability path.
Server-side clustering
The nodes own the map: in Redis Cluster they redirect clients that ask the wrong node, gossip, detect failures and promote replicas. You gain built-in failover and online resharding without proxies, and pay for cluster-aware clients, single-slot multi-key commands, and a cluster protocol to operate.
| Client-side hashing | Proxy tier | Server-side cluster | |
|---|---|---|---|
| Who holds the key-to-node map | Every client | The proxies | The nodes; clients cache a copy |
| Network hops per request | 1 | 2 | 1, or 2 after a redirect |
| Connections per cache node | Every client process × pool | Proxies × pool (small) | Every client process × pool |
| Adding a node | Push a new server list to every client | Update the proxies | Move slots; clients learn from redirects |
| Failover | Clients or a config system; gutter pools | Proxy health checks and failover routes | Built in: a replica is promoted by vote |
| Multi-key reads | Client splits by node | Proxy splits and merges | Only within one slot (hash tags) |
| Examples | Memcached with ketama, EVCache | mcrouter, twemproxy, Envoy | Redis Cluster |
| Pick it when | Few languages, every microsecond counts | Many services or huge client fleets | You want Redis features plus automatic failover |
Inside Redis Cluster: slots, redirects and hash tags
Every key maps to one of 16,384 slots: HASH_SLOT = CRC16(key) mod 16384. Each primary owns slot ranges; with three primaries a typical split is 0–5460, 5461–10922 and 10923–16383, and menu:7781 (slot 14816) lives on the third. The slot count caps a cluster at 16,384 primaries, but the spec suggests about 1,000 nodes as the practical limit.
Redirects. Clients cache the slot map and go straight to the owner. Ask the wrong node and it replies -MOVED 14816 host:port; the client retries there and should refresh its whole map with CLUSTER SHARDS, since a failover or reshard usually moves many slots at once. While a slot migrates, the source answers -ASK for keys that have already left; the client sends ASKING plus the command to the target for that one request, without updating its map.
Hash tags. If a key contains {…}, only the text inside the first braces is hashed. {user42}:cart and {user42}:orders both hash user42 (slot 14710), so one transaction, script or multi-key command can use both. Keys in different slots can’t be combined, and during a slot’s migration multi-key commands may fail with TRYAGAIN.
The cluster bus. Each node opens a second port (data port + 10000, so 16379 for a node on 6379) and keeps a TCP connection to every other node. Nodes ping a few random peers every second, plus any peer silent for half of NODE_TIMEOUT; each heartbeat carries a slot bitmap of 16,384 bits = 2 KB. Replicas serve reads to clients that send READONLY and accept stale data.
Hash tags can build you a hot shard
Everything with the same tag lives on one primary. Tag by the smallest unit that needs atomicity (a user, an order), never by a city or a big tenant, or one shard carries Mumbai while the rest idle. Single hot keys are covered in hot keys, cache stampede and invalidation.
Replication and failover
Each Redis primary streams writes to its replicas asynchronously: it replies OK without waiting, and replicas report how far they have read about once a second. After a short disconnect a replica resumes from its offset; otherwise it takes a full snapshot. So a write can be acknowledged and then lost before any replica has it.
Both the Cluster spec and the Sentinel docs say it plainly: acknowledged writes can be lost on failover. Three settings limit the damage; none removes it:
WAIT n timeoutblocks until the client’s earlier writes reachnreplicas; it is still not strong consistency.min-replicas-to-writerefuses writes unless enough replicas are connected and recently caught up.- Persistence on primaries. A primary without persistence that auto-restarts comes back empty, and its replicas then sync to empty too.
Sentinel or Cluster
Sentinel adds failover to non-clustered Redis (one primary per dataset). Run at least three Sentinels on machines that fail independently. A quorum must agree the primary is down and a majority must authorise the failover, so the minority side of a partition never fails over. Clients ask Sentinel for the current primary.
Cluster builds failover into the nodes. A primary unreachable for NODE_TIMEOUT (15 seconds in the default redis.conf) is suspected; once a majority of primaries agree, its replicas ask for votes and the winner takes over its slots, usually within a second or two. The minority side stops taking writes after NODE_TIMEOUT, and writes it accepted before then may be lost.
Why a cache can usually shrug, and when it can’t
For a cache, the database is the truth: a lost SET is just a miss. The dangerous case is a lost DEL, which leaves a stale value until its TTL. And when Redis is the store (sessions, rate-limit counters, carts, leaderboards), a lost write is lost data: use WAIT and AOF, or a durable Redis-compatible service such as Amazon MemoryDB, which writes to a Multi-AZ transaction log. The trade-offs mirror database data replication and CAP and PACELC.
A lost delete is worse than a lost set
After any failover, assume the new primary holds some values whose invalidations died with the old one. Keep a TTL on every key, and if deletes come from the database’s change log (change data capture), replay its last few seconds after a failover.
Adding and removing nodes
With hash(key) mod N, going from N to N + 1 nodes remaps N/(N + 1) of the keys; consistent hashing remaps about 1/(N + 1). For a cache, a remapped key is a miss. Take 20 nodes, 1.2M reads/s and 95% hits, so the database normally sees 60,000 reads/s. Add a 21st node:
- Modulo: 20/21 ≈ 95% of keys move. Hits fall to about 0.95 × 1/21 ≈ 4.5%, so the database sees about 1.15M reads/s, roughly 19× normal.
- Consistent hashing: about 1/21 ≈ 4.8% move. Hits fall to about 0.95 × 20/21 ≈ 90.5%, so the database sees about 114,000 reads/s, roughly 1.9×, falling as the new node fills.
Redis Cluster avoids the miss burst by moving data with the slot. The source marks the slot MIGRATING, the target IMPORTING, and a tool moves keys in batches with MIGRATE, so each key lives on exactly one side and ASK covers keys in flight. You pay in network and latency instead: giving a new node 1/21 of 300 GB is about 14 GB, roughly 5 minutes at a throttled 50 MB/s. MIGRATE locks both nodes while a key moves, so the spec warns against resharding big keys when latency matters. Removing a node means moving its slots away first.
Grow before the rush, one node at a time
Add capacity the day before an IPL final or a 10 am tatkal opening, one node at a time, watching hit ratio and database load. Flush any node that rejoins after being unreachable: it holds values whose deletes went elsewhere.
When a cache node dies
Lose one of those 20 nodes and its 60,000 reads/s all miss. The database’s 60,000 normal misses already include that node’s 3,000, so it now sees 57,000 + 60,000 = 117,000 reads/s: a brown-out for a 100,000 reads/s database, made worse by retry storms. Your options:
- Fall through to the database. Fine only if it has the headroom.
- Rehash onto the survivors. Facebook avoided this: one key can draw 20% of a server’s requests, and moving it onto a neighbour can topple that one too.
- Promote a replica. Redis failover hands over a warm copy within seconds of detection, for twice the memory.
- Use a gutter pool. Facebook keeps about 1% of its memcached servers idle as Gutter. A client whose get times out retries there; on a gutter miss it reads the database and fills the gutter with a short-lived entry, since gutter entries are never invalidated. This cut client-visible failures by 99%; when a server dies outright, gutter hit rates pass 35% within four minutes and often approach 50%.
- Read another zone’s copy. EVCache keeps a copy per availability zone, writes to all and reads locally, falling back to another zone on a miss or zone failure.
- Cap and shed. Whatever else you do, rate-limit fallback queries and serve degraded responses beyond the cap (backpressure and load shedding).
Cold clusters. A new or flushed cluster starts with no hits (Caching 101 covers warming one cache). Facebook’s Cold Cluster Warmup lets a cold cluster fetch misses from a warm one instead of the database, reaching full capacity in a few hours instead of a few days. Deletes in the cold cluster carry a two-second hold-off that rejects adds for the key, so a stale value from the warm side can’t land after an invalidation; a failed add sends the client to the database.
Caches across regions
Each region runs its own cache clusters, because cross-region round trips cost tens of milliseconds and each region should survive alone. So every hot key has a copy per region, and every write must reach them all.
Facebook’s design is the standard reference. One primary region holds the master databases; others hold read replicas fed by MySQL replication. A write embeds the cache keys to delete in its SQL. An invalidation daemon, mcsqueal, on every database reads what that database committed and sends the deletes to the cache clusters in its own region, batched through mcrouter (18× more deletes per packet). Because each region’s daemon follows its own replica, a key is deleted only after that region’s database has the change, so a refill can’t re-cache the old row. Buffered deletes are replayed after an outage.
Two more pieces complete it. Web servers also delete the key in their own cluster at once, so writers see their change. And a write from a non-primary region first sets a remote marker; a later miss that finds it reads the primary region, paying latency to avoid caching a stale replica row.
So Region B’s consistency window is roughly replication lag plus invalidation lag; Facebook calls this best-effort eventual consistency. EVCache instead writes cache values to every zone’s copy: simpler, but a failed remote write leaves that copy stale until its TTL. For the database side, see multi-region and active-active.
Redis vs Memcached
| Redis | Memcached | |
|---|---|---|
| Threading | One main thread executes commands; optional I/O threads for socket work | Multi-threaded workers (4 by default) |
| Data model | Strings, hashes, lists, sets, sorted sets, streams; atomic commands and Lua | Opaque byte values: get, set, delete, CAS, incr |
| Largest value | 512 MB per string | 1 MB by default, configurable up to 1 GB |
| Persistence | Optional RDB snapshots and AOF | None; a restart is empty |
| Replication | Built-in asynchronous primary to replica | None in the server; clients or proxies write copies (mcrouter, EVCache) |
| Clustering | Redis Cluster: slots, gossip, automatic failover | Client-side or proxy hashing; servers never talk |
| Eviction | maxmemory-policy: LRU, LFU, random or TTL-based |
LRU within each slab class |
| Security | Protected mode, ACL users, TLS | SASL; TLS since 1.5.13; never expose to untrusted networks |
| Pick it when | You need data structures, replication, failover or persistence | Plain key-value caching at scale, using many cores per node |
Eviction details are in cache eviction policies. Managed options handle failover and patching: Amazon ElastiCache (Valkey, Redis OSS or Memcached), Amazon MemoryDB (durable, for when Redis is the database), Google Memorystore for Redis and Redis Cluster, and Azure Managed Redis, the migration path from Azure Cache for Redis. You still own key design, sizing, hot keys and the outage plan; more in Redis.
Going deeper: limits that bite in production
Connections
With client-side hashing every node sees every app process. 3,000 pods × a pool of 4 is 12,000 connections per node, past Redis’s default maxclients of 10,000 (lower if file descriptors are short); ElastiCache fixes it at 65,000, and memcached defaults to 1,024. Facebook found a TCP connection from every web thread to every server too costly in memory, so it sends gets over UDP and funnels the rest through mcrouter. Share one pool per process, multiplex, or add a proxy tier (connection pooling).
Big values and serialisation
A 1 MB value read 1,000 times a second is 1 GB/s, about 8 Gbit/s: most of a 10 Gbit/s NIC for one key. Huge collections make single commands slow on Redis’s one thread and stall slot migration. Split them into chunks, compress, or keep blobs in object storage and cache a pointer. Every hit also pays deserialisation; Facebook’s values had a median of 135 bytes but a mean of 954, so measure yours (serialization and schema evolution).
Memory you can’t use
Per-key overhead dominates small values, fragmentation grows, and snapshots copy pages on write. Hence ElastiCache’s 25% default reserve: 13.5 GB advertised becomes about 10.1 GB of maxmemory. Memcached’s fixed size classes also strand memory when the mix of value sizes shifts.
One hop, many shards: fan-out and incast
Pages rarely read one key. One popular Facebook page fetched 521 distinct items on average (1,740 at p95), and most requests for it touched over 100 memcached servers. Wide fan-out hurts three ways:
- Tail amplification. A request waits for its slowest shard. If each shard is slow 1% of the time, a request touching 100 shards is slow 1 − 0.99¹⁰⁰ ≈ 63% of the time (assuming independent shards).
- Incast. Hundreds of replies arriving together overflow switch buffers. Facebook’s clients cap outstanding requests with a sliding window that grows on success and shrinks on timeouts.
- Splitting doesn’t help multigets. Facebook’s example: a server holding 100 items serves 500,000 requests/s, each for all 100 keys. Split the keys over two servers and each still sees 1M requests/s; replicate them and each sees 500,000.
Batch keys per node, co-locate keys read together, cap the window, replicate small hot sets, and cache assembled fragments (latency vs throughput vs bandwidth).
Security and tenancy
Redis is built for trusted clients on trusted networks. Since 3.2 it starts in protected mode, answering only on loopback if bound to every interface without a password; Redis 6 added ACL users limited by command and key pattern, and TLS can cover client, replication and cluster-bus links. Memcached’s docs say it must never face untrusted users; TLS arrived in 1.5.13. Keep caches in private subnets reachable only from the app tier, use TLS for personal data, and separate workloads: Facebook split a default “wildcard” pool from dedicated pools because high-churn keys evicted valuable ones. Per-team pools or prefix-scoped ACL users stop one tenant becoming everyone’s noisy neighbour (multi-tenancy and isolation).
Cheat sheet
| Idea | Remember it as |
|---|---|
| Why distribute | Memory, ops/s, NIC bandwidth, availability: compute each; the largest wins |
| Topologies | In-process (≈100 ns, N copies), remote (≈0.2–0.5 ms, one copy), near cache (L1 + L2), sidecar |
| Partitioning | Client hashing (ketama), proxy (mcrouter, twemproxy, Envoy), cluster (Redis slots) |
| Redis Cluster | CRC16(key) mod 16384; MOVED updates the map; ASK is one-off; {tag} for multi-key |
| Replication | Asynchronous; ack before copy; failover can lose acked writes; WAIT narrows, doesn’t close |
| Lost delete | Stale until TTL; replay invalidations after a failover |
| Resharding | mod N moves N/(N + 1); consistent hashing about 1/(N + 1); slot moves copy data |
| Node failure | Replica failover, gutter pool (≈1%), capped DB fallback; don’t rehash hot keys onto neighbours |
| Regions | One cache per region; delete from each region’s own database log |
| Fan-out | P(slow) = 1 − 0.99^k; batch per node, cap the window, replicate small hot sets |
| Security | Private subnet, ACLs or SASL, TLS; never internet-facing |
How to say it in the interview
“I’d run Redis Cluster for the menu cache. Memory says 13 shards and throughput 12, but 10 KB values mean 96 Gbit/s, so bandwidth sets 20 primaries, each with an async replica in another zone. Clients cache the slot map; keys that change together share a hash tag. Writes go to Postgres, then I delete the key, with a CDC consumer replaying deletes and a TTL as backstop. If a primary dies, its replica takes over seconds after detection; a few acknowledged deletes may be lost, and the TTL covers them. Database fallback is rate-limited, and I add shards the day before the sale, not during it.”
Why not just hash mod N? Growing from 20 to 21 nodes remaps 20/21 ≈ 95% of keys; hits fall from 95% to about 5% and the database sees about 19× its normal load. Consistent hashing or slot migration touches about 1/21.
Can the cache lose a write the client was told succeeded?
Yes. Replication is asynchronous, so a primary can acknowledge and die before streaming the write. A lost set is a miss; a lost delete is staleness until the TTL. WAIT and min-replicas-to-write shrink the window; data that must survive belongs in a durable store.
Client-side hashing or a proxy? Client-side for one hop and few client languages; a proxy when many services share the cache or connection counts explode, for an extra hop and a fleet to run.
How do you keep caches in two regions consistent? Each region has its own cluster, and deletes come from each region’s own database log, so they can’t overtake the data. A local delete shows writers their change; TTLs bound the rest.
A page reads 300 keys from 60 shards and p99 is bad. What do you do? Tail amplification: 1 − 0.99⁶⁰ ≈ 45% of pages wait on a slow shard. Batch per shard, co-locate keys with hash tags, cap outstanding requests, replicate small hot sets, and cache the assembled fragment.
Where to go next
- Consistent hashing: the ring, virtual nodes, jump hash and why fixed slots work.
- Hot keys, cache stampede and invalidation: one key, too many readers.
- Caching strategies: delete-on-write, leases and the stale-set race.
- Cache eviction policies: what each node throws away when it is full.
- Data replication: the same asynchronous-replication trade-offs for databases.
- Database sharding: partitioning when the data can’t be refilled.
- Redis: the engine behind most distributed caches.
- Design a distributed cache: all of this as a full interview problem.
References and further reading
- Redis cluster specificationredis.io16,384 hash slots and CRC16, hash tags, MOVED and ASK redirects, slot migration, the cluster bus, failure detection, and the windows in which acknowledged writes are lost.
- Redis replicationredis.ioAsynchronous primary-to-replica replication, partial and full resync, WAIT, min-replicas-to-write, and the danger of auto-restarting a primary without persistence.
- High availability with Redis Sentinelredis.ioAt least three Sentinels, quorum for detection versus majority for failover, no failover on the minority side, and no guarantee that acknowledged writes survive.
- Redis client-side caching referenceredis.ioServer-assisted near caches: tracking and broadcasting modes, the invalidation table, and flushing the local cache when the invalidation link drops.
- Redis securityredis.ioTrusted clients in trusted networks, protected mode, ACL users, and TLS on client, replication and cluster-bus links.
- Scaling Memcache at Facebook (Nishtala et al., NSDI 2013)usenix.orgConsistent hashing in clients, mcrouter, incast and sliding windows, pools, Gutter (about 1% of servers), mcsqueal, regional pools, cold cluster warm-up, remote markers, and measured fan-out and latency.
- mcrouter wiki (Facebook)github.comA memcached protocol router handling almost 5 billion requests per second at peak; ch3 consistent hashing by default, pooled connections, failover, warm-up and replicated pools.
- Memcached documentation: Configuringdocs.memcached.orgWorker threads (default 4), the 1,024 default connection limit, UDP off by default, and why memcached must never face untrusted networks.
- Announcing EVCache: distributed in-memory datastore for cloud (Netflix Technology Blog)netflixtechblog.comKetama sharding within a zone, one copy per availability zone, writes to every zone, local-zone reads with fallback, and a sidecar per memcached server.
- Amazon ElastiCache: Managing reserved memory for Valkey and Redis OSSdocs.aws.amazon.comWhy 25% of a node’s memory is held back by default for fragmentation, copy-on-write snapshots and replica buffers.