docker高级篇2-分布式存储之三种算法

作者：凯哥Java(公众号：凯哥Java)
Docker
时间：2022-12-18 13:23
4753人已阅读

工作小总结&小工具类 Redis AI相关 MQTT Maven mybatis ChatGPT uniapp zookeeper Thymeleaf语法 POI-TL sa-token PowerDesigner16.5 taos数据库 frp echarts Actor模型及Akka thingsboard 大疆无人机对接 CI/CD 教师资格证小任务面试其他职场淘宝客支付宝支付 HBuilder X Flink Java集合类多线程 ES Ribbon eureka Docker java游戏网络通信 Nacos 芋道管理系统 Solr 分布式相关 Dubbo 数据结构 EasyPOI Drools RocketMQ JS 七天深入MySQL实战营书籍 kafka spring Java基础 java web 若依(ruoyi) 分布式事务面试宝典 mysql java8新特性 spring cloud ElasticSearch学习系列 HM_leadnews 即时通讯并发思维&学习 VUE 宝塔面板算法刷题设计模式 RabbitMQ学习系列教程 P3C规范 JVM学习系列反射自定义注解网络美文 PHP源码经验分享资源 git项目 websocket 网赚数据库读写分离测试相关其他随笔 shiro学习系列 fremarker学习系列学习笔录-spring boot 网络文章工作小总结

简介面试题：1~2亿条数据需要缓存，请问如何设计这个缓存案例？答：单机单台100%是不可能的。肯定是分布式缓存的。那么用Redis如何落地？一般有三种方案：哈希取余分区；一致性哈希算法分区；哈希槽分区。如下图：哈希取余分区：对redis的key进行hash后和机器总数取余。公式：has(key)%N这种分区算法的优点：简单粗暴，直接有效。只需要预估好数据规划好节点。就能保证一段时间的数据支撑。使用HA

🔔🔔🔔好消息!好消息!🔔🔔🔔

有需要的朋友👉:联系凯哥微信号 kaigejava2022

面试题：

1~2亿条数据需要缓存，请问如何设计这个缓存案例？

答：单机单台100%是不可能的。肯定是分布式缓存的。那么用Redis如何落地？

插播一条

下面这个公众号是凯哥开发的，福利号：外卖、买菜、电商领Q的

怎么领券？

一般有三种方案：

哈希取余分区；一致性哈希算法分区；哈希槽分区。如下图：

大家好,我是凯哥Java(kaigejava)，乐于分享，每日更新技术文章，欢迎大家关注“凯哥Java”，及时了解更多。让我们一起学Java。也欢迎大家有事没事就来和凯哥聊聊~~~

哈希取余分区：

对redis的key进行hash后和机器总数取余。公式：has(key)%N

这种分区算法的优点：

简单粗暴，直接有效。只需要预估好数据规划好节点。就能保证一段时间的数据支撑。使用HASH算法让固定的一部分请求落到同一台服务器上，这样每台服务器固定处理一部分请求，起到负载均衡+分而治之的作用。

缺点：

原来规划后的节点，进行扩容或者缩容就比较麻烦了。不管是扩容还是缩容，每次数据变更导致几点有变动，映射关系需要重新进行计算。在服务器个数固定不变的时候没问题。如果需要弹性扩容或者故障停机的情况下，原来的取模公式就会发生变化。此时地址经过某个redis机器宕机了。由于机器总数量发生了变化，会导致hash取余全部数据重新洗牌啊！！

一致性哈希算法分区：

一致性hash算法是什么？

一致性hash算法在1997年麻省理工学院提出的，设计目标是为了解决：

分布式缓存数据变动和映射问题。某个机器宕机了，分母数量改变了，自然取余就出问题了。

一致性hash算法能干嘛？

提出一致性hash解决方案。目的是当服务器个数发生变动的时候，尽量减少影响客户端到服务器的映射关系。

都有哪些步骤？

3大步骤。

1：算法构建一致性哈希环；

一致性哈希算法必然有个hash函数并安装算法产生hash值，这个算法的所有可能哈希值会构成一个全量集，这个集合可以成为hash空间，范围是[0,2^32-1]，这是一个线性空间，但是在算法中，通过适当的逻辑控制将其首尾相连（0=2^32）,这样在逻辑上，就形成了一个环形的空间。

