写点什么

5.3 分布式缓存架构:一致性 hash 算法

用户头像
张荣召
关注
发布于: 2020 年 10 月 25 日

1.分布式对象缓存的一致性 hash 算法

           分布式缓存算法:hash 取模余数法

           结果分析: 1.伸缩导致集群失效: 增加服务器后,路由算法改变,原有缓存数据不能被命中

==>缓存集群失效==>请求转向数据库==>数据库压力上升超过最大处理能力

==>数据库崩溃==>应用崩溃==>整个系统崩溃。

                             2.不均衡性:   

           问题焦点:路由算法得到的结果不一致。

           解决方法:一致性 Hash 算法。

 Hash 环:Hash 值范围 1~(2 的 32 次幂-1),首位衔接形成环------范围正整数范围。

 服务器位置计算:服务器取 hash 值,然后存放到环上。

                 NODE0 位置---->"NODE0".hashCode()=10000;

                 NODE1 位置---->"NODE1".hashCode()=20000;

                 NODE2 位置---->"NODE2".hashCode()=40000;


 Key 路由计算:key 取 hash 值,放在环上,顺时针查找最近的服务器。

                "key1".hashCode()=1; "key8".hashCode=10;  

                 =>1,10 顺时针距离 10000(NODE0)的位置最近

                 ==>key1,key8 存放在 NODE0 服务器上;


                 "key2".hashCode()=10001; "key5".hashCode=10010;   

                  =>10001,10010 顺时针距离 20000(NODE1)的位置最近

                  ==>key2,key5 存放在 NODE1 服务器上;


                 "key3".hashCode()=30001; "key4".hashCode=30010; "key6".hashCode=30020;   

                  =>30001,30010,30020 顺时针距离 40000(NODE2)的位置最近

                  ==>key3,key4,key6 存放在 NODE2 服务器上;

2.一致性 hash 节点扩容

      服务器扩容增加服务器 NODE3:

             NODE3 位置:取 Hash 值,存放上环。NODE4.hashCode()=30000;

             key 值存放影响:key3,key6 转移到 NODE3 服务器上。其他 key 值不受影响。

             效果分析: key3,key6 所在的小段受到影响,改变存放到 NODE3.    

                               key3,key6=>NODE3;


                               key1,key8=>NODE0;

                               key2,key5=>NODE1;

                               key4        =>NODE2;

                               ==>增加服务器后,原有的缓存,仍然可以命中(小部分缓存失效:影响小部分 key,这小部分 key 到数据库查找,过段时间数据写入到 NODE3,可以到 NODE3 上访问缓存数据)。

                               ==>解决了"余数 Hash 算法"的问题:增加服务器,大部分缓存失效。  

             问题分析:服务器随机存放位置的不均衡。服务器 Hash 值比较集中。

                              假设:"NODE0".hashCode()=0;  

                                        "NODE1".hashCode()=1;

                                        "NODE2".hashCode()=2;

                                        "NODE3".hashCode()=3;

                              NODE0,NODE1,NODE2,NODE3 比较集中,key 分布集中 NODE0 上,NODE0 压力最大,NODE1,NODE2,NODE3 压力最小,


增加服务器后,并不能平均或者近似平均分摊其他服务器压力。

假设:缓存 key-value 有 600W,三台服务器每台 200W。

增加一台服务器至 4 台服务器:目标均摊 600W,每台服务器 150W。

现状:NODE0=200W;NODE1=200W;NODE2=100W;NODE3=100W;

=>服务器没有差别,但是访问压力不一样,没有达到目的:均衡分摊压力。

核心焦点:1.负载压力不均衡;

2.增加服务器后,压力分摊不均衡。   

解决方法:目的:压力均衡分摊----基于虚拟节点的一致性 Hash 算法。      

3.基于虚拟节点的一致性 hash 算法

        算法:一台物理服务器,虚拟成若干个虚拟节点,随机分布在环上,压力近似均衡分摊。

        示例:NODE0 物理服务器,虚拟为 150 个虚拟节点(v1~v150),随机分配在 Hash 环上 150 个位置上。

                  三台物理服务器,虚拟出 150*3=450 个虚拟节点,随机分配在 Hash 环上。

有长有短,最后平均,可近似均摊压力==>三台服务器负载近似平均。

        扩容:增加一台服务器。先虚拟 150 个节点,随机散落在 Hash 环上

        重点:分布式一致性 Hash 算法是分布式系统,分布式缓存的重要算法。具有重要的意义。        

4.技术栈各个层次的缓存

  • 缓存为什么能显著提升性能

        1.缓存数据通常来自内存,比磁盘上的数据有更快的访问速度。

        2.缓存存储数据的最终形态,不需要中间计算,减少 CPU 的资源消耗。

        3.缓存降低数据库,磁盘,网络的负载压力,使这些 IO 设备获得更好的响应特性。

  • 缓存是系统性能优化的大杀器

        1.技术简单

        2.性能提升显著

        3.应用场景多。

  • 合理使用缓存

         1.频繁修改的数据:这种数据缓存起来,由于频繁修改,还没来得及读就已经失效或者更新,增加系统负担。一般读写比 2:1 以上,缓存才有意义。

         2.没有热点的访问:二八定律:80%的访问在 20%的数据上,缓存 20%的数据。有热点的访问,缓存读写比比较高,缓存有意义。

         3.数据不一致与脏读:

         4.缓存雪崩:

         5.缓存预热:

         6.缓存穿透:访问业务中不存在的数据,缓存中没有保存该数据。 


5.Redis VS Memcached

     1.Redis 支持复杂的数据结构

        2.Redis 支持多路复用异步 I/O-----高性能(Memcached 阻塞式请求)

        3.Redis 支持主从复制-------------高可用(Master 宕机后,请求可转移到 Slave 上)

        4.Redis 原生集群与 Share nothing 集群模式。


Redis 是 Memcached 优化发展出来的。

6.Redis 集群

           1.Redis 集群预分好 16384 个桶,当需要再 Redis 集群中放置一个 key-value 时,

             根据 CRC16(key) mod 16384 的值,决定将一个 key 放到那个桶中。

           2.redis-cluster 把所有的物理节点映射到【0-16383】 slot 上(不一定时平均分配),

             cluster 负责维护 slot 与服务器的映射关系。

           3.客户端与 Redis 节点直连,客户端不需要连接到集群中所有节点,

连接集群中任何一个可用节点即可。

           4.所有的 Redis 节点彼此互联。


           桶<==映射==>服务器

           伸缩操作:添加服务器,现有每台服务器调整一部分桶到新增加的服务器上。



用户头像

张荣召

关注

还未添加个人签名 2018.05.02 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
沙发,slot本身不存储数据,只是管理数据与节点的关系手段👍
2021 年 01 月 19 日 14:33
回复
没有更多了
5.3分布式缓存架构:一致性hash算法