Skip to content

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
Asked at
Practice this question

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

AskWhy it mattersA 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.

The requirements menu

RequirementScopeWhy

Set, get and delete key-value pairs

Core

The whole product: three operations on one key each, which is what lets the keys be spread across machines without coordination.

Set an expiry time on each key

Core

Callers decide how long a value may be trusted. It forces each node to track a deadline per entry and to drop entries whose deadline has passed.

Evict the least recently used keys when memory is full

Core

Memory is finite and the cache is allowed to forget. The policy decides what each node tracks on each read and write.

Fetch many keys in one call

Optional

Worth taking if time allows: a page can need many keys, and a multi-get lets the client library fan the request out to the owning nodes in parallel and merge the answers. Leave it if the interviewer wants depth on placement or hot keys instead.

Atomic increment on a numeric value

Optional

A real need for counters and rate limits, and cheap on a single node because one node owns the key. Mention it, then park it unless the interviewer brings up a key that takes constant writes.

Report hit rate, evictions and memory per node

Optional

You run this for the rest of the company, so you need to see when a node is full or a key is hot. Name the counters and where they go; the dashboard itself isn't part of this round.

Namespaces or quotas per team

Out of scope

Prefixing keys by team is a naming convention, and quotas are a separate control plane. Say the key prefix is enough for now and move on.

Conditional writes such as compare-and-set

Out of scope

Useful against lost updates, but it pulls in versioning per entry. Set, get and delete cover this question.

Keeping data across restarts

Out of scope

The database behind the cache is the source of truth, so a lost node costs a refill, not lost data. Writing each change to a node's disk adds latency for nothing the requirements ask for.

Strong consistency

Out of scope

Keeping copies in step on each write means waiting for acknowledgments, which fights the latency target. Eventual consistency is the stated bar.

Queries and transactions

Out of scope

Operations that touch several keys at once would need keys co-located or a coordinator across nodes. Single-key operations are what let the design stay simple.

Letting users configure the cache size

Out of scope

Capacity is set by the operators from the data size and the memory per node, not by callers.

Non-functional requirements

RequirementWhat 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

QuantityWorkingResultWhat 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

EntityWhat 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

EndpointNotes

GET /cache/{key} → value or miss

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.

PUT /cache/{key} { value, ttl_seconds }

Stores the value and records the deadline as now plus ttl_seconds. A set of an existing key replaces the value and pushes the entry to the front of the recency list. If the node is full, entries come off the tail first. The node copies the write to its follower without waiting for it.

DELETE /cache/{key}

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

missget, setServiceCache node AMap + LRU listDatabase

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.

hashhot keysasyncasyncchangeshot listmissServiceClient libraryHash ringLocal cacheCache node ACache node BMap + LRU listFollower AFollower BCoordinationserviceHot key detectorDatabase
The whole design

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?

A concept that helps here: Consistent hashingA concept that helps here: Sharding and partition keysA concept that helps here: Leader election and failover

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?

A concept that helps here: Hot keys and hot partitionsA concept that helps here: Replication and read replicasA concept that helps here: Caching strategies

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: Cache evictionA concept that helps here: Cache invalidation and TTLs

Concepts this guide uses

Sources

  1. Wikipedia: Consistent hashing
  2. timilearning: MIT 6.824 lecture 16, Scaling Memcache at Facebook (lecture notes)
  3. Redis documentation: Replication
  4. Redis documentation: Redis cluster specification
  5. Apache ZooKeeper: Programmer's Guide
  6. Redis documentation: Key eviction
  7. Redis FAQ: What are the impacts of the Redis expiration algorithm?
  8. Redis documentation: Client-side caching reference
  9. Amazon ElastiCache Well-Architected Lens: Performance efficiency pillar
  10. Momento: Horizontal scaling with ElastiCache Redis, hot keys and shards
  11. Interview Cake: LRU cache data structure and implementation
Sign in to report a mistake