ketama consistent hashing update

Russell Garrett russ at
Wed Aug 8 13:13:05 UTC 2007

Steven Grimm wrote:
> I'm much more in favor of making "n" large enough that it's reasonable 
> to say something like, "Oops, that bucket is taken already; overwrite 
> it with me if the address of the node it currently points to is 
> numerically less than mine, else don't insert myself here." Then you 
> will deterministically end up with exactly the same search tree no 
> matter what order the nodes are inserted. If you are inserting each 
> node 10 times in a tree and your search space is a full 32 bits, the 
> occasional node that's inserted 9 times instead is going to be 
> basically irrelevant to the health of the system. Not perfectly 
> balanced, sure, but there will almost never be any collisions to begin 
> with and it isn't worth optimizing such a rare edge case.
Yeah. We don't care about this case at the moment - our "n" is 2^32, and 
the number of times we insert each server is 160 (which is a fairly 
arbitrary number we found empirically). So the chances of a collision 
are about 1 in 250,000 for us at the moment, which is acceptable. This 
is probably an improvement that needs to be made, though.


Russ Garrett Ltd.
russ at

More information about the memcached mailing list