不同于应用服务器集群的伸缩性设计,分布式缓存集群的伸缩性不能使用简单的负载均衡手段来实现。
和所有服务器都部署相同应用的应用服务器集群不同,分布式缓存服务器集群中不同服务器中缓存的数据各不相同,缓存访问请求不可以在缓存服务器集群中的任意一台处理,必须先找到缓存有需要数据的服务器,然后才能访问。
必须让新上线的缓存服务器对整个分布式缓存集群影响最小,也就是说新加入缓存服务器后应使整个缓存服务器集群中已经缓存的数据尽可能还被访问到,这是分布式缓存集群伸缩性设计的最主要目标。
Hash取余算法的优点是实现简单,只需要求得缓存键的hash值与缓存节点数的余数即可确定缓存节点;但该该方法存在伸缩容困难的缺点。
假设原有 3 台缓存服务器,使用hash取余算法作为路由选择方案。
如果要增加 1 台服务器来扩充缓存的容量,此时只有hash值为0,1,2,12,13,14,...的缓存键对应的数据可以命中,以为一个周期,每个周期中存在3个数的hash取余结果保持不变。
因此在扩容一台服务器的情况下将只有大约的缓存数据能够继续命中!
3台服务器扩容至4台服务器,大约有75%被缓存了的数据不能正确命中,随着服务器集群规模的增大,这个比例线性上升。当100台服务器的集群中加入一台新服务器,不能命中的概率是99%()。
这个结果显然是不能接受的,在网站业务中,大部分的业务数据读操作请求事实上是通过缓存获取的,只有少量读操作请求会访问数据库,因此数据库的负载能力是以有缓存为前提而设计的。当大部分被缓存了的数据因为服务器扩容而不能正确读取时,这些数据访问的压力就落到了数据库的身上,这将大大超过数据库的负载能力,严重的可能会导致数据库宕机。
一致性Hash算法通过一个叫作一致性Hash环的数据结构实现KEY到缓存服务器的Hash映射:
具体算法过程为:
当缓存服务器集群需要扩容的时候,只需要将新加入的节点名称(NODE3)的Hash值放入一致性Hash环中,由于KEY是顺时针查找距离其最近的节点,因此新加入的节点只影响整个环中的一小段:
上图中,加入新节点NODE3后,原来的KEY大部分还能继续计算到原来的节点,只有KEY3、KEY0从原来的NODE1重新计算到NODE3。这样就能保证大部分被缓存的数据还可以继续命中。
3台服务器扩容至4台服务器,可以继续命中原有缓存数据的概率是75%,远高于Hash取余算法的25%,而且随着集群规模越大,继续命中原有缓存数据的概率也逐渐增大,100台服务器扩容增加1台服务器,继续命中的概率是99%。
新加入的节点NODE3只影响了原来的节点NODE1,也就是说一部分原来需要访问NODE1的缓存数据现在需要访问NODE3(概率上是50%)。但是原来的节点NODE0和NODE2不受影响,这就意味着NODE0和NODE2缓存数据量和负载压力是NODE1与NODE3的两倍。如果4台机器的性能是一样的,那么这种结果显然不是我们需要的。
怎么办?
计算机领域有句话:计算机的任何问题都可以通过增加一个虚拟层来解决。
解决上述一致性Hash算法带来的负载不均衡问题,也可以通过使用虚拟层的手段:将每台物理缓存服务器虚拟为一组虚拟缓存服务器,将虚拟服务器的Hash值放置在Hash环上,KEY在环上先找到虚拟服务器节点,再得到物理服务器的信息。
这样新加入物理服务器节点时,是将一组虚拟节点加入环中,如果虚拟节点的数目足够多,这组虚拟节点将会影响同样多数目的已经在环上存在的虚拟节点,这些已经存在的虚拟节点又对应不同的物理节点。最终的结果是:新加入一台缓存服务器,将会较为均匀地影响原来集群中已经存在的所有服务器,也就是说分摊原有缓存服务器集群中所有服务器的一小部分负载
在图中,新加入节点NODE3对应的一组虚拟节点为V30,V31,V32,加入到一致性Hash环上后,影响V01,V12,V22三个虚拟节点,而这三个虚拟节点分别对应NODE0,NODE1,NODE2三个物理节点。
先构造一个长度为0~的整数环(这个环被称作一致性Hash环)
根据节点名称的Hash值(其分布范围同样为0~)将缓存服务器节点放置在这个Hash环上
然后根据需要缓存的数据的KEY值计算得到其Hash值(其分布范围也同样为0~),然后在Hash环上顺时针查找距离这个KEY的Hash值最近的缓存服务器节点,完成KEY到服务器的Hash映射查找
具体应用中,这个长度为的一致性Hash环通常使用二叉查找树实现,Hash查找过程实际上是在二叉查找树中查找不小于查找数的最小数值。当然这个二叉树的最右边叶子节点和最左边的叶子节点相连接,构成环。