Database Sharding & Partition Keys

1. What It Is & Why It Exists

The Core Problem: The Vertical Scaling Wall

A single relational or document database instance is bound by physical hardware constraints: CPU core limits, memory bus bandwidth, NVMe IOPS limits, and operating system file descriptor maximums. When an application scales to tens of terabytes of data or hundreds of thousands of write queries per second:

• Financial Prohibitions: Renting extreme-tier instances (e.g., AWS u-12tb1.112xlarge with 448 vCPUs and 12 TB RAM) costs about $\text{\textdollar}80,000\text{/month}$ per node on demand ($109.20 an hour in us-east-1, Linux).
• Connection & Thread Contention: Thousands of concurrent application worker threads exhaust database connection pools, spending more CPU time on lock arbitration and context switching than on query execution.
• Maintenance Paralysis: Executing standard database maintenance (e.g., PostgreSQL VACUUM, B-Tree index rebuilds, schema migrations, or restoring point-in-time backups) on a monolithic 50 TB database can run for hours or days while competing with live traffic.

The Breakdown: Monolithic Database vs. Shared-Nothing Sharding

Concrete Proof: The Vertical Scaling Wall vs. Horizontal Sharding

Consider a global e-commerce datastore scaling from $2\text{ TB}$ to $40\text{ TB}$ and $5,000$ to $120,000\text{ write QPS}$:

---

The First-Principles Solution: Shared-Nothing Horizontal Partitioning

Database Sharding partitions a massive monolithic dataset horizontally across $N$ independent database servers (shards), where each shard runs on completely separate physical or virtual compute:

1. Shared-Nothing Architecture: Shards share no physical RAM, CPU, or disk volumes, completely eliminating cross-node hardware contention.
2. Deterministic Route Mapping: Incoming queries pass through a routing intelligence layer (smart client driver or gateway proxy) that inspects the query's Partition Key and routes the operation directly to the specific shard owning that key.
3. Fault Domain Isolation: A catastrophic hardware crash or kernel panic on Shard 4 impacts only $1/N$ of keys, allowing $(N-1)/N$ shards to continue processing user traffic without interruption.

Synthesizing vector architecture diagram...

Both panels start with 100k workers sending about 120k QPS. In the "Broken Baseline" panel, all of it lands on one database: connections run out, CPU hits 100%, latency climbs, and even maintenance cannot run. In the "Production Standard" panel, a router computes hash(PK) mod 4 for each request and sends it to the one shard that owns that key; each shard has its own storage and CPU and shares nothing with the others, so each holds about a quarter of the keys (and carries about a quarter of the load only if no single key is hot), and one shard failing affects only a quarter of the keys. The catch: queries that do not include the partition key must ask every shard, so choose the key to match your most frequent query.

---

2. Core Mechanics & Algorithmic Architecture

Sharding Strategies Compared

Synthesizing vector architecture diagram...

1. Hash-Based Sharding

• Mathematical Mechanics: The partition key is hashed using a uniform hash function (non-cryptographic MurmurHash3 or xxHash; MD5, a cryptographic hash, also works and is what Kinesis uses), and mapped to a shard: $\text{Shard ID} = \text{Murmur3}(\text{PartitionKey}) \pmod N$
• Pros: Uniform key distribution; eliminates temporal clustering. It does not even out load: every request for one hot key still lands on the one shard that owns it.
• Cons: Range queries (SELECT * WHERE timestamp BETWEEN t1 AND t2) cannot be routed to a single node and must be executed as Scatter-Gather operations across all $N$ shards. And changing $N$ under mod N moves most keys: going from 4 to 5 shards moves 80% of them, and even doubling moves 50%. Consistent hashing with many virtual nodes, or fixed slots with a directory, moves only about the new shard's share (the section Adding capacity: rings, slots and splits of Sharding, Hot Keys & Rebalancing).

2. Range-Based Sharding

• Mathematical Mechanics: Contiguous lexicographical or numerical key intervals map to dedicated shards: $\text{Keys in } [0, 1000000) \to \text{Shard 1}, \quad [1000000, 2000000) \to \text{Shard 2}$
• Pros: Range scans within an interval execute on a single physical shard.
• Cons: Monotonic Write Hotspotting. Using auto-increment IDs or timestamps routes 100% of concurrent writes to the newest shard, defeating horizontal scaling.

3. Directory-Based (Lookup Table) Sharding

• Mechanics: A centralized distributed coordinator (e.g., DynamoDB, etcd, ZooKeeper) maintains an explicit routing dictionary: $\text{TenantID} \to \text{ShardID}$
• Pros: Extreme flexibility. Individual massive enterprise tenants can be isolated onto dedicated physical hardware without altering cluster-wide hash functions.
• Cons: Introduces an extra network hop to query the directory service (mitigated by local client LRU caching).

---

Formal Mathematical Sizing Formulations

1. Minimum Cluster Shard Sizing Formula

