一致性哈希以及原理的实现

集群的使用

在使用redis的过程中,为了保证redis的高可用,我们一般会对 redis做主从复制,组成master和slave的形式,进行数据的读写分离,当数据量超过一定数量时,我们要对redis集群做分库分表的操作

来个栗子，我们有一个电商平台，需要使用Redis存储商品的图片资源，存储的格式为键值对，key值为图片名称，Value为该图片所在的文件服务器的路径，我们需要根据文件名，查找到文件所在的文件服务器上的路径，我们的图片数量大概在3000w左右，按照我们的规则进行分库，规则就是随机分配的，我们以每台服务器存500w的数量，部署12台缓存服务器，并且进行主从复制

由于我们定义的规则是随机的，所以我们的数据有可能存储在任何一组Redis中，比如我们需要查询"product.png"的图片，由于规则的随机性，我们需要遍历所有Redis服务器，才能查询得到。这样的结果显然不是我们所需要的。所以我们会想到按某一个字段值进行Hash值、取模。所以我们就看看使用Hash的方式是怎么进行的。

使用Hash的Redis集群

如果我们使用Hash的方式,每一张图片进行分库的时候都可以定位到特定的服务器

我们需要查询的是图product.png，由于我们有6台主服务器，所以计算的公式为：hash(product.png) % 6 = 5, 我们就可以定位到是5号主从，这们就省去了遍历所有服务器的时间，从而大大提升了性能。

问题

虽然不需要对所有redis服务器进行遍历而提升了性能.但是使用hash算法缓存会出现一些问题,redis服务器变动时,所有缓存的位置都会发生改变.比如,现在redis 服务器增加了三台,结果肯定不是hash(product.png) % 8结果肯定不是原来的5了

再者,6台服务器中,当某个主从群出现故障时,也无法进行缓存,那我们需要把故障机器溢出,所以取模数又会从6变成了5.

为了避免上述情况,hash一致性算法就诞生了

一致性hash算法原理

一致性hash算法也是使用取模的方法,不过上述方法是对服务器数量进行取模,而一致性hash算法是对2的32方取模.即一致性hash算法将整个hash空间组成一个虚拟的圆环,hash函数的空间位置为0-2^32-1(32位无符号整型)

整个圆环以顺时针方向组织,圆环上方的点代表0,0点右侧的第一个点代表1,以此类推.第二部我们将各个服务器进行hash,就具体可以选择服务器的ip或者主机名作为关键字哈希,这样每台服务器确定在哈希环的一个位置上,比如有三台机器就如图所示

现在,我们使用以下算法 定位数据访问到相关的服务器:

将数据key使用相同的函数hash计算出哈希值,并确定次数据在环上的位置,从此位置沿顺时针查找,遇到的服务器就是其该定位到的服务器

容错性和可扩展性

现在假设node c宕机了,我们从图中可以看到AB不会受影响,只有c对象被重新定位到nodeA,所以我们发现在一致性哈希算法中,如果一天服务器不可用,受影响的数据仅仅是此服务器到环形空间前一台服务器之间的数据,其他不会受影响

数据倾斜问题

在一致性hash算法服务节点太少的情况下,容易因为节点分布不均匀造成数据倾斜（被缓存的对象大部分缓存在某一台服务器上）问题

为了解决数据倾斜问题,一致性hash算法引入了虚拟节点机制,即对每一个服务器节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点

具体操作可以为服务器或主机名后加入编号来实现

数据定位算法不变,时序增加一步:虚拟节点到实际点的映射

所以加入虚拟节点后,即使在服务节点很少的情况下,也能做到数据的均匀分布