关于一致性哈希算法的简单讲解

川长思鸟来 2022-05-22 21:17 50阅读 0赞

传统的取模方式

例如10条数据，3个节点，如果按照取模的方式，那就是

node a: 0,3,6,9

node b: 1,4,7

node c: 2,5,8

当增加一个节点的时候，数据分布就变更为

node a:0,4,8

node b:1,5,9

node c: 2,6

node d: 3,7

总结：数据3,4,5,6,7,8,9在增加节点的时候，都需要做搬迁，成本太高

一致性哈希方式

最关键的区别就是，对节点和数据，都做一次哈希运算，然后比较节点和数据的哈希值，数据取和节点最相近的节点做为存放节点。这样就保证当节点增加或者减少的时候，影响的数据最少。

还是拿刚刚的例子，（用简单的字符串的ascii码做哈希key）：

十条数据，算出各自的哈希值

0：192

1：196

2：200

3：204

4：208

5：212

6：216

7：220

8：224

9：228

有三个节点，算出各自的哈希值

node a: 203

node g: 209

node z: 228

这个时候比较两者的哈希值，如果大于228，就归到前面的203，相当于整个哈希值就是一个环，对应的映射结果：

node a: 0,1,2

node g: 3,4

node z: 5,6,7,8,9

这个时候加入node n, 就可以算出node n的哈希值：

node n: 216

这个时候对应的数据就会做迁移：

node a: 0,1,2

node g: 3,4

node n: 5,6

node z: 7,8,9

这个时候只有5和6需要做迁移

另外，这个时候如果只算出三个哈希值，那再跟数据的哈希值比较的时候，很容易分得不均衡，因此就引入了虚拟节点的概念，通过把三个节点加上ID后缀等方式，每个节点算出n个哈希值，均匀的放在哈希环上，这样对于数据算出的哈希值，能够比较散列的分布（详见下面代码中的replica）

通过这种算法做数据分布，在增减节点的时候，可以大大减少数据的迁移规模。

下面转载的哈希代码，已经将gen\_key改成上述描述的用字符串ascii相加的方式，便于测试验证。

\[python\]  [view plain][]   [copy][view plain]

1.  **import** md5  
2.  **class** HashRing(object):  
3.      **def** \_\_init\_\_(self, nodes=None, replicas=3):  
4.          """Manages a hash ring. 
5.          \`nodes\` is a list of objects that have a proper \_\_str\_\_ representation. 
6.          \`replicas\` indicates how many virtual points should be used pr. node, 
7.          replicas are required to improve the distribution. 
8.          """  
9.          self.replicas = replicas  
10.         self.ring = dict()  
11.         self.\_sorted\_keys = \[\]  
12.         **if** nodes:  
13.             **for** node **in** nodes:  
14.                 self.add\_node(node)  
15.     **def** add\_node(self, node):  
16.         """Adds a \`node\` to the hash ring (including a number of replicas). 
17.         """  
18.         **for** i **in** xrange(0, self.replicas):  
19.             key = self.gen\_key('%s:%s' % (node, i))  
20.             **print** "node %s-%s key is %ld" % (node, i, key)  
21.             self.ring\[key\] = node  
22.             self.\_sorted\_keys.append(key)  
23.         self.\_sorted\_keys.sort()  
24.     **def** remove\_node(self, node):  
25.         """Removes \`node\` from the hash ring and its replicas. 
26.         """  
27.         **for** i **in** xrange(0, self.replicas):  
28.             key = self.gen\_key('%s:%s' % (node, i))  
29.             **del** self.ring\[key\]  
30.             self.\_sorted\_keys.remove(key)  
31.     **def** get\_node(self, string\_key):  
32.         """Given a string key a corresponding node in the hash ring is returned. 
33.         If the hash ring is empty, \`None\` is returned. 
34.         """  
35.         **return** self.get\_node\_pos(string\_key)\[0\]  
36.     **def** get\_node\_pos(self, string\_key):  
37.         """Given a string key a corresponding node in the hash ring is returned 
38.         along with it's position in the ring. 
39.         If the hash ring is empty, (\`None\`, \`None\`) is returned. 
40.         """  
41.         **if** **not** self.ring:  
42.             **return** None, None  
43.         key = self.gen\_key(string\_key)  
44.         nodes = self.\_sorted\_keys  
45.         **for** i **in** xrange(0, len(nodes)):  
46.             node = nodes\[i\]  
47.             **if** key <= node:  
48.                 **print** "string\_key %s key %ld" % (string\_key, key)   
49.                 **print** "get node %s-%d " % (self.ring\[node\], i)  
50.                 **return** self.ring\[node\], i  
51.         **return** self.ring\[nodes\[0\]\], 0  
52.     **def** print\_ring(self):  
53.         **if** **not** self.ring:  
54.             **return** None, None  
55.         nodes = self.\_sorted\_keys  
56.         **for** i **in** xrange(0, len(nodes)):  
57.             node = nodes\[i\]  
58.             **print** "ring slot %d is node %s, hash vale is %s" % (i, self.ring\[node\], node)  
59.     **def** get\_nodes(self, string\_key):  
60.         """Given a string key it returns the nodes as a generator that can hold the key. 
61.         The generator is never ending and iterates through the ring 
62.         starting at the correct position. 
63.         """  
64.         **if** **not** self.ring:  
65.             **yield** None, None  
66.         node, pos = self.get\_node\_pos(string\_key)  
67.         **for** key **in** self.\_sorted\_keys\[pos:\]:  
68.             **yield** self.ring\[key\]  
69.         **while** True:  
70.             **for** key **in** self.\_sorted\_keys:  
71.                 **yield** self.ring\[key\]  
72.     **def** gen\_key(self, key):  
73.         """Given a string key it returns a long value, 
74.         this long value represents a place on the hash ring. 
75.         md5 is currently used because it mixes well. 
76.         """  
77.         m = md5.new()  
78.         m.update(key)  
79.         **return** long(m.hexdigest(), 16)  
80.         """ 
81.         hash = 0 
82.         for i in xrange(0, len(key)): 
83.             hash += ord(key\[i\])  
84.         return hash 
85.         """  
86.   
87.   
88. memcache\_servers = \['a',  
89.                    'g',  
90.                     'z'\]  
91. ring = HashRing(memcache\_servers,1)  
92. ring.print\_ring()  
93. server = ring.get\_node('0000')  
94. server = ring.get\_node('1111')  
95. server = ring.get\_node('2222')  
96. server = ring.get\_node('3333')  
97. server = ring.get\_node('4444')  
98. server = ring.get\_node('5555')  
99. server = ring.get\_node('6666')  
100. server = ring.get\_node('7777')  
101. server = ring.get\_node('8888')  
102. server = ring.get\_node('9999')  
103.   
104. **print** '----------------------------------------------------------'  
105.   
106. memcache\_servers = \['a',  
107.                    'g',  
108.                    'n',  
109.                     'z'\]  
110. ring = HashRing(memcache\_servers,1)  
111. ring.print\_ring()  
112. server = ring.get\_node('0000')  
113. server = ring.get\_node('1111')  
114. server = ring.get\_node('2222')  
115. server = ring.get\_node('3333')  
116. server = ring.get\_node('4444')  
117. server = ring.get\_node('5555')  
118. server = ring.get\_node('6666')  
119. server = ring.get\_node('7777')  
120. server = ring.get\_node('8888')  
121. server = ring.get\_node('9999')

[view plain]: https://blog.csdn.net/gerryke/article/details/53939212#