Skip to content
notes.vinhnq.com

Search

System DesignSenior14 min read

Sharding in system design: choosing a shard key, four case studies and resharding

Review 11 cards
On this page

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 % 1024 never 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.

  1. 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.
  2. It’s small: the key appears in every table, every index and every routing decision. A bigint beats a long string.
  3. It has many distinct values (high cardinality): so data spreads evenly. country_code has 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 of order_id hold 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_entry rows, each sharded by its own account_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, not created_at, because message_id is 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 ShardRouter that picks a DataSource, for example Spring’s AbstractRoutingDataSource), or through a proxy (Vitess vtgate, 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_id when sharding by user_id → maintain an order_by_shop table sharded by shop_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:

  1. Background copy: snapshot + change capture (binlog/WAL, for example Debezium or Vitess VReplication) so the new DB catches up.
  2. Verify: compare row counts and checksums per logical shard.
  3. Cutover: block writes to those logical shards for a few seconds, wait for lag to reach 0, switch the routing map, reopen writes.
  4. 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_id is 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 by driver_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 % N makes 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.