Design a distributed cache

A distributed cache is a fleet of machines that keeps hot data in RAM so your databases don’t have to answer every read. To a product team it looks like one enormous hash table: get, set with a time-to-live, delete, answered in well under a millisecond. Underneath hide three hard problems. Routing: which of 300 machines holds catalog:v7:product:12345, and what moves when you add one? Consistency: how does the cache learn the price just changed? Load protection: what happens to the database when a popular key expires, or a node dies, at 00:00 on the first night of a big sale? You will design a shared cache service — Memcached or Redis run as a platform — that hundreds of teams put in front of their databases, at 10 million operations a second during a Big Billion Days-style sale or a cricket World Cup final.

Understand the problem

Start by saying what a cache is not: a database. The database is the source of truth; the cache may lose any item at any moment — eviction, expiry, a restart, a dead node — and the system must stay correct, only slower. That shapes every later decision: no write depends on the cache, and every miss has a well-defined way to refill.

Functional requirements

1. Clients should be able to get, set (with a TTL) and delete values by key, and fetch many keys in one call.
2. The system should support cache-aside safely. A miss tells the caller to load from the database and fill; a database write invalidates the cached copy, and no race may leave a stale value behind indefinitely.
3. Teams should be able to create an isolated namespace with a memory quota, a default and maximum TTL, and a resilience level (one copy or two), self-service and live within minutes.
4. The system should manage memory by itself: expire items at their TTL and evict the least useful items when a namespace is full, without ever refusing a write.

Non-functional requirements

• Latency. p50 under 0.5 ms and p99 under 2 ms for a client in the same zone. For calibration, the Facebook memcache paper measured a 333 µs median get in production.
• Throughput. 10M ops/s at peak — the first minutes of a midnight sale, the last overs of a final — and about 3M/s on a normal evening. Around 90% reads.
• Hit ratio. At least 95%, reported per namespace. The databases are sized for the misses.
• Capacity. About 25 TB of unique cached data, roughly 25 billion items, in about 200 namespaces. Values up to 1 MB; most are a few hundred bytes to a few KB.
• Availability. 99.99% of operations get an answer — a hit or a clean miss — within the client’s timeout. Losing a node, or a zone, must never become a database outage.
• Freshness. Eventually consistent: after a database commit, the cached key is gone in every zone within 1 s at p99, and every item has a TTL, so anything missed heals itself.
• Durability. None, by design.

Out of scope

• Durable storage. Data that must not be lost belongs in a key-value store or a database.
• HTTP and edge caching. Caching whole responses near users is a CDN’s job.
• Large blobs. Images, video segments and values over 1 MB go to object storage, usually behind a CDN.
• Rich data types and scripting. This platform is plain key-value; the rate limiter shows Redis scripting.
• Strongly consistent caching across regions. We sketch multi-region behaviour in the follow-ups.

The set-up

Plan the approach

Name the shape early: “a data plane of cache nodes plus a smart routing layer, and a control plane that owns topology and namespaces.” Build one working path per requirement, then spend most of the time in the deep dives, where this problem is won.

Core entities

• Namespace. A team’s slice of the cache: name, owner, pool, memory quota, default and maximum TTL, copies (1 or 2), and a generation number baked into every key.
• Item. Key (at most 250 bytes in our API), value (opaque bytes, at most 1 MB), flags, expiry time, and a version number used for compare-and-set.
• Pool. A group of nodes that serves one or more namespaces, with its own eviction policy and replication setting.
• Slot map. For each pool, a versioned table from 16,384 hash slots to a primary node (and a replica, if the pool keeps two copies).
• Lease. A short-lived token the cache hands to the one caller allowed to fill a missing key.
• Hot-key list. Keys currently flagged as hot, pushed to every router.

Keys carry the namespace, its generation and the entity:

catalog:v7:product:12345        namespace catalog, generation 7, product 12345
session:v3:u:8812f0             namespace session, generation 3, a login session

API

On the wire this is a compact protocol — memcached’s or Redis’s RESP — over persistent TCP connections. It is shown as HTTP for readability.

Read. A hit returns the value and its version. A miss returns a lease if you are the first to miss; otherwise it asks you to wait briefly and may hand you the last known value, marked stale.

GET /v1/catalog/product:12345

{ "hit": true, "value": "eyJuYW1lIjoiUGhvbmUgWDEiLCJwcmljZSI6OTk5OX0=", "version": 88123, "ttl_ms": 241000 }

{ "hit": false, "lease": "ls_7f3a91c2", "lease_ttl_ms": 10000 }

{ "hit": false, "lease": null, "retry_after_ms": 5, "stale": { "value": "eyJuYW1lIjoi…", "age_ms": 1800 } }

