Technique
Consistent hashing is based on mapping each object to a point on the edge of a circle (or equivalently, mapping each object to a real angle). The system maps each available machine (or other storage bucket) to many pseudo-randomly distributed points on the edge of the same circle.
To find where an object should be placed, the system finds the location of that object's key on the edge of the circle; then walks around the circle until falling into the first bucket it encounters (or equivalently, the first available bucket with a higher angle). The result is that each bucket contains all the resources located between its point and the next bucket point.
If a bucket becomes unavailable (for example because the computer it resides on is not reachable), then the angles it maps to will be removed. Requests for resources that would have mapped to each of those points now map to the next highest point. Since each bucket is associated with many pseudo-randomly distributed points, the resources that were held by that bucket will now map to many different buckets. The items that mapped to the lost bucket must be redistributed among the remaining ones, but values mapping to other buckets will still do so and do not need to be moved.
A similar process occurs when a bucket is added. By adding a bucket point, we make any resources between that and the next smaller angle map to the new bucket. These resources will no longer be associated with the previous bucket, and any value previously stored there will not be found by the selection method described above.
The portion of the keys associated with each bucket can be altered by altering the number of angles that bucket maps to.
Read more about this topic: Consistent Hashing
Famous quotes containing the word technique:
“Irony in writing is a technique for increasing reader self- approval.”
—Jessamyn West (1907–1984)
“The audience is the most revered member of the theater. Without an audience there is no theater. Every technique learned by the actor, every curtain, every flat on the stage, every careful analysis by the director, every coordinated scene, is for the enjoyment of the audience. They are our guests, our evaluators, and the last spoke in the wheel which can then begin to roll. They make the performance meaningful.”
—Viola Spolin (b. 1911)
“In love as in art, good technique helps.”
—Mason Cooley (b. 1927)