分布式一致性 Hash 算法

# -*- coding: UTF-8 -*- import sysimport hashlib CONTENT = """Consistent hashing is a special kind of hashing such that when a hash table is resized and consistent hashing is used, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped.""" # 所有机器列表SERVERS = [    "192.168.1.1",    "192.168.2.2",    "192.168.3.3",    "192.168.4.4"]  class HashRing(object):    """Constructs.    """    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 range(0, self.replicas):            key = self.gen_key('%s:%s' % (node, i))            self.ring[key] = node            # print("key=[%s]=[%s]." %(key, node))            self._sorted_keys.append(key)         self._sorted_keys.sort()        #print("%s" %(self._sorted_keys))     def remove_node(self, node):        """Removes `node` from the hash ring and its replicas.        """        for i in range(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        nodes_num = len(nodes)        for i in range(0, nodes_num):            node = nodes[i]            if key <= node:                return self.ring[node], i         # 对于key>node节点key的，全部落在第1个key对应的节点(192.168.1.4)上，这样就形成了1个闭环。        print("[%s:%s] string_key=[%s] key=[%s] node=[%s] self.ring[nodes[0]]=[%s].\n" %(__file__, sys._getframe().f_lineno, string_key, key, node, self.ring[nodes[0]]))        return self.ring[nodes[0]], 0     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 = hashlib.md5()        m.update(key.encode('utf-8'))        return m.hexdigest()  def consistent_hash(replicas):    '''docstring'''    # 模拟初始化每天机器的db    database = {}    for s in SERVERS:        database[s] = []     hr = HashRing(SERVERS,replicas)     for w in CONTENT.split():        database[hr.get_node(w)].append(w)     # 打印所有的节点下面的数据    for node in database:        print("[%s]=[%s].\n" %(node, database[node]))  if __name__ == '__main__':    '''docstring'''    replicas = 3     if len(sys.argv) > 1:        replicas = long(sys.argv[1])     if( replicas < 3 or replicas > 100000 ):        print( "Rreplicas should lower than 100000." )        sys.exit()     consistent_hash(replicas)