Databases at Scale
Replication for reads and availability, sharding for size, consistency and CAP in plain terms, choosing SQL or NoSQL, and a hash-based shard router with fixed slots.
advanced45 min#replication#sharding#cap#consistency#nosql
Prerequisites: Databases and SQL, Caching Strategies
Why it matters
A single database server eventually runs out of something: disk, memory, CPU, or connections. It is also one machine that can fail. Scaling the data tier is harder than scaling stateless app servers because data has to live somewhere and stay correct. Two tools do most of the work: replication (copies for read capacity and survival) and sharding (splitting data so no machine holds all of it). Each brings consistency trade-offs you need to be able to explain.
Intuition
Replication is photocopying a book so several readers can read at once and one fire cannot destroy the only copy. The catch: when the author edits the original, the copies are briefly out of date.
Sharding is splitting an encyclopedia into volumes, A to F, G to M, and so on. Each volume is smaller and can sit on its own shelf. The catch: a question that spans volumes needs several lookups, and rebalancing the volumes later is real work.
How it works
Replication
In leader-follower replication, all writes go to one leader, which streams changes to followers. Reads can be served by followers, multiplying read capacity. If the leader dies, a follower is promoted (failover).
- Asynchronous replication returns after the leader writes. It is fast, but followers lag, so a read from a follower can return old data, and an unreplicated write can be lost if the leader dies.
- Synchronous replication waits for a follower to confirm. It is safer but slower, and a slow follower slows every write.
Replication helps reads and availability. It does not help write volume or total data size, because every node still holds everything.
Sharding
Sharding (horizontal partitioning) splits rows across independent databases by a shard key. Common strategies:
- Range: key ranges per shard. Range queries are cheap, but hot ranges (like newest timestamps) overload one shard.
- Hash: hash the key and map to a shard. Load spreads evenly, but range scans touch every shard.
- Directory: a lookup table says where each key lives. Flexible, but the directory is another component to keep alive.
Hashing with hash % number_of_shards breaks when you add a shard because almost every key moves. A better pattern: hash into a large fixed number of slots (for example 64 or 1,024), then keep a small table mapping slots to shards. Adding a shard means reassigning some slots and copying only their data.
Costs of sharding: cross-shard joins and transactions are hard, secondary indexes may span shards, and a bad shard key (low cardinality or skewed) creates hot spots that no amount of hardware fixes.
Each cell is a shard and the number of its 64 slots. Adding s5 takes 12 slots (64 divided by 5, rounded down) from the busiest shards, so only those slots' data is copied.
Consistency and CAP in plain terms
When a network partition splits your nodes, you must choose between two things. You can keep answering requests, risking stale or conflicting answers (availability). Or you can refuse some requests until the nodes agree, so every answer is correct (consistency). That is the CAP trade-off: during a partition you cannot have both. When there is no partition, the real trade-off is latency versus consistency.
- Strong consistency: after a write completes, every read sees it. Easier to reason about; slower and less available.
- Eventual consistency: replicas converge if writes stop, but reads may be stale for a while. Faster and more available.
Useful middle grounds: read-your-writes (you always see your own updates, for example by reading from the leader right after you write) and monotonic reads (you never see time go backwards).
SQL or NoSQL?
Choose from access patterns, not fashion.
- Relational (SQL): structured data, joins, multi-row transactions, ad hoc queries. Scales vertically very far and with replication; sharding is possible but manual.
- Key-value and wide-column stores: simple lookups by key at very large scale, built for partitioning, often eventual consistency, limited queries.
- Document stores: nested, flexible-shape records fetched as a unit.
A frequent answer is both: SQL as the system of record for money-like data, plus a key-value store or cache for high-volume simple reads.
| Operation | Time | Notes |
|---|---|---|
| Read from a replica | Scales with replicas | May be stale (replication lag) |
| Write (single leader) | Bounded by one machine | Replication does not add write capacity |
| Shard lookup (hash to slot to shard) | O(1) | Plus network hop |
| Cross-shard query | O(number of shards) | Scatter-gather; avoid on the hot path |
Code: a hash-based shard router
The router hashes a key into one of 64 slots and looks up the owner. Adding a shard steals slots from the busiest shards. We compare how many keys move against naive modulo hashing.
def h32(text):
h = 2166136261
for b in text.encode("utf-8"):
h ^= b
h = (h * 16777619) & 0xFFFFFFFF
h ^= h >> 16
h = (h * 0x85EBCA6B) & 0xFFFFFFFF
h ^= h >> 13
h = (h * 0xC2B2AE35) & 0xFFFFFFFF
h ^= h >> 16
return h
class ShardRouter:
SLOTS = 64
def __init__(self, shards):
self.owner = [shards[i % len(shards)] for i in range(self.SLOTS)]
def route(self, key):
return self.owner[h32(key) % self.SLOTS]
def add_shard(self, name):
shards = sorted(set(self.owner))
target = self.SLOTS // (len(shards) + 1)
for _ in range(target):
counts = {s: self.owner.count(s) for s in shards}
donor = max(shards, key=lambda s: (counts[s], s))
slot = max(i for i, s in enumerate(self.owner) if s == donor)
self.owner[slot] = name
def load(self, keys):
out = {}
for k in keys:
s = self.route(k)
out[s] = out.get(s, 0) + 1
return dict(sorted(out.items()))
keys = [f"user:{i}" for i in range(1000)]
router = ShardRouter(["s1", "s2", "s3", "s4"])
before = {k: router.route(k) for k in keys}
print("load before:", router.load(keys))
router.add_shard("s5")
after = {k: router.route(k) for k in keys}
print("load after:", router.load(keys))
moved = sum(1 for k in keys if before[k] != after[k])
modulo_moved = sum(1 for k in keys if h32(k) % 4 != h32(k) % 5)
print("slot router moved:", moved)
print("modulo moved:", modulo_moved)function h32(text) {
let h = 2166136261;
for (const b of Buffer.from(text, "utf8")) {
h ^= b;
h = Math.imul(h, 16777619) >>> 0;
}
h ^= h >>> 16;
h = Math.imul(h, 0x85ebca6b) >>> 0;
h ^= h >>> 13;
h = Math.imul(h, 0xc2b2ae35) >>> 0;
h ^= h >>> 16;
return h >>> 0;
}
class ShardRouter {
static SLOTS = 64;
constructor(shards) {
this.owner = Array.from({ length: ShardRouter.SLOTS },
(_, i) => shards[i % shards.length]);
}
route(key) {
return this.owner[h32(key) % ShardRouter.SLOTS];
}
addShard(name) {
const shards = [...new Set(this.owner)].sort();
const target = Math.floor(ShardRouter.SLOTS / (shards.length + 1));
for (let n = 0; n < target; n++) {
const counts = Object.fromEntries(
shards.map((s) => [s, this.owner.filter((o) => o === s).length]));
let donor = shards[0];
for (const s of shards) {
if (counts[s] > counts[donor] ||
(counts[s] === counts[donor] && s > donor)) donor = s;
}
let slot = -1;
this.owner.forEach((s, i) => { if (s === donor) slot = i; });
this.owner[slot] = name;
}
}
load(keys) {
const out = {};
for (const k of keys) {
const s = this.route(k);
out[s] = (out[s] || 0) + 1;
}
return Object.fromEntries(Object.entries(out).sort());
}
}
const show = (o) => "{" + Object.entries(o)
.map(([k, v]) => `'${k}': ${v}`).join(", ") + "}";
const keys = Array.from({ length: 1000 }, (_, i) => `user:${i}`);
const router = new ShardRouter(["s1", "s2", "s3", "s4"]);
const before = new Map(keys.map((k) => [k, router.route(k)]));
console.log("load before:", show(router.load(keys)));
router.addShard("s5");
const after = new Map(keys.map((k) => [k, router.route(k)]));
console.log("load after:", show(router.load(keys)));
const moved = keys.filter((k) => before.get(k) !== after.get(k)).length;
const moduloMoved = keys.filter((k) => h32(k) % 4 !== h32(k) % 5).length;
console.log("slot router moved:", moved);
console.log("modulo moved:", moduloMoved);Both versions print:
load before: {'s1': 249, 's2': 249, 's3': 242, 's4': 260}
load after: {'s1': 195, 's2': 202, 's3': 200, 's4': 207, 's5': 196}
slot router moved: 196
modulo moved: 812
Only the keys in the reassigned slots moved, a small fraction of the data, whereas modulo hashing relocated most of it.
In production, those moved slots are copied in the background and the table is switched over when each slot is caught up.
Common pitfalls
- Sharding too early. Indexes, caching, and read replicas take many systems a long way. Sharding permanently complicates queries and transactions.
- Hot shards. A celebrity user or a timestamp key sends disproportionate traffic to one shard.
- Reading stale replicas by accident. Reading your own write from a lagging follower makes data look lost. Route those reads to the leader or track lag.
- Cross-shard transactions. They need coordination protocols and are slow and fragile. Design so the common operations stay inside one shard.
- Modulo placement. It makes adding capacity a mass migration. Use slots or consistent hashing.
- Assuming failover is free. Promotion can lose acknowledged writes under asynchronous replication, and split-brain (two leaders) must be prevented.
Practice
Replicas and write volume easy
Hint
Where do writes go in leader-follower replication?
Show solution
Adding followers increases read capacity but not write capacity: every write still goes to the leader and is replayed on every follower. If writes are the bottleneck you need sharding (or a different write path), not more replicas.
Choose a shard key for a messaging app medium
Hint
What is the most common query? Which key keeps it on one shard?
Show solution
The hot query is "fetch the messages in this conversation". Sharding by conversation id keeps a conversation on one shard and spreads load across many conversations. Sharding by sender would scatter a conversation across shards, and sharding by timestamp would make the newest shard the hot one.
Fix read-your-writes medium
Hint
After a write, where could the next read be served from?
Show solution
Options: read from the leader for a short window after a user writes; or have the client carry the write's position (a version or log offset) and read only from replicas that have caught up to it. The first is simpler; the second preserves replica read capacity.
Rebalance with fewer moved keys hard
Hint
Which fixed layer sits between key and machine?
Show solution
Use many more slots than shards. When a shard is added, reassign roughly an equal share of slots from existing shards to it and copy just those slots. Keys move only if their slot moves, so about 1/(n+1) of the data relocates instead of nearly everything. This is the same idea behind consistent hashing and fixed hash-slot designs.
Interview questions
- Replication versus sharding? Replication copies the same data for read scale and availability; sharding splits different data across machines for size and write scale.
- Explain CAP simply. In a network partition you either serve possibly stale data (available) or reject requests until agreement (consistent).
- What are the downsides of eventual consistency? Stale reads and conflicting writes that need resolution, so the application must tolerate or handle them.
- When would you pick NoSQL over SQL? When access is simple key-based lookups at a scale or shape that a single relational node cannot serve, and you can live without joins and multi-row transactions.
- How do you pick a shard key? High cardinality, even load, and alignment with the dominant query so most operations stay on one shard.
Interviewers look for: the distinction between read scaling and write scaling, explicit mention of consistency trade-offs, and a shard key justified by query patterns and skew.
Quick check
Your database is read-heavy and the leader's CPU is fine, but read latency is high. What is the most direct first step?
Finished this lesson?
Further resources
- Replication (Wikipedia) (article)
- Shard (database architecture) (Wikipedia) (article)
- CAP theorem (Wikipedia) (article)
- Eventual consistency (Wikipedia) (article)