How Database Sharding Actually Works: Hash, Range, and Directory-Based Strategies

Quick Answer

Sharding splits DIFFERENT rows of data across multiple databases so no single machine holds it all, scaling write capacity and total storage. The three common strategies — hash-based, range-based, and directory-based — trade off evenness of distribution against how expensive it is to change the number of shards later, and we ran all three against the same 20 sample user IDs in Python to show the real, measured difference rather than just describe it.

Sharding vs replication: different data, not the same data

It's worth being precise about this up front, since the two get confused constantly: Priodemy's database replication post covers copying the same data onto multiple machines, mainly to scale reads and survive failures. Sharding is the opposite move — splitting different rows across different machines, so that no single database has to hold, or write, the entire dataset. Replication helps you serve more reads of data that already fits on one machine; sharding helps you when the data, or the write volume, has outgrown what one machine can hold or handle at all. Large systems commonly run both at once — each shard is itself replicated for redundancy.

This post focuses purely on the mechanics of how a key gets mapped to a shard, with real code run on real sample data. For the equally important operational question of whether you should shard at all, and what cross-shard joins cost you once you do, Priodemy's existing sharding fundamentals post covers that ground well — this one picks up where a formula actually decides where a row lives.

Hash-based sharding: the code, and the real distribution

The simplest scheme: hash the key, take it modulo the number of shards. Here's real code, run against 20 sample user IDs (1001 through 1020) across 4 shards:

import hashlib

def hash_shard(key: int, n: int) -> int:
    # A stable hash (not Python's built-in hash(), which is randomized
    # per-process for strings) so the mapping is reproducible.
    h = hashlib.md5(str(key).encode()).hexdigest()
    return int(h, 16) % n

user_ids = list(range(1001, 1021))   # 20 sample user IDs
n = 4
assignment = {uid: hash_shard(uid, n) for uid in user_ids}

The actual resulting distribution:

shard 0: [1002, 1015, 1017]  (count=3)
shard 1: [1005, 1007, 1008, 1009, 1013, 1016, 1018, 1019, 1020]  (count=9)
shard 2: [1001, 1003, 1004, 1006, 1012, 1014]  (count=6)
shard 3: [1010, 1011]  (count=2)

Notice this isn't perfectly even — shard 1 got 9 of the 20 keys while shard 3 got only 2. That's not a bug in the hash function; it's what you should expect from a small sample. MD5 (and any well-behaved hash function) distributes uniformly in the limit, over a large number of keys, but with only 20 data points, random-looking clumping is completely normal, the same way flipping a fair coin 20 times can land on 13 heads without the coin being biased. At the scale real systems actually shard at — millions of keys — this evens out close to perfectly.

The resharding problem: growing from 4 shards to 5

Here's the real cost of naive modulo hashing. Take the exact same 20 keys and the exact same hash function, and just change n from 4 to 5 — which is what happens the moment you add one more database server to handle growth:

Keys that moved to a different shard: 15 / 20 -> [1001, 1003, 1004, 1005, 1006, 1007, 1008, 1011, 1013, 1014, 1015, 1016, 1018, 1019, 1020]
Keys that stayed on the same shard:   5 / 20 -> [1002, 1009, 1010, 1012, 1017]
Percentage remapped: 75%

75% of the keys landed on a different shard than before, for adding a single machine to a 4-node cluster. That's not a rounding error — it's the defining weakness of plain modulo hashing, because key % 4 and key % 5 are almost entirely unrelated functions of the same key. Every one of those remapped keys means a real row of data has to physically migrate to a different machine before reads and writes against it will even find the right shard. Production systems avoid this with consistent hashing, which bounds the fraction of keys that move when you add or remove a shard to roughly 1/n instead of nearly everything — confirming, with real numbers, exactly the claim you'll see stated in the sharding fundamentals post linked above.

Range-based sharding: simple, until the hot range problem

Range sharding assigns contiguous blocks of the key space to each shard instead of scattering them by hash:

def range_shard(key: int, boundaries: list) -> int:
    for i, upper in enumerate(boundaries):
        if key < upper:
            return i
    return len(boundaries)

boundaries = [1006, 1011, 1016]   # 4 shards of 5 IDs each
range_assignment = {uid: range_shard(uid, boundaries) for uid in user_ids}

