Distributed Cache Design: Sharding, Stampedes and Staleness

A database answers a query in milliseconds and handles a limited number per second. An in-memory cache such as Redis or Memcached answers in well under a millisecond and handles many times more. If most reads repeat, a cache in front of the database cuts latency and lets the database serve far more users.

One node eventually runs out of memory or network capacity. A distributed cache spreads keys across several nodes. That raises capacity, and it also raises the questions this article is about: which node holds which key, what happens when nodes change, and what happens when a popular key disappears.

Cache-aside (lazy loading): the application checks the cache first. On a miss it reads the database, writes the result into the cache with a TTL, and returns it. On a write it updates the database and then deletes the cached key, so the next read repopulates it. This is simple and the cache only holds data that was actually requested.

Write-through writes to the cache and the database together, keeping them in step at the cost of slower writes. Write-behind acknowledges after writing to the cache and flushes to the database later, which is fast but can lose data if the cache node fails first. Most applications use cache-aside with deletion on write. Deleting rather than updating the key avoids a race where two concurrent writers leave the older value in the cache.

The obvious way to choose a node is hash(key) % N. It works until N changes. Adding a fifth node to four makes the result change for most keys, so most of the cache is suddenly in the wrong place and every one of those reads becomes a miss that hits the database.

Consistent hashing places both nodes and keys on a circle. A key belongs to the first node clockwise from its position. Adding a node only takes over the keys between it and its predecessor. Each physical node is given many points on the circle (virtual nodes) to even out the load.

I measured it with 20,000 keys, 4 nodes growing to 5, and 100 virtual nodes per node:

Roughly one fifth of the keys moved with the ring, which is the minimum possible, against four fifths with modulo. In production that is the difference between a small blip and a database flooded with misses.

Suppose a very popular key expires. In the next few milliseconds, hundreds of requests all miss and all query the database for the same value. I simulated 50 threads requesting one missing key with a 50 ms database call:

The database was called 50 times. The fix is single-flight: only one request recomputes and the rest wait for its result.

With this, the same test made 1 database call. The re-check after taking the lock is essential, because the previous holder has probably filled the key. In a distributed setting the lock is a short-lived key in the cache itself (set only if absent), or a lease from the cache. Other defences are refreshing popular keys before they expire, and serving the stale value for a moment while one request refreshes it.

If you warm the cache with a thousand keys and give them all a 300-second TTL, they all expire in the same second and the database takes a thousand queries at once. Add a random offset. In a check with 1,000 keys, a fixed 300-second TTL put all 1,000 expiring in the same second, while 300 + random(0, 60) spread them so that at most 24 shared any one second. It costs one line of code.

Consistent hashing balances keys, not traffic. One celebrity profile or one product on sale can send a huge share of requests to a single node. Remedies include a small local in-process cache in front of the shared one for the hottest keys, replicating a hot key under several names, and monitoring per-key load.

When a node dies, its keys are remapped and become misses. Replicas (a primary and a copy) soften this. Treat the cache as disposable: the system must stay correct, only slower, if the whole cache is empty. If the database cannot survive a cold cache, the design has a hidden dependency on it.

Size it from the working set, not the whole dataset. Eviction (commonly least-recently-used) removes cold items when memory fills.

A cache is a copy, and copies go stale. The TTL is the upper bound on how long a missed invalidation can persist. For data like a product description, minutes of staleness are fine. For an account balance, caching may be inappropriate or need strict invalidation. A race remains even with delete-on-write: a reader can fetch the old value from the database, a writer then updates the database and deletes the key, and the reader finally writes its old value into the cache. A short TTL bounds the damage. State the freshness you promise (for example, "up to 60 seconds old") as part of the design.

Q: Why consistent hashing instead of modulo?
A: Changing the node count moves only about 1/N of the keys with a ring, versus most keys with modulo.

Q: What is a cache stampede and how do you stop it?
A: Many requests recompute the same expired hot key at once. Use single-flight locking, early refresh, or serve stale while one request refreshes.

Q: Cache-aside versus write-through?
A: Cache-aside loads on demand and deletes on write. Write-through updates cache and database together for fresher data at the price of slower writes.

Q: Why delete rather than update the key on a write?
A: Concurrent writers can leave the older value in the cache. Deleting lets the next read fetch the truth.

Q: What are virtual nodes?
A: Many ring positions per physical node, which evens out the key distribution.

Q: How do you handle a hot key?
A: A local cache for it, replicas under several keys, and per-key monitoring.