# Sharding (Part 1: Shard Keys and Routing) ## 1. Sharding Is Partitioning Across Separate Servers `01-database_partitioning/` covered splitting a table into smaller pieces, on one server, for pruning/maintenance benefits. Sharding takes the identical idea — split a dataset by a key into pieces — and adds one more constraint: **each piece (shard) is a separate database instance**, with its own CPU, memory, and disk. Where table partitioning solves "this table is too big to scan/maintain efficiently," sharding solves the problem partitioning alone cannot: **write throughput past what one server's CPU/disk can handle**, because now there are N independent servers each handling only 1/N of the total write load, in parallel. ``` Single leader, replicated (02-replication/): Sharded: ALL writes -> [LEADER] writes for key range A -> [SHARD 1] │ writes for key range B -> [SHARD 2] replicated to followers (reads only) writes for key range C -> [SHARD 3] -> read scaling, NOT write scaling -> write AND read scaling, both split ``` Replication (previous topic) makes copies of the *same* full dataset on multiple machines — every follower can answer any query, but every follower must also absorb every write eventually. Sharding makes each shard hold a *different slice* of the dataset — no shard has the full data, but each shard only has to absorb the writes that land in its slice. ## 2. The Shard Key The shard key is the column (or columns) whose value determines which shard a row lives on — mechanically the same idea as a partition key (`01-database_partitioning/` section 4's rule still applies: match the highest-volume real query pattern), but the stakes are higher, because **moving a row between shards later is a real data-migration operation**, not a cheap metadata change, so a bad shard key is far more expensive to fix after the fact than a bad table-partition key. ``` users table sharded by user_id: shard_for(user_id) = hash(user_id) % NUM_SHARDS user_id=101 -> hash -> shard 2 user_id=204 -> hash -> shard 0 user_id=305 -> hash -> shard 1 ``` A query that includes the shard key in its predicate (`WHERE user_id = 101`) can be routed to exactly one shard. A query that does *not* include it (`WHERE email = 'x@example.com'`, if `email` isn't the shard key) must be broadcast to every shard and the results merged — a **scatter-gather** query, which is strictly more expensive than a single-shard query and, at high shard counts, can dominate total system load if it's common. ## 3. Range-Based vs. Hash-Based Sharding **Range-based sharding** assigns contiguous ranges of the shard key to each shard (shard 1 = user IDs 1-1,000,000, shard 2 = 1,000,001-2,000,000, ...). - Range queries on the shard key (`WHERE user_id BETWEEN ...`) stay single-shard or few-shard. - Risk: if key values aren't uniformly distributed over time or value, ranges fill unevenly — a monotonically increasing key (auto-increment ID, or a timestamp-derived key) concentrates all *new* writes on whichever shard currently owns the highest range, exactly the hot-partition failure mode from `01-database_partitioning/` section 5, just now on a whole database server instead of a table partition. **Hash-based sharding** applies a hash function to the shard key and uses the hash (mod shard count, or via consistent hashing — see `databases/caching/08-distributed_caching/` for the same technique applied to cache nodes) to pick the shard. - Spreads load evenly regardless of the key's natural distribution — the classic fix for range sharding's hot-shard risk. - Cost: destroys range-query locality entirely. `WHERE user_id BETWEEN 100 AND 200` under hash sharding could touch every single shard, since hashed outputs for adjacent inputs land anywhere. The choice mirrors `01-database_partitioning/` section 6's pitfall #3 exactly, just at server-instance scale rather than table-partition scale: pick range if range queries on the key are common and even growth can be engineered (e.g. pre-splitting ranges, or using a key with better distribution than raw auto-increment); pick hash if point lookups dominate and even load distribution matters more than range-query locality. ## 4. The Routing Layer Something has to know, for a given shard key value, which physical shard to send the query to. This routing logic lives in one of a few places: - **Client-side / application-level routing** — the app computes `shard_for(key)` itself and connects to the right database directly. Simple, no extra network hop, but every service that talks to the database needs the same routing logic kept in sync. - **A routing proxy/middleware tier** — a dedicated layer (e.g. `mongos` in MongoDB's sharded clusters, Vitess for MySQL) sits between the application and the shards, accepts a query, determines the shard(s) it needs, and forwards it — centralizing the routing logic outside application code, at the cost of an extra network hop and an additional component to run and keep available. - **A shard map / metadata service** — a small, separately-replicated store (often itself just a tiny highly-available database, or something like etcd/ZooKeeper) that holds the current key-range-to-shard or hash-to-shard assignment, which the routing layer consults — critical once shard assignments can *change* over time (see Part 2, resharding), since routing can no longer be a pure stateless function of the key alone once ranges move. ![A router maps tenant_id to one of three independent shard databases; queries with the shard key hit one shard while queries without it scatter to all shards](diagrams/01-shard-routing.svg) ## 5. Quick Reference (Part 1) ``` Sharding = partitioning across SEPARATE DATABASE SERVERS -> solves write-throughput scaling (replication alone only scales reads; sharding scales both reads and writes) Shard key: picks which shard a row lives on -> match it to the highest-volume query pattern Single-shard query: predicate includes the shard key -> routed to exactly one shard Scatter-gather query: predicate omits the shard key -> broadcast to every shard, merged -> expensive Range sharding: contiguous key ranges per shard -> good range-query locality, hot-shard risk Hash sharding: hash(key) picks the shard -> even spread, destroys range-query locality Routing layer: client-side logic, a proxy/middleware tier, or a shard-map metadata service ``` Part 2 (`dbscale_sharding_theory_2.md`) covers what happens when shard assignments must change: resharding/rebalancing, cross-shard queries as sharding's ongoing cost, and the hot-shard problem in its sharding-specific form (the "celebrity" problem).