Range vs hash partitioning, shard routers, cross-shard joins, two-phase commits, and distributed IDs.
What you will learn
Compare range, modulo-hash and consistent-hash sharding, including what moves when a shard is added.
Choose a shard key by cardinality, write spread and query co-location.
Handle queries without the shard key, transactions across shards, and IDs that are unique across shards.
Horizontal database sharding
Horizontal sharding partitions a single logical table across several independent databaseservers (shards) where each shard holds a mutually exclusive subset of rows. As with federation, each shard sees less traffic, has less to replicate, keeps more of its (smaller) data and indexes in memory, and accepts writes in parallel with the others. If one shard goes down the others keep working, but you still need replication within each shard to avoid losing its data.
In the ideal case, where load spreads evenly across shards:
Total capacity≈N×Capacityshardwhat its symbols mean
In practice distribution can become lopsided: a set of power users on one shard can load it far more than the others.
1. Partitioning strategies
A. Range-based sharding
Mechanism: Rows are assigned to shards based on contiguous key ranges (e.g. Shard 1: user_id 1–1,000,000; Shard 2: user_id 1,000,001–2,000,000; or by creation dates).
Pros: Efficient range scans (WHERE created_at BETWEEN '2026-01-01' AND '2026-03-31').
Cons: High risk of hotspotting — all new writes hit the highest range shard while older shards sit idle.
B. Hash-based (modulo) sharding
Mechanism:Shard=hash(shard_key)modNwhat its symbols mean.
Pros: Uniform distribution of writes across all N shards.
Cons:Resharding is expensive. Going from N to N+1 shards changes the result of mod for about N+1N of all keys (80% when going from 4 to 5 shards), forcing a cluster-wide data migration.
C. Consistent hashing with virtual nodes
Mechanism: Keys and shards are hashed onto the same circular hash space (a ring); each key belongs to the first shard found moving clockwise from it. The arrival or departure of a shard only affects its immediate neighbors on the ring.
Virtual nodes: Placing each shard at a single point spreads keys unevenly, so systems such as Amazon's Dynamo give each physical node many points ("virtual nodes"). This evens out the load and spreads a new node's intake across many existing nodes.
Rebalancing: Adding a shard moves only about N+11 of the keys (the new shard's fair share), and all of them move onto the new shard. Try it in the visual below.
2. Shard key selection criteria
Choosing the wrong shard key is the most expensive mistake in distributed database architecture:
High Cardinality: The key must have millions of distinct values (e.g. user_id or account_id, never country_code or status).
Uniform Write Distribution: Avoid monotonically increasing sequences as primary keys on range-sharded systems.
Query Co-location: Queries should target a single shard via the shard key. If 90% of queries filter by account_id, sharding by account_id ensures O(1)what its symbols mean single-shard routing.
3. Distributed joins and cross-shard queries
When a query cannot specify the shard key (e.g. SELECT * FROM orders WHERE status = 'PENDING'), the shard router must execute a Scatter-Gather (Fan-Out):
Broadcast the query in parallel to all Nwhat its symbols mean physical shards.
Collect N result streams.
Merge, re-sort, and paginate the results in the router's memory.
A scatter-gather query is only as fast as its slowest shard (chapter 1's tail-latency effect): if each of N shards is independently slow with probability pwhat its symbols mean,
P(the query is slow)=1−(1−p)Nwhat its symbols mean
which grows quickly with N. Joining data across shards is likewise more complex, and the application logic must know how to work with shards.
4. Distributed transaction coordination
Pattern
Mechanism
Pros
Cons
Two-phase commit (2PC)
A coordinator asks every participant to prepare, and commits only if all vote yes; otherwise all abort.
All participants commit or none do (atomic commit)
Participants hold locks while they wait for the decision, and the protocol blocks if the coordinator fails
Saga
A sequence of local transactions, coordinated by events (choreography) or by an orchestrator, with compensating transactions to undo completed steps if a later one fails.
No distributed locks; each step commits on its own
Compensations must be written by hand, and there is no isolation: concurrent sagas can see each other's partial work, so anomalies need countermeasures
5. Globally unique distributed ID generation
Auto-incrementprimary keys cannot be shared across independent databaseshards. Common alternatives:
Twitter Snowflake (64-bit integer):IDs are roughly time-ordered ("k-sorted"):
ms timestamp, custom epoch (69 years)41 bits+machine id (1,024 machines)10 bits+sequence (4,096 per ms per machine)12 bits
That is 63 bits, so every ID fits in a 64-bit integer.
UUIDv7 (128-bit, RFC 9562): A 48-bit Unix millisecond timestamp followed by random bits. Because successive values sort together, inserts land near each other in a B-treeindex; random UUIDs (v4) scatter inserts across the index, which can hurt performance dramatically.
Sharding and routing a key
Shard routerRouting key: user_9482 ➔ Shard DB-2
Shard DB-1
64 vnodes · 23% of ring
2,500 write RPS1.2M rows
Shard DB-2
Target
64 vnodes · 23% of ring
2,500 write RPS1.3M rows
Shard DB-3
64 vnodes · 28% of ring
2,500 write RPS1.5M rows
Shard DB-4
64 vnodes · 26% of ring
2,500 write RPS1.6M rows
If you add shard 5 now: 20% of keys move to a different shard (measured on 2,000 sample keys; the minimum possible is about 20%, the new shard's fair share).
Strategy trade-off: Consistent hashing places each shard at many points ("virtual nodes") on a hash ring; a key belongs to the first shard clockwise from it. A new shard takes over only the arcs just before its own points, so only about 1/(N+1) of keys move, and only onto the new shard.
Follow a query from the app servers: the shard router hashes its shard key and sends it to the one shard whose range holds that hash. Each shard holds a quarter of the rows, so the four together carry about four times the load of one, if the keys spread evenly. A query without the shard key must go to all four and wait for the slowest.
App servers: 1 × Users
Shard router: 4 × Load balancer
Shard 0: 2 × Relational database
Shard 1: 2 × Relational database
Shard 2: 2 × Relational database
Shard 3: 2 × Relational database
App servers sends requests to Shard router
Shard router sends requests to Shard 0
Shard router sends requests to Shard 1
Shard router sends requests to Shard 2
Shard router sends requests to Shard 3
Key takeaways
Range sharding keeps range scans cheap but sends new writes to one hot shard; modulo hashing spreads writes but moves about N+1Nwhat its symbols mean of the keys when a shard is added.
Consistent hashing with virtual nodes moves only the new shard's fair share, about N+11.
A query without the shard key scatters to every shard and is as slow as the slowest: 1−(1−p)Nwhat its symbols mean.
Cross-shard writes need two-phase commit (locks, blocking) or a saga (compensations, no isolation); IDs come from Snowflake or UUIDv7, not auto-increment.