Database sharding

Database sharding splits one logical dataset across several independent database servers, each holding only the rows whose shard key maps to it. It scales writes, storage and the hot working set past what one primary can handle, and it is the costliest scaling step to undo, because every query, transaction, index and ID scheme must now know where its data lives.

Picture it first: one ledger, many branches

A cooperative bank keeps every account in one ledger at head office. Then the town grows: the queue reaches the street and the ledger no longer fits on the desk. A faster clerk or photocopies of the ledger at a side window help for a while, but every deposit still goes into the one book by the one clerk.

So the bank opens branches. Accounts 1 to 10,000 go to Branch A, 10,001 to 20,000 to Branch B, and so on, each with its own clerk and ledger, and a signboard at the entrance tells you where your account lives. Three new problems appear at once:

• The signboard must always be right, or deposits land in the wrong ledger.
• A transfer between two branches needs a courier and a protocol, because no single clerk can update both ledgers at once.
• A question like “who holds more than ₹10 lakh?” means asking every branch and adding up the answers.

Map it back: the branches are shards, the account number is the shard key, the signboard is the shard map and router, the courier is a cross-shard transaction protocol, and asking every branch is a scatter-gather query. Good sharding is choosing the numbering scheme so couriers and branch-wide questions are rare.

Do you actually need to shard?

Replicas copy every write, so they add read capacity but not write capacity. Sharding divides the writes themselves. Three pressures push you there.

Write throughput. Take a chat app with 50 million daily users who each send 40 messages a day: 50M × 40 = 2 billion messages a day, or 2 × 10⁹ ÷ 86,400 ≈ 23,000 writes per second on average. Assume evening peaks run about 3× that: roughly 70,000 writes per second. If your load tests show one primary sustaining about 15,000 of these writes per second with headroom, you need at least 70,000 ÷ 15,000 ≈ 5 primaries for writes alone.

Data size. At about 200 bytes per message, that is 400 GB a day, or about 146 TB a year before indexes and replicas. Notion, when it sharded, capped itself at 500 GB per table and 10 TB per physical database to keep PostgreSQL maintenance healthy. At 10 TB each, a year of messages needs about 15 databases. Size also slows recovery: restoring 10 TB at 500 MB/s takes (10 × 10¹²) ÷ (5 × 10⁸) = 20,000 seconds, about 5.5 hours.

Working set. Performance falls off a cliff once the hot data no longer fits in memory. If users mostly read the last 30 days, that is 30 × 400 GB = 12 TB of hot data, far beyond one machine’s RAM.

Here storage sets the shard count (about 15 for year one), not writes (5). Round up to 16.

Now the counter-example. A regional food-delivery app with 200,000 orders a day writes 200,000 ÷ 86,400 ≈ 2.3 orders per second, a few dozen at a 10× dinner peak, and about 146 GB a year at 2 KB per order. One well-indexed primary carries that for years. Climb the cheaper rungs of the database scaling ladder first: fix queries and indexes, scale vertically, add connection pooling, a cache and read replicas, partition big tables, then move whole groups of tables to their own databases. Figma ran a dozen of these vertical partitions before it sharded a single table.

Sharding, partitioning and replication

These words get mixed up constantly. They solve different problems, and real systems combine all three.

Moving whole tables to a separate database is vertical partitioning, a functional split; sharding is horizontal partitioning across machines.

The moving parts: shard map and router

A sharded system adds two pieces to an ordinary database: a shard map that says which key range lives where, and a router that consults it on every request.

The router can live in three places:

• A client library in the application, as at Instagram and Notion. No extra network hop and full control, but every service and language needs the library, and a reshard means updating config on every app server.
• A proxy in front of the shards, such as Vitess’s VTGate, MongoDB’s mongos or Figma’s DBProxy. The application sees one database, and routing, scatter-gather and load shedding live in one place. You pay an extra hop and a proxy fleet to run.
• A coordinator inside the database, as in Citus or distributed SQL. The engine owns the map and plans cross-shard queries, which gives the most SQL compatibility but hands placement decisions to the engine.

Keep the shard map in a strongly consistent store such as etcd or ZooKeeper, cache it in every router, and version it. A router with an old map sends requests to the wrong place, so each shard should also reject keys it does not own.

Choosing a shard key

The shard key is the column, or columns, whose value decides where a row lives. Changing it later means moving almost every row, so it is the decision to get right. A good key has five properties:

1. High cardinality. The number of distinct values caps the number of useful shards. MongoDB’s documentation uses continent as the cautionary example: seven values means at most seven shards, however many machines you buy.
2. Even distribution. Many distinct values are not enough if a few of them carry most of the rows or traffic.
3. Present in the dominant queries. If most reads and writes include the key, the router sends each one to exactly one shard.
4. Keeps a transaction on one shard. Rows that must change together should share the key, so the transaction stays local and ACID.
5. Never changes. A new key value means moving the row; Vitess simply forbids updates to a table’s primary vindex columns.

