- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

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

凯哥Java 发表于 2022/12/18 13:58:00 2022/12/18

【摘要】面试题：1~2亿条数据需要缓存，请问如何设计这个缓存案例？答：单机单台100%是不可能的。肯定是分布式缓存的。那么用Redis如何落地？一般有三种方案：哈希取余分区；一致性哈希算法分区；哈希槽分区。如下图：大家好,我是凯哥Java(kaigejava)，乐于分享，每日更新技术文章，欢迎大家关注“凯哥Java”，及时了解更多。让我们一起学Java。也欢迎大家有事没事就来和凯哥聊聊~~~哈希取余...

面试题：

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

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

一般有三种方案：

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

大家好,我是凯哥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.以槽为单位移动数据，因为槽的数目是固定的，处理起来比较容器，这样数据迁移问题就解决了.