Partitioning and sharding: splitting data across machines

“We’re resharding next month”

What are partitioning and sharding?

Words you’ll meet in this lesson

Partitioning across the big data stack

Partitioning at three levels

Range, hash, directory and composite partitioning

Side by side

Choosing a partition key

Sharding an orders table

1. Pick the partition key

   TiffinGo’s app mostly asks “show this user’s orders” and “place an order for this user”. So the orders table is partitioned by user_id.

   The key decides everything else: balance, which queries are fast, and which queries must visit every shard.

2. Hash partitioning spreads users evenly

   import hashlib
   def shard_for(user, n=4):
       return int(hashlib.md5(user.encode()).hexdigest(), 16) % n
   for u in ["U9", "U42", "U777", "U1001"]:
       print(u, "-> shard", shard_for(u))

   U9 -> shard 1 U42 -> shard 0 U777 -> shard 2 U1001 -> shard 2
   A stable hash (here MD5; never Python’s hash(), which changes between runs) turns each user id into a big number; % 4 picks one of four shards. Similar ids land on different shards, so load spreads evenly.

3. Range partitioning keeps dates together

   ranges = [("2026-01", "2026-03", "P0"), ("2026-04", "2026-06", "P1"),
             ("2026-07", "2026-09", "P2"), ("2026-10", "2026-12", "P3")]
   def part_for(month):
       return next(p for lo, hi, p in ranges if lo <= month <= hi)
   print("2026-10 ->", part_for("2026-10"), "| 2026-02 ->", part_for("2026-02"))

   2026-10 -> P3 | 2026-02 -> P0
   For analytics, ranges of dates are natural: a report on October reads only P3. The catch: every new order goes into the newest range, so one partition takes all the writes.

4. The trouble with % N when you grow

   import hashlib
   h = lambda k: int(hashlib.md5(k.encode()).hexdigest(), 16)
   keys = [f"U{i}" for i in range(1000)]
   moved = sum(1 for k in keys if h(k) % 4 != h(k) % 5)
   print(f"mod-N, 4 -> 5 shards: {moved / len(keys):.0%} of keys move")

   mod-N, 4 -> 5 shards: 79% of keys move
   Going from 4 to 5 shards changes hash % N for most keys, so most of the data would have to move. Consistent hashing reduces this to roughly one fifth (see scenario 1).

5. Directory partitioning for special cases

   directory = {"tenant_acme": "shard-A", "tenant_bigbazaar": "shard-B", "tenant_small_1": "shard-C"}
   print(directory["tenant_bigbazaar"])
   directory["tenant_bigbazaar"] = "shard-D"     # move a big tenant to its own shard
   print(directory["tenant_bigbazaar"])

   shard-B shard-D
   A lookup table lets you place big customers deliberately and move them without rehashing anyone else. It is common in multi-tenant SaaS products. The directory itself must be fast and highly available.

6. Queries with and without the key

   “Orders of U42” goes to one shard. “All orders from Pune today” has no user id, so the router asks all shards and merges the results.

   Scatter-gather works, but it gets slower and costlier as shards grow. Such analytical questions are better answered from a data lake or warehouse copy partitioned by date.

Two queries: one shard or all shards

Step through the six frames. Left: Riya checking her orders and a support agent searching by city. Right: how the router finds the data.

Real-time scenarios: partitions under pressure

Three live scenarios: adding a shard with and without consistent hashing (real numbers), a viral offer that overloads one shard, and an advanced look at the date-partitioning trade-off.

Adding a fifth shard: who has to move?

These numbers come from the program in “Run it on your PC”: 3,000 users on 4 shards, then a 5th shard is added. Compare simple hash % N with consistent hashing.

One viral offer melts one shard

Orders are sharded by kitchen. Then one famous kitchen announces a ₹1 biryani offer at 8 pm. Watch the CPU of each shard.

Partitioning by date: great for reports, bad for writes

Range partitioning by date makes date-range reports fast, but it creates a moving hotspot: every new row lands in the newest partition. Watch the trade-off and the composite-key fix.

Partitioning in real systems

Route orders to shards

