Consistent hashing i

I have implemented consistent hashing in Python. The module is called hash_ring and you can get it right away. This post will explain the motivation behind the project and details. I think other languages such as Ruby can reuse my code since it's fairly simple :-)

To install the project, simply do:

sudo easy_install  hash_ring

Example of usage when mapping keys to memcached servers:

memcache_servers = ['192.168.0.246:11212',
                    '192.168.0.247:11212',
                    '192.168.0.249:11212']
ring = HashRing(memcache_servers)
server = ring.get_node('my_key')

The motivation behind hash_ring

Consistent hashing is really neat and can be used anywhere where you have a list of servers and you need to map some keys (objects) to these servers. An example is memcached or a distributed system.

A problem when you use memcached clients is that you map keys to servers in following way:

server=serverlist[hash(key)%len(serverlist)]

The major problem with this approach is that you'll invalidate all your caches when you add or remove memcache servers to the list - and this invalidation can be very expensive if you rely on caching.

This problem was solved 10 years ago by David Karger et al and they have published following articles that explain the idea of consistent caching in greater details:

• Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web

• Web Caching with Consistent Hashing

Another motivation is that I am currently looking into building a distributed hash map - and consistent hashing is essential in such a system. Here are a few widely used systems that use consistent hashing:

• Amazon Dynamo

• BitTorrent

How consistent hashing works

Consistent hashing is fairly simple (and genius way of distributing keys). It can be best explained by the idea that you have a ring that goes from 0 to some big number. Given a node A, you find a placement for A on the ring by running hash_function(A), the hash_function should generally mix the values well - good candidates for the hash function are MD5 or SHA1. Given a (key, value) pair you find the key's placement on the ring by running hash_function(key). A node holds all the keys that have a value lower than itself, but greater than the preceding node.

Tom White has written a great blog post about consistent hashing, take a look at it, it explains the idea in much greater detail.

Python implementation

I think my Python implementation is beatiful so I will share the full implementation. The code speaks for itself or something:

import md5
class HashRing(object):
    def __init__(self, nodes=None, replicas=3):
        """Manages a hash ring.
        `nodes` is a list of objects that have a proper __str__ representation.
        `replicas` indicates how many virtual points should be used pr. node,
        replicas are required to improve the distribution.
        """
        self.replicas = replicas
        self.ring = dict()
        self._sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)
    def add_node(self, node):
        """Adds a `node` to the hash ring (including a number of replicas).
        """
        for i in xrange(0, self.replicas):
            key = self.gen_key('%s:%s' % (node, i))
            self.ring[key] = node
            self._sorted_keys.append(key)
        self._sorted_keys.sort()
    def remove_node(self, node):
        """Removes `node` from the hash ring and its replicas.
        """
        for i in xrange(0, self.replicas):
            key = self.gen_key('%s:%s' % (node, i))
            del self.ring[key]
            self._sorted_keys.remove(key)
    def get_node(self, string_key):
        """Given a string key a corresponding node in the hash ring is returned.
        If the hash ring is empty, `None` is returned.
        """
        return self.get_node_pos(string_key)[0]
    def get_node_pos(self, string_key):
        """Given a string key a corresponding node in the hash ring is returned
        along with it's position in the ring.
        If the hash ring is empty, (`None`, `None`) is returned.
        """
        if not self.ring:
            return None, None
        key = self.gen_key(string_key)
        nodes = self._sorted_keys
        for i in xrange(0, len(nodes)):
            node = nodes[i]
            if key <= node:
                return self.ring[node], i
        return self.ring[nodes[0]], 0
    def get_nodes(self, string_key):
        """Given a string key it returns the nodes as a generator that can hold the key.
        The generator is never ending and iterates through the ring
        starting at the correct position.
        """
        if not self.ring:
            yield None, None
        node, pos = self.get_node_pos(string_key)
        for key in self._sorted_keys[pos:]:
            yield self.ring[key]
        while True:
            for key in self._sorted_keys:
                yield self.ring[key]
    def gen_key(self, key):
        """Given a string key it returns a long value,
        this long value represents a place on the hash ring.
        md5 is currently used because it mixes well.
        """
        m = md5.new()
        m.update(key)
        return long(m.hexdigest(), 16)