Database sharding: when and how
Sharding removes cross-shard transactions, joins, and unique constraints, so it should be the last scaling step. What to exhaust first, how to pick the key, and how to leave room to reshard.
Originally written on 8 August 2022. Migrated from a WordPress blog and reformatted.
Sharding is horizontal partitioning across database instances: rows are distributed by a shard key, and each shard holds a disjoint subset. It scales writes and storage beyond a single machine. It also removes cross-shard transactions, cross-shard joins, and the ability to add an index and see it apply everywhere. It should be the last step.
Before sharding
Most databases that appear to need sharding need one of these first:
| Symptom | Try first |
|---|---|
| Read latency under load | read replicas, query optimisation, a cache |
| Table too large to index or vacuum | partitioning within one instance (PostgreSQL declarative partitioning) |
| One tenant dominates | move that tenant to its own instance |
| Writes saturate one instance | batch writes, remove unnecessary indexes, faster storage |
| Storage limit | archive cold rows to cheaper storage |
A single well-configured PostgreSQL instance on modern hardware handles tens of thousands of writes per second and several terabytes. Sharding below that scale adds cost without benefit.
Choosing the shard key
Every query that does not include the shard key must be sent to every shard. The key is therefore chosen by the access pattern, not by the data model.
shard key: customer_id
SELECT * FROM orders WHERE customer_id = 42 -> one shard
SELECT * FROM orders WHERE id = 9001 -> every shard
SELECT * FROM orders WHERE created > '2022-08-01' -> every shard
SELECT count(*) FROM orders -> every shard, then sumGood keys have three properties:
- High cardinality, so rows spread evenly.
countryis a poor key;customer_idis a reasonable one. - Present in most queries, so most queries are single-shard.
- Stable, since moving a row between shards on key change is expensive.
For multi-tenant systems the tenant id is almost always the answer. For consumer systems the user id usually is. Time-based keys are attractive for append-only data and disastrous for anything else, because all current writes land on one shard.
Mapping keys to shards
Hash. shard = hash(key) % N. Even distribution, no metadata, and every key moves when N changes. Acceptable when N is fixed for a long time.
Range. Contiguous key ranges per shard, held in a lookup table. Supports range queries on the key and rebalancing by splitting ranges. Requires the lookup table to be consulted on every query and risks hot ranges.
Directory. An explicit key -> shard mapping. Maximum flexibility, including moving one tenant at a time. The directory becomes a critical dependency and must be cached aggressively.
Consistent hashing sits between hash and directory: even distribution and minimal movement on resize, at the cost of some implementation complexity.
What sharding costs
Transactions span one shard. An order and its line items must share a shard key, or the write is no longer atomic. Design the schema so that every unit of work is co-located.
Joins across shards do not exist. Either denormalise the joined data into the row, or join in the application. Reference tables that are small and rarely change (countries, plans) are replicated to every shard.
Unique constraints apply per shard. A globally unique email address needs either a global lookup service or a scheme where the unique value determines the shard.
Schema migrations run N times, and a migration that succeeds on 9 shards and fails on the 10th leaves the system in a mixed state. Migrations must be backward compatible so that the application works during the rollout.
Operations multiply: backups, monitoring, failover, and capacity planning per shard.
Resharding
The number of shards will need to change. Plan for it at the start:
- Use more logical shards than physical instances (for example 256 logical shards mapped to 4 instances). Growing to 8 instances then moves logical shards between machines without rehashing any key.
- Write the shard mapping to a table or config that can be changed without a deploy.
- Support dual-writing during a move: writes go to both old and new locations until the copy is verified, then reads switch.
Summary
Shard when a single instance is at its limit after replicas, partitioning, caching, and tenant isolation have been exhausted. Pick the key from the query pattern. Co-locate everything a transaction touches. Over-provision logical shards from day one so that resharding is a data move rather than a rehash.