Orders are routed to 4 shards by a stable hash of the user id. The program prints how many orders land on each shard, then answers one query that has the shard key and one that doesn't. Then try the challenges: range partitioning, choosing a key, mod-N rebalancing, consistent hashing and hot keys.

import hashlib

def shard_for(key, n=4):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % n

orders = [("O1", "U9", "Pune"), ("O2", "U42", "Thane"), ("O3", "U9", "Pune"),
          ("O4", "U7", "Mumbai"), ("O5", "U42", "Pune"), ("O6", "U13", "Nashik")]
shards = {0: [], 1: [], 2: [], 3: []}
for oid, user, city in orders:
    shards[shard_for(user)].append((oid, user, city))

for s, rows in shards.items():
    print(f"shard {s}: {rows}")

# With the shard key: ask one shard
target = shard_for("U9")
print("orders of U9 -> shard", target, ":", [r[0] for r in shards[target] if r[1] == "U9"])

# Without the shard key: ask every shard (scatter-gather)
pune = [r[0] for rows in shards.values() for r in rows if r[2] == "Pune"]
print("orders from Pune -> all shards:", pune)

• return int(hashlib.md5(key.encode()).hexdigest(), 16) % nA stable hash turns the key into a big number; % n picks a shard. (Python's built-in hash() changes between runs, so it can't be used for routing.)
• shards[shard_for(user)].append((oid, user, city))All orders of one user land on the same shard, because the user id is the partition key.
• pune = [r[0] for rows in shards.values() for r in rows if r[2] == "Pune"]City is not the shard key, so every shard must be searched: scatter-gather.

Run it on your PC: four real shards with SQLite

This program creates four SQLite database files, routes 20,000 orders to them by a hash of the user id, then compares a query with the shard key (one database) and one without it (all four). Finally it measures how many users would move when a fifth shard is added, with % N and with consistent hashing. Only the standard library is used. Save it as shard_lab.py and run it.

"""Four real SQLite database files used as shards.
Orders are routed by a hash of the user id. Then we compare a query that uses the
shard key with one that doesn't, and measure how many keys move when a shard is added."""
import bisect, hashlib, os, random, sqlite3

SHARDS = 4
os.makedirs("shards", exist_ok=True)


def h(text):
    """A stable hash (Python's built-in hash() changes between runs)."""
    return int(hashlib.md5(text.encode()).hexdigest(), 16)


conns = []
for i in range(SHARDS):
    path = f"shards/orders_{i}.db"
    if os.path.exists(path):
        os.remove(path)
    c = sqlite3.connect(path)
    c.execute("CREATE TABLE orders (order_id TEXT, user_id TEXT, city TEXT, amount INT)")
    conns.append(c)

random.seed(11)
cities = ["Pune", "Mumbai", "Thane", "Nashik"]
for n in range(20_000):
    user = f"U{random.randint(1, 3000)}"
    shard = h(user) % SHARDS
    conns[shard].execute("INSERT INTO orders VALUES (?, ?, ?, ?)",
                         (f"O{n}", user, random.choice(cities), random.randint(50, 900)))
for c in conns:
    c.commit()

print("Rows per shard:", [c.execute("SELECT COUNT(*) FROM orders").fetchone()[0] for c in conns])

# Query 1: by the shard key -> exactly one shard
user = "U42"
shard = h(user) % SHARDS
rows = conns[shard].execute("SELECT COUNT(*), SUM(amount) FROM orders WHERE user_id = ?", (user,)).fetchone()
print(f"\nOrders of {user}: ask shard {shard} only -> {rows[0]} orders, Rs {rows[1]}")

# Query 2: not by the shard key -> ask every shard and merge (scatter-gather)
parts = [c.execute("SELECT COUNT(*) FROM orders WHERE city = 'Pune'").fetchone()[0] for c in conns]
print(f"Orders from Pune: ask all {SHARDS} shards {parts} -> total {sum(parts)}")

# Adding a fifth shard: how many users would have to move?
users = [f"U{i}" for i in range(1, 3001)]
moved_mod = sum(1 for u in users if h(u) % 4 != h(u) % 5)

def ring(nodes, vnodes=100):
    points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
    return [p for p, _ in points], [n for _, n in points]

def owner(key, r):
    keys, names = r
    i = bisect.bisect(keys, h(key)) % len(keys)
    return names[i]

