Sharding a relational database

Sharding a relational database means splitting PostgreSQL or MySQL tables across many servers while keeping as much of SQL working as possible: joins, transactions, constraints and IDs. You can route queries in your own code, put a sharding layer such as Vitess in front of MySQL, or extend PostgreSQL with Citus. Whichever you choose, the hard parts are the same: the schema, the live migration, and years of operating many databases instead of one.

This lesson assumes the basics of shard keys, placement strategies and logical shards from database sharding.

Picture it first: a law firm’s filing room

A law firm keeps one filing room. Each client’s contracts, letters and invoices are stapled into one folder, a price list hangs on the wall, and every document takes the next number from a counter by the door. When the room fills up, the firm opens three more rooms and splits the clients between them, and quickly learns that:

• Folders must move whole, or every question about a client means walking between rooms.
• The price list must be photocopied into every room and kept in step.
• The counter by the door stops working; each room needs numbers that never clash, ideally with the room number printed in them.
• A document involving two clients in different rooms cannot be filed in one step.
• Clerks keep filing while folders are carried to the new rooms.

Map it back: a folder is the root entity (tenant, workspace, user), the staple is co-location by shard key, the price list is a reference table, the counter is ID generation, and carrying folders while filing continues is the live migration.

Why relational sharding is harder

Stores built for partitioning, such as DynamoDB or Cassandra, never offered cross-partition joins or foreign keys, so their users designed around that from day one. PostgreSQL and MySQL applications have years of code that assumes all of it. Figma’s databases team called horizontal sharding an order of magnitude more complex than its earlier scaling work, and its first sharded table took about nine months.

Three ways to shard

There are three places to put the routing logic, and the choice decides how much of the system you build yourself.

There is a fourth answer: don’t shard it yourself. Distributed SQL databases such as Google Spanner, CockroachDB and YugabyteDB split tables into ranges automatically, move ranges between nodes, and run transactions across them with consensus replication. You gain resharding you never schedule and cross-shard transactions that just work. You pay with a different engine, extra latency for consensus writes, and a migration of everything you already run. Both Figma and Slack considered this route and declined it for similar reasons: moving every query to a new engine was too risky, and each had years of operational expertise in the engine it already ran.

Application-level sharding: three case studies

Instagram: schemas as logical shards, IDs that carry the shard

Instagram ran Django on PostgreSQL, looked at NoSQL stores, and chose to shard PostgreSQL instead. It created several thousand logical shards, each a PostgreSQL schema containing its own copy of every sharded table, and mapped them in code onto far fewer servers. Growing the fleet means moving whole schemas to a new server; no row is ever re-bucketed.

IDs come from the database itself. Each table in each schema has a default of next_id(), a short PL/pgSQL function that combines the clock, the schema’s shard number and a per-table sequence into one 64-bit value.

You gain IDs that sort by time, route themselves, and need no extra service. One subtlety if you copy the scheme: PostgreSQL’s bigint is signed, so a full 41-bit timestamp sets the sign bit once 2⁴⁰ ms, about 34.8 years, have passed since the epoch. Choose a recent epoch, or keep the top bit at zero.

Notion: 480 logical shards and a monolith on the brink

Notion sharded its PostgreSQL monolith when VACUUM began stalling and transaction ID wraparound, which would force PostgreSQL to stop accepting writes, became a real threat. It considered Citus and Vitess but wanted full control over data placement, so it routed in application code. Its decisions:

• Shard everything reachable from block. Every table related to a block by a foreign key moved with it, so no transaction straddled the monolith and a shard.
• Partition by workspace ID. Every block belongs to exactly one workspace, and users mostly work inside one workspace, so most queries stay on one shard.
• 480 logical shards on 32 physical databases, 15 schemas each, sized for 60,000 IOPS of current demand, at most 500 GB per table and 10 TB per database.
• Separate tables per schema, not native partitioning. A PostgreSQL partitioned table would have added a second routing layer; Notion wanted the application to be the single source of truth for workspace → shard.

Figma: colos, DBProxy and logical sharding first

Figma already ran about a dozen vertically partitioned PostgreSQL databases on RDS when some tables reached several terabytes and billions of rows and approached RDS’s IOPS ceiling. It built horizontal sharding in-house, with several deliberate choices:

