Redis:分片技术（Redis Cluster）详解
Redis:分片技术（Redis Cluster）详解
Redis Cluster是Redis 3.0版本引入的分布式解决方案，通过分片技术实现数据的水平扩展。本文将详细介绍Redis Cluster的核心概念、数据分片算法、请求重定向机制、状态检测及维护、故障恢复以及扩容缩容等关键内容。
前面两篇文章，主从复制和哨兵机制保障了高可用，就读写分离而言虽然slave节点扩展了主从的读并发能力，但是写能力和存储能力是无法进行扩展，就只能是master节点能够承载的上限。如果面对海量数据那么必然需要构建master（主节点分片)之间的集群，同时必然需要吸收高可用（主从复制和哨兵机制）能力，即每个master分片节点还需要有slave节点，这是分布式系统中典型的纵向扩展（集群的分片技术）的体现；所以在Redis 3.0版本中对应的设计就是Redis Cluster。
Redis集群
Redis 的集群就是引入多组 Master / Slave , 每一组 Master / Slave 存储数据全集的一部分, 从而构成一个更大的整体, 称为 Redis 集群 (Cluster).
- Master1 和 Slave11 和 Slave12 保存的是同样的数据. 占总数据的 1/3
- Master2 和 Slave21 和 Slave22 保存的是同样的数据. 占总数据的 1/3
- Master3 和 Slave31 和 Slave32 保存的是同样的数据. 占总数据的 1/3
每个部分都可以称为是一个分片 (Sharding). 如果全量数据进一步增加, 只要再增加更多的分片, 即可解决。
数据分片算法
Redis cluster 的核心思路是用多组机器来存数据的每个部分. 那么接下来的核心问题就是, 给定一个数 据 (⼀个具体的 key), 那么这个数据应该存储在哪个分片上? 读取的时候又应该去哪个分片读取?
1) 哈希求余
设有 N 个分片, 使用 [0, N-1] 这样序号进行编号.
针对某个给定的 key, 先计算 hash 值, 再把得到的结果 % N, 得到的结果即为分片编号.
优点: 简单高效, 数据分配均匀
缺点: 扩容时数据搬运多,开销大
2) 一致性哈希
第⼀步, 把 0 -> 2^32-1 这个数据空间, 映射到一个圆环上. 数据按照顺时针方向增长.
第二步, 假设当前存在三个分片, 就把分片放到圆环的某个位置上.
第三步, 假定有一个 key, 计算得到 hash 值 H, 那么这个 key 映射到哪个分片呢? 规则很简单, 就是从 H 所在位置, 顺时针往下找,找到的第一个分片,就是key所在的分片。
优点: 大大降低了扩容时数据搬运的规模, 提高了扩容操作的效率.
缺点: 数据分配不均匀 (有的多有的少, 数据倾斜).
3) 哈希槽分区算法(Redis使用)
为了解决上述问题 (搬运成本高 和 数据分配不均匀), Redis cluster 引入了哈希槽 (hash slots) 算法.
hash_slot = crc16(key) % 16384
16384 其实是 16 * 1024, 也就是 2^14
相当于是把整个哈希值, 映射到 16384 个槽位上, 也就是 [0, 16383]. 然后再把这些槽位比较均匀的分配给每个分片. 每个分片的节点都需要记录自己持有哪些分片.
这⾥的分片规则是很灵活的. 每个分片持有的槽位也不一定连续. 每个分片的节点使用 位图 来表⽰自己持有哪些槽位.对于 16384 个槽位来说, 需要 2048 个字 节(2KB) 大小的内存空间表示。
请求重定向
Redis cluster采用去中心化的架构，集群的主节点各自负责一部分槽，客户端如何确定key到底会映射到哪个节点上呢？这就是我们要讲的请求重定向。
在cluster模式下，任意节点对请求的处理过程如下：
- 检查当前key是否存在当前NODE？
- 通过crc16（key）/16384计算出slot
- 查询负责该slot负责的节点，得到节点指针
- 该指针与自身节点比较
- 若slot不是由自身负责，则返回MOVED重定向
- 若slot由自身负责，且key在slot中，则返回该key对应结果
- 若key不存在此slot中，检查该slot是否正在迁出（MIGRATING）？
- 若key正在迁出，返回ASK错误重定向客户端到迁移的目的服务器上
- 若Slot未迁出，检查Slot是否导入中？
- 若Slot导入中且有ASKING标记，则直接操作
- 否则返回MOVED重定向
这个过程中有两点需要具体理解下： MOVED重定向 和 ASK重定向。
#Moved 重定向
- 槽命中：直接返回结果
- 槽不命中：即当前键命令所请求的键不在当前请求的节点中，则当前节点会向客户端发送一个Moved 重定向，客户端根据Moved 重定向所包含的内容找到目标节点，再一次发送命令。
从下面可以看出 php 的槽位9244不在当前节点中，所以会重定向到节点 192.168.2.23:7001中。redis-cli会帮你自动重定向（如果没有集群方式启动，即没加参数 -c，redis-cli不会自动重定向），并且编写程序时，寻找目标节点的逻辑需要交予程序员手动完成。
cluster keyslot keyName # 得到keyName的槽
#ASK 重定向
Ask重定向发生于集群伸缩时，集群伸缩会导致槽迁移，当我们去源节点访问时，此时数据已经可能已经迁移到了目标节点，使用Ask重定向来解决此种情况。
状态检测及维护
Redis Cluster中节点状态如何维护呢？这里便涉及 有哪些状态，底层协议Gossip，及具体的通讯（心跳）机制。
Cluster中的每个节点都维护一份在自己看来当前整个集群的状态，主要包括：
- 当前集群状态
- 集群中各节点所负责的slots信息，及其migrate状态
- 集群中各节点的master-slave状态
- 集群中各节点的存活状态及不可达投票
当集群状态变化时，如
新节点加入
、
slot迁移
、
节点宕机
、
slave提升为新Master
，我们希望这些变化尽快的被发现，传播到整个集群的所有节点并达成一致。节点之间相互的心跳（PING，PONG，MEET）及其携带的数据是集群状态传播最主要的途径。
#Gossip协议
Redis Cluster 通讯底层是Gossip协议，所以需要对Gossip协议有一定的了解。
gossip 协议（gossip protocol）又称 epidemic 协议（epidemic protocol），是基于流行病传播方式的节点或者进程之间信息交换的协议。 在分布式系统中被广泛使用，比如我们可以使用 gossip 协议来确保网络中所有节点的数据一样。
Gossip协议已经是P2P网络中比较成熟的协议了。Gossip协议的最大的好处是，即使集群节点的数量增加，每个节点的负载也不会增加很多，几乎是恒定的。这就允许Consul管理的集群规模能横向扩展到数千个节点。
Gossip算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了Gossip的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的状态都是一致的，当然这也是疫情传播的特点。
上面的描述都比较学术，其实Gossip协议对于我们吃瓜群众来说一点也不陌生，Gossip协议也成为流言协议，说白了就是八卦协议，这种传播规模和传播速度都是非常快的，你可以体会一下。所以计算机中的很多算法都是源自生活，而又高于生活的。
#Gossip协议的使用
Redis 集群是去中心化的，彼此之间状态同步靠 gossip 协议通信，集群的消息有以下几种类型：
Meet
通过「cluster meet ip port」命令，已有集群的节点会向新的节点发送邀请，加入现有集群。
Ping
节点每秒会向集群中其他节点发送 ping 消息，消息中带有自己已知的两个节点的地址、槽、状态信息、最后一次通信时间等。
Pong
节点收到 ping 消息后会回复 pong 消息，消息中同样带有自己已知的两个节点信息。
Fail
节点 ping 不通某节点后，会向集群所有节点广播该节点挂掉的消息。其他节点收到消息后标记已下线。
#基于Gossip协议的故障检测
集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此交换各个节点状态信息，检测各个节点状态：在线状态、疑似下线状态PFAIL、已下线状态FAIL。
自己保存信息：当主节点A通过消息得知主节点B认为主节点D进入了疑似下线(PFAIL)状态时,主节点A会在自己的clusterState.nodes字典中找到主节点D所对应的clusterNode结构，并将主节点B的下线报告添加到clusterNode结构的fail_reports链表中，并后续关于结点D疑似下线的状态通过Gossip协议通知其他节点。
一起裁定：如果集群里面，半数以上的主节点都将主节点D报告为疑似下线，那么主节点D将被标记为已下线(FAIL)状态，将主节点D标记为已下线的节点会向集群广播主节点D的FAIL消息，所有收到FAIL消息的节点都会立即更新nodes里面主节点D状态标记为已下线。
最终裁定：将 node 标记为 FAIL 需要满足以下两个条件：
- 有半数以上的主节点将 node 标记为 PFAIL 状态。
- 当前节点也将 node 标记为 PFAIL 状态。
#通讯状态和维护
我们理解了Gossip协议基础后，就可以进一步理解Redis节点之间相互的通讯心跳（PING，PONG，MEET）实现和维护了。我们通过几个问题来具体理解。
#什么时候进行心跳？
Redis节点会记录其向每一个节点上一次发出ping和收到pong的时间，心跳发送时机与这两个值有关。通过下面的方式既能保证及时更新集群状态，又不至于使心跳数过多：
- 每次Cron向所有未建立链接的节点发送ping或meet
- 每1秒从所有已知节点中随机选取5个，向其中上次收到pong最久远的一个发送ping
- 每次Cron向收到pong超过timeout/2的节点发送ping
- 收到ping或meet，立即回复pong
#发送哪些心跳数据？
- Header，发送者自己的信息
- 所负责slots的信息
- 主从信息
- ip port信息
- 状态信息
- Gossip，发送者所了解的部分其他节点的信息
- ping_sent, pong_received
- ip, port信息
- 状态信息，比如发送者认为该节点已经不可达，会在状态信息中标记其为PFAIL或FAIL
#如何处理心跳？
1，新节点加入
- 发送meet包加入集群
- 从pong包中的gossip得到未知的其他节点
- 循环上述过程，直到最终加入集群
2，Slots信息 - 判断发送者声明的slots信息，跟本地记录的是否有不同
- 如果不同，且发送者epoch较大，更新本地记录
- 如果不同，且发送者epoch小，发送Update信息通知发送者
3，Master slave信息
发现发送者的master、slave信息变化，更新本地状态
4，节点Fail探测(故障发现) - 超过超时时间仍然没有收到pong包的节点会被当前节点标记为PFAIL
- PFAIL标记会随着gossip传播
- 每次收到心跳包会检测其中对其他节点的PFAIL标记，当做对该节点FAIL的投票维护在本机
- 对某个节点的PFAIL标记达到大多数时，将其变为FAIL标记并广播FAIL消息
注：Gossip的存在使得集群状态的改变可以更快的达到整个集群。每个心跳包中会包含多个Gossip包，那么多少个才是合适的呢，redis的选择是N/10，其中N是节点数，这样可以保证在PFAIL投票的过期时间内，节点可以收到80%机器关于失败节点的gossip，从而使其顺利进入FAIL状态。
#将信息广播给其它节点？
当需要发布一些非常重要需要立即送达的信息时，上述心跳加Gossip的方式就显得捉襟见肘了，这时就需要向所有集群内机器的广播信息，使用广播发的场景：
- 节点的Fail信息：当发现某一节点不可达时，探测节点会将其标记为PFAIL状态，并通过心跳传播出去。当某一节点发现这个节点的PFAIL超过半数时修改其为FAIL并发起广播。
- Failover Request信息：slave尝试发起FailOver时广播其要求投票的信息
- 新Master信息：Failover成功的节点向整个集群广播自己的信息
故障恢复（Failover）
master节点挂了之后，如何进行故障恢复呢？
当slave发现自己的master变为FAIL状态时，便尝试进行Failover，以期成为新的master。由于挂掉的master可能会有多个slave。Failover的过程需要经过类Raft协议的过程在整个集群内达到一致， 其过程如下：
- slave发现自己的master变为FAIL
- 将自己记录的集群currentEpoch加1，并广播Failover Request信息
- 其他节点收到该信息，只有master响应，判断请求者的合法性，并发送FAILOVER_AUTH_ACK，对每一个epoch只发送一次ack
- 尝试failover的slave收集FAILOVER_AUTH_ACK
- 超过半数后变成新Master
- 广播Pong通知其他集群节点
扩容&缩容
Redis Cluster是如何进行扩容和缩容的呢？
扩容
当集群出现容量限制或者其他一些原因需要扩容时，redis cluster提供了比较优雅的集群扩容方案。
- 首先将新节点加入到集群中，可以通过在集群中任何一个客户端执行cluster meet 新节点ip:端口，或者通过redis-trib add node添加，新添加的节点默认在集群中都是主节点。
- 迁移数据 迁移数据的大致流程是，首先需要确定哪些槽需要被迁移到目标节点，然后获取槽中key，将槽中的key全部迁移到目标节点，然后向集群所有主节点广播槽（数据）全部迁移到了目标节点。直接通过redis-trib工具做数据迁移很方便。 现在假设将节点A的槽10迁移到B节点，过程如下：
B:cluster setslot 10 importing A.nodeId
A:cluster setslot 10 migrating B.nodeId
循环获取槽中key，将key迁移到B节点
A:cluster getkeysinslot 10 100
A:migrate B.ip B.port "" 0 5000 keys key1[ key2....]
向集群广播槽已经迁移到B节点
cluster setslot 10 node B.nodeId
缩容
缩容的大致过程与扩容一致，需要判断下线的节点是否是主节点，以及主节点上是否有槽，若主节点上有槽，需要将槽迁移到集群中其他主节点，槽迁移完成之后，需要向其他节点广播该节点准备下线（cluster forget nodeId）。最后需要将该下线主节点的从节点指向其他主节点，当然最好是先将从节点下线。