What replicas cannot absorb
Writes, which all still go through the single leader.
Lesson 4-2 in one line is that replicas copy the leader and cannot accept writes. Adding a fourth or tenth replica multiplies read capacity and leaves write capacity exactly where it was.
Replicas make write load slightly worse, which is worth noting. Every write now has to be shipped to and replayed by every follower, so the leader's job grows with the number of replicas rather than shrinking.
Data size is the other ceiling, and it is independent of throughput. A replica holds a full copy, so a table too large for one machine is too large for every machine in the set.
When write volume or total data size outgrows one leader machine, copying stops helping. You must split the data itself, which is sharding.
Sharding
Sharding (also called partitioning) splits one big table across several independent databases. Each piece is a shard, and each shard is a full leader-follower setup from unit 4 holding only its slice of the rows.
Every row is assigned to a shard by a shard key, a column chosen up front. Two common schemes:
- Range sharding: shard 0 holds users A through F, shard 1 holds G through M, and so on. Great for range queries, but risky: new signups or hot alphabet regions can pile onto one shard
- Hash sharding: run the shard key through a hash function and compute
hash(user_id) % number_of_shards
That second scheme needs a term your prerequisites did not cover. A hash function is a formula that turns any piece of data (a user ID, an email, a whole file) into a fixed-size number. Two properties make it useful here: the same input always produces the same number, and different inputs land spread across the whole output range, as if at random. So hash(user_id) gives every user a stable, random-looking number, and % number_of_shards (the remainder after division) turns that number into a shard index from 0 to N-1. Same user, same shard, every time, with users spread evenly and no lookup table to maintain.
Hash sharding is the common default. It has one famous weakness though: what happens when you add a shard? The modulus changes, and almost every key now maps somewhere new.
How a hash function assigns shards
h turns any name into a huge number, using md5 because Python's built-in hash gives different values on each run.
import hashlib def h(s): return int(hashlib.md5(s.encode()).hexdigest(), 16) for name in ["ada", "bob", "cai"]: print(name, "-> hash ends in", h(name) % 1000, "-> shard", h(name) % 4) print("ada again -> shard", h("ada") % 4)
Output
ada -> hash ends in 225 -> shard 1 bob -> hash ends in 632 -> shard 0 cai -> hash ends in 807 -> shard 3 ada again -> shard 1
Both properties show up in that output. The three shard assignments are scattered rather than sequential, and hashing ada twice gives shard 1 both times.
Determinism is what makes this usable as a routing rule, since any app server can compute the shard for a user with no coordination. There is no lookup table to keep in sync, which is the main advantage over range sharding.
The scattering matters just as much, because it is what balances the shards. Names that are alphabetically adjacent land on unrelated shards, so a burst of signups starting with the same letter does not pile onto one machine.
int(..., 16) parses the hex digest as a base-16 number, turning md5's text output into an integer that % can work on. The 16 is the base, not a length.
Adding your own name to the list gives it a shard too, with no configuration anywhere. That is the property to hold onto, and the next block shows what it costs when the shard count changes.
What adding a shard costs under mod-N
A thousand keys on 4 shards, then on 5, counting how many changed shard.
import hashlib def h(s): return int(hashlib.md5(s.encode()).hexdigest(), 16) keys = ["user" + str(i) for i in range(1000)] before = {k: h(k) % 4 for k in keys} after = {k: h(k) % 5 for k in keys} moved = sum(1 for k in keys if before[k] != after[k]) print("Adding a 5th shard with mod-N moved", moved, "of 1000 keys")
Output
Adding a 5th shard with mod-N moved 795 of 1000 keys
Nearly 80% of keys changed shard, and each of those is data that must physically move between machines. The ideal number is 200, meaning only the keys the new shard should take over.
The reason is in the definition of ownership. A shard owns every key whose remainder is 2, and changing the divisor changes almost every remainder, so the key that mapped to shard 2 under mod 4 has no reason to map there under mod 5.
Think about what 795 of 1000 means at real scale. A terabyte database means 800 GB crossing the network while the system is serving traffic, which is hours of degraded performance and a genuinely risky operation.
That cost is why teams put off resharding until it is an emergency, and then do it under the worst conditions. The fix is to make growth cheap, which is the next block.
md5 is used instead of Python's hash() because md5 gives the same value on every run. Python randomizes string hashing per process for security reasons, which would make this experiment produce a different number each time.
Consistent hashing
Moving 80% of your data to add one machine is a disaster. Consistent hashing fixes it by changing what a shard owns. Under mod-N, a shard owns "every key whose remainder is 2", a definition that changes for almost every key when N changes. Under consistent hashing, a shard owns fixed regions of the hash space, the full range of numbers the hash function can output, and those regions do not depend on how many shards exist.
The rule: give each shard many marker numbers scattered through the hash space (its virtual nodes). A key belongs to the shard owning the nearest marker at or above the key's hash, and a key hashing beyond the last marker wraps around to the first. Because of that wrap-around, engineers draw the hash space as a circle, the hash ring: place the shard markers on the circle, hash the key onto the circle, walk clockwise to the first marker you meet.
Now watch what adding a shard does: its new markers claim only the slices of hash space just before them. Keys in every other slice keep their old owner untouched. Ideally only about 1/N of keys move, exactly the fraction the new shard should take over.
This one idea powers Cassandra, DynamoDB, and most distributed caches, and it is a favorite interview question. Compare its result against mod-N.
The same growth on a hash ring
build_ring places each shard at 100 points, and lookup walks clockwise using binary search.
import hashlib, bisect def h(s): return int(hashlib.md5(s.encode()).hexdigest(), 16) def build_ring(nodes, vnodes=100): return sorted((h(n + "#" + str(v)), n) for n in nodes for v in range(vnodes)) def lookup(ring, key): hashes = [point for point, node in ring] i = bisect.bisect(hashes, h(key)) % len(ring) return ring[i][1] keys = ["user" + str(i) for i in range(1000)] ring4 = build_ring(["s0", "s1", "s2", "s3"]) ring5 = build_ring(["s0", "s1", "s2", "s3", "s4"]) moved = sum(1 for k in keys if lookup(ring4, k) != lookup(ring5, k)) print("Adding a 5th shard with a hash ring moved", moved, "of 1000 keys")
Output
Adding a 5th shard with a hash ring moved 179 of 1000 keys
179 is close to the ideal 1/5 of 1000, which is 200, because only the keys the new shard takes over move. Compare that with 795 from mod-N, and the same operation just got four times cheaper.
h(n + "#" + str(v)) is what creates the virtual nodes, giving shard s0 a hundred different positions around the ring. Without them a shard would own one contiguous slice, and the slices would be badly uneven by luck.
The % len(ring) in lookup is the wrap-around, so a key hashing past the last marker belongs to the first. That single modulo is what makes the hash space a circle rather than a line.
bisect.bisect finds the insertion point in the sorted list, which is the first marker at or above the key's hash. It is a binary search, so lookup cost grows logarithmically with the ring size rather than linearly.
The number is 179 rather than exactly 200 because hashing is random rather than perfectly uniform. More virtual nodes tightens it toward the ideal, which is why production rings use hundreds per shard.
This one idea powers Cassandra, DynamoDB, and most distributed caches. It is also a favorite interview question, and being able to describe the ring plus virtual nodes plus the clockwise walk is usually enough.
Querying by something other than the shard key
The query must ask every shard and merge the results, because username is not the shard key.
The shard key is user_id, so usernames are scattered across all shards by design. That scattering is exactly what balanced the data, and it is what makes this query expensive.
This is called a scatter-gather query, and it is the great cost of sharding. Anything not keyed by the shard key gets expensive, so the choice of shard key determines which queries stay cheap for the life of the system.
The costs compound in ways worth naming. The query is as slow as the slowest shard, it consumes capacity on every machine rather than one, and sorting or paginating the merged results has to happen in the application layer.
There are two standard mitigations. A secondary index sharded by username gives a direct lookup at the cost of maintaining a second structure, and pushing the query to a search system such as Elasticsearch handles the cases SQL was never going to do well anyway.
The design lesson is to pick the shard key from your query patterns rather than from what looks like a natural identifier. If most queries filter by user, shard by user, and accept that everything else is a scatter-gather.