• Several shard keys, grouped into colos. No single key fit every table, so tables shard by UserID, FileID or OrgID. Tables that share a key form a colo (colocation) and support joins and full transactions when a query is restricted to one key value.
• Hash the key. Many keys were auto-increment or Snowflake-style timestamp IDs that would have piled onto one shard, so routing uses a hash of the key, at the cost of range scans on that key.
• DBProxy. A Go service between the application and PgBouncer parses each query, extracts shard IDs in a logical planner and maps them to physical databases in a physical planner.
• A deliberately small SQL subset. Figma replayed production traffic through “shadow planning” for candidate shard keys and chose a dialect covering the most common 90% of queries. Joins are allowed only inside a colo and only on the shard key.
• Logical before physical. Before moving any data, Figma created PostgreSQL views per shard, each selecting one hash range, and routed reads and writes through them with a percentage rollout. The tables already behaved sharded on one host, views cost under 10% in the worst case, and rolling back was a configuration change.

Its first table was physically sharded in September 2023, with about ten seconds of partial availability on primaries and no measured latency or availability regression afterwards.

Vitess: a sharding layer for MySQL

Vitess began at YouTube in 2010 to move shard-routing code out of the application and into a proxy. Its moving parts:

• VTGate is a lightweight proxy that speaks the MySQL protocol, so applications connect to it as if it were one MySQL server. It routes each query to the right shards and merges results.
• VTTablet runs beside every mysqld and manages it. Each tablet has a type: primary, replica for live reads, or rdonly for batch jobs and backups.
• A topology service, backed by a consistent lock server, holds the cluster metadata: keyspaces, shards and which tablet is primary.
• A keyspace is a logical database. A sharded keyspace is split into shards named by ranges of a hashed keyspace ID: -80 holds the lower half, 80- the upper half.

Sharding is declared in a VSchema. Each table names a primary vindex, which is both the shard key and the function that turns it into a keyspace ID. Secondary lookup vindexes are cross-shard indexes: a separate table maps a column value to the keyspace ID of its row and is written whenever the owner table is. A sequence, backed by a single-row table in an unsharded keyspace that hands out IDs in cached blocks, replaces AUTO_INCREMENT.

{
  "sharded": true,
  "vindexes": {
    "xxhash": { "type": "xxhash" },
    "order_id_idx": {
      "type": "consistent_lookup_unique",
      "params": { "table": "order_id_idx", "from": "order_id", "to": "keyspace_id" },
      "owner": "orders"
    }
  },
  "tables": {
    "orders": {
      "column_vindexes": [
        { "column": "restaurant_id", "name": "xxhash" },
        { "column": "order_id", "name": "order_id_idx" }
      ],
      "auto_increment": { "column": "order_id", "sequence": "order_seq" }
    }
  }
}

Orders are sharded by a hash of restaurant_id, and a query by order_id costs one extra lookup instead of a scatter. Vitess’s documentation is frank that maintaining an owned lookup is essentially a distributed transaction; the consistent_lookup types avoid 2PC by locking and ordering commits carefully. A primary vindex column can never be updated in a way that moves the row to another shard.

Resharding is built on VReplication, which copies a snapshot and then tails the source’s binary log. MoveTables moves tables into Vitess or to another keyspace (a vertical split); Reshard splits or merges shards, for example 80- into 80-c0 and c0-. Both follow the same steps: create, watch progress, run VDiff to compare source and target row by row, SwitchTraffic (VTGate can buffer queries during the switch), ReverseTraffic if something looks wrong, and complete to drop the old copies.

Slack’s migration shows what this buys. Slack had sharded MySQL by workspace in its PHP monolith, with a lookup cluster mapping workspaces to shards. Large enterprise customers created hot spots it could not split, and rebuilding routing in the monolith would not have fixed its operational problems. From 2017 it moved to Vitess, proving each table with backfill, double-write and double-read diffing tooling. Three years later Vitess served 99% of its MySQL queries: 2.3 million per second at peak (2 million reads, 300,000 writes), with a 2 ms median and 11 ms p99. When query rates rose 50% in one week in March 2020, Slack split one of its busiest keyspaces with Vitess’s resharding workflows.

Citus, and the “don’t shard it yourself” options

