The simplest way to distribute data is to take the hash of the key and divide it by the number of machines, taking the remainder. It works perfectly until you add a fourth machine to a three-machine cluster—at which point nearly every key is reassigned, and the cluster must transfer all the data over the network.
Arrange everything in a circle
Consistent hashing maps both the key and the server into the same space—imagine it as a circle. Each key is assigned to the first server encountered when moving clockwise from its position.
Adding a server affects only the segment immediately preceding it—on average, 1/n of the data rather than nearly all of it. Removing a server has the same effect: only the portion handled by that server is transferred to the next server.
The Problem of Skewed Distribution and How to Fix It
With a small number of machines, the distribution points across the ring are uneven, with some machines covering an arc several times longer than others. The standard solution is a virtual node: each physical machine is hashed into the ring at hundreds of different positions. The law of large numbers ensures an even distribution.
Virtual nodes are also convenient because more powerful machines can handle more locations than less powerful ones—distributing the load based on actual capacity.
Where you saw it
Distributed caching, distributed key-value databases, content delivery networks that select edge servers, and load balancing to ensure that a single user always connects to the same server.
If your system consists of only one machine—and may always consist of just one—don’t set this up. It solves the scalability problem, and is only worth it if that problem actually exists.
Thảo luận