Sharding & partitioning at scale — System Design

The wall you hit, and the things to try before sharding

Sharding is splitting one logical dataset across many independent databases so that no single machine holds it all. It is the most powerful scaling tool you have and the most expensive, because it takes away things you have relied on your whole career: joins, transactions, unique constraints, and ORDER BY across the whole table. The senior answer to "how would you scale the database?" starts by not sharding.

Do this first	Buys you	Runs out when…
Vertical scaling	The biggest cloud boxes reach 896 vCPU and 32 TiB of RAM (AWS u7in-32tb). As conservative planning figures, one relational primary on NVMe with a warm cache handles about 20,000 simple indexed point reads/sec and 5,000 committed writes/sec. These are not limits: strong hardware with batching and group commit does several times more (100,000+ reads/sec and 20,000–50,000 writes/sec are reported), and OpenAI runs ChatGPT on one Azure PostgreSQL primary plus about 50 read replicas at millions of aggregate queries per second, while moving shardable write-heavy workloads elsewhere. Rule of thumb: start planning a change when sustained reads pass ~20k/s (cache, replicas) or sustained writes pass ~5k/s (partitioning or a queue), and treat 20k+ sustained writes as "you are sharding or queueing now". Measure, do not assume.	Price becomes superlinear, and the single-writer ceiling is fixed no matter how big the box is.
Read replicas	Scales reads ~linearly. Five replicas, five times the read capacity.	Writes still all land on one primary. Replication lag becomes a correctness problem for read-your-writes.
Caching (see the caching chapter)	Can remove most reads for skewed workloads (a planning figure is 80–95% of reads, at well under 1 ms per hit). Measure your own hit rate.	The write path and cache-miss path are unchanged; a cold cache now takes the DB down.
Archiving cold rows / table partitioning on one host	Keeps the hot working set in RAM. Postgres declarative partitioning lets queries prune to the hot partitions and makes dropping old data a cheap metadata operation. How much it speeds up reads depends entirely on the workload; measure before promising a number.	The hot set alone exceeds RAM, or write throughput exceeds one primary.

You shard when one of three things is true: the working set no longer fits in RAM on the biggest box you're willing to pay for; write throughput exceeds what one primary can commit; or the blast radius has become unacceptable (a single 8 TB database takes hours to restore, and during those hours every customer is down).

Vertical vs horizontal partitioning

Vertical partitioning shrinks the row so more rows fit in a page and in RAM; horizontal partitioning is the only one that removes the single-machine ceiling.

Vertical partitioning splits a table by column — move rarely read wide columns out to a separate table or store so the hot row stays small and many rows fit in each page of RAM. Note that Postgres (TOAST) and InnoDB already move very large values off-row automatically, so the gain comes mostly from mid-sized columns (hundreds of bytes to a few KB) that bloat every page; the rows-per-page improvement is whatever the ratio of hot to cold bytes works out to. It is cheap and reversible. Taken to its extreme across services it becomes "each service owns its own database", which is the microservices decomposition, not a scaling technique. It never removes the write ceiling, because the hot table still lives on one machine.

Horizontal partitioning (sharding) splits by row. Every shard has the identical schema and a disjoint subset of rows. This is the one that scales writes, and everything difficult in this chapter follows from it.

Shard key selection: the decision you cannot take back

The shard key determines which shard a row lives on. It is embedded in your routing layer, your access patterns, your operational tooling, and — because most systems put it in the primary key — often in the IDs your customers have already saved in bookmarks and integrations. Changing it means physically moving every row while the system stays online. Plan for weeks, and treat this as the single highest-stakes call in the design.

Property the key must have	Why
High cardinality	You can never have more shards than distinct key values. Sharding by `country` caps you at ~200 shards and half your traffic is in three of them.
Even access distribution	Even data distribution is not enough — a shard holding 1/8 of the rows but 60% of the QPS is still a hot shard.
Immutable	If the key can change, a row must be deleted from one shard and inserted into another: not atomic, breaks foreign keys, and invalidates any ID derived from it.
Present in the majority of queries	A query without the shard key must be broadcast to every shard. If 90% of your reads lack the key, you have built a distributed full scan.
Aligned with your transaction boundary	If the rows that must change atomically share a shard key, transactions stay single-shard and you never need two-phase commit.