Fill and write. A fill carries the lease. If the key was deleted after your miss, the lease is void and the cache drops your value, because it may already be out of date.

PUT /v1/catalog/product:12345?ttl_s=300&lease=ls_7f3a91c2
Content-Type: application/octet-stream

<value bytes>

{ "stored": false, "reason": "lease_invalid" }

Delete is idempotent and always succeeds: DELETE /v1/catalog/product:12345 returns 204 No Content whether or not the key existed.

Multi-get fetches many keys at once; the router splits it into one batch per node and sends the batches in parallel.

POST /v1/catalog:mget
Content-Type: application/json

{ "keys": ["product:12345", "price:12345", "stock:12345:BLR"] }

Namespaces are created through a low-traffic admin API in the control plane:

POST /v1/namespaces
Content-Type: application/json

{ "name": "catalog", "team": "catalog-platform", "memory_gb": 3000,
  "default_ttl_s": 600, "max_ttl_s": 86400, "copies": 2, "eviction": "lfu" }

Back-of-envelope estimates

These numbers decide the node count, the routing layer, and which failure hurts most (method: back-of-envelope estimation).

Operations. 10M ops/s at peak, 90% reads: 9M gets/s and 1M writes/s. At a 95% hit ratio, 9M × 5% = 450k misses/s reach the databases, and nearly every miss becomes a fill, so about 450k writes are sets and ~550k are deletes from invalidation. Notice the leverage: with no cache the databases would see 9M reads/s — twenty times as many — and if the hit ratio slips from 95% to 90%, misses double to 900k/s. This cache is load-bearing.

Items. Assume about 1 KB per item, counting key, value and metadata — a round number near published figures: the Facebook paper reports a 135-byte median and 954-byte mean response, and in the Twitter study the median cluster’s mean value is about 230 bytes. 25 TB ÷ 1 KB = 25 billion items.

Memory. Namespaces whose misses really hurt — sessions, the sale catalogue — keep a second copy in another zone; say 5 TB of the 25. Total: 25 + 5 = 30 TB of cached data.

Nodes, by memory. Take a node with 128 GB of RAM, 16 cores and a 25 Gbps NIC, and use 100 GB for items; the rest covers the hash table, fragmentation, connection buffers and the OS. 30 TB ÷ 100 GB = 300 nodes: 250 primaries plus 50 replicas.

Nodes, by operations. The Facebook paper’s Table 2 shows near-peak production loads of 262k gets/s per memcached server in its default pool and 710k in a replicated pool. Budget 200k ops/s per node to keep CPU near 50%. Reads and writes go to primaries: 10M ÷ 250 = 40k ops/s per primary on average. Operations alone would need 10M ÷ 200k = 50 primaries, against 250 for memory, so memory is the constraint, by a factor of five. The spare CPU absorbs skew: the busiest node routinely carries several times the average.

Network. 9M gets/s × 1 KB = 9 GB/s, about 72 Gbps leaving the fleet; ÷ 250 primaries ≈ 0.3 Gbps per node, around 1% of the NIC. Fills add 450k × 1 KB ≈ 3.6 Gbps fleet-wide. On average the network is idle — but one hot 20 KB value read 150k times a second is 20 KB × 150k = 3 GB/s = 24 Gbps, an entire NIC for one key.

Connections. About 20,000 application pods run on 2,500 hosts. If every pod keeps 2 connections to every primary, each node holds 20,000 × 2 = 40,000 connections (10M in total) — four times Redis’s default limit of 10,000 clients. With one routing sidecar per host: 2,500 × 2 = 5,000.

Latency. A read is mostly network — a few hundred microseconds of round trip and kernel time; the server’s hash lookup takes tens. The p99 comes from queueing and big values, another reason to keep nodes near 50% CPU.

High-level design

Build one requirement at a time; by the end, the cache works in one region at moderate load.

Clients should be able to get, set and delete by key

One server is easy: a hash table in RAM, which is what a memcached instance is. But 30 TB doesn’t fit in one machine, so the data is split across nodes and something must decide which node holds which key.

Put that decision in a routing layer next to the application — for now, a client library inside every app pod. The library hashes the key to one of 16,384 slots, looks the slot up in a slot map, and sends the request straight to the node that owns it. A config service pushes a new slot map whenever the fleet changes. The nodes stay simple: independent hash tables that never forward requests or talk to each other, as memcached servers work in the Facebook deployment.

The path is short:

1. The app calls get("catalog:v7:product:12345").
2. The library computes CRC16 of the key modulo 16,384 — slot 7755 — and reads the owner from its in-memory copy of the slot map: node 119.
3. It sends the request on a connection it already holds to node 119 and gets the value back, one round trip.

