Design a distributed cache

Functional requirements

• CoreServices read an item by key, read many items at once for a page, store an item with a TTL of up to 24 hours, and delete an item after the data behind it changes.
• CoreA read of an item that isn’t cached, or has passed its TTL, returns a miss; the service then reads its own database and stores the result.
• CoreKeys are up to 250 bytes; most values are under 10 KB, and some are up to 1 MB.
• CoreThe platform team adds and removes cache servers while the cache is serving traffic.
• CoreAbout 200 teams share the cache, each with its own services and data.
• Below the lineData types beyond plain values, such as lists, sets and counters.
• Below the linePublish and subscribe.
• Below the lineSaving items to disk so a restarted server comes back full.
• Below the lineKeeping the caches of other regions in step (each region runs its own).
• Below the lineWriting through to the teams’ databases.Services own their databases and fill the cache themselves.
• Below the lineTransactions across keys.Keys live on different servers, and get-many covers a page.

Non-functional requirements

• ConsistencyAdding or removing a server, planned or not, must leave nearly every cached item where clients will find it.
• LatencyA read or a write takes at most about 2 ms at p99, measured from the app server.
• AvailabilityThe hit rate is about 95% today; if more than about one read in ten misses, the databases behind the cache fall over.
• AvailabilityA server fails about once a week, and a whole zone has gone down twice in three years; the cache stays available and full through both.
• ConsistencyThe cache holds copies and the databases stay the record: an item may be out of date for at most its TTL, and losing the last few seconds of writes in a failure is acceptable.
• Quality

Scale

From the briefNumbers here are given in the practice brief.

• ScaleAbout 4 million requests a second at the peak, 90% of them reads, from about 5,000 app servers in one region with three zones.
• ScaleAbout 6 TB of items at the peak, growing to about 10 TB within a year; each cache server has about 100 GB of memory for items.
• ScaleLoad tests show one cache server handles about 150,000 requests a second.
• ScaleThe busiest key can get about 300,000 reads a second during a flash sale; the homepage item gets about 50,000 a second.

Out of scope

• Out of scopeThe databases behind the cache, and how services query them.
• Out of scopeAuthentication internals: services already have credentials.
• Out of scopeServer hardware and the network between zones.
• Out of scopeThe services’ own business logic.