Sharding

1Sharding 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.

2The 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.

3Range-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.

4The 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.

📋 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 1 covered choosing a shard key and routing scheme. This part covers the ongoing costs that show up after a sharded system is running: what happens when the shard count or shard boundaries need to change, why queries spanning multiple shards are sharding's most persistent tax, and how a single outsized key can still create a hot shard even with a well-chosen key.

1Resharding: Why Shard Counts Change

A shard count picked today is a guess about future data volume. Two forces eventually break that guess: uneven growth (some shards fill faster than others even under hash sharding, if the underlying dataset itself isn't perfectly uniform — e.g. hash sharding by user_id still concentrates data if some users generate vastly more rows than others), and simply outgrowing the total capacity of the current shard count and needing to add more shards to spread the same data thinner.

Resharding is the process of changing shard assignments — adding shards and redistributing data onto them, or splitting an overloaded shard into two. This is fundamentally different from adding a table partition (cheap, metadata-only in most systems) because the data itself must physically move between servers:

Before (4 shards, hash mod 4):          After (8 shards, hash mod 8):
  key=17 -> hash%4 = 1 -> shard 1         key=17 -> hash%8 = 5 -> shard 5  (MOVED)
  key=42 -> hash%4 = 2 -> shard 2         key=42 -> hash%8 = 2 -> shard 2  (stayed, coincidentally)

Naive hash % N sharding has a specific, severe resharding cost: changing N (the shard count) changes the target shard for almost every key, because the modulo result depends on N directly. Going from 4 shards to 8 doesn't just add capacity for new data — it requires re-routing and physically moving the overwhelming majority of existing data too.

2Consistent Hashing: Reducing Resharding's Blast Radius

Consistent hashing (the same technique covered for cache clusters in databases/caching/08-distributed_caching/) addresses exactly this problem: shards (or cache nodes) are placed at positions on a hash ring, and a key is assigned to the next shard clockwise from its own hash position. Adding or removing a shard only moves the keys that fall between the new shard's position and its nearest neighbor on the ring — not the entire keyspace.

Hash ring (simplified, 4 positions shown):

        shard A (pos 10)
    shard D              shard B
   (pos 250)            (pos 90)
        shard C (pos 170)

key hashes to pos 55 -> walks clockwise -> lands on shard B (next shard past 55)

Adding shard E at position 130:
  only keys between shard C (170) and shard E (130) -- i.e. keys that hashed
  into that specific arc -- move from shard C to shard E.
  Shards A, B, and D are completely unaffected.

This is why consistent hashing (or an equivalent range-map approach where the shard map is stored explicitly and updated incrementally rather than recomputed via modulo) is the standard technique in real sharded systems, rather than plain hash % N.

3Cross-Shard Queries and Joins

Sharding's most persistent ongoing cost isn't the one-time resharding event — it's every query that can't be answered by a single shard. Two forms show up constantly in a sharded relational schema:

• Scatter-gather reads (introduced in Part 1) — any query whose predicate doesn't include the shard key must fan out to all shards and merge results application-side, since no single shard's SQL engine can see the others' data.
• Cross-shard joins — a join between two tables sharded on different keys (or between a sharded table and data that landed on a different shard than the row you're joining against) cannot be executed as a single SQL JOIN at all, because a database engine can only join rows it can see, and each shard only sees its own slice. The application (or a routing/query-federation layer) must fetch from each side separately and join in application code — losing the query planner's join optimization entirely, and paying N network round trips instead of one.

-- Single-database join: one query, one engine, one query plan
SELECT o.id, o.total, c.name
FROM orders o JOIN customers c ON o.customer_id = c.id
WHERE c.region = 'eu';

-- Sharded equivalent (orders sharded by order_id, customers sharded by customer_id):
-- 1. query the customers shard(s) for region='eu' -> get a list of customer_ids
-- 2. for each customer_id, determine which orders shard(s) might hold their orders
-- 3. query those shard(s) for matching orders
-- 4. join the two result sets in application code

The standard mitigation is co-location: choosing shard keys so that data that's frequently joined together lands on the same shard (e.g. sharding both orders and order_items by the same customer_id-derived key, even though order_items's natural key might be order_id), turning what would be a cross-shard join into a same-shard join. This isn't always possible — a schema with many different join patterns across different keys cannot be co-located for all of them simultaneously, which is precisely why sharding is a last resort reached for after replication and vertical scaling stop being enough, not a default architecture.

4The Hot Shard ("Celebrity") Problem

Even a well-distributed shard key can produce a hot shard if the access pattern, not just the data volume, is uneven. The canonical example: a social platform shards posts by user_id, evenly distributing storage — but one user's account goes viral, and that single user's shard now absorbs a wildly disproportionate share of read traffic (everyone fetching that user's viral post), even though their data volume on that shard is unremarkable.

Storage distribution (even):        Read traffic distribution (uneven):
shard 1: [=====] 20%                shard 1: [==] 8%
shard 2: [=====] 20%                shard 2: [===================] 76%  <- celebrity's shard
shard 3: [=====] 20%                shard 3: [==] 8%
shard 4: [=====] 20%                shard 4: [==] 8%
shard 5: [=====] 20%                shard 5: [==] 8%

This is not fixable by resharding on the same key, since the key itself isn't the problem — the distribution of demand for one specific key's data is. Real mitigations: a caching layer in front of shards specifically to absorb read spikes for hot keys (see databases/caching/, especially 04-caching_strategies/), read replicas of just the hot shard, or, for write-side celebrity problems, splitting that one key's data further (e.g. sub-sharding one user's own data across multiple physical locations, which reintroduces cross-shard-style complexity for just that one key).

⚠️ Common Pitfalls

1. Using plain hash(key) % N sharding — resharding then moves almost every key, not just the new capacity's fair share; use consistent hashing or an explicit, incrementally-updatable shard map instead.
2. Sharding related tables on unrelated keys — turns routine joins into expensive cross-shard, application-level joins; co-locate data that's frequently joined together whenever the access pattern allows it.
3. Assuming even data volume means even load — the celebrity problem shows storage-balanced sharding can still produce read (or write) hotspots driven by demand, not data size.
4. Reaching for sharding before exhausting simpler options — vertical scaling (bigger server), read replicas (02-replication/), caching (databases/caching/), and query/index optimization (databases/indexing-storage/) are all cheaper to operate than a sharded cluster and should be the first line of response to scaling pressure.
5. Under-provisioning the routing/shard-map layer — if the component that knows "which shard has key X" is itself a single point of failure or a bottleneck, it can undermine the availability/throughput gains sharding was meant to provide.

📋 Quick Reference (Part 2)

Resharding: data physically moves between servers when shard count/boundaries change
  hash % N: changes target shard for almost every key when N changes -- avoid
  Consistent hashing: only keys in the affected ring arc move -- standard technique

Cross-shard cost: scatter-gather reads (predicate omits shard key) + cross-shard joins
  (a join can't span shards in one query -- app must fetch+join separately, no query planner help)
Co-location: shard related tables on the same key to turn cross-shard joins into same-shard joins

Hot/celebrity shard: even DATA distribution can still get uneven LOAD from one key's demand
  Fix: caching in front of shards, targeted read replicas, or sub-sharding the hot key specifically

Sharding is a last resort: try vertical scaling, replication, and caching first

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: dbscale_sharding_theory_1.md, dbscale_sharding_theory_2.md · generated by tools/build_lessons.py