ketama consistent hashing update

[Russell Garrett]

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.

For what it's worth, Ketama can do 1 million lookups in 5ms (including 
building the initial data structures) on a fairly ancient Xeon, so I'm 
not sure if there is a need for any further optimisation in this area.

Cheers,

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