求锤得锤，你要的一致性 hash 来了！ | 附代码
前言
最近总有人问我一致性hash的事情，求锤得锤，我们今天就来聊聊看。前两篇我们分别介绍了两类哈希分片的方法:hash取模和虚拟桶。
hash取模法导致架构缺乏灵活性，需要扩、缩容一倍的节点才能保证50%的映射关系不变，否则查询命中率会更低，当有一台节点异常时，简直是灾难。
虚拟桶的分片方法在hash取模的基础上做了优化，符合通用的3层路由分片模型，此外将分片数量固定，避免了取模敏感度高的问题，节点变动后每台老节点会有部分分片迁移到新节点上。
虽然虚拟桶比hash取模好上很多，但总归是有影响比较多节点的，那有没有影响更小的方法呢？本篇我们就开始讲解一致性hash的内容。
一致性hash原理实现
1. 构建空hash环
-
我们一步一步来，之前我们尝试过对节点取模，尝试过分片数量取模，而在一致性hash中是对 2^32取模的。在取模的时候我们一般选取正数，因此取模的结果必然是在[0,2^32-1]这个区间内的。较真儿一下，为什么是2的32次方呢?经过一番资料的翻找，通常解释为“java中int的最大值是2^31-1，最小值是-2^31,2^32刚好是无符号整形的最大值”，这个答案也虽然也解释的通，但是为啥不是short 呢？它招谁惹谁了。我猜测有可能算法的创始者觉得short的最大值32767（2^16）过小。那为啥不是其他较大的数值呢？有知道原因的小伙伴可以文章下面留言～ -
这里我们把这个范围想象成一个圆环，如下所示，正中间为为0，数值以顺时针的方向，依次增大，直到最大值2^32-1，我们称这样的环为hash环。
2. 构建hash环上的节点拓扑
-
一致性hash与上图中的hash环到底有什么关系呢？
hash（节点的IP地址或主机名） % 2^32
-
如上述相同，其取模的结果必然是在[0,2^32-1]这个区间中，也意味着，必然会落到hash环中。我们对A、B、C三个节点，均执行相同的操作。此时会得到如下所示的结果，每个节点都会根据hash取模后的数值大小，在hash环上进行分布。
3. 将key映射到hash环
-
我们将key使用和上述同样的方法进行处理，通过哈希、取模2^32，并映射到hash环上。 -
在一致性hash的逻辑中，每个key会顺时针寻找的最近的一个节点，作为其对应的节点，如下图所示，我们拿3个key进行举例。
4. 模拟节点下线
5. 模拟节点上线
6.模型分析
代码实现
#!/bin/bash/env python# -*- coding:utf8 -*-# auorth:lzjimport hashlibimport sysreload(sys)sys.setdefaultencoding('utf-8')class ConsistentHash(object):def __init__(self, nodes=None):'''a. 初始化nodes即节点列表b. 字典ring 为我们文中讲述的节点hash取模数值和节点的映射关系c. 列表sortedKeys为模拟顺时针数值从0到2^32依次增大的关系，可以想象成环d. 然后将节点增加到集群中'''self.nodes = nodesself.ring = {}self.sortedKeys = []self.addNodes(nodes)#nodes是一个节点的列表，遍历列表逐个添加到hash环中def addNodes(self, nodes):if nodes:for node in nodes:# 和第一篇hash取模相同，我们使用sha1算法进行hash处理，然后强转intnodeHashResult = hashlib.sha1(node).hexdigest()intNodeHashResult = int(nodeHashResult, 16)modIntNodeHashResult = intNodeHashResult % (2 ** 32)self.ring[modIntNodeHashResult] = nodeself.sortedKeys.append(modIntNodeHashResult)self.sortedKeys.sort()def removeNodes(self, nodes):'''和增加节点相同，此时我们需要将节点hash取模数值和节点的映射关系进行更新删除，并在环上将清理该节点的信息'''if nodes:for node in nodes:nodeHashResult = hashlib.sha1(node).hexdigest()intNodeHashResult = int(nodeHashResult, 16)modIntNodeHashResult = intNodeHashResult % (2 ** 32)self.ring.pop(modIntNodeHashResult)self.sortedKeys.remove(modIntNodeHashResult)def getNode(self, modKeyHashResult):'''依次遍历 sortedKeys中的所有node，由于是有序的，依次判断，直到node的数值大于key的数值，那么此时key就是属于对应的节点'''position = 0for _modIntNodeHashResult in self.sortedKeys:position += 1if modKeyHashResult < _modIntNodeHashResult:return self.ring[_modIntNodeHashResult]else:continue'''遍历了全部节点都对比失败的话，说明是在hash环上0开始逆时针第一个节点到顺时针第一个节点之间，因此将key对应到第一个节点'''if position == len(self.sortedKeys):return self.ring[self.sortedKeys[0]]def allocateKey(self,number):keyNodeMap = []# 模拟若干个key，同样的将key进行hash取模for i in range(number):keyName = 'testKey' + str(i)keyHashResult = hashlib.sha1(keyName).hexdigest()intKeyHashResult = int(keyHashResult, 16)modKeyHashResult = intKeyHashResult % (2 ** 32)# 对key进行寻址，即确定key 是属于哪一个节点，哪一个分片_node = self.getNode(modKeyHashResult)print '%s is allocateKey to %s' %(keyName,_node)keyNodeMap.append(keyName + '_' + _node)return keyNodeMap#模拟集群有4个节点iniServers = ['192.168.1.1','192.168.1.2','192.168.1.3','192.168.1.4',]print '初始化一个hash环，构建hash环上的节点拓扑'h = ConsistentHash(iniServers)print h.ringprint h.sortedKeysprint '构造若干个key，将key映射到hash环'number = 40oldMap = h.allocateKey(40)print '尝试上线一个新节点,我们看下key是否会正常迁移到新节点'newNode = ['192.168.1.5']h.addNodes(newNode)print h.ringprint h.sortedKeysaddNodeMap = h.allocateKey(40)print '尝试下线一个节点，我们再观察下'removeNode = ['192.168.1.1']h.removeNodes(removeNode)print h.ringprint h.sortedKeysremoveNodeMap = h.allocateKey(40)究竟代码完成度高不高呢？我们在从运行结果的角度反向测试下。如下所示初始化一个hash环，构建hash环上的节点拓扑环上的节点：{560662416L: '192.168.1.1', 216828752L: '192.168.1.3', 2895068098L: '192.168.1.2', 1580996791L: '192.168.1.4'}节点hash值排序：[216828752L, 560662416L, 1580996791L, 2895068098L]构造若干个key，将key映射到hash环testKey0 is allocateKey to 192.168.1.4testKey1 is allocateKey to 192.168.1.1testKey2 is allocateKey to 192.168.1.4testKey3 is allocateKey to 192.168.1.4testKey4 is allocateKey to 192.168.1.3testKey5 is allocateKey to 192.168.1.3testKey6 is allocateKey to 192.168.1.2testKey7 is allocateKey to 192.168.1.2testKey8 is allocateKey to 192.168.1.3testKey9 is allocateKey to 192.168.1.2testKey10 is allocateKey to 192.168.1.4testKey11 is allocateKey to 192.168.1.1testKey12 is allocateKey to 192.168.1.3testKey13 is allocateKey to 192.168.1.4testKey14 is allocateKey to 192.168.1.3testKey15 is allocateKey to 192.168.1.2testKey16 is allocateKey to 192.168.1.4testKey17 is allocateKey to 192.168.1.4testKey18 is allocateKey to 192.168.1.1testKey19 is allocateKey to 192.168.1.1testKey20 is allocateKey to 192.168.1.3testKey21 is allocateKey to 192.168.1.2testKey22 is allocateKey to 192.168.1.4testKey23 is allocateKey to 192.168.1.2testKey24 is allocateKey to 192.168.1.2testKey25 is allocateKey to 192.168.1.3testKey26 is allocateKey to 192.168.1.2testKey27 is allocateKey to 192.168.1.3testKey28 is allocateKey to 192.168.1.2testKey29 is allocateKey to 192.168.1.2testKey30 is allocateKey to 192.168.1.2testKey31 is allocateKey to 192.168.1.1testKey32 is allocateKey to 192.168.1.3testKey33 is allocateKey to 192.168.1.2testKey34 is allocateKey to 192.168.1.2testKey35 is allocateKey to 192.168.1.3testKey36 is allocateKey to 192.168.1.2testKey37 is allocateKey to 192.168.1.2testKey38 is allocateKey to 192.168.1.2testKey39 is allocateKey to 192.168.1.2尝试上线一个新节点,我们看下key是否会正常迁移到新节点[注意标红处]环上的节点：{560662416L: '192.168.1.1', 216828752L: '192.168.1.3', 2895068098L: '192.168.1.2', 1785826697L: '192.168.1.5', 1580996791L: '192.168.1.4'}节点hash值排序：[216828752L, 560662416L, 1580996791L, 1785826697L, 2895068098L]testKey0 is allocateKey to 192.168.1.4testKey1 is allocateKey to 192.168.1.1testKey2 is allocateKey to 192.168.1.4testKey3 is allocateKey to 192.168.1.4testKey4 is allocateKey to 192.168.1.3testKey5 is allocateKey to 192.168.1.3testKey6 is allocateKey to 192.168.1.2testKey7 is allocateKey to 192.168.1.2testKey8 is allocateKey to 192.168.1.3testKey9 is allocateKey to 192.168.1.2testKey10 is allocateKey to 192.168.1.4testKey11 is allocateKey to 192.168.1.1testKey12 is allocateKey to 192.168.1.3testKey13 is allocateKey to 192.168.1.4testKey14 is allocateKey to 192.168.1.3testKey15 is allocateKey to 192.168.1.5testKey16 is allocateKey to 192.168.1.4testKey17 is allocateKey to 192.168.1.4testKey18 is allocateKey to 192.168.1.1testKey19 is allocateKey to 192.168.1.1testKey20 is allocateKey to 192.168.1.3testKey21 is allocateKey to 192.168.1.2testKey22 is allocateKey to 192.168.1.4testKey23 is allocateKey to 192.168.1.5testKey24 is allocateKey to 192.168.1.2testKey25 is allocateKey to 192.168.1.3testKey26 is allocateKey to 192.168.1.2testKey27 is allocateKey to 192.168.1.3testKey28 is allocateKey to 192.168.1.2testKey29 is allocateKey to 192.168.1.2testKey30 is allocateKey to 192.168.1.2testKey31 is allocateKey to 192.168.1.1testKey32 is allocateKey to 192.168.1.3testKey33 is allocateKey to 192.168.1.2testKey34 is allocateKey to 192.168.1.2testKey35 is allocateKey to 192.168.1.3testKey36 is allocateKey to 192.168.1.5testKey37 is allocateKey to 192.168.1.2testKey38 is allocateKey to 192.168.1.2testKey39 is allocateKey to 192.168.1.2尝试下线一个节点，我们再观察下[注意标红处]环上的节点：{216828752L: '192.168.1.3', 2895068098L: '192.168.1.2', 1785826697L: '192.168.1.5', 1580996791L: '192.168.1.4'}节点hash值排序：[216828752L, 1580996791L, 1785826697L, 2895068098L]testKey0 is allocateKey to 192.168.1.4testKey1 is allocateKey to 192.168.1.4testKey2 is allocateKey to 192.168.1.4testKey3 is allocateKey to 192.168.1.4testKey4 is allocateKey to 192.168.1.3testKey5 is allocateKey to 192.168.1.3testKey6 is allocateKey to 192.168.1.2testKey7 is allocateKey to 192.168.1.2testKey8 is allocateKey to 192.168.1.3testKey9 is allocateKey to 192.168.1.2testKey10 is allocateKey to 192.168.1.4testKey11 is allocateKey to 192.168.1.4testKey12 is allocateKey to 192.168.1.3testKey13 is allocateKey to 192.168.1.4testKey14 is allocateKey to 192.168.1.3testKey15 is allocateKey to 192.168.1.5testKey16 is allocateKey to 192.168.1.4testKey17 is allocateKey to 192.168.1.4testKey18 is allocateKey to 192.168.1.4testKey19 is allocateKey to 192.168.1.4testKey20 is allocateKey to 192.168.1.3testKey21 is allocateKey to 192.168.1.2testKey22 is allocateKey to 192.168.1.4testKey23 is allocateKey to 192.168.1.5testKey24 is allocateKey to 192.168.1.2testKey25 is allocateKey to 192.168.1.3testKey26 is allocateKey to 192.168.1.2testKey27 is allocateKey to 192.168.1.3testKey28 is allocateKey to 192.168.1.2testKey29 is allocateKey to 192.168.1.2testKey30 is allocateKey to 192.168.1.2testKey31 is allocateKey to 192.168.1.4testKey32 is allocateKey to 192.168.1.3testKey33 is allocateKey to 192.168.1.2testKey34 is allocateKey to 192.168.1.2testKey35 is allocateKey to 192.168.1.3testKey36 is allocateKey to 192.168.1.5testKey37 is allocateKey to 192.168.1.2testKey38 is allocateKey to 192.168.1.2testKey39 is allocateKey to 192.168.1.2
更多精彩推荐
点分享 点点赞 点在看