Infrastructure · Intermediate

Distributed cache

Sharded memcached behind consistent hashing, with cache-aside reads, delete-on-write and a gutter pool.

Every part, and why it is there

Users

Page views that each need dozens of small pieces of data. Most of those reads repeat, which is what makes caching pay off.

Load balancer

Spreads requests over the web tier. Any web server can serve any user because no state lives on them.

Web servers

Use cache-aside: read the cache first; on a miss, read the database and fill the cache. On a write, update the database and then delete the cached key rather than updating it.

Cache router (consistent hashing)

Maps each key to a shard with consistent hashing, so adding or losing one shard remaps only about 1/N of keys instead of nearly all of them. It also batches many small gets into one round trip.

Cache shard 1

Holds a slice of the keyspace in RAM and evicts the least recently used items when full. A shard knows nothing about the others.

Cache shard 2

Another slice. Very hot keys (one celebrity profile) can overload a single shard, so those are often replicated or cached in the web server’s memory too.

Cache shard 3

And another. Shards are cheap and interchangeable; losing one only costs some extra database reads.

Gutter pool

A small standby pool. When a shard dies, its traffic goes here with short expiry instead of flooding the database while the ring rebalances.

Database

The source of truth. Sized for cache misses, not total traffic: a 95% hit rate means it sees only 1 read in 20.

Invalidation events

Every write publishes “key X changed”. Fan-out delivers it to every region and cluster that may hold a copy.

Invalidation daemon

Deletes the changed keys through the router. Deleting is safe to repeat and to reorder, which updating a value is not.

Asked in interviews at

  • google
  • microsoft
  • meta
  • amazon

Concepts used here

  • Caching: Keep recent answers in memory so the database only does each piece of work once. Then deal with the three ways that goes wrong: stale data, a full cache, and a stampede.
  • Bloom filter: Answer “have I seen this before?” for a hundred million names in about 10 bits each. It never wrongly says no.
  • Consistent hashing: Why adding one cache server can take a database down, and the ring that makes it move only about 1 key in 5 instead of 4 in 5.

Learn more

All system design examples