ketama consistent hashing update

Russ Garrett russ at
Wed Aug 8 22:48:01 UTC 2007

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 


Russ Garrett Ltd.
russ at

More information about the memcached mailing list