深入学习 Redis Cluster - 集群是啥，数如何理解据分片算法

古城微笑少年丶 2024-03-26 23:42 9阅读 0赞

**目录**

一、集群模式

1.1、集群是什么，解决了什么问题

1.2、数据分片算法（重点/考点）

1.2.1、哈希求余

a）算法思路

b）面临的问题

1.2.2、一致性哈希算法

a）算法思路

b）面临的问题

1.2.3、哈希槽分区算法（redis使用）

a）算法思想

b）问题一：redis 集群是最多有 16384 个分片么？

c）问题二：为什么是 16384 个槽位

--------------------

## 一、集群模式 ##

--------------------

### 前言 ###

**重点：什么是 redis 集群，解决了什么问题？三种分片算法是什么，优缺点是什么？哈希槽分片算法为什么是 16384槽位，为什么最多是 16384 集群？**

### 1.1、集群是什么，解决了什么问题 ###

集群这个词，有两种说法：

*  广义的集群：只要你是多个机器，构成的分布式系统，都可以成为是一个 “集群”，**也就是说，之前所讲的 主从结构、哨兵模式，也可以称为是一个 “广义的集群”.**
 *  狭义的集群：这个说的就是 redis 提供的集群模式. 这个集群模式之下，主要就是解决，存储空间不足的问题.

> Ps：之前讲到，哨兵模式提高了系统的可用性，本质上还是 redis 主从节点存储数据，也就要求一个主节点/从节点，就得存储整个数据的 “全集”.

**Redis cluster 的核心思路就是多搞几台机器，每台机器只存储全集数据的一部分.**

*例如 有 1TB 的数据需要存储.*

*拿两台机器来存，每个机器只需要 512GB 即可.*

*拿三台机器来存，每个机器只需要 300多 GB 即可.*

*拿四台机器来存，每个机器只需要 256GB 即可.*

*随着机器数量的增加，每个机器存储的数据量就减少了.*

机器足够多了，那么接下来要面临的一个问题就是，如果给你一个 key，你该去哪台机子上存 value 值，或者读取 value 值？这时候就需要使用数据分片算法了~

### 1.2、数据分片算法（重点/考点） ###

关于数据分片算法，有三种主流的分片方式.

#### 1.2.1、哈希求余 ####

##### a）算法思路 #####

哈希求余算法，借鉴了哈希表的基本思想，**借助 hash 函数，把一个 key 映射到整数，在针对数组的长度求余，就可以得到一个数组的下标.**

比如有三个分片，编号 0 1 2

此时就可以针对要插入的数据 key（这里是一个键值对数据），计算 hash 值（比如使用 md5），再把这个 hash 值余上一个分片的个数，就得到了一个下标，此时就可以把这个数据放到下标对应的分片中了.

假设 hash(key) % N = 0，那么此时这个 key 就要存储到 0 号分片中，后续如果查询的 key 是一样的，hash 函数不变，那么得到的分片就是一样的.

> 对 md5 的解释

md5 本身就是一个计算 hash 值的算法，针对一个字符串，里面的内容进行一系列的数字变换，最终得到一个整数.

md5 计算有以下三个特点：

1.  md5 计算结果是定长的：无论输入的原字符串是多长，最终算出的结构都是固定长度.
2.  md5 计算结构式分散的：两个原字符串，哪怕大部分相同，只有一个小的地方不同，算出来的 md5 也会差别很大.
3.  md5 计算的结果不可逆：给你一个原字符串，可以很容易的算出 md5 的值，但是给你 md5 值，很难还原出原始字符串（网上有些 md5 破解，其实就是把常见的字符串用 md5 提前算好，保存下来，然后按照打表的方式，来映射对应的字符串，具体能不能查到，就随缘了）. 基于这一特点，经常用来做加密处理.

##### b）面临的问题 #####

一旦服务器集群需要扩容，那么此时分片越多，数据量越大，扩容的成本越高.

这是为什么？

使用 hash(key) % N 的方式来计算，一旦引入新的分片，N 就改变了. 这也就导致，分片中很多原来的数据，都需要进行重新分配，也就是搬运元素，搬运到其他的分片中.

如下图：

![70e77f77774e4ab5a8ce657b18edbf89.png][]

一共 12 个元素，只有 3 个数据不需要搬运，如果数据量十分庞大，搬运的成本就非常高了.

> Ps：上述级别的扩容，开销极大，是不能直接再生产环境上操作的，只能通过 “替换” 的方式来实现扩容. 但是替换的成本更大，操作很复杂（重新搞原来这么多分片，并把数据都拷贝过来，再在新机器上扩容，扩容好了，再用新机器代替旧机器）.

#### 1.2.2、一致性哈希算法 ####

##### a）算法思路 #####

在 hash 求余算法中，当前 key 属于哪个分片，是交替的，也就是不连续.

在 一致性哈希算法 中，就把 交替出现，改进成了 连续出现.

具体的，**第一步**，把 0 ~ 2^32-1这个数据空间, 映射到⼀个圆环上. 数据按照顺时针⽅向增⻓.

