分布式缓存-一致性哈希算法

3/3/2017来源:C/C++教程人气:2261

写此文的目的   自己本来明明很懂一致性哈希算法,可是在一次面试中却表达不清楚自己的想法。谨以此文记录“心中有千言万语却不知如何表达”的心绪。

算法过程   一致性Hash算法通过一个叫做一致性Hash还的数据结构实现KEY到缓存服务器的Hash映射,如下图所示:   这里写图片描述

  ①先构造一个长度为0~2^32(2的32次幂)个的整数环(又称:一致性Hash环),根据节点名称的Hash值将缓存服务器节点防置在这个Hash环中,如上图中的node1,node2等;   ②根据需要缓存的数据的KEY值计算得到其Hash值,如上图中右半部分的“键”,计算其Hash值后离node2很近;   ③在Hash环上顺时针查找距离这个KEY的Hash值最近的缓存服务器节点,完成KEY到服务器的Hash映射查找,如上图中离右边这个键的Hash值最近的顺时针方向的服务器节点是node2,因此这个KEY会到node2中读取数据;

节点扩容   当缓存服务器集群需要扩容的时候,只需要将新加入的节点名称(如node5)的Hash值放入一致性Hash环中,由于KEY总是顺时针查找距离其最近的节点,因此新加入的节点只影响整个环中的一部分。如下图中所示,添加node5后,只影响右边逆时针方向的三个Key/Value对数据,只占整个Hash环中的一小部分。 这里写图片描述

扩容优点   1. 与普通余数Hash扩容作对比:采用一直性Hash算法时,当3台服务器扩容到4台时,可以继续命中原有缓存数据的概率为75%,远高于普通余数Hash的25%,而且随着集群规模越大,继续命中原有缓存数据的概率也会随之增大。当100台服务器增加1台时,继续命中的概率是99%。虽然,仍有小部分数据缓存在服务器中无法被读取到,但是这个比例足够小,通过访问数据库也不会对数据库造成致命的负载压力;   2. 在资源允许的情况下,可以考虑用对单点的节点部署采用集群部署的方式实现高可用性。

扩容缺陷   1. 扩容之后,必然导致扩容的目标key用不到缓存,这将突然给生成这些缓存的数据库打来巨大的压力,甚至导致数据库服务宕机。此时,我们可以采用预热缓存的方法减小数据库服务器的压力,同时在业务量小的时间段进行扩容;   2. 上面的部署方式还有一个缺陷,添加的节点5只是减轻了节点4的压力,而节点1、节点2、节点3的压力却没有任何的减轻。在业务场景中,一般都是已有结点的压力都快到达饱和的时候需要扩容,此种添加节点扩容的方式不一定能够解决问题;   3. 在哈希算法中,当由于业务量过大导致一个节点失去了缓存的能力,根据其失效转移的方式,如果将会导致其下一个节点的业务压力更大。此种恶性循环的蝴蝶效应将使所有节点全部瘫痪,当然我们会在单节点上使用主从集群实现高可用性;   4. ……

进一步思考部署   脱离哈希环上部署实际节点的构想,在环上部署多个虚拟节点,假设400个,那么每个虚拟节点负责的缓存key的范围就是总范围的1/400。把其中的100份的范围的缓存key分别映射到4个真实节点上。以后扩容,就可以在尽量能够采用原有的缓存的情况下,重新分配这400份的范围缓存的任务量让每个节点分担的缓存量为:N1/N2 份。其中N1为虚拟节点数,N2为实际节点数,结果为取整(除法余数的缓存范围的部分大家自己考虑)。

备注:集群是一些物理机器构成的集合,分布式是一种集群的协作方式,指把业务拆分,让不同的机器一起协作完成业务,例如MaPReduce,5个人搬石头。可以通过集群实现分布式协作模式,但是集群实现协作模式有很多,例如主从模式,负载均衡模式等等。

算法实现 ~待续~