A chat app. Shard per-user data (inbox, settings, contacts) by user_id: hundreds of millions of values, and almost every request starts with “me”. Shard messages by conversation_id, so a conversation’s history sits on one shard. Slack originally sharded everything by workspace, its largest customers became hot spots, and it moved message data to sharding by channel ID.

A food-delivery orders table. Three plausible keys, three different bills:

restaurant_id usually wins: the order’s life (accept, cook, hand over) and the stock decrement are restaurant-scoped, and the kitchen tablet polls constantly. Serve the rarer “my orders” from a global index on customer_id. If customer history were the heaviest query, the answer would flip: the key follows the dominant access pattern.

Anything keyed on created_at. Huge cardinality, terrible shard key. Every new row has the largest value yet, so under range placement every insert lands on the shard that owns “now” while the others idle. Auto-increment and time-prefixed IDs behave the same way; MongoDB’s documentation calls these monotonically changing keys and recommends hashing them.

Placement strategies

Once you have a key, you need a rule that turns it into a shard. Range placement gives each shard a contiguous run of key values: range scans stay on one shard, but monotonic keys pile onto the last range. Hashing spreads any key shape evenly, which is why Figma routes on the hash of its keys (many were auto-increment or time-prefixed), but neighbouring keys scatter. Consistent hashing puts keys and servers on a ring so that adding a server moves only about 1/(N+1) of keys. A directory stores an explicit key → shard table, like Slack’s original metadata cluster mapping each workspace to a shard. Geo or tenant placement keeps Indian users in Mumbai and EU users in Frankfurt, or a large customer on its own shard; Slack runs Vitess clusters in six regions for data residency.

Logical shards make resharding cheap

Plain hash(key) mod N hides a nasty surprise. Going from N shards to N + 1, a key stays put only if k mod N equals k mod (N+1). In every block of N(N+1) consecutive hash values exactly N satisfy that, so only 1/(N+1) of keys stay and N/(N+1) move: 80% going from 4 shards to 5, about 91% from 10 to 11. You copy almost everything to add one machine.

The fix is to separate the two jobs. Hash each key into a fixed number of logical shards, far more than you have machines, and map logical shards to hosts in a small table. A key never changes logical shard; adding a host moves a few whole logical shards. Unlike a hash ring, the map is explicit, so operators can read it and pin a hot tenant by hand.

Real systems use this pattern everywhere. Instagram maps several thousand logical shards, each a PostgreSQL schema, onto far fewer servers. Notion chose 480 logical shards on 32 databases (15 schemas each); its later re-shard tripled the fleet to 96 databases of 5 schemas each without changing any key’s logical shard. Vitess hashes the key into a keyspace ID and gives each shard a range of them, so splitting a shard replaces one range with two halves and no other shard moves.

Moving a logical shard follows the same sequence whether you do it by hand or a tool does it:

1. Copy a snapshot to the new host.
2. Keep it in sync through application double-writes or by tailing the source’s replication stream (change data capture).
3. Verify with row comparisons and “dark reads” against both copies.
4. Cut over: pause writes briefly, let the copy catch up, flip the shard map, resume.
5. Keep a reverse stream from new to old for rollback, then clean up.

Vitess describes its cutover as a few seconds of read-only time. In Notion’s move to 96 databases, a user saw at worst about a second of “saving” spinner. The production playbook is in Sharding a relational database.

Hot shards and the celebrity problem

Even a well-chosen key produces hot spots, because real traffic is skewed. A celebrity posts and millions like that one post. A cricket-score app gets most of its comments on one match in the final over. A tatkal window opens at 10 am and every request targets the same train. Managed stores have the same limit, just hidden: each DynamoDB partition delivers at most 3,000 read units and 1,000 write units per second, however large the table.

• Hot reads: cache and replicate. Put the hot item in a cache in front of the shard (see hot keys and cache stampedes) and add replicas. Reads are the easy half.
• Hot writes: salt the key. Spread one logical key over k physical keys, match:42#0 to match:42#k-1. Writes pick a random suffix; reads query all k and merge. If a match’s comment counter takes 20,000 one-kilobyte writes a second and a partition takes 1,000 write units a second, you need at least 20,000 ÷ 1,000 = 20 suffixes; use 32 for headroom. You gain 32× write capacity on that key and pay a 32-way read fan-out. DynamoDB’s guide shows the same trick with suffixes 1 to 200, plus a variant that computes the suffix from another attribute so single-item reads still hit one key.
• Hot tenants: isolate them. Give a whale its own shard, or several; a directory or a logical-shard map with tenant overrides makes this a config change. Slack’s workspace sharding struggled here: large customers created hot spots it could not spread while much of the fleet sat underused. Under range placement, split hot ranges instead.

