Data in system design series: 1. Choosing a database · 2. Sharding: shard keys and resharding
Partitioning inside one server is covered in JOINs and partitioning. This post goes on to many servers: when to shard, how to pick a shard key through four real problems, and how to add shards without stopping the system.
1. When you need to shard
Key idea: shard when one node (even with good indexes, cache, replicas and partitions) can’t handle the write load or the data size. For read-heavy load, replicas and cache are usually enough.
Suggested thresholds, not rules:
| Signal | Reference threshold |
|---|---|
| Rows in one table | ≥ 50M: partition; ≥ 200M: consider sharding |
| Write load | ≥ 3,000 TPS sustained |
| Latency | p99 of common queries > 120 ms even after tuning |
| Maintenance | VACUUM, index builds, backups take hours |
Sharding costs you a lot: global unique and foreign keys, cross-shard transactions and joins, global secondary indexes, routing, rebalancing. The full list is in the “Partition or shard” table in the partitioning post.
2. Range, hash and consistent hashing
Key idea: the sharding strategy decides two things: whether data spreads evenly, and whether range queries stay cheap. No strategy gives you both.
| Strategy | How it works | Pros | Cons |
|---|---|---|---|
| Range | created_at 2024 → shard 0, 2025 → shard 1… |
Simple, matches the business, cheap range queries | Needs tuning to stay even; hot spots |
| Hash | hash(key) % N |
Spreads both data and load evenly | Range queries hit every shard; unusually hot keys still happen |
| Directory | A lookup table key → shard |
Flexible, can move single keys | The lookup table is a point of failure and a bottleneck, must be cached |
A range hot spot example: a news feed partitions the post table by created_date, and 98% of traffic hits the newest partition. Shard that way and one machine does all the work while the rest sit idle.
Hash is the default, but hash % N has a hole: add one shard (N → N+1) and about N/(N+1) of the keys move. Two fixes:
- Logical shards: pre-split into many logical shards (say 1,024).
hash % 1024never changes; only the “logical shard → physical server” map changes when you add machines. Redis Cluster does exactly this with 16,384 slots. - Consistent hashing: put servers and keys on a hash ring; a key belongs to the nearest server going clockwise. A new server only takes keys from one arc of the ring, so about 1/N of the keys move. Use many virtual nodes per server to keep it even. Cassandra and DynamoDB use this idea.
flowchart LR
K[order user_id=42] --> H["hash(42) % 1024 = 517"]
H --> M{Logical → physical map}
M -->|0–255| D0[(DB 0)]
M -->|256–511| D1[(DB 1)]
M -->|512–767| D2[(DB 2)]
M -->|768–1023| D3[(DB 3)]
3. Choosing a shard key: three properties
Key idea: list the most common queries first, then pick a key those queries always carry. A good key meets as many of these three properties as possible.
- It’s the reference entity: related data sits on one shard, so the main queries don’t hit many shards. For example, orders and order items both go by
user_id. - It’s small: the key appears in every table, every index and every routing decision. A
bigintbeats a long string. - It has many distinct values (high cardinality): so data spreads evenly.
country_codehas only ~200 values; if Vietnam has most of the users, one shard is overloaded.
One more practical condition: the key doesn’t change over time. Shard by the user’s city_id and you have to move data every time a user moves house.
4. Four case studies
Key idea: the same line of thinking (main query → key → primary key) gives four different answers, including “don’t shard”.
| System / table | Main queries | Strategy, key | Primary key |
|---|---|---|---|
E-commerce / order |
Create an order, a user’s order history, order details | HASH(user_id) |
(order_id, user_id) |
Payments / transaction |
Create a transaction, history for both debit and credit sides, details | Don’t shard (until you must) | transaction_id |
Monitoring / metric_log |
Write device metrics by time, view one device’s history, delete old data | HASH(device_id) then nested RANGE(timestamp); better: a time-series DB |
(device_id, timestamp) |
Chat (Discord) / message |
Send a message, view a channel’s history | HASH(channel_id) |
(channel_id, message_id), sorted by message_id |
A few points that need explaining:
- Order: “order details” only has
order_id. A neat trick is to embed the shard key in the ID: a few bits oforder_idhold the user’s logical shard, so reading the ID tells you the shard, no lookup needed. - Transaction: one transaction belongs to two accounts. Shard by the debit side and the credit side’s history has to ask every shard. When you really must shard, the double-entry model helps: each transaction produces two
ledger_entryrows, each sharded by its ownaccount_id, written with a saga/outbox instead of one transaction. - Metric: nested partitioning works but is hard to operate; TimescaleDB does it for you (see choosing a database).
- Discord: sorted by
message_id, notcreated_at, becausemessage_idis a Snowflake ID: increasing over time, unique, and no collisions when two messages arrive in the same millisecond.
Snowflake IDs and embedding the shard in the ID
A Snowflake ID is a 64-bit number: 1 sign bit, 41 bits of milliseconds since an epoch (enough for ~69 years), 10 machine bits (1,024 machines), 12 sequence bits (4,096 IDs per ms per machine). Consequences:
- Sorting by ID ≈ sorting by time, so one index
(channel_id, message_id)both locates the channel and paginates by time. - No coordination between machines to hand out IDs.
- A clock that jumps backwards (NTP adjustment) can produce duplicates; a good implementation waits or refuses when it notices.
Embedding the shard: replace the 10 machine bits with 10 bits for the user’s logical shard (Instagram did something like this with PostgreSQL schemas). Then order_id carries its own shard, and “order details by id” goes straight to the right shard.
Minimal Java code:
long nextId(long logicalShard) { // 0..1023
long now = System.currentTimeMillis() - EPOCH;
synchronized (this) {
if (now == lastMs) {
seq = (seq + 1) & 0xFFF;
if (seq == 0) now = waitNextMs(lastMs); // used up all 4,096 IDs in this ms
} else {
seq = 0;
}
lastMs = now;
return (now << 22) | (logicalShard << 12) | seq;
}
}
5. Cross-shard queries and routing
Key idea: every query without the shard key is expensive. Design so common queries always carry the key, and replicate data for the rest.
- Routing: in the application (a
ShardRouterthat picks aDataSource, for example Spring’sAbstractRoutingDataSource), or through a proxy (Vitessvtgate, ShardingSphere-Proxy). - Scatter-gather: ask every shard and merge. Fine for rare admin tasks, not for user-facing APIs: latency equals the slowest shard and load is multiplied by N.
- Global secondary index: to find orders by
shop_idwhen sharding byuser_id→ maintain anorder_by_shoptable sharded byshop_id, updated asynchronously through outbox/CDC. Or push it to Elasticsearch. - Joins: only within one shard (same key). Small tables that rarely change (categories, config) are replicated to every shard.
- Global pagination (the 20 newest orders across the whole system): take the top 20 from each shard and merge; it’s expensive, so it’s usually read from an analytics store.
6. Resharding without downtime
Key idea: do it once for several years (many logical shards, few physical ones), so later resharding just moves whole logical shards to new machines instead of rehashing every row.
Example starting point: 1,024 logical shards on 16 physical databases (64 logical per DB). When one DB is overloaded, move half of its logical shards to a new DB:
- Background copy: snapshot + change capture (binlog/WAL, for example Debezium or Vitess VReplication) so the new DB catches up.
- Verify: compare row counts and checksums per logical shard.
- Cutover: block writes to those logical shards for a few seconds, wait for lag to reach 0, switch the routing map, reopen writes.
- Clean up: keep the old data for a while so you can roll back, then delete it.
Each physical shard should have a primary + replicas like any normal database. Reading from replicas means dealing with replication lag: a “write then read it back” flow (read-your-writes) should read from the primary, or pin the user to the primary for a few seconds after a write.
Exercises
Exercise 1: Sharding the trips table of a ride-hailing app
Task: a trip table with 2 billion rows and 4,000 new trips/s at peak. Queries: (a) a driver views their current trip and history, (b) a rider views their history, (c) operations view every active trip in a city, (d) customer support looks up a trip by trip_id. Pick a shard key, a primary key, and a way to serve all four queries.
Solution to Exercise 1
- There are two natural “owners”, the rider and the driver, just like the payments problem. Pick
HASH(rider_id)for the main table, because there are many riders, they spread evenly, and rider history is the most frequent query. trip_idis a Snowflake ID with the rider’s logical shard embedded → (d) goes straight to the shard.- (a) A side table
trip_by_driver(driver_id, trip_id, started_at, summary)sharded bydriver_id, updated through outbox → Kafka. A driver’s current trip lives in Redis (driver:{id}:current_trip), no DB needed. - (c) “Active trips per city” is hot, small data (tens of thousands of trips): keep it in Redis/a stream keyed by
city_id, or in a service that tracks trip state; don’t scatter-gather the DB. - Primary key of the main table:
(rider_id, trip_id). 1,024 logical shards on 8 DBs to start: 4,000/8 = 500 write TPS per DB, leaving room for 2–3× growth.
Remember
- Name the signals that you need to shard, and why read-heavy load usually doesn’t need it yet.
- Explain why
hash % Nmakes resharding painful, and how logical shards / consistent hashing fix it. - Pick a shard key for orders, transactions, metrics and messages, and explain the primary key.
- Know four ways to handle queries without the shard key.
- Walk through the steps of resharding without downtime.
Interview questions
Mid
How do partitioning and sharding differ?
Partitioning splits one table into pieces on the same server; sharding splits data across many servers.
Partitioning lets you read less and delete old data cheaply, but it doesn’t raise write capacity beyond one machine. Sharding raises write capacity and storage, but you lose transactions, joins and global uniqueness.
Range or hash sharding, which do you pick?
Hash by default, because it spreads data and load evenly; pick range when range queries dominate and load is spread evenly across the ranges.
Range by time almost always creates a hot spot on the newest range. Hash loses range queries across keys, so combine them: hash by entity, sort by time within the shard.
What properties does a good shard key have?
It’s the root entity of the main queries, it’s small, it has many distinct values, and it doesn’t change over time.
Example: user_id for orders. A user’s order history sits on one shard, a bigint is small, there are millions of values, and a user never changes their id.
Senior
How would you shard the transaction table of a payment system?
Put off sharding as long as possible, because a transaction belongs to two accounts; when you must shard, switch to double-entry and shard each entry by its own account_id.
Each transaction produces two ledger_entry rows (debit, credit), each on its own account’s shard, so every account’s history is a single-shard query. The two writes are on two shards, so use a saga/outbox plus reconciliation, with an idempotency key per entry.
You have 8 shards with hash % 8 and need to go to 12. How?
Going from 8 to 12 with hash % N moves about 2/3 of the rows; switch to logical shards instead (say 1,024) and only move whole logical shards.
Steps: add a column/function that computes the logical shard, build a logical → physical map that matches the current 8 shards, then gradually move some logical shards to the 4 new machines with CDC, verify checksums, and cut over group by group with a few seconds of blocked writes.
How does Discord store messages so channel history reads are fast?
Partition by channel_id and sort within the partition by message_id, a Snowflake ID, so a channel’s history is one sequential read on one node.
Very large channels make partitions too big, so they add a time bucket to the partition key (channel_id, bucket), where the bucket is a fixed window (for example 10 days). They moved from Cassandra to ScyllaDB because of GC and compaction latency.
How do you find orders by shop_id when the order table is sharded by user_id?
No scatter-gather on the API; keep a copy of the data keyed by shop_id (a side table sharded by shop_id, or an Elasticsearch index) updated asynchronously.
The source of truth is still the table sharded by user. The copy is updated through outbox/CDC → Kafka, accepts a few seconds of delay, and has a reconciliation job. Very large shops may need a secondary shard by (shop_id, month).
Useful phrases for interviews
- “The shard key must appear in every hot query.”
- “Range sharding by date creates a hot spot on the newest shard.”
- “Without the shard key, the query becomes a scatter-gather.”
- “Consistent hashing moves only about one N-th of the keys.”
- “We pre-split into 1,024 logical shards and move them as a whole.”
- “Resharding is a cutover, not a rehash of every row.”
- “Country code has too low cardinality to be a shard key.”
- “Orders and order items are co-located by user id.”
- “The cutover blocks writes for a few seconds.”
- “Double-entry rows let us shard the ledger by account.”
Notes based on the System Design course (Ronin Engineer), rewritten in my own words.