Engineering Atlas › System Design Fundamentals

Spreading data across machines by sharding

15 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

When one machine stops being enough

Partitioning inside one server (previous lesson) still shares one CPU, one WAL and one disk, and replicas add read capacity but take every write. When the primary's write rate, working set or disk outgrows the largest instance you can buy, different rows need different primaries. That is sharding: each partition lives on its own server with its own replicas.

Choosing the shard key

A shard key should have high cardinality (millions of values, not 50 countries), even frequency (no single value with 30% of traffic), and, most important, it should be present in almost every query. For a SaaS product that is usually tenant_id: one tenant's data lives together, joins and transactions within a tenant stay local, and tenants spread across shards. For a social app it might be user_id, which keeps a user's posts together but makes "all comments on this post" a cross-shard question if comments are keyed by commenter.

Monotonic keys like timestamps are poor shard keys under range placement, because all new writes hit the newest shard.

Placement strategies

Routing

In client-side routing the application library holds the shard map (Instagram's and Notion's Postgres sharding work this way). In proxy routing a tier such as Vitess vtgate, MongoDB mongos or the Citus coordinator parses the query, finds the shard key in the WHERE clause and forwards the query, or fans it out and merges results when it cannot. In server-side redirection any node accepts a request and either serves it or tells the client where to go, as Redis Cluster does with MOVED (Redis Cluster spec).

What you give up

Within one shard you keep transactions, foreign keys and joins; across shards you lose them by default. The shard key itself is hard to change later. MongoDB only gained online resharding to a new key in 5.0 (MongoDB docs), and most hand-built systems never get it. Unique non-key columns need a global table, queries without the key fan out, and multi-shard writes need two-phase commit or a saga. Sequences must become globally unique IDs, for example Instagram's 64-bit layout of 41 bits of milliseconds, 13 bits of logical shard and 10 bits of per-shard sequence, which also lets you find a row's shard from its ID.

Down the stack

Layer 1The contract

A statement whose shard key resolves to one shard gets that shard's full guarantees: transactions, constraints, fast index lookups. A statement touching several shards gets weaker promises: Vitess's default transaction_mode is MULTI, which commits multi-shard writes shard by shard with no atomicity guarantee; TWOPC makes them atomic but needs semi-sync replication and adds commit latency (Vitess docs); a scatter read sees each shard at a slightly different moment, not one global snapshot. During resharding the contract is that no committed write is lost and that each key has exactly one writable owner at any instant, with a brief window where writes to moving keys block or fail and are retried.

Layer 2The mechanism

Redis Cluster computes HASH_SLOT = CRC16(key) mod 16384 using CRC16-XMODEM (Redis Cluster spec). If the key contains a non-empty {...} section, only that hash tag is hashed, so {user1000}.following and {user1000}.followers share a slot and can be used together in one multi-key command. Nodes gossip bitmaps of the slots they own. To move a slot, the operator marks it MIGRATING on the source and IMPORTING on the target and runs MIGRATE on its keys in batches. Meanwhile a request for an already moved key gets -ASK <slot> <host:port>, and the client sends ASKING plus the command to the target for that one request. CLUSTER SETSLOT <slot> NODE <id> then makes the move permanent, and clients get -MOVED and update their slot map.

Vitess maps each row through its primary vindex to a 64-bit keyspace ID, and names shards by keyspace ID ranges: -80 and 80- split the space in half. Resharding -80 into -40 and 40-80 runs a VReplication workflow (Vitess docs): a copy phase streams rows to the new shards, then the workflow tails the source's binlog by GTID to catch up. VDiff compares source and target row by row. SwitchTraffic moves reads first, then writes: it stops writes on the source, waits for the target to reach the final GTID, flips the routing in the topology server, and starts reverse replication so you can switch back if the new shards misbehave.

Layer 3The machine

Scatter queries pay for tail latency. If each shard answers in under 20 ms 99% of the time, a query over 64 shards waits for the slowest: the chance that at least one is slow is 1 - 0.99^64, about 47%, so the fan-out query's median is near a single shard's p99. Dean and Barroso's version: with a 1-in-100 slow server, a request that fans out to 100 servers is slow 63% of the time (The Tail at Scale). Connections multiply too. Two hundred application pods, each with a pool of 10 to each of 32 shards, hold 64,000 server connections; at a few MB of memory per Postgres backend that is hundreds of GB, which is why sharded Postgres nearly always runs a pooler such as PgBouncer. Notion hit exactly this when it tripled its shard count: it had to shard its PgBouncer layer too, because old and new shards would otherwise have exceeded the connection limits during the migration (Notion).

