背景描述:

哈希分槽器,顾名思义,它的主要工作就是根据redis协议中的key值进行哈希计算,并选择相关的存储节点,在不同的节点上完成redis数据的读写操作.

通过上面的描述,我们可以看出,哈希分槽器主要的设计部分包括如下:

  1. 数据分槽器 : 基于一致性哈希算法,负责key值的落槽工作,每个槽对应一个redis group 单元.
  2. 哈希结构及算法 : 需要减少节点添加删除造成的缓存失效问题,所以采用一致性哈希算法.

一. 数据分槽器(Slots)

在RedTun设计下, 数据分槽器属于Neter的一部分,主要是面向网络组进行服务,数据分槽器前后沟通了一致性哈希算法,服务器group节点,redis客户端请求这三方,是用户的请求可以通过一致性哈希算法准确落到指定的redis group内,响应的group负责读写分离.

1.1 用户数据分槽流程

1.2 分槽器实现

为了兼容线上环境,分槽器目前的一致性哈希算法实现高度参考predis的hashring,采用crc32 IEEE作为hash的值计算算法,采用uint32作为hash环的大小.

1.3 算法兼容性测试

为了保障RedTun的一致性哈希算法 和 线上环境predis的一致性哈希算法一致,避免缓存大量失效的情况,目前我们针对这两个算法实现做了单元测试:

  1. 测试总量: 8529820次 随机 key 的哈希生成与结果匹配.

  2. 测试异常: 0次

总共进行了800多万次测试,两个语言的算法实现没有出现差异结果,说明RedTun内部的一致性哈希算法已经和线上高度一致,不会造成失效问题.

1.4 一致性哈希的相关数据结构优化

1.4.1 哈希环的hash key选择

一致性哈希中,每个key的稳定性决定了哈希环上节点位置的稳定性,所以,在RedTun中,对于hash key的选择没有粗略的选择 IP:PORT , 而是在用户配置区间为每个GROUP提供了一个名字叫做”hash_ring_key” , 根据这个字段内的数据进行哈希环的构造.

二 . 哈希结构及算法

现在我们需要设计一个哈希结构,这个哈希结构能够把各个redis group节点映射上来,并且这个哈希结构具有较高的稳定性,当添加或者删除相关的group节点时,不会造成哈希映射的大规模失效.在上述的需求下,我们选择了一致性哈希这个算法.

2.1 一致性哈希相关解释

关于一致性哈希的描述,各处都有比较完善的文章,下面主要摘抄部分来阐述一致性哈希的关键点.

其实,⼀致性哈希算法也是使⽤取模的⽅法,只是,刚才描述的取模法是对服务器的数量进⾏取模,⽽⼀致性哈希算法是对2^32取模.⾸先,我们把⼆的三⼗⼆次⽅想象成⼀个圆,就像钟表⼀样,钟表的圆可以理解成由60个点组成的圆,⽽此处我们把这个圆想象成由2^32个点组成的圆,⽰意图如下:


圆环的正上⽅的点代表0,0点右侧的第⼀个点代表1,以此类推,2、3、4、5、6……直到2^32-1,也就是说0点左侧的第⼀个点代表2^32-1,我们把这个由2的32次⽅个点组成的圆环称为hash环,假设我们有3台缓存服务器,服务器A、服务器B、服务器C,那么这三台服务器肯定有⾃⼰的IP地址,我们使⽤它们各⾃的IP地址进⾏哈希计算,使⽤哈希后的结果对2^32取模,可以使⽤如下公式⽰意。

hash(服务器A的IP地址) % 2^32

通过上述公式算出的结果⼀定是⼀个0到2^32-1之间的⼀个整数,我们就⽤算出的这个整数,代表服务器A,既然这个整数肯定处于0到2^32-1之间,那么,上图中的有⼀个点与这个整数对应,⽽我们刚才已经说明,使⽤这个整数代表服务器A,那么,服务器A就可以映射到这个环上,⽤下图⽰意.

同理,服务器B与服务器C也可以通过相同的⽅法映射到上图中的hash环中

hash(服务器B的IP地址) % 2^32

hash(服务器C的IP地址) % 2^32

通过上述⽅法,可以将服务器B与服务器C映射到上图中的hash环上,⽰意图如下

假设,我们需要使⽤缓存服务器缓存图⽚,⽽且我们仍然使⽤图⽚的名称作为找到图⽚的key,那么我们使⽤如下公式可以将图⽚映射到上图中的hash环上。

hash(图⽚名称) % 2^32

映射后的⽰意图如下,下图中的橘⻩⾊圆形表⽰图⽚

好了,现在服务器与图⽚都被映射到了hash环上,那么上图中的这个图⽚到底应该被缓存到哪⼀台服务器上呢?上图中的图⽚将会被缓存到服务器A上,为什么呢?
位置开始,沿顺时针⽅向遇到的第⼀个服务器就是A服务器,所以,上图中的图⽚将会被缓存到服务器A上,如下图所⽰。

⼀致性哈希算法就是通过这种⽅法,判断⼀个对象应该被缓存到哪台服务器上的,将缓存服务器与被缓存对象都映射到hash环上以后,从被缓存对象的位置出⽅向遇到的第⼀个服务器,就是当前对象将要缓存于的服务器,由于被缓存对象与服务器hash后的值是固定的,所以,在服务器不变的情况下,⼀张图⽚必定会被缓存服务器上,那么,当下次想要访问这张图⽚时,只要再次使⽤相同的算法进⾏计算,即可算出这个图⽚被缓存在哪个服务器上,直接去对应的服务器查找对应的图⽚即刚才的⽰例只使⽤了⼀张图⽚进⾏演⽰,假设有四张图⽚需要缓存,⽰意图如下:

1号、2号图⽚将会被缓存到服务器A上,3号图⽚将会被缓存到服务器B上,4号图⽚将会被缓存到服务器C上。

文档更新时间: 2019-01-18 17:40   作者:李彪