Consistent Hashing

gistfile1.py

def _hashKey(key):
    return long(md5(key).hexdigest(), 16)

def _nodeKey(node, replica):
    return _hashKey('%s:%d' % (str(node), replica))

class ConsistentRing(object):
    """
    Consistent Hashing:

        ring = ConsistentRing()
        ring.addNode(('192.168.1.20', 20550))
        ring.addNode(('192.168.1.20', 20551))
        ring.addNode(('192.168.1.21', 20550))
        ring.addNode(('192.168.1.22', 20550))

        node = ring.getNode('key1') -> ('192.168.1.20', 20550)
        node = ring.getNode('key2') -> ('192.168.1.22', 20550)
        node = ring.getNode('key3') -> ('192.168.1.20', 20551)

        ring.removeNode(('192.168.1.20', 20551))
        node = ring.getNode('key1') -> ('192.168.1.20', 20550)
        node = ring.getNode('key2') -> ('192.168.1.22', 20550)
    """
    def __init__(self, replicas=3):
        self.replicas = replicas

        self._ring = {}
        self._keys = []

    def addNode(self, node):
        for replica in xrange(self.replicas):
            key = _nodeKey(node, replica)
            self._ring[key] = node
            self._keys.append(key)
        self._keys.sort()

    def removeNode(self, node):
        for replica in xrange(self.replicas):
            key = _nodeKey(node, replica)
            del self._ring[key]
            self._keys.remove(key)

    def getNode(self, key):
        return next(iter(self.getNodes(key)))

    def getNodes(self, key):
        key = _hashKey(key)

        index = 0
        for i, node in enumerate(self._keys):
            if key <= node:
                index = i
                break

        visited = set()
        for i in xrange(index, len(self._keys)):
            node = self._ring[self._keys[i]]
            if node not in visited:
                yield node
                visited.add(node)

        for i in xrange(index):
            node = self._ring[self._keys[i]]
            if node not in visited:
                yield node
                visited.add(node)