A New Start

手动实现一致性 Hash 算法

一、背景

最简单的一个应用场景便是缓存,当单机缓存量过大时需要分库,然后根据相关信息进行 hash 取模运算到指定的机器上去,比如 index = hash(ip) % N。

但是当增加或者减少节点的时候,由于上述公式的 N 值是有变化的,所以绝大部分,甚至说所有的缓存都会失效,对于这种场景最直接的解决办法便是使用一致性 hash 算法

二、一致性 Hash 算法简介

1、简单的一致性 Hash

关于一致性 Hash 算法,简单的抽象描述就是一个圆环,然后上面均匀布局了 2^32 个节点,比如 [0,1,2,4,8…],然后将我们的机器节点散列在这个圆环上,至于散列的规则,可以使用 hash(ip) 或者 hash(域名)。

hash 环

当寻找数据的时候,只需要将目标数据的key散列在这个环上,然后进行顺时针读取最近的一个机器节点上的数据即可。

如下图的简单版本,假如总共有3个数据节点(A、B、C),当需要查找的数据的key经计算在A和B之间,则顺时针找,便找到了节点B。

数据查找

最大的优点是:还是以上面的案例为背景,当节点B宕了之后,顺时针便找到了C,这样,影响的范围仅仅是A和B之间的数据,对于其他的数据是不影响的。

2、虚拟节点

但是在散列数据节点的时候,紧凑性会受 hash 算法的影响,比如A、B、C三个数据服务器,在 hash 计算后散列在 1、2、4三个节点上,这样就会因为太密集而失去平衡性。比如此时我们要查找的数据的key经过 hash 运算之后,大概率是出现在4和1之间的,即在C之后,那样的话顺时针查找便会找到A,那么A服务器便承载了几乎所有的负载,这就失去了该算法的意义。

此时虚拟节点便出现了,比如上述的三台服务器各虚拟分裂出1各虚拟节点(A1、B1、C1),那么这样便可以在一定程度上解决一致性hash的平衡性问题。

虚拟节点A1、B1、C1

三、数组简陋版

1、思路

简单描述下思路:其实就是使用一个数组去存储所有的节点信息,存完之后需要手动排序一下,因为是有序的,所以取的时候就从 index 为0开始挨个对比节点的 hash 值,直到找到一个节点的 hash 值是比我们的目标数据的 hash(key) 大即可,否则返回第一个节点的数据。

2、代码其实很简单,直接撸:

3、弊端

① 排序算法:上面直接使用 Arrays.sort() ,即 TimSort 排序算法,这个值得改进;
② hash 算法:上文没有提及 hash 算法,需要改进;
③ 数据结构:上文使用的是数组,但是需要手动进行排序,优点是插入速度尚可,但是扩容不便,而且需要手动排序,排序的时机也不定,需要改进;
④ 虚拟节点:没有考虑虚拟节点,需要改进。

四、TreeMap 进阶版

上文的实现既然有弊端,那就操刀改进之:

① 数据结构:我们可以使用 TreeMap 数据结构,优点是该数据结构是有序的,无需再排序,而且该数据结构中有个函数叫 tailMap,作用是获取比指定的 key 大的数据集合;
② hash 算法:此处我们使用 FNV1_32_HASH 算法,该算法证实下来散列分布比较均匀,hash 碰撞尚且 ok;
③ 虚拟节点:我们暂且设置每个节点锁裂变的虚拟节点数量为10。

代码也不难,也是直接撸:

五、其他

1、虚拟节点的数量建议:

虚拟节点数量和服务器数量关系(待考量)

看上图,X 轴是虚拟节点数量,Y 轴是服务器数量,很显然,服务器越多,建议的虚拟节点数量也就越少。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注