System Design: Distributed Cache (Walnut Cache: Slots, Replication, Failover, Eviction)
Goal: Design Walnut Cache, our own distributed in-memory cache. It holds about 530 GB across many servers, serves a million operations a second, and answers a read in under a millisecond.
It keeps serving when a server or a whole data center fails. Apps use it as a fast copy of their data, never the only copy.
1. What We Are Building
🔒 Premium section
2. Requirements and Scale
2.1 What Walnut Cache Must Do
Apps reach Walnut Cache through the Client Library, so some requirements are about the library.
- Working with keys. Get a value, or a clear miss. Set a value with an optional TTL, or only if the key is absent. Delete. Get many keys in one call. Increment a counter in one step. Set or change a TTL. Run a short script on the node as one step.
Running the cluster:
- Memory limit with eviction. Each node stays under a set memory limit. When it's full, it drops the least useful keys, which is called eviction.
- Sharding. Split the keys across many primaries. Each primary's part is a shard.
- Replicas and automatic failover. Keep a copy of each shard on another node, and promote it with no person involved when its primary dies.
- Live scale-out. Add or remove nodes while serving, moving only the keys that must move.
For apps and operators:
- Client routing. The library sends each command to the key's owner, and follows along when keys move or a node fails.
- Auth. Only known clients may connect, and each may touch only the keys it's allowed to.
- Metrics. Each node reports hit ratio, latency, memory, evictions and its busiest keys.
2.2 How Well It Must Do It
Two terms first. We measure latency as p99: 99 requests in 100 finish faster than this. And a zone is a separate data center inside one region, with its own power and network.
- A read in under 1 ms at p99, measured at the app server, network included.
- 1 million operations a second at peak, such as during a holiday sale.
- About 530 GB of data in memory. The store's popular data must fit, or the hit ratio falls.
- Survive one node, and one whole zone, with keys served again within seconds from a warm copy.
- No single point of failure. No one node, link or coordinator can stop the cluster.
- Bounded loss on failover. About a second of writes after a crash, a few seconds in a network split (section 9). This is the price of copying in the background.
- Live resharding. Moving keys between nodes must not cause downtime or a wave of misses.
2.3 The Consistency We Promise
What can a client count on after a write? Here are our promises, strongest first.
- One key, one owner, one order. Each key has one primary at a time, and that primary runs commands one at a time. So every single-key command is atomic: it happens fully or not at all, and nothing runs in its middle. All writes to one key happen in one order.
- You see your own writes on the primary. While a primary lives, a client that reads from it sees its own writes.
- Copies may lag, but not forever. A replica applies each write a little after its primary, usually well under a second. A Local Cache copy can be up to 5 seconds old. Apps read copies only where slightly old data is fine.
- A failover can drop writes that were already acknowledged. The primary replies OK before its replica has the write. If the primary dies in that gap, the promoted replica never saw it.
So Walnut Cache is not linearizable. That would mean every read sees the latest acknowledged write, as if there were one copy that never failed. We give it up to stay fast and keep serving.
A client that cares more can follow a write with a wait-for-replica command. The primary then holds its reply until a replica confirms it has the write, or a timeout passes.
That lowers the risk. It doesn't remove it. Others can read the write before the replica has it. And after a timeout, the write stays on the primary, unconfirmed, and can still be lost.
2.4 The Numbers
- Operations. At peak the store sends 1 million operations a second. About 700,000 are reads. The other 300,000 are writes: copies stored after a miss, deletes after the database changes, and cache-only data such as sessions and counters.
- Data. The store keeps about 250 million keys, with an average value of about 2 KB. That's 500 GB of values. Each key also has a fixed cost for its name and its table entry, about 100 bytes, plus a little for its TTL. That brings the total to about 530 GB. Section 6 shows where those bytes go.
- Hit ratio. The hit ratio is the share of reads that find a copy. The store aims for 95%. Then 5 reads in 100 miss, which is about 35,000 database reads a second. A bad hour can drop the ratio to 90% and double that. So the store sizes its database for about 70,000 reads a second, and alerts the on-call engineer below 90%.
So 530 GB must be split across many primaries (section 2.5). And an empty cache is the real danger. If every copy vanished, all 700,000 reads would hit a database built for a tenth of that. So failover must bring back a warm copy.
For measured numbers, we ran an existing open-source in-memory cache server that uses this same design, as a stand-in for one Cache Node. It ran on a small shared machine, so its numbers are floors (section 21).
2.5 Sizing the Cluster
Memory sets the count. We give each primary about 22 GB of data, under a memory limit of 25 GB, where eviction starts, on a 32 GB machine. The last 7 GB is spare room for copying data to a new replica and for memory the node can't reuse (section 6.8).
530 GB in 22 GB pieces gives 24 primaries. Each has one replica, so Walnut Cache runs 48 Cache Nodes.
Why not fewer, bigger shards? Copying a 22 GB shard to a new replica already takes a few minutes, and the shard has no spare copy the whole time. A bigger shard takes longer to copy, and the node pauses longer when the copy starts (section 16.6).
CPU fits, with care. At peak each primary takes about 42,000 operations a second, 1 million divided by 24. The stand-in server did about 106,000 reads and 89,000 writes a second with no pipelining. It ran on a small shared machine, so that is a floor, not a ceiling.
We plan each primary at no more than half of that floor, because latency climbs well before a single thread is fully busy. Our mix is mostly reads, so half the floor is about 50,000 operations a second. Our 42,000 sits under that, but not by much.
CPU alone would need only 1 million divided by 50,000, so 20 primaries. Memory needs 24, so memory sets the count, and CPU is the next limit we would hit. The floor was also measured without TLS, the encryption on each connection, so we measure real machines with TLS before adding load.
2.6 Out of Scope
- Durable storage of record. Walnut Cache is never the only copy of data that matters. Disk, if used, only speeds up restarts (section 8).
- Transactions across nodes. A script can change several keys as one step only when they all live on one node.
- Queries. No search and no secondary index. You ask by exact key.
- One cluster across regions. Each region runs its own cluster (section 17).
3. The API
🔒 Premium section
4. From One Node to a Cluster: The High-Level Design
🔒 Premium section
5. Key Design Choices
🔒 Premium section
6. Deep Dive: Inside One Cache Node
🔒 Premium section
7. Deep Dive: Splitting Keys Across Nodes
🔒 Premium section
8. Deep Dive: Replication and Persistence
🔒 Premium section
9. Deep Dive: Membership, Failure Detection and Failover
🔒 Premium section
10. Deep Dive: The Client Library
🔒 Premium section
11. Deep Dive: Scaling Out and Resharding
🔒 Premium section
12. Deep Dive: Hot Keys, Big Keys and Stampedes
🔒 Premium section
13. How Applications Use Walnut Cache
🔒 Premium section
14. Capacity at Scale
🔒 Premium section
15. What Happens When Each Part Goes Down
🔒 Premium section
16. Bottlenecks
🔒 Premium section
17. Multi-Region
🔒 Premium section
18. Running It
🔒 Premium section
19. Trade-offs
🔒 Premium section
20. In the Interview
🔒 Premium section
21. How We Measured
🔒 Premium section
22. Further Reading
🔒 Premium section
Explore the Technologies
🔒 Premium section