Sharding

The problem it solves

One database eventually runs out — of disk, of write throughput, of memory for the working set, of connections. Read replicas do not help, because they multiply reads and not writes. The remaining option is to split the data across independent machines, and the moment you do, you must choose a partition key.

That choice is the highest-consequence decision in most designs and the one most often made casually. It determines whether your load is even, whether your common queries touch one shard or all of them, whether you can add capacity without moving everything, and whether one large customer can take down the system. It is also the hardest thing to change later, because changing it means rewriting every row’s location.

The mechanism

Range partitioning assigns contiguous key ranges to shards. Range scans are efficient — “all orders from March” is one shard — and rebalancing moves whole ranges. Its failure is monotonic keys: timestamps, auto-increment ids, ULIDs. Every new row has the largest key, so every write goes to the last shard while the others sit idle. You have built a distributed system with one active node.

Hash partitioning assigns hash(key) mod shards, or better, positions on a ring. Distribution is excellent because hashing destroys the structure that caused the hot spot. In exchange you lose ordering: a range scan must touch every shard, and “the most recent 100 orders” becomes a scatter-gather with a merge.

Directory partitioning keeps an explicit map from key (or from a bucket of keys) to shard. Maximum flexibility — you can move an individual hot tenant to its own shard — at the cost of a lookup service that is now on the critical path of every query and must be highly available and consistent.

Underneath all three is a distinction worth stating: partitioning splits data by key, and a hot key is not split by anything, because it is one key.

What the simulation shows

Start with hash partitioning on skewed traffic and the load-per-shard panel is comfortably even. Now switch to range partitioning with monotonic keys. Every write lands on the last shard. The imbalance metric goes to its ceiling, the latency panel shows that shard queueing while five others idle, and no amount of adding shards helps — the new shard becomes the last one and inherits the entire write stream.

Then the harder lesson. Turn on a hot tenant taking half the traffic, under hashing. Hashing was supposed to fix skew. It does not fix this, because the skew is not across many keys, it is within one key. That key hashes to one shard, and that shard is overloaded no matter how many others exist. Try range and directory too: all three schemes fail identically, which is the point — the fix is not a partitioning scheme, it is a change to the key or to the architecture.

Finally, look at the rebalancing panel when a shard is added. Under naive mod n hashing, nearly every key re-maps; under range or directory partitioning, about one shard’s worth moves. That is the same result as consistent hashing, from the storage side where the moved keys are real bytes over a real network.

The numbers worth carrying

Imbalance ratio — busiest shard over mean — is the number that decides whether a design works. Under 1.5 is comfortable; above 3 means you are provisioning every shard for the busiest one and wasting most of your fleet.

Rebalancing cost is bytes: shards × bytes-per-shard × fraction moved. Ten shards holding 400 GB each, adding one, moving a tenth of the data, is 400 GB across the network while serving live traffic. That is hours, and it competes with the foreground workload the whole time.

Capacity per shard should be planned so you split before you must: splitting an overloaded shard is a much worse operation than splitting a comfortable one, because the copy competes with traffic the shard already cannot serve.

Where it breaks down

Cross-shard queries. Any query that does not include the partition key becomes a scatter-gather across every shard, with the tail latency consequences that implies — a fan-out of n means the slowest of n shards sets your latency. Secondary indexes are the same problem: a global index is itself a partitioned structure needing its own key, and a local index requires touching every shard.

Cross-shard transactions. Now you need two-phase commit, or a saga, or a schema in which the transaction never crosses shards. The third option is the one that works, and it usually means picking a partition key that co-locates everything a transaction touches — customer id, tenant id, account id.

Resharding. Doubling shard count is the easy case (each shard splits in two). Arbitrary counts are much harder. The standard trick is to partition into a large fixed number of logical shards — 1,024, say — and map many logical shards to each physical node; then rebalancing moves logical shards, and the key-to-logical-shard mapping never changes.

The hot key. Compound the key (tenant:bucket where bucket is a small random or time-derived suffix) to spread writes at the cost of gathering on read; give the hot tenant a dedicated shard; or put a cache in front. Those are the three answers, and there is no fourth.

What people get wrong

“Hashing solves hot spots.” It solves hot ranges. A single hot key survives every scheme on this page.

“We will shard later.” Later means migrating a live production database with an active schema, which is a project, not a task. At minimum, choose a partition key early and put it in every table’s primary key even before you split.

“Add a shard when we are full.” The copy competes with foreground traffic on the shard that is already at its limit. Split before it is full.

“Auto-increment ids are fine.” With range partitioning they are the hot-shard failure in the simulation. With hashing they are fine — which is why “is it fine” always depends on the other half of the design.

In production

Vitess shards MySQL with a lookup layer and online resharding; Citus does the same for Postgres; MongoDB supports ranged and hashed sharding and its documentation is unusually direct about monotonic keys defeating ranged shard keys. DynamoDB’s partition key is a hash key by construction and its documentation calls the hot-key failure out explicitly, recommending exactly the write-sharding suffix described above. Cassandra separates partition key from clustering key, which is a useful mental model in any system: one decides where, the other decides order within.

The logical-shard trick is worth naming in an interview. Fixing the number of logical partitions up front — Kafka does this with partitions, Elasticsearch with primary shards, and both make it painful to change afterwards — is how you make rebalancing an assignment problem instead of a rehashing problem.

The follow-up questions

“What is your partition key and why?” — The expected answer names the key, names the queries it makes single-shard, and names the queries it makes scatter-gather.

“One customer is 40% of your traffic. What happens?” — The hot-key failure. Then: compound key, dedicated shard, or cache. Pick one and say the cost.

“How do you add a shard?” — Logical shards, or accept the copy. Give the byte arithmetic.

“How do you do a transaction across two shards?” — Avoid it by key choice; otherwise 2PC or a saga, with the availability cost of each.