System Design HLD-07.04
Partitioning and sharding
Splitting data across many databases: range, hash and directory partitioning, choosing a shard key, cross-shard queries, and the pain of resharding.
The big idea
Replication copies the whole dataset to more machines, which helps reads and availability but not size or write volume: every replica still holds everything and applies every write. When the data no longer fits on one machine, or one machine cannot absorb all the writes, you must split it. PartitioningSplitting a dataset into disjoint pieces, each stored and served by a different database node., called sharding when the pieces live on separate database servers, divides the rows so each shardOne piece of a partitioned dataset, held by its own database node, usually with its own replicas. holds a manageable part and handles only that part's traffic.
Everything about sharding revolves around one decision: the shard keyThe column or value used to decide which shard a row belongs to.. A good shard key spreads data and traffic evenly and keeps the queries you run most often on a single shard. A bad one creates hot shards, forces queries to visit every shard, and is very painful to change later.
Think of a library that outgrows its building and opens branches. Split books by author's surname and readers looking for one author visit one branch; split them by color and every search visits every branch.
How it works
Step 1: A router in front of shards
The routing logic can live in the application (a library), in a proxy (such as Vitess for MySQL), or in the database itself (distributed databases do it internally).
Step 2: Three ways to assign keys
- Range partitioning: each shard owns a range of the key (customers 0 to 249,999 on shard 1, and so on). Range scans are efficient and neighbors stay together. But if the key increases over time, like a timestamp or an auto-increment id, every new write lands on the last shard: a write hotspot.
- Hash partitioning: shard = hash(key) mod number of shards, or better, consistent hashing ( Consistent hashing ). Data and load spread evenly, but range queries must visit every shard, and naive modulo moves almost everything when you add shards.
- Directory-based: a lookup table records which shard each key (or tenant) lives on. Maximum flexibility, including moving a big customer to its own shard, at the cost of an extra lookup and a directory that must be highly available.
Many systems split into many small logical shards (say 480 or 4,096) mapped onto fewer physical servers. Moving a logical shard to a new server is much easier than re-splitting data.
Try it
Try this:
- customer_id, hash: rows spread reasonably, and one customer's orders live on one shard. Look for the shard holding a very big customer.
- created_at, range: today's writes all land on the last shard, the classic time-based hotspot.
- country, hash: a handful of values for many rows: some shards are huge, some nearly empty.
- order_id, hash: perfectly even, but "orders of customer 1" now touches every shard.
Step 3: What gets harder
- Cross-shard queries: anything without the shard key becomes a scatter-gather across all shards, as slow as the slowest one ( Latency vs throughput, and why percentiles matter ). Secondary indexes must be either local per shard (queries scatter) or global (writes update another shard).
- Cross-shard transactions and joins: no longer free; you need two-phase commit or sagas ( Sagas: choreography and orchestration ), or a design that avoids them.
- Resharding: adding capacity means moving data while serving traffic: copy, catch up with ongoing writes, verify, switch over.
Going deeper
Shard as late as you can, but plan early
Sharding adds permanent complexity, so delay it with vertical scaling, read replicas, caching and archiving old data. But choose a schema where a shard key is natural (most tables carry a tenant or user id), because retrofitting one into a mature schema is the expensive part.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Range partitioning | Range scans and ordered data with a key that does not grow monotonically | Hotspots for sequential keys like timestamps |
| Hash partitioning | Even spread of data and load | Range queries, and resharding unless you use consistent hashing or logical shards |
| Directory-based | Multi-tenant systems that move big tenants around | An extra lookup and a critical directory service |
Common mistakes
- Sharding by a timestamp or auto-increment id with range partitioning.
- Choosing a low-cardinality key like country or status.
- Sharding before exhausting simpler options.
- Picking a shard key that most queries do not include, turning every query into scatter-gather.
In the wild
Notion
Herding elephants: lessons learned from sharding Postgres at Notion (opens in a new tab)Garrett Fidalgo's 2021 post describes Notion outgrowing a single Postgres database, with VACUUM stalling and the risk of transaction ID wraparound, which would have stopped all writes. Notion sharded by workspace ID, since each block belongs to exactly one workspace and users usually query within one workspace, into 480 logical shards spread across 32 physical databases, 15 per database, chosen because 480 divides evenly into many future host counts. The migration used double writes through an audit log, a backfill of existing data that took about three days, and dark reads comparing old and new systems before switching. Their top lesson: shard earlier, before load makes the migration harder.
Check yourself
-
What is the most important decision when sharding?
Show answer
B. The shard key The shard key determines balance, hotspots and which queries stay on one shard.
-
Why does range partitioning by created_at create a hotspot?
Show answer
B. All new writes have the latest dates, so they all go to the last shard Monotonically increasing keys concentrate current traffic on one range.
-
What is the downside of hash partitioning?
Show answer
B. Range queries must visit every shard Hashing scatters neighboring keys, so ranges become scatter-gather queries.
-
Why use many logical shards on fewer physical servers?
Show answer
B. Moving whole logical shards is much easier than re-splitting data when you add servers You rebalance by relocating logical shards rather than rehashing rows.
Recap
- Sharding splits data across databases so each holds and serves only part of it.
- The shard key decides balance, hotspots and which queries stay on one shard.
- Range keeps neighbors together but risks hotspots; hash spreads load but scatters ranges.
- Cross-shard queries, transactions and resharding are the ongoing costs.
- Delay sharding with simpler tools, but design a natural shard key early.
Next up
- Crack the system design round learning path