How to design a distributed cache
The first sections are free. The deep dives, level expectations and quiz are part of Pro.
On this page
- The problem
- Clarifying questions
- The requirements menu
- Non-functional requirements
- Estimates
- Core entities
- The API
- The high-level design
- What breaks first
- The deep dives
- Entity fields
- Spreading 1 TB over nodes
- Hot keys
- Eviction, expiry and invalidation
- Variants
- What each level is expected to show
- The 30-second answer
- Quiz
The problem
A distributed cache keeps key-value pairs in memory across a fleet of machines so that services read from it before they touch a database. Clients set, get and delete keys with an expiry, and a node that runs out of memory drops the entries it has gone longest without reading. The answer turns on two things: placing keys across machines so that adding one doesn't reshuffle them all, and keeping a single machine alive when one key draws a large share of the traffic.
Clarifying questions
| Ask | Why it matters | A typical answer |
|---|---|---|
How much data do we hold, and how many requests do we serve at peak? | The data size decides how many machines you need and whether you need to split keys at all; the request rate decides whether a single machine's network and CPU are the limit. | About 1 TB of data, 100,000 requests a second at peak, and gets and sets answered in under 10 ms. |
Does data need to survive a restart or a lost machine? | A cache that must keep data across restarts needs some durable record, such as a local log or a durable store behind it, and a different design. If losing a node just means readers reload its keys from the database, memory is enough. | No. Keeping data across restarts is out of scope: a node that dies loses its keys, and the readers refill them from the database. |
How fresh does a read have to be after a write? | Strong consistency across copies means waiting for acknowledgments on each write, which fights the latency target. Eventual consistency lets copies lag by a little. | Eventual consistency is acceptable. A reader may see an old value for a short time after a write, but the cache should stay up. |
Who sets the expiry, and what happens when memory is full? | An expiry per key chosen by the caller means the node must track one deadline per entry; a memory limit means a replacement policy, and the interviewer's checklist names which one. | The caller passes an expiry in seconds with each set. When a node is full it evicts the least recently used keys. |
Is it plain get, set and delete, or do we need queries, transactions or counters? | Multi-key operations and transactions force keys to be co-located or coordinated across nodes, which changes the placement scheme. | Plain get, set and delete on single keys. Queries and transactions are out of scope; a counter that is written constantly may come up as a twist near the end. |
Should I assume traffic is spread evenly across keys? | If a few keys take most of the reads, the machine that owns them is the bottleneck, and no amount of extra machines fixes that on its own. | Assume it isn't. When a post goes viral, one key can take a large share of all reads, and the design needs an answer for the machine that owns it. |
Non-functional requirements
| Requirement | What it forces |
|---|---|
Get and set answer in under 10 ms | One network hop from the caller to the owning node, and constant-time work on that node. The client library has to know which node owns a key without asking anyone on each request, and values stay in memory, not on disk. |
Hold 1 TB of data | A single machine with that much memory exists, but it leaves one point of failure and no room to grow, so this design splits keys across smaller nodes. With about 64 GB usable per node that's about 16 nodes before headroom, and about 20 with room to grow, each needing a follower if the data is to survive a lost machine. |
Serve 100,000 requests a second at peak | Spread evenly over 16 nodes that's about 6,250 requests a second per node. The pressure comes from skew: one hot key can send a large share of the peak to one node, so the design needs a plan for that node. |
Highly available; eventual consistency is acceptable | Each node gets a follower that is promoted when the node fails, and copies are made asynchronously so writes don't wait for them. On failover, the last writes that hadn't reached the follower are gone, and readers may briefly see an old value, which the requirements allow. |
Estimates
| Quantity | Working | Result | What it sizes |
|---|---|---|---|
Cache nodes to hold 1 TB | Assume about 64 GB of usable memory per node once the operating system and buffers are set aside. 1 TB ÷ 64 GB ≈ 16 nodes. Add about a quarter for growth and uneven slices: 20 nodes. Give each a follower: 40 machines, holding 2 TB of memory in total. | About 16 nodes bare, 20 with headroom, 40 machines with a follower each | The cluster size, and the point that half the fleet's memory is spent on copies that serve no reads unless you route hot-key reads to them. |
Requests per node on an even spread | 100,000 ÷ 16 nodes ≈ 6,250 requests a second per node; with 20 nodes, 5,000. | About 6,250 requests a second per node on 16 nodes | The per-node load if traffic were even, which is also the upper bound on database misses when one node restarts empty, until it warms. |
Keys that move when one node joins | Hash mod N, growing from 16 to 17 nodes: a key keeps its node when its hash mod 16 equals its hash mod 17, which happens for about 1 key in 17, so about 94% of keys move. On a hash ring, the new node takes about one share in 17, about 5.9% of keys. | About 94% of keys move with mod N; about 5.9% with a ring | The miss storm after adding a node: with mod N nearly the whole cache refills from the database; with a ring a small slice does. |
Load on the node that owns a hot key | As an example, say half of the peak asks for one key: 50,000 requests a second on one node, 8 times its even share of 6,250. Spread over three copies that's about 16,700 each; spread over all 20 nodes, about 2,500 each. | 50,000 requests a second on one node in this example; about 16,700 per copy with three copies | How many copies of a hot key you need, and why adding nodes without copying the key doesn't help. |
Core entities
| Entity | What it holds |
|---|---|
Entry | One cached value and the moment it stops being valid. |
Cache node | One machine's share of the keys, with the structures that make get, set and eviction cheap. |
Ring | The placement map: which machine owns which range of hash values. |
Client library | Code inside each calling service that knows the ring and talks to nodes directly. |
The API
| Endpoint | Notes |
|---|---|
| The client library hashes the key, finds its node on the ring and asks that node directly. A miss is a normal answer, not an error: the caller then reads the database and sets the key. An entry whose expiry has passed is treated as a miss and removed. |
| Stores the value and records the deadline as now plus |
| Removes the entry if present and succeeds either way, so callers can retry it after a database write without checking the result. Deleting rather than updating after a write leaves the next reader to refill from the database; a lease on that miss is what rejects a stale fill that raced with the delete. |
The high-level design
Step 1 of 4
One node with constant-time get, set and eviction
Start with a single cache node and the service that reads from it. The node keeps a hash map from key to entry, and each entry also sits on a doubly linked list ordered by last use. A get looks the entry up in the map and moves it to the head of the list; when memory is full, the node drops entries from the tail. Each entry carries its expiry, checked on read. On a miss the service reads the database and sets the key, and after a database write it deletes the key so the next reader refills it.
What breaks first
The deep dives
Spreading 1 TB over nodes. A terabyte of keys has to sit across many machines. Which machine does a key live on, what happens to the other keys when a machine is added, and what serves a machine's keys after it dies?
Hot keys. After a celebrity post, one key draws a large share of all reads and the machine that owns it slows down. What fails on that machine, what keeps it alive, and what does a reader see right after a write?
Eviction, expiry and invalidation. A node is full when a new key arrives, and a value that just changed in the database is still being served. What gets evicted, how do expired entries leave, and how does a changed value stop being served?
A concept that helps here: Request coalescing and leases
Concepts this guide uses
Sources
- Wikipedia: Consistent hashing
- timilearning: MIT 6.824 lecture 16, Scaling Memcache at Facebook (lecture notes)
- Redis documentation: Replication
- Redis documentation: Redis cluster specification
- Apache ZooKeeper: Programmer's Guide
- Redis documentation: Key eviction
- Redis FAQ: What are the impacts of the Redis expiration algorithm?
- Redis documentation: Client-side caching reference
- Amazon ElastiCache Well-Architected Lens: Performance efficiency pillar
- Momento: Horizontal scaling with ElastiCache Redis, hot keys and shards
- Interview Cake: LRU cache data structure and implementation