r4, r5 = ring(["S0", "S1", "S2", "S3"]), ring(["S0", "S1", "S2", "S3", "S4"])
moved_ring = sum(1 for u in users if owner(u, r4) != owner(u, r5))
print(f"\nAdding a 5th shard, users that must move:")
print(f"  hash % N          : {moved_mod} of {len(users)} ({moved_mod / len(users):.0%})")
print(f"  consistent hashing: {moved_ring} of {len(users)} ({moved_ring / len(users):.0%})")

# In a terminal:  python shard_lab.py

Routing by range, one line at a time

Three orders are placed into quarterly partitions by month. Watch the loop find the first partition whose range contains each month.

Worked examples: real problems, solved and traced in memory

Four partitioning problems, from routing by hash to finding hot keys. Each runs live and is traced.

U1 … U9, 3 servers

U1 -> server 1
U2 -> server 2
U3 -> server 2
U4 -> server 0
U5 -> server 0
U6 -> server 0
U7 -> server 0
U8 -> server 2
U9 -> server 2
users per server: {0: 4, 1: 1, 2: 4}

365 daily partitions, 7-day query

partitions scanned: 7 of 365 (days 288-294 of the year)
data read: 1.9% of the table

8 sample orders, keys: city, user_id, order_id

order_id: 8 distinct, biggest share 12%
user_id : 6 distinct, biggest share 25%
city    : 3 distinct, biggest share 62%

sample of 40 requests over 9 keys

K7 is hot: 24 requests vs average 4.4 -> split into 3 sub-keys

Check yourself

Quick revision

Interview and viva questions

Practice problems

Partitioning exercises, from routing a key to sizing Kafka partitions. The last two are business tasks.

101, 256, 999, 1200

101 -> shard 5
256 -> shard 4
999 -> shard 3
1200 -> shard 0

for cid in [101, 256, 999, 1200]:
    print(cid, "-> shard", cid % 6)

1500

P1

ranges = [("P0", 1, 1000), ("P1", 1001, 2000), ("P2", 2001, 3000)]
print(next(p for p, lo, hi in ranges if lo <= 1500 <= hi))

6 orders

{'Pune': 2, 'Mumbai': 3, 'Thane': 1}

cities = ["Pune", "Mumbai", "Pune", "Thane", "Mumbai", "Mumbai"]
counts = {}
for c in cities:
    counts[c] = counts.get(c, 0) + 1
print(counts)

[120, 95, 300, 110]

1.92 unbalanced

rows = [120, 95, 300, 110]
skew = max(rows) / (sum(rows) / len(rows))
print(round(skew, 2), "unbalanced" if skew > 1.5 else "ok")

3 shards

[('O5', 990), ('O1', 900), ('O3', 880)]

shard_results = [[("O1", 900), ("O7", 650)], [("O3", 880), ("O9", 300)], [("O5", 990), ("O2", 410)]]
merged = sorted([r for res in shard_results for r in res], key=lambda r: -r[1])
print(merged[:3])

ids 1–1000

831 of 1000 move

moved = sum(1 for i in range(1, 1001) if i % 5 != i % 6)
print(moved, "of 1000 move")

1024 logical, 4 → 5 servers

target per server: [205, 205, 205, 205, 204]
logical shards moved: 204 (20%)

logical = 1024
before = [logical // 4] * 4
target = [logical // 5 + (1 if i < logical % 5 else 0) for i in range(5)]
moved = sum(max(0, b - t) for b, t in zip(before, target[:4]))
print("target per server:", target)
print("logical shards moved:", moved, f"({moved / logical:.0%})")

60 MB/s, 4 MB/s per consumer, +50%

23 partitions

import math
print(math.ceil(60 * 1.5 / 4), "partitions")

6 TB, +250 GB/month, 2 TB per shard

now: 3 shards | in 2 years: 6 shards

import math
now = 6
later = now + 0.25 * 24
print("now:", math.ceil(now / 2), "shards | in 2 years:", math.ceil(later / 2), "shards")

Real-world scenario questions (asked in company interviews)

Partitioning decisions from real systems and interviews. Decide your answer first, then open the model answer.