ketama consistent hashing update

[Alex Stapleton]

Russell Garrett wrote:
> Steven Grimm wrote:
>
>> Brad Fitzpatrick wrote:
>>>    -- do we pre-compute 'n' points like my perl client?
>>>
>>>       (note that this can be done lazily too, only evaluating each of
>>>        1024 positions the first time they're accessed)
>>>   
>> I'd like to request that we standardize on a much bigger number than 
>> 1024. If you have a ton of memcached instances, "n" doesn't have to 
>> be very high before a space of 1024 values starts to get pretty 
>> crowded, if not completely full.
> I don't think Brad is talking about a continuum of 1024 entries - 
> Ketama uses 0 to MAX_INT - he's talking about pre-computing a lookup 
> table of 1024 entries in order to find the target point quicker, 
> instead of doing a binary search.
It does set a hard limit on your maximum number of unique nodes though. 
I agree that a binary search of the continuum does seem like a pretty 
acceptable method of doing the lookups. 5,000,000 lookups a second is 
several times enough to saturate a GigE network in actual responses to 
those keys :)