On our same 20 IDs, this produces a perfectly even split, because the sample happens to be a contiguous, evenly-sized block:

shard 0: [1001, 1002, 1003, 1004, 1005]  (count=5)
shard 1: [1006, 1007, 1008, 1009, 1010]  (count=5)
shard 2: [1011, 1012, 1013, 1014, 1015]  (count=5)
shard 3: [1016, 1017, 1018, 1019, 1020]  (count=5)

That even split is exactly the trap. Real user IDs are usually sequential, auto-incrementing integers, which means every new signup gets a number higher than every existing one. Simulate 20 new signups arriving right after the existing range, and here's what actually happens under both strategies on the identical new data:

new_signups = list(range(1021, 1041))   # 20 new users, IDs keep climbing

Range sharding result:
shard 3: 20 of the 20 new signups   -> 100% of new write traffic hits one shard

Hash sharding on the SAME 20 new signups, for comparison:
shard 0: 6 of the 20 new signups
shard 1: 2 of the 20 new signups
shard 2: 1 of the 20 new signups
shard 3: 11 of the 20 new signups

Every single new signup lands on shard 3 under range sharding — that's the hot range problem, and it's not a contrived edge case, it's the default behavior of range sharding on any monotonically increasing key, which describes most primary keys. Hash sharding, run on the exact same 20 new IDs, spreads them across all 4 shards instead, precisely because a hash function deliberately destroys the ordering that range sharding depends on and that causes the hot spot in the first place. The trade-off is real: range sharding gives you cheap, efficient range queries ("all orders from this week") at the cost of write hotspots on growing keys; hash sharding gives you even write distribution at the cost of range queries now requiring a scatter-gather across every shard.

Directory-based sharding: a lookup table instead of a formula

The third approach skips formulas entirely: an explicit table mapping each key to its shard, which you can populate by whatever policy makes sense — here, by the region a user signed up from:

region_to_shard = {"mumbai": 0, "delhi": 1, "bangalore": 2, "chennai": 3}
directory = {uid: region_to_shard[region_of_user[uid]] for uid in user_ids}

shard 0 (mumbai):    [1001, 1005, 1009, 1013, 1017]
shard 1 (delhi):     [1002, 1006, 1010, 1014, 1018]
shard 2 (bangalore): [1003, 1007, 1011, 1015, 1019]
shard 3 (chennai):   [1004, 1008, 1012, 1016, 1020]

Rebalance user 1005 onto a different shard:
before: user 1005 -> shard 0
after:  user 1005 -> shard 3   (only the directory row changed — no formula to recompute)

The payoff shows up when you need to rebalance. Under hash or range sharding, moving one user to a different shard means changing the formula itself, which risks moving every other key too. Under a directory, moving one user is a single row update in the lookup table — nothing else in the system's addressing scheme changes. This is genuinely how large-scale systems like MongoDB's sharded clusters and Vitess (MySQL sharding, built at YouTube) handle rebalancing in practice: a lookup layer they control directly, rather than a fixed hash or range formula baked into application code. The cost is the mirror image of the benefit: the directory itself becomes a critical, must-be-fast, must-be-correct piece of infrastructure, and a wrong or stale entry in it silently sends a query to the wrong shard.

Cross-shard queries: the part no strategy fixes

None of these three strategies makes a query spanning multiple shards cheap. "Give me the total order count across all users" has to hit every shard, collect the partial results, and merge them in application code or a query-routing layer (which is exactly what dedicated sharding middleware like Vitess or Citus exists to automate) — the database engine on any single shard has no way to see rows living on a different shard. Good shard-key choice reduces how often you're forced into this (see below), but it never eliminates it for queries that are inherently cross-cutting, like global aggregates or admin reports.

Picking a shard key in practice

Given the trade-offs above, a good shard key in practice needs three things at once: high cardinality (many distinct values, so the key space is actually large enough to spread across shards), an access pattern that doesn't concentrate writes on one value (which is exactly what a growing, low-cardinality, or sequential key breaks), and enough locality that data commonly queried together lands on the same shard — sharding by tenant_id or user_id, for instance, keeps one customer's own rows together so their queries stay single-shard, even though the overall dataset is spread across many shards. There's no key that's right for every workload; the right choice depends entirely on which queries you run most and which of these three failure modes you'd rather live with.

Frequently Asked Questions