Multi-get groups keys by node and sends one batch per node in parallel; in the Facebook paper, a popular page fetched 521 items on average. Fan-out has a cost: a page that touches 100 nodes waits for the slowest, so one sick node shows up in many pages’ tail latency. Put keys read together on one node (a shared hash tag, below), and cap requests in flight so a burst of replies doesn’t overflow switch buffers — the paper’s incast congestion.

The system should support cache-aside safely

The cache doesn’t know your database, so the application drives it. This is cache-aside (or look-aside): on a read, try the cache; on a miss, read the database and fill the cache with a TTL. On a write, update the database, then delete the key rather than overwriting it — deletes are idempotent, as the Facebook paper notes, and the next reader refills from whatever the database now says.

Why not read-through or write-through, where the cache loads from and writes to the database itself? Because 200 teams bring 200 schemas and a dozen database technologies; a cache-aside cache only stores bytes. Dumb servers and a smart, stateless client is also the Facebook paper’s lesson: stateless code is easy to change and roll back. (Compare caching strategies.)

Two rules make it safe enough for now. Every item has a TTL, capped per namespace, so a wrong value is wrong for minutes, not forever (TTLs are mandatory at Twitter, per its study). And writers delete after the commit, never before — deep dive 2 shows why, and the race that remains.

Teams should be able to create isolated namespaces

Two hundred teams in one big pool interfere. The Facebook paper describes the classic case: in a shared LRU, valuable but rarely read keys are evicted to make room for high-churn keys nobody reads again. So every key carries its namespace as a prefix, and each namespace is assigned to a pool of nodes with its own memory and eviction settings. Big or sensitive namespaces get dedicated pools; the long tail shares one. A small gutter pool stays idle until a node fails (deep dive 6).

The node counts follow from the estimates: the catalogue’s 3 TB and the sessions’ 2 TB are stored twice (60 and 40 nodes), and the other 20 TB fills 200 shared nodes — 300 in all. Creating a namespace is a control-plane operation: the API validates it against capacity, the registry records it, and the config service publishes maps every router picks up within seconds.

A shared pool can’t give each namespace a hard memory quota — one LRU serves them all — so the router enforces per-namespace ops/s, value-size and TTL limits, and a namespace that needs guaranteed memory moves to a dedicated pool. Pooling is cheap; isolation is predictable.

The system should manage memory by itself

Each node has a hard memory limit. Items expire at their TTL — checked when read, and by a background crawler — and when memory is full, the node evicts something. It never refuses a write: Redis’s noeviction policy, which errors at the limit, suits a database, not a cache. What to evict is deep dive 5.

You now have a working cache. The deep dives are about what breaks at 10M ops/s.

Deep dives

How do we spread keys across nodes?

Every router must agree which node owns each key, and when the fleet changes, as few keys as possible should move — in a cache, a key that moves is a key that misses.

Bad: hash mod N. node = hash(key) mod N is perfectly even and needs no state. Then you add one node. A key stays where it was only if hash mod N equals hash mod (N+1), which happens for about 1 key in N+1. Going from 3 to 4 nodes, 9 keys in 12 move; going from 250 to 251 primaries, 250 ÷ 251 ≈ 99.6% of keys move. Each is looked up on a node that doesn’t have it, so the hit ratio drops to nearly zero and the databases get 9M reads/s. Removing a dead node does the same. Karger and his co-authors made this point in 1997: with a classical hash, “almost every item would be hashed to a new location”.

Good: consistent hashing. Karger’s construction places nodes and keys at pseudo-random points on a circle, and each key belongs to the nearest node point in one direction. Adding node D moves only the keys on D’s new arc, all to D; no key moves between old nodes. The expected share moved is 1/(N+1): 1 ÷ 251 ≈ 0.4%, about 36k extra misses a second for a few minutes instead of a wipe (see consistent hashing).

One point per node is too lumpy: the longest of N random arcs is roughly ln N times the average, so at 250 nodes the unluckiest node owns 5 to 6 times its fair share. The fix, already in Karger’s paper, is many points per node — virtual nodes. A node’s share is then a sum of V random arcs, and its spread shrinks like 1/√V: about ±10% with 100 virtual nodes, ±5% with 400. The cost: a ring of 25,000 points to binary-search per lookup, and membership changes that reshuffle thousands of small arcs at once, which makes “what moved, and when” hard to reason about.

Great: fixed hash slots. Redis Cluster makes the useful part explicit. The key space is cut into 16,384 slots; a key’s slot is CRC16(key) mod 16384; a slot map says which node owns each slot. With 250 primaries each owns 65 or 66 slots, even to within about 1.5%. Adding a node means handing it about 65 slots, at a pace you control. The map is a 16,384-entry array — 32 KB with 2-byte node IDs — so every router holds a copy and a lookup is one array read.