Key	Verdict	Why
`user_id` for a social/consumer app	Good	High cardinality, immutable, and nearly every read is "everything for this user" — timeline, settings, orders. Transactions naturally stay local.
`tenant_id` for B2B SaaS	Good	Every query already filters by tenant; it gives you free per-customer isolation, per-customer backup/restore, and the ability to move a whale onto its own hardware.
`conversation_id` for chat	Good	The unit of read is a conversation. Sharding by `user_id` instead would put the two sides of a DM on different shards and make every message a cross-shard write.
hash of `(device_id, day)` for telemetry	Good	Spreads writes, keeps a device's day contiguous for the common query, and lets you drop whole days by dropping partitions.
Auto-increment `id` or `created_at`, range-partitioned	Catastrophic	Every insert goes to the newest shard forever. You have N shards and one of them is doing 100% of the writes. This is the single most common sharding mistake.
`status`, `country`, `is_active`	Catastrophic	Low cardinality and Zipfian distribution. Hard ceiling on shard count and guaranteed skew.
A mutable attribute (`current_plan`, `region`)	Catastrophic	An upgrade from free to pro physically relocates the row. Non-atomic, and every cached reference to its location is now wrong.
`user_id` when 90% of reads are by `order_id`	Catastrophic	The key is correct in isolation and wrong for the workload: nearly every read becomes a scatter-gather. Always check the key against the read patterns, not just the write ones.

⚠ Do not pick the key before you have listed the queries Candidates announce "I'll shard by user ID" thirty seconds into the design. Write the top five queries by volume on the board first, then pick the key that keeps the most of them single-shard, then name explicitly which queries you have just made expensive. That sequence is the entire signal.

Range vs hash vs directory

Strategy	How it routes	Wins	Loses	Reach for it when…
Range	Sorted key space cut into contiguous intervals; a metadata service maps interval → shard.	Range scans and ordered pagination are one shard. Splits are cheap — cut a hot range in half (systems like Spanner, CockroachDB, HBase and Vitess split and merge ranges online).	Sequential keys create a permanent hotspot on the newest range.	You need ordered scans: time-series reads, "next 50 rows after X". HBase, Bigtable, Spanner, CockroachDB, MongoDB ranged sharding.
Hash	`shard = hash(key) mod N`, or a token on a consistent-hashing ring.	Near-perfect distribution with no thought. Routing is a pure function — no lookup hop.	Range scans are dead (adjacent keys are on different shards). Naive `mod N` makes resizing catastrophic.	Point lookups dominate and you want zero routing state. Cassandra (Murmur3 token), DynamoDB partition key, Vitess hash vindex.
Directory / lookup	An explicit key → shard map held in a coordination service, cached at the client.	Total control: move one noisy tenant to dedicated hardware with a single row update. Heterogeneous shard sizes are fine.	An extra hop, and the directory becomes a critical HA dependency. A stale cached map routes writes to the wrong shard — you need versioning and a redirect.	B2B SaaS with wildly uneven tenants, or any time "give this customer its own database" is a product requirement. Vitess-style keyspaces, and how most large multi-tenant apps actually work.

These compose. Cassandra hashes the partition key onto a ring and then range-orders rows inside the partition by clustering key — which is exactly why "hash of device, range on time" is the canonical time-series schema. DynamoDB is the same idea with different words: partition key hashes, sort key ranges.

Consistent hashing, and why virtual nodes are the real trick

The problem with hash(key) mod N is resizing. Go from 10 shards to 11 and about 90% of keys change owner — every cache is cold, every row moves, and you cannot do it online. Consistent hashing fixes this by hashing both keys and nodes onto the same circular space (typically 2⁶⁴ or 2³² points). A key belongs to the first node found by walking clockwise. Adding an (N+1)th node moves only about 1/(N+1) of the keys. With one point per node they all come from its immediate clockwise successor; with virtual nodes (below) they come in small slices from many nodes.

Virtual nodes are what make removal survivable: the departing node's load is spread over every survivor instead of doubling one neighbour.

