Sharding

When one database machine cannot hold all the data or serve all the requests, the rows of a table are split across several machines, called shards. Each row goes to one shard according to its shard key. Choosing that key is the big decision: it sets how evenly data and traffic spread, and which queries can be answered by one shard and which must ask them all.

Speed1x

Each dot in a shard is one user record, coloured by country; each shard stands for one database machine. Change the shard key or the number of shards and the records move to their new shards, ringed so you can count them. A shard turns red when it serves well above its share of requests.

Sizing the shards

Users

Data per userKB

Profile, settings and everything else stored per user row.

One shard holdsGB

The storage one database machine can comfortably manage.

Fill each shard to%

Room left for growth before the next split.

1. Total data
users x data per user = 500M x 10 KB = 4.66 TB
2. Shards needed
total / (one shard x fill) = 4.66 TB / (500 GB x 70%), rounded up = 14 shards
3. With an evenly spread key (user id)
each shard holds about total / shards = 341 GB
4. With country as the key
the biggest country, 34% of users, sits on one shard: 1.58 TB, 3.24 times what a shard holds. No number of shards fixes that.
5. A query that does not include the shard key
has to ask every shard: 14 requests instead of 1, and it is as slow as the slowest shard
A good shard key has many distinct values, spreads reads and writes evenly, and appears in the queries you run most. User id usually wins for user data; the cost is that other lookups need a second index or must ask every shard.

Where these formulas come from

Step 1 is the storage estimate from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1, which also lists sharding, and its hotspot and resharding problems, among the ways to scale a database. Steps 2 to 5 follow directly: a shard can only hold so much, and a row lives on exactly one shard, chosen by its key.

What sharding costs

Hot shards

A key with few values (country), a skewed one, or one that only grows (sign-up date) puts more data or more traffic on one shard. The whole system then runs at that shard's limit.

Queries across shards

Anything not keyed by the shard key must ask every shard and merge the answers. Joins between rows on different shards, and transactions across shards, become the application's problem.

Resharding

Adding shards later means moving data while the system runs. How much moves depends on the placement method: the next pages compare hash, range, directory, consistent and rendezvous placement.

Only when needed

A single database with read replicas and caching goes a long way. Sharding adds lasting complexity, so the usual advice is to shard when data or write traffic truly outgrows one machine.

How MongoDB and Notion choose shard keys

One is the database's own guidance; the other is a company's account of sharding its production Postgres.

MongoDB: cardinality, frequency, and monotonic keys

MongoDB's guide gives nearly this page's country example: with a continent field as the key, "the shard key would have a cardinality of 7", so "adding more than seven shards would not provide any benefit." On keys that only grow: "all new inserts are routed to the chunk with maxKey as the upper bound", and that shard "becomes the bottleneck for write operations." Queries without the shard key "are broadcast to all shards", which it calls scatter-gather queries.

Notion: workspace id, and many logical shards

Notion sharded its Postgres data by workspace: "each block belongs to exactly one workspace, we used the workspace ID as the partition key", because "users typically query data within a single workspace at a time". It created "480 logical shards evenly distributed across 32 physical databases", choosing 480 because it "is divisible by a lot of numbers": machines can be added without splitting any shard. Even so, "A single large enterprise customer" can generate more load than many small workspaces.

Sources and credibility

MongoDB's pages are its official manual; Notion's is a first-hand engineering post (Garrett Fidalgo, October 2021). Quoted phrases are short attributed quotations; everything else is described in our words.