头图 | 视觉中国

序言

最近总有人问我同等性hash的事情，求锤得锤，我们本日就来聊聊看。
前两篇我们分别先容了两类哈希分片的方法:hash取模和虚拟桶。

hash取模法导致架构缺少灵巧性，须要扩、缩容一倍的节点才能担保50%的映射关系不变，否则查询命中率会更低，当有一台节点非常时，切实其实是灾害。

php哈希取模求锤得锤你要的一致性 hash 来了 附代码 Webpack

虚拟桶的分片方法在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环。

图1

2. 构建hash环上的节点拓扑

同等性hash与上图中的hash环到底有什么关系呢？

这里我们通过实际的例子来讲解。
假设这里我们有三个节点，A、B、C。
每个节点有自己的ip地址和主机名，(一样平常同一个VPC下或者集群中不会存在重复的ip和主机名），首先将节点的ip地址或者主机名进行hash处理，然后对2^32次方取模。

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进行举例。

此时小伙伴有疑问了，这看着跟之前讲的通用模型并不符合啊，是不是代表着同等性hash已经分开通用的路由分片模型了呢?

实际上，同等性hash也是符合通用路由模型的，我们之前聊到会有数据-分片-节点的分层，那么分片在哪呢？我们回看一下2中的hash环，通过3个物理节点将环分为3区间，即节点A-节点B、节点B-节点C、节点C-节点A。
这里我们可以把每一个区间都当作一个分片，比如key-01，是落在节点C-节点A的分片上，因此分片归属于节点A。
这样看依然是符合咱们的通用路由分片模型的。

4. 仿照节点下线

接下来我们就开始仿照节点下线（机器宕机或者节点缩容），如下图所示，当节点C下线后，全体hash环上只存在节点A和节点B，意味着只存在两个分片：节点A-节点B，节点B-节点A。
那么原来在节点C（节点B-节点C这一分片）上的key03，按照上面的逻辑，顺时针探求下一个节点，这时找到了节点A，即节点B-节点A的分片上。

此时创造，当一个节点下线后，只影响着hash环上当前下线节点到逆时针方向第一个节点之间的所有key，这些key须要重新分布在新节点上。
而hash环上其他分片上的所有key是不受影响的。

5. 仿照节点上线

同样的，在上面仿照节点下线后，我们开始仿照节点上线（扩容节点、宕机节点规复），此时有个新的节点D加入到hash环上，并且取模后的数值，在节点B和节点C之间，将原来节点B-节点C的一个分片，切分为节点B-节点D和节点D到节点C2个分片。

与节点下线类似，此时key03会顺时针找到找到第一个节点，由过去的C节点上重分布到节点D上。
影响的范围也仅限在上线的节点到hash环上逆时针方向的第一个节点之间的所有key。

6.模型剖析

上述便是同等性hash的核心事理和实现，我们此时再转头看，针对数据重映射程度高的问题，同等性hash比较hash取模来说，是有很大提升的。

那究竟为什么同等性hash在节点变动时会有明显的提升呢？

我们还是按照我们的老方法，回到通用的路由分片模型上，当一个节点变革的时候，同等性hash实际上只会影响一个分片、一个节点上的数据，并不会像虚拟桶以及hash取模一样，会影响多个分片和多个节点。
因此同等性hash在容错性和扩展性上是比较上风的。

代码实现

理论太干，上代码。
（下面只涉及根本代码，并对主要部分作出注释）

#!/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 = nodes self.ring = {} self.sortedKeys = self.addNodes(nodes) #nodes是一个节点的列表，遍历列表逐个添加到hash环中 def addNodes(self, nodes): if nodes: for node in nodes: # 和第一篇hash取模相同，我们利用sha1算法进行hash处理，然后强转int nodeHashResult = hashlib.sha1(node).hexdigest intNodeHashResult = int(nodeHashResult, 16) modIntNodeHashResult = intNodeHashResult % (2 32) self.ring[modIntNodeHashResult] = node self.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 = 0 for _modIntNodeHashResult in self.sortedKeys: position += 1 if 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