Sharding
When the data no longer fits on one machine, you split it by key. That choice decides which queries stay cheap, where the load piles up, and how painful it will be to add the next machine.
The whole idea
Why split the data
Replication puts a full copy of the data on several machines. That buys read capacity and fault tolerance, but every replica still stores everything and the leader still takes every write. When the data outgrows one disk, or the write rate outgrows one machine’s IOPS, copies don’t help. You have to split the data itself.
Sharding (or partitioning) splits a dataset into pieces so that each record lives in exactly one piece, and puts different pieces on different machines.Every system names the piece differently: a shard in MongoDB and Vitess, a region in HBase, a tablet in Bigtable, a range in CockroachDB, a vnode in Cassandra, a partition in DynamoDB and Kafka. Same idea. Each shard is a small database of its own. A query that names one key touches one shard, so adding shards adds both storage and throughput.
In practice you do both. Each shard is replicated, so one machine typically leads some shards and follows for others. Everything from the replication lessons still applies, once per shard.
Sharding is also expensive to retrofit. Figma ran on a single Postgres instance on AWS’s largest physical machine in 2020; by 2023 some tables had reached several terabytes and billions of rows, and the busiest were heading for the IOPS ceiling of RDS. Sharding the first table took them roughly nine months. So the questions in this lesson are worth answering before you need to:
- Which key decides where a record lives?
- How does the key map to a shard: by range, or by hash?
- What happens when one key, or one shard, gets too much traffic?
- How does data move when you add a machine?
- How does a request find the right shard?
- What about queries that don’t name the key?
Range partitioning
The first way to split is the way an encyclopedia does: sort the keys and give each shard a contiguous range. Volume 1 holds A–B, volume 2 holds C–D. The ranges don’t need to be equal in width; they need to hold roughly equal amounts of data, so the boundaries follow the data. Bigtable, HBase, CockroachDB, TiKV, Spanner and MongoDB’s ranged sharding all work this way.
Because each shard keeps its keys sorted, range scans are cheap. “All orders for customer 42 between March and May” reads one contiguous run on one shard.
The weakness is just as direct: the access pattern follows the key order. If the key is a timestamp, or an auto-increment ID, every new write goes to whichever shard owns “now”. One shard is on fire and the rest sit idle, however many you add.
Range vs hash, on the same keys
Hash partitioning
The second way is to run the key through a hash function and place the record by the hash, not the key.
A good hash turns 09:00, 09:05 and 09:10 into unrelated numbers, so consecutive keys scatter and new
writes spread across every shard. The hash doesn’t need to be cryptographic: Cassandra uses Murmur3,
Redis Cluster uses CRC16. It does need to be stable across processes and versions, which rules out
many languages’ built-in string hashes, since they are seeded per process.
What you give up is order. Keys that were neighbours are now on different shards, so a range query over the original key becomes a query to every shard.
Compound keys recover most of both. Hash the first part of the key to choose the shard, and sort rows
by the rest within it. A table keyed by (sensor_id, time) spreads sensors across the cluster, yet one
sensor’s history is a single sorted run on one shard. This is the partition key plus sort key of
DynamoDB, and the partition key plus clustering columns of Cassandra.Discord stores messages
under (channel_id, bucket), where a bucket is a fixed window of time. They sized it at about 10 days,
enough to keep even the busiest channel’s partition under roughly 100 MB.
Consistent hashing
Hashing picks a number; you still have to map numbers to machines. The obvious rule, hash(key) mod N,
falls apart the moment N changes.
Adding one machine
Going from 4 to 5 nodes under mod N keeps a key in place only if h mod 4 = h mod 5, which holds for
about 1 in 5 keys. The other 80% move, and every one of those moves is a network copy while you’re
already short of capacity.
Consistent hashing fixes this. Hash nodes and keys onto the same ring; each key belongs to the first node clockwise from it. Adding a node takes over one arc from one neighbour, and removing a node hands its arc to one neighbour. Only about 1/N of the keys move. The idea comes from a 1997 paper by Karger and colleagues on spreading load across web caches; two of its authors went on to found Akamai.
Two problems remain. With one point per node, arcs come out uneven, and a departing node dumps all of its load on a single neighbour. The fix is virtual nodes: many points per machine. Cassandra used 256 random tokens per node in 2.x; 4.0 changed the default to 16, with a deterministic token allocator doing the balancing that sheer numbers used to do, because more tokens per node also means more neighbours and slower cluster-wide maintenance.
There are other ways to get the same property. Rendezvous hashing scores every (key, node) pair and picks the highest score. Google’s jump consistent hash (2014) needs no memory and about five lines of code, but only works when buckets are numbered 0 to n−1, which suits storage shards better than a pool of caches that come and go.
Hot spots
A hash spreads keys evenly. It does nothing about load. If one key is far more popular than the rest, like a celebrity’s post or one huge customer, every request for it still lands on the one shard that owns it.
One key, too much love
The standard fix is key salting: append a small suffix (post:9001#0 … #9) so writes for one logical
key spread across up to ten shards. Reads must then fetch all ten sub-keys and combine them, so do it only for
keys you know are hot, and keep a record of which ones they are. DynamoDB’s own guidance calls this write
sharding.
The limits are concrete. Every DynamoDB partition is designed for at most 3,000 reads and 1,000 writes per second. DynamoDB will split a partition whose traffic crosses a threshold, choosing the split point from the keys it has actually seen requested. Its 2022 paper is explicit about what that can’t fix: a partition whose traffic goes to a single item, or whose key range is accessed sequentially, gains nothing from a split, so DynamoDB detects those patterns and doesn’t try.
Discord’s 2023 write-up is the best account of hot partitions in the wild. A busy channel hammered the nodes holding its partition, and because reads and writes used quorum consistency, the slowness spread to unrelated queries on those nodes. Their fix was partly a new database and partly a new layer: Rust data services that route by channel ID with consistent hashing and coalesce concurrent identical reads into one query.
Rebalancing
Over time you add machines, lose machines and grow data. Rebalancing moves shards so load evens out again. Whatever the scheme, you want three things: the load ends up fair, the database keeps serving during the move, and no more data moves than necessary.
How data moves
There are three common strategies.
- A fixed number of partitions. Create many more partitions than nodes on day one, and move whole
partitions between nodes. A key’s partition never changes, so nothing is rehashed. Redis Cluster has exactly
16,384 hash slots (
CRC16(key) mod 16384); an Elasticsearch index has its shard count fixed at creation. Notion split Postgres into 480 logical shards (one schema each) over 32 hosts in 2021, picking 480 because it divides evenly by many host counts. In 2023 they tripled the fleet to 96 hosts, five schemas each, moving schemas with Postgres logical replication; users saw at most about a second of a “saving” spinner. The catch: the count is a ceiling. Choose too few and each partition grows huge; choose too many and per-partition overhead dominates. - Dynamic splitting. Start with few partitions and split any that grow too big, merging ones that shrink. The number of partitions tracks the data. CockroachDB splits a range when it passes 512 MiB by default, and also splits on load: by default once a range uses more than 500 ms of CPU per second (or 2,500 QPS if the cluster balances by QPS). HBase and DynamoDB do the same. An empty database starts with one partition, so a bulk load hits one node until the first splits; some systems let you pre-split.
- Partitions proportional to nodes. Each node owns a fixed number of partitions (Cassandra’s tokens), so a new node takes a share from the others and the partition count grows with the cluster.
Moving a partition is itself a careful procedure. The safe pattern copies the data while the old owner keeps serving, catches up on writes that arrived during the copy, verifies, and only then flips ownership.
Online resharding
Vitess names its shards by the key range they own (-80 is everything below 0x80, 80- is the rest), so
splitting 0 into -80,80- is the whole operation. The copy and catch-up run online; the only interruption is
the write cutover, when the source primaries briefly reject writes while routing flips to the new shards.
Request routing
Once data moves, a client needs to find it. “Which node owns key K right now?” is a small instance of service discovery, with a twist: the answer changes during rebalancing.
Finding the owner
There are three designs, and real systems mix them.
- Any node forwards. Clients connect to any node, and the node forwards the request if it doesn’t own the key. Cassandra nodes learn the ring by gossip.
- A routing tier. A stateless layer that holds the map and proxies queries: Vitess’s VTGate, MongoDB’s mongos, Figma’s DBProxy, DynamoDB’s request routers. It’s also the natural place to plan scatter-gather queries. Figma’s DBProxy supports the subset of SQL covering about 90% of their queries, and allows joins only between tables in the same colo, on the shard key.
- Partition-aware clients. The client caches the map and goes straight to the owner. Kafka producers and
Redis Cluster clients work this way; a stale Redis client gets
MOVEDand retries.
The hard part is keeping the authoritative map correct while it changes. That is a consensus problem, so
most systems delegate it: Vitess keeps its topology in etcd, ZooKeeper or Consul, and HBase uses ZooKeeper.
CockroachDB stores range addresses in its own replicated meta1/meta2 ranges, and nodes cache what they read.
DynamoDB moved its partition metadata into an in-memory store called MemDS, and its routers refresh their
caches asynchronously on every hit, so the metadata fleet sees the same load whether caches are warm or cold.
Secondary indexes
Everything so far assumes the query names the partition key. A secondary index is how you query by anything else, and across shards it comes in two shapes.
Local vs global secondary indexes
- A local index (document-partitioned) lives inside each shard and covers only that shard’s rows. Writes stay local and transactional, but a query by the indexed value must ask every shard and merge. Its latency is the slowest shard’s, which is tail latency amplification in its purest form. Elasticsearch, MongoDB and Cassandra’s built-in secondary indexes work this way.
- A global index (term-partitioned) is itself partitioned by the indexed value, so all entries for “red” live in one place. Reads go to one index partition. But one row write can now touch several partitions, so most systems update global indexes asynchronously.
DynamoDB has both, and the names map imperfectly. A GSI is a true global index with its own partitions and capacity, supports eventually consistent reads only, and can be added at any time. An LSI shares the table’s partition key and only changes the sort key, so it lives with the base partition and allows strong reads, but it must be defined when the table is created, and each partition key value is capped at 10 GB across the table and its LSIs.
Trade-offs
| Choice | Wins | Costs |
|---|---|---|
| Range partitioning | range scans on one shard; splits follow the data | sequential keys create a hot shard |
| Hash partitioning | even spread of keys and writes | range scans hit every shard |
| Compound key (hash + sort) | spread across entities, order within one | queries must name the first part |
| Consistent hashing + vnodes | ~1/N of data moves per node change | more neighbours per node; uneven without many tokens |
| Fixed partitions | moves are whole partitions; no rehashing | partition count is a ceiling you pick up front |
| Dynamic splitting | partition count tracks data and load | a single hot key or sequential pattern can’t be split |
| Routing tier | thin clients; one place for scatter-gather plans | an extra hop and another fleet to run |
| Local index | cheap, transactional writes | every query fans out |
| Global index | one-partition reads | multi-partition writes, usually async and stale |
In the real world
- DynamoDB hashes the partition key, keeps each item collection sorted by the sort key, and keeps three replicas of each partition in different Availability Zones, kept in step with Multi-Paxos. Partitions split for size and for traffic. During Prime Day 2021, Amazon’s systems peaked at 89.2 million requests per second against it.
- Vitess shards MySQL. A Vindex maps a column to a keyspace ID, shards own ranges of keyspace IDs, VTGate routes, and Reshard or MoveTables workflows split shards online. Cross-shard transactions default to a best-effort mode, so atomicity across shards is opt-in; that’s the subject of Distributed Transactions.
- Figma (2024 write-up) hashes its shard keys (UserID, FileID, OrgID) because auto-increment and timestamp-prefixed IDs would have created hot shards. Groups of tables sharing a key form a colo that supports joins and transactions on that key. They first shard logically, using Postgres views on the old database so rollback is a config change, and only then move data physically. Their first physical failover cost about ten seconds of partial availability on primaries.
- Notion routes by workspace ID in application code: 480 logical shards, 32 hosts in 2021, 96 in 2023, with peak CPU and IOPS falling to about 20% afterwards.
- Discord partitions messages by
(channel_id, bucket). Hot channels pushed them to ScyllaDB and to coalescing data services; p99 for inserts went from 5–70 ms to a steady 5 ms. - Kafka hashes a record’s key to choose a partition, so order is guaranteed per key. Adding partitions to a topic changes that mapping, which is why topics are usually created with headroom.
Pitfalls
- Picking the key from the schema instead of the queries. The queries that don’t name it become fan-outs.
- Monotonic keys under range partitioning. Timestamps and auto-increment IDs make one hot shard. Hash them, or prefix them with something that spreads.
- “We hashed, so load is even.” Hashing evens out keys. One hot key still lands on one shard.
hash(key) mod Nwith a changing N. It moves almost every key. Use consistent hashing, jump hash, or a fixed partition count.- Unstable hash functions. A language’s built-in string hash may differ between processes. The mapping must be identical everywhere, forever.
- Too few fixed partitions. You can’t add more nodes than partitions, and re-partitioning later is a migration.
- Cross-shard features you assumed for free. Unique constraints, joins, and transactions across shards all need extra machinery, or a schema where related rows share a shard key.
Recall
Go deeper
- Elhemali et al., “Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service” (USENIX ATC 2022): partition limits, split for consumption, and why routing metadata needed its own store.
- Karger et al., “Consistent Hashing and Random Trees” (STOC 1997): the original ring, invented to relieve hot spots in web caches.
- Lamping & Veach, “A Fast, Minimal Memory, Consistent Hash Algorithm” (2014): jump consistent hash in five lines, and its limits.
- Vitess docs: Sharding and Resharding: keyspace IDs, range-named shards and the online split workflow.
- Sammy Steele, “How Figma’s databases team lived to tell the scale” (2024): choosing shard keys, colos, logical before physical sharding.
- Notion, “Herding elephants” (2021) and “The Great Re-shard” (2023): 480 logical shards and tripling the fleet without downtime.
- Discord, “How Discord Stores Trillions of Messages” (2023): hot partitions, request coalescing and a 177-node migration.
- CockroachDB docs: Load-Based Splitting: how a range decides where to split, and when splitting would hurt.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Transactions & Isolation (what “atomic” means on one machine) and Distributed Transactions (keeping it when a write spans shards).