ketama consistent hashing update
alexs at advfn.com
Wed Aug 8 11:52:06 UTC 2007
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 :)
More information about the memcached