Sharding
Split data across machines when one database is too big or too busy: range, hash and directory partitioning, consistent hashing, resharding, hot keys and cross-shard queries.
On this page
- The problem: the data outgrew the machine
- The idea: a key decides where each row lives
- Three ways to map keys to shards
- Worked example: how many shards?
- Adding shards: why "hash mod N" hurts, and consistent hashing
- Resharding without downtime
- Hot partitions: when hashing isn't enough
- Queries that cross shards
- When not to shard
- In the interview
- Quiz
The problem: the data outgrew the machine
An order system stores 50 TB and takes 40,000 writes a second at peak. A single well-tuned Postgres or MySQL primary manages thousands to low tens of thousands of simple writes a second, and 50 TB on one machine means backups that take a day and a restore that takes longer.
Replication does not help here. Every follower holds all 50 TB and applies all 40,000 writes. Followers scale reads; they do nothing for size or write load.
Too big and too busy for one machine
- Replicas copy all the data to every machine. But what if the data itself is too big for one machine, or there are too many writes for one leader? Then you split it up: that is sharding.
Sharding (also called partitioning) splits the data so that each machine holds only part of it. Each part is a shard. With 32 shards, each holds about 1.6 TB and takes about 1,250 writes a second, which any machine can handle. In practice each shard is also replicated, so a shard is a small leader-follower group, not one box.
The idea: a key decides where each row lives
Each shard holds a part; the shard key says which
- Each shard holds part of the data. Users A to M on one machine, N to Z on another, for example. Together they hold everything, and each one only does part of the work.
- The app needs a rule to find the right shard. That rule uses a shard key, a field like user ID. Given the key, the app always knows exactly which shard to ask.
Every row has a shard key (or partition key): a field such as user_id that the routing rule turns into a shard number. Given the key, the app (or a routing proxy) knows exactly which shard to ask, with no searching. The rule must be deterministic: the same key always goes to the same shard, until you deliberately move it.
Everything good and bad about a sharded system follows from that one choice of key:
- Queries that include the shard key go to one shard: fast and cheap.
- Queries that don't must ask every shard and merge the answers.
- If many requests share a key value, they all land on one shard, however many shards you have.
Three ways to map keys to shards
Range partitioning
Each shard owns a continuous range of keys: users A–F, G–M, and so on, or timestamps by month. Range scans are cheap ("all orders from 1 to 7 March" reads one or two shards), and ranges can be split when they grow, which is what HBase, Bigtable, CockroachDB and MongoDB's ranged sharding do automatically.
The weakness is uneven load. Keys are rarely spread evenly through their range, and sequential keys are the worst case: if the key is a timestamp or an auto-increment ID, every new write goes to the shard holding "now", while the others sit idle.
A bad key: one shard does most of the work
- Choose the key badly and you get a hot shard. Split by country, and the shard holding your biggest country does most of the work while the others sit idle.
Hash partitioning
Run the key through a hash function and use the result to pick a shard. A good hash scatters even neighbouring keys (user:1001, user:1002) to unrelated shards, so load spreads evenly. Cassandra, DynamoDB, Redis Cluster and most key-value stores work this way.
Hashing the key spreads load evenly
- A common fix is hash-based sharding: run the key through a hash function, which scatters keys evenly, so every shard gets a fair share.
The price is that range queries across keys no longer work: users 1000–2000 are scattered everywhere. A common compromise is a compound key: hash the first part to choose the shard, then sort by the second part inside it. In Cassandra, PRIMARY KEY ((user_id), created_at) puts all of one user's orders on one shard, in time order, so "this user's last 20 orders" is a single sorted read.
Directory (lookup) partitioning
Keep an explicit table: tenant 42 → shard 7. Any key can go anywhere, and moving one big customer to its own shard is a single update. Multi-tenant SaaS products often work like this, and Vitess can route by a stored mapping like this (its lookup vindexes are mostly used as secondary-index mappings). The catch: every request needs the mapping, so the directory must be fast, cached and highly available, or it becomes the new single point of failure.
| Method | Good at | Weak at | Use when |
|---|---|---|---|
| Range | Range scans, ordered reads, splitting a range that grew | Hot spots on sequential or skewed keys | Time series with a compound key, ordered data, systems that split ranges automatically |
| Hash | Even spread of load and data | Range queries across keys; adding shards needs care | The default for key-value lookups by ID |
| Directory | Full control; move one tenant at will | Extra lookup on every request; the directory must never go down | Multi-tenant apps with a few huge customers |
Worked example: how many shards?
Take the order system: 50 TB today, growing 50% a year; 40,000 writes/s and 200,000 reads/s at peak. Plan each shard to hold at most 2 TB (so backups, restores and rebuilding a replica take hours, not days) and to take at most 4,000 writes/s (well under one primary's limit, leaving headroom).
| Limit | Calculation | Shards needed |
|---|---|---|
| Storage | 50 TB ÷ 2 TB | 25 |
| Writes | 40,000 ÷ 4,000 | 10 |
| Take the larger, plus one year of growth | 25 × 1.5 ≈ 38 | ~40 |
| Machines with a leader and two followers per shard | 40 × 3 | 120 |
| Reads per machine | 200,000 ÷ 120 | ~1,700/s, easy |
Storage, not writes, decides the count here. Notice also that you plan for growth up front, because adding shards later means moving data (below).
Adding shards: why "hash mod N" hurts, and consistent hashing
The obvious rule is shard = hash(key) % N. It spreads load perfectly, until N changes. Going from 4 shards to 5 changes the result for about 80% of keys (in general N/(N+1) of them), so almost all the data has to move at once.
Consistent hashing fixes this. Picture the hash space as a ring. Each server is placed on the ring by hashing its name, and each key belongs to the first server clockwise from the key's position. Adding a server takes over only the keys between it and the server before it; every other key stays where it was.
On a ring, a new shard takes over one slice
- Adding a shard later is tricky. With a simple “hash mod number of shards” rule, almost every key moves. Consistent hashing places shards on a ring, so adding one only moves a small slice of the keys.
With one point per server the ring is lumpy, though: the gaps between servers are random, so one server can own twice the keys of another, and when a server dies its whole arc falls onto a single neighbour. The fix is virtual nodes: each server takes many points on the ring (100–256 is common), so its share is the sum of many small slices and evens out.
Virtual nodes even out the ring, and a new server takes a little from everyone
Here is a complete ring with virtual nodes. The demo adds a fifth server and counts how many of 100,000 keys moved: about 20% (one fifth), against 80% for hash mod N.
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
public class HashRing {
private final TreeMap<Long, String> ring = new TreeMap<>(); // point on the ring -> node
private final int vnodes;
public HashRing(int vnodes) { this.vnodes = vnodes; }
public void addNode(String node) {
for (int i = 0; i < vnodes; i++) ring.put(hash(node + "#" + i), node);
}
public void removeNode(String node) {
for (int i = 0; i < vnodes; i++) ring.remove(hash(node + "#" + i));
}
public String nodeFor(String key) {
if (ring.isEmpty()) throw new IllegalStateException("no nodes");
Map.Entry<Long, String> e = ring.ceilingEntry(hash(key)); // first point at or after the key
return (e != null ? e : ring.firstEntry()).getValue(); // wrap around past the top
}
private static long hash(String s) {
try {
byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
long h = 0;
for (int i = 0; i < 8; i++) h = (h << 8) | (d[i] & 0xff);
return h;
} catch (NoSuchAlgorithmException ex) {
throw new IllegalStateException(ex);
}
}
public static void main(String[] args) {
HashRing ring = new HashRing(100);
for (String n : new String[] {"db-a", "db-b", "db-c", "db-d"}) ring.addNode(n);
Map<String, String> before = new HashMap<>();
for (int i = 0; i < 100_000; i++) before.put("user:" + i, ring.nodeFor("user:" + i));
ring.addNode("db-e");
long moved = before.entrySet().stream()
.filter(e -> !ring.nodeFor(e.getKey()).equals(e.getValue())).count();
System.out.printf("%d%% of keys moved%n", moved * 100 / before.size()); // about 20%
}
}import bisect, hashlib
class HashRing:
def __init__(self, vnodes=100):
self.vnodes = vnodes
self.points = [] # sorted points on the ring
self.owner = {} # point -> node
@staticmethod
def _hash(s):
return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")
def add_node(self, node):
for i in range(self.vnodes):
h = self._hash(f"{node}#{i}")
self.owner[h] = node
bisect.insort(self.points, h)
def remove_node(self, node):
for i in range(self.vnodes):
h = self._hash(f"{node}#{i}")
del self.owner[h]
self.points.remove(h)
def node_for(self, key):
if not self.points:
raise LookupError("no nodes")
i = bisect.bisect_left(self.points, self._hash(key)) # first point at or after the key
return self.owner[self.points[i % len(self.points)]] # wrap around past the top
ring = HashRing()
for n in ["db-a", "db-b", "db-c", "db-d"]:
ring.add_node(n)
keys = [f"user:{i}" for i in range(100_000)]
before = {k: ring.node_for(k) for k in keys}
ring.add_node("db-e")
moved = sum(ring.node_for(k) != before[k] for k in keys)
print(f"{moved / len(keys):.0%} of keys moved") # about 20%MD5 is used here only to spread keys, not for security; production systems usually use a faster non-cryptographic hash such as MurmurHash or xxHash. Cassandra and the original Dynamo paper are built on this ring idea (the DynamoDB service hides it behind a partition map that splits partitions automatically). Two alternatives worth naming: a fixed number of slots mapped to nodes (Redis Cluster's 16,384 slots), and rendezvous hashing, where each key picks the node with the highest hash(key, node) score.
Resharding without downtime
Whatever the scheme, moving data between machines while the app keeps running follows the same steps:
- Copy a snapshot of the partition to its new home.
- Catch up by replaying the changes made since the snapshot, from the source's change log.
- Cut over: briefly pause writes to that partition (milliseconds to seconds), apply the last changes, and switch the routing table.
- Clean up the old copy once nothing reads it.
Vitess, MongoDB's balancer and Citus automate this; DynamoDB splits partitions on its own as they grow.
Hot partitions: when hashing isn't enough
Hashing spreads different keys evenly. It cannot split one key. If a celebrity's post gets 100,000 likes a second, every one of those writes hashes to the same shard. DynamoDB, for example, limits each partition to about 1,000 write units and 3,000 read units a second, so one hot key is throttled no matter how big the table is.
Queries that cross shards
A query without the shard key asks every shard
- One more trade-off: a query that needs data from many shards, like “top sellers across all users”, must ask every shard and combine the answers. Pick a shard key that keeps your most common queries on one shard.
Secondary indexes: local or global
Orders are sharded by user_id, but support staff search by product_id. There are two ways to index a field that is not the shard key.
Local index: ask everyone. Global index: ask the index, then only the shards that matter
| Local index (per shard) | Global index (sharded by the indexed field) | |
|---|---|---|
| Write | Cheap: the index lives with the row, updated in the same transaction | Expensive: the index entry may live on another shard, so it is updated separately, usually asynchronously |
| Read | Scatter-gather to every shard | One index shard, then only the shards holding matches |
| Freshness | Always in step | Can lag behind the data |
| Examples | Cassandra secondary indexes, MongoDB, Elasticsearch | DynamoDB global secondary indexes (eventually consistent), a separate search index fed by CDC |
Scatter-gather and the tail
Asking every shard is fine for rare admin queries, but it costs more than it looks. Each extra shard adds load, and the query is only as fast as the slowest shard. If each shard is slower than its 99th-percentile latency 1% of the time, a query that waits for 32 shards hits at least one slow shard in 1 − 0.99³² ≈ 28% of requests. Fan-out turns a rare slow response into a common one.
Joins and transactions across shards
- Co-locate data that is used together by giving it the same shard key:
ordersandorder_itemsboth keyed byuser_idjoin locally. Citus and Vitess call these co-located tables. - Denormalise: copy the product name into the order row, so the order page needs no join.
- Transactions across shards need two-phase commit (a coordinator asks every shard to prepare, then tells all of them to commit; if it crashes in between, the shards wait holding locks), or a saga (a chain of local transactions, each with a compensating "undo" step). Both are slow and complex, so the best design keeps each transaction inside one shard.
- IDs: per-shard auto-increment collides across shards. Use UUIDs or Snowflake-style IDs (timestamp + machine + sequence).
When not to shard
- It still fits on one machine. A large server today has dozens of cores, terabytes of RAM and tens of terabytes of fast SSD. Scaling up, adding read replicas, caching and archiving old rows are all cheaper than sharding.
- Your main queries don't share a key. If half the traffic is by user and half by product, every choice makes half the queries scatter. Consider a store with global indexes, or a separate search system.
- You need many cross-entity transactions. Sharding turns them into distributed transactions. A distributed SQL database (CockroachDB, Spanner, YugabyteDB) shards for you and keeps transactions, at a latency cost.
Sharding is close to a one-way door: once data and code assume it, going back is very hard. Do it when the numbers demand it, not before.
In the interview
A chat app stores 2 trillion messages (about 200 TB) and adds 1 M messages a second. The main queries are "the latest 50 messages in this conversation" and "older messages before this one" when scrolling. Pick the shard key and the partitioning method, and say what happens with a 100,000-member group chat.
Compare with our answer
A strong answer mentions:
- Shard by
conversation_id, hashed, so one conversation's messages live together and the two main queries hit one shard. - Sort inside the shard by message ID or time (a compound key such as
((conversation_id), message_id)), so "latest 50" and "before X" are sorted range reads. - Not by
message_idor time alone: that scatters a conversation (or puts all new writes on one shard). - Bucket huge conversations, e.g.
(conversation_id, month), so one partition doesn't grow without limit. - The giant group is a hot partition: buffer and batch its writes, cache its recent messages, or give it dedicated capacity.
- Rough sizing: 200 TB ÷ 2 TB ≈ 100+ shards, and 1 M writes/s spread over them.
A team shards an events table by created_at month using range partitioning, and routes with shard = hash(month) % 4 on each app server. They plan to add a fifth shard next quarter. List what will go wrong.
Compare with our answer
A strong answer mentions:
- Every new write goes to the current month's shard: a hot shard by design, while the other three idle. (Hashing the month doesn't help: one month is one key.)
- Queries by user or event type must scatter to every shard.
% 4→% 5moves about 80% of the data at once.- Each app server holds its own copy of the rule, so during a change some servers route differently: writes land on the wrong shard.
- Fix: shard by a high-cardinality key such as
user_idorevent_id(hashed), keep time as a sort key inside the shard, use consistent hashing or logical shards, and route via a versioned table or a proxy.
- Why: data or writes too big for one machine. Replicas don't help writes; shards do. Each shard is itself replicated.
- Shard key decides everything: queries with it hit one shard; without it, every shard.
- Range: good scans, hot spots on sequential keys. Hash: even spread, no cross-key ranges. Directory: total control, needs a highly available lookup.
- Compound keys: hash the first part to pick the shard, sort by the second inside it.
- Sizing: max(data ÷ ~1–2 TB, writes ÷ safe writes per shard) × growth; × 3 for replicas.
hash mod Nmoves N/(N+1) of keys on growth (80% for 4 → 5). Consistent hashing moves about 1/(N+1). Virtual nodes even out the ring. Or use many logical shards (Redis Cluster's 16,384 slots).- Resharding: copy, catch up from the log, short cut-over, redirect stale clients (
MOVED, versioned tables). - Hot key: salting, caching, write batching, a dedicated shard.
- Secondary indexes: local = cheap writes, scatter reads; global = one-shard reads, async and lagging writes.
- Cross-shard: scatter-gather tail latency (1 − 0.99³² ≈ 28%), co-locate, denormalise, avoid distributed transactions.
1. A ride-hailing app shards its trips table. The most common query is "show this rider's past trips". Which shard key fits best?
Matching the key to the main query makes it a one-shard read. Trip ID spreads evenly but scatters a rider's trips; start time puts every new write on one shard; city creates hot shards for big cities.
2. A cluster of 4 shards uses shard = hash(key) % N. The team adds a 5th shard. Roughly what share of keys must move?
A key stays put only if hash % 4 equals hash % 5, which happens for about 1 in 5 keys. Consistent hashing would move only about 20%.
3. Why do consistent-hashing systems give each server many virtual nodes instead of one point on the ring?
Many small slices per server average out the random spacing, and when a server leaves, its slices are spread across many others. Replication is a separate mechanism (often "the next N distinct servers clockwise").
4. Orders are hash-sharded across 32 shards by user ID. Each shard is slower than its p99 latency 1% of the time. A report queries all 32 shards and waits for every answer. About how often is the report slowed by at least one slow shard?
The chance all 32 are fast is 0.99³² ≈ 0.72, so about 28% of queries hit a slow one. Scatter-gather amplifies tail latency.
5. A celebrity's post receives 50,000 likes per second, and the like counter's shard is throttled, though the cluster has 200 shards. What helps most?
One key always hashes to one shard, so adding shards does nothing for it. Salting spreads that key's writes across several shards; batching increments in memory helps too.
6. An e-commerce site shards orders by user ID and adds a global secondary index on product ID, updated asynchronously. What should the team expect?
A global index is partitioned by the indexed field, so lookups are targeted. Because it lives on other machines and is updated asynchronously, it lags the data slightly.
7. During a live migration, some app servers keep an old copy of the routing table and send writes to a shard that has handed off that data. Which design handles this safely?
A shard that no longer owns a key must refuse it and say where it went (Redis Cluster's MOVED/ASK), or requests must carry a routing-table version that shards check. Accepting the write silently risks lost or diverging data.
Score 60% or more and the lesson is marked complete.