1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132

-*- coding: UTF-8 -*- ''' FileName: consistenthashdistributed1.sh Description: 分布式系统：一致性hash算法的应用 Simple Usage: python consistenthashdistributed1.py numbers of replicate Reference: http://www.firefoxbug.com/index.php/archives/2791/ (c) 2018.02.17 vfhky https://typecodes.com/python/consistenthashdistributed1.html ''' import sys import 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.ringkey = 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.ringkey 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 = nodesi if key <= node: return self.ringnode, i # 对于key>node节点key的，全部落在第1个key对应的节点(192.168.1.4)上，这样就形成了1个闭环。 print("%s:%s string_key=%s key=%s node=%s self.ring[nodes0]=%s.\n" %(__file__, sys._getframe().f_lineno, string_key, key, node, self.ring[nodes0])) return self.ring[nodes0], 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: databases = [] hr = HashRing(SERVERS,replicas) for w in CONTENT.split(): databasehr.get_node(w).append(w) # 打印所有的节点下面的数据 for node in database: print("%s=%s.\n" %(node, databasenode)) if __name__ == '__main__': '''docstring''' replicas = 3 if len(sys.argv) > 1: replicas = long(sys.argv1) if( replicas < 3 or replicas > 100000 ): print( "Rreplicas should lower than 100000." ) sys.exit() consistent_hash(replicas)