Partitioning · 1 of 1

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.

≈ 25 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

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:

  1. Which key decides where a record lives?
  2. How does the key map to a shard: by range, or by hash?
  3. What happens when one key, or one shard, gets too much traffic?
  4. How does data move when you add a machine?
  5. How does a request find the right shard?
  6. 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

key space →Shard 1 · a–dShard 2 · e–hShard 3 · i–ladabocydeeelifaygushalivyjokailu
Twelve keys, three shards. Range keeps order and pays for it in hot spots; hash spreads load and pays for it in scans.

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

hashmod 4mod 517BC42CC8AD91DB63DD30CA76AB55DA24AE99DE12AC38CD10 of 12 keys change node
mod N reshuffles almost everything. A ring moves one arc.

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

More shards can't help a single key. Splitting the key can.

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.

3,000 / 1,000reads / writes per second one DynamoDB partition is designed for
177 → 72nodes when Discord moved its messages from Cassandra to ScyllaDB (2022)
40–125 → 15 msDiscord's p99 for reading message history, before and after

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

Node 1Node 2Node 3Node 4 · not yetp0p1p2p3p4p5p6p7p8p9p10p1112 partitions, fixed forever · key → partition never changes
Move whole partitions, or split the ones that grow.

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's Reshard workflow, step by step. The only pause is the switch.

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

Three places to put the map, and what happens when it goes stale.

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 MOVED and 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

Pay at read time (scatter-gather) or at write time (cross-shard index updates).
  • 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 N with 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

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).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Partitioning: roadmapBack to the roadmap