On this page
Description
Replication gives you more copies of the same data. Sometimes that isn't enough: the data itself, or the write load, outgrows one machine. A messaging app with 40 TB of messages and 80,000 writes a second can't fix that with replicas, because every replica would still store all 40 TB and apply every write. The data has to be split: each node - a shard, or partition - holds only a slice.
Splitting is the easy part. The hard part is splitting so that each request touches as few shards as possible, the load stays even, and you can add machines later without moving everything. In this lesson:
- The shard key - the one choice that decides the rest.
- Hash versus range partitioning.
- Why
hash mod Nhurts when you add a node, and how consistent hashing fixes it. - Hot partitions, and splitting a single huge key.
- Queries and transactions that span shards.
- A checklist for choosing a shard key.
The shard key
Every row is assigned to a shard by its shard key. Choose it from the hot query:
- "Messages in conversation X, newest first" → shard by
conversation_id. Each conversation lives on one shard; reading it is a single-shard range scan. - Shard by
sender_idinstead and reading a conversation means gathering messages from every participant's shard. - Shard by timestamp and all of today's writes land on the same shard.
The key decides both locality (what can be read from one shard) and balance (whether load is even).
Hash versus range partitioning
| Hash partitioning | Range partitioning | |
|---|---|---|
| Assign by | hash(key) | Key ranges (A-F, G-M, ...) |
| Balance | Even, for many keys | Uneven if keys cluster (e.g. by time) |
| Range scans across keys | Scatter to every shard | Efficient - neighbors are together |
| Typical use | User IDs, conversation IDs | Time-ordered data within a key, alphabetical ranges |
Many systems combine them: hash on the first part of a compound key (conversation_id) and keep rows sorted by the second part (sent_at) within the partition.
hash mod N, and why it hurts
The simplest mapping is shard = hash(key) mod N. Adding a node changes N - and changes the answer for most keys. Going from 4 shards to 5, a key stays put only if h mod 4 = h mod 5, which happens for 4 of every 20 values of h mod 20: 80% of the data moves. For a 40 TB dataset that's a migration nobody wants.
Consistent hashing
Put both nodes and keys on a ring (hash values from 0 to 2^32). A key belongs to the first node clockwise from its position. Adding a node claims only the arc between it and its predecessor - about 1/N of the keys (20% going from 4 to 5) - and nothing else moves. Removing a node hands its arc to the next one.
Two refinements make it practical:
- Virtual nodes. Each physical node takes many positions on the ring (say 100). Arcs even out statistically, bigger machines can take more positions, and when a node fails its many small arcs are spread over all the others instead of doubling one neighbor's load.
- Replication along the ring. Store each key on the next few distinct nodes clockwise, so losing one node loses no data.
Cassandra, DynamoDB and many caches use this scheme.
Hot partitions
Even with a good key, some partitions run hot:
- Time-ordered range keys send every new write to the newest range. Hash the key or put a hashed prefix before the timestamp.
- One enormous key - a celebrity's follower list, a viral post's like counter - lives on one shard whatever the scheme; consistent hashing can't split a single key. Split it yourself: write to
likes:post42#0..#15(a random sub-key per write) and sum the sub-keys on read, or handle the few huge keys with a separate path.
Queries across shards
A query by anything other than the shard key has two options:
- Scatter-gather: send it to every shard and merge the results. Fine for rare admin queries; expensive for hot paths, and its latency is the slowest shard's.
- A global secondary index: a second table partitioned by the other attribute (users by city → shard by city, listing user IDs), updated asynchronously when users change. Fast reads, eventually consistent.
Transactions across shards - moving money between two accounts on different shards - need a distributed protocol: two-phase commit (a coordinator asks both to prepare, then commit; blocking if it fails mid-way) or a saga (a local transaction on each shard, with compensating actions if a later step fails). Both cost latency and complexity, which is the real reason to choose a shard key that keeps common operations on one shard.
Choosing a shard key: a checklist
| Question | Good sign |
|---|---|
| Does the hottest query include the key? | Yes - it's served by one shard |
| Do common multi-row writes share the key? | Yes - no cross-shard transactions |
| Are there many distinct key values? | Millions - load can spread |
| Is any single key huge or very hot? | No - or it has a plan (sub-keys) |
| Is the key monotonic (time, sequence)? | No - or it's hashed first |
| Will the key ever change for a row? | No - moving a row between shards is expensive |
Going further. The deep dive (next tab) simulates how even the load really is with and without virtual nodes, measures how much data moves under each scheme, and covers jump and rendezvous hashing, logical partitions, online resharding, and the real cost of two-phase commit versus sagas.
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why is consistent hashing better than hash mod N when you add a node?
Show answer
hash mod N changes almost every key's shard when N changes (80% of keys move from 4 to 5 nodes). Consistent hashing moves only the keys in the new node's arc - about 1/N.
2. Orders are range-partitioned by created_at month. Where do today's writes go?
Show answer
All to the shard holding the current month - one hot shard while the others sit idle for writes. Hash-partition by order or customer ID instead (and keep time as a sort key within the partition).
3. Users are sharded by user ID. How do you serve "all users in Boston" quickly?
Show answer
A global secondary index partitioned by city (city → user IDs), updated asynchronously as users change - or accept a scatter-gather query across all shards if it's rare.
Key takeaways
- Shard when data or writes outgrow one node; replicas don't help there.
- The shard key follows the hot query - locality first, balance second.
- Hash partitioning balances; range partitioning keeps neighbors together but can create hot shards.
- hash mod N moves most keys on resize; consistent hashing moves about 1/N. Use virtual nodes.
- A single huge key stays hot - split it into sub-keys.
- Off-key queries scatter or use a global index; cross-shard writes need 2PC or sagas.