Consistent hashing
Pixel's four shards are filling up, and a fifth is due. Adding a shard sounds simple — so what happens to the users who are already placed, and is there a better way to pick a shard?
13 minMediumStation: Consistent hashingMembers lesson
Membership isn’t open yet. The free lessons are open — 16 of them, including the whole first leg of the Scale Line.
- Pixel goes viral
- Sharding
- Consistent hashing
- Hot keys
- Multi-region
What you'll be able to do
- 1Predict roughly what share of the keys move to another shard when one shard is added, with hash mod N and with a hash ring.
- 2Explain how a ring finds a key's shard, and why adding or removing a shard only touches the keys next to it.
- 3Explain why each server takes many points on the ring, and what that changes when a server joins or fails.
Inside the lesson
- steps
- 12
- questions
- 8
- simulations
- 4
You guess first, then run the system and see if you were right.
Step 1 · The setup
Pixel's four shards held up — and Pixel kept growing. Writes are up to 480 a second, about 120 per shard, and each shard runs about 60% busy. Before the next spike, the team adds a fifth shard.
At the last stop the router hashed each user id to pick a shard. The simplest way to do that is hash(user id) mod 4: four shards, four remainders. With five shards it becomes mod 5. The new shard will take about a fifth of the load — but whose rows will now live somewhere else?
Steps 2–12 are for members
More on the Scale Line
- Latency & percentilesOpen8 min
- Server capacity & scaling upFree with an account10 min
- Split app and database tiersFree with an account10 min
- Load balancerFree with an account10 min
- Horizontal scaling with a stateless tierFree with an account10 min
- Cache-asideFree with an account10 min
- Object storage for user filesMembers10 min
- A CDN for the files everyone wantsMembers12 min