Skip to main content
Database Shardinglesson 4 of 4 · 3 min read

Living with Cross-Shard Queries

Queries that name their key stay fast

A query that names its shard key stays fast forever. One person's orders live on one shard, and an index finds them there.

Every other query just got expensive. Sharding did not really make those queries slow. It revealed that they now need a distributed system where an index used to be enough.

Scatter-gather, and why it scales badly

Expect to reach for scatter-gather, which asks every shard at once and merges the answers in your application. It works, and it scales badly in two separate ways.

Load, because one search makes work on every machine you own, so your total cost multiplies by the number of shards. And latency, because you wait for the slowest one to answer. At 16 shards, every such query is a fresh sample of your worst machine on its worst day. Acceptable for an admin screen nobody opens. Poison on a page everybody opens.

Joins across shards mostly stop existing. You replace them two ways. Copy the seller's name onto the order row as you write it, so the read never joins anything. And keep a second copy of the data organised by a different key, updated as changes stream through.

You are paying storage and a more complicated write path to keep your reads on one shard, and that is nearly always the right trade.

Transactions across shards are the sharpest edge in the chapter. A protocol for committing on two machines at once exists, and it is slow and fragile enough that most teams refuse it. They undo the first step when the second one fails, or accept a brief disagreement and reconcile later.

Solve it upstream instead, by picking a shard key that keeps things which must change together on the same machine. That is why keying by tenant is so popular: a tenant's entire world commits in one place.

Analytics belong off your shards entirely. Stream your changes into a warehouse, and let the queries that want all of the data run where all of the data lives.

the shape of it
Order historybuyer 881Query routerShard 012 msShard 19 msShard 2slowest: 400 msno shard keyfan outfan outfan outmerge waits
step 1 of 5
A query with no shard key fans out to every shard and finishes only when the slowest one answers.

Worked example

Ingrid's marketplace shards by seller_id, which makes seller dashboards instant. Then product asks for a buyer order history page, and a buyer's orders are scattered across however many sellers they bought from. Version one scatter-gathers all 16 shards; p99 lands at 600 ms because some shard is always having a bad moment, and every page view multiplies query load 16x during peak. Version two builds a second table, orders_by_buyer, sharded on buyer_id and written through the outbox that already feeds their event bus. Writes now touch two places, the backfill takes a weekend, and order storage doubles, about 40 dollars a month at their size. The page becomes a single-shard read at 9 ms. When product later asks to sort sellers by rating across all orders, that query goes to the warehouse.

Database Sharding: wrapping up

In the real world

  • 01Instagram sharded Postgres early and encoded placement into every ID: 41 bits of timestamp, 13 bits of logical shard, and 10 bits of sequence, so any row's home shard is computable from its ID alone.
  • 02Pinterest's MySQL sharding used thousands of virtual shards mapped onto physical hosts with the shard ID packed into object IDs, and carried the site from tens of millions to hundreds of millions of users.
  • 03Vitess was built at YouTube to shard MySQL behind a routing layer, including live resharding via data copies; Slack later adopted it to break up its monolithic MySQL tier.
  • 04Notion shards Postgres by workspace ID across 480 logical shards, and its 2023 expansion from 32 to 96 physical machines worked by relocating whole logical shards rather than rehashing rows.
  • 05Discord partitions trillions of messages by channel plus a 10-day time bucket, first on Cassandra and later ScyllaDB, precisely so enormous channels cannot pin all their load to one partition.

Questions people ask

At what point do I actually need to shard?

When sustained writes approach what one primary can handle, roughly 5,000 to 10,000 per second for a tuned relational database, or when the working set has outgrown what RAM and archiving can contain, and you have already used caching, read replicas, and a bigger instance. Measure and project first; sharding a database doing 100 writes per second is pure cost.

Can I change my shard key later?

Only by migrating everything, since the key determines where every row lives; changing it is a full resharding project with dual writes and backfills. That is why you choose it against your actual query log. For specific queries the key serves badly, a secondary copy of the data organized by a different key is far cheaper than re-keying the world.

Do unique constraints and foreign keys work across shards?

No. Each shard enforces constraints only on its own rows, so a globally unique email needs either a dedicated lookup service or a design where all rows for that scope live on one shard. Globally unique IDs are usually solved with generation schemes like Snowflake IDs or Instagram-style IDs that embed the shard.

Quick review

Each shard is an independent DB with a subset of rows. Same schema across shards
Hash sharding:
hash(user_id) % N. Even distribution; no range queries; resharding is disruptive
Range sharding:
partition by date range or ID range. Range queries efficient; hotspots possible (recent data)
Directory sharding:
lookup table maps key → shard. Flexible rebalancing but lookup service is bottleneck
Write hotspot:
one key takes a disproportionate share of writes. Fix: add a random suffix to the shard key so the writes spread
Read hotspot:
a celebrity row is read constantly from one shard. Suffixing makes this worse (every read becomes a scatter-gather). Cache the row, replicate it, or give it a separate path, which is why Twitter fans out on write for normal users and on read for celebrities
Cross-shard queries:
joins, transactions across shards are expensive or impossible. Denormalize or use application-layer joins
Resharding:
use consistent hashing to minimize data movement when adding shards. Requires careful data migration
the trade-off

Massive added complexity. Avoid sharding until you've measured that you actually need it.

in the room

A single RDBMS node sustains roughly 5 to 10k writes/sec. Shard when sustained writes approach that, and only after read replicas + caching are exhausted.