普通哈希的问题
分布式集群中,对机器的添加删除,或者机器故障后自动脱离集群这些操作是集群管理最基本的功能。如果采用常用的hash(object)%N取模的方式,在节点进行添加或者删除后,需要重新进行迁移改变映射关系,否则可能导致原有的数据无法找到。
举个栗子
随着业务和流量的增加,假如我们的Redis查询服务节点扩展到了3个,为了将查询请求进行均衡,每次请求都在相同的Redis中,使用hv = hash(key) % 3的方式计算,对每次查询请求都通过hash值计算,得出来0、1 、2的值分别对应服务节点的编号,计算得到的hv的值就去对应的节点处理。
图片
但是这里有个问题,服务增减是需要对此时的key进行重新计算,比如减少一个服务的时候,此时需要按 hv = hash(key) % 2计算,而增加一个服务节点的时候需要按hv = hash(key) % 4计算,而这种取模基数的变化会改变大部分原来的映射关系,导致数据查询不到。
图片
这个时候只能进行数据迁移,真是太麻烦了,而一致性哈希算法显然是一个更好选择!
一致性hash算法
一致性哈希同样使用了取模的方式,不同的是对 2^32 这个固定的值进行取模运算。
在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n 个关键字重新映射,其中K是关键字的数量, n是槽位数量,而不需要对所有的映射关系进行重新映射!
Hsh环
我们可以把一致哈希算法是对 2^32 进行取模运算的结果值虚拟成一个圆环,环上的刻度对应一个 0~2^32 - 1 之间的数值,如下图:
图片
节点入环
下图我们三个节点(A/B/C)经过哈希计算,放入下面环中,一般我们会根据服务器的IP或者唯一别名进行哈希计算。
图片
那数据是如何进行关系映射呢,同样key值经过哈希之后,结果映射到哈希环上,然后将结果值按顺时针方向找到离自己最近的节点上,将value存储到那个节点上。
如下图:
图片
k1、k2、k3经过哈希计算后在哈希环的位置,顺时针方向找到离自己最近的节点,比如k1最近的节点是A,节点A就是存储 k1数据value的节点。
新增节点
新增加点D,节点的数量增加到了四个,而此时k2最近的节点是D,所以会迁移到D,k1和k3不受影响
图片
删除节点
删除节点B之后,存储在B节点上的k2,将会重新映射找到离它最近的节点C,此时k2的数据存储在C节点上,k1、k3不受影响。
图片
不平衡问题
我们通过新增节点和删除节点,知道了该方式会影响该节点的顺时针的后一个节点,其他节点不受影响。
但是因为生成哈希值的分布并不是均匀的,如下图新增k4、k5,如果节点B宕机了,k2和k4也迁移到节点C,导致那么大部分请求就落到节点C了,如果数量更多呢,此时会导致节点C压力陡增,这样就不均衡了!
图片
那如何解决这个问题呢?
那就是通过 虚拟节点
虚拟节点
虚拟节点 可以理解为是作为实际节点的一个copy,多个虚拟节点映射一个实际节点,因为在哈希环上节点越多就分布的越均匀,即使我们现实中不会有那么多真实节点。
图片
上图中三个真实节点A、B、C,映射了9个虚拟节点,如果key值经过哈希落到临近A-1、A-2、A-3的虚拟节点,那么最终都将映射到真实节点A,你想如果虚拟节点再多点,是不是就会更均衡了!
假设真实节点A被移除,A对应虚拟节点也会移除,但是多虚拟节点方式可以映射更多真实节点,让剩余的节点更好得去承担节点变化的请求压力!
如下图:
图片
这里简单讲解一下,图中真实节点A被移除,那么对应的虚拟节点移除,那么此时k1的重新映射到C-1、k3重新映射到B-3,也就是说被迁移到真实节点B和C,由此可见节点被移除会被更均衡的分散到其他节点上。
图中只简单列举了几个虚拟节点,虚拟节点越多,相对会越均衡。
好了,今天关于一致性哈希算法的介绍就到这了!