SyntaxPilot
Courses/System Design/Lesson 12

System Design · Lesson 12 of 40 · 11 min

Sharding

queued

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#0 to Biryani 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

  1. Too big for one machine, and replicas don't make room → split it into shards with a shard key.
  2. Ranges of an always-increasing id → every new write on the last shard: a hot spot.
  3. A stable hash % N → an even spread (and never Python's hash()).
  4. A query without the shard key → scatter-gather across every shard. Choose the key from your most common queries.
  5. One viral key → a hot key → split it into sub-keys, or give it its own shard.
  6. 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

  1. Homework: in Demo 3, use 8 shards. Is the spread still even?
  2. Homework: in Demo 7, go from 10 shards to 11. How many users move? What about doubling, 4 → 8?
  3. Homework: in Demo 6, split Biryani Blues into 8 sub-keys. How busy is the busiest shard now? Try 64.
  4. Shard 1,000 users by city (4 cities) on 8 shards. What goes wrong?
  5. Fix Demo 2's shard_for so an id outside every range gives a clear error instead of a confusing TypeError.
  6. 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) % N spreads keys evenly ([2457, 2538, 2502, 2503]). Never use Python's hash(): 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?