Citus is a PostgreSQL extension. One node is the coordinator; the others are workers. Applications connect to the coordinator, which looks up its metadata tables and either routes a query to one worker or splits it into fragments that run on many workers in parallel.

• A distributed table is split by its distribution column into shards, each an ordinary PostgreSQL table on a worker covering a range of hash values.
• Co-location puts shards with the same hash range on the same worker, and keeps them together through rebalancing. Distribute workspace, page and comment by workspace_id, and joins, foreign keys and transactions within one workspace run on one node.
• A reference table is a single shard copied to every worker, so joins with it are always local. Citus writes to it with two-phase commit.
• Schema-based sharding (Citus 12.0 and later) treats each PostgreSQL schema as a shard group: the Instagram and Notion pattern, managed for you.

The documentation suggests 32 to 128 shards per table for multi-tenant workloads, enough to grow to 128 workers without changing the shard count. citus_rebalance_start() moves shards to new workers without blocking reads or writes (since Citus 11.0), and isolate_tenant_to_new_shard() carves one tenant into a dedicated shard, which matters because tenant sizes tend to follow a Zipf-like curve: a few giants, a long tail.

Designing the schema for sharding

Whichever tool routes the queries, the schema decides whether most of SQL keeps working. Five rules cover most designs.

1. Pick a root entity. Find the thing most requests are scoped to: a workspace, organisation, restaurant or user. Its ID becomes the shard key, and every table hangs off it. (Choosing the key itself is covered in database sharding.)
2. Carry the shard key in every child table and lead the primary key with it. comment stores workspace_id even though it could be found through page. This is denormalisation on purpose: the router can place every row, and the database can enforce keys locally.
3. Make foreign keys include the shard key. (workspace_id, page_id) REFERENCES page (workspace_id, page_id) can be enforced on one shard; a foreign key without the shard key cannot. The same goes for unique constraints: unique per workspace is easy, globally unique needs a lookup table.
4. Classify every other table. Small, shared, rarely written tables (plans, currencies, feature flags) become reference tables copied to every shard. Tables keyed by something else, such as users and logins, live in an unsharded global database or in a second group sharded by their own key, the way Figma runs separate colos for users, files and organisations. Many-to-many links, such as workspace membership, are often stored twice: once under each side’s key.
5. Use IDs that embed the shard, or at least are globally unique. Notion’s hindsight is instructive: its sharded rows use a composite key of the old id plus space_id, and it wished it had merged them into one new column during the migration, so that space_id didn’t need to be passed around the application.

-- PostgreSQL with Citus; the same shape works for app-level sharding
CREATE TABLE plan (plan_id int PRIMARY KEY, name text NOT NULL);

CREATE TABLE workspace (
  workspace_id bigint PRIMARY KEY,
  name         text NOT NULL,
  plan_id      int  NOT NULL REFERENCES plan (plan_id)
);

CREATE TABLE page (
  workspace_id bigint NOT NULL REFERENCES workspace (workspace_id),
  page_id      bigint NOT NULL,
  title        text,
  PRIMARY KEY (workspace_id, page_id)
);

CREATE TABLE comment (
  workspace_id bigint NOT NULL,
  comment_id   bigint NOT NULL,
  page_id      bigint NOT NULL,
  body         text,
  PRIMARY KEY (workspace_id, comment_id),
  FOREIGN KEY (workspace_id, page_id) REFERENCES page (workspace_id, page_id)
);

SELECT create_reference_table('plan');
SELECT create_distributed_table('workspace', 'workspace_id');
SELECT create_distributed_table('page', 'workspace_id', colocate_with => 'workspace');
SELECT create_distributed_table('comment', 'workspace_id', colocate_with => 'workspace');

The live migration playbook

Going from one database to N shards, or from N to 3N, follows the same arc; published accounts differ in tools, not shape.

0. Prepare. Populate the shard key in every row and query path, and route everything through the shard-aware layer while it still points at one database. Notion’s older rows lacked the workspace ID, and backfilling it would have overloaded the strained monolith, so it filled the column on the fly while copying. Figma’s logical sharding through views is this step done thoroughly.

1. Sync writes. New writes must reach both copies. There are three ways:

Notion used an audit log for its first sharding, because logical replication could not keep up with the block table during the initial snapshot. Its re-shard used logical replication: three publications per old host, five schemas each, one per new host.

