Partitioning

Partitioning, also called sharding, splits a dataset that’s too big or too busy for one machine into pieces, each owned by a different machine. You need a rule that maps every key to its owner. The obvious rule, hash the key and take the remainder by the number of servers, works until you add a server, at which point almost every key moves. Consistent hashing fixes that by placing servers and keys on a ring and giving each key to the next server clockwise, so a new server only takes keys from its neighbors, roughly 1/n of them with n servers. Each server usually gets many small spots on the ring, called virtual nodes, to even out the load. What remains hard is hot spots: one celebrity key can swamp its partition however evenly keys are spread.