Designing a distributed cache

The problem: Snip's cache is now a system of its own

Snip's four Redis nodes from 05.03 Consistent hashing were enough for 100,000 cache reads a second. A year later the targets are:

• 300,000 reads a second at peak, almost all redirects, plus a few thousand writes (new links, edits, deletes).
• 40 million links in the working set.
• p99 under 2 ms for a cache read, so the cache stays far faster than the database.
• Losing a node mustn't overload Postgres, which is sized for about 1% of reads.

Treat it like any design (01.07 The design framework, step by step): estimate, choose how keys are placed and found, then decide what happens when things fail.

Sizing

Memory. A cached link is a key, a URL and the cache's own bookkeeping per entry: say 500 bytes in all. 40 million × 500 bytes is 20 GB. Leave room for growth and for memory fragmentation, and plan for about 32 GB of primaries.

Throughput. Snip's load tests show a node comfortably serving 50,000 reads a second at the latency target. 300,000 ÷ 50,000 is 6 nodes at full load. To leave headroom, and so that losing one node moves only a small share of keys, Snip runs 12 primaries of about 4 GB each, each with one replica.

Running more, smaller nodes has a real benefit: when one fails, a twelfth of the keys are affected, not a quarter.

Finding the right node

Every request must reach the node that owns its key. There are three ways to arrange that:

Redis Cluster is the third kind. It divides the key space into 16,384 hash slots: a key's slot is CRC16(key) mod 16384, and each primary owns a range of slots. A client that asks the wrong node gets -MOVED 3999 10.0.0.7:6379 and updates its map. While a slot is being moved to another node, the client may get ASK, meaning "try that node for this one request". Slots are fixed logical partitions, exactly like Snip's 256 logical shards (05.04 Rebalancing without downtime): adding a node moves whole slots, not individual keys.

Hash tags let you keep related keys together: only the part inside {...} is hashed, so {x7Kp}:url and {x7Kp}:owner land on the same node and can be read in one command. Use them sparingly, since one popular tag puts all its keys on one node.

Replicas and failover

Each primary copies its writes to a replica asynchronously. If a primary dies, the replica is promoted. Because copying is asynchronous, the last few writes before a crash can be lost, and the Redis Cluster specification says so plainly: there are "small windows where acknowledged writes can be lost".

For a cache, that's acceptable: the database is the source of truth, and a lost entry is just a miss. A lost delete is worse, since the promoted replica may still hold a value that was invalidated. That's another reason every entry has a TTL (06.04 Invalidation and staleness).

Replicas can also serve reads, which adds read capacity, at the price of reading slightly behind the primary.

When a node fails

Without a replica, or during the seconds before a replica takes over, a node's keys are unreachable. What should clients do?

• Treat it as a miss and go to the database. Simple, but a twelfth of Snip's cached traffic, 25,000 reads a second, suddenly hits a database sized for 3,000. It can cascade.
• Rehash onto the remaining nodes. With a ring, the failed node's keys spread to its neighbours, which start cold. A single hot key can account for a big share of a node's traffic, so the neighbour that inherits it can be overloaded in turn.
• Send them to a small spare pool. Facebook's answer, the Gutter pool: about 1% of servers, idle normally, that take over failed servers' requests with short-lived entries. Misses there go to the database once, and then become hits (below).

Snip uses replicas for failover, and limits the misses any one app server can send to Postgres at once (03.11 Backpressure and load shedding), so a slow failover degrades latency instead of taking the database down.

The client matters as much as the servers

• Timeouts. A cache read that takes 50 ms is worse than none. Give cache calls a tight timeout (a few milliseconds), and treat a timeout like a failed node, not as a reason to wait.
• Batch, but watch the tail. Reading 20 keys in one multi-get is far cheaper than 20 round trips, but a request that waits for 10 nodes is as slow as the slowest of them (03.12 Tail latency and why p99 matters).
• Hot keys. Spread them with a small in-process cache and suffixed copies (05.02 Hot partitions and celebrity keys).
• Coalescing. Collapse concurrent misses for the same key (06.05 Stampedes and request coalescing).

More than one region

If Snip serves from Virginia and Frankfurt, each region gets its own cache, filled from its own database replica, because a cache read across an ocean costs more than a local database read. The hard part is invalidation: an edit in Virginia must delete the entry in Frankfurt's cache too, and not before Frankfurt's database replica has the new row, or a miss there will refill the old value. Driving deletes from each region's own replication stream solves both: a region deletes a key when its database applies the change (06.04 Invalidation and staleness).

Try it

Recap

Interview questions