19 分布式缓存集群的伸缩性设计,IDEA太强悍了

2 Memcached分布式缓存集群的伸缩性挑战

由上述讨论可得知,在Memcached分布式缓存系统中,对于服务器集群的管理,路由算法至关重要,和负载均衡算法一样,决定着究竟该访问集群中的哪台服务器。

简单的路由算法可以使用余数Hash:用服务器数目除以缓存数据KEY的Hash值, 余数为服务器列表下标编号。假设图6.10中BEIJING的Hash值是490806430 ( Java中的HashCode()返回值),用服务器数目3除以该值,得到余数1,对应节点NODElo由于 HashCode具有随机性,因此使用余数Hash路由算法可保证缓存数据在整个Memcached 服务器集群中比较均衡地分布。

对余数Hash路由算法稍加改进,就可以实现和负载均衡算法中加权负载均衡一样的加权路由。事实上,如果不需要考虑缓存服务器集群伸缩性,余数Ha

《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

sh几乎可以满足绝 大多数的缓存路由需求。

但是,当分布式缓存集群需要扩容的时候,事情就变得棘手了。

假设由于业务发展,网站需要将3台缓存服务器扩容至4台。更改服务器列表,仍旧使用余数Hash,用4除以EEIJING的Hash值49080643,余数为2,对应服务器NODE2o 由于数据<,BEIJING,DATA>缓存在NODE1,对NODE2的读缓存操作失败,缓存没有命 中。

很容易就可以计算出,3台服务器扩容至4台服务器,大约有75%( 3/4)被缓存了的数据不能正确命中,随着服务器集群规模的增大,这个比例线性上升。当100台服务 器的集群中加入一台新服务器,不能命中的概率是99% (N/(N+1))。

这个结果显然是不能接受的,在网站业务中,大部分的业务数据读操作请求事实上 是通过缓存获取的,只有少量读操作请求会访问数据库,因此数据库的负载能力是以有 缓存为前提而设计的。当大部分被缓存了的数据因为服务器扩容而不能正确读取时,这 些数据访问的压力就落到了数据库的身上,这将大大超过数据库的负载能力,严重的可 能会导致数据库宕机(这种情况下,不能简单重启数据库,网站也需要较长时间才能逐 渐恢复正常。详见本书第13章。)

本来加入新的缓存服务器是为了降低数据库的负载压力,但是操作不当却 导致了数据库的崩溃。如果不对问题和解决方案有透彻了解,网站技术总有想 不到的陷阱让架构师一脚踩空。遇到这种情况,用某网站一位资深架构师的话说,就是“一股寒气从脚底板窜到了脑门心”。

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

能不能通过改进路由算法,使得新加入的服务器不影响大部分缓存数据的正确命中 呢?目前比较流行的算法是一致性Hash算法。


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

一致性Hash算法通过一个叫作一致性Hash环的数据结构实现KEY到缓存服务器的 Hash映射,如图6.11所示。

19 分布式缓存集群的伸缩性设计,IDEA太强悍了

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

在图 6.11 中,假设 N0DE1 的 Hash 值为 3,594,963,423, NODE2 的 Hash 值为1,845,328,979,而KEYO的Hash值为2,534,256,785,那么KEYO在环上顺时针查找,找

到的最近的节点就是NODEl。

当缓存服务器集群需要扩容的时候,只需要将新加入的节点名称(NODE3 )的Hash 值放入一致性Hash环中,由于KEY是顺时针查找距离其最近的节点,因此新加入的节点只影响整个环中的一小段,如图6.12中深色一段。

19 分布式缓存集群的伸缩性设计,IDEA太强悍了

假设 NODE3 的 Hash 值是 2,790,324,235,那么加入 NODE3 后,KEY0( Hash 值 2,534, 256,785 )顺时针查找得到的节点就是NODE3。

图6.12中,加入新节点NODE3后,原来的KEY大部分还能继续计算到原来的节点, 只有KEY3、KEY0从原来的NODE1重新计算到NODE3。这样就能保证大部分被缓存的 数据还可以继续命中。3台服务器扩容至4台服务器,可以继续命中原有缓存数据的概率 是75%,远高于余数Hash的25%,而且随着集群规模越大,继续命中原有缓存数据的概率也逐渐增大,100台服务器扩容增加1台服务器,继续命中的概率是99%。虽然仍有小 部分数据缓存在服务器中不能被读到,但是这个比例足够小,通过访问数据库获取也不 会对数据库造成致命的负载压力。

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

但是,上面描述的算法过程还存在一个小小的问题。

新加入的节点NODE3只影响了原来的节点NODE1,也就是说一部分原来需要访问NODE1的缓存数据现在需要访问N0DE3 (概率上是50% )。但是原来的节点NODEO和NODE2不受影响,这就意味着NODEO和NODE2缓存数据量和负载压力是NODE1与NODE3的两倍。如果4台机器的性能是一样的,那么这种结果显然不是我们需要的。

怎么办?

上一篇:Android面试刨根问底之常用源码篇(一),Android开发教程


下一篇:Java安全学习笔记--反序列化利用链HashMap类源码简单分析