Notion noticed that after tripling its fleet, the few unusually heavy workspaces stood out even more: more shards improve averages and expose outliers.

Queries and transactions that cross shards

Scatter-gather and the tail

A query without the shard key, such as “orders over ₹5,000 yesterday”, goes to every shard and the router merges the answers. Two costs follow.

Load does not shrink. Figma’s team notes that each scatter-gather puts as much total load on the fleet as the same query did on the unsharded database. More shards only add more places to ask.

Latency is set by the slowest shard. Suppose each shard is slow, say over 50 ms, on 1% of requests. A query waiting on N shards is fast only if all N are, with probability 0.99^N, so the chance of a slow answer is 1 − 0.99^N: about 10% at 10 shards and 63% at 100. Turn it around: for 99% of 100-shard queries to beat 50 ms, each shard must beat it with probability 0.99^(1/100) ≈ 0.9999. A 100-way fan-out’s p99 is each shard’s p99.99, the tail amplification at the heart of Dean and Barroso’s paper “The Tail at Scale”.

So put the shard key in the query wherever the product allows (Figma ran “shadow planning” on live traffic to see which queries each candidate key would scatter), add a global index for the few important non-key lookups, hedge slow sub-requests to a replica (Figma’s DBProxy does), and move analytics off the shards into a warehouse fed by CDC; see OLTP vs OLAP.

Joins

A join runs on one shard only if matching rows live there. So shard related tables by the same key: orders, order items and payments all by restaurant_id. Figma calls such a group a colo and allows joins only inside one, on the shard key. Copy small, rarely changing tables such as cities or cuisines to every shard as reference tables. Anything else becomes an application-side join.

Transactions

A transaction whose rows share a shard key is an ordinary local ACID transaction, which is the main reason to match the key to transaction boundaries. When a write truly spans shards, such as a transfer between wallets on different shards, you have two tools (see two-phase commit vs sagas):

• Two-phase commit is atomic, but holds locks across extra round trips, and a stuck coordinator can block participants.
• A saga commits locally on each shard in turn and compensates if a later step fails. You gain availability and pay with no isolation between steps.

Figma chose not to support atomic cross-shard transactions at first and made product logic tolerate partial failures instead.

Secondary indexes and global IDs

Local vs global secondary indexes

Orders are sharded by restaurant_id, and the customer app needs “my orders” by customer_id. A local index lives on each shard and covers only its rows: writes update it in the same local transaction, but a lookup by customer_id must scatter to every shard. A global index is itself sharded by the indexed value, so customers 50–99 live in one index partition wherever their orders are. A lookup hits one partition and fetches only the shards it names, but every write now touches two places, so you choose between a distributed transaction and an index that lags.

• DynamoDB global secondary indexes are updated asynchronously and are eventually consistent, normally within a fraction of a second. Each consumes its own write capacity, so every index raises the cost of writes.
• Vitess lookup vindexes are tables mapping a column value to the shard holding the row. Its docs call their maintenance essentially a distributed transaction; the “consistent lookup” variants order commits carefully to stay correct without 2PC.
• Uniqueness is a global-index problem in disguise: a unique email across shards needs a lookup table keyed by email. Figma’s first version supported unique indexes only when they included the shard key.

Global unique IDs

A per-shard AUTO_INCREMENT or SERIAL counter hands out 1, 2, 3 on every shard, so IDs collide. The usual answers (design a unique ID generator) are random UUIDs, a ticket service, or Snowflake-style 64-bit IDs. Instagram’s sharding-aware version packs into 64 bits:

• 41 bits of milliseconds since a custom epoch: 2⁴¹ ms ≈ 2.2 × 10¹² ms, about 69 years.
• 13 bits of logical shard ID: up to 2¹³ = 8,192 logical shards.
• 10 bits of per-shard sequence: 1,024 IDs per shard per millisecond, about a million per second per shard.

Each logical shard generates its own IDs in the database, so there is no extra service, IDs sort roughly by time, and any ID routes itself: the router reads 13 bits and knows the logical shard.

Going deeper: failure modes

One shard down is a partial outage. Every user whose key maps to a failed shard is down while everyone else is fine. At Slack, a shard outage meant a full Slack outage for every customer on it. Give each shard replicas and automatic failover, and keep shards small enough that one failure hits a tolerable slice; cell-based architecture extends the idea to whole stacks.

Stale routing. During a move, a router with yesterday’s map writes to the old owner, and the write vanishes when the old copy is dropped. Version the map, make shards reject keys they no longer own, and keep the old owner read-only until every router has caught up.

