ketama consistent hashing update

[Russ Garrett]

Brad Fitzpatrick wrote:
> Now, because of this one unlucky distribution where A only has 1 unit of
> space between it and B, you're not saved by the multiple points.
>
> Now item A's second point is at 2654435761+10, and item B is at
> 2654435761+11, etc...
>
> So A overall ends up owning n/2**32 of the space, and B ends up owning
> (2**32-n)/32 of the space.  Even though they have the same weight!
>
> The whole point of multiple points is to cancel out the unfairness you'd
> get if you just did one point.
>
> That said, I'm no expert in this, but your proposal doesn't seem like
> it'd work.
>   
Yeah, this is what we found too - the way Ketama does it is by hashing 
40 different string variations per server (using MD5, currently, which 
is 128bits), then splitting each hash value into four 32-bit values, and 
putting each of these on the continuum. This results in the 160 points 
per server which I mentioned earlier, and ends up with a relatively even 
distribution.

--

Russ Garrett
Last.fm Ltd.
russ at last.fm