首页 > 网站建设 >

大型网站建设分布式缓存进行伸缩性设计之一致性Hash算法

发布时间:2018-11-08 作者:深圳网站建设

大型网站建设分布式缓存进行伸缩性设计之一致性Hash算法
一、分布式缓存的一致性Hash算法
  深圳网站建设公司在上一篇文章中,对于大型网站平台建设的集群分布式缓存伸缩性设计经验分享文章中对于设计“伸缩性架构”进行过详细介绍,本文主要分享“伸缩性架构设计”的一致性算法。一致性算法通过一个叫作一致性Hash环的数据结构实现KEY到缓存服务器的Hash映射。这个结构关系如图6-11所示
大型网站建设一致性Hash算法原理图6-11
  具体算法过程为:先构造一个长度为0~ 2 32的整数环(这个环被称作一致性Hash环),根据节点名称的Hash值(其分布范围同样为0~ 2 32)将缓存服务器节点放置在这个Hash环上。然后根据需要缓存的数据的EEY值计算得到其Hash值(其分布范围电同样为0~ 2 32),然后在Hash环上顺时查找距离这个KEY的Hash值最近的缓存服务器节点,完成KEY到服务器的Hash映射查找。
  在图6-11中,假设NODE1的Hash值为3,594,963,423,NODE2的Hash值为l,845,328,979.而TuKEYOhOHash值)为2,534,256,785,那么KEYO在环上顺时针查找,找到的最近的节点就是NODE1。
  当缓存服务器集群需要扩容的时候,只需要将新加入的节点名称(NODE3)的Hash值放入致性Hash环中,由于KEy顺时针查找距离其最近的节点,因此新加入的节点只影响整个环中的小段,如图6-12中深色段。
      大型网站建设之示意图6-12增加节点后的一致性Hash环结构
  假设NODE3的Hash值是2,790,324,235,那么加入NODE3后,1:EYO(Hash值2,534,256,785)顺时针查找得到的节点就是NODE3。图6-12中,加入新节点NODE3后,原来的KEY大部分还能继续计算到原来的节点,只有KEY3、KEYO从原来的NODE1重新计算到NODE3。这样就能保证大部分被缓存的数据还可以继续命中。3台服务器扩容至4台服务器,可以继续命中原有缓存数据的概率是75%,远高于余数Hash的25%,而且随着集群规模越大,继续命中原有缓存数据的概率电逐渐增大,100台服务器扩容增加l台服务器,继续命中的概率是99%。虽然
仍有小部分数据缓存在服务器中不能被读到,但是这个比例足够小,通过访问数据库获取也不会对数据库造成致命的负载压力。
  具体应用中,这个长度为2s-的致性Hash环通常使用二叉查找树实现,Hash查找过程实际上是在二叉查找树中查找不小于查找数的最小数值。当然这个二叉树的最右边叶子节点和最左边的叶子节点相连接,构成环。但是,上面描述的算法过程还存在个小小的问题
  新加入的节点NODE3只影响了原来的节点NODE1,电就是说部分原来需要访问NODE1的缓存数据现在需要访问NODE3(概率上是50%)但是原来的节点NODEO和NODE2不受影响,这就意味着NODEO和NODE2缓存数据量和负载压力是NODE1与NODE3的两倍。如果4台机器的性能是样的,那么这种结果显然不是我们需要的。
怎么办?
  计算机领域有句话:计算机的任何问题都可以通过增加一个虚拟层来解决。计算机硬件、计算机网络、计算机软件部莫不如此。计算机网络的7层协议,每层部可以看作是下层的虚拟层;计算机操作系统可以看作是计算机硬件的虚拟层;Java虚拟机可以看作是操作系统的虚拟层;分层的计算机软件架构事实上电是利用虚拟层的概念。
  解决上述致一性Hash算法带来的负载不均衡问题,也可以通过使用虚拟层的手段:将每台物理缓存服务器虚拟为组虚拟缓存服务器将虚拟服务器的Hash值放置在Hash环上,KEY在环上先找到虚拟服务器节点,再得到物理服务器的信息。
  这样新加入物理服务器节点时,是将组虚拟节点加入环中,如果虚拟节点的数目足够多,这组虚拟节点将会影响同样多数目的已经在环上存在的虚拟点,这些已经存在的虚拟节点又对应不同的物理节点。最终的结果是:新加入台缓存服务器,将会较为均匀地影响原来集群中已经存在的所有服务器,也就是说分摊原有缓存服务器集群中所有服务器的小部分负载,其总的影响范围和上面讨论过的相同。如图6-13所示。
  在图6-13中.新加入节点NODE3对应的组虚拟节点为V30,V31,V32,加入到一致性Hash环上后,影响V01,V12,V22三个虚拟节点.而这三个虚拟节点分别对应NODEO,NODE1,NODE2三个物理节点。最终Memcached集群中加入个节点,但是同时影响到集群中己存在的三个物理节点,在理想情况下.每个物理节点受影响的数据量(还在缓存中,但是不能被防问到数据)为其节点缓存数据量的1/4(X/(X/ (N-X)),N为原有物理节点数,X为新加入物理节点数).也就是集群中已经被缓存的数据有75%可以被继续命中,和未使用虚拟节点的致性Hash算法结果相同。
  显然每个物理节点对应的虚拟节点越多,各个物理节点之间的负载越均衡,新加入物理服务器对原有的物理服务器的影响越保持一致(这就是致性Hash这个名称的由来)。那么在实践中,一台物理服务器虚拟为多少个虚拟服务器节点合适呢?太多会影响性能,太少又会导致负载不均衡,一般说来,经验值是150,当然根据集群规模和负载均衡的精度需求,这个值应该根据具体隋况具体对待。好了,网站建设公司关于大型网站架构建设之Hash一致性算法的方法本文就分享到这里。谢谢您的关注,博纳网络编辑整理。
文章标题:大型网站建设分布式缓存进行伸缩性设计之一致性Hash算法
本文地址:https://www.198bona.com/news/1677.html
如果您觉得案例还不错请帮忙分享:

网站建设

网络推广

解决方案

域名主机

建站行业资讯