Sharding a Relational Database: Shard Keys, Routing, IDs, Hot Shards and Resharding

By mid-2020, Notion's on-call engineers were often woken by database CPU spikes, and Postgres VACUUM had started to stall. The scary part wasn't disk space. It was transaction ID wraparound, the safety stop where Postgres refuses all writes rather than risk overwriting data. Around the same time, Figma watched a single RDS instance run above 65% CPU at peak while its database traffic grew about 3x a year. Both teams ended up doing the same thing: they squeezed one big machine as far as it would go, then split their data across many. This article is about that split: how to choose the key, how a query finds its shard, where IDs come from, what to do about hot shards, and how to reshard without taking the product down.

We'll stay with relational databases (PostgreSQL and MySQL InnoDB) that you shard yourself or through a layer like Vitess. Distributed SQL databases such as Spanner and CockroachDB are a topic for another day.

01Before you shard: the cheaper rungs

Think of a busy restaurant. Before you open a second kitchen across town, you fix the slow dishes, buy a bigger stove and move pastry into its own room. A second kitchen is a different kind of change: from that day on, every order needs an address. Sharding is the second kitchen. It works, but it changes every query and transaction you write afterwards. So climb the cheaper rungs first:

1. Fix the queries. A missing index or an N+1 loop can look exactly like "the database is too small".
2. Scale up. Figma moved from an r5.12xlarge to an r5.24xlarge, the largest instance available (How Figma scaled to multiple databases). Notion's verdict on doing this forever: "playing Cookie Clicker with the RDS 'Resize Instance' button is not a viable long-term strategy".
3. Pool connections and cache. Figma added PgBouncer when its connections reached the thousands.
4. Add read replicas. These scale reads, not writes, and Figma found some reads couldn't move to replicas because the app was sensitive to replication lag.
5. Split tables. Partition a big table on the same server, or move groups of tables to their own database (vertical partitioning). By the end of 2022 Figma ran "a dozen vertically partitioned databases" (How Figma's databases team lived to tell the scale).
6. Shard the rows. Only now.

The ladder below shows the shape: each rung costs more than the one before and is harder to undo.

Partitioning is not sharding

The PostgreSQL partitioning docs suggest partitioning pays off when a table would otherwise be bigger than the server's memory, and dropping a partition avoids the VACUUM work a bulk DELETE creates. But as PlanetScale's When to shard page puts it, partitioning "does not remove a single-primary write bottleneck".

The signals that it's really time, from PlanetScale's When to shard MySQL and Postgres: the primary stays limited by write throughput or IOPS after tuning, the working set no longer fits in RAM, backups and schema changes take too long, and replicas lag because the primary writes too fast. Figma hit several at once: tables of several terabytes and billions of rows hurt reliability during vacuums, and the busiest tables were heading for the maximum IOPS Amazon RDS supports. Vertical partitioning couldn't go further because "the smallest unit of partitioning is a single table".

02Choosing a shard key

The shard key is the decision you'll live with longest, so let's make it on a concrete product. Meet Tasklane, a made-up project-management SaaS. Companies sign up as workspaces. A workspace has projects, projects have tasks, tasks have comments, and one user can belong to several workspaces. List the queries that matter, hottest first:

1. Load a project board: every task in one project, with assignees and comment counts.
2. Update a task, or post a comment on it.
3. Search tasks inside a workspace.
4. "My tasks": everything assigned to me, across all my workspaces.
5. A monthly billing report across all workspaces.

Queries 1 to 3 all live inside one workspace. That's a strong hint. Notion faced the same shape and partitioned by workspace ID, because "each block belongs to exactly one workspace" and "users typically query data within a single workspace at a time" (Herding elephants). Shopify used shop_id; Slack started with workspace ID.

A good key passes five tests. The first three are almost word for word from the Vitess resharding guide:

• It's in the hottest WHERE clauses, so the router can send the query to one shard.
• It co-locates what you join and write together. One workspace's projects, tasks and comments on one shard means local joins and ordinary transactions.
• It has high cardinality (many distinct values). Millions of workspace IDs spread well; 200 country codes don't.
• It spreads load, not only rows. Notion noticed that "a single large enterprise customer... generates more load than many average personal workspaces combined".
• It never changes. In Vitess the shard-key column can't be updated after insert, since that would mean moving the row (Vindexes). Shard on status and every status change relocates the task.

In practice every sharded table carries the key, and the key leads the primary key:

-- PostgreSQL: every sharded table carries workspace_id
CREATE TABLE tasks (
  workspace_id bigint NOT NULL,
  id           bigint NOT NULL,
  project_id   bigint NOT NULL,
  title        text   NOT NULL,
  status       text   NOT NULL,
  PRIMARY KEY (workspace_id, id)
);

-- The router sees workspace_id, so this hits one shard
SELECT id, title, status
FROM tasks
WHERE workspace_id = 17 AND project_id = 301;

The picture below compares our key with a tempting alternative, sharding tasks by its own id.

The queries that don't carry the key

No key is perfect; what matters is what you do with the leftovers.

• "My tasks" is keyed by user. Keep a denormalised assigned_tasks table sharded by user_id, updated asynchronously when an assignee changes. Reads become single-shard; the price is a few seconds of staleness.
• The billing report touches everything. Stream changes into a warehouse and run it there.
• The users table has no single workspace. Keep it unsharded, or shard it separately by user_id. Slack had exactly this: a "kitchen sink" cluster for data not tied to a workspace (Scaling Datastores at Slack with Vitess).

You don't need one key for the whole schema either. Figma found "no single good candidate" and chose a handful (UserID, FileID, OrgID). Tables sharing a key form a colo, and inside a colo, joins and full transactions work as long as they stick to one shard key value.

03Sharding strategies: range, hash and directory

Next you need a rule that turns a key value into a shard. PlanetScale's Sharding strategies post covers the three families:

• Range: each shard owns a contiguous range of keys. Range scans are cheap and a hot range can be split. The trap: with a growing key (auto-increment, timestamps), every new row lands on the last shard.
• Hash: hash the key and give each shard a range of hash values. Load spreads evenly if cardinality is high; cheap range scans on the key are gone.
• Directory (lookup): a table maps each key to a shard. You can put any tenant anywhere and move it by updating one row, but every query pays for a lookup, so the directory must be cached and highly available.

Figma shows the trade-off in real life. Many of its keys were auto-increment or Snowflake IDs that start with a timestamp, which would have caused "significant hotspots" under range sharding. Rewriting IDs meant a long migration, so they hashed the key and accepted slower range scans, which were rare in their code. PlanetScale says it steers customers toward hash sharding by default for the same reason. Here are the three side by side.

Why hash % N hurts, and the logical-shard fix

The naive rule is shard = hash(key) % N. It works until you add a server. Going from 4 shards to 5, a key stays put only if hash % 4 equals hash % 5, which happens for about 1 key in 5. So roughly 80% of rows would move (our own maths, assuming a uniform hash).

The fix almost everyone uses is to separate logical shards from physical hosts. Hash keys into a large, fixed number of logical shards that never changes, and keep a small table saying which host holds which logical shard. Adding hosts means moving whole logical shards. No key is ever re-hashed.

• Notion chose 480 logical shards on 32 physical databases, 15 per database, each a Postgres schema. Why 480? It has many divisors, so they could grow from 32 to 40 to 48 hosts and keep every host equal. With 512 they'd have had to double each time.
• Instagram used "several thousand 'logical' shards", also Postgres schemas, "mapped in code to far fewer physical shards" (Sharding & IDs at Instagram).
• Pinterest created 4,096 shards up front on eight MySQL servers. To add capacity they replicated a server holding shards 0 to 511 onto a new pair, then changed the config so each owned half (Sharding Pinterest).

Here is Notion's layout before and after its later re-shard.