Design a distributed cache
How do you cache across many machines when everyone wants the same key at once?
Why was one cache machine overloaded while the others sat idle?
By October the delivery service runs in Pune, Mumbai and Nashik. The menu cache from lesson 1.2 is now six Redis machines, and the cache client spreads keys over them with the hash ring.
Then the app gains a strip at the top of every screen: “Today’s specials”, built from all three cities’ kitchens. It is one key, specials:today, and every screen reads it.
At 12:30 the next day the pages start timing out. The dashboard shows something odd. Five cache machines are at about a third of what they can serve. The sixth, cache-4, is at its limit, its network card full, and requests to it time out. The app does what it was built to do when the cache fails: it asks PostgreSQL. PostgreSQL’s CPU goes to 100%. Yet the cluster as a whole is at about 60% of what it can serve, so it is not obvious why anything should be overloaded.
That night six more machines are added. The next day at 12:30 it happens again: cache-4 is at its limit, and the other eleven machines are lightly loaded.
A parcel sorting station can have the same problem. Suppose each sorter handles the boxes for one office building, and half of all the boxes in Pune are for one building. Hiring more sorters for the other buildings does not help, because the one sorter for that building still has half of all the boxes.
Three things are wrong at once, and it helps to separate them before reading on. A key that every screen reads lives on one machine, and adding machines does not move it. Every time the cache is slow for a minute, the app sends those reads to the database instead, and the database is overloaded. And the whole city wants the same thing at the same minute, yet it is kept in only one place.
Pause and predict Six machines became twelve, and cache-4 is still at its limit. What would spread specials:today?
What must never go wrong?
The System Context diagram shows the cache tier as a system that the ordering platform depends on, with the databases behind it as the source of truth.
Database protection comes first in the table, because the database must keep working through the minutes when the cache is slow or down.
Core entities, in two minutes
A cache entry (key, value, TTL, version), a shard that owns a range of keys, the source record it copies (a kitchen’s menu, the day’s specials), and a hot-key rule that marks a key for special treatment.
The estimate that changes the design
About 2 million keys of about 2 KB each, 150,000 reads a second at 12:30, and one cache machine serves about 40,000 reads a second for these value sizes.
Pause and predict Which number decides the shape of this cache cluster?
The obvious cluster, and how it breaks
The first cluster is what lesson 1.2 ended with: a ring of shards, each key on the first shard clockwise from its hash, and the app server falling back to the database when the cache does not answer.
Run it at 12:30, then add shards, as happened that night.
Pause and predict With copies off and no near cache, double the shards from 6 to 12. Does the hot shard come under its 40,000 reads a second?
A mental model
Three questions organise the whole design. How are keys placed on machines, so that the spread is even and survives machines being added or removed? What happens to a key that is too hot for any one machine? And when a machine dies, who refills its keys, and how much extra work does that put on the database?
- Hot key
- One key that receives a large share of all requests, enough to overload the one machine that holds it.
- For example:
specials:today, read by 40% of all cache reads at 12:30: 60,000 a second on a machine that can serve 40,000.
Copies in the cluster, or a near cache in every server?
Both tools reduce the load on the hot key’s shard. The question is which one should be the default.
Invisible copies are a real risk, and that is why the near cache holds only keys marked hot, for one second, and only display data. Copies divide the hot key’s load, and that load still grows with traffic; the near cache caps it at one read per app server per second. Copies remain the right tool for hot keys that must never be a second out of date.
What to remember
- Sharding spreads keys evenly and leaves traffic where it falls. A key hotter than one machine stays on one machine however many machines you add.
- Route by slot or ring so that adding a machine moves a few keys; Redis Cluster uses 16,384 hash slots and hash tags to keep related keys together.
- Cool a hot key with copies on several shards, which divides its load, or a short-TTL near cache, which caps its load at one read per app server per TTL. Decide how stale each copy may be.
- Control refills: leases give one reader per key the right to rebuild, a gutter catches a dead shard’s keys, and a cold cache is warmed before it takes the rush.
- Watch the busiest shard, because the cluster average hides it, and that shard’s timeouts decide how much load falls on the database.
Sharding spreads keys evenly, and a key hotter than one machine has to be stored in more than one place.
In the real world
The simulator places ordinary keys evenly and charges each shard by reads alone. Real clusters also suffer from big keys (one huge value that is slow to send and to evict), from network limits that arrive before CPU limits, and from refills that slow the database and so widen the window in which more readers miss. Facebook’s paper describes a further layer left out here: many frontend clusters in a region, each with its own caches, kept consistent by invalidations read from the database’s commit log.
That last idea, turning the database’s log into a stream other systems follow, returns in the outbox and change data capture lesson (lesson 6.5). For now the specials strip loads in a millisecond at 12:30, and losing a cache machine at lunch costs the database a few hundred queries.