Sharding & Partitioning

Table of Contents#

1. Recap: When Replication Alone Isn't Enough
2. What Sharding Actually Is
3. Choosing a Shard Key — The Single Most Important Decision
4. Range-Based Sharding
5. Hash-Based Sharding
6. Directory-Based (Lookup) Sharding
7. Comparing the Three Strategies
8. The Hot Shard Problem
9. The Resharding Nightmare
10. Consistent Hashing, Revisited for Databases
11. The Cross-Shard Query Problem
12. Cross-Shard Transactions — Genuinely Hard
13. Real-World Sharding Tools
14. When to Actually Reach for Sharding
15. Common Mistakes
16. Worked Practice Problems
17. Summary and What's Next

---

Recap: When Replication Alone Isn't Enough#

Part 1's replication techniques (including read replicas from the Capacity Planning & Performance series) scale read capacity beautifully — but every replica still holds a complete copy of the same data, and every single write still has to go through the one primary. When write volume itself becomes the bottleneck, or when the data simply becomes too large for any single machine to hold at all, replication alone can't help — this is exactly the problem sharding solves.

Diagram

---

What Sharding Actually Is#

Sharding (also called horizontal partitioning) means splitting one large dataset into smaller pieces (shards), each stored on a separate, independent database instance.

Diagram