To dimension the required number of physical shards ($N_{\text{shards}}$):

$$N_{\text{shards}} = \max\left( \left\lceil \frac{S_{\text{total}}}{S_{\text{shard\_max}}} \right\rceil, \; \left\lceil \frac{W_{\text{peak}}}{W_{\text{shard\_max}}} \right\rceil, \; \left\lceil \frac{R_{\text{peak}}}{R_{\text{shard\_max}}} \right\rceil \right)$$

Where:

• $S_{\text{total}}$ is the total dataset size (e.g., 20 TB), and $S_{\text{shard\_max}}$ is the safe operational storage ceiling per shard (e.g., 2 TB).
• $W_{\text{peak}}$ is peak write QPS, and $W_{\text{shard\_max}}$ is write throughput ceiling per node.
• $R_{\text{peak}}$ is peak read QPS, and $R_{\text{shard\_max}}$ is read capacity per node.

2. Load Imbalance Factor (Coefficient of Variation)

To quantify partition key skew across $N$ shards:

$$\mu = \frac{1}{N} \sum_{i=1}^N L_i, \quad \sigma = \sqrt{\frac{1}{N} \sum_{i=1}^N (L_i - \mu)^2}$$ $$\text{Coefficient of Variation (CV)} = \frac{\sigma}{\mu}$$

Where $L_i$ is the request load on shard $i$. Lower is better, and the alert threshold is your team's choice (for example $\text{CV} \le 0.10$ as a target). CV is a spread, not the worst case, so also track the busiest shard's load divided by the average: that ratio is what hits a shard's ceiling first.

---

Step-by-Step Deterministic Routing Pipeline

Synthesizing vector architecture diagram...

---

In-Memory Shard Mapping Representation

In production proxies (like Vitess VTGate or Citus Coordinator), routing topologies are maintained in memory as sorted slot boundary tables:

---

Query Execution & Routing Trace Matrix

Under cluster configuration $N = 4$ shards, partition key customer_id, and routing rule $\text{Shard} = \text{Murmur3}(\text{PK}) \pmod 4$:

---

3. Data Migration, Anti-Entropy & Consistency Protocols

1. Online Live Resharding Protocol (Zero-Downtime Cluster Expansion)

When a shard reaches capacity, splitting it (e.g., from $N \to 2N$) without taking the database offline requires a strict 4-phase protocol (modeled after Vitess VReplication and DynamoDB partition splitting):

Synthesizing vector architecture diagram...

---

2. Cross-Shard Transactions: Two-Phase Commit (2PC) vs. Entity Co-Location

Executing atomic transactions spanning multiple shards requires Two-Phase Commit (2PC):

• Phase 1 (Prepare): Coordinator asks all participating shards if they can commit. Shards acquire local locks and write prepare records to their WAL.
• Phase 2 (Commit): If all shards answer "YES", coordinator writes commit to its log and commands shards to commit. If any shard fails, coordinator commands all shards to rollback.
• The Performance Cost: 2PC adds a second round of messages (prepare, then commit), each with a durable log write on the coordinator and the participants, and holds locks across those round trips; a coordinator crash between the phases leaves the participants holding their locks until it recovers.
• The Architectural Safeguard (Entity Co-Location): Design schemas so that related entities (e.g., User, Orders, Payments) share the exact same partition key (customer_id). All related mutations execute within a single shard, completely avoiding cross-shard 2PC!

3. Shard Draining Lifecycles & Anti-Entropy Resharding Verification

• Anti-Entropy Verification Before Cutover: Prior to advancing the routing epoch in Phase 4, background verification jobs execute cryptographic hash sampling across the child shards ($[0x0000, 0x1FFF]$ on Shard 1A vs. source shard). Only when CDC stream lag drops to zero and sample checksums match $100\%$ does the coordinator fence the source (it refuses reads and writes for the moving range with a retryable error), wait until the children have applied everything up to the fence, and then advance the cluster routing epoch.
• Graceful Shard Draining Protocol: When decommissioning a retired source shard:
  1. Keep the source shard refusing the moved range (the fence set before the epoch advanced), so a router with an old map is redirected instead of writing to a copy nobody reads.
  2. Maintain a graceful connection draining window ($60\text{--}120\text{ seconds}$) allowing in-flight transactions to conclude cleanly.
  3. Terminate idle client TCP connections and archive a final storage snapshot to Amazon S3 before de-provisioning instance hardware.
• Stale Topology Cache Invalidation: When an application pod caches an obsolete routing epoch and dispatches writes to a retired shard, the node returns SHARD_MOVED <new_shard_id> <epoch> from a record it keeps permanently, which is what makes the move safe (timers and polls only bound how long a stale client bounces; see the section Moving live data of Sharding, Hot Keys & Rebalancing). Smart client drivers intercept this error, invalidate local memory routing maps, back off with jitter, and fetch the authoritative epoch topology from the coordinator.

---