【redis】集群 数据分片算法：哈希求余、一致性哈希、哈希槽分区算法

什么是集群

广义的集群，只要你是多个机器，构成了分布式系统，都可以称为是一个“集群”

• 前面的“主从结构”和“哨兵模式”可以称为是“广义的集群”

此处我们介绍的是狭义的集群，redis 提供的“集群模式”，主要是解决存储空间不足的问题（拓展存储空间）

哨兵模式提高了系统的可用性。但是其本质上还是 redis 的主从节点存储数据。其中就要求一个主节点/从节点，就得存储整个数据的“全集”

• 是用内存存储数据的，内存空间也都有限，很可能出现存储不下的情况

此处关键问题，就是引入多台机器，每台机器存储一部分数据

• 随着机器数目的增加，每个机器存储的数据量就减少了
• 只要机器的规模足够多，就可以存储任意大小的数据了（公司的实力）

不是说光引入多台机器就够了，每个存储数据的机器还需要搭配若干多个从节点

image.png

数据分片算法

每块数据都称为是一个“分片”（上图的每个红框）

哈希求余

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

比如有三个分片：0、1、2

1. 此时就可以针对要插入的 key（redis 都是键值对结构的数据），计算 hash 值（比如 MD5）
2. 再把这个 hash 值余上分片个数 N，就得到了一个下标
3. 此时就可以把这个数据放到该下表对应的分片中了

• hash(key) % N => 0 ，此时这个 key 就要存储在 0 号分片中 后续查询 key 的时候，还是同样的算法
• key 是一样的，hash 函数是一样的，得到的分片值就是一样的

[!quote] MD5 算法 其本身就是一个计算 hash 值的算法，针对一个字符串，里面的内容进行一系列的数学变换，得到的是一个十六进制的数字

• MD5 计算结果是定长的；无论输入的原字符串多长，最终算出的结果就是固定长度
• MD5 计算结果是分散的（哈希函数）；两个原字符串，哪怕大部分都相同，只有一个小的地方不同，算出来的 MD5 值也会差别很大
• MD5 计算结果是不可逆的（加密）；给你原字符串，可以很容易算出 MD5 的值，给你 MD5 的值，很难还原出原始的字符串（理论上是不可行的）

分片搬运

一旦服务器需要扩容，就需要更高的成本了

分片主要目的是为了能提高存储能力，分片越多，能存的数据越多，成本也越高

• 一般都是先搞几个分片（3 个）
• 但是随着业务增长，数据变多了，3 个分片就已经不足以保存了，就需要扩容

但是引入新的分片之后，N 就改变了。hash(key) % N => 0

• 当 hash 函数和 key 都不变的情况下，如果 N 改变了，整体的分片结果仍然会变
• 如果我们发现某个数据，在扩容之后，不应该待在当前的分片中了，就需要搬运

此处我们列出的这些值，可以脑补成 hash(key)。假设当前计算完 hash 值之后，得到的数值正好是 100-120

image.png

• 扩容后，绝大部分 key 都是需要进行搬运的
• 搬运的时候，不仅仅只搬主节点，相关从节点也是都要搬运的，非常麻烦

如果是 20亿 个数据呢？

• 这个级别的扩容，开销极大，往往是不能直接在生产环境上操作的，只能通过“替换”的方式来实现扩容
• 这样依赖的机器更多了，成本更高，操作步骤非常复杂

一致性哈希

可以有效的降低上面搬运的开销

1. 把 0->2^32-1 这个数据空间，映射到一个圆环上，数据按照顺时针方向增长![[Pasted Image 20250326152129_941.png|426]]
2. 假设当前存在三个分片，就把分片放到圆环的某个位置上

image.png|386

1. 假定有一个 key，计算得到 hash 值 H，那么这个 key 映射到哪个分片呢？
   • 就是从 H 所在位置，顺时针往下找，找到的第一个分片，即为该 key 所从属的分片

   

   image.png

这就相当于，N 个分片的位置，把整个圆环分成了 N 个管辖区间，key 的 hash 值落在某个区间内，就归对应区间管理

image.png

• 在哈希求余这种操作中，当前 key 属于哪个分片，是交替的，而这种交替出现就会导致成本变大
  • 101 属于 0
  • 102 属于 1
  • 103 属于 2
• 在一致性哈希这样的设定下，把交替出现改成了连续出现

扩容

原有分片在环上的位置不动，只要在环上新安排一个分片位置即可

image.png

• 此时，只需要把 0 号分片上的部分数据，搬运给 3 号分片即可。1 号和 2 号分片管理的区间都是不变的

优点：大大降低了扩容时数据搬运的规模，提高了扩容操作的效率 缺点：数据分配不均匀（有的多有的少，数据倾斜）

