Quiz
Warm-up from unit 4: you added three read replicas, but the database still cannot keep up. What kind of load are replicas unable to absorb?
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.
Code exercise · python
Run this hash demo before the sharding experiments. h() turns any name into a huge number (we use md5, a standard hash function, because Python's built-in hash() gives different values on each run). Notice both properties: the outputs look scattered, and hashing ada twice gives the same shard both times.
Code exercise · python
Run this experiment. We place 1,000 keys on 4 shards using hash mod N, then grow to 5 shards and count how many keys changed shard, meaning their data must physically move between machines.
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. Run it and compare against mod-N.
Code exercise · python
Run the hash ring version of the same experiment. build_ring places each shard at 100 points, lookup walks clockwise using bisect (binary search on the sorted ring). Compare the moved count with the 795 from mod-N.
Quiz
A table sharded by user_id needs to answer: find all users whose username starts with A. What must the query do?