Hands-on design challenge

Challenge 14: A distributed cache

The situation

Build the cache tier itself. Your application servers call it directly through a client library, and every read the cache cannot answer goes to the backing database behind it, which can serve only so many. Most reads are for popular keys, which the cache keeps, so a cache that has all its nodes answers nearly all of them. A cache node can fail at any time, and the database must keep up even then. At the start, keys are placed on the nodes by hash mod N.

Traffic

50,000 requests a second.

OperationShareSteps
Read90%Read data
Write10%Write data
  • Read90%Read data
  • Write10%Write data

Data

A cache answers 95% of the reads that reach it. A read the cache misses goes to the backing database, 10 ms away.

What you are proving

Losing one cache node should cost only that node's share of the hits: how keys are placed on the nodes decides whether a failure loses a small share of the cache or nearly all of it at once.

Rules

  • A CDN does not help here.The callers are your own application servers, which call the cache directly; a CDN serves users from copies near them and has nothing to offer servers that call a cache.
  • The cache is the whole design: the calling servers and the backing database are given.The challenge is the cache tier itself, so every read the cache misses counts against the backing database you were given, even if you draw another store behind the cache.

Builds on

Further reading: System Design Interview, volume 1, chapter 5.

Targets

  • Serve all 50,000 requests a second
  • p99 at most 20 ms
  • At least 99.99% available, with no single point of failure
  • At most 1,200 USD a month
  • Any tier loses one instance: nothing dropped, p99 holds, misses stay within their limit, no tier over 80% busy
  • At most 7,000 misses a second reach the backing store

Hints