Slots also give you two tools a ring makes awkward:

• Co-location by design. If a key contains a hash tag in curly braces, only the tag is hashed, so {u:8812f0}:cart and {u:8812f0}:profile land in the same slot and one multi-get to one node fetches both.
• Explicit migration. A slot being moved is MIGRATING on the old owner and IMPORTING on the new; requests for keys already moved get an ASK redirect, and once the move finishes, stale routers get MOVED and refresh their map.

A pure cache can go cheaper: reassign the slot without copying anything. The new owner fills on demand: 9M reads/s × 65 ÷ 16,384 ≈ 36k extra misses/s, briefly, kept orderly by the leases described below. Copy data only for namespaces with expensive misses. Either way, a node that gives up a slot must drop that slot’s keys; otherwise, if the slot ever returns, it serves values that missed every delete while away.

The cost: 16,384 caps primaries per cluster, and Redis suggests staying around 1,000 nodes. Our 300 fit comfortably.

Where should routing run? The mapping is easy; the question is which process applies it.

Choose the sidecar. It adds no network hop, cuts each node’s connections from 40,000 to 5,000, and gives one place to ship leases, gutter failover and near caches without 200 teams redeploying. Facebook runs this shape: mcrouter, a memcached-protocol router, runs on each web server to coalesce TCP connections and now handles almost 5 billion requests a second at peak. Keep a native library as an opt-in, and a proxy tier only for clients you can’t change (see sidecar, ambassador and service mesh and connection pooling).

How do we keep the cache consistent with the database?

No transaction spans the database and the cache. The question is not whether the cache is ever stale, but how stale, and for how long.

Bad: update the cache on every write. Two writers break it: writer 1 sets the price to ₹999 in the database, writer 2 sets ₹899, and their cache updates arrive in the opposite order. The database says ₹899, the cache says ₹999, and only the TTL will fix it. It also ships values that may never be read.

Good: delete on write. Update the database, then delete the key. Concurrent deletes can’t conflict, and a retried delete is harmless. Much better — but one race survives, which the Facebook paper calls a stale set.

A reader misses and reads the old price. Before it fills, a writer commits a new price and deletes the key — deleting nothing, because the key isn’t there yet. Then the reader’s set lands, and the old price stays until its TTL runs out. In a flash sale, with thousands of readers per hot key, this race is routine.

Great: leases, plus a TTL backstop. On a miss, the cache returns a lease — in Facebook’s implementation, a 64-bit token bound to the key — which the caller must present when it fills. A delete voids any outstanding lease, so a fill carrying a voided token is dropped: “store only if nobody touched it since I looked”, like load-linked/store-conditional on a CPU. The cost is one token per in-flight miss. The TTL still caps the damage of anything the scheme misses — a lost delete, a bug — at minutes.

Who sends the delete? So far, the writing app — which can crash between commit and delete, may share the table with other services that forget, and doesn’t run when an operator issues a bulk UPDATE at 2 a.m.

The robust answer is to drive invalidation from the database’s commit log, which sees every committed change. Facebook runs a daemon called mcsqueal on every database: data-changing SQL carries the cache keys to invalidate, and after commit mcsqueal reads them from the log and broadcasts deletes to every frontend cluster. Because the source is a durable log, lost deletes can be replayed.

Our platform does the same with standard change data capture:

1. The app commits a change to its database.
2. A CDC reader tails the replication log (MySQL binlog, PostgreSQL WAL), which holds only committed changes.
3. It publishes row changes to a Kafka topic, which is durable and replayable.
4. An invalidator consumes the topic and turns rows into cache keys using key templates each namespace registers, for example products.id → catalog:v7:product:{id}.
5. It batches deletes per node and sends them to every zone; Facebook’s batching packed 18× more deletes per packet at the median.
6. The writing app also deletes the key in its own zone, so a user sees their own change on the next page. The pipeline is the guarantee; this is the fast path.

Most deletes hit nothing — in the Facebook paper only 4% removed a cached item — so keep them cheap. Templates handle “one row, one key”; derived keys such as catalog:v7:top20:phones depend on many rows, so give them short TTLs.

How fresh is “eventually”? Facebook measured four nines of deletes applied within 1 second inside its master region, and three nines across replica regions; our 1-second p99 target is in that range. TTLs turn the remaining tail from “stale forever” into “stale for minutes”, so choose them by how wrong a value may be: a price for 5 minutes, a description for an hour.

How do we stop a cache stampede?