Copying a 2 TB shard at a throttled 200 MB/s takes about 3 hours while the source keeps serving and its binlog grows. The cutover is short: stop writes, apply the last few MB of binlog in well under a second, update routing, resume. If you turn on vtgate buffering (--enable-buffer, off by default), it holds queries for up to --buffer-window (10 seconds) during the switch, so clients see added latency instead of errors (Vitess docs).

Why it's built this way

  1. A single primary's write path is limited by one log device and one CPU set, so writes must be split across primaries.
  2. Rehashing every row when a server is added is too expensive, so keys map to a fixed, large set of logical shards and only the shard-to-server map changes.
  3. Clients cannot all learn a new map at the same instant, so servers redirect stale clients (MOVED, ASK) or a proxy owns the map.
  4. Copying a large shard takes hours and the source must stay online, so moves are copy plus change-log catch-up, with a short write freeze only at the end.
  5. A bad cutover is costly, so systems verify with a diff and keep reverse replication running for a cheap rollback.

Diagram

sequenceDiagram
  participant C as Client
  participant A as Node A (slot 12218 MIGRATING)
  participant B as Node B (slot 12218 IMPORTING)
  C->>A: GET {user1000}.following
  A-->>C: -ASK 12218 nodeB
  C->>B: ASKING
  C->>B: GET {user1000}.following
  B-->>C: value
  Note over A,B: MIGRATE finishes, SETSLOT 12218 NODE B
  C->>A: GET {user1000}.followers
  A-->>C: -MOVED 12218 nodeB
  C->>B: GET {user1000}.followers

Worked example

A B2B messaging product stores 18 TB of messages and peaks at 60,000 writes per second. Its largest practical Postgres primary sustains about 8,000 writes per second with headroom and holds 4 TB comfortably. Writes need at least 8 primaries and storage needs at least 5, so plan 16 physical shards for growth.

The shard key is workspace_id, since every message query is scoped to a workspace. Keys hash into 1,024 logical shards, 64 per server. One 40,000-employee customer generates 6% of writes, 3,600 per second, half a server's capacity, so the directory pins its logical shard to a server of its own: a config change, not a code change.

A year later traffic doubles and the team adds 16 servers. Each old server hands 32 of its 64 logical shards to a new one, moving half the data, 9 TB, which is the minimum for an even spread. The next step, from 32 to 40 servers, shows the real benefit: with logical shards only one fifth of the data moves, while rehashing rows from mod 32 to mod 40 would relocate about 80% of them. At 200 MB/s per stream and 8 parallel moves, 9 TB copies in under 2 hours, followed by one short cutover per logical shard.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Hash into logical slotsEven spread, cheap rebalancing by moving slotsNo range locality; scatter for range queriesPoint lookups by key, many similar tenants
Range shardsRange scans and ordered pagination stay localHot tail with monotonic keys; needs splittingTime-ordered or lexicographic access
Directory per tenantIsolate or move any tenant; heterogeneous shard sizesDirectory lookup on every request; must be highly availableMulti-tenant SaaS with very uneven tenants
Proxy routing (vtgate, mongos)Apps see one database; central control of reshardingExtra hop, proxy tier to run and scaleMany services, many languages
Client-side routingNo extra hop, simple infrastructureEvery client must update its map; harder to evolveOne codebase, small team, few clients

Pitfalls in production

Leadership lens

Check yourself

  1. Why do production systems hash keys into thousands of logical shards instead of directly onto N servers?

    Show answer

    Adding servers then moves whole logical shards, the minimum needed for balance, with only the shard-to-server map changing. Hashing directly onto N servers changes most keys' owners whenever N changes.

  2. In Redis Cluster, what is the difference between -ASK and -MOVED?

    Show answer

    ASK is a one-request redirect while a slot is mid-migration, and the client must not update its slot map. MOVED means the slot has permanently changed owner, so the client updates its map.

  3. Why does Vitess switch reads before writes during resharding?

    Show answer

    Reads on the new shards can be validated while the source is still authoritative and writes are unaffected; if they misbehave you switch reads back. Writes switch last, behind a brief freeze, because that is the irreversible step.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →