一致性hash算法

1、为什么要用一致性hash算法

在使用Redis集群，Mysql集群，memcached集群时，经常用到将某个数据按照某种规则存放在不同的服务器节点上，比如使用hash取模算法，将value值为1,2,3,4,5,6分别存放在三台服务器上。

使用hash(value)%3就可以分别得出，value=1存放在编号为1的服务器，value=2存放在编号为2的服务器，value=3存放在编号为3的服务器，value=4存放在编号为1的服务器，value=5存放在编号为2的服务器，value=6存放在编号为3的服务器。

最后的结果就是这样

但是如果其中Node3机器宕机，再使用以前的规则来进行分布（hash(value)%2），结果就会变成

由于算法简单，效果不是特别明显，但能够明白，如果宕机一台机器，那么大部分情况下，存储的值和对应的服务器编号也会相应的改变，增加一台机器也会如此。这会导致基本上所有的数据都会失效，从而服务器会短时间承担巨大的压力。

Q1:如何减少因宕机或增加机器而受影响的缓存？A1:一致性hash算法。

2、一致性hash算法详解

一致性hash算法也是取模算法，但它是对2^32取模，而hash算法是对服务器的数量取模。

画图来讲，就是将2^32划分成2^32个单位，每个值都能在这上面找到对应的位置。

按顺时针来看，正上方的点表示0，以此类推，最后一个点是2^32-1，而2^32和0重合，把这些点组成的圆环如图所示

假设有3台Redis服务器（服务器A，服务器B，服务器C），按照一致性hash算法将ip地址和主机名计算（hash(ip地址)%2^32）得到值在这个圆环上面一定能够体现。

确定了服务器的位置后，再对需要存储的值进行运算，假如有value为1,2,3,4,5，一共5个值，将它们存储到对应的服务器上，经过一致性hash计算后，最终分布如下

根据一致性hash算法的规则，将value根据一致性hash算法计算出来并确定在圆环的位置后，从这个位置沿着顺时针走，碰到的第一个Node就是存储它的服务器。

于是得到，value为5,2,1的值会存储在A服务器上，value为3,4的值会存储在B服务器上。

2.1、一致性hash算法的可扩展性

如果此时节点A不幸宕机，那么圆环的样子就是下图所示

这时，如果再次计算value为5,2,1的hash值，最终它们的归属的Node是C服务器。而B服务器是不受影响的。

如果此时增加了一台D服务器

这时，value为5的hash值最终会归属到D服务器上，而A服务器则不受影响。

总结：一致性hash算法能够尽量的减少因服务器宕机或增加服务器而带来的数据失效的问题。但是一致性hash算法也会带来另一个问题：数据倾斜。

2.2、一致性hash算法的数据倾斜问题

如图所示

其中，A节点存储的数量是3个，B节点是2个，C节点则是0个，如果大部分的数据在圆环上表示的点在B-A之间，那么大部分的数据都会归属于A节点。这会导致A服务器的压力过大，而其他服务器的压力过小，造成负载不均衡的问题。

为了解决这个问题，只能尽可能的让服务器尽量够多，而且要均匀地分布在这个圆环上。但是真实的服务器只有三台，如何让它们变得够多？这时需要将这些真实服务器复制出来变成虚拟节点。

如何增加虚拟节点？

计算服务器在圆环上的位置是使用hash(ip地址)%2^32的计算方法，只需要改变括号中的内容即可。

因此可以使用hash(ip地址+主机名)%2^32来计算新的hash地址。