![de2c4341ee3147268fb415d16db82dbf.png][]

**第二步**，假设当前存在三个分⽚, 就把分⽚放到圆环的某个位置上.

![bc3d6e6a46784649b16816f5d327be29.png][]

**第三步**，假设有一个 key，通过 hash 计算出来的值为 value，就把个 value，映射到圆环上，接着顺时针去找，找到第一个分片就是该 key 所在的分片. 这样的分配就类似于下图

![b4cfb28f499049a2998c165601fd084f.png][]

**最后如果，如果需要扩容，**那么原有分⽚在环上的位置不动, 只要在环上新安排⼀个分⽚位置即可，如下

![4efb8eab6dbb44f2b51d21d22ee2ce68.png][]

这时候只需要把 0 号分片上部分数据搬运给 3 号分片即可，其他分片不用动.

##### b）面临的问题 #####

这种算法，虽然搬运的成本低了，但是会导致数据倾斜（这几个分片上的数据量，可能会不均匀）.

#### 1.2.3、哈希槽分区算法（redis使用） ####

##### a）算法思想 #####

**这也是 redis 真正采用的分片算法. 这种算法的本质，就是把 一致性哈希 和 哈希求余 这两种方式结合了一下.**

hash_slot = crc16(key) % 16384

*  hash\_slot：表示哈希槽，有了哈希槽，就可以进一步把这些哈希槽分配到不同分片上.
 *  crc16：也是一种计算 hash 值的算法.
 *  16384：16 \* 1024，也就是 2^14.

相当于是把整个哈希值, 映射到 16384 个槽位上, 也就是 \[0, 16383\]. 然后再把这些槽位⽐较均匀的分配给每个分⽚. 每个分⽚的节点都需要记录⾃⼰持有哪些分⽚.

假设当前有三个分片，一种可能的分配方式如下：

*  0 号分片：\[0, 5461\]，共 5462 个槽位.
 *  1 号分片：\[5462, 10923\]，共 5642 个槽位.
 *  2号分片：\[10924, 16383\]，共 5460 个槽位.

**虽然不是严格意义的 “均匀” 差异非常小，但已经是比较均匀的了. 这只是一种分片方式，实际上分片是非常灵活的，槽位号可以是连续的，也可以是不连续的.**

例如，进⾏扩容, ⽐如新增⼀个 3 号分⽚, 就可以针对原有的槽位进⾏重新分配. ⽐如可以把之前每个分⽚持有的槽位, 各拿出⼀点, 分给新分⽚. ⼀种可能的分配⽅式:

• 0号分⽚: \[0, 4095\], 共 4096 个槽位

• 1号分⽚: \[5462, 9557\], 共 4096 个槽位

• 2号分⽚: \[10924, 15019\], 共 4096 个槽位

• 3号分⽚: \[4096, 5461\] + \[9558, 10923\] + \[15019, 16383\], 共 4096 个槽位

> Ps：每一个分片都会使用 “位图” 这样的数据结构，表示除当前有多少槽位. 16384 个 bit 位，每一位用 0/1 区分是否是自己这个分片当前持有的槽位号.
> 
> 并且，redis 中，当前某个分片包含哪些槽位都是可以手动配置的.

##### b）问题一：redis 集群是最多有 16384 个分片么？ #####

如果是这样，那么极端情况下，**每个分片上就只分配一个槽位，而 key 是要先映射到槽位，在映射到分片的，这就导致很难保证数据在各个分片上的均衡性**，因为有的槽位可能是多个 key，有的槽位可能没有 key，抛开这个不说，**1.6W 个分片，整个服务器的集群规模就相当可怕，几万台主机构成的集群，整个集群的可用性是很低的**（机器越多，越容易出故障）.

> Ps：实际上，Redis 作者建议分片的数目不因该超过 1000.

##### c）问题二：为什么是 16384 个槽位 #####

1.  分片之间是通过心跳包通信的，心跳包中就包含了该分片持有了哪些槽位，如果这个分片中持有的槽位越多，虽然使用位图这种数据结构表示，占用的内存不多，但是心跳包是周期性通信，吃非常吃网络带宽的（网络带宽相比于内存更稀有，更贵重）.
2.  另一方面，这个值基本够用了，占用的网络带宽也不是很大.

![46fc807531e8418696dc7f7a42e98c7b.gif][]

[70e77f77774e4ab5a8ce657b18edbf89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/aeb7c76e5e164ab98b0b41ba9c6b810f.png
[de2c4341ee3147268fb415d16db82dbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/588b1b892c04418c92fe7f11d7680663.png
[bc3d6e6a46784649b16816f5d327be29.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/295cc18d4c6944cb9574ef9dcbb9a774.png
[b4cfb28f499049a2998c165601fd084f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/feaf1e06e0f04143a268129085b232b2.png
[4efb8eab6dbb44f2b51d21d22ee2ce68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/56abba3f41c3416682d483dc0f8ade0c.png
[46fc807531e8418696dc7f7a42e98c7b.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/43835179ff7d42edb382fb484d058c71.png