如果一次扩容高多个分片，确实是一个好的思路，可以避免刚才的数据倾斜的情况。总的搬运数量仍然是比最初的 hash 求余的方式更少的

• 最大的问题：领导会给你批这么多机器码？

哈希槽分区算法

redis 真正采用的分片算法

hash_slot crc16(key) % 16384

• crc16 是一种 hash 值的算法
• 16384 是 16 * 1024 => 2^14(16KB)
• hash_slot 是哈希槽
• 相当于是把整个哈希值，映射到 16384 个槽位上，也就是 [0, 16383]，然后再把这些槽位比较均匀的分配给每个分片上，每个分片的节点都需要记录自己持有哪些分片

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

• 0 号分片：[0, 5461]，共 5462 个槽位
• 1 号分片： [5462, 10923]，共 5462 个槽位
• 2 号分片： [10924, 16383]，共 5460 个槽位 虽然不是严格意义的均匀，但是差异非常小。此时这三个分片上的数据就是比较均匀的了

这种算法，本质就是把一致性哈希和哈希求余这两种方法结合了一下

上面只是一种可能的分片方式，实际上分片是非常灵活的。每个分片持有的槽位号，可以使连续的，也可以是不连续的，只要数量差不多

• 此处每个分片都会使用“位图”这样的数据结构，表示出当前有多少槽位号
• 16384 个 bit 位，用每一位 0/1 来区分自己这个分片当前是否持有该槽位号

扩容

如果需要扩容，比如新增一个 3 号分片，就可以针对原有的槽位进行重新分配

比如可以把之前每个分片持有的槽位，各拿出一点，分给新分片。一种可能得分配方式：

• 0 号分片：[0, 4095]，共 4096 个槽位
• 1 号分片：[5462, 9557]，共 4096 个槽位
• 2 号分片：[10924, 15019]，共 4096 个槽位
• 3 号分片：[4096, 5461] + [9558, 10923] + [15019, 16383] ，共 4096 个槽位

我们在实际使用 redis 集群分片的时候，不需要手动指定哪些槽位分配给哪个分片，只要告诉某个分片应该持有多少个槽位即可，redis 会自动完成后续的槽位分配，以及对应的 key 搬运的工作

• 不过也可以手动配置

相关问题

1. redis 集群是最多有 16384 个分片吗？

并非如此，如果每个分片上就只有一个槽位，此时很难保证数据在各个分片上的均衡性

• key 是要先映射到槽位，再映射到分片。如果每个分片包含的槽位较多，如果槽位个数相当，就可以认为是包含的 key 数量相当
• 如果每个分片包含的槽位非常少，槽位个数不一定能直观的反映到 key 的数目
• 有的槽位可能是有多个 key；有的槽位可能是没有 key

实际上 redis 的作者建议集群分片数不应该超过 1000

• 如果真是 1.6w 个分片，整个数据服务器的集群规模就太可怕了，几万台主机构成的集群了，整个集群的可用性是非常堪忧的

1. 槽位数量为什么是 16384

redis 作者的答案： https://github.com/redis/redis/issues/2576 The reason is:

1. Normal heartbeat packets carry the full configuration of a node, that can be replaced in an idempotent way with the old in order to update an old config. This means they contain the slots configuration for a node, in raw form, that uses 2k of space with16k slots, but would use a prohibitive 8k of space using 65k slots.
2. At the same time it is unlikely that Redis Cluster would scale to more than 1000 mater nodes because of other design tradeoffs.

So 16k was in the right range to ensure enough slots per master with a max of 1000 maters, but a small enough number to propagate the slot configuration as a raw bitmap easily. Note that in small clusters the bitmap would be hard to compress because when N is small the bitmap would have slots/N bits set that is a large percentage of bits set.

翻译过来⼤概意思是:

• 节点之间通过⼼跳包通信. ⼼跳包中包含了该节点持有哪些 slots. 这个是使⽤位图这样的数据结构表⽰的. 表⽰ 16384 (16k) 个 slots, 需要的位图⼤⼩是 2KB. 如果给定的 slots 数更多了, ⽐如 65536 个了, 此时就需要消耗更多的空间, 8KB 位图表⽰了. 8KB, 对于内存来说不算什么, 但是在频繁的网络⼼跳包中, 还是⼀个不⼩的开销的.
• 另⼀⽅⾯, Redis 集群⼀般不建议超过 1000 个分⽚. 所以 16k 对于最⼤ 1000 个分⽚来说是⾜够⽤的, 同时也会使对应的槽位配置位图体积不⾄于很⼤
• 虽然 8KB 比 2KB 也打不了多少，但是心跳包是周期性通信的，非常频繁，很吃网络带宽
• 这个值个数上基本够用了，同时占用的硬件资源（网络带宽）又不是很大