Tied to Mission: Backend Depth — the third leg of DDIA's replication/partitioning/consensus triad, flagged as a gap since Lesson 15. Lesson 17's log got its capacity from partitions; this lesson treats the same idea for databases: how one logical dataset becomes many physical ones.
The users table is 2TB. Queries are slow even though your indexes are perfect — because the index is on one node, and one node's disk, memory, and CPU are the bottleneck (Lesson 9's planner does its best, but it only sees one machine's resources). So you split the table across 10 nodes. Two surprises follow. First: your most famous user — the one with a billion followers — lands on the busiest shard, and every query about them fans out into a small disaster. Second: the day you add an 11th node, millions of rows move, and your writes slow to a crawl for an hour. The index was never the problem. The data just doesn't fit on one node anymore.
Lesson 15's replication makes copies of the same data — for fault tolerance and read scaling. Partitioning (sharding) makes subsets — each node holds a different slice, so the cluster's total capacity is the sum of its nodes. They combine: a partition is the unit that gets replicated, so a sharded database is really "each shard has replicas" (Lesson 15's machinery, applied per shard). The two questions are independent, and confusing them is a classic system-design mistake: replication helps you survive node failure; partitioning helps you survive data size.
The whole design hangs on one choice: how you decide which node owns a given row. Two families exist, and each buys something and charges for it.
hash(key) % N (or a hash ring) and let the hash decide the node. The win: even spread by construction — similar keys land on different nodes, and load balances across the cluster. The cost: range scans die — adjacent keys are scattered, so any range query is a scatter-gather across all shards. And even spread of keys isn't even spread of load: one celebrity user's row still lives on exactly one node, and every read of that row hits that node. Hash partitioning fixes skew-by-key; it cannot fix skew-by-hotness.This is the same choice Lesson 17 made for the log: partitions by key give per-key order and parallelism. The database version adds the access-pattern question: the partition key must match your primary query shape. If most queries are "fetch this user's data," key on user id. If most are "what happened last week," key on time and accept the write hotspot, or design around it.
Your primary key defines the partition. But every other index is a second way to look up data, and indexes don't partition themselves. Two designs: local (each shard keeps its own index; a lookup by secondary key must query every shard and merge — fan-out on every read) or global (one index spanning all shards; reads hit one node, but writes must update two places, which breaks the "one partition per write" property). Every sharded system quietly pays one of these costs for every non-primary-key lookup.
Shards must move when nodes join or leave — that's rebalancing. The naive scheme is the trap: user_id % N with N nodes. Add one node and switch to % N+1, and almost every key's remainder changes — the cluster has to move nearly all its data, and writes stall while it does. The fix is to break the coupling between key and node count:
Both schemes exist for the same reason: rebalancing should move a small fraction of data, not all of it — the data-moved-per-node-added is the number that determines whether scaling out is a 10-minute operation or a maintenance window.
user_id % 4. You add a 5th node and switch to user_id % 5. What happens to the data?% N, changing N changes the remainder for most keys. That's why real systems assign keys to a large fixed set of partitions (or a hash ring) and move partitions when nodes change: the data moved per node added stays near 1/N.
Not quite — % N couples every key to the node count, so changing N rehashes nearly everything. The whole point of consistent hashing and fixed partition counts is to make node changes move only a small slice. Re-read the rebalancing section.
Prove the rebalancing cost to yourself in ~30 lines of Python. Generate 10,000 keys, shard them with key % 4, then re-shard with key % 5 and count how many keys changed node: it's most of them. Now implement a hash ring: hash each key to a position on a circle of 4 nodes; add a 5th node at a random position and count keys whose owner changed: roughly 1/5, independent of total key count. Then add the skew experiment: give one key 1,000× the reads of others and note that its shard is saturated no matter how the ring is arranged — that's the hot-key problem no sharding scheme fixes, and it's why Lesson 3's caching exists. If you want the fan-out half, run a secondary-index lookup against all shards and observe that the slowest shard sets the answer's latency.
Designing Data-Intensive Applications, Chapter 6, "Partitioning" — the authoritative treatment: range vs. hash, skewed workloads, secondary indexes, rebalancing. The original consistent hashing paper (Karger et al.) is short and explains the ring precisely; Dynamo's paper and Cassandra's architecture docs show the ring in production. For a concrete range-sharding case study, Instagram's Sharding IDs post shows why they moved off naive approaches.
Partitions spread data across nodes — but they only stay consistent if the cluster can agree on who owns what, even when nodes fail. Lesson 19: quorum and consensus.