Loading...
Loading...
Distribute data across nodes with minimal reshuffling
Distributed Data Partitioning
You already know from the sharding module how a shard key spreads rows across machines, and how naive key-modulo-N placement reshuffles nearly everything when N changes. Naive math says server = hash(key) divided by N, the remainder after division, where a hash is a recipe turning any key into a number and N is the server count. That breaks the day N changes, relocating nearly every key at once. Consistent hashing, a placement scheme where servers and keys share one ring and each key belongs to the next server clockwise, arranges servers on a ring so a newcomer adopts only its neighbors' keys. Try it above: add a node and count what moves.
Think of numbered seats around a clock face, the one comparison we will use here: guests sit at the next taken seat clockwise from their ticket number, so adding one chair only reseats the guests nearest to it. In the lab, note the moved-key count with three servers, add a fourth, and watch it stay near a quarter instead of three quarters, because only the arcs next to the newcomer change owners.
Remainder assignment is simple: hash the key, divide by N, keep the remainder. We rejected it for elastic fleets because it spreads evenly while N sits still, and it has no memory of yesterday, so the day N moves almost every remainder changes. Work the tiny case below and feel why caches dread scaling day.
Map the whole hash range onto a circle, where 2 to the 32nd is about 4.3 billion slots. Hash each server name to one seat and each key to one ticket number, then store each key on the first server clockwise from its ticket. Clockwise means moving forward around the ring until the next seat. No table of locations is needed because the rule plus the seat list answers every lookup.
D takes over only the arc from B to D. Keys elsewhere never notice.
B's arc falls to the next seat clockwise, say C. Everyone else keeps serving.
Random single seats land unevenly: one server can own half the clock while another owns a sliver. A virtual node (one of many seats dealt to the same physical server, often 100 to 200 of them) fixes that by scattering each server around the ring. Averages tighten as seats multiply, and a new server's load arrives as many small arcs instead of one giant one.
The trade is bookkeeping: 450 seats instead of 3, plus slightly longer seat lists to share. That cost is trivial next to balanced disks. In the lab, toggle virtual nodes from 1 to 150 and watch the tallest bar shrink toward the average, because many small arcs average out.
Large key-value stores, services that map keys to values across many machines with no master, use rings plus virtual seats so new racks adopt slices without pausing traffic. Even spreading is what keeps one rack from melting.
Wide-column databases, stores that group columns into flexible rows spread by partition key, use hundreds of virtual seats per machine by default. That density is why removing one machine moves only its fair share instead of reshuffling the cluster.
New box joins, neighbors hand over a slice, everyone else keeps serving. Placement without stampedes keeps the data reachable, but reachable copies still have to agree. Once your keys land on three different machines, how do you decide which copy a reader should trust?
Try this in the playground
Open a template and build it yourself — then take a quiz.