These are the notes for System Design episode 12. Last episode, replicas gave ChaiNow copies of its database, so one dead disk can't take it down. Today ChaiNow grows so big that the data doesn't fit on one machine at all, and copies can't fix that. You'll invent the fix: sharding, which means splitting the data across many machines. We pick a shard key, try the obvious split by ranges and get a hot spot, fix it with hash sharding, fall into the trap of Python's built-in hash(), count the cost of scatter-gather queries, watch one viral restaurant become a hot key, and finally add one more shard and see 80% of the data move. Every demo is plain Python with only the standard library (hashlib), and every output below is real (Python 3.13). The order volumes in Demo 1 are an illustrative ChaiNow scenario, not any real company's numbers.
The six problems
| Problem | What it teaches |
|---|---|
| Too big for one machine | Sharding, the shard key |
| One shard does all the work | Range sharding, hot spots |
| Spread it evenly | Hash sharding (and a stable hash) |
| Which shard has it? | Scatter-gather, choosing a shard key |
| One viral restaurant | The hot key, and splitting it |
| Add one more shard | With % N, 80% of the data moves |
Problem 1: too big for one machine
ChaiNow is now in 100 cities, with 1 crore (10 million) orders a day. Every order, its items and its index entries take a few kilobytes. That adds up to terabytes (TB, a million million bytes) a year, and a big database disk is only a few TB.
What about replicas (full copies of the database, from episode 11)? They don't help here. Each replica holds all the data, so each one is just as full. And every write still goes to one primary, the one copy that accepts writes.
Demo 1: the maths
This is an illustrative scenario: the numbers are chosen to be realistic for a food-delivery app of this size, not taken from any real company.
orders_per_day = 1_00_00_000 # 1 crore orders a day
bytes_per_order = 4_000 # order + items + indexes
disk_tb = 4 # one big database disk
per_year_tb = orders_per_day * bytes_per_order * 365 / 1e12
print(f"data per year: {per_year_tb:.2f} TB")
print(f"one {disk_tb} TB disk is full in {disk_tb / per_year_tb * 12:.0f} months")
writes_per_sec = orders_per_day * 10 / 86_400 # each order = ~10 writes
print(f"average writes/s: {writes_per_sec:,.0f} (lunch peak: 5x)")
Output:
data per year: 14.60 TB
one 4 TB disk is full in 3 months
average writes/s: 1,157 (lunch peak: 5x)
(Python lets you put _ anywhere between digits, so 1_00_00_000 is written the Indian way: 1 crore.)
14.6 TB a year. The disk is full in 3 months. And over a thousand writes every second on average, five times that at lunch, all on one primary. A bigger machine buys a few months: that's vertical scaling (making one machine bigger, episode 5), and it has a ceiling. We need many machines that each hold only part of the data and take only part of the writes.
Real-life example: the exam hall
| In an exam hall | In a database |
|---|---|
| 3,000 students can't fit in 1 room | One database can't hold all the data |
| 10 rooms, each holds some students | Shards: separate databases, each holding part of the data |
| Your roll number decides your room: 1-300 → room 1, 301-600 → room 2 | Shard key: a field that decides the shard, using one rule everyone agrees on |
Splitting data this way is sharding. The MongoDB 5.0 manual defines it as "a method for distributing data across multiple machines", and explains the key: "MongoDB uses the shard key to distribute the collection's documents across shards. The shard key consists of a field or multiple fields in the documents." Another name for the same idea is horizontal partitioning: the rows of one table are split into groups, and each group lives on a different machine.
Problem 2: one shard does all the work (range sharding)
The exam-hall rule in code: four shards, each owning a range of user ids. This is range sharding. The MongoDB manual describes ranged sharding as one that "divides data into ranges based on the shard key values".
Demo 2: range sharding and the hot spot
# Range sharding: each shard owns a range of user ids
RANGES = [(1, 250_000), (250_001, 500_000),
(500_001, 750_000), (750_001, 1_000_000)]
def shard_for(user_id):
for i, (lo, hi) in enumerate(RANGES):
if lo <= user_id <= hi:
return i
print("user 42 -> shard", shard_for(42))
print("user 600000 -> shard", shard_for(600_000))
writes = [0, 0, 0, 0]
for user_id in range(990_001, 1_000_001): # today's 10,000 new sign-ups
writes[shard_for(user_id)] += 1
print("new sign-up writes per shard:", writes)
Output:
user 42 -> shard 0
user 600000 -> shard 2
new sign-up writes per shard: [0, 0, 0, 10000]
Lookups work: user 42 is on shard 0, user 6 lakh on shard 2. But new users always get the newest ids, so today's 10,000 sign-ups all land on the last shard. Three shards sit idle while one does all the work. An overloaded shard like this is a hot spot.
The MongoDB manual warns: "Poorly considered shard keys can result in uneven distribution of data". The classic mistake is a monotonic key: one that only ever goes up, like an auto-increment id, a timestamp or a date. With ranges, every new row goes to the end.
Look closely at shard_for too: if no range matches, the loop ends and the function silently returns None. User 1,000,001 will crash it (see Common mistakes).
Problem 3: spread it evenly (hash sharding)
Real-life example: dealing cards
| Dealing cards | Hash sharding |
|---|---|
| Deal by position, not by value | Hash the key: turn it into a big scrambled number, so neighbours get separated |
| Around the table, 1-2-3-4: everyone gets a fair share | % number of shards: the remainder (0 to 3) picks the shard |
| Same rule every time | Deterministic: the same key always gives the same shard, so you can find it again |
A hash function takes any input and turns it into a fixed-size number that looks random. Tiny changes in the input (990,001 vs 990,002) give completely different numbers. MD5 is one such function, available in Python's hashlib module (the standard-library module for stable hash functions). Modulo (%) gives the remainder after division: 13 % 4 is 1.
Demo 3: hash sharding with MD5
import hashlib
def shard_for(user_id, n_shards=4):
h = hashlib.md5(str(user_id).encode()).hexdigest()
return int(h, 16) % n_shards # same id -> same shard, always
print("user 42 -> shard", shard_for(42))
print("user 600000 -> shard", shard_for(600_000))
writes = [0, 0, 0, 0]
for user_id in range(990_001, 1_000_001): # the same 10,000 sign-ups
writes[shard_for(user_id)] += 1
print("new sign-up writes per shard:", writes)
Output:
user 42 -> shard 2
user 600000 -> shard 2
new sign-up writes per shard: [2457, 2538, 2502, 2503]
Step by step: str(user_id).encode() turns the id into bytes (MD5 works on bytes), .hexdigest() gives the hash as 32 hexadecimal characters, int(h, 16) reads that as a (very big) number, and % n_shards picks the shard.
About 2,500 on every shard: the hot spot is gone. This is hash sharding. The MongoDB manual says hashed sharding "computes a hash of the shard key field's value" and gives "more even data distribution, especially for shard keys that change monotonically", which is exactly our always-increasing ids.
Demo 4: the trap, Python's built-in hash()
Why MD5, and not Python's built-in hash()? Run this one line twice.
print(hash("asha")) # Python's built-in hash of a string
Output, run 1:
7558807255284962967
Output, run 2:
-8427205455786588780
A different number every run (it can even be negative). Python randomises string hashes each time a program starts, on purpose, as a security measure. Inside one running program hash("asha") is consistent, which is all a Python dict needs. But your servers are many programs, restarted at different times. If they used hash(), a restart would send Asha to a different shard, and her data would seem to vanish.
For sharding, use a stable hash: one that gives the same answer on every machine, every day, like MD5 from hashlib or another fixed function.
Problem 4: which shard has it? (scatter-gather)
Our orders are sharded by user id. The router (the piece of code or service that decides which shard a request goes to) can send Asha's query to exactly one shard. But the Pune manager wants all orders from Pune, and the query has no user id. So the router asks every shard, waits for all of them, and merges the answers. This is scatter-gather: scatter the query to all shards, gather the results. It's also called a broadcast query.
Demo 5: one shard vs all of them
import hashlib
def shard_for(key, n=4):
return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % n
# orders sharded by user_id: each shard holds some users' orders
shards = [[] for _ in range(4)]
cities = ["Pune", "Delhi", "Chennai", "Kolkata"]
for user_id in range(1, 1001):
order = {"user": user_id, "city": cities[user_id % 4]}
shards[shard_for(user_id)].append(order)
def query(where, shard_ids):
hits = [o for s in shard_ids for o in shards[s] if where(o)]
print(f"asked {len(shard_ids)} shard(s), found {len(hits)} orders")
query(lambda o: o["user"] == 42, [shard_for(42)]) # has the shard key
query(lambda o: o["city"] == "Pune", range(4)) # no shard key
Output:
asked 1 shard(s), found 1 orders
asked 4 shard(s), found 250 orders
One shard for user 42, four shards for Pune. With 4 shards that's fine. With 400 shards, every Pune query hits 400 machines, and the answer is only as fast as the slowest one. The MongoDB manual names this cost of hashing: "range-based queries on the shard key are less likely to target a single shard, resulting in more cluster-wide broadcast operations". Hashing scatters neighbouring keys on purpose, so "ids 1000 to 2000" is also spread across every shard.
Choosing a shard key
| A good shard key... | Example |
|---|---|
| Is in your most common queries | user_id for "my orders": most queries touch one shard |
| Has many different values | not city: only 100 cities, so at most 100 useful shards, and Mumbai's shard is huge |
| Spreads writes evenly | hash it if it only goes up (ids, timestamps) |
| Never changes | changing it means moving the row to another machine |
Start from your queries, not from your tables. Rare queries, like the Pune report, can live with scatter-gather, or read from a separate copy of the data built for reports. Practice 4 shows what a key with too few values does.
Problem 5: one viral restaurant (the hot key)
A different team shards orders by restaurant, so a restaurant's menu and orders live together. Seems natural. Then one restaurant goes viral: Biryani Blues gets half of all orders in the city. Hashing spreads different keys, but every Biryani Blues order has the same key, so every one goes to the same shard.
Demo 6: 64% on one shard
import hashlib
def shard_for(key, n):
return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % n
# 1 lakh orders, sharded by restaurant. One restaurant goes viral.
load = [0, 0, 0, 0]
for i in range(100_000):
restaurant = "Biryani Blues" if i % 2 == 0 else f"shop{i % 500}"
load[shard_for(restaurant, 4)] += 1
print("orders per shard:", load)
print("busiest shard has", round(max(load) / sum(load) * 100), "% of all orders")
Output:
orders per shard: [12200, 13400, 64200, 10200]
busiest shard has 64 % of all orders
One shard has 64,200 orders, the others 10 to 13 thousand. This is a hot key: one key with far more traffic than all the rest. No hash function can fix it, because a hash sends one key to one place.
The usual fixes:
- Split the key (sub-keys): store Biryani Blues orders under
Biryani Blues#0toBiryani Blues#7, so they land on different shards, and read all eight parts when you need the whole picture. Practice 3 measures this. - Give the celebrity its own shard, so its traffic can't hurt anyone else.
Problem 6: add one more shard (the resharding trap)
Months later, four shards are full again. Easy: add a fifth machine and change the rule from % 4 to % 5. But hash % 5 is a different remainder from hash % 4 for most keys. It's like an exam hall adding one room and giving almost every student a new room number. Every key whose shard changed must be copied to its new machine, while the app is running. This is resharding (changing the number of shards) and the copying is rebalancing.
Demo 7: 80% must move
import hashlib
def shard_for(key, n):
return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % n
users = range(1, 100_001) # 1 lakh users
moved = sum(1 for u in users if shard_for(u, 4) != shard_for(u, 5))
print(f"4 -> 5 shards: {moved:,} of 100,000 users must move "
f"({moved / 1000:.0f}%)")
Output:
4 -> 5 shards: 80,010 of 100,000 users must move (80%)
We added one shard to take a fifth of the load, and had to move four fifths of the data. A key stays put only when hash % 4 and hash % 5 happen to agree, which is about 1 time in 5. The Apache Cassandra docs (the "Dynamo" architecture page) say it directly: with naive modulo hashing, "adding a single node might invalidate almost all of the mappings". The fix is the next episode.
The whole chain
- Too big for one machine, and replicas don't make room → split it into shards with a shard key.
- Ranges of an always-increasing id → every new write on the last shard: a hot spot.
- A stable hash
% N→ an even spread (and never Python'shash()). - A query without the shard key → scatter-gather across every shard. Choose the key from your most common queries.
- One viral key → a hot key → split it into sub-keys, or give it its own shard.
- Change N → 80% of the data moves → we need a better scheme: consistent hashing.
Common mistakes (and the real errors)
| Mistake | Code | Error / output | Fix |
|---|---|---|---|
Python's hash() as the shard hash |
shard = hash(user_name) % 4 |
run 1: 7558807255284962967, run 2: -8427205455786588780 |
Use a stable hash: hashlib.md5 |
| Ranges on an increasing id or timestamp | shard by created_at / auto-increment id |
writes per shard: [0, 0, 0, 10000] |
Hash the key, or add a spread-out prefix |
% N, then changing N |
md5(key) % N, N = 4 → 5 |
80,010 of 100,000 users must move (80%) |
Consistent hashing (next episode) |
| An id outside every range | writes[shard_for(1_000_001)] += 1 |
TypeError: list indices must be integers or slices, not NoneType |
Raise a clear error, or add an open-ended last range (Practice 5) |
Hashing a str without encoding |
hashlib.md5("asha") |
TypeError: Strings must be encoded before hashing |
hashlib.md5("asha".encode()) |
Hashing an int directly |
hashlib.md5(42) |
TypeError: object supporting the buffer API required |
hashlib.md5(str(42).encode()) |
| Forgetting base 16 | int(h) % 4 on a hex digest |
ValueError: invalid literal for int() with base 10: 'a2d5dc83dddc9580d68221d6604a759f' |
int(h, 16) |
| Zero shards | shard_for("asha", len(shards)) with shards = [] |
ZeroDivisionError: integer modulo by zero |
Create the shards before routing to them |
| A key with too few values | shard by city (4 cities) on 8 shards |
users per shard: [500, 0, 250, 0, 0, 0, 250, 0] |
Pick a key with many values (Practice 4) |
The range-sharding crash in full. Sign-up number 1,000,001 matches no range, so shard_for falls off the end and returns None:
RANGES = [(1, 250_000), (250_001, 500_000),
(500_001, 750_000), (750_001, 1_000_000)]
def shard_for(user_id):
for i, (lo, hi) in enumerate(RANGES):
if lo <= user_id <= hi:
return i
writes = [0, 0, 0, 0]
writes[shard_for(1_000_001)] += 1 # sign-up number 1,000,001
Output:
Traceback (most recent call last):
File "main.py", line 10, in <module>
writes[shard_for(1_000_001)] += 1 # sign-up number 1,000,001
~~~~~~^^^^^^^^^^^^^^^^^^^^^^
TypeError: list indices must be integers or slices, not NoneType
The first hashlib mistake in full (the others in the table look the same, with the message shown):
import hashlib
print(hashlib.md5("asha").hexdigest())
Output:
Traceback (most recent call last):
File "main.py", line 2, in <module>
print(hashlib.md5("asha").hexdigest())
~~~~~~~~~~~^^^^^^^^
TypeError: Strings must be encoded before hashing
Misconceptions
- "Sharding and replication are the same thing." Replication copies all the data to several machines (safety, more reads). Sharding splits the data so each machine holds a different part (more storage, more writes). Real systems often do both: every shard has its own replicas.
- "Sharding and partitioning are different things." Sharding is partitioning (splitting a table into pieces) where the pieces live on different machines. Horizontal partitioning splits by rows; that's the kind sharding uses.
- "Sharding is free scaling." It costs: queries without the shard key become scatter-gather, a cross-shard join or cross-shard transaction (one that touches rows on several shards) is slow and hard, hot keys still melt one shard, and resharding moves data. Shard when one machine truly can't cope.
- "A hash fixes every imbalance." A hash spreads different keys. One very popular key still goes to one shard.
- "Adding a shard moves only the new shard's share." Not with
hash % N: going from 4 to 5 shards moved 80%.
Mini project: a tiny sharded key-value store
A key-value store keeps values under keys, like a Python dict. Ours has 4 shards (plain dicts), a router that hashes the key with MD5, a get that asks one shard, a find that does scatter-gather, and a hot "likes" counter split into 8 sub-keys.
# A tiny sharded key-value store: 4 shards (plain dicts), a router that
# hashes the key with MD5, a scatter-gather query, and a hot key split
# into sub-keys.
import hashlib
def stable_hash(key):
return int(hashlib.md5(str(key).encode()).hexdigest(), 16)
class ShardedStore:
def __init__(self, n_shards):
self.shards = [{} for _ in range(n_shards)]
self.asked = 0 # how many shard visits so far
def shard_for(self, key): # the router
return stable_hash(key) % len(self.shards)
def put(self, key, value):
self.shards[self.shard_for(key)][key] = value
def get(self, key): # has the key: ask ONE shard
self.asked += 1
return self.shards[self.shard_for(key)].get(key)
def find(self, where): # no key: ask EVERY shard
hits = []
for shard in self.shards:
self.asked += 1
hits += [v for v in shard.values() if where(v)]
return hits
def sizes(self):
return [len(s) for s in self.shards]
store = ShardedStore(4)
cities = ["Pune", "Delhi", "Chennai", "Kolkata"]
for n in range(1, 2001): # 2,000 orders
store.put(f"order:{n}", {"id": n, "city": cities[n % 4], "amount": n % 300})
print("orders per shard:", store.sizes())
store.asked = 0
print("get order:42 ->", store.get("order:42"), "| shards asked:", store.asked)
store.asked = 0
pune = store.find(lambda o: o["city"] == "Pune")
print("Pune orders:", len(pune), "| shards asked:", store.asked)
# Hot key: one counter for Biryani Blues gets every 'like'.
# Split it into 8 sub-keys; each like goes to one sub-key in turn.
SPLIT = 8
for like in range(10_000):
key = f"likes:Biryani Blues#{like % SPLIT}"
store.put(key, (store.get(key) or 0) + 1)
parts = [f"likes:Biryani Blues#{s}" for s in range(SPLIT)]
print("sub-key shards:", [store.shard_for(k) for k in parts])
per_shard = [0] * 4
for k in parts:
per_shard[store.shard_for(k)] += store.get(k)
print("like writes per shard:", per_shard)
print("total likes:", sum(store.get(k) for k in parts))
Output:
orders per shard: [514, 513, 480, 493]
get order:42 -> {'id': 42, 'city': 'Chennai', 'amount': 42} | shards asked: 1
Pune orders: 500 | shards asked: 4
sub-key shards: [3, 3, 2, 1, 2, 2, 1, 2]
like writes per shard: [0, 2500, 5000, 2500]
total likes: 10000
The orders spread evenly, a lookup by key asks one shard, and the Pune search asks all four. The hot counter's 10,000 writes now go to three shards instead of one, and reading the total means reading all 8 sub-keys. Notice shard 0 got none and shard 2 got half: with only 8 sub-keys, the hash can still lump them together. Try SPLIT = 64, or add a delete method and a second hot key.
Practice
- Homework: in Demo 3, use 8 shards. Is the spread still even?
- Homework: in Demo 7, go from 10 shards to 11. How many users move? What about doubling, 4 → 8?
- Homework: in Demo 6, split Biryani Blues into 8 sub-keys. How busy is the busiest shard now? Try 64.
- Shard 1,000 users by
city(4 cities) on 8 shards. What goes wrong? - Fix Demo 2's
shard_forso an id outside every range gives a clear error instead of a confusingTypeError. - Homework (comment): what shard key would you choose for a chat app's messages, like WhatsApp?
Solutions and hints
1. Still even: about 1,250 each.
import hashlib
def shard_for(user_id, n_shards=8):
h = hashlib.md5(str(user_id).encode()).hexdigest()
return int(h, 16) % n_shards
writes = [0] * 8
for user_id in range(990_001, 1_000_001): # the same 10,000 sign-ups
writes[shard_for(user_id)] += 1
print("new sign-up writes per shard:", writes)
print("ideal per shard:", 10_000 // 8)
Output:
new sign-up writes per shard: [1222, 1260, 1234, 1254, 1235, 1278, 1268, 1249]
ideal per shard: 1250
2. 10 → 11 moves 91%: the more shards you have, the worse % N gets (a key stays only when both remainders agree, about 1 time in 11). Doubling is the kindest case, and it still moves half.
import hashlib
def shard_for(key, n):
return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % n
users = range(1, 100_001) # 1 lakh users
for old, new in [(10, 11), (4, 8)]:
moved = sum(1 for u in users if shard_for(u, old) != shard_for(u, new))
print(f"{old} -> {new} shards: {moved:,} of 100,000 users must move "
f"({moved / 1000:.0f}%)")
Output:
10 -> 11 shards: 90,946 of 100,000 users must move (91%)
4 -> 8 shards: 49,906 of 100,000 users must move (50%)
3. 64% drops to 52% with 8 sub-keys (Biryani Blues#0 to #7). Better, but not even: with only 8 sub-keys, 4 of them happened to hash to shard 2 and none to shard 3. More sub-keys spread better (31% with 64), at the cost of reading more parts when you need the whole restaurant.
import hashlib
def shard_for(key, n):
return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % n
for split in [1, 8, 64]:
load = [0, 0, 0, 0]
for i in range(100_000):
if i % 2 == 0:
key = f"Biryani Blues#{i % split}"
else:
key = f"shop{i % 500}"
load[shard_for(key, 4)] += 1
print(f"{split:>2} sub-keys: {load} busiest = "
f"{round(max(load) / sum(load) * 100)}%")
Output:
1 sub-keys: [12200, 13400, 64200, 10200] busiest = 64%
8 sub-keys: [12200, 25900, 51700, 10200] busiest = 52%
64 sub-keys: [20012, 30587, 31390, 18011] busiest = 31%
4. Only 4 different keys exist, so at most 4 shards can ever get data. Here two cities even hashed to the same shard, and 5 of the 8 shards are empty.
import hashlib
def shard_for(key, n):
return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % n
load = [0] * 8 # 8 shards, sharded by city
cities = ["Pune", "Delhi", "Chennai", "Kolkata"]
for user_id in range(1, 1001):
load[shard_for(cities[user_id % 4], 8)] += 1
print("users per shard:", load)
Output:
users per shard: [500, 0, 250, 0, 0, 0, 250, 0]
5. Raise an error that says what happened (or make the last range open-ended, (750_001, float("inf")), which brings back the hot spot).
RANGES = [(1, 250_000), (250_001, 500_000),
(500_001, 750_000), (750_001, 1_000_000)]
def shard_for(user_id):
for i, (lo, hi) in enumerate(RANGES):
if lo <= user_id <= hi:
return i
raise ValueError(f"no shard owns user id {user_id}")
print(shard_for(999_999))
print(shard_for(1_000_001))
Output:
3
Traceback (most recent call last):
File "main.py", line 11, in <module>
print(shard_for(1_000_001))
~~~~~~~~~^^^^^^^^^^^
File "main.py", line 8, in shard_for
raise ValueError(f"no shard owns user id {user_id}")
ValueError: no shard owns user id 1000001
6. There's no single right answer; reason from the queries. The most common query is "show the latest messages in this chat", so a chat (conversation) id, hashed, keeps each chat's messages on one shard. Sharding by sender would scatter one chat across many shards; sharding by time would make a hot spot. Watch out for hot keys: one giant group chat. This is a thinking exercise, not a description of how any real app is built.
Quick quiz
# orders sharded by hash(user_id), 8 shards
SELECT * FROM orders
WHERE restaurant_id = 77
AND created_at > '2026-10-01';
# how many shards are asked?
- A. 1
- B. 2
- C. 8
- D. 0, it's an error
Answer
C, all 8. The query has no user_id, the shard key, so the router can't tell where the rows are: scatter-gather.
Interview questions
- What is sharding? How is it different from replication, and from vertical scaling?
- What is a shard key? What makes a good one? (In common queries, many values, spreads writes, never changes.)
- Compare range sharding and hash sharding. When does each work well, and what does each cost?
- Why does sharding by an auto-increment id or a timestamp with ranges create a hot spot? How do you fix it?
- Why must a shard hash be stable? Why is Python's
hash()of a string a bad choice? - What is a scatter-gather query? How do you avoid it for common queries? (Choose the shard key from them; keep a separate copy for reports.)
- What is a hot key? Give two ways to handle one, and the trade-off of splitting it.
- With
hash % N, roughly what fraction of keys move when N goes from 4 to 5? From 10 to 11? (About 80%; about 91%.) What's the alternative? (Consistent hashing.) - When should you not shard yet?
Glossary
| Term | Meaning |
|---|---|
| Shard | One separate database that holds part of the data |
| Sharding | Splitting data across several machines, each holding a different part |
| Shard key | The field (or fields) whose value decides which shard a row goes to |
| Partitioning | Splitting a table into pieces |
| Horizontal partitioning | Splitting a table by rows: each piece holds some of the rows (what sharding does) |
| Replica / replication | A full copy of the database / keeping such copies (episode 11) |
| Primary | The copy that accepts writes |
| Vertical scaling | Making one machine bigger (episode 5); it has a ceiling |
| TB (terabyte) | 10¹² bytes, a million million |
| Lakh / crore | Indian numbers: 1 lakh = 1,00,000 (100 thousand); 1 crore = 1,00,00,000 (10 million) |
| Writes per second | How many inserts and updates the database must handle each second |
| Range sharding | Each shard owns a range of key values (1 to 2,50,000, ...) |
| Hot spot | One shard getting far more work than the others |
| Monotonic key | A key that only ever increases: auto-increment ids, timestamps, dates |
| Hash function / hash | A function that turns any input into a fixed-size, random-looking number / that number |
| MD5 | A well-known hash function giving a 128-bit value (32 hex characters); here used only to spread keys, not for security |
hashlib |
Python's standard-library module of stable hash functions (md5, sha256, ...) |
.encode() / hexdigest() / int(h, 16) |
String to bytes / the hash as hex (base 16) digits / hex text to a number |
Modulo (%) |
The remainder after division: 13 % 4 is 1; % N picks one of N shards |
| Deterministic | Always gives the same output for the same input |
| Stable hash | A hash that is the same on every machine and after every restart |
hash() |
Python's built-in hash; for strings it's randomised per process, so not stable |
| Hash sharding | Shard = stable hash of the key % N; spreads keys evenly |
| Router | The code or service that decides which shard a request goes to |
| Scatter-gather | Send a query to every shard, then merge the answers |
| Broadcast query | A query sent to all shards (MongoDB's term: "cluster-wide broadcast operations") |
| Hot key | One key with far more traffic than all others; a hash sends it all to one shard |
| Sub-key / key splitting | Storing one hot key as several keys (Biryani Blues#0 ... #7) so they land on different shards |
| Resharding | Changing the number of shards (or the rule that maps keys to them) |
| Rebalancing | Moving data between shards so each holds its new share |
| Cross-shard join / transaction | A query or an all-or-nothing change that touches rows on more than one shard; slow and hard |
| Key-value store | A database that stores values under keys, like a Python dict |
| Consistent hashing | The next episode: a scheme where adding a shard moves only a small share of keys |
TypeError / ValueError / ZeroDivisionError |
Python errors for a wrong type / a bad value / dividing (or %) by zero |
| Traceback | Python's report of where an error happened, last call at the bottom |
Summary
- When data outgrows one machine, replicas don't help (each holds everything). Sharding splits the data across machines, using a shard key.
- Range sharding on an always-increasing key puts every new write on the last shard: a hot spot (
[0, 0, 0, 10000]). - Hash sharding with a stable hash (
hashlib.md5)% Nspreads keys evenly ([2457, 2538, 2502, 2503]). Never use Python'shash(): it changes every run. - A query without the shard key must ask every shard: scatter-gather. Choose the shard key from your most common queries, with many values, an even spread, and no changes.
- One viral key is a hot key (64% on one shard). Split it into sub-keys, or give it its own shard.
- With
hash % N, adding one shard moved 80% of the data (10 → 11 moved 91%).
Next episode: Consistent hashing. Adding one shard moved 80% of our data. What if adding a shard moved only the data the new shard needs?