一致性hash
场景:
一个分布式的存储系统(N台服务器),需要将数据存储到某个节点上,如果采用普通的hash算法,通过取模运算将数据映射到具体的节点上,那么当有节点故障或者新节点加入集群时,之前所有的数据映射都将失效。对应于持久化存储就需要做数据迁移,对于分布式缓存系统,那么保存的缓存数据都将失效。
为了解决上述问题,引入了一致性hash算法。
原理:
把数据使用hash函数,映射到一个空间中(0~2^32-1)。当数据存储时,得到一个hash值,对应到这个环的相应位置,存储节点也计算hash值,分散到这个环中。如图:object1对应到图中的key1位置。
然后,沿着顺时针方向找到最近的节点,将数据保存到该节点上,如图:
如果node2发生故障,则只会影响node1和node2之间的数据重新分配,如下图:之前保存在node2上的object2和object3的将重新分配到node3上。
后期扩展加入新的节点,影响也不是全范围的,如图:在node1和node2中加入新节点node3,只会导致node1和node4之间的数据重新分配到node4上,其余的不受影响。
但是我们发现,在实际的生产环境中,如果其中一个节点NodeA挂了,恰好NodeA上承担的数据比较多,那么NodeA承担的数据将会分配到下一个节点NodeB上,导致NodeB因为负载突然变高,最终也导致NodeB宕机,这样依次下去,就导致整个集群都挂了,这就是俗称的“雪崩”效应。
为了解决上述问题,又引入了“虚拟节点”的概念。
虚拟节点:
正如上所述,hash算法并不是保证绝对的平衡,尤其当node比较少的情况下,对象并不能均匀的映射到node上,在上图中,object2和object3就都保存到了node2上。为了解决这一问题,引入虚拟节点。它是实际节点在hash空间的复制品,一个实际节点对应了若干了虚拟节点。下图是一个比较理想的分散图:
nodeA1和nodeA2是nodeA的虚拟节点,依次类推,如果虚拟节点能够均匀分散,那么这个集群的数据就回分散均匀。实际生产环境中,虚拟节点在hash环上的分布是按照实际节点的ip加上数字的后缀,例如nodeA的ip为:192.168.0.100,引入3个虚拟节点,那么:
hash("192.168.0.100#1") //nodeA1
hash("192.168.0.100#2") //nodeA2
hash("192.168.0.100#3") //nodeA3
转载于:https://my.oschina.net/vbird/blog/384007