Chapter 08 — Sharding & Partitioning
Chapter 08 — Sharding & Partitioning
Hey everyone! Welcome back to Namaste System Design! 🙏
Replication (Chapter 07) copies the whole database — great for reads, but every copy still holds all the data and takes all the writes. When you have 500 million users and 50 terabytes of data, no single machine can hold it. The answer is to split the data across machines. That's sharding, and it's the deepest end of the data pool.
What we will cover:
- Partitioning vs sharding (the pizza analogy)
- How sharding scales writes AND storage
- Sharding strategies: range-based, hash-based, directory-based, consistent hashing
- The dreaded "hotspot" (celebrity) problem
- Why cross-shard queries hurt
- Resharding pain & a teaser for Deep Dive 01
- Interview Questions
1. The Pizza Analogy
One giant pizza, ten hungry friends. You can't clone the pizza (that's replication — same toppings everywhere). Instead you slice it, and each person holds a different slice. 🍕
┌─────────────────────────────────────────────────────────────┐ │ SHARDING = splitting ONE database into pieces (shards), │ │ where each shard holds a DIFFERENT subset of the data. │ │ │ │ Replication → same data copied many times (Ch 07) │ │ Sharding → different data split across machines │ └─────────────────────────────────────────────────────────────┘
BEFORE (one huge DB): AFTER (3 shards): ┌───────────────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ users 1–3,000,000 │ ──▶ │ users │ │ users │ │ users │ │ (50 TB) 🥵 │ │ 1–1M │ │ 1M–2M │ │ 2M–3M │ └───────────────────┘ └─────────┘ └─────────┘ └─────────┘ won't fit / too slow each holds ~17TB, fast 😌
(Note: "partitioning" is the general term for splitting; "sharding" usually means partitioning across separate machines. Interviews use them interchangeably.)
2. Why Shard? What It Uniquely Solves
✅ WRITE SCALING → each shard takes only its slice of writes.
(Replication couldn't do this — one leader.)
✅ STORAGE SCALING → data too big for one disk now spreads out.
✅ SMALLER INDEXES → each shard's index is smaller → faster queries.
⚠️ COST: complexity explodes. Sharding is a LAST resort, only
when replication + caching are no longer enough.
3. Sharding Strategies (How Do We Decide Which Shard?)
You pick a shard key (e.g. user_id) and a strategy to map it to a shard. Let's go through the four you'll be asked about.
3.1 Range-Based Sharding
Split the key space into contiguous ranges. Each range lives on one shard.
Shard by username's first letter: users A–H → Shard 1 users I–P → Shard 2 users Q–Z → Shard 3 "Aarav" → Shard 1 "Meera" → Shard 2 "Zoya" → Shard 3
✅ PROS Easy to reason about. Range queries ("give me
users M through Q") stay on one or two shards.
❌ CONS Real data isn't evenly spread — lots of names
cluster around certain letters → hotspot.
👉 USE IT WHEN Your data naturally has evenly-distributed
ranges, e.g. sharding time-series data by month.
3.2 Hash-Based Sharding
Run the shard key through a hash function, then mod by the number of shards.
shard = hash(user_id) % 3 user 1001 → hash → 7 → 7 % 3 = 1 → Shard 1 user 1002 → hash → 9 → 9 % 3 = 0 → Shard 0 user 1003 → hash → 8 → 8 % 3 = 2 → Shard 2
✅ PROS Spreads data very evenly — no natural clustering.
❌ CONS Range queries now hit EVERY shard (no ordering).
Adding a shard changes N, so almost every key
remaps → painful migration (more in section 6).
👉 USE IT WHEN You need even spread and don't need range
queries. The most common default.
3.3 Directory-Based Sharding
A separate lookup table explicitly records which shard holds which key.
LOOKUP TABLE (its own small database): ┌─────────┬─────────┐ │ user_id │ shard │ ├─────────┼─────────┤ │ 1001 │ Shard 2│ │ 1002 │ Shard 0│ │ 1003 │ Shard 1│ └─────────┴─────────┘ App asks the lookup table FIRST, then goes to that shard.
✅ PROS Full flexibility — move any key to any shard anytime,
rebalance without a formula-driven remap.
❌ CONS The lookup table itself is a new single point of
failure / bottleneck (though it can be small & cached).
👉 USE IT WHEN You need fine-grained control over placement,
e.g. keeping specific customers on dedicated shards.
3.4 Consistent Hashing
A smarter hash scheme that fixes hash-based sharding's biggest flaw: adding or removing a shard no longer remaps almost everything.
Shards AND keys placed on a logical ring (0 to 360°). Each key belongs to the next shard clockwise from it. user 1001 (at 40°) → next shard clockwise → Shard B user 1002 (at 210°) → next shard clockwise → Shard C Add Shard D at 250°? Only keys between the PREVIOUS shard and 250° move. Everyone else stays put.
✅ PROS Adding/removing a shard moves only ~1/N of the keys,
not nearly all of them.
❌ CONS More moving parts to implement than plain hashing.
👉 USE IT WHEN You expect to add/remove shards over time —
distributed caches, CDNs. Full ring walkthrough
lives in Deep Dive 01.
Visual Comparison
| Strategy | Even spread? | Range queries? | Easy resharding? | Example key |
|---|---|---|---|---|
| Range-Based | ❌ | ✅ | ✅ | username A–H |
| Hash-Based | ✅ | ❌ | ❌ | hash(user_id) % N |
| Directory-Based | ✅ (manual) | Depends | ✅ | lookup table row |
| Consistent Hashing | ✅ | ❌ | ✅ | hash on a ring |
4. The Hotspot Problem
The nightmare of sharding: one shard gets way more traffic than the others, defeating the whole purpose.
Shard by COUNTRY:
┌──────────┐ ┌──────────┐ ┌──────────┐
│ India │ │ Bhutan │ │ Nauru │
│ 400M 🔥🔥 │ │ 50k │ │ 30 │
└──────────┘ └──────────┘ └──────────┘
overloaded idle idle
Bad shard key → uneven load → one shard melts while
others nap. Choose a HIGH-CARDINALITY, evenly-distributed
key (like a hashed user_id), not "country".
Same issue with a celebrity: if you shard tweets by author, Cristiano Ronaldo's shard gets hammered — hundreds of millions of followers all reading (and replying to) his posts land on one machine. Real systems special-case such "hot" keys — e.g. giving a celebrity's data extra replicas of its own, or splitting their data further by a secondary key.
5. The Pain: Cross-Shard Queries
Once data is split, operations that need many shards get expensive.
"Get user 1042's profile" → one shard → fast ✅ "Count ALL users who joined today" → must ask EVERY shard and merge results → slow, complex (a scatter-gather) ❌ JOINs across shards? Even worse — often you can't, so you DENORMALIZE (duplicate data) to keep queries on one shard.
Design lesson: choose your shard key so that your most common query hits a single shard. This is the whole game.
6. Resharding Pain
With plain hash(key) % N, adding a shard changes N — so almost every key now maps to a different shard, forcing a massive, painful data migration.
Was: hash % 3 Now: hash % 4 → nearly EVERY key moves to a new shard. Migration hell. 😭
Section 3.4's consistent hashing solves this elegantly — adding a shard moves only a small fraction of keys, not all of them. It's so important it gets its own Deep Dive 01.
Interview Questions — Quick Fire!
Q: What is sharding and how is it different from replication?
"Sharding splits a database into pieces called shards, where each shard holds a different subset of the data across separate machines. Replication keeps full copies of the same data. Replication scales reads and improves availability, but every copy still holds all the data and takes all the writes. Sharding is what scales writes and total storage, because each shard handles only its slice."
Q: What are common sharding strategies?
"Range-based splits by key ranges, like username A-H, which is simple and keeps range queries efficient but risks uneven distribution. Hash-based applies a hash function to the shard key to spread data evenly, but loses range-query ability and makes adding shards harder. Directory-based uses a lookup table mapping keys to shards, which is very flexible but adds a lookup layer that can become a bottleneck. Consistent hashing is a refinement of hash-based sharding that makes adding or removing shards cheap. Hash-based and consistent hashing are the most common in practice."
Q: What is a hotspot in sharding and how do you avoid it?
"A hotspot is when one shard receives disproportionately more traffic or data than others, so it becomes overloaded while others sit idle — which defeats the point of sharding. It usually comes from a poorly chosen shard key, like sharding by country, or from a single 'celebrity' key that gets far more activity than any other. You avoid it by choosing a high-cardinality, evenly distributed key such as a hashed user ID, and special-casing known hot keys."
Q: Why are cross-shard queries a problem?
"Because a query that needs data from many shards has to fan out to all of them and merge the results — a scatter-gather that's slow and complex — and joins across shards are often impractical. The mitigation is to pick a shard key so the most common queries hit a single shard, and to denormalize data when needed so related data lives together."
Q: Why is resharding painful, and how does consistent hashing help?
"With plain hash(key) % N sharding, adding or removing a shard changes N, which changes almost every key's mapping — forcing a huge, disruptive data migration. Consistent hashing places shards and keys on a logical ring so each key maps to the next shard clockwise from it. Adding a shard then only moves the keys between the new shard and its neighbour, roughly one over N of all keys, instead of nearly all of them."
Key Points to Remember
| Concept | Key Takeaway |
|---|---|
| Sharding | Split data across machines; each shard holds a different subset. |
| Uniquely solves | Scales WRITES and STORAGE (replication can't). A last resort — high complexity. |
| Strategies | Range-based (simple, uneven) · hash-based (even, no ranges) · directory-based (flexible) · consistent hashing (even + cheap resharding). |
| Hotspots | Bad keys overload one shard. Avoid "country"; watch for celebrity keys. |
| Resharding | hash % N makes adding shards painful → consistent hashing (Deep Dive 01). |
What's Next?
We've been dancing around a fundamental tension: when data is spread across machines, can it be both perfectly consistent AND always available? Chapter 09 confronts the most famous theorem in distributed systems — the CAP theorem.
Keep designing, keep scaling! See you in the next one!
Post a Comment