At 00:00 the sale opens and one product page — the ₹9,999 phone — is read 50,000 times a second. Its entry expires. The query behind it takes 50 ms under sale load, and every request in those 50 ms misses and runs it: 50,000/s × 0.05 s = 2,500 identical queries in flight for one row. The load slows the query, which widens the window, which lets in more misses — the VLDB stampede paper calls it a cascading failure.

Bad: do nothing. Fine for cold keys, fatal for hot ones.

Good: request coalescing (single-flight). In each process, the first miss starts the fill and later requests for that key wait for its result. It is a few lines in the sidecar, but it only coalesces within one process: with 500 pods serving the page, up to 500 concurrent queries remain.

Great: leases with hot-miss throttling, and hot keys that never expire. The same lease does double duty. The cache issues at most one lease per key per few seconds — Facebook’s default is one every 10 seconds — and tells other missers to wait a few milliseconds and retry, by which time the key is usually filled. Concurrent queries drop to one, fleet-wide; in the paper, peak database queries for herd-prone keys fell from 17K/s to 1.3K/s. Two refinements:

• Serve stale while one refills. Keep a deleted or expired value for a few seconds and return it, marked stale, to callers without the lease; Facebook found most applications could use it unchanged. The caller decides: a two-second-old description is fine, a checkout price is not.
• Refresh hot keys before they expire. Probabilistic early expiration (the VLDB paper’s XFetch) has each reader refresh early with a probability that rises near expiry: refresh if now − Δ·β·ln(rand()) ≥ expiry, where Δ is the last refill time and β defaults to 1. At 50,000 reads a second, dozens of readers can still fire together, so pair it with the lease. Keys on the hot list are simply refreshed in the background by the sidecar.

One stampede is self-inflicted: synchronised expiry. A job that warms 2 million keys at 23:50 with a 600-second TTL makes them all expire at 00:00, as the sale opens. A TTL of 600 ± 60 seconds spreads them over two minutes (more in hot keys, cache stampede and invalidation).

How do we handle hot keys?

Last over of a World Cup final: the 2 KB live-score key cricket:v2:match:wc-final:score is read 1M times a second, and it lives on one node (node 92, slot 6015) budgeted for 200k ops/s. The CPU saturates first; 1M × 2 KB = 2 GB/s = 16 Gbps also eats two-thirds of the NIC. Node 92 holds about 100 million other keys from dozens of namespaces, and all of them start timing out — a noisy neighbour the size of one item. In a sale, a 20 KB product payload read 150,000 times a second needs 24 Gbps, a whole NIC.

First, find them. Each sidecar samples about 1 request in 100 into a small top-K sketch and flushes it to a hot-key detector every second — 10M ops/s becomes 100k samples/s. Keys above about 10% of a node’s budget (20k ops/s) go on the hot list, pushed to every sidecar within seconds. Many hot keys are predictable — the final, the headline sale item — so namespaces can pre-register them and be protected before 00:00, not two minutes after.

Bad: a bigger node. One key lives on one node, and every request for it lands on one NIC and, in Redis, one thread. More cores or RAM change nothing.

Good: replicate the hot key. Store R copies under suffixed keys — …:score#0 to …:score#3 land on nodes 190, 127, 64 and 1 — and read a random one. With R = 4 each copy sees 250k reads/s, still over budget; with R = 8, 125k. Facebook replicates within a pool for the same reason. You pay in writes: every fill and delete must reach all R copies, and two readers may briefly see different versions.

Great: a near cache in the sidecar, on top of a few copies. For hot-list keys, the sidecar keeps the value in memory for one second, so each of 2,500 sidecars asks the cache at most once a second: 2,500 reads/s instead of 1M — 99.75% never leave the host — or about 625 per copy. The cost is freshness: a score up to a second old is fine, stock at checkout is not, so the near cache is opt-in per namespace. When a second is too long, push invalidations: Redis’s client-side caching tracks which keys each client read and notifies it on change, or broadcasts changes by key prefix.

Two habits keep hot keys rare. Keep hot values small: split a 20 KB product blob into a tiny fast-changing key (price, stock) and a large slow-changing one with a long TTL. And keep hot keys out of hash tags: a hot tag pins everything sharing it to one node.

How do we evict and use memory well?

Memory sets the fleet size, and one byte wasted per item is 25 GB across 25 billion items.

What an item costs. Besides key and value, every item carries bookkeeping: 49 bytes per object in Twemcache, per the Twitter study; 32 to 40 bytes for memcached’s item header on a 32-bit build, more on 64-bit; and in Redis even an expiry costs extra memory. With a 40-byte key and a 230-byte value, 50 bytes of metadata is about a sixth of the item; with a 100-byte value, about a quarter. Tiny items are expensive: ten feature flags as ten keys pay ten headers, as one key they pay one.

