分布式缓存的一致性 Hash 算法

分布式缓存的一致性 Hash 算法
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

分布式缓存的一致性 Hash 算法

一、使用一致性 Hash 算法的原因


简单的路由算法可以使用余数 Hash:用服务器数据除缓存数据 KEY 的 Hash 值,余数为服务器列表下标编码。这种算法可以满足大多数的缓存路由需求。但是,当分布式缓存集群需要扩容的时候,事情就变得棘手了。举个例子:很容易可以计算出,3台缓存服务器扩容至4台服务器,大约有 75%(3/4)被缓存了的数据不能正确命中,随着服务器集群规模的增大,这个比例线性上升。当100台服务器的集群中加入一台新服务器,不能命中的概率是 99%(N/N+1)。这种结果显然是不能接受的。

一种解决办法是在网站访问量最少的时候扩容缓存服务器集群,这时候数据库的负载冲击最小。然后通过模拟请求的方法逐渐预热缓存,使缓存服务器中的数据重新分布。但这种方案对业务场景有要求,还需要技术团队通宵加班。当然还有比流行的方案:一致性Hash 算法。

二、分布式缓存的一致性 Hash 算法


一致性 Hash 算法通一个叫作一致性 Hash 环的数据结构实现 KEY 到缓存服务器的 Hash 映射,如下图:
img

具体算法过程为:先构造一个长度为 2^{32} 整数环(这个环被称作一致性 Hash环)根据节点名称的 Hash 值(其分布范围为[0,2^{32}-1])将缓存服务器节点放置在这个 Hash 环上。然后根据需要缓存的数据的 KEY 值计算得到其 Hash 值(其分布范围也同样为[0,2^{32}-1]),然后在 Hash 环上顺时针查找距离这个 KEY 的 Hash 值最近的缓存服务器节点,完成 KEY 到服务器的 Hash 映射查找。

在缓存服务器集群需要扩容的时候,只需要将新加入的节点名称(Cache 服务器5)的 Hash 值放入一致性 Hash 环中,由于 KEY 是顺时针查找距离其最近的节点,因此新加入的节点只影响整个环中的一小段,如下图:
img
上图中,加入新节点 NODE5 后,原来的 KEY 大部分还能继续计算到原来的节点,只有节点4的部分数据重新计算到了节点5。这样就能保证大部分被缓存的数据还可以继续命中。3台服务器扩容至4台服务器,可以继续命中原有缓存数据的概率为 75%,远高于余数哈希的 25%,而且随着集群规模越大,继续命中原有缓存数据的概率也逐渐增大,100台服务器扩容增加1台,继续命中的概率 99%。虽然仍有小部分数据缓存在服务器中不能被读到,但是这个比例足够小,通过访问数据库获取也不会对数据库造成致命的负载压力。

具体应用中,这个长度为 2^{32}的一致性 Hash 环通常使用二叉查找树实现,Hash 查找过程实际上是在二叉查找树中查找不小于查找树的最小数值。当然这个二叉树的最右边叶子节点和最左边的叶子节点相连接,构成环。

三、分布式缓存的一致性 Hash 算法存在的问题


新加入的节点 NODE5 只影响了原有节点 NODE4,也就是说一部分原来需要访问 NODE4 的缓存数据现在访问 NODE5(概率上是50%)。但是原来的其它节点不受影响,这就意味着其它节点缓存数据量和负载压力是 NODE4 和 NODE5 的两倍。如果所有节点的硬件和性能一样,那么这个结果显然不是我们需要的。

四、分布式缓存的一致性 Hash 算法问题解决方案


计算机领域有句话:计算机的任何问题都可以通过增加一个虚拟层来解决。计算机硬件,计算机网络,计算机软件都一样。计算机的 7层协议,每一层都可以看做是下一层的虚拟层;计算机操作系统可以看做是计算机硬件的虚拟层;Java 虚拟机可以看做是操作系统的虚拟层;分层的计算机软件架构事实上也是利用虚拟层的概念。解决上述问题就可以使用虚拟层的手段;将每台物理缓存服务器虚拟为一组虚拟缓存服务器,将虚拟服务器的 Hash 值放置在 Hash 环上,KEY 在环上先找到虚拟服务器节点,再得到物理服务器的信息。这样新加入物理服务器节点时,是将一组虚拟节点加入环中,如果虚拟节点的数目足够多,这组虚拟节点将会影响同样多数目的已经在环上存在的虚拟结点,这些已经存在的虚拟节点有对应不同的物理节点。最终的结果是:新加入一台缓存服务器,将会较为均匀地影响原来集群中已经存在的服务器,也就是说分摊原有缓存服务器集群中所有服务器的小部分负载,其总的影响范围和上面讨论过的相同。如下图:
img
新加入的节点 Node3 对应的一组虚拟节点为 V31,V32,V33 加入到一致性 Hash 环上后,影响 V01,V12,V22 三个虚拟节点,而这三个虚拟节点分别对应 Node0,Node1,Node2 三个物理节点。最终 Node3 加入后会影响到集群中已存在的三个物理节点,在理想情况下,每个物理节点受影响的数据量为其节点缓存数据量的 1/4(X/(N+X)),N为原有物理节点,X为新加入的物理节点,也就是集群中已经被缓存的数据有 75% 可以被继续命中,和未使用虚拟节点的一致性 Hash 算法结果相同。

75% 可以被继续命中,和未使用虚拟节点的一致性 Hash 算法结果相同。

虽然每个物理节点对应的虚拟节点越多,各个物理节点之间的负载越均衡,新加入物理服务器对原有的物理服务器的影响越保持一致(这就是一致性 Hash 这个名称的由来)。在实践中,一台物理服务器虚拟为多少个虚拟服务器节点比较合适呢?太多会影响性能,太少会导致负载不均衡,一般来说,经验值是150,当然根据集群规模和负载均衡的精度需求,这个值应该根据具体情况具体对待。

本文来源程序猿进阶,由javajgs_com转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/8306

发表评论