Sharding & partitioning at scale

One machine is a limit, not a bug — but the shard key you pick in week one is the decision you will still be paying for in year five.

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	A modern cloud box tops out around 400+ vCPU and 24 TB of RAM. A well-tuned Postgres on NVMe handles roughly 5–10k simple indexed reads/sec per core-rich box and low thousands of write TPS.	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)	Removes 80–95% of reads for skewed workloads at ~0.3 ms per hit.	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 and index-only scans often buy a full order of magnitude.	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 cache line and in RAM; horizontal partitioning is the only one that removes the single-machine ceiling.

Vertical partitioning splits a table by column — move the 40 KB bio_text and the blob out to a separate store so the hot 60-byte row stays cache-resident. It is cheap, reversible, and often worth a 3–5× improvement in rows-per-page. 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.	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 — and only from its immediate successor.

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 — shard sizes routinely vary by 2–3×. 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 (Dynamo used ~100–200; Cassandra's num_tokens defaulted to 256 historically and 16 in modern versions with the token allocation algorithm). Load variance 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, ~50ns.
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.

Hot shards and the celebrity problem

Real access distributions are Zipfian: the top 0.1% of keys often carry 40–60% of the traffic. 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 typically multiplies write latency by 3–10×. 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. Use UUIDs/Snowflake IDs so uniqueness is probabilistic-by-construction, or keep 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. Dual-write every mutation to both topologies, with the old one remaining the source of truth. Failures writing to the new side are logged, not fatal.
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. Vitess, Slack, Notion and most well-run sharded fleets are built exactly this way, and it converts the irreversible decision above into 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.

Do this first

Buys you

Runs out when…

Vertical scaling

A modern cloud box tops out around 400+ vCPU and 24 TB of RAM. A well-tuned Postgres on NVMe handles roughly 5–10k simple indexed reads/sec per core-rich box and low thousands of write TPS.

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)

Removes 80–95% of reads for skewed workloads at ~0.3 ms per hit.

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 and index-only scans often buy a full order of magnitude.

The hot set alone exceeds RAM, or write throughput exceeds one primary.

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.

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.

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.

// Ring = sorted array of {token, node}. Lookup is a binary search, ~50ns. 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 }

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 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 typically multiplies write latency by 3–10×. 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. Use UUIDs/Snowflake IDs so uniqueness is probabilistic-by-construction, or keep 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.