How memory is allocated. A general-purpose allocator fed billions of small, varied objects fragments badly — the Twitter paper’s reason for avoiding one. Memcached uses a slab allocator: memory is cut into 1 MB pages, each page belongs to a slab class, and each class cuts its pages into equal chunks — 80, 104, 136, 176 bytes and up in the memcached wiki’s example, each about 1.25 to 1.3 times the last. An item takes the smallest chunk that fits, so a 90-byte item wastes 14 bytes of a 104-byte chunk; with a growth factor of 1.25, no item wastes more than about 20%. Facebook used 1.07 to waste less.

The catch is slab calcification: in classic memcached a page never leaves its class. If a team adds fields and items grow from 900 bytes to 1.4 KB, the larger class owns few pages and evicts its newest items within minutes, while old-class pages sit on items nobody reads. The Twitter study found sizes really do shift, daily and suddenly. The fixes move memory: Facebook’s adaptive allocator gives a page to any class whose next eviction victim is at least 20% more recently used than average; open-source memcached added a rebalancer that evens out eviction rates; Twemcache evicts whole slabs. Turn rebalancing on and alert when eviction ages diverge.

Which item to evict. When a class (or, in Redis, the instance) is full:

• Exact LRU needs two list pointers per item and a lock to move an item on every hit. Memcached softens this with a segmented LRU (hot, warm and cold queues, maintained by a background thread): most reads skip the lock, and items read once flow out through the cold queue without pushing out the regulars.
• Approximated LRU, Redis’s approach: sample a few keys (maxmemory-samples, default 5), evict the one idle longest, and keep a pool of good candidates. With 10 samples it is very close to true LRU, with no per-item pointers.
• LFU counts accesses instead. Redis keeps an 8-bit logarithmic (Morris) counter per key, saturating around a million hits by default, and decays it after a period of disuse (one minute by default) so yesterday’s bestseller can fade. It suits stable, skewed popularity, and a scan of cold keys can’t flush the bestsellers.
• FIFO is simplest, and the Twitter study found it often matches LRU at reasonable cache sizes.
• Expired items first. Facebook’s transient item cache frees short-TTL items the moment they expire; for one key family it cut the pool’s memory share from 6% to 0.3% with no loss of hit rate.

The default is sampled LRU with expired items reclaimed first; the catalogue pool uses LFU; high-churn namespaces get their own pool. More in cache eviction policies.

What happens when a cache node fails?

With 300 nodes, one is always failing or being replaced. Each primary serves 9M ÷ 250 = 36k reads/s; when it dies they become misses — 8% more than the normal 450k/s, spread over many namespaces. Survivable, unless a hot key concentrates its misses on one database, every request waits out a timeout, or a whole zone goes.

Detect locally: each sidecar marks a node down after a few 5 ms timeouts and probes it in the background — a per-node circuit breaker. The control plane confirms before changing any map.

Bad: rehash the dead node’s keys onto survivors. The keys are cold wherever they land, so database load is unchanged — and the neighbour inherits the hot keys. The Facebook paper warns one key can be 20% of a server’s requests: the neighbour slows, is marked dead, passes everything on, and the failure cascades. And a returning node holds values that missed every delete, so it must be flushed.

Good: a gutter pool. Keep a few idle nodes — Facebook’s gutter is about 1% of a cluster; ours is 3 nodes, one per zone. When a get times out, the sidecar retries in the gutter; on a gutter miss it reads the database and fills the gutter with a short TTL (10 seconds), since the pipeline sends the gutter no deletes. No healthy node inherits anyone’s hot keys. Facebook reports the gutter cuts client-visible failures by 99%, and when a server dies its hit rate passes 35% within four minutes, often approaching 50%. The costs: up to 10 seconds of staleness, and 3 × 200k ÷ 36k ≈ 16 dead nodes’ worth of capacity — a handful, not a zone.

Great: a second copy in another zone where misses are expensive, plus the gutter for the gap. The catalogue and session pools replicate every slot to another zone. Once the control plane confirms a primary is dead, it promotes the replica and publishes a new map; the gutter covers the seconds between. (Redis Cluster promotes on its own once a primary has been unreachable for cluster-node-timeout — 15 seconds by default — plus a second or two for the election.) Replication is asynchronous, so the last writes before a crash can be lost — and a lost delete is a stale value until its TTL. Close the hole with the log you already have: after a promotion, the invalidator replays the last minute of deletes for that node’s slots from Kafka. Deletes are idempotent, so extras are harmless.

