Sharding & partitioning

Replication is not enough

Replication copies the whole dataset to every node, so it scales reads and survives failures — but every node still holds everything, and every node still takes every write. Once the data won’t fit on one disk, or the write rate exceeds what one leader can absorb, copying doesn’t help; you have to split. Sharding (horizontal partitioning) divides the dataset into disjoint pieces — shards or partitions — and puts each on a different node, so each node holds only 1/N of the data and takes only its slice of the writes.

(A note on words: “partitioning” inside one database engine — Postgres declarative partitions, say — and “sharding” across separate database servers are the same idea at different scopes. The databases track’s sharding unit goes deep on the single-engine mechanics; here we reason about the distribution choice itself.)

The decision that governs everything is the partition key: the field whose value decides which shard a row lives on. Pick it well and load spreads evenly and your common queries stay on one shard. Pick it badly and you get the hook’s hot shard and cross-shard queries that fan out to every node.

Three ways to assign keys to shards

Which strategy you pick is a decision you’ll live with for years — so it’s worth understanding the exact trade-off each one buys before you write the first migration script.

range:      [A–F] → shard 0   [G–M] → shard 1   [N–Z] → shard 2
hash:       shard = hash(key) mod N         (spreads neighbours apart)
directory:  lookup table: key → shard       (explicit, flexible, one more hop)

• Range partitioning keeps keys in sorted order, so range scans (“all orders from March”) hit one shard and stay efficient. The danger is that ordered keys cluster: shard by timestamp and all of today’s writes land on the last shard — a moving hot spot.
• Hash partitioning runs the key through a hash and assigns by the result, scattering neighbouring keys across shards so load spreads evenly. The cost is that range scans now hit every shard, because adjacent keys are deliberately far apart.
• Directory partitioning keeps an explicit lookup table mapping keys (or key ranges) to shards. Maximum flexibility — you can move a hot key to its own shard — at the cost of an extra lookup and a directory that is itself critical infrastructure.

Together these three strategies form a dial: range gives you query efficiency at the cost of write hot-spots on ordered keys; hash gives you even write load at the cost of range scans; directory gives you flexibility at the cost of an extra hop and a new piece of critical infrastructure to maintain. Without understanding this dial, you’ll reach for hash by default and only discover the range-scan penalty in a production incident.

The hot-shard / celebrity problem

Even partitioning evenly by key count does not partition evenly by load. The hook’s celebrity is the canonical case: one key (a user, a product, a video) receives orders of magnitude more traffic than the average, so its shard saturates while the rest idle. This is skew, and it defeats the naive “just hash the key” answer, because all of one hot key’s traffic still lands on the one shard that owns it.

Mitigations all amount to spreading a hot key’s load:

• Split the hot key: append a random suffix (celebrity_id:00…:09) so its writes scatter across ten logical keys on different shards, and fan reads back in. You trade simplicity for spread.
• Cache the hot key in front of the shard so most reads never reach it (the next unit’s caching lessons).
• Isolate it: give the known hot key its own dedicated shard (directory partitioning makes this a one-row change).

Together these three mitigations reduce the traffic that reaches the hot shard — splitting moves writes to many shards, caching absorbs reads before they arrive, and isolation gives the hot key its own capacity budget. Without at least one of them, a single celebrity key can saturate a shard no matter how many nodes the rest of the cluster has.

The senior reflex: a uniform key distribution does not imply a uniform load distribution. You must reason about the access pattern, not just the key space.

Resharding pain

Sooner or later you outgrow your shard count and must reshard — add shards and redistribute data. With the naive hash(key) mod N scheme this is brutal: change N and almost every key maps to a different shard, so you must move nearly the whole dataset at once, while serving live reads and writes against keys that are mid-flight. This is precisely the “rehash everything” pain that consistent hashing (the next lesson) exists to solve — it lets you add a shard and move only ~1/N of the keys instead of all of them.

Even with consistent hashing, resharding is an operational marathon: you copy data while it’s changing, keep a record’s old and new home in sync until cutover, double-write or use change-data-capture to avoid losing writes during the move, and flip routing atomically. Teams that designed for resharding (more logical shards than physical nodes, so growth is “move a shard,” not “re-split the keyspace”) have a far easier time than teams who must split a live keyspace for the first time during a capacity crisis.

Cross-shard joins, transactions, and secondary indexes

Splitting data breaks the two things a single database gave you for free:

• Cross-shard joins no longer happen in the engine. A join between data on different shards must be done by the application (or a query layer): scatter-gather the pieces and join them in memory. It works, but it’s slow and fragile, which is why shard keys are chosen so that data joined together lives together (colocation — e.g. shard a customer’s orders onto the same shard as the customer).
• Cross-shard transactions lose single-node ACID atomicity. Updating two rows on two shards atomically needs a distributed transaction (two-phase commit) or a saga — a sequence of local transactions with compensating undo steps. Both are far more expensive and failure-prone than a single-node BEGIN…COMMIT; the distributed track’s sagas unit covers the pattern in depth.
• Secondary indexes stop being global. If you shard by user_id but need to query by email, the email index is scattered across all shards. You either keep a local index per shard (then a query by email must hit every shard — scatter-gather) or a global index that is itself a separate sharded structure (kept consistent with the base data, often asynchronously, so it can lag). DynamoDB’s global secondary indexes, for instance, are eventually consistent for exactly this reason.