Module P-6·24 min read

Hash vs range vs directory partitioning, hot partitions, and the cross-shard queries and joins nobody plans for.

JJS

Written by Jatin Jain Saraf · Senior Software Engineer

Module P-6 — Sharding and Partitioning

Q: A team shards `orders` by `hash(order_id)` because it distributes perfectly evenly. After moving from 4 shards to 32, the customer order-history page's p99 rises from 40 ms to 900 ms, while every individual shard reports a p99 under 50 ms.

The query filters on `customer_id`, not the shard key, so every read is a scatter-gather across all 32 shards — and it completes only when its slowest branch does, so a large fraction of requests contain a p99 branch and aggregate p99 approaches a single shard's far tail. Shard on `customer_id` instead. — This is the module's central rule plus its arithmetic. `order_id` is uniform but appears in one query; everything the storefront actually asks carries `customer_id`, so the key is absent from the majority of reads and each must ask all shards. Because the response waits on the slowest branch, `1 − 0.99^32` of requests include a p99 branch — which is why per-shard p99 looks healthy while the aggregate degrades, and why *adding* shards made it worse. Option B is the strongest near-miss: consistent hashing is real, but it addresses rebalancing when the node set changes, not fan-out caused by a missing key. Option C names a genuine consequence of sharding (Module P-4's pool multiplication), but that would slow every endpoint, not specifically the query that fans out. Option D invents replicas the scenario doesn't have, and lag produces stale data rather than this latency shape.

Q: A 16-shard system hash-partitions on `tenant_id`. Distribution looked even in staging. In production one shard runs at 90% write utilisation with a two-second p99 while the other fifteen sit near 12%, and the skew traces to one enterprise tenant holding roughly 40% of all rows.

No hash function can split a single key, and raising the shard count redistributes everything except the problem — so either shard on a compound `(tenant_id, bucket)` key, accepting that every read for that tenant now fans out across buckets, or give the tenant a dedicated shard via a directory, accepting special-case routing and bespoke capacity planning. — Hashing distributes keys evenly, not traffic, and a whale tenant is a single key that hashes to a single value and therefore one bucket. Both remedies carry the costs the module states: salting into `(tenant_id, bucket)` converts a hot partition into a scatter-gather for that tenant, and a dedicated shard costs special-case routing plus a shard you capacity-plan separately. Option D is the genuine near-miss and the thing teams reach for first — it is a real technique that does reduce per-shard keyspace, but tenant 42 still lands wholly on one shard, so the hot shard stays hot and you have funded a resharding project to relocate its innocent neighbours. Option A conflates two problems the module separates: virtual nodes address rebalancing and ring skew (Module P-7), not one oversized key. Option B misreads the symptom entirely — the shard is write-saturated, and every replica applies all of those same writes.

What this module covers: The escalation order that gets you here — index, vertical scaling, read replicas, then shard — and why sharding is last. Partitioning inside one system versus sharding across many, which turn on the same key choice. Hash, range, and directory strategies with the specific failure each produces. Hot partitions and the one whale account that breaks an even scheme. Choosing a shard key that appears in your queries, what scatter-gather costs at the tail, why multi-shard writes become distributed transactions, Postgres pruning and the unique-index constraint, and why resharding cannot be done casually.

Sharding Is the Fourth Thing You Try, Not the First

The pager reason that leads here has one shape: writes at 400 ms p99, a 900 GB table, autovacuum falling behind, and the largest instance the cloud sells already running the database. Someone says "we need to shard." Usually they do, eventually. Almost never this week, and finding that out in the wrong order costs a year.

Step	Buys you	Costs you
1. Index / query fix	10–1000× on one query path	Write amplification, storage, one more thing the planner can misjudge (Module F-13)
2. Vertical scaling	2–8× on everything, no code change	Money, non-linearly; a hard ceiling; a failover restart
3. Read replicas	Near-unbounded read capacity	Replication lag, so read-your-writes breaks (Module P-5); zero write capacity
4. Sharding	Write throughput, working set, index size all divided by N	Cross-shard reads and joins, distributed transactions, a key you can't change

Read the third row twice. It is the most common misdiagnosis here: replicas get added because reads are slow, when the real constraint was write throughput or working-set size, and every replica applies all the writes. Two cheaper steps also sit between 3 and 4 — archiving old rows, since a 900 GB table where 800 GB is older than 90 days is not a sharding problem, and moving one hot table to its own database.

Why this matters in production: sharding does not reduce total work. It divides work across machines and adds coordination on top. A design 3× too slow from a missing index is 3× too slow on eight shards, and you now debug it across eight machines through a router.

Partitioning Splits a Table; Sharding Splits the Fleet

Partitioning splits one logical table into physical pieces inside a single database system: one transaction manager, one WAL. Joins, foreign keys, and ACID transactions still work across partitions, because there is still one database.

Sharding splits data across independent systems, each with its own storage and failure domain. Nothing spans them for free. A cross-shard join is application code. A cross-shard transaction is a distributed transaction (Module A-3). A backup is N backups not taken at the same instant.

Analogy: partitioning is labelled drawers in one filing cabinet — you walk to one cabinet, and the clerk who manages it can see every drawer. Sharding is opening branch offices in different cities. Each branch is faster because it holds less, but no clerk can see everything, and "find this customer's file" depends entirely on whether the label tells you which city to drive to. If it doesn't, you drive to all of them.

They belong together because the hard part is identical: every row needs a bucket, and a key decides which. Choose badly and partitioning gives you a table where no query can prune, while sharding gives you a fleet where every query fans out. Same mistake, different blast radius — which is the argument for partitioning first. Range-partitioning by month is reversible in an afternoon and tells you whether your queries carry the key.

Three Ways to Pick the Bucket, Three Distinct Failures

Strategy	How the bucket is chosen	Good at	Characteristic failure
Range	Ordered boundaries: `created_at` by month, IDs 1–1M	Range scans, time windows, cheap retention	Hot partition on recent data — all writes hit the newest bucket
Hash	`hash(key) mod N`, or a ring	Even write spread, no boundary management	No efficient range scans — adjacent keys scattered by design
Directory	An explicit key → shard map	Arbitrary placement; move one tenant alone	The lookup service becomes a dependency and a bottleneck

Range fails on temporal skew. Partition events by month and every insert today lands in one partition: it holds the hot index pages, takes the WAL traffic, absorbs the lock contention, while eleven idle. Storage is distributed perfectly and writes not at all — and sequential integer keys have the same shape, every new signup on the last shard. The exchange is real, though: DROP TABLE events_2025_01 is an instant retention policy where deleting 200 million rows is a week of vacuum work. Range is excellent for read-mostly history, poor on the write path.

Hash fails because you gave up ordering deliberately. hash(user_id) spreads users evenly and guarantees that "signups in the last hour" and "the next page after this cursor" have no locality at all. Cursor pagination (Module F-8) is what bites: a cursor is an ordering assumption, and hashing destroyed the ordering.

Directory fails by being a new single point of failure. A shard map — a small table, etcd, Redis — is the most flexible option and what most mature multi-tenant systems converge on, because moving a noisy tenant becomes an operation rather than a project. Its availability caps yours: map down means you cannot route, so you cannot serve. And you will cache it in every process, because a hop per query is unacceptable, so a tenant migration leaves some processes writing to a shard that is no longer authoritative — which needs a read-only window in the migration protocol, not a shorter TTL.

The Shard Key Must Be in the Query, or Every Read Fans Out

The rule: the shard key must appear as an equality predicate in the large majority of your queries — above all the latency-critical ones.

Take an orders table. order_id is perfectly uniform under hashing and present in exactly one query: "fetch this order." Order history, unpaid balance, and the cart badge all carry a customer_id and no order_id, so each must ask every shard. customer_id is slightly less uniform, since customers order at different rates, but present in nearly every storefront query — so a customer's whole history sits on one shard and the read costs what the unsharded version cost. It is the less uniform option and the right one: query locality beats distribution evenness, up to the point where one key gets hot.

The test before committing: take the top 20 queries by total time from pg_stat_statements and mark whether the candidate key appears as an equality predicate. Fewer than roughly 15 means the key is wrong. Two hours of work that routinely saves a quarter.

For queries that don't carry it: denormalise the key downward, carrying customer_id on order_items so items co-locate with their customer — Module F-13's denormalisation trade with the staleness condition free, because the value never changes after insert. Or add a small unpartitioned lookup (email → customer_id) to turn a login into a single-shard read, at the cost of a second write and therefore the dual-write problem (Module F-14).

Hot Partitions and the One Account That Breaks Everything

Here is the failure that surprises people, because the scheme looked right in staging: hashing distributes keys evenly, not traffic. Traffic follows users, and user activity is closer to a power law than a uniform.

The symptom: sixteen shards, one at 90% write utilisation with a p99 of two seconds, fifteen at 12%. Nothing is misconfigured. One key is enormous — the enterprise tenant with 40% of the rows, the celebrity whose every post fans out to 90 million followers, the internal service account every job writes as.

No hash function can split a single key. hash(tenant_42) is one value and maps to one bucket. Going from 16 shards to 64 redistributes everything except the problem — tenant 42 still lands entirely on one shard, now sharing it with a quarter as many innocent neighbours. Consistent hashing doesn't help; it solves rebalancing, not skew (Module P-7).

What works, with costs named:

Compound or salted key. Shard on (tenant_id, bucket) with bucket = hash(row_id) mod 16, spreading one tenant across sixteen shards. The cost is permanent: every read for that tenant now fans out to sixteen shards, so you traded a hot partition for a scatter-gather. Salting everyone keeps the code uniform and makes everyone pay; salting selectively means two code paths.
A dedicated shard for the whale. What a directory is for, and usually right for the SaaS case. It costs special-case routing, bespoke capacity planning for that shard, and a precedent you'll repeat for the next four whales.
Change the access pattern instead. The celebrity problem is solved by not doing the fan-out write — reading their posts on demand rather than pushing into 90 million inboxes. Module A-14's news-feed capstone works that through, and it is the honest answer: some hot keys are telling you the design is wrong.

Why this matters in production: hot partitions live in your users' distribution, so synthetic uniform load cannot find them — a load test with random keys shows sixteen evenly-loaded shards and proves nothing. You need real key-frequency data before committing, and an alert on per-shard skew afterwards. Module P-8 takes this into the isolation models that structurally contain a noisy neighbour; Module P-18 into the per-tenant limits that stop one tenant eating a shard's budget.

Scatter-Gather Pays Module F-4's Fan-Out Tax

A query without the shard key becomes scatter-gather: ask all N shards, merge. The naive expectation is that it costs one query. It completes when its slowest branch completes, and if each shard independently serves p99 = 50 ms, the chance at least one of N is in its slow tail is 1 − 0.99^N:

Shards	Chance of hitting at least one p99 branch
4	~4%
16	~15%
64	~47%
100	~63%

At 64 shards nearly half of requests contain a p99 branch, so the p99 of the whole approaches a single shard's p99.9 or worse. Adding shards can make the system slower at the tail while making each shard faster — which is why "we doubled the shards and p99 got worse" is a real report, not a measurement error.

Three further costs, escalating:

Aggregations get subtly wrong. COUNT and SUM compose across shards; AVG doesn't unless you gather sum and count separately, and percentiles don't compose at all, for the reason F-4 gives. LIMIT 20 ORDER BY created_at means asking every shard for its top 20 — 20N rows fetched to return 20.

Cross-shard joins are application code. Two tables sharded on different keys cannot be joined by the database. Options: a small reference table broadcast to every shard (fine for countries, not for products); denormalise the joined field onto the row; or pull both sides into the application, which is an N+1 with network hops (Module F-8). Choose the key so the joins you need are co-located.

Multi-shard writes stop being transactions. A single-shard write is an ordinary ACID transaction with all of Module P-1's guarantees. A write spanning two shards has no shared transaction manager, so you get two-phase commit, which blocks if the coordinator dies mid-protocol; a saga with compensation you write yourself; or the outbox, which makes the local write atomic and propagation asynchronous. All three are Module A-3's subject and far more work than BEGIN … COMMIT. Keep multi-shard writes on an exception path.

Postgres Partitioning: Pruning, and the Unique-Index Constraint

sql

CREATE TABLE events (
  id          bigint GENERATED BY DEFAULT AS IDENTITY,
  tenant_id   bigint NOT NULL,
  occurred_at timestamptz NOT NULL,
  payload     jsonb NOT NULL,
  -- The partition key MUST be in the primary key. `PRIMARY KEY (id)` is
  -- rejected outright, so the only PK you can declare is a composite.
  PRIMARY KEY (id, occurred_at)
) PARTITION BY RANGE (occurred_at);

CREATE TABLE events_2026_07 PARTITION OF events
  FOR VALUES FROM ('2026-07-01') TO ('2026-08-01');

Partition pruning is the payoff: the planner excludes partitions that cannot contain matching rows.

sql

-- Prunes to one partition. This is the query the design exists for.
SELECT count(*) FROM events
 WHERE occurred_at >= '2026-07-01' AND occurred_at < '2026-07-08';

-- Prunes nothing: no predicate on occurred_at. Every partition's index is
-- scanned and merged — scatter-gather inside a single database.
SELECT * FROM events WHERE tenant_id = 42 ORDER BY occurred_at DESC LIMIT 20;

The second query is this whole module in four lines. Partitioning by time while querying by tenant means a per-partition index scan on every read, worsening each month as partitions accumulate. Pruning happens at plan time for constant predicates, and at execution time when the value is only known then — a parameterised query, or a nested loop — but verify which you get with EXPLAIN, because "I partitioned it and it got slower" is nearly always "nothing pruned."

The unique-index constraint is the sharp edge. A unique index on a partitioned table must include all partition key columns, because Postgres enforces uniqueness with per-partition local indexes and has no index spanning partitions.

So on the table above you cannot declare UNIQUE (email). The closest Postgres accepts is UNIQUE (email, occurred_at), which enforces nothing you wanted — the same address in July and August satisfies it. Global uniqueness on a non-key column needs a separate unpartitioned table written in the same transaction, and once you shard rather than partition, even that transaction is gone and you are back to the dual-write problem. This constraint alone kills a lot of partitioning proposals.

Resharding Is Why Module F-14 Called This the Hardest Decision to Reverse

Module F-14 said the partition key is the hardest decision to reverse. Here is the mechanism. Changing it means every row potentially moves while the system stays up:

Stand up the new topology alongside the old.
Dual-write every mutation to both, tolerating divergence on partial failure.
Backfill history — a full scan of a very large table, competing with production for IOPS.
Reconcile counts and checksums per key range, repair, repeat, because step 2 leaked.
Shadow-read from the new topology and compare without serving.
Cut over reads, keeping the old side writable so you can roll back, and only then stop dual-writing and delete.

Months for a large dataset, every step a place where a bug writes to the wrong shard. Compare adding an index: minutes, CONCURRENTLY, reversible with a DROP.

Three decisions made before sharding make this far cheaper. Over-provision logical buckets — hash into a large fixed count, say 1,024, and map buckets to physical shards, so growing the fleet moves whole buckets and never rehashes a row. Highest-leverage item here, and it costs a routing layer from day one. Use a directory, so moving one tenant is a map update and a copy. And never use mod N with N as the machine count, because adding one machine rehashes nearly every key — the problem Module P-7 exists to solve.

Why this matters in production: the cost asymmetry should change what you do at design time. A week spent writing down the top 20 queries, confirming they carry the key, and measuring real key skew is cheap insurance against a two-quarter migration. This is the one place in the course where analysis genuinely beats iteration, because the iteration loop is measured in months.

Where This Shows Up in Your Stack

PostgreSQL: PARTITION BY RANGE/LIST/HASH; verify pruning with EXPLAIN rather than trusting it; the partition key must be in every unique index. Citus distributes tables on a chosen column and co-locates tables sharing it — the "make joins local" rule as a product feature. Its cost is that non-co-located queries become coordinator-side scatter-gather.
Node.js: the router is a thin key → pool function, and the trap is pool multiplication. Eight shards × 20 connections × 30 instances is 4,800 connections against databases whose default max_connections is 100 (Module P-4). Shard-aware pooling bounds total connections, not per-shard ones.
Redis: Redis Cluster splits the keyspace into 16,384 hash slots — the over-provisioned-bucket pattern shipped as a product. Multi-key operations must land in one slot, which is why hash tags (user:{42}:cart) exist: they force related keys to co-locate. Violating co-location returns an error rather than a slow query, arguably the better failure.
DynamoDB and Cassandra: both make the partition key explicit in the API, so "the key must be in the query" is enforced at design time instead of discovered in production. DynamoDB throttling one hot partition key is this module's failure with a billing line attached (Module O-8).

Summary

Escalate in order: index → vertical scaling → read replicas → shard. Replicas add read capacity and zero write capacity; sharding is the only step that divides writes, and the only one you cannot undo cheaply.
Partitioning splits a table inside one system; sharding splits across independent systems — keeping joins and transactions, or giving them up. The key logic is identical, so partition first.
Range hot-spots on recent data; hash destroys range scans and ordering; a directory becomes a dependency whose availability caps yours. Pick the failure you can live with, and write it down.
The shard key must be an equality predicate in the large majority of queries — check the top 20 by total time — or every read is a scatter-gather. Query locality beats distribution evenness.
Hashing distributes keys, not traffic. A whale is one key, and no hash or shard-count increase splits it. Salting costs that tenant a permanent fan-out; a dedicated shard costs special-case routing; sometimes a hot key means the design is wrong (Modules P-8, A-14).
Scatter-gather pays F-4's fan-out tax: at 64 shards ~47% of requests hit a p99 branch, so aggregate p99 approaches a single shard's far tail. AVG, DISTINCT, and percentiles don't compose, cross-shard joins are application code, and multi-shard writes become distributed transactions (Module A-3).
Postgres pruning fires only on a predicate over the partition key, and a unique index must include that key — so global uniqueness on email is unenforceable on a time-partitioned table.
Resharding is dual-write, backfill, reconcile, shadow-read, cut over, clean up — months. Over-provision logical buckets and use a directory so the fleet grows without rehashing.

The next module, Consistent Hashing, attacks the problem this one kept deferring: adding and removing nodes without rehashing the keyspace. It covers the ring, virtual nodes as the answer to the skew a plain ring produces, and how Redis Cluster's slots and Cassandra's token ranges decide which node owns a key — the mechanism that turns resharding from a project into an operation.

Knowledge Check

A team shards orders by hash(order_id) because it distributes perfectly evenly. After moving from 4 shards to 32, the customer order-history page's p99 rises from 40 ms to 900 ms, while every individual shard reports a p99 under 50 ms.

An events table is range-partitioned monthly on occurred_at. A developer adds UNIQUE (email, occurred_at) after Postgres rejected UNIQUE (email), then finds the same address inserted in both July and August.

A 16-shard system hash-partitions on tenant_id. Distribution looked even in staging. In production one shard runs at 90% write utilisation with a two-second p99 while the other fifteen sit near 12%, and the skew traces to one enterprise tenant holding roughly 40% of all rows.

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule P-5: Replication Next Module P-7: Consistent Hashing

Discussion

Join the discussion

Loading comments...