Start here: the problem it solves#
TL;DRthe 30-second version
- Sharding splits one dataset across many machines. A shard is one piece; a partitioning strategy is the rule that decides which shard each row lives on.
- Hash partitioning sends hash(key) mod N to a shard. It spreads load evenly, but a resize changes N and moves almost every key.
- Range partitioning gives each shard a contiguous band of keys. It makes range scans fast, but sequential keys (auto-increment ids, timestamps) pile into one shard — a hotspot.
- Directory partitioning keeps an explicit lookup table of key to shard. You get total control, at the cost of a table that grows with the data and one extra lookup per request.
- The hidden cost is resharding. Plain hash-mod moves ~N/(N+1) of the data when you add a shard. A stable scheme — consistent hashing, or a fixed set of virtual buckets — moves only ~1/(N+1).
Say you're running a user database. It started on one server and life was simple: every row was in one place, and any query — a lookup, a join, a count — just ran. Then you grew. Now you have two billion users, each row is about 1 KB, and that's 2 TB of data taking far more than 2 TB once you add indexes. No single machine has the memory to cache it or the disk throughput to serve it. You've run out of one-machine.
The first instinct is to buy a bigger machine. That's called scaling up, and it works right until it doesn't: the biggest server money can buy still has a ceiling, and you pay a steep premium as you approach it. The alternative is to scale out — spread the data across many ordinary machines. That's sharding. The word comes from breaking a pane of glass into shards; each shard holds a slice of the whole.
But splitting the data is the easy half. The moment there's more than one machine, two hard questions appear. First: given a key, which machine has it? You can't search all of them for every request. Second: how do you keep the pieces roughly equal, so one machine isn't drowning while the others nap? Both questions come down to the same thing — the function that maps a key to a shard.
The idea that almost works: split by the first letter#
Start with the most obvious split. You have four machines, so put usernames starting A–F on shard 0, G–M on shard 1, N–S on shard 2, and T–Z on shard 3. To find a user, look at the first letter and go straight to the right machine. No searching. This already answers the first hard question, and it feels clean.
Now watch it break. Far more usernames start with 'S' or 'M' than with 'X' or 'Z', so the shards that own those letters fill up while others stay half-empty. That's the balance problem, and it's not a rounding error — the busiest shard might hold three times what the quietest one does. When one shard is three times as full, it's also roughly three times as busy, and it becomes the bottleneck for the whole system.
The letter split made a specific mistake: it mapped keys to shards using a property of the key that isn't evenly distributed. Real names aren't spread evenly across the alphabet. To fix balance, you need a mapping that doesn't care what the key looks like — one that scatters keys evenly no matter how lopsided the input is.
The mechanism: a shard key and a routing rule#
Every sharding scheme has two parts. The shard key is the field you route on — the user id, the account id, whatever you look things up by. The routing rule is the function that turns that shard key into a shard number. Pick the shard key once, up front; it's painful to change later because it decides where every row lives. Then choose one of three routing rules.
The first rule is hash partitioning. Take the shard key, hash it to a number, and compute that number mod N, where N is the shard count. The hash spreads keys evenly, so each shard gets about the same share, and neighbouring keys like user:1000 and user:1001 land on completely different shards. This is the default when you just want even load and you look rows up one at a time.
The second rule is range partitioning. Give each shard a contiguous band of the key space: shard 0 owns keys 0 through 1999, shard 1 owns 2000 through 3999, and so on. To route a key, find the band it falls in. The payoff is range scans — 'give me every order from last Tuesday' touches one or two shards instead of all of them, because nearby keys live together. The risk is the flip side of that same property, and we'll see it in a moment.
The third rule is directory partitioning. Keep an explicit table that records, for every key, which shard it's on. Routing is a lookup in that table. This gives you total control — you can put any key anywhere, move a single hot key by itself, and rebalance by editing entries — but the table has one row per key, so it grows with the data, and every request pays for the extra lookup.
The simulator runs exactly this. Load the range scenario, route user:1000 through user:1007, and watch every one of them fall into the same band — one shard climbs to eight while the other three stay empty. Then load the hash scenario with the same keys and watch them spread two per shard. Same data, same shard count; the only thing that changed is the routing rule.
PredictYou shard an events table on a timestamp using range partitioning. New events always have the current time. Which shard gets all the writes?
Hint: Where does 'now' always fall in a range that runs oldest to newest?
The last one — the shard that owns the most recent time range. Because timestamps only ever increase, every new write lands at the top of the key space, so one shard takes the entire write load while the rest only serve old reads. This is the monotonic-key hotspot, and it's the classic reason not to range-partition on a timestamp or an auto-increment id.
When one shard runs hot#
A hotspot is a shard that carries far more than its fair share of data or traffic. Range partitioning creates them whenever the shard key climbs over time. Auto-increment ids, timestamps, and monotonically increasing sequence numbers all do this: the newest keys are always the largest, so they always fall in the same top band, so the shard that owns that band takes every new write. The other shards sit idle holding cold history. You bought four machines and you're writing to one.
Hash partitioning avoids that particular trap because it scatters sequential keys, but it has its own hotspot: a single popular key. If one celebrity account, one viral product, or one enormous tenant gets a thousand times the traffic of everyone else, hashing sends all of that traffic to whichever shard owns that key. No amount of adding shards helps, because the key is indivisible — it always hashes to one place. Fixing this needs something outside the sharding scheme: replicate the hot key to several shards, or cache it in front of the database, or split the key itself into sub-keys.
Range partitioning has a graceful answer to its own hotspots, though. When a range gets hot, split it. Cut the busy shard's band in two at the median of its keys and hand the upper half to a new shard. Only that one shard's keys move; everything else is untouched. This is exactly how HBase splits regions and how DynamoDB's 'split for heat' relieves a hot partition — it picks a split point based on where the traffic actually is, so the load divides roughly in half.
The cost nobody plans for: adding a shard#
Balance is only half the story. The other half shows up the day you need more capacity and add a shard. This is resharding, and its cost is measured in one number: how many keys have to physically move to a new machine. Every key that moves is a network copy, a cache invalidation, and a window where a request might look in the wrong place.
Here's why plain hash-mod is expensive to grow. Routing is hash(key) mod N. Go from 4 shards to 5, and the divisor changes from 4 to 5, so almost every key's answer changes. Concretely, a key stays put only if hash(key) mod 4 and hash(key) mod 5 happen to agree, which is rare — so about four out of every five keys move. You added one machine and shuffled 80% of your data across the network. Do that on a live 2 TB cluster and you're copying 1.6 TB while still serving traffic.
The fix is to stop hashing directly onto the shard count. Instead, hash onto a large, fixed number of virtual buckets — say a few thousand — and keep a small map from buckets to shards. Routing becomes: hash to a bucket, then look up the bucket's shard. Now the shard count never appears in the hash, so growing the cluster doesn't rehash anything. To add a shard, you reassign a handful of buckets to it and move only the keys in those buckets — about one in N+1 of the data, roughly 20% going from 4 shards to 5. This is the fixed-partition idea from 'Designing Data-Intensive Applications', and it's the same insight as consistent hashing, which you may already know as the ring: put a layer of indirection between the key and the machine so the machine count can change cheaply.
| Strategy | Keys moved when 4 → 5 shards | Why |
|---|---|---|
| Hash-mod (hash mod N) | ~80% (four in five) | The divisor N is baked into the hash, so changing N re-routes almost everything. |
| Bucketed / consistent hashing | ~20% (one in five) | Keys hash to fixed buckets; only the reassigned buckets' keys move. |
| Range (split a hot shard) | Only the split shard's keys | A targeted split touches one shard; the rest are untouched. |
| Directory | Only what you choose to move | The table forces no movement; you migrate keys deliberately. |
The simulator makes this concrete. Seed sixteen keys, then add a shard under hash and watch the move count jump to around 80%. Reset to the bucketed strategy, seed the same sixteen keys, add a shard, and watch only about two of the sixteen move — a small-sample glimpse of the ~20% (1/(N+1)) the stable scheme promises. Same growth, same data — the mapping layer is the entire difference.
Go deeperDeeper: why exactly ~N/(N+1) under hash-mod
For a uniformly random hash value h, the key stays on its shard after a resize only when h mod N equals h mod (N+1). Across the whole hash range these two only agree for a fraction of values — in the limit, about 1/(N+1) of keys keep their home and N/(N+1) move. So 4→5 keeps ~1/5 and moves ~4/5; 9→10 keeps ~1/10 and moves ~9/10. The larger the cluster, the worse a single mod-N resize gets, which is precisely why no serious system reshards this way.
Consistent hashing reaches the same ~1/(N+1) movement bound without a bucket map, by placing both keys and shards on a ring and walking clockwise. Fixed buckets are the discrete, easy-to-reason-about version of the same trick; virtual nodes then smooth out the per-shard balance. See the consistent hashing topic for the ring in full.
Choosing a strategy#
| Strategy | Load balance | Range scans | Resize cost | Best when |
|---|---|---|---|---|
| Hash | Even | Bad (hits all shards) | High unless bucketed | Point lookups by key, even load matters most |
| Range | Risky (hotspots) | Excellent | Cheap (split one shard) | Time-series, range queries, ordered scans |
| Directory | Whatever you enforce | Depends on layout | Whatever you choose | Few large tenants, need per-key control |
Most real systems combine these. A common pattern is a compound shard key: hash a high-cardinality prefix so load spreads, then keep a range component within each shard so scans inside a tenant still work. Another is to range-partition but pre-split the ranges and add randomness to the key so monotonic writes don't all land in one place. The three pure strategies are the vocabulary; production keys are usually a blend chosen to dodge a specific hotspot.
The one decision that outlives all the others is the shard key itself. Load balance, resize cost, and which queries stay fast all follow from it. Choose a key with high cardinality (many distinct values, so load can spread), low skew (no single value dominates the traffic), and alignment with your most common query (so that query hits one shard, not all of them). Get those three right and the routing rule is a detail; get the key wrong and no routing rule saves you.
The trades you're actually making#
Each strategy hands you one thing and quietly takes another. It's worth naming the trade for each, because the thing it takes is what bites you six months later.
Hash trades range scans for even load. The hash scatters neighbouring keys, so no shard runs hot from a run of sequential ids. But that same scattering means a query like 'every order from Tuesday' is spread across every shard, so the database has to ask all of them and merge the answers. You get balance and you give up cheap ordered reads.
Range trades safety for scans. Neighbouring keys live together, so an ordered read or a range scan touches one or two shards instead of all of them. But keys that climb over time — timestamps, auto-increment ids — all fall in the top band, so one shard takes every new write. You get fast scans and you invite a hotspot.
Directory trades simplicity for control. The lookup table lets you put any key on any shard and move a single hot key by itself. But now every request pays for one extra lookup, and that lookup service is a new component you have to keep fast and keep alive — if it's down, nobody can find anything. You get flexibility and you take on a dependency.
Underneath all three sits the resize trade, and it's the one people forget. Routing straight onto the shard count with hash-mod is the simplest rule to write, but it moves almost the whole dataset the day you add a shard. Putting a mapping layer in between — fixed virtual buckets, or a consistent-hashing ring — costs you a little indirection on every request, and in return a resize moves only a small slice. You pay a constant, tiny tax so you never pay the enormous one.
How real systems shard
MongoDB shards a collection on a shard key and offers both hashed and ranged sharding. It groups documents into chunks, splits chunks as they grow, and runs a balancer that migrates chunks from busy shards to idle ones. Its own advice for a monotonically increasing key is to use hashed sharding, or a compound key with a high-cardinality prefix, precisely to avoid the range hotspot.
DynamoDB hides the shard count entirely: you pick a partition key and it spreads items across internal partitions by hashing it. When one partition gets hot, adaptive capacity isolates the busy items and can split the partition for heat, choosing a split point from recent traffic. That's why AWS hammers on high-cardinality partition keys — a low-cardinality key concentrates traffic on one partition and throttles, since a single partition caps out around 3,000 reads or 1,000 writes per second.
Vitess shards MySQL horizontally. A keyspace is split into N shards with non-overlapping ranges, and a vindex maps each row's shard key to a shard — typically a hash vindex for even spread. Its resharding tool splits or merges shards on a live cluster: it copies and verifies data to the new shards while the old ones keep serving, then cuts over with only a few seconds of read-only time. Cassandra takes yet another route, hashing the partition key onto a consistent-hashing ring with virtual nodes, so adding a node steals a fair, small slice from the existing ones.
Pitfalls
- Range-partitioning on a monotonic key. Timestamps and auto-increment ids always grow, so every write lands on the last shard. Hash the key, or add a random prefix, or pre-split and salt.
- Rehashing on the shard count. hash(key) mod N moves ~80% of your data on a 4→5 resize. Hash onto fixed buckets (or use consistent hashing) so the shard count never enters the hash.
- A single hot key. One celebrity or one giant tenant can overwhelm its shard no matter how many shards you add, because the key is indivisible. Replicate it, cache it, or split it into sub-keys.
- Cross-shard queries and transactions. A join or an aggregate that spans shards has to fan out to all of them and merge the results, and an atomic transaction across shards needs a coordinator. Design the shard key so your hottest query stays on one shard.
- Changing the shard key later. It decides where every row lives, so changing it means re-sharding the entire dataset. Choose it deliberately, up front, for the queries you'll actually run.
- Forgetting rebalancing is not free. Even a good scheme copies data over the network during a resize. Do it gradually, throttle it, and keep serving from the old layout until the new one is verified.
In an interview
When a design problem outgrows one machine, say the word sharding and then immediately go to the two decisions that matter: what's the shard key, and what's the routing rule. Justify the shard key against the dominant query — 'we look users up by id, so shard on user id' — and against balance and skew. Interviewers are listening for whether you know the key is the important choice, not the algorithm.
Reach for hash partitioning by default for even load on point lookups, and call out that you'd hash onto fixed buckets (or use consistent hashing) so you can grow without a full reshuffle. Reach for range partitioning when the workload is range scans or time-series, and in the same breath name its hotspot risk and how you'd dodge it. If someone raises a celebrity or a whale tenant, recognise it as a single-hot-key problem and answer with replication or caching, not more shards.
The senior signal is talking about resharding before you're asked. Anyone can split data; the people who've run a cluster know the expensive day is when you add capacity. Bring up the ~N/(N+1) movement of naive hash-mod, contrast it with the ~1/(N+1) of a stable scheme, and mention doing the migration live and throttled. That one paragraph tells the interviewer you've operated a sharded system, not just read about one.
What's the difference between sharding and partitioning?
People use them almost interchangeably. 'Partitioning' is the general act of splitting a dataset into pieces; 'sharding' usually means partitioning across separate machines specifically for horizontal scale. A partitioned table can live on one server; a sharded one spans many.
Sharding vs replication — same thing?
No, and you usually want both. Sharding splits different data onto different machines for capacity. Replication copies the same data onto several machines for availability and read throughput. A production cluster shards for scale, then replicates each shard so a machine failure doesn't lose that slice.
How is this different from consistent hashing?
Consistent hashing is one specific routing rule — the ring — designed to minimise movement when the machine count changes. Sharding is the broader question of how to split and locate data at all; consistent hashing (or fixed buckets) is the answer to the resharding half of it. This page frames the whole decision; the consistent hashing topic drills into the ring.
Can I change the shard key later?
Only by re-sharding the entire dataset, which is a major migration. The shard key decides where every row lives, so treat it as a long-term commitment and pick it for the queries you'll actually run at scale.
References
- Designing Data-Intensive Applications, Ch. 6: Partitioning — Kleppmann — partitioning by key range vs hash, rebalancing, and the fixed-number-of-partitions strategy.
- MongoDB Manual — Sharding — Shard keys, chunks, the balancer, hashed vs ranged sharding.
- MongoDB Manual — Hashed Sharding — Why hashed sharding suits monotonically changing shard keys.
- Amazon DynamoDB — Partitions, hot keys, and split for heat — How DynamoDB partitions by hash and splits a hot partition.
- DynamoDB — Burst and adaptive capacity — Adaptive capacity and per-partition throughput limits.
- Vitess — Resharding — Splitting and merging shards on a live cluster with minimal downtime.
- Cassandra — Data distribution and virtual nodes — Consistent-hashing ring with vnodes for even, cheap rebalancing.
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.