Why not two copies of everything? It would take 50 TB of RAM instead of 30 TB for namespaces whose misses are cheap. Know what you accept: if every pool were single-copy, losing one of three zones would make a third of all keys miss — once the lost zone’s users shift to the other two, about 9M × 1/3 ≈ 3M extra misses/s, more than six times normal. Shared-pool tenants must ride out a cold third with leases, stale reads and load shedding in front of their databases (see backend failure modes).

Warming cold capacity. A new node starts at 0% hits, and Facebook says a memcached server takes a few hours to reach 90% of its peak hit rate. Ramp traffic onto new nodes gradually. For a whole new cluster, let misses read from a warm cluster instead of the database — Facebook’s cold cluster warm-up does this, with a 2-second hold-off on deletes so racing stale fills are rejected, and reaches full capacity in hours instead of days. Netflix warms new EVCache clusters by dumping keys from existing ones, and Facebook keeps cached data in shared memory so an upgrade doesn’t empty a node.

The final design

The hot path is the app, its host’s sidecar and one cache node; everything else runs beside it.

Follow a product-page read and a price change through the system:

1. Near cache. The app asks its host’s sidecar for catalog:v7:product:12345. A hot-list key is answered from the one-second near cache.
2. Route and read. Otherwise the sidecar hashes the key to slot 7755, looks up its primary and sends a get over a pooled connection. A hit returns in well under a millisecond; a miss returns a lease, or a short wait and perhaps a stale value if someone else holds it.
3. Miss and write. On a miss, the app reads the database and fills with its lease and a TTL; the fill is dropped if the key was deleted meanwhile. On a write, the app commits, then deletes the key in its own zone.
4. Capture. A CDC reader tails the database log and publishes committed row changes to Kafka.
5. Invalidate. The invalidator maps rows to keys with the namespace’s templates and sends batched deletes to every copy in every zone within a second at p99, replaying recent deletes after any promotion.
6. Fail over. If a node stops answering, the sidecar’s breaker opens after a few 5 ms timeouts and its traffic goes to the gutter pool (10-second TTL) until a replica is promoted or the node replaced.
7. Configure. The control plane creates namespaces, publishes versioned slot maps and pushes the hot-key list. If it is down, sidecars keep their last maps.

Check it against the requirements. Latency: one in-zone round trip through a loopback sidecar, inside 0.5 ms at p50, with nodes at 40k of a 200k ops/s budget to protect the p99. Throughput: 10M ops/s over 250 primaries, hot keys absorbed by near caches and copies. Capacity: 300 nodes hold 30 TB. Hit ratio: pools, LFU for stable popularity, and leases keep misses near 450k/s. Availability: no single node — and for critical pools no zone — can push its traffic onto the databases. Freshness: delete-on-commit, leases and a log-driven pipeline, with TTLs as the last line of defence.

What interviewers look for by level

Follow-up questions

What if we run in two regions?

Give each region — say Mumbai with the primary database and Hyderabad with read replicas — its own cache fleet, and keep reads local. The trap is invalidation in the replica region: if the delete reaches Hyderabad before the replica has the new row, a reader there refills the old row. Facebook runs its invalidation daemons on the replica databases too, so a delete is issued only after its data has arrived. For a user who writes from Hyderabad, Facebook first sets a remote marker; a later miss that finds it reads from the primary region, trading latency for freshness. For computed data with no database, replicate the cache itself: EVCache puts only the key on Kafka, and a relay copies the value to other regions, with p99 under a second for most caches. More in multi-region and active-active.

What if a team wants to use the cache as its database?

Say no: items can be evicted, expired or lost in a failover at any moment. Some teams do keep data with no other home — Netflix precomputes recommendations into EVCache, Facebook stores machine-learning results in memcache — but only because it can be recomputed. Data that must survive belongs in a key-value store, with the cache in front.

What if a namespace’s working set is far bigger than its RAM budget?

Move the values, not the keys, to flash. Memcached’s extstore keeps keys and metadata in RAM and values on NVMe. Netflix measured RAM reads rarely above 1 µs and SSD reads of 100–500 µs, which still fits a cache with a roughly 1 ms latency target; after moving to extstore, most of its clusters were sized for network throughput rather than storage. It suits large, warm values such as recommendation lists, not the hottest small keys.

What if a deploy changes the format of cached values?

Never flush a namespace to “clean up”: at 450k misses a second already, emptying the catalogue pool would multiply database load. Bump the namespace’s generation instead — catalog:v7: becomes catalog:v8: — so new code reads and writes new keys while old keys age out through TTL and eviction. Roll out gradually, and expect the hit ratio for that namespace to dip while v8 fills, so do it off-peak, not on sale day.

What if one tenant floods the shared pool?