Simple analogy: think of a massive physical library with millions of books, too many for one building. Instead of one impossibly large building, the library splits into several separate, smaller branches, each holding a specific subset of the collection (say, alphabetically by author's last name) — a librarian (the shard router) always knows exactly which branch to send you to, based on what you're looking for.

---

Choosing a Shard Key — The Single Most Important Decision#

The shard key is the field used to decide which shard a given row/document belongs to — and this single decision shapes almost everything else about how well the sharded system actually performs.

Diagram

A genuinely important, often-underestimated point worth stating explicitly: choosing the wrong shard key is one of the most expensive mistakes possible in database design, because — as covered later in this Part — changing it after the fact (resharding) is a genuinely difficult, high-risk operation. This decision deserves real, upfront thought, not a quick default choice.

---

Range-Based Sharding#

Data is split based on ranges of the shard key's value — e.g., all users with IDs 1-1,000,000 on Shard 1, IDs 1,000,001-2,000,000 on Shard 2, and so on.

Diagram

Strength: range queries (e.g., "give me all users created in January") can often be answered efficiently from a single shard, if the range aligns well with the query pattern.

Weakness, and a genuinely common, real problem: if the shard key correlates with time (like an auto-incrementing ID, or a timestamp), all new writes concentrate on whichever shard currently holds the newest range — e.g., every single new user signup lands on Shard 3 (the highest current range), while Shards 1 and 2 sit comparatively idle. This is a direct, textbook case of the "hot shard" problem, covered fully below.

---

Hash-Based Sharding#

Instead of ranges, run the shard key through a hash function, and use the hash result to decide the shard — directly reusing the hashing concept from the Reliability & Architecture Patterns series (Part 1).

Diagram

Strength: naturally spreads data (and therefore write load) evenly across shards, since a good hash function distributes values essentially randomly, regardless of any real-world skew in the underlying key values (e.g., regardless of whether user IDs are sequential or clustered).

Weakness: range queries become genuinely difficult — "give me all users created in January" now potentially requires querying every single shard, since consecutive user IDs are deliberately scattered randomly across all of them by the hash function, defeating any range-based locality.

---

Directory-Based (Lookup) Sharding#

A third approach: maintain an explicit, separate lookup table (a directory) mapping each specific shard key value to its shard — rather than computing the mapping algorithmically (via a range or a hash).

Diagram

Strength: maximum flexibility — you can move any individual key to any shard at any time, just by updating the lookup table, without any rigid mathematical formula constraining you (useful for deliberately rebalancing hot keys, or migrating specific high-value customers to dedicated, isolated shards).

Weakness: the lookup directory itself becomes a new, additional system that needs to be highly available and fast — every single query now requires an extra lookup step, and if the directory service itself goes down or becomes a bottleneck, it can affect access to every shard at once.

---

Comparing the Three Strategies#

---

The Hot Shard Problem#

Already previewed under range-based sharding — deserves its own full treatment since it's one of the most commonly asked "what can go wrong with sharding" interview questions.

Diagram

A real, concrete, frequently-cited example worth knowing: a "celebrity problem" — if a social media platform shards by user ID, and a specific user (a celebrity with millions of followers) generates dramatically more read/write activity than a typical user, that one user's specific shard can become massively hotter than every other shard, even though the sharding scheme is otherwise "even" by the numbers.

Mitigations worth naming: using a well-distributed hash-based key specifically to avoid correlation with real-world skew; monitoring per-shard load explicitly (an extension of the USE method from the Monitoring Methodologies series, applied per-shard); and, for genuinely extreme outlier cases, manually isolating a specific hot key onto its own dedicated shard (exactly what directory-based sharding's flexibility enables).

---

The Resharding Nightmare#

This is arguably the single most important, most feared operational reality of sharding, worth understanding deeply — and it's precisely why the shard-key decision matters so much upfront.

Diagram

This is exactly, precisely the same underlying problem the "plain hashing vs. consistent hashing" discussion from the Reliability & Architecture Patterns series (Part 1) already covered for caches — now applied to database shards, where the stakes (actual, durable data, not just cache entries) are dramatically higher.

---

Consistent Hashing, Revisited for Databases#

The exact same fix from that earlier tutorial applies here, worth restating in this specific, higher-stakes context.

Diagram

A strong, senior-level interview line, directly connecting these two tutorials: "The exact same consistent hashing technique I'd use for a distributed cache is even more important for database sharding, because the cost of getting it wrong is dramatically higher — a cache reshuffle just causes temporary cache misses hitting the origin harder; a naive database resharding scheme means physically moving terabytes of real, durable, load-bearing data between machines, live, which is a genuinely high-risk, all-hands operation if not designed correctly from the start."

---

The Cross-Shard Query Problem#

A query that needs data from multiple shards at once is fundamentally harder and slower than a query answerable from a single shard.

Diagram

Why this matters practically, and it's a genuinely important design consideration: a well-chosen shard key means the common, everyday queries an application actually needs hit only a single shard (fast, simple) — while rarer, cross-cutting queries (like company-wide analytics) accept the cost of fanning out to every shard and merging results, often handled by a completely separate analytics/reporting pipeline rather than the live, transactional sharded database at all.

---

Cross-Shard Transactions — Genuinely Hard#

The hardest problem in this entire tutorial, worth understanding at a conceptual level even without full implementation depth.

Diagram

Why this is genuinely hard, not just an implementation inconvenience: if the write to Shard A succeeds but the write to Shard B then fails, the system is left in a partially-completed, inconsistent state with no built-in way to automatically detect or fix it. Real solutions (two-phase commit protocols, or application-level "saga" patterns that explicitly define compensating actions to undo a partial failure) add real complexity and are a genuinely advanced topic — the practical, senior-level takeaway worth stating in an interview is simply: "I'd design the shard key specifically so that data needing strong transactional guarantees together always lands on the SAME shard, avoiding the cross-shard transaction problem entirely wherever possible, rather than trying to solve it after the fact."

---

Real-World Sharding Tools#

Worth knowing a few real names, since interviewers often ask "have you used any sharding tools/systems" to gauge hands-on exposure.

---

When to Actually Reach for Sharding#

A genuinely important, senior-level closing point — sharding should never be a default, reflexive choice.

Diagram

A strong, balanced interview line: "Sharding is a powerful but genuinely high-complexity, high-risk tool — I'd only reach for it after confirming, with real capacity planning data, that write volume or raw data size is the actual bottleneck, and after exhausting simpler options (vertical scaling, read replicas, caching) first. Sharding solves a real problem, but it introduces real new problems of its own — cross-shard queries, transactions, and the ever-present resharding risk — that shouldn't be taken on prematurely."

---

Common Mistakes#

---

Worked Practice Problems#

Problem 1: A team shards their orders table by order_id, using a simple auto-incrementing integer as the shard key with range-based sharding (Shard N holds the Nth range of IDs). They notice the newest shard is consistently at 95% capacity while older shards sit at 20%. What's happening, and how would you fix it?

Answer: Because order_id is auto-incrementing (and therefore directly correlates with time), every single new order — which is, by definition, all new writes — lands on whichever shard currently holds the highest ID range, creating a textbook hot shard while every other shard, holding only historical orders that are no longer being actively written to, sits comparatively idle. The fix is switching to a hash-based shard key (hashing order_id before assigning it to a shard, or choosing a genuinely well-distributed key entirely) so new writes spread evenly across all shards instead of concentrating entirely on the newest one.

Problem 2: A company needs to move from 6 shards to 12 as their data grows, currently using hash(key) % 6 for shard assignment. What will happen if they naively switch the formula to hash(key) % 12, and what should they have used from the start?

Answer: Changing the modulo from 6 to 12 changes the shard assignment for almost every single key in the system (since x % 6 and x % 12 agree only for a small fraction of possible hash values), requiring the physical movement of a massive fraction of the entire dataset between shards, live, while the system needs to keep running — a genuinely high-risk, all-hands operation. They should have used consistent hashing (a hash ring) from the start, which would have meant adding the 6 new shards only reassigns the small slice of keys nearest to each new shard's position on the ring, leaving the vast majority of existing data undisturbed.

Problem 3: An application needs to atomically transfer funds between two user accounts as part of a single business transaction, but the sharding scheme (hash-based on user ID) means the two accounts could easily end up on different shards. What's the fundamental problem, and what design change would you recommend?

Answer: A single shard's database can guarantee ACID atomicity for changes within itself, but has no native mechanism to guarantee atomicity across two completely independent, separate shard databases — if the debit succeeds on Shard A but the credit then fails on Shard B, the system is left in a partial, inconsistent state with no automatic way to detect or roll it back. The most practical fix is redesigning the shard key so that related accounts likely to need atomic joint transactions (e.g., all accounts belonging to the same organization or household) are deliberately co-located on the same shard — avoiding the cross-shard transaction problem by design, rather than attempting to solve the genuinely hard problem of distributed atomicity after the fact.

---

Summary and What's Next#

• Sharding splits data itself across multiple independent databases, solving the write-volume and data-size ceilings that replication alone (Part 1) can't address.
• The shard key choice is the single most important, highest-stakes decision in sharding — it determines data distribution, query efficiency, and how painful resharding will eventually be.
• Range-based sharding supports efficient range queries but risks severe hot shards on sequential/time-correlated keys; hash-based sharding distributes load evenly but makes range queries expensive; directory-based sharding offers maximum flexibility at the cost of an additional, critical lookup service.
• The hot shard problem (including the classic "celebrity" scenario) happens when real-world data skew concentrates load on one shard, even when the sharding scheme looks even "by the numbers."
• Resharding is one of the highest-risk operations in database engineering — exactly the same naive-hashing problem already covered for caches in the Reliability & Architecture Patterns series, but with dramatically higher stakes; consistent hashing is the standard, correct fix.
• Cross-shard queries and transactions are fundamentally harder than single-shard operations — the strongest practical strategy is designing the shard key so the vast majority of everyday operations, especially anything needing atomic transactional guarantees, stay within a single shard.
• Sharding should be a deliberate, last-resort scaling decision, reached only after confirming (via real capacity planning) that simpler options — vertical scaling, read replicas, caching — genuinely can't solve the actual bottleneck.

Continue to Part 3 (03-backup-recovery-and-durability.md) to cover the other essential half of database reliability — backup strategies, RPO/RTO, point-in-time recovery, and the durability guarantees underneath it all.