Every design in this course has a box labelled “cache”. The URL shortener caches hot links; the rate limiter keeps its counters in Redis. Now we open that box. “Design a distributed cache” (or “design Redis”) is a frequently reported question at companies like Amazon, Microsoft and Netflix, and it teaches one of the most reused ideas in system design: consistent hashing.
Step 1 · Requirements
- Functional:
get(key),set(key, value, ttl),delete(key); items expire; old items are evicted when memory fills. - Non-functional: very low latency (about a millisecond); scales by adding servers; keeps working if one server dies; most reads should be hits.
- Clarify: it's a cache, not the source of truth. Losing some data is acceptable; the database still has it.
Step 2 · Estimates
- Traffic: say 1 million reads per second at peak with a 90% hit rate: 100,000 reads/s still reach the database, so the hit rate matters enormously.
- Data: 500 million hot items × ~1 KB = 500 GB. With 64 GB usable per server, that's about 8 servers, plus replicas.
- Throughput: one in-memory node can do on the order of 100,000 simple operations per second, so ~10–20 nodes cover the traffic comfortably.
Step 3 · API
get(key) → value | null (null = miss) set(key, value, ttl=300) → ok (expires after 300 seconds) delete(key) → ok (used to invalidate after a write)
Step 4 · Design
How the app uses the cache
| Pattern | How writes work | Good | Watch out |
|---|---|---|---|
| Cache-aside (lazy) | Write the DB, delete the cached copy | Simple; cache holds only what's read | First read after a change is a miss |
| Write-through | Write cache and DB together | Cache always fresh | Slower writes; caches unread data |
| Write-back (write-behind) | Write cache now, DB later in batches | Very fast writes | Data loss if the cache dies first |
| Write-around | Write the DB only; cache fills on read | Avoids caching write-once data | Recent writes always miss |
Inside one cache server: eviction
Memory is limited, so something must go. LRU keeps a hash map for O(1) lookups plus a doubly linked list ordered by use: every access moves an item to the front, and eviction removes from the back. Both are O(1), which is why “implement an LRU cache” is a classic coding question too. Add a TTL on every key so stale data disappears on its own.
Spreading keys across servers: consistent hashing
With many servers, every app server must agree which one holds user:42. The obvious answer, hash(key) % N, breaks badly when N changes. Try it:
🎮 Add or remove a cache server
Servers (click to add or remove):
Add server D. With hash % N roughly three quarters of all keys change servers, so almost the whole cache goes cold at once. With a hash ring only the keys in D's new slices move, about 1 in N.
On a hash ring, servers and keys are hashed onto the same circle; a key belongs to the next server clockwise. Each server is placed at many points (virtual nodes) so the slices even out. Adding a server only steals the keys just before its points.
import bisect
def fnv1a(key: str) -> int:
"""Small, stable 32-bit hash (same result in every language)."""
h = 2166136261
for b in key.encode():
h ^= b
h = (h * 16777619) & 0xFFFFFFFF
return h
class HashRing:
def __init__(self, vnodes: int = 100):
self.vnodes = vnodes # virtual points per server: spreads keys evenly
self.points = [] # sorted hash positions on the ring
self.owner = {} # position -> server name
def add(self, server: str):
for i in range(self.vnodes):
p = fnv1a(f"{server}#{i}")
bisect.insort(self.points, p)
self.owner[p] = server
def remove(self, server: str):
for i in range(self.vnodes):
p = fnv1a(f"{server}#{i}")
self.points.remove(p)
del self.owner[p]
def get(self, key: str) -> str:
"""Walk clockwise from the key's position to the first server point."""
i = bisect.bisect(self.points, fnv1a(key)) % len(self.points)
return self.owner[self.points[i]]
ring = HashRing()
for s in ["cache-A", "cache-B", "cache-C"]:
ring.add(s)
keys = [f"user:{i}" for i in range(10000)]
before = {k: ring.get(k) for k in keys}
ring.add("cache-D")
moved = sum(before[k] != ring.get(k) for k in keys)
print(ring.get("user:42"))
print(f"moved {moved} of {len(keys)} keys") # about 1 in 5 keys move; with hash % N it would be ~3 in 4Step 5 · Scale and reliability
- Replication: give each shard a replica on another machine; if the primary dies, the replica takes over (Redis Sentinel or Redis Cluster handle this).
- Hot keys: one key (a celebrity, a viral product) can overload one server. Copy it to several servers, keep a tiny in-process cache in app servers, or split it as
key#1…key#10. - Cache stampede: when a hot key expires, let one request rebuild it while others wait or get the old value; refresh popular keys early; add random jitter to TTLs.
- Invalidation: Phil Karlton famously joked that the two hard things in computer science are cache invalidation and naming things. Delete on write, keep TTLs as a safety net, and accept brief staleness where the product allows it.
- Cold start: a new or restarted cache is empty. Warm it with the most popular keys before sending full traffic.
- Monitoring: watch the hit rate, memory use, evictions and latency. A falling hit rate is an early warning.
🧠 PATH memory card
Remember the distributed cache design for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
A library with a round reading room. Popular books sit on shelves arranged in a circle; each book lives on the next shelf clockwise from its number. Missing books are fetched from the stacks downstairs, and books nobody has read lately are cleared away. Add a shelf and only the books just before it move.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Ask the shelf first; the ring picks the shelf”
- Ask the shelf first→Cache-aside: read the cache, then the DB on a miss
- The ring→Consistent hashing: key → next server clockwise
- Many spots per shelf→Virtual nodes keep the load even
- Clear old books→LRU eviction + TTL expiry
- Add a shelf→Only ~1/N of keys move
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Three servers on the ring.get(user:42)hashes to a point just before one of cache-A's points → ask cache-A → miss → read the DB →set(user:42, ttl=300). Next read: hit in ~1 ms. Add cache-D: only keys whose positions fall just before D's points move (about a fifth in our code), so most reads stay hits. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 8 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Follow-up questions interviewers ask
- “Redis or Memcached?” Memcached is a simple, multithreaded key-value cache. Redis adds data structures (lists, sets, sorted sets), persistence and replication, so it's also used for counters, leaderboards and queues.
- “What if the whole cache goes down?” The database gets every request. Protect it with rate limits and circuit breakers, and warm the cache back up gradually.
- “How do you keep cache and DB consistent?” Delete-on-write plus TTLs gives eventual consistency. For stricter needs, use change-data-capture from the DB to invalidate keys.
Where to go next
Caches make reads fast. Next, a system that's all about sending: millions of push notifications, emails and SMS a day, reliably and without spamming anyone: design a notification system.
Key takeaways
- ✓A distributed cache is an in-memory key-value store across servers; it's not the source of truth.
- ✓Cache-aside is the default: read cache, fill on miss, delete on write.
- ✓Evict with LRU (hash map + linked list) and expire with TTLs.
- ✓Consistent hashing with virtual nodes moves only ~1/N keys when servers change.
- ✓Plan for replication, hot keys, stampedes and invalidation.
Frequently asked questions
What is a distributed cache?
A distributed cache is a fast, in-memory key-value store spread across several servers, so it can hold more data and handle more requests than one machine. Applications check it before the database: if the data is there (a hit) it comes back in about a millisecond; if not (a miss) the app reads the database and stores the result in the cache for next time. Redis and Memcached are the best-known examples.
What is consistent hashing and why is it used?
Consistent hashing places both servers and keys on a circle of hash values; each key belongs to the next server clockwise. When a server is added or removed, only the keys in its slice of the circle move, about 1/N of all keys. With simple hash(key) % N, changing N moves most keys, which suddenly empties the cache and floods the database. Virtual nodes (many points per server) keep the load even.
What is the difference between cache-aside and write-through?
In cache-aside (lazy loading), the application reads from the cache and, on a miss, loads from the database and fills the cache; writes go to the database and the cached copy is deleted. In write-through, every write goes to the cache and the database together, so the cache is always fresh but writes are slower and the cache fills with data that may never be read. Cache-aside is the most common default.
What is a cache stampede?
A cache stampede (or thundering herd) happens when a popular key expires and thousands of requests miss at the same moment, all hitting the database to rebuild the same value. Fixes include letting only one request rebuild the value while others wait (a lock or request coalescing), refreshing popular keys shortly before they expire, and adding random jitter to expiry times so keys don't all expire together.
Which eviction policy should a cache use?
LRU (least recently used) is the usual default: when memory is full, remove the item that hasn't been used for the longest time. LFU (least frequently used) keeps items that are used often, which helps when a few keys are always popular. TTL (time to live) removes items after a fixed time, useful for data that goes stale. Real caches combine a TTL with LRU or LFU.
🧠 Quick check: distributed cache
1. You have 4 cache servers using hash(key) % 4 and add a 5th. Roughly what happens?
2. In cache-aside, what should happen when a user updates their profile?
3. Memory is full. Which item does LRU remove?
4. A celebrity's profile key gets 500,000 reads per second and overloads one cache server. Good fix?
Checking your access…