2. Backfill. Copy historical rows while sync runs, comparing row versions and skipping rows the sync already updated, so the two converge in any order. Notion’s first backfill took about three days on a 96-CPU instance; in the re-shard, building indexes after the copy cut synchronisation from three days to twelve hours.

3. Verify. Notion sampled random UUIDs and compared the rows around each one, then ran dark reads: read both copies, return the old result, log differences. In the re-shard it compared only a sample of queries returning at most 5 rows, after a 1-second wait for replication, because comparing everything added visible latency. Different engineers wrote the migration and the verification, so one person’s mistake could not hide in both. Vitess automates this step with VDiff.

4. Move reads, then 5. move writes. Shift reads gradually behind a flag, then cut writes over one shard at a time. Notion’s re-shard script, per database: pause traffic in PgBouncer and let in-flight queries finish; confirm replication caught up; point PgBouncer at the new host and revoke the application’s login on the old one; reverse replication; resume. Users saw at worst about a second of “saving” spinner. Vitess buffers queries in VTGate during SwitchTraffic.

6. Clean up. Keep the reverse stream until you are sure, then drop the old copies. Notion kept a tested reverse audit log for this, and Figma made “avoid one-way migrations” an explicit goal.

Operating a sharded fleet

Cutover day is the start, not the end.

Schema migrations run N times. An ALTER TABLE must reach every shard, some will fail or lag, and for a while shards differ. Use expand-and-contract changes that old and new code both tolerate, and a runner that tracks per-shard progress and retries idempotently (see online schema and data migrations). Citus propagates DDL to all shards for you; Figma still listed sharded schema updates as unfinished work when it published its account.

Hot shards need splitting. Shards drift apart as tenants grow. With logical shards, a split is the migration playbook in miniature: copy some logical shards to a new host, sync, verify, flip. Notion’s re-shard did exactly this for every host at once.

With Citus, the same job is citus_rebalance_start() after adding workers, or isolate_tenant_to_new_shard() for a single giant tenant. With Vitess, it is a Reshard workflow splitting one key range into two.

Cross-shard reporting moves out. Don’t scatter-gather dashboards across production shards at peak. Stream each shard’s changes through CDC into a warehouse (OLTP vs OLAP); point admin tools that need live cross-shard reads at replicas.

Backups and restores are per shard. Each shard has its own log and point-in-time recovery. Undoing one tenant’s mistake means restoring that shard to a side instance and copying the tenant’s rows back; restoring “everything as of 14:05” is N independent restores, and a cross-shard saga may land on both sides of that instant.

Connections multiply. Every pooler holds connections to every shard. Notion had about 100 PgBouncer instances, each allowed 6 connections per shard: 600 per database. Pointing the new 96-shard map at the old hosts during the migration would have tripled that to 18 per instance on each old shard, so it first split PgBouncer into four clusters of 24 databases each. Citus has the same arithmetic: concurrent multi-shard queries times shard count must fit within workers times max_connections. See connection pooling.

Failures become partial. One shard down is an outage for its tenants only, easy to miss in fleet averages, so alert per shard. Before Vitess, a shard outage at Slack was a full outage for every workspace on it. Contain the blast radius with small shards, automatic failover and per-shard rollouts; cell-based architecture applies the same idea to whole stacks.

Lessons from the war stories

• Shard before you are desperate (Notion). A strained primary leaves no headroom for backfills, which is exactly when you need it.
• Separate logical from physical (Instagram, Notion, Figma). Fixed logical shards make every later split a placement change.
• De-risk the code path before moving data (Figma). Run on a logically sharded topology first, with a percentage rollout and a config-change rollback.
• Restrict SQL on evidence (Figma). Measure which query shapes real traffic uses, support those, and rewrite the rest.
• Verify independently (Notion). Different authors for migration and verification, plus sampled dark reads.
• Never make a one-way move (Notion, Figma). Reverse replication or a reverse audit log until you are certain.
• Watch the plumbing (Notion). Connection poolers and their limits became the bottleneck of the re-shard.
• Prefer a proven layer when it fits (Slack). Rebuilding routing in its monolith would not have fixed its operational problems; adopting Vitess did.

Cheat sheet

How to say it in the interview

