从实践中检验“真理”
通过上一篇《大数据基础-求锤得锤，你要的一致性hash来了(上）[附代码]》的讲解，我们已经掌握了一致性hash的基本原理，其路由分片策略在类p2p模型架构中是非常典型的(之前提到的redis cluster也是p2p协议的一种实现)，在节点宕机时的影响很小，只影响到一个分片。只看原理的话确实也就这么多了，那么其实际效果究竟是否和原理中完全一致？是否还存在一些问题呢？我们来逐一验证下。
写这个系列文章以后，从后台看到收藏次数很多，我本身也是很开心，说明很多小伙伴还是有所收获的，也希望能在收藏之余，来个三连哈!!!
-
节点扩容测试
集群4个节点[192.168.1.1~192.168.1.4]，扩容第5个节点[192.168.1.5]时的key迁移信息，查看待迁移key的信息。
-
print
'上线一个节点，需要迁移节点个数:{}'.format(len(list(
set(addNodeMap).difference(
set(oldMap)))))
-
print
'需要迁移的key-node信息:',list(
set(addNodeMap).difference(
set(oldMap)))
扩容结果：需要迁移部分key 到新扩容的节点192.168.1.5上，这里总计有3个key
-
上线一个节点，需要迁移节点个数
:3
-
需要迁移的
key-node信息:
['testKey15_192.168.1.5', 'testKey36_192.168.1.5', 'testKey23_192.168.1.5']
-
缩容节点测试
此时集群共有5个节点[192.168.1.1~192.168.1.5]，再操作缩容第5个节点[192.168.1.5]，同样观察其变化。
-
print
'需要迁移节点个数:{}'.format(len(list(
set(removeNodeMap).difference(
set(addNodeMap)))))
-
print
'等待迁移的key信息:{}'.format(list(
set(removeNodeMap).difference(
set(addNodeMap))))
下线结果：需要迁移部分key 到老节点192.168.1.2上，这里依旧还是那3个key。
-
下线节点
['192.168.1.5']，需要迁移节点个数
:3
-
等待迁移的
key信息:
['testKey23_192.168.1.2', 'testKey36_192.168.1.2', 'testKey15_192.168.1.2']
-
结论
通过模拟上线、下线节点的操作，我们发现确实是只影响其中3个key的分配位置，这3个key在hash环上位于节点192.168.1.2和节点192.168.1.5之间的区域内，无论上线还是下线节点，都不会影响其他分片的内容，这一点是是符合咱们之前的理论的。
从“真理”中发现问题
-
发现问题
我们继续测试，上面测试模拟下线的是192.168.1.5节点。此时保持集群在5个节点的状态下，逐个对每个节点进行测试下线，会发现什么呢？话不多说，直接开测！先编写下测试代码：
-
nodeist = [
-
[
'192.168.1.1'],
-
[
'192.168.1.2'],
-
[
'192.168.1.3'],
-
[
'192.168.1.4'],
-
[
'192.168.1.5']
-
]
-
for node
in nodeList:
-
h.removeNodes(node)
-
removeNodeMap = h.allocateKey(40)
-
print
'下线节点{}，需要迁移节点个数:{}'.format(node,len(list(
set(removeNodeMap).difference(
set(addNodeMap)))))
-
print
'等待迁移的key信息:{}'.format(list(
set(removeNodeMap).difference(
set(addNodeMap))))
-
h.addNodes(node)
运行结果如下，我们可以很清晰的发现，当我们下线不同节点时，有对应的若干个key会迁移到其他节点。
-
下线节点
['192.168.1.1']，需要迁移节点个数
:5
-
等待迁移的
key信息:
['testKey31_192.168.1.4', 'testKey18_192.168.1.4', 'testKey19_192.168.1.4', 'testKey11_192.168.1.4', 'testKey1_192.168.1.4']
-
下线节点
['192.168.1.2']，需要迁移节点个数
:14
-
等待迁移的
key信息:
['testKey30_192.168.1.3', 'testKey33_192.168.1.3', 'testKey34_192.168.1.3', 'testKey24_192.168.1.3', 'testKey26_192.168.1.3', 'testKey38_192.168.1.3', 'testKey28_192.168.1.3', 'testKey37_192.168.1.3', 'testKey21_192.168.1.3', 'testKey9_192.168.1.3', 'testKey7_192.168.1.3', 'testKey29_192.168.1.3', 'testKey6_192.168.1.3', 'testKey39_192.168.1.3']
-
下线节点
['192.168.1.3']，需要迁移节点个数
:10
-
等待迁移的
key信息:
['testKey27_192.168.1.1', 'testKey20_192.168.1.1', 'testKey25_192.168.1.1', 'testKey35_192.168.1.1', 'testKey8_192.168.1.1', 'testKey32_192.168.1.1', 'testKey14_192.168.1.1', 'testKey5_192.168.1.1', 'testKey4_192.168.1.1', 'testKey12_192.168.1.1']
-
下线节点
['192.168.1.4']，需要迁移节点个数
:8
-
等待迁移的
key信息:
['testKey2_192.168.1.5', 'testKey10_192.168.1.5', 'testKey16_192.168.1.5', 'testKey13_192.168.1.5', 'testKey22_192.168.1.5', 'testKey17_192.168.1.5', 'testKey0_192.168.1.5', 'testKey3_192.168.1.5']
-
下线节点
['192.168.1.5']，需要迁移节点个数
:3
-
等待迁移的
key信息:
['testKey23_192.168.1.2', 'testKey36_192.168.1.2', 'testKey15_192.168.1.2']
虽然结果也符合预期，但此时我们似乎也发现了其他两个问题。
-
问题1 key分布不均衡
当下线192.168.1.2节点时，需要迁移14个key，而迁移192.168.1.5的时候只需要迁移3个key。这意味着什么呢？我们还是举例说明，如下所示，节点A、B、C分别承载2、0、1个key，这里我们假设每个key都是请求量相同，那么A、B、C三个节点压力也会是不同的，A会相对较忙、C节点次之，B节点很闲。简言之，分布不均衡导致后端节点负载压力差异大，在不考虑节点实际瓶颈的情况下，压力相对大的节点上的key比较容易产生读写慢的问题。
那如何解这个问题呢？首先我们还是找到核心矛盾点：节点少导致分片少。
解法1:扩容物理节点 OR 保持现状
从这个角度来看，扩容节点确实对分布均衡是很有效的，但是扩容的同时意味着成本的巨幅增加，对于上面测试数据来说，只有40个key，却要使用50台机器来达到相对的均衡，显然是非常荒谬的。当负载程度快要或者已经达到单点瓶颈的时候，扩容节点无疑是最好的方法，但如果量小的时候，我们也不必纠结于这一点，不均衡就不均衡呗，反正离单点瓶颈值还有相当大的一段距离。
解法2:物理节点虚拟化
在不扩容物理节点的情况下，增加若干个虚拟节点，将仅有的“5”个节点，当”50“个节点用。还是拿之前的图式来举例，对于节点A、B、C来说，假设1个物理节点对应2个虚拟节点，那么节点A对应的虚拟节点是A-01，A-02，当对B、C执行相同处理后，得到如下所示的分布状态，由3个物理节点 转换为6个虚拟节点。由于节点多了，在hash环中，相比过去来说自然就相对均匀了。
-
下线节点
['192.168.1.1']，需要迁移节点个数
:15
-
下线节点
['192.168.1.2']，需要迁移节点个数
:6
-
下线节点
['192.168.1.3']，需要迁移节点个数
:8
-
下线节点
['192.168.1.4']，需要迁移节点个数
:7
-
下线节点
['192.168.1.5']，需要迁移节点个数
:4
先验证下结果，从数据分布来均衡的角度来说，似乎不是太直观，其根本原因是由于测试样本太少，即待分片的key不够，导致40个key 分布在5*10的节点上效果不太明显。
-
下线节点
['192.168.1.1']，需要迁移节点个数
:136
-
下线节点
['192.168.1.2']，需要迁移节点个数
:93
-
下线节点
['192.168.1.3']，需要迁移节点个数
:96
-
下线节点
['192.168.1.4']，需要迁移节点个数
:103
-
下线节点
['192.168.1.5']，需要迁移节点个数
:72
我们在同样的场景下，将待分片的key提升到500个，结果如上所示，发现此时的key分布已经相对均匀（具体实现放在下一小节一并给出）注意使用一致性hash进行路由分片无法像轮询那样得到完全的均衡，只能实现相对均衡。（实现方法我们放在后面和问题2一起来讲）。
-
问题2 容易引发雪崩
每次下线一个节点时，只能将涉及到的key，迁移到hash环上顺时针方向的下一节点上，此时就导致下一节点不仅要负责原先自己负责的key，还要接收上一个节点的全部key。还是用上面的图1来说，当节点B下线，那么相当于3个key都由节点A承载，如果此时节点A已经处于高压状态，那么突如其来的“接盘”，会导致节点A也陷入崩溃下线，继续往后传递，会导致节点一个接连一个的崩溃，最后集群完全不可用。雪崩之下，没有一片雪花是无辜的，何况还是好多片。
那么这个问题怎么解呢？
实际上结合问题1中的解法2来说，通过物理节点虚拟化出多个虚拟节点的方法，也可以使hash环上的虚拟节点分布的更加均匀，让key分布在不同的虚拟节点上，由于每个虚拟节点只会逻辑存在，并且都会对应一个物理节点，所以也就间接打散了物理节点分布。话不多说，我们在上篇代码的基础上，进行了虚拟节点的优化。代码如下：
-
#!/bin/bash/env python
-
# -*- coding:utf8 -*-
-
# auorth:lzj
-
-
import hashlib
-
import sys
-
reload(sys)
-
sys.setdefaultencoding(
'utf-8')
-
-
-
class ConsistentHash(object):
-
def __init__(self, nodes=None,replicaFactor=10):
-
'''
-
a. 初始化nodes即节点列表
-
b. 每个节点虚拟化节点个数
-
c. 字典ring 为我们文中讲述的节点hash取模数值和节点的映射关系
-
d. 列表sortedKeys为模拟顺时针数值从0到2^32依次增大的关系，可以想象成环
-
f. 然后将节点增加到集群中
-
'''
-
-
self.nodes = nodes
-
self.replicaFactor = replicaFactor
-
self.ring = {}
-
self.sortedKeys = []
-
self.addNodes(nodes)
-
-
#nodes是一个节点的列表，遍历列表逐个添加到hash环中
-
def addNodes(self, nodes):
-
if nodes:
-
for node
in nodes:
-
# 增加虚拟节点，并映射到环上
-
for number
in range(self.replicaFactor):
-
replicaNode =
"%s%s" %(node,number)
-
# print replicaNode
-
replicaNodeHashResult = hashlib.sha1(replicaNode).hexdigest()
-
intReplicaNodeHashResult = int(replicaNodeHashResult,
16)
-
modIntReplicaNodeHashResult = intReplicaNodeHashResult % (
2 **
32)
-
self.ring[modIntReplicaNodeHashResult] = node
-
self.sortedKeys.append(modIntReplicaNodeHashResult)
-
self.sortedKeys.sort()
-
-
def removeNodes(self, nodes):
-
'''，
-
和增加节点相同，此时我们需要将节点hash取模数值和节点的映射关系进行更新删除，
-
并在环上将清理该节点的信息
-
'''
-
if nodes:
-
for node
in nodes:
-
for number
in range(self.replicaFactor):
-
replicaNode =
"%s%s" %(node,number)
-
replicaNodeHashResult = hashlib.sha1(replicaNode).hexdigest()
-
intReplicaNodeHashResult = int(replicaNodeHashResult,
16)
-
modIntReplicaNodeHashResult = intReplicaNodeHashResult % (
2 **
32)
-
self.ring.pop(modIntReplicaNodeHashResult)
-
self.sortedKeys.remove(modIntReplicaNodeHashResult)
-
-
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
我们此时再来对新的一致性hash进行测试，看是否解决了我们的问题，如下所示，我们此时发现，当一个节点下线需要迁移时，会向多个物理节点迁移，而不再只向一个节点迁移。这样我们的问题就圆满解决了。
-
下线节点
['192.168.1.1']，需要迁移节点个数
:15
-
等待迁移的
key信息:
['testKey27_192.168.1.5', 'testKey15_192.168.1.5', 'testKey16_192.168.1.4', 'testKey33_192.168.1.2', 'testKey12_192.168.1.2', 'testKey11_192.168.1.2', 'testKey26_192.168.1.2', 'testKey13_192.168.1.5', 'testKey22_192.168.1.2', 'testKey3_192.168.1.5', 'testKey7_192.168.1.2', 'testKey29_192.168.1.2', 'testKey0_192.168.1.2', 'testKey8_192.168.1.5', 'testKey20_192.168.1.2']
-
下线节点
['192.168.1.2']，需要迁移节点个数
:6
-
等待迁移的
key信息:
['testKey2_192.168.1.1', 'testKey10_192.168.1.1', 'testKey18_192.168.1.3', 'testKey31_192.168.1.3', 'testKey14_192.168.1.5', 'testKey17_192.168.1.3']
-
下线节点
['192.168.1.3']，需要迁移节点个数
:8
-
等待迁移的
key信息:
['testKey1_192.168.1.2', 'testKey34_192.168.1.2', 'testKey9_192.168.1.2', 'testKey24_192.168.1.1', 'testKey28_192.168.1.2', 'testKey19_192.168.1.2', 'testKey6_192.168.1.1', 'testKey37_192.168.1.1']
-
下线节点
['192.168.1.4']，需要迁移节点个数
:7
-
等待迁移的
key信息:
['testKey30_192.168.1.2', 'testKey35_192.168.1.1', 'testKey38_192.168.1.2', 'testKey21_192.168.1.2', 'testKey32_192.168.1.1', 'testKey39_192.168.1.2', 'testKey4_192.168.1.5']
-
下线节点
['192.168.1.5']，需要迁移节点个数
:4
-
等待迁移的
key信息:
['testKey23_192.168.1.1', 'testKey5_192.168.1.4', 'testKey25_192.168.1.3', 'testKey36_192.168.1.1']
从“真理”出发，向外发散
-
个性化一致性hash
上面我们从结果验证了一致性hash的原理，并且从原理出发，解决了key分布不均衡 、和容易引发雪崩的痛点。那么还有其他点需要我们注意吗？实际上，在第二部分中我们是假定所有key的请求量相同，然后从分布均衡与否的角度去看待一致性hash这个路由分片策略的，而在实际业务场景中，我们会发现每个key的请求量必然是不相同的。因此问题会变得更加棘手。
当物理节点上的key数量分布相对均衡时，对于请求量高的key，会增加其对应物理节点的资源消耗，再次带来负载差异化，除了扩容物理节点外，还需要个性化的一致性hash策略，具体实现方法很多且和实际场景强相关，因此不再一一实现测试。这里将一些想法抛出来，如果有其他idea，也欢迎留言，大家一起讨论。
-
-
针对不同物理节点设置不同的replicaFactor，对于有热点key请求的节点 需要将虚拟节点数量减少，或者非热点key所在节点增加虚拟节点数量；
-
在第一次生成key-node映射关系后，在不下线节点的情况下，维护全局key-node的Map，基于实际的节点负载，将非热点key逐渐从高负载节点移动到底负载节点。
-
-
究竟1个物理节点虚拟多少个最佳呢？
-
首先你要知道“最佳”代表着key分布的均衡、并且计算分布的速度还快。但此时你要记住，一致性hash永远没有绝对均衡，只有相对均衡。
-
精确答案肯定是没有的，不要信网上虚200个或者几百个就差不多了，都是拍脑袋或者不严谨的。不同机器、不同配置，根本没有可比性。即使配置相同，机器上细微的差异都会对结果有影响。但是大趋势是有的，效果和虚拟个数是成正相关的，随着虚拟个数的增加，当到达某一阀值后，计算分布的性能会逐渐下降。所以使用时先测试吧，找一个你服务能接受的值。
-
尾记
一致性hash至此告一段落，写着写着字数就多了。上下两篇加起来有万字了。相信坚持总会有所收获。加油！
原创不易，觉得多少有所收获的话，就请你为本文点个赞或者无情转发、关注吧。你的支持是我写作的动力。
如果看了有任何问题，可以与我联系，全程解答！
转载：https://blog.csdn.net/weixin_47158466/article/details/107971859