Distributed Cache

Memcached / Redis tier

Design an in-memory cache tier spread over hundreds of servers that absorbs most of an application's reads, stays correct when data changes, and protects the database when things go wrong.

Overview

A distributed cache keeps recently used data in the memory of many servers, so most reads are answered in well under a millisecond instead of going to a database. The cache is not the source of truth: it may lose or evict anything, and the application must still work, only slower.

The hard parts are not the hash table on each server. They are spreading keys across hundreds of servers, keeping cached values in step with the database, and making sure the database survives the moments when the cache fails: a popular key expires, a server dies, or a new cluster starts empty. Facebook's 2013 paper on scaling memcache describes each of these problems at very large scale, and this problem follows its solutions. General caching strategies and stampede protection each have their own topics (Cache Read/Write Strategies, Cache Stampede, Consistent Hashing); this problem shows how they fit into one design.

Questions to ask first

What sits behind the cache? — A sharded SQL database and other services
How much traffic? — 5 million reads and 500,000 writes or deletes a second
How much data is hot? — About 20 TB of items, 500 bytes on average
How stale may a read be? — Seconds at most, and never stale forever
Who fills the cache? — The application, on a miss (look-aside)
One data center or several? — One region in depth; several regions as a follow-up

What you will be able to do

Explain look-aside caching and why a write deletes the cached key instead of updating it.
Spread keys over servers and route requests, with a client library or a proxy.
Stop thundering herds and stale sets with leases, and show the effect with numbers.
Handle a failed server, a cold cluster and invalidations at scale without overloading the database.
Choose an eviction policy and explain what the cache may lose.

Key concepts

Look-aside caching
Delete on write
Consistent hashing
Hash slots
Leases
Thundering herd
Stale sets
Eviction (LRU, LFU)
Gutter pool
Invalidation from the commit log

Functional requirements

get(key) returns the cached value or a miss
set(key, value, ttl) stores a value with an expiry
delete(key) removes a value; used whenever the database changes
Multi-get of many keys in one round trip
Automatic spreading of keys when servers are added or removed

Non-functional requirements

Cache get under 1 ms at p99 inside a data center (a target we chose)
Hit rate of 99% for the hot working set (a target we chose)
A cached value is never stale for longer than it takes an invalidation to arrive
A failed cache server must not multiply database load
Adding servers moves only a small share of keys

Interview questions

Walk me through a read and a write with a look-aside cache.
How do you stop a thundering herd when a hot key expires?
What is a stale set, and how do you prevent it?
How are keys spread over servers, and what happens when you add one?
A cache server dies. What happens to the database?
How do you keep several cache clusters consistent with one database?
Which eviction policy would you choose?
Why not just use the cache as the database?