Sharding: range, hash, directory

The problem: one primary isn't enough

At a hundred times today's traffic (01.05 Back-of-the-envelope estimation), Snip stores a billion new links a month: 30 TB over five years, and growing by 6 TB a year. Reads are mostly served by the cache, but every new link, every cache miss and every dashboard query lands on one primary. Its disk, its memory for hot indexes, its vacuum (04.05 MVCC) and its backups (a 30 TB restore takes many hours) all get harder every month. 04.08 Scaling a relational database's cheaper steps have been used up.

Sharding splits the data itself: each of several databases (shards) holds part of the rows, and each row lives on exactly one shard. Every shard is an ordinary Postgres primary with its own replicas, a fraction of the size.

The shard key decides everything

Each row is placed by its shard key. The rule for choosing it: the queries you run most should need only one shard. Snip's hot query is the redirect, "find the link for code x7Kp", so the natural key is code.

That choice has a cost. The dashboard query, "Ana's links, newest first", now doesn't know which shards hold Ana's links: they're spread across all of them. It must ask every shard and merge the answers (scatter-gather), which is as slow as the slowest shard (03.12 Tail latency and why p99 matters). The usual fix is a second, denormalised copy keyed the other way (04.12 Denormalisation): a small links_by_owner table, sharded by owner_id, holding each owner's codes.

Good shard keys have many distinct values, spread traffic evenly, and appear in nearly every query. Tenant IDs (workspace, organisation) are popular because most queries stay inside one tenant, until one tenant grows bigger than a shard.

Three ways to map keys to shards

Range. Each shard holds a contiguous range of keys: codes 0–F on shard 1, G–P on shard 2, and so on. Range queries ("every key between these two") stay on one shard, and splitting a full range in two is natural. The danger is keys that arrive in order: if the key is a timestamp or an increasing ID, every new row goes to the last range, and one shard takes all the writes.

Hash. Hash the key and use the hash to pick the shard. Neighbouring keys land far apart, so load spreads evenly, including for increasing IDs. The price: range queries on the key now touch every shard, and the obvious mapping, hash(key) mod N, moves almost every key when N changes. That's the problem 05.03 Consistent hashing solves.

Directory. A lookup table records which shard holds each key, or each group of keys (a tenant, a range). It's the most flexible: move one big customer to a shard of their own by changing one row. The cost is an extra lookup on every request, and the directory itself must be fast, cached and highly available, since nothing works without it.

Logical shards on physical machines

Instead of one shard per machine, most systems create many more logical shards than machines, and place several on each: say 256 logical shards on 8 machines, 32 each. The key maps to a logical shard, which never changes; a small table maps logical shards to machines, which does. Growing to 16 machines then means moving whole logical shards, not re-splitting rows (05.04 Rebalancing without downtime).

The router can live in three places: a library in the application (no extra hop, but every service needs it), a proxy between the application and the databases, or the database itself, as in the distributed databases of 04.10 NoSQL families.

What you give up

Once rows live on different machines, features that one database gave you for free stop working across shards:

• Transactions across shards. Updating rows on two shards atomically needs a distributed protocol (08.11 Two-phase commit vs sagas); most designs avoid it by keeping related rows on one shard.
• Joins across shards, done in application code or avoided with copies.
• Unique constraints across shards. A unique email on users sharded by user_id can't be enforced by any one shard. (Snip's codes are fine: the code is the shard key, so its shard checks it.)
• Auto-increment IDs, since each shard counts separately (05.05 Distributed ID generation).
• Simple operations. Schema changes, backups and failovers now happen N times.

That's why sharding comes last: shard when the data or write load truly outgrows one well-tuned primary, and choose the key by studying the queries first.

Try it

Recap

Interview questions