Where does each comment live?
By Zeeshan Adil · 2 min read
Sharding sounds like one decision. It's three: which partition a record belongs to, which database hosts that partition right now, and how you move it without losing a write. This challenge builds all three on real databases, in seven parts.
THE PROBLEM
The problem
One database can't hold every comment of a busy app, so you split the comments across several databases, called shards. Then every request has to answer a question: which database owns this post?
Whenever you add, remove or lose a database, you have to answer a second one: what has to move, and how do you move it while writes keep coming? Then comes the post that goes viral and lands on one database no matter how many you add, and the API server whose cached map is out of date and keeps writing to a database that no longer owns the data.
Keep one idea in mind throughout: hashing decides which partition a record belongs to, a separate map says which database hosts that partition right now, and moving data is a third, separate job. Mixing them up is where the dangerous bugs live.
STEP 1 · PREDICT
You have 3 databases and route each post with hash(post_id) % 3. A 4th database joins and the rule becomes % 4. What share of posts now belong to a different database?
- About 25%: the new database's share
- About 50%
- About 75%
Write your answer down. The rest of the page will tell you.
STEP 2 · BUILD IT
Build a Comments API across several SQLite shards that can add, remove and lose a database without losing a write.
Your solution should:
- Route by four placements behind one
owner(key)interface:hash % n, fixed buckets with a map, a hash ring with virtual nodes, and key ranges. - Move data live when the placement changes: capture, copy, catch up, fence writes briefly, switch, clean up. Lose none of the writes you acknowledged while it moves.
- Spread one viral post by splitting its key into stripes, and accept that a read then asks every stripe.
- Fence at the database: each vnode's map entry carries an epoch that goes up when it moves, and a write from an API server holding an older map is refused, refreshed and retried, with a request id so the retry doesn't duplicate.
Stuck? Hints
- One token per database on a ring is a lottery. Give each database many virtual nodes and measure how even the shares get.
- Key ranges make neighbouring keys live together, which is great for scans and terrible for the newest keys, which all land on the last range.
- Forgetting a crashed database is not the same as removing one. Reroute without a copy and its posts disappear silently.
STEP 3 · CHECK IT
Run the tests that hold it to the rules
git clone https://github.com/ZeeshanAdilButt/distributed-systems-challenges cd distributed-systems-challenges uv sync --all-packages uv run shardbox # opens http://127.0.0.1:8090
No Postgres needed, and it runs on Windows too. Each part also has its own script, for example uv run challenges/03-consistent-hashing/part-1-why-modulo-breaks/modulo_breaks.py. What the seven parts show:
| part | what you'll see |
|---|---|
| 1 · Why hash % n breaks | adding a 4th database moves 75% of posts |
| 2 · Fixed buckets | only the map entry changes; post 15001 is always bucket 9 |
| 3 · The ring and vnodes | one token each: one database held 98.6% of the ring; 256 vnodes: 23% to 26.5% |
| 4 · Key ranges | a 1,000-post scan asks 1 database, and all 10,000 newest posts land on 1 |
| 5 · Moving data safely | 0 of 10,000+ acknowledged writes lost in a live move |
| 6 · One viral post | one key is one database at 2 shards or 32, until you stripe it |
| 7 · Stale routers and epochs | with an epoch check all 200 writes land; without, 200 of 200 are stranded |
STEP 4 · UNDERSTAND
Try it yourself first. This is how the solution in the repo works.
Why modulo breaks, and what replaces it
About 75% was right. Change n in hash % n and almost every key gets a new owner, so adding one database means moving most of your data. Every other strategy moves only the new database's share.
| Fixed buckets | Hash ring | Key ranges | |
|---|---|---|---|
| The rule | crc32(post_id) % 12 picks a bucket, a map says who holds it | hash onto a circle, the first token clockwise owns it | each database owns a run of post ids |
| Add a database | it takes a few whole buckets you choose | it takes the arcs just before its tokens | the busiest range splits at its median |
| Good at | predictable moves | every router computes ownership from the member list | range scans |
| Watch out | the bucket count caps how fine you can split | one token per database is a lottery: use vnodes | new keys pile onto the last range |
| Used by | Redis Cluster, Kafka partitions | Dynamo, Cassandra, ScyllaDB | Bigtable, Spanner, CockroachDB |
Moving data without losing writes
The move runs in phases: capture new writes, copy the existing rows, catch up on what was captured, fence writes for a moment, switch the map, then clean up. Measured live, none of more than 10,000 acknowledged writes were lost. Crash a database with no copy and forget it, and 658 posts are gone, silently if you only reroute.
The stale router is the same lesson as challenge 01 in a new place. An API server with an old map computes the old owner and writes there. With an epoch on the map, checked at the database, that write is refused once, the server refreshes its map, and the retry lands in the right place. Without it, every one of its writes is stranded.
What this does not do
- One process. The shards are separate files, but the router and the shards share a process, so real network partitions and clock skew aren't modelled.
- One lock stands in for consensus. A real metadata service is replicated, with etcd or ZooKeeper, so it survives a member failing.
- Replicas and migration are kept apart. Moving data while keeping every replica in step is the next level.
STEP 5 · YOUR TURN
Lose a database on purpose
In shardbox, pick ring + vnodes, add a database, then crash one and forget it instead of restoring it. How many posts are gone, and why would simply rerouting hide that from you?
THE SOLUTION
Compare yours with mine
The shardbox system (shards, cluster, routing and the page), the four placements in jiffy-ring, and a README, script, results and test for each of the seven parts.
Finished part 3?
Star the repo so you hear when the next challenge lands, and post your results. Other machines are half the fun.