Caching, replication and sharding
Lesson 2 of 3
2Caching, replication and sharding
The big pictureMost apps read far more than they write. Every read that reaches the database costs. A cache answers from memory, replicas spread the reads, and sharding spreads the data itself when it no longer fits on one server.
What the picture shows: The read path stops at the first layer that has the answer. Writes always go to the primary, then get copied.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
In a café the menu does not change every minute, so you print it and hang it up instead of every customer asking the manager. That is the cache. When customers multiply you print copies for the tables: those are read replicas. But change a price and forget an old copy on one table, and a customer sees the old price: that is the invalidation problem.
Caching patterns: cache-aside (the app reads and fills), write-through (writes go to both), write-behind (write to the cache, the database later). Eviction: LRU, LFU and TTL. Invalidation on write is the hardest part, and a cache stampede is solved with a lock or early refresh. Read replicas: the primary writes and replicas follow with a delay (replication lag), so reading what you just wrote may need the primary (read-your-writes). Sharding: spreading rows across databases by a key; plain hash % N moves most keys when N changes, while consistent hashing moves only about 1/N. And CAP: during a network partition you choose consistency or availability.
Before You Start
⚖️Scaling
The previous lesson.
🍃NoSQL and Redis
The NoSQL lesson in the databases track.
The Core Idea
1An LRU cache yourself
LRU evicts the least recently used item when memory is full. OrderedDict makes it a few lines:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity, self.data = capacity, OrderedDict()
self.hits = self.misses = 0
def get(self, key, load):
if key in self.data:
self.hits += 1
self.data.move_to_end(key)
return self.data[key]
self.misses += 1
value = load(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)
return value
cache = LRUCache(capacity=2)
for product in ["latte", "mocha", "latte", "tea", "mocha", "latte"]:
cache.get(product, load=lambda k: f"{k} from db")
print("hits:", cache.hits, "misses:", cache.misses, "kept:", list(cache.data))2Read replicas and their lag
A user changes their name, then opens their profile at once, and the request goes to a replica the write has not reached yet. A simulation:
primary = {"name": "Sara"}
replica = dict(primary)
pending = [] # writes not yet copied
def write(key, value):
primary[key] = value
pending.append((key, value))
def replicate():
while pending:
key, value = pending.pop(0)
replica[key] = value
write("name", "Sara A.")
print("replica right after write:", replica["name"])
print("primary right after write:", primary["name"])
replicate()
print("replica after catch-up :", replica["name"])3Consistent hashing
With hash % N, adding a fourth database moves most keys. Consistent hashing places databases on a ring and each key goes to the first database after it, so an addition moves only a small share:
import bisect
import hashlib
def h(text):
return int(hashlib.md5(text.encode()).hexdigest(), 16)
def ring(nodes, replicas=50):
points = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(replicas))
return [p for p, _ in points], [n for _, n in points]
def owner(key, hashes, names):
i = bisect.bisect(hashes, h(key)) % len(hashes)
return names[i]
keys = [f"user:{i}" for i in range(1000)]
before = {k: f"db{h(k) % 3}" for k in keys}
after = {k: f"db{h(k) % 4}" for k in keys}
print("modulo moved :", sum(before[k] != after[k] for k in keys), "of 1000")
r3, r4 = ring(["db0", "db1", "db2"]), ring(["db0", "db1", "db2", "db3"])
moved = sum(owner(k, *r3) != owner(k, *r4) for k in keys)
print("consistent moved :", moved, "of 1000")Worked example
Problem: the product page runs 8 queries, the database sits at 90% at peak, and 95% of requests are reads. Fix: cache the whole product page in Redis for 5 minutes, delete it when the product is edited, and add a read replica for search pages. Result: a 92% hit rate and the database down to 25%, with no sharding and no change to the core design.
Myth vs Reality
| Myth | Reality |
|---|---|
| Cache everything. | What changes often or is read rarely adds invalidation complexity for no gain. |
| Sharding is the first fix for a slow database. | Indexes, then caching, then read replicas, then a bigger server. Sharding is last because it complicates everything. |
Test your understanding
An LRU cache is full and needs room. What is evicted?
LRU = Least Recently Used.
A user edited their profile and cannot see the change. Likely cause?
Replication lag or forgotten invalidation.
The advantage of consistent hashing?
Modulo moves most keys when the count changes.
Quick review cards
Check Your Understanding
What is the hardest part of caching?
Invalidation: knowing when a cached value is stale and removing it.
Why do writes not go to read replicas?
Because there is one source of truth (the primary) and replicas follow it.
When do you consider sharding?
When writes or data no longer fit one server even after indexes, caching, replicas and a bigger server.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Official docs2
Done with this lesson?
Sign in to save your progress.