Shards grow apart. One tenant grows, one hash range collects heavy users. Watch size, CPU and IOPS per shard, not fleet averages.

Every chore is now N chores. Schema changes, index builds, upgrades and restores run on every shard, and a half-applied migration is a new kind of inconsistency; see online schema and data migrations.

Connections multiply. Notion ran about 100 PgBouncer instances with up to 6 connections each to every shard: 600 per database. Tripling the shard count naively would have meant 18 per instance to each old shard during the move, so it first split its poolers into four groups. Plan connection pooling per shard group.

No single point in time. Each shard has its own log and backups, so restoring “the database as of 14:05” means restoring every shard separately, and cross-shard transactions may land on different sides of that line.

Cheat sheet

How to say it in the interview

“First I’d check that a bigger primary, replicas, caching and partitioning can’t carry it. Here they can’t: about 70,000 writes a second at peak and 400 GB a day, so storage alone needs about 15 databases in year one. I’d shard messages by conversation ID and user data by user ID, hashing into 720 logical shards on 16 PostgreSQL primaries, 45 each, every one with replicas. A routing library with a cached, versioned shard map sends each request to one shard, and IDs embed the logical shard so any ID routes itself. Search and analytics read from separate stores fed by CDC. To grow, I move whole logical shards: copy, replicate, verify, brief cutover.”

How do you add a shard without downtime? Move logical shards, not keys: copy a snapshot, stream ongoing changes, verify with row comparisons and dark reads, pause writes for a second or two to catch up, flip the shard map, and keep a reverse stream for rollback.

What if one customer is bigger than a shard? Then the tenant can’t be the whole shard key for that data. Shard its data by a finer key such as channel or project, as Slack did when it moved messages from workspace to channel sharding.

How do you query by something that isn’t the shard key? If it’s rare or analytical, scatter-gather to replicas or ask the warehouse. If it’s frequent, build a global index on that attribute and accept slight lag or a distributed write.

Can sharding make things slower? Yes. Queries without the shard key do the same total work plus a merge, and track the slowest shard; cross-shard transactions add round trips. Sharding speeds up keyed queries and makes everything else harder.

Where to go next

• Sharding a relational database: Vitess, Citus, application-level sharding and live migration playbooks.
• Consistent hashing: the ring, virtual nodes and why only 1/(N+1) of keys move.
• Table partitioning: splitting a table inside one database, the step before sharding.
• Database scaling: the full ladder from query tuning to distributed SQL.
• Data replication: how each shard stays available, and where replica lag comes from.
• Design a unique ID generator: Snowflake, UUIDv7 and ticket servers in depth.
• Two-phase commit vs sagas: what to do when a write must span shards.
• Multi-tenant data: shard-per-tenant, pooled tables and noisy neighbours.

References and further reading

1. MongoDB Manual: Choose a Shard Keymongodb.comCardinality, frequency and monotonically increasing keys, the seven-continent example, and scatter-gather when a query lacks the shard key.
2. Amazon DynamoDB: Best practices for designing and using partition keys effectivelydocs.aws.amazon.comThe per-partition ceiling of 3,000 read units and 1,000 write units per second used in the hot-key arithmetic.
3. Amazon DynamoDB: Using write sharding to distribute workloads evenlydocs.aws.amazon.comRandom and calculated key suffixes (key salting) and the cost of merging reads across every suffix.
4. Amazon DynamoDB: Using Global Secondary Indexesdocs.aws.amazon.comGlobal indexes are updated asynchronously, are eventually consistent and consume their own write capacity.
5. Vitess documentation: Shardingvitess.ioKey ranges over a hashed keyspace ID, splitting a shard into two ranges, and resharding with a few seconds of read-only time.
6. Vitess documentation: Vindexesvitess.ioPrimary vindex as the shard key (not updatable), and lookup vindexes as cross-shard indexes that behave like distributed transactions.
7. Sharding & IDs at Instagram (Instagram Engineering)medium.comThousands of logical shards as PostgreSQL schemas mapped to fewer servers, and the 41 + 13 + 10 bit ID layout.
8. Herding elephants: lessons learned from sharding Postgres at Notionnotion.com480 logical shards on 32 databases, why 480, the 500 GB per table and 10 TB per database limits, and the double-write, backfill, verify, switch-over sequence.
9. How Figma’s databases team lived to tell the scalefigma.comHashing auto-increment keys to avoid hotspots, scatter-gather load, co-located table groups, logical vs physical sharding and no atomic cross-shard transactions.
10. Scaling Datastores at Slack with Vitess (Slack Engineering)slack.engineeringA workspace lookup table as a shard directory, hot spots from large customers, shard outages as full outages, and re-sharding messages by channel.