Horizontal sharding and consistent hashing

Horizontal database sharding

Horizontal sharding partitions a single logical table across multiple independent physical database instances (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:

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: $\text{Shard} = \text{hash}(\text{shard\_key}) \bmod N$.
• Pros: Uniform distribution of writes across all $N$ shards.
• Cons: Resharding is expensive. Going from $N$ to $N+1$ shards changes the result of $\bmod$ for about $\frac{N}{N+1}$ 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 $\frac{1}{N+1}$ 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:

1. High Cardinality: The key must have millions of distinct values (e.g. user_id or account_id, never country_code or status).
2. Uniform Write Distribution: Avoid monotonically increasing sequences as primary keys on range-sharded systems.
3. 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)$ 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):

1. Broadcast the query in parallel to all $N$ physical shards.
2. Collect $N$ result streams.
3. 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 $p$,

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

5. Globally unique distributed ID generation

Auto-increment primary keys cannot be shared across independent database shards. Common alternatives:

• Twitter Snowflake (64-bit integer): IDs are roughly time-ordered ("k-sorted"):
  $$\underbrace{41\text{ bits}}_{\text{ms timestamp, custom epoch (69 years)}} + \underbrace{10\text{ bits}}_{\text{machine id (1,024 machines)}} + \underbrace{12\text{ bits}}_{\text{sequence (4,096 per ms per machine)}}$$
  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-tree index; random UUIDs (v4) scatter inserts across the index, which can hurt performance dramatically.