[TOC]
z
用Redis故障转移实践理解raft协议
本文分为三个部分
第一部分，尽可能以简明的语言阐述raft协议。
第二部分，通过kill掉Redis集群的主节点，以观察集群overfail的全过程，通过实践进一步理解raft协议。
第三部分，探讨raft论文的细节，针对原论文提出一些问题，并自问自答。
最后附上原论文链接，以及有帮助的参考资料。
一、raft解决了什么问题？怎么解决的？
Raft是分布式一致性协议，它是对分布式系统达成共识的一种解决方案，那么什么是分布式系统的共识问题呢？
拜占庭将军问题
这是Lamport（图灵奖得主）在其论文中提出的一个假设故事：
几个拜占庭将军准备攻城。将军们只有两种行动策略：进攻或撤离。将军们需要达成行动共识，因为只有绝大部分将军同时进攻/撤退，行动才能成功，将军可以彼此通信（但没法聚在一起开会）。棘手的是，这其中有不定数量的叛徒将军，叛徒将军将给出完全错误的信息阻碍达成共识。因此我们需要一种策略，使得将军们在叛徒们干扰的情况下，仍能达成共识。
如果将军根据最简单的策略:收到的多数投票行动，将会导致达成共识失败。假设有9位将军投票，其中1名叛徒。一半将军投票进攻，另一半投票撤退，这时候叛徒给4名投进攻的将军投票进攻，而给4名投撤退的将军投票撤退。这样一来在4名投进攻的将军看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤退的将军看来则是5人投撤退。军队达成错误的共识，导致行动失败。
这个假设故事，映射到现实计算机，将军即分布式节点，每个节点可以彼此通信，但无法聚在一起“开会”，并且某节点或者某条通信网路可能出现错误（fault-tolerant），在这种情况下，分布式系统如何达成一致（consensus）？
Raft协议提供的解决方案简单来说是这样的：
Raft 通过首先从节点里选举一个leader，让它有最高权力，比如决定进攻还是撤退，来实现分布式系统的一致性，从节点的唯一任务就是备份主节点的数据。如果leader 宕机或失联，就选举出一个新的leader代替它，参加选举的节点叫candidate。之后如果老的leader重新上线，它会退化成普通节点，接受新leader的命令。
这里我们可知，在raft协议里每个节点有三个状态：leader、follower 或者 candidate 。
那么怎么进行选举呢？这不又回到了拜占庭将军问题吗，没错，这就是raft协议的重点之一，领导选举。下面简述选举过程：
Raft 使用一种心跳机制来触发 leader 选举，节点之间会用心跳保持联系。如果一个 follower 在一段选举超时时间内没有接收到任何消息，它会开始进行选举。首先，follower 先增加自己的当前任期号并且转换到 candidate 状态。然后投票给自己，并且让其他服务器节点投票给它。之后会有三种情况
第一种情况：当一个 candidate 获得集群中过半服务器节点针对同一个任期的投票，它就赢得了这次选举并成为 leader 。要求获得过半投票的规则确保了最多只有一个 candidate 赢得此次选举。
第二种情况：candidate 可能会收到另一个声称自己是 leader 的服务器节点发来的 AppendEntries RPC 。如果这个 leader 的任期号大于 candidate 当前的任期号，那么 candidate 会承认该 leader 的合法地位并回到 follower 状态。 如果 RPC 中的任期号比自己的小，那么 candidate 就会拒绝这次的 RPC 并且继续保持 candidate 状态。
第三种情况： candidate 既没有赢得选举也没有输：如果有多个 follower 同时成为 candidate ，那么选票可能会被瓜分以至于没有 candidate 赢得过半的投票。当这种情况发生时，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举。然而，如果没有其他机制的话，该情况可能会无限重复。我将在第三部分细节探讨raft提供了哪些解决方案避免无限重复选举发生。
这里提到了任期（term）的概念，任期在 Raft 算法中充当逻辑时钟的作用，每一个服务器节点存储一个当前任期号，该编号随着时间单调递增。
二、实践Redis的故障转移
Redis的分布式设计大部分都参考了Raft协议。网上虽然也有Raft协议的动画演示，但我认为以观察Redis的故障转移更能深刻理解Raft协议，毕竟Raft只是学术论文，Redis的分布式设计才是真正落地了的解决方案。
接下来就通过一次模拟Redis故障转移去观察raft协议的整个过程。
建立节点
首先需要租一个云服务器，在云服务器上分别设立Redis主节点、2个从节点和3个哨兵节点 。
| 哨兵 | 主节点 | 从节点 |
|---|---|---|
| 26379 | 6379 | 6380 |
| 26380 | 6381 | |
| 26381 |
建立节点的过程因为和本文主题无关就不帖了。（如果读者有兴趣实践，一个小技巧是：只用租一台服务器，每个节点不同端口，就不用每个节点都租一台服务器了，而且方便查看日志。）
杀掉主节点
开始进入正题，首先干掉主节点，手动制造故障。先.查一下master的进程id ps -ef | grep Redis-server 进程id是22284，然后直接杀掉进程 kill -9 22284
哨兵和各节点之间用用流言协议来监控节点情况，哨兵会持续做如下3件事。
（1）每隔10s确认主从关系。
（2）每隔两秒，哨兵都会通过master节点内部的channel来交换信息（基于发布订阅）。
（3） 每隔一秒每个哨兵对其他的Redis节点（master，slave，哨兵）执行ping操作。
所以当我们kill掉主节点后，哨兵很快就会发现主节点挂掉了。
主观下线和客观下线
什么是主观下线和 客观下线呢？
- sdown 是主观宕机，就一个哨兵如果自己觉得一个 master 宕机了，那么就是主观宕机
- odown 是客观宕机，如果 quorum 数量的哨兵都觉得一个 master 宕机了，那么就是客观宕机
sdown 达成的条件很简单，如果一个哨兵 ping 一个 master，超过了 is-master-down-after-milliseconds 指定的毫秒数之后，就主观认为 master 宕机了；如果一个哨兵在指定时间内，收到了 quorum 数量的其它哨兵也认为那个 master 是 sdown 的，那么就认为是 odown 了。
什么是法定人数（quorum）？法定人数即哨兵决定表决的同意比，可以在sentinel的conf里配置，如下，后面的2就是法定人数
1 | sentinel monitor mymaster 127.0.0.1 6379 2 |
法定人数需要比一般的哨兵数还大，如果小于，法定人数为一半以上的哨兵数。
回到实践中，让我们来查看哨兵26379的日志 cat 哨兵 26379.conf | grep -v "#" | grep -v "^$"，会观察到几条关键日志
首先是哨兵的主观下线（sdown）日志，哨兵26379观察到了主节点6379失联。
22522:X 21 Aug 16:40:38.162 # +sdown master mymaster 127.0.0.1 6379
哨兵们进行通信后，出现了客观下线（odown）日志，表面超过法定人数的哨兵都认为主节点挂了。
1002:X 21 Aug 19:20:43.517 # +odown master mymaster 127.0.0.1 6379 #quorum 3/2
哨兵选举
这个哨兵尝试成为代表哨兵/领导者，为什么要选举呢？因为需要选举出一个哨兵去做故障转移。
哨兵选举的过程如下 ：
- 每个做主观下线的哨兵节点向其他哨兵节点发送命令,要求将它设置为领导者。
- 收到命令的哨兵节点如果没有同意通过其他哨兵节点发送命令,那么将同意该请求，否则拒绝。
- 如果该哨兵节点发现自己的票数已经超过哨兵集合半数且超过quorum,那么它将成为领导者。
- 如果此过程有多个哨兵节点成为了领导者,那么将等待一段时间重新进行选举。
回到实践中，让我们来看看竞选者哨兵的日志，try-failover表示哨兵们确认master下线，要进行故障转移了。其中一个哨兵去竞选，接着它收到了两个哨兵的投票，成功成为领导者。
1 | 998:X 21 Aug 19:20:42.514 # +try-failover master mymaster 127.0.0.1 6379 |
主节点的故障转移
哨兵的选举基本是根据raft协议的，代表哨兵只需要集群达成共识就行，其实哪个哨兵都可以去做。但是新主节点的选举是有条件的，会选举出一个最有“能力”的节点。、
首先如果一个 slave 跟 master 断开连接的时间已经超过了 down-after-milliseconds 的 10 倍，外加 master 宕机的时长，那么 slave 就被认为不适合选举为 master。在剩余的 slave里排序：
- 按照 slave 优先级进行排序，slave priority 越低，优先级就越高。
- 如果 slave priority 相同，那么看 replica offset，哪个 slave 复制了越多的数据，offset 越靠后，优先级就越高。
- 如果上面两个条件都相同，那么选择一个 run id 比较小的那个 slave。
回到实践中，从日志上可以看到，哨兵成为领导者后开始干活，它选择了6381节点作为新的主节点，进行故障转移
1 | 998:X 21 Aug 19:20:42.573 # +elected-leader master mymaster 127.0.0.1 6379 |
slave 配置的自动纠正
哨兵会负责自动纠正 slave 的一些配置，比如 slave 如果要成为潜在的 master 候选人，哨兵会确保 slave 复制现有 master 的数据；如果 slave 连接到了一个错误的 master 上，比如故障转移之后，那么哨兵会确保它们连接到正确的 master 上。
slave上升为master日志中可以发现，这一条配置重写的日志
1 | 989:M 21 Aug 19:20:42.729 # CONFIG REWRITE executed with success. |
##
最后的一条日志标志，master切换完成。
1002:X 21 Aug 19:20:43.759 # +switch-master mymaster 127.0.0.1 6379 127.0.0.1 6381
三、细节探讨
Redis的分布式设计和Raft协议有哪些不同？
虽然本文是用Redis故障转移实践理解raft协议，redis并不是完全基于raft实现的，两者还是有区别的。
两者的一致性级别要求不同：Raft中采用的是QUORUM， 即确保至少大部分节点都接收到写操作之后才会返回结果给Client， 而Redis默认采用的实际上是ANY/ONE, 即只要Master节点写入成功后，就立刻返回给Client，然后该写入命令被异步的发送给所有的slave节点。
Raft怎么避免多个condidate竞争导致的无限重复选举？
当follower判定当前的leader节点故障之后，follower会首先随机休眠一段时间，比如我们设置所有的节点休眠时间为150-300ms之间，即rand(150, 300)，每个节点休眠结束后，便向其他的节点发起拉票。比如A节点先唤醒，唤醒后向B、C节点发起拉票。每个Term期间，每个节点只能至多投一票给别人。
参考资料
拜占庭将军问题：https://www.youtube.com/watch?v=e9KVmyI1eCg&t=303s
Redis与raft相同与不同之处：https://zhuanlan.zhihu.com/p/112651338