Ketama: Consistent Hashing
libketama is a consistent hashing library written in C. You supply a list of servers and ketama will map keys to servers in a consistent way, even after adding or removing servers from the list.
It is a generic library, but was initially written to replace how our memcached
clients mapped keys to servers.
Previously, clients mapped keys->servers like this:
server = serverlist[hash(key)%serverlist.length];This meant that whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache.
Ketama solves this problem in the following way:
- Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
- Hash each server string to several (100-200) unsigned ints
- Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)
- Each number links to the server it was hashed from, so servers appear at several points on the continuum, by each of the numbers they hashed to.
- To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum. The server linked to that number is the correct server for that key.
- If you hash your key to a value near 2^32 and there are no points on the continuum greater than your hash, return the first server in the continuum.
Implementation details
The server list is stored in a file, whenever the file mtime is changed, libketama will rebuild the continuum data structure. This structure is stored in shared memory and used every time you lookup the mapping for a key. You can have all your machines using memcache pull down the latest copy of the file periodically (if it changed) and libketama will rebuild the continuum automatically.
See the README and test scripts for examples and additional information.
Source Code
Latest code is in our public svn repo here:
svn://svn.audioscrobbler.net/misc/ketama
libketama is BSD licensed, the php extension uses the php license, and the java code is TODO(same as the official java client).
References
Consistent Hashing and Random Trees:
Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
Web Caching with Consistent Hashing
