ketama consistent hashing update

[Russell Garrett]

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
Last.fm Ltd.
russ at last.fm