Database Scaling: Sharding, Partitioning & Replication

A single monolithic database server hits physical ceilings: NVMe throughput caps at ~7–14 GB/s, memory buses saturate, and replication threads lag behind master writes. Once your dataset exceeds 5–10 Terabytes or write volume surpasses 20,000 writes/sec, you must partition your database horizontally across independent nodes. This is Database Sharding.

1. 01The Modulo Re-Sharding Catastrophe: Under naive shard = hash(key) % N, changing node count from $N$ to $N+1$ alters the remainder calculation for nearly all keys. Approximately $N/(N+1)$ of the entire database (~80% when scaling from 4 to 5 nodes) must be rehashed and transferred across the network, saturating storage and causing multi-hour outages.
2. 02The Scatter-Gather Tail Latency Trap: When a query omits the shard key (e.g. SELECT * FROM orders WHERE status = "PENDING"), the query coordinator must broadcast requests to ALL 100 shards simultaneously and merge the results. If each shard has a P99 latency of 50ms, the mathematical probability of a 100-shard scatter-gather query taking $\ge 50\text{ms}$ is $1 - (0.99)^{100} = 63.4\%$! The client’s median response time becomes governed by the slowest, most degraded node in the entire cluster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

DIRECT QUERY ROUTING (O(1) Single-Shard Hop):
  [Client Query: WHERE user_id = 42]
         |
         v
  [Query Router (Vitess / Proxy)] --(hash(user_id) % N)--> [Shard 2 Only] (Fast, < 2ms)

SCATTER-GATHER FANOUT (Omitting Shard Key):
  [Client Query: WHERE status = 'PENDING']
         |
         v
  [Query Router (Coordinator)]
     +----(Broadcast)----> [Shard 1] (12ms)
     +----(Broadcast)----> [Shard 2] (15ms)
     +----(Broadcast)----> [Shard 3] (480ms - GC stall / lock wait!)
         |
         v
  * Client latency = 480ms (Bound to the slowest tail node in the cluster!)

1. 011. Table Co-Location by Entity: Store related tables (users, orders, order_items) on the SAME physical shard using a shared user_id routing key. This allows 99% of customer transactions and relational joins to execute locally on a single machine with full ACID integrity.
2. 022. Cross-Shard Transactions (Saga > 2PC): When mutations span multiple shards (e.g., deducting inventory on Shard 1 and charging balance on Shard 2), avoid Two-Phase Commit (2PC) because coordinator crashes cause shards to hold row locks indefinitely. Instead, use an asynchronous Saga pattern with local ACID transactions and compensating actions.
3. 033. The Celebrity Shard Pattern: Route normal users by user_id. For designated celebrity accounts (e.g. 50M followers), route their posts by post_id across all shards and use Fan-out on Read (merging dynamically at query time) to avoid single-shard write bottlenecks.
4. 044. Zero-Downtime Resharding Pipeline: 1) Enable dual-writing at the routing proxy. 2) Backfill historical records via Change Data Capture (CDC) replication. 3) Run shadow validation checks to verify parity. 4) Atomically switch read routing to the new shard topology.