“Our multi-tenant PostgreSQL is outgrowing one primary, so I’d shard by workspace. Every tenant table gets workspace_id, first in its primary and foreign keys, so a workspace’s joins and transactions stay on one shard. Plans become reference tables; users and logins stay in a small global database. I’d hash workspace_id into 480 logical shards on 32 hosts, routing in our data layer or letting Citus do it. To migrate: populate the key, run on a logically sharded topology first, stream changes with logical replication, backfill, verify with sampled dark reads, then cut over one shard at a time with reverse replication for rollback. Analytics moves to a warehouse fed by CDC.”

Vitess, Citus, or build your own? On MySQL, Vitess: proxy routing, vindexes and online resharding are already built and proven at YouTube and Slack. On PostgreSQL with a natural tenant, Citus. Build your own only if you need control those tools can’t give you and can staff it for years, as Notion and Figma chose to.

How do you keep email unique across shards? A lookup table keyed by email, sharded by email, written before the user row; in Vitess that is a consistent_lookup_unique vindex. The shard-local unique index then only guards each shard.

How do you run a schema change on 480 shards? Expand and contract: add nullable columns, deploy code that handles both versions, apply per shard with a runner that tracks and retries, backfill, then tighten constraints in a later change.

One tenant now drives 30% of the load. What now? Isolate it: move its logical shard to a dedicated host, or in Citus carve it out with isolate_tenant_to_new_shard(). If it outgrows even that, shard its data by a finer key, as Slack did by moving messages from workspace to channel sharding.

Why not just migrate to Spanner or CockroachDB? Early on, that may be the right answer. Late in a product’s life it means moving every query to a new engine when you have the least headroom, which is why Figma and Slack stayed put.

Where to go next

• Database sharding: shard keys, placement strategies, hot keys and resharding fundamentals.
• Table partitioning: splitting tables inside one PostgreSQL or MySQL server.
• Online schema and data migrations: expand and contract, backfills and dual writes in depth.
• Change data capture: the change streams behind live migration and warehouse feeds.
• Design a unique ID generator: Snowflake-style IDs, sequences and UUIDv7.
• Multi-tenant data: pooled, schema-per-tenant and database-per-tenant models.
• Tenancy models: silo, pool and bridge: when a big tenant deserves its own shard.
• Two-phase commit vs sagas: the options when a write must span shards.

References and further reading

1. Sharding & IDs at Instagram (Instagram Engineering)medium.comThousands of logical shards as PostgreSQL schemas, and the 41 + 13 + 10 bit ID generated by a PL/pgSQL function, with the worked example used in the ID figure.
2. Herding elephants: lessons learned from sharding Postgres at Notionnotion.comWhy Notion sharded, workspace ID as partition key, 480 logical shards on 32 databases, the audit-log double write, backfill, verification and its hindsight lessons.
3. The Great Re-shard: adding Postgres capacity (again) with zero downtime (Notion)notion.comGoing from 32 to 96 databases with logical replication by publication, dark reads, the PgBouncer-driven failover, reverse replication and the connection-pool problem.
4. How Figma’s databases team lived to tell the scalefigma.comColos, hashed shard keys, DBProxy’s query engine, logical sharding with views, the supported SQL subset, and the first physical shard split.
5. Scaling Datastores at Slack with Vitess (Slack Engineering)slack.engineeringWhy Slack moved from workspace-sharded MySQL to Vitess, its migration tooling, load figures, and resharding during the March 2020 surge.
6. Vitess documentation: Historyvitess.ioVitess’s origin at YouTube as a proxy that took shard routing out of application code.
7. Vitess documentation: Vindexesvitess.ioPrimary, functional and lookup vindexes, owned lookup tables, consistent lookups without 2PC, and the VSchema format.
8. Vitess documentation: Reshard (VReplication)vitess.ioThe create, VDiff, SwitchTraffic, ReverseTraffic and complete steps of a resharding workflow, and query buffering at cutover.
9. Citus documentation: Conceptsdocs.citusdata.comCoordinator and workers, distribution columns, hash-range shards, co-location, reference tables with 2PC, and row- versus schema-based sharding.
10. Citus documentation: Cluster managementdocs.citusdata.comShard-count guidance, connections per shard, the non-blocking rebalancer, and isolating a large tenant onto its own shard.