Plain consistent hashing with one point per node has two flaws. Random placement of 10 points on a circle gives wildly uneven arcs — in expectation the largest arc is about 2.9× the mean and the smallest about 0.1×, a spread of roughly 30× between the luckiest and unluckiest node. And when a node dies, its entire range falls on its single clockwise successor, which promptly gets double load and often dies too. Virtual nodes fix both: give each physical node V positions on the ring (deployments commonly use tens to a few hundred; Cassandra's num_tokens defaulted to 256 historically and 16 in modern versions with the token allocation algorithm). The relative spread of load (its standard deviation) shrinks roughly as 1/√V, and a departing node's data is refilled from every survivor in parallel. As a bonus, a machine with twice the RAM simply gets twice the vnodes.

// Ring = sorted array of {token, node}. Lookup is a binary search, O(log n).
function buildRing(nodes, vnodesPerNode) {
  const ring = [];
  for (const node of nodes) {
    for (let v = 0; v < vnodesPerNode; v++) {
      ring.push({ token: hash64(node.id + "#" + v), node }); // deterministic vnode positions
    }
  }
  return ring.sort((a, b) => (a.token < b.token ? -1 : 1));
}

function lookup(ring, key) {
  const h = hash64(key);
  let lo = 0, hi = ring.length - 1;
  while (lo < hi) {                       // first token >= h
    const mid = (lo + hi) >> 1;
    if (ring[mid].token < h) lo = mid + 1; else hi = mid;
  }
  return ring[ring[lo].token < h ? 0 : lo].node; // wrap past the end of the ring
}

For replication factor 3, you do not take the next three vnodes — you walk clockwise until you have three distinct physical nodes, and ideally three distinct racks or AZs. Forgetting that is how people end up with all three replicas of a key on one machine.

Consistent hashing with vnodes is not the only way to avoid the mod N reshuffle. Rendezvous (highest-random-weight) hashing scores every node against the key and picks the highest, so removing a node moves only that node's keys and there is no ring to maintain, at O(N) cost per lookup. Jump consistent hash maps a key to one of N numbered buckets in O(log N) with no memory, but buckets can only be added or removed at the end, which suits caches and sharded stores that grow, not clusters where an arbitrary node dies. Bounded-load consistent hashing caps each node at a multiple of the average load and spills the excess to the next node, which tames hot nodes in a cache fleet. All of these decide placement of keys; none helps with one key that is itself too hot.

Separately, someone has to answer "which shard holds this key?" at request time. There are three common shapes: the client sends to any node, which forwards (Cassandra, Dynamo); a routing tier looks the key up in the shard map and proxies (Vitess vtgate, mongos); or a shard-aware client library caches the map and talks directly (Redis Cluster clients, Kafka producers), refreshing on a redirect. Whatever you choose, the shard map is the thing that needs a coordination service and versioning. Related placement tools: geo-partitioning pins a row to the region of its owner for latency and data residency, and co-located or interleaved tables keep a parent and its children on the same shard so joins and transactions stay local.

Dry run: a 3-node ring with 4 vnodes each (positions 0–999, chosen for illustration), then removing node B

Vnode	Position	Arc it owns (previous position, this one]	Size
A3	49	(931, 49] — wraps past 999	118
A2	100	(49, 100]	51
A0	134	(100, 134]	34
C1	283	(134, 283]	149
C2	331	(283, 331]	48
B2	434	(331, 434]	103
B1	659	(434, 659]	225
C3	724	(659, 724]	65
B0	738	(724, 738]	14
B3	832	(738, 832]	94
A1	927	(832, 927]	95
C0	931	(927, 931]	4

Node shares before any removal: A owns 118 + 51 + 34 + 95 = 298 of 1000 (29.8%), B owns 103 + 225 + 14 + 94 = 436 (43.6%), C owns 149 + 48 + 65 + 4 = 266 (26.6%). With only four vnodes each the split is visibly lumpy, which is the 1/√V effect in action. Two real keys (MD5 of the key string, mod 1000) pinned to that ring: hash("user:7") = 559 falls in B1's arc (434, 659], served by node B. hash("order:39") = 982 falls in A3's wraparound arc (931, 49], served by node A.

B's arc before removal	New owner after B leaves the ring
(331, 434] — was B2	C3 @ 724
(434, 659] — was B1	C3 @ 724
(724, 738] — was B0	A1 @ 927
(738, 832] — was B3	A1 @ 927

B owned 436 of 1000 positions. After it leaves, C3 absorbs 103 + 225 = 328 of them (75%) and A1 absorbs 14 + 94 = 108 (25%), so B's data lands on two nodes instead of one neighbour. The final shares are A 40.6% and C 59.4% (A 298 + 108 = 406; C 266 + 328 = 594). That is better than dumping all of B on one successor, but the 75/25 split shows the limit of four vnodes: with 128 or more per node each survivor would take close to an equal slice. user:7 (hash 559), previously on B1, now resolves to C3's expanded arc (331, 724] and moves to node C; every key owned by A or C before the removal stays where it was.

Hot shards and the celebrity problem

Real access distributions are heavily skewed (Zipfian): in many workloads a tiny fraction of keys carries a large share of the traffic (illustratively, tens of percent from the top fraction of a percent). Hashing gives you an even spread of keys, not of requests. One artist with 80 million followers, one enterprise tenant with 200× the average volume, or one viral post will saturate a single shard while the other 63 idle — and you cannot fix it by adding shards, because the unit of load is a single key.

Mitigation	Mechanism	Cost
Cache the hot key	By definition a hot key has a ~99% hit rate. Put it in Redis or even in-process, and add request coalescing so a miss doesn't stampede.	Staleness, and a cold-cache event now hits the hot shard even harder. Do this first anyway — it is the cheapest 10×.
Key salting	Write to `celeb:42#0 … celeb:42#31` and read by fanning out to all 32. Spreads one logical key over 32 shards.	Every read becomes 32 reads. Only apply it to keys detected as hot at runtime, never uniformly — otherwise you have made the average case 32× worse to fix the p99.9.
Dedicated shard	Directory partitioning moves the whale onto its own hardware with one map update.	Operational sprawl and a manual placement decision — but it is what large B2B SaaS actually does, and it is why the directory strategy earns its extra hop.
Change the data model	The celebrity's followers stop being a fan-out-on-write problem: push to normal users, and let followers of the celebrity pull her posts at read time and merge.	A hybrid read path. This is the well-known Twitter timeline answer and it is a modelling fix, not an infrastructure fix — usually the strongest one available.
Managed adaptive capacity	DynamoDB will isolate and split a hot partition automatically.	Still bounded by hard per-partition limits (about 3,000 read and 1,000 write units per second). A single key that exceeds this cannot be saved by the platform.

What sharding costs you

What you lose	What you do instead
Cross-shard joins	Application-side joins (fetch IDs, then batch-fetch by shard — never row by row, or you have built an N+1 over the network), or denormalize the joined columns into the child row and accept the update cost.
Cross-shard transactions	Two-phase commit works but adds a coordinator, blocks if the coordinator dies mid-commit, and adds durable prepare and commit round trips while holding locks, so a distributed commit typically costs a small multiple of a single-shard commit (measure it). The alternatives are sagas with explicit compensating actions, or — far better — choosing a shard key that keeps transactions single-shard in the first place.
Global unique constraints	The database can only enforce uniqueness within a shard. Generate IDs that are unique without coordination: UUIDs (random, with negligible collision probability) or Snowflake-style IDs (deterministic: timestamp, worker ID and sequence). That only covers surrogate IDs. Business keys such as email still need a small dedicated uniqueness table (email → user_id) that is itself sharded by the constrained column.
Cheap secondary indexes	Local index: lives on each shard, cheap to write, but a lookup by that column must scatter-gather across all shards. Global index: a separate table sharded by the indexed column — one hop to read, but writing it is a cross-shard write, which is why it is maintained asynchronously and why DynamoDB's Global Secondary Indexes are eventually consistent.
Cheap `ORDER BY` / `LIMIT` / `COUNT`	Top-K across shards needs each shard to return its own top K and the router to merge. Deep offset pagination is pathological — use keyset ("seek") pagination on a sortable cursor instead.

Tail latency amplification: a fan-out read inherits the worst p99 in the fleet, so scatter-gather designs need hedging, per-shard deadlines, or a data model that avoids the fan-out.

Re-sharding a live system

Everything above is why the shard key is irreversible in practice — but "irreversible" means expensive, not impossible, and being able to walk the migration is a strong staff-level signal.

1. Stand up the new topology alongside the old. Nothing reads from it.
2. Backfill historical rows in throttled chunks, watching replication lag and IO on the source. For a multi-TB table this runs for days; make it resumable and idempotent.
3. Keep the new side in sync while the old one remains the source of truth. Start capturing changes before the backfill begins (or from the snapshot position it reads), so no write falls into a gap between the two. The safer default is change data capture: tail the old database's WAL or binlog and apply it to the new topology, so there is one writer and an ordered stream. An application-level dual-write is not atomic (one side can succeed while the other fails), so if you do it — Notion did, with an audit log and a catch-up script replaying missed writes — build in reconciliation.
4. Shadow-read and diff: serve from old, also read from new, compare, emit a mismatch counter. You want a full day at zero mismatches before proceeding. This step is the one people skip and the one that catches the bugs.
5. Flip reads gradually — 1% of tenants, then 10%, then 50% — with an instant rollback that requires no deploy.
6. Flip the source of truth, keep dual-writing for a week as your undo button, then stop and drop the old topology.

Design so you never have to do that again Choose a large fixed number of logical shards up front — 1,024 or 4,096 — and map many logical shards onto each physical machine. Growing the cluster then means moving whole logical shards, never rehashing a single key: the shard key and the routing function never change, only the placement map does. Notion runs this shape: 480 logical shards across 32 Postgres databases, routed in the application, with no Vitess (480 divides evenly across 32, 40 or 48 hosts). Designing Data-Intensive Applications lists this fixed partition count as the simple strategy. The alternative is dynamic splitting, used by Vitess, HBase, Spanner and CockroachDB: each shard owns a range of the key space and is split or merged online as it grows, which adapts without a guess at the right count but needs split-and-merge machinery. Either way, the irreversible decision above becomes a routine capacity operation.

Say it like this → "I'll shard by tenant ID into 4,096 logical shards placed on 16 physical Postgres hosts, with a directory in etcd mapping logical shard to host. Tenant ID is in essentially every query, so reads and transactions stay single-shard, and when a tenant outgrows shared hardware I move its logical shards to dedicated hosts by updating one row in the directory — no rehashing, no ID changes."

Recognizing it in an unseen problem

The numbers force it: estimate data volume and write throughput out loud. "500M users × 2 KB = 1 TB, at 50k writes/sec" is the sentence that justifies sharding without you having to assert it.
A naive design says "we'll add read replicas". Replicas never scale writes — if the prompt's bottleneck is write throughput or dataset size, replicas are the wrong tool and saying why earns the point.
The prompt mentions a skewed population — celebrities, whale tenants, viral content, one huge customer. That is a hot-shard question wearing a costume; go straight to caching, salting, or dedicated placement.
Distinguish from replication: replication makes copies of the same data for availability and read scale; partitioning splits different data for write scale and capacity. Real systems do both, and every shard is itself a replica set.
The moment you name a shard key, immediately name the query it breaks and how you'll serve that query anyway (global index, denormalized copy, or search engine). Volunteering the downside is the difference between L5 and L6.
Never propose hash(key) mod N without saying what happens when N changes — consistent hashing with vnodes, or fixed logical shards, are the two acceptable answers.

Before you move on

Given a candidate shard key, check it against all five required properties — cardinality, access distribution, immutability, query coverage, transaction alignment — and say which ones it fails.
Explain why hash(key) mod N breaks under resizing, and how consistent hashing with virtual nodes fixes it, including why the relative spread of load shrinks as vnode count V grows.
Trace, by hand, which surviving nodes absorb a failed node's arcs on a small consistent-hashing ring — and explain why that split, not a single overloaded neighbor, is what vnodes buy you.
Name at least two mitigations for a hot shard caused by one celebrity key, and say which to reach for first and why.
Explain why choosing a large fixed number of logical shards up front means you never have to rehash a key again when the cluster grows.

Sources and further reading

OpenAI: scaling PostgreSQL — one primary and about 50 replicas at millions of queries per second, with shardable writes moved elsewhere
Notion: sharding Postgres — 480 logical shards on 32 databases, application-level routing, and the dual-write migration
Vitess sharding — keyspace ID ranges per shard, vindexes, and splitting or merging shards
Vitess Reshard — online resharding workflow and its brief cutover
DynamoDB partition key design — the 3,000 read and 1,000 write units per partition limits
EC2 High Memory instances — the family of very large single machines (u7in-32tb: 896 vCPU, 32 TiB)
Cassandra architecture: Dynamo — token rings, virtual nodes and how token counts evolved
Dynamo paper (SOSP 2007) — consistent hashing with virtual nodes and the load-balancing strategies compared

Claims in this chapter were checked against these sources in October 2026. Figures marked "planning figure" are rules of thumb, not guarantees. The ring dry run uses illustrative vnode positions; the key hashes are real MD5 values mod 1000.