The sidecars meter every namespace’s ops/s and bytes/s. One over its limit is throttled — its callers see errors and treat them as misses, which protects other tenants but loads its own database — then alerted and moved to a dedicated pool. Big tenants shouldn’t share at all. See noisy neighbours and fairness.

How to say it in the interview

“I’ll design a shared in-memory cache, Memcached- or Redis-like, that about 200 teams put in front of their databases: 10 million operations a second at peak, mostly reads, half a millisecond at p50 and 2 at p99, a 95% hit ratio — and the cache may lose anything but must never take a database down.

Sizing: 25 TB of unique data plus second copies for critical namespaces is 30 TB — 300 nodes at 100 GB each. Operations would need only 50, so memory is the constraint and the spare CPU absorbs skew.

Keys map to 16,384 hash slots, and a config service maps slots to nodes. A sidecar on every host routes each key straight to its node, cutting connections per node from 40 thousand to 5 thousand without a network hop. Adding a node moves about 0.4% of keys.

Teams use cache-aside: read, on a miss load from the database and fill; on a write, commit then delete. Leases stop the stale-set race and stampedes — one fill per key, fleet-wide — and a CDC pipeline tails the database log and deletes changed keys in every zone within a second. Every key has a TTL as a backstop.

Hot keys like a live score get a one-second near cache in the sidecar plus a few copies, turning a million reads a second into a few thousand. Separate pools stop one team’s churn evicting another’s data. When a node dies, its traffic goes to a small gutter pool instead of rehashing onto neighbours, and expensive-miss pools keep a replica in another zone, with recent deletes replayed after failover.”

Concepts used in this design

• Caching 101 — hit ratio, TTLs and why a cache is not a source of truth.
• Caching strategies: cache-aside, read-through, write-through — why a shared platform uses cache-aside.
• Distributed caching — spreading a cache over many nodes.
• Cache eviction policies — LRU, LFU, FIFO and TTL, compared.
• Hot keys, cache stampede and invalidation — the three failure patterns behind deep dives 2 to 4.
• Consistent hashing — the ring, virtual nodes, and why only 1/(N+1) of keys move.
• Redis — hash slots, eviction policies and client-side caching.
• Change data capture — turning the database’s log into invalidations.
• Data replication — why asynchronous replicas can lose the last writes.
• Strong vs eventual consistency — the consistency model the cache offers.
• Multi-region and active-active — regional caches and cross-region invalidation.
• Scaling reads — where a cache fits among read-scaling tools.
• No caching — the anti-pattern this whole platform exists to fix.
• Noisy neighbour — hot keys and greedy tenants on shared nodes.
• Control plane vs data plane — keeping configuration off the request path.

References and further reading

1. Scaling Memcache at Facebook (Nishtala et al., NSDI 2013)usenix.orgLook-aside caching with delete-on-write, leases against stale sets and thundering herds, pools, the gutter pool, mcrouter, mcsqueal invalidation, regional pools, remote markers and production numbers.
2. Redis Cluster specificationredis.io16,384 hash slots, CRC16 keys, hash tags, MOVED and ASK redirects, slot migration, failure detection and asynchronous replication.
3. Key eviction (Redis documentation)redis.iomaxmemory, the eviction policies, sampled (approximated) LRU and LFU with Morris counters and decay.
4. Consistent Hashing and Random Trees (Karger et al., STOC 1997)cs.princeton.eduThe original consistent hashing construction: buckets and items on the unit interval, several points per bucket, and monotonicity when buckets are added.
5. Caching for a Global Netflix (Netflix Technology Blog)netflixtechblog.comEVCache scale, writes to every zone’s copy, and cross-region replication through Kafka that carries keys, not values.
6. Evolution of Application Data Caching: From RAM to SSD (Netflix Technology Blog)netflixtechblog.comA 1 ms latency target with a 20 ms default timeout, memcached extstore on NVMe, and warming new clusters by dumping keys.
7. A large scale analysis of hundreds of in-memory cache clusters at Twitter (Yang et al., OSDI 2020)usenix.orgReal key and value sizes, mandatory TTLs, 49-byte item metadata, slab calcification, and FIFO versus LRU.
8. Memcached wiki: user internalsgithub.com1 MB pages, slab classes and chunk sizes, wasted bytes per item, and how memcached decides what to evict.
9. Optimal Probabilistic Cache Stampede Prevention (Vattani et al., VLDB 2015)cseweb.ucsd.eduWhy stampedes happen and XFetch, a one-line probabilistic early refresh.
10. Client-side caching reference (Redis documentation)redis.ioServer-assisted near caches: key tracking and broadcasting modes that push invalidations to clients.