ketama - a consistent hashing algo for memcache clients

Dustin Sallings dustin at
Wed Apr 11 07:54:18 UTC 2007

On Apr 10, 2007, at 23:13, Steven Grimm wrote:

> Only if you remove a server from the list when it's down. If you  
> leave it in there and live with the cache misses (i.e., the same  
> approach you take when you don't rehash keys in the non-consistent- 
> hashing memcached client) then that's not an issue; you'll only  
> move keys around when you administratively add / remove servers.  
> And if you do a flush_all on a machine before you add it, there  
> will be no stale data to worry about.

	The problem in the consistent-hashing case is that an added node  
effectively shadows a node that was previously responsible for a  
given key.  The new node will be queried for that key, but the  
previous node will still contain it.  Removing the new node makes the  
previous node be responsible for the key.

	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.''

	Alternatively, a cache miss on a node could attempt a get+delete on  
the next node in a continuum.

Dustin Sallings

More information about the memcached mailing list