一致性哈希环也是使用的取模的方方，是对2^32取模。一致性hash算法将这个哈希值空间组织成一个虚拟的圆环，整个哈希环是按照顺时针方法组织的。如下图：

2：服务器IP节点映射

将集群中的各个IP节点映射到环上的某一个位置。将各个服务器使用hash进行一个hash.(具体可以选择服务器的IP或者主机名称作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置)。例如4个节点NodeA、B、C、D，经过IP地址的哈希环上计算(hash(ip))，使用IP地址哈希后环空间位置如下图：

3：key落到服务器的落键规则

hash环构建了、服务器IP节点也映射了，那么当我们需要存储一个KV键值对的时候，先要计算的是key对应的hash值(hash(key))，将这个key使用相同的函数hash计算出哈希值并确定此数据在环上的位置，从此位置沿着环顺时针"行走",第一遇到的服务器就是其应该定位到的服务器。并将该键值对存储在这个节点上。

例如：我们有ObjA、ObjB、ObjC、ObjD四个数据对象，在经过hash计算之后，在环上分布的空间位置如下图。

根据一致性hash算法，ObjA的数据将会被定位到NodeA上。其他的类推，B将会在NodeB上，C将会在NodeC上，D将会在NodeD上.

一致性hash算法的优点是什么？

1：一致性哈希算法的容错性

假设上图中的NodeC所在的服务器宕机了，可以看到次数对象ABD不会受到影响，只有C队形会被重定位到NodeD的机器上。一般地，在一致性Hash算法中，如果一台服务器不可用了，则受到影响的数据仅仅是对应服务器到其环空间中前一台服务器(也就是沿着逆时针方向行走遇到的第一台服务器)之间的数据而已，其他的数据不会受到影响，简单的来说，就是C服务器挂了，受影响的只是B、C之间的数据，并且这些数据会迁移到D上进行存储。

2：一致性哈希算法的扩展性

所谓的扩展性，就是数据量增加了，则需要增加一台节点NodeX,X的位置在A和B之间，那受到影响的也就是A到X之间的数据，重新把A到X的数据录入到X上即可，不会导致hash重新取余，全部数据重新洗牌.如下图：

一致性hash算法的缺点是什么？

一致性哈希算法的数据倾斜问题

在服务器节点太少的情况下，容易因为节点数据分布不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)的问题。假设系统中只有两台服务器。那么出现数据倾斜就如下图：

总结一致性hash算法：

目的：为了在节点数目发生改变时尽可能少迁移数据。将所有的存储节点排列在相接的hash环上，每个key在计算hash之后，会按照顺时针找到的存储节点存放。而当有节点加入或者退出时候，仅影响该节点在hash环上的顺时针相邻的后续节点。

优点：加入和删除节点只会影响哈希环中顺时针方向相邻的节点，对其他节点无影响。

缺点：数据的分布和节点的位置有关，因为这些节点不是均匀地分布在哈希环上的，所以数据进行存储时候达不到均匀分布效果。可能就出现了数据倾斜问题。

针对上面问题，于是，又有了新的方案。就是接下来要讲的，哈希槽分区。

哈希槽分区

哈希槽是什么？

为什么会出现哈希槽算法？

因为一致性哈希算法的数据倾斜问题，为了解决这个问题。

哈希槽实质上就是一个数组，数组[0,2^14-1]形成hash slot空间。

能干什么？

解决均匀分配的问题，在数据和节点之间又加入了一层，把这一层称为哈希槽(slot),用于管理数据和节点之间的关系。现在就相当于节点上放的是槽，槽里面上的是数据。

槽解决的是粒度问题，相当于是把粒度变大了。这样便于数据移动。

哈希解决的是映射问题，使用key的哈希值来计算所对应槽，便于数据分配。

多少个hash槽：

一个集群中只能有16384个槽。编号为0--16383(0-2^14-1)，这些槽会分配给集群中所有的主节点，分配策略没有要求。可以指定哪个编号的槽分配给哪个主节点。集群会记录节点和槽对应的关系。解决了节点和槽的关系后，接下来就需要对key进行hash值计算，然后对16384取余。余数是几，那么key就落入到对应的槽中。slot=CRC16(key)%16384.以槽为单位移动数据，因为槽的数目是固定的，处理起来比较容器，这样数据迁移问题就解决了.