目录
什么是集群
数据分片算法
哈希求余
一致性哈希算法
哈希槽分区算法
集群的处理流程
故障判定
故障迁移
什么是集群
上篇文章的”哨兵“模式, 提⾼了系统的可⽤性. 但是真正⽤来存储数据的还是 master 和 slave 节点. 所有的数据都需要存储在单个 master 和 slave 节点中。/如果数据量很⼤, 接近超出了 master / slave 所在机器的物理内存, 就可能出现严重问题了.
虽然硬件价格在不断降低，可以增加更多更大容量的配置，但是在当前这个“大数据时代”俨然不算什么, 有的时候我们确实需要更⼤的内存空间来保存更多的数据。
如何获取更⼤的空间? 加机器即可! 所谓 "⼤数据" 的核⼼, 其实就是⼀台机器搞不定了, ⽤多台机器来搞。
Redis 的集群就是在上述的思路之下, 引⼊多组 Master / Slave , 每⼀组 Master / Slave 存储数据全集的⼀部分, 从⽽构成⼀个更⼤的整体, 称为 Redis 集群 (Cluster).
假定整个数据全集是 1 TB, 引⼊三组 Master / Slave 来存储. 那么每⼀组机器只需要存储整个
数据全集的 1/3 即可.
在上述图中,
- Master1 和 Slave11 和 Slave12 保存的是同样的数据. 占总数据的 1/3
- Master2 和 Slave21 和 Slave22 保存的是同样的数据. 占总数据的 1/3
- Master3 和 Slave31 和 Slave32 保存的是同样的数据. 占总数据的 1/3
这三组机器存储的数据都是不同的.
每个 Slave 都是对应 Master 的备份(当 Master 挂了, 对应的 Slave 会补位成 Master).
每个红框部分都可以称为是⼀个 分⽚ (Sharding).
如果全量数据进⼀步增加, 只要再增加更多的分⽚, 即可解决.
数据分片算法
Redis cluster 的核⼼思路是⽤多组机器来存数据的每个部分. 那么接下来的核⼼问题就是, 给定⼀个数据 (⼀个具体的 key), 那么这个数据应该存储在哪个分⽚上? 读取的时候⼜应该去哪个分⽚读取?
围绕这个问题, 业界有三种⽐较主流的实现⽅式.
哈希求余
假设有 N 个分⽚, 使⽤ [0, N-1] 这样序号进⾏编号.
针对某个给定的 key, 先计算 hash 值, 再把得到的结果 % N, 得到的结果即为分⽚编号.
后续如果要取某个 key 的记录, 也是针对 key 计算 hash , 再对 N 求余, 就可以找到对应的分⽚编号了.
优点: 简单⾼效, 数据分配均匀.
缺点: ⼀旦需要进⾏扩容, N 改变了, 原有的映射规则被破坏, 就需要让节点之间的数据相互传输, 重新排列, 以满⾜新的映射规则. 此时需要搬运的数据量是⽐较多的, 开销较⼤.
N 为 3 的时候, [100, 120] 这 21 个 hash 值的分布 (此处假定计算出的 hash 值是⼀个简单的整数, ⽅便⾁眼观察)
当引⼊⼀个新的分⽚, N 从 3 => 4 时, ⼤量的 key 都需要重新映射. (某个key % 3 和 % 4 的结果不⼀样,就映射到不同机器上了).
如上图可以看到, 整个扩容⼀共 21 个 key, 只有 3 个 key 没有经过搬运, 其他的 key 都是搬运过的。
一致性哈希算法
key 映射到分⽚序号的过程不再是简单求余了, ⽽是改成以下过程:
第⼀步, 把 0 -> 2^32-1 这个数据空间, 映射到⼀个圆环上（哈希环）. 数据按照顺时针⽅向增⻓.
第⼆步, 假设当前存在三个分⽚, 根据哈希算法将三台主节点的名称对（2^32）取余；将余数映射到哈希环上的对应位置
第三步, 假定有⼀个 key, 计算得到 hash 值 H, 那么这个 key 映射到哪个分⽚呢? 规则很简单, 就是从 H所在位置, 顺时针往下找, 找到的第⼀个分⽚, 即为该 key 所从属的分⽚.
这就相当于, N 个分⽚的位置, 把整个圆环分成了 N 个管辖区间. Key 的 hash 值落在某个区间内, 就归对应区间管理.
在这个情况下, 如果扩容⼀个分⽚, 如何处理呢?
原有分⽚在环上的位置不动, 只要在环上新安排⼀个分⽚位置即可.
此时, 只需要把 0 号分⽚上的部分数据, 搬运给 3 号分⽚即可. 1 号分⽚和 2 号分⽚管理的区间都是不变的.
优点: ⼤⼤降低了扩容时数据搬运的规模, 提⾼了扩容操作的效率.
缺点: 数据分配不均匀 (有的多有的少, 数据倾斜).也有可能多个分片在哈希环上的对应位置比较集中，导致大部分的数据让一个分片承担；
哈希槽分区算法
为了解决上述问题 (搬运成本⾼ 和 数据分配不均匀), Redis cluster 引⼊了哈希槽 (hash slots) 算法.
hash_slot = crc16(key) % 16384相当于是把整个哈希值, 映射到 16384 个槽位上, 也就是 [0, 16383].
然后再把这些槽位⽐较均匀的分配给每个分⽚. 每个分⽚的节点都需要记录⾃⼰持有哪些分⽚.
假设当前有三个分⽚, ⼀种可能的分配⽅式:
- 0 号分⽚: [0, 5461], 共 5462 个槽位
- 1 号分⽚: [5462, 10923], 共 5462 个槽位
- 2 号分⽚: [10924, 16383], 共 5460 个槽位
说明：
- 这⾥的分⽚规则是很灵活的. 每个分⽚持有的槽位也不⼀定连续.
- 每个分⽚的节点使⽤ 位图 来表⽰⾃⼰持有哪些槽位. 对于 16384 个槽位来说, 需要 2048 个字节(2KB) ⼤⼩的内存空间表⽰.
如果需要进⾏扩容, ⽐如新增⼀个 3 号分⽚, 就可以针对原有的槽位进⾏重新分配.
⽐如可以把之前每个分⽚持有的槽位, 各拿出⼀点, 分给新分⽚.
⼀种可能的分配⽅式
0 号分⽚: [0, 4095], 共 4096 个槽位
1 号分⽚: [5462, 9557], 共 4096 个槽位
2 号分⽚: [10924, 15019], 共 4096 个槽位
3 号分⽚: [4096, 5461] + [9558, 10923] + [15019, 16383], 共 4096 个槽位
为什么是 16384 个槽位?
节点之间通过⼼跳包通信. ⼼跳包中包含了该节点持有哪些 slots. 这个是使⽤位图这样的数据结构表⽰的. 表⽰ 16384 (16k) 个 slots, 需要的位图⼤⼩是 2KB. 如果给定的 slots 数更多了, ⽐如65536个了, 此时就需要消耗更多的空间, 8 KB 位图表⽰了. 8 KB, 对于内存来说不算什么, 但是在频繁的⽹络⼼跳包中, 还是⼀个不⼩的开销的.
另⼀⽅⾯, Redis 集群⼀般不建议超过 1000 个分⽚. 所以 16k 对于最⼤ 1000 个分⽚来说是⾜够用的, 同时也会使对应的槽位配置位图体积不⾄于很⼤.
集群的处理流程
故障判定
集群中的所有节点, 都会周期性的使⽤⼼跳包进⾏通信.
1. 节点 A 给 节点 B 发送 ping 包, B 就会给 A 返回⼀个 pong 包. ping 和 pong 除了 message type
属性之外, 其他部分都是⼀样的. 这⾥包含了集群的配置信息(该节点的id, 该节点从属于哪个分⽚,
是主节点还是从节点, 从属于谁, 持有哪些 slots 的位图...).
2. 每个节点, 每秒钟, 都会给⼀些随机的节点发起 ping 包, ⽽不是全发⼀遍. 这样设定是为了避免在节点很多的时候, ⼼跳包也⾮常多(⽐如有 9 个节点, 如果全发, 就是 9 * 8 有 72 组⼼跳了, ⽽且这是按照 N^2 这样的级别增⻓的).
3. 当节点 A 给节点 B 发起 ping 包, B 不能如期回应的时候, 此时 A 就会尝试重置和 B 的 tcp 连接, 看能否连接成功. 如果仍然连接失败, A 就会把 B 设为 PFAIL 状态(相当于主观下线).
4. A 判定 B 为 PFAIL 之后, 会通过 redis 内置的 Gossip 协议, 和其他节点进⾏沟通, 向其他节点确认 B的状态. (每个节点都会维护⼀个⾃⼰的 "下线列表", 由于视⻆不同, 每个节点的下线列表也不⼀定相同).
5. 此时 A 发现其他很多节点, 也认为 B 为 PFAIL, 并且数⽬超过总集群个数的⼀半, 那么 A 就会把 B 标记成 FAIL (相当于客观下线), 并且把这个消息同步给其他节点(其他节点收到之后, 也会把 B 标记成FAIL).
⾄此, B 就彻底被判定为故障节点了.
某个或者某些节点宕机, 有的时候会引起整个集群都宕机 (称为 fail 状态).
以下三种情况会出现集群宕机:
- 某个分⽚, 所有的主节点和从节点都挂了.
- 某个分⽚, 主节点挂了, 但是没有从节点.
- 超过半数的 master 节点都挂了.
故障迁移
上述例⼦中,B 故障, 并且 A 把 B FAIL 的消息告知集群中的其他节点.
如果 B 是从节点, 那么不需要进⾏故障迁移.
如果 B 是主节点, 那么就会由 B 的从节点 (⽐如 C 和 D) 触发故障迁移了.
所谓故障迁移, 就是指把从节点提拔成主节点, 继续给整个 redis 集群提供⽀持.
具体流程如下:
1. 从节点判定⾃⼰是否具有参选资格. 如果从节点和主节点已经太久没通信(此时认为从节点的数据和主节点差异太⼤了), 时间超过阈值, 就失去竞选资格.
2. 具有资格的节点, ⽐如 C 和 D, 就会先休眠⼀定时间. 休眠时间 = 500ms 基础时间 + [0, 500ms] 随机时间 + 排名 * 1000ms. offset 的值越⼤, 则排名越靠前(越⼩).
3. ⽐如 C 的休眠时间到了, C 就会给其他所有集群中的节点, 进⾏拉票操作. 但是只有主节点才有投票资格.
4. 主节点就会把⾃⼰的票投给 C (每个主节点只有 1 票). 当 C 收到的票数超过主节点数⽬的⼀半, C 就会晋升成主节点. (C ⾃⼰负责执⾏ slaveof no one, 并且让 D 执⾏ slaveof C).
5. 同时, C 还会把⾃⼰成为主节点的消息, 同步给其他集群的节点. ⼤家也都会更新⾃⼰保存的集群结构信息.
今天对Redis集群（Cluster）的分享到这就结束了，希望大家读完后有很大的收获，也可以在评论区点评文章中的内容和分享自己的看法；个人主页还有很多精彩的内容。您三连的支持就是我前进的动力，感谢大家的支持！！!