ketama - a consistent hashing algo for memcache clients

[Steven Grimm]

Dustin Sallings wrote:
>     It might be interesting, in this case, to send a delete for a 
> given key to the next node in the continuum whenever performing a 
> mutation operation on the node responsible for a key.  Perhaps this 
> would be appropriate whenever a node is considered ``new.''

That approach won't work if servers are typically added and removed in 
batches, which is certainly the case for us -- we hardly ever add just 
one server at a time, and when we administratively remove servers it's 
often due to a network change that forces us to remove a bunch of them 
at once. On the other hand, I think I can count on one hand the number 
of times we've needed to do that, so maybe we're not the best test case 
for this particular failure mode. More often we replace broken servers, 
but it looks like Ketama will handle that just fine without relocating 
any keys as long as we put the replacement machine in the same position 
in the list as the one it's replacing.

-Steve