一致性hash 之 python实现

wocaosinima

http://amix.dk/blog/post/19367　　
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
if key