Raft算法的成员身份(服务器节点状态)
- 领导者(Leader)：同一时刻只有一个Leader，主要工作有处理写请求、管理日志复制和不断地发送心跳信息
- 跟随者(Follower)：默默接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，主动站出来，推荐自己当候选人
- 候选者(Candidate)：每一个节点都可以成为Candidate，节点在该角色下才可以被选为新的Leader，候选人将向其它节点发送请求投票(RequestVote) RPC消息，通知其它节点来投票，如果赢得了大多数选票，就晋升当领导者
- Raft算法是强领导者模型，集群中只能有一个领导者
- 任何一个节点有且仅有三种状态: Leader、 Follower、 Candidate。 Candidate 是一个中间状态，是正在选举中，选举结束后要么切换到Leader，要么切换到Follower
Raft 算法如何避免 Paxos 的活锁问题？
- Raft 限制为「单点写入」，必须选出一个 Leader，并且任一时刻只允许一个有效的 Leader 存在，所有的写请求都传到 Leader 上，然后由 Leader 同步给超过半数的 Follower
Raft算法中的日志结构是怎样
- 在Raft算法中，副本数据以日志的形式存在，日志是由日志项组成，日志项是一种数据格式，主要包含任期编号(Term)、索引值(Log index)、和用户指定的数据，即指令(Command/Content)
- 任期编号(term)：创建这条日志项的领导者的任期编号，后一条日志的 term >= 前一条日志的 term
- 索引值(index)：日志项对应的整数索引值，用来标识日志项，是一个连续的、单调递增的整数号码
- 指令(command)：一条由客户端请求指定的、状态机需要执行的指令。可理解成客户端指定的数据
- 注意：一届领导者任期，往往有多条日志项。而且日志项的索引值是连续的
什么是任期(term)？
- Raft算法中的领导者也是有任期的，每个任期由单调递增的数字(任期编号)标识，如节点A的任期编号是1。任期编号是随着选举的举行而变化的
- 1.跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，如节点A的当前任期编号为0，那么在推举自己为候选人时，会将自己的任期编号加1
- 2.如果一个服务器节点，发现自己的任期编号比其它节点小，那么它会更新自己的编号到较大的编号值。如节点B的任期编号是0，当收到来自节点A的请求投票RPC消息时，因为信息中包含了结点A的任期编号，且编号为1，那么节点B将把自己的任期编号更新为1
- Raft 算法中的任期不只是时间段，而且任期编号的大小，会影响领导者选举和请求的处理，可解决「脑裂」问题
- 1.在Raft算法中约定，如果一个候选人或领导者，发现自己的任期编号比其它节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为3的领导者节点B，收到来自新领导者的，包含任期编号为4的心跳信息，那么节点B将立即恢复成跟随者状态
- 2.还约定如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。如节点C的任期编号为4，收到包含任期编号为3的请求投票RPC消息，那么它将拒绝这个消息，以此可保证选举时是选日志最新的节点作为 Leader
每个节点上维护的State变量
- log[]
- currentTerm
- votedFor
- 存储在磁盘，当前 term 下，把票投给谁了，一个 term 只能投一次票
- commitIndex
- 存储在内存
- 一条日志被「commit」，指的是这条日志被复制到了多数派的机器。一旦一条日志被认定是「commit」，这条日志将不能被改变和删除
- 这里的日志 commit 设计应用了类似 TCP 协议中的技巧，可称为递增式的 commit。假设 commitIndex = 7 代表 index <= 7 的所有日志都是 commit 状态
- lastApplied
- 存储在内存，记录哪些日志已经被回放到了状态机，lastApplied <= commitIndex，lastApplied 在 Raft 算法本身起始不需要，只是上层的状态机的实现所需要的
- nextIndex[]
- 只存储在Leader 的内存，为每个 Follower 维护一个 nextIndex，即将要同步的日志的起始位置
- matchIndex[]
- 只存储在Leader 的内存，为每个 Follower 维护的，match 日志的最大 index
- nextIndex 和 matchIndex 是[begin, end]关系，这个区间里面的日志意味着要复制但还没有复制给 Follower 的
Raft 的三个阶段
阶段 1：选举阶段：选举出 Leader，其它机器为 Follower
- 过程
- 1.初始化时，所有节点均为Follower状态，等待 Leader 的心跳信息(一个机器成为 Leader 后，会周期性地给其它 Follower 发心跳)。很显然此时没有 Leader，所以收不到心跳消息
- Raft算法实现了随机超时时间的特性，即每个节点等待领导者节点心跳信息的超时时间间隔是随机的。如上图，集群中没有领导者，而节点A的等待超时时间最小(150ms)，它会最先因为没有等到领导者的心跳信息，发生超时
- 2.当 Follower 在给定的时间内收不到 Leader 的消息，将认为 Leader 宕机，然后随机睡眠 0~1000ms 之间的一个值(为了避免大家同时发起选举)，把自己切换成 Candidate 状态，发并向其它节点发送选举请求
- 这时，节点A就增加自己的任期编号，推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者
- 3.其它节点根据接收到的选举请求的先后顺序，回复是否同意成为主。注意这里的每一轮选举中，一个节点只能投出一张票
- 如果其它节点接收到候选人A的请求投票RPC消息，在编号为1的这届任期内，也还没有进行过投票，那么它将把选票投给节点A，并增加自己的任期编号
- 4.若发起选举请求的节点获得超过一半的投票，则成为主节点，其状态转化为Leader，其它节点的状态则由Candidate降为Follower。Leader 周期性地单向往 Follower 发送心跳，以检测节点是否活着
- 如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内的新领导者
- 节点A当选领导者后，将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举，篡权
- 5.当Leader节点的任期到了，即发现其它服务器开始下一轮选主周期时，Leader节点的状态由Leader降级为Follower，进入新一轮选主
- 实现过程
- 处于 Candidate 状态的节点会向所有节点发起一个 RequestVote 的 RPC 调用，如果有超过半数的节点回复 true，则该节点成为 Leader。该 RPC 的具体实现如表
- 这里所说的接收者包括Leader、Follower 和其他Candidate, Candidate会并发地向所有接收者发起该RPC调用，选举结果可能有下面三种：
- 1.收到了多数派的机器返回true， 也就是同意该Candidate成为Leader
- 2.正在选举的时候，收到了某个Leader发来的复制日志的请求，并且term大于或等于自己发起的term，知道自己不用选举了，切换成Follower。如果term小于自己发起的term，则拒绝这个请求，自己仍然是Candidate，继续选举
- 3.没有收到多数派的机器返回true,或者某些机器没有返回,超时了。就仍然处在Candidate状态，过一会儿之后，重新发起选举
- 通过看接受者的处理逻辑就会发现，新选出的 Leader 一定拥有最新的日志。因为只有 Candidate 的日志和接受者一样新，或者比接受者还要新，接受者才会返回 true
- 新旧日志的判断原则为：
- 日志 a 比日志 b 要新，当且仅当符合下面两个条件之一
- a.term > b.term
- a.term == b.term 且 a.index > b.index
- 注：假设有两个Candidate，term = 5，同时发起一次选举。对于Follower来说，先到先得，先收到谁的请求，就把票投给谁。保证对一个term而言，一个Follower 只能投一次票，如果投给了Candidate1，就不能再投给Candidate2。这意味着两个Candidate 可能都得不到多数派的票，就把自己的term自增到6，重新发起一次选举
阶段 2：正常阶段(日志复制)：Leader 接收写请求，然后复制给其它 Followers
- Leader 会并发地向所有的 Follower 发送 AppendEntries RPC 请求，只要超过半数的 Follower 复制成功，就返回给客户端日志写入成功。AppendEntries RPC 的实现如表
- 在这个 RPC 里面，有两个关键的「日志一致性」保证，保证 Leader 和 Follower 日志序列完全一模一样：
- 1.对于两个日志序列里面的两条日志，如果其 index 和 term 都相同，则日志的内容必定相同
- 2.对于两个日志序列，如果在 index = M 处的日志相同，则在 M 之前的所有日志也都完全相同
- 利用这个保证，Follower 接收到日志之后，可以很方便地做一致性检查
- 如果发现自己的日志中没有(prevLogIndex, prevLogTerm)日志，则拒绝接收当前的复制
- 如果发现自己的日志中，某个 index 位置和 Leader 发过来的不一样，则删除 index 之后的所有日志，然后从 index 的位置同步接下来的日志
阶段 3：恢复阶段
- 旧 Leader 宕机，新 Leader 上任，其它 Follower 切换到新的 Leader，开始同步数据
- Follower 是被动的，其实并不会主动发现有新的 Leader 上台了，而是新的 Leader 上台之后，会马上给所有的 Follower 发一个心跳消息(一个空的 AppendEntries消息)，这样每个 Follower 都会将自己的 term 更新到最新的 term。这样旧的 Leader 即使活过来了，也没有机会再写入日志
节点间如何通讯
- 在Raft算法中，服务器节点间的沟通联络采用的是远程过程调用(RPC)，在领导者选举中，需要用到两类RPC：
- 1.请求投票(RequestVote) RPC，由候选人在选举期间发起，通知各节点进行投票
- 2.日志复制(AppendEntries) RPC，由领导者发起，用来复制日志和提供心跳信息
- 注意：日志复制 RPC 只能由领导者发起，这是实现强领导者模型的关键之一
选举有哪些规则
- 1.领导者周期性地向所有跟随者发送心跳信息(即不包含日志项的日志复制RPC消息)，通知大家我是领导者，阻止跟随者发起新的选举
- 2.如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举
- 3.在一次选举中，赢得大多数选票的候选人，将晋升为领导者
- 4.在一个任期内，领导者一直都会是领导者，直到它自身出现问题(如宕机)，或者因为网络延迟，其它节点发起一轮新的选举
- 5.在一次选举中，每一个服务器节点最多会对一个任期编号投出一章选票，并且按照「先来先服务」的原则进行投票。如节点C的任期编号为3，先收到了1个包含任期编号为4的投票请求(来自节点A)，然后又收到了1个包含任期编号为4的投票请求(来自节点B)。那么节点C将会把唯一一张选票投给节点A，当再收到节点B的投票请求RPC 消息时，对于编号为 4 的任期，已没有选票可投了
- 6.当任期编号相同时，日志完整性高的跟随者(即最后一条日志项对应的任期编号值更大，索引号更大)，拒绝投票给日志完整性低的候选人。比如节点B、C的任期编号都是3，节点B的最后一条日志项对应的任期编号为3，而节点C为2，那么当节点C请求节点B投票给自己时，节点B将拒绝投票
- 注意：选举时跟随者发起的，推举自己为候选人；大多数选票是指集群成员半数以上的选票；大多数选票规则的目标，是为了保证在一个给定的任期内最多只有一个领导者
- 除了选举规则外，还需要避免一些会导致选举失败的情况，如同一任期内，多个候选人同时发起选举，导致选票被瓜分，选举失败。在Raft使用随机超时时间来避免这个问题
如何理解随机超时时间
- Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况
- Raft算法的随机超时时间的 2 种含义
- 1.跟随者等待领导者心跳信息超时的时间间隔，是随机的
- 2.当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，即等待选举超时的时间间隔，是随机的
如何复制日志？
- 可把Raft 的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟
- 1.领导者进入第一阶段，通过日志复制(AppendEntries) RPC消息，将日志项复制到其它节点上
- 2.如果领导者接收到大多数的「复制成功」响应后，它将日志项提交到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端
领导者将日志项提交到它的状态机，为什么没通知跟随者提交日志项？
- 这是 Raft 中的一个优化，领导者不直接发送消息通知其它节点提交指定日志项。因为领导者的日志复制RPC消息或心跳消息，包含了当前最大的，将会被提交的日志项索引值。所以通过日志复制RPC消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息
- 因此，当其它节点接受领导者的心跳信息，或者新的日志复制RPC消息后，就会将这条日志项提交到它的状态机。这个优化，降低了处理客户端请求的延迟，将二阶段提交优化为一阶段提交，降低了一半的消息延迟
日志复制过程
- 1.接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中
- 2.领导者通过日志复制RPC，将新的日志项复制到其它的服务器
- 3.当领导者将日志项，成功复制到大多数服务器上的时候，领导者会将这条日志项提交到它的状态机中
- 4.领导者将执行的结果返回给客户端
- 5.当跟随者接收到心跳信息，或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中
如何实现日志的一致？
- 在Raft算法中，，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。即Raft是通过以领导者的日志为准，来实现各节点日志的一致的
- 1.领导者通过日志复制RPC的一致性检查，找到跟随者节点上，与自己想通日志项的最大索引值。即在这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了
- 2.领导者强制跟随者更新覆盖不一致的日志项，实现日志的一致
Raft实现日志的一致的详细过程
- 引入2个新变量
- PrevLogEntry：表示当前要复制的日志项，前面一条日志项的索引值。如在图中，如果领导者将索引值为8的日志项发送给跟随者，那么此时 PrevLogEntry 值为7
- PrevLogTerm：表示当前要复制的日志项，前面一条日志项的任期编号，如在图中，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogTerm值为4
- 1.领导者通过日志复制RPC消息，发送当前最新日志项到跟随者，这个消息的PrevLogEntry值为7，PrevLogTerm值为4
- 2.如果跟随者在它的日志中，找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项，即它的日志和领导者的不一致了，那么跟随者者就会拒绝接收新的日志项， 并返回失败信息给领导者
- 3.这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，这个消息的 PrevLogEntry 值为 6，PrevLogTerm 值为 3
- 4.如果跟随者在它的日志中，找到了 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的日志项，那么日志复制 RPC 返回成功，这样一来，领导者就知道在 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的位置，跟随者的日志项与自己相同
- 5.领导者通过日志复制RPC，复制并更新覆盖索引值后的日志项(即不一致的日志项)，最终实现了集群各节点日志的一致
- 从上面步骤中可以看到，领导者通过日志复制 RPC 一致性检查，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各节点日志的一致。注意，跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志
由 A、B、C 3 个节点组成的 Raft 集群，现需要增加 2 个副本(节点) D、E，那么 Raft 算法如何保障在集群配置变更时，集群能稳定运行，不出现 2 个领导者？
- 成员变更的风险
- 在节点之间发生了分区错误时，可能会出现 2 个领导者
- 单节点变更：通过一次变更一个节点实现成员变更
- 假设节点 A 是领导者，目前的集群配置为[A, B, C]，我们先向集群中加入节点 D，这意味着新配置为[A, B, C, D]。成员变更，是通过这么两步实现的：
- 1.领导者（节点 A）向新节点（节点 D）同步数据
- 2.领导者（节点 A）将新配置[A, B, C, D]作为一个日志项，复制到新配置中所有节点（节点 A、B、C、D）上，然后将新配置的日志项提交到本地状态机，完成单节点变更
- 这样就通过一次变更一个节点的方式，完成了成员变更，保证了集群中始终只有一个领导者，而且集群也在稳定运行，持续提供服务
- 在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的
- 在分区错误、节点故障等情况下，如果并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现 2 个领导者的情况
- 如果你遇到这种情况，可以在领导者启动时，创建一个 NO_OP 日志项（也就是空日志项），只有当领导者将 NO_OP 日志项提交后，再执行成员变更请求
Consul 基于 Raft 实现了哪三种一致性模型
- default：客户端访问领导者节点执行读操作，领导者确认自己处于稳定状态时（在 leader leasing 时间内），返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端是可能读到旧数据的，比如此时发生了网络分区错误，新领导者已经更新过数据，但因为网络故障，旧领导者未更新数据也未退位，仍处于稳定状态
- consistent：客户端访问领导者节点执行读操作，领导者在和大多数节点确认自己仍是领导者之后返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端读到的都是最新数据
- stale：从任意节点读数据，不局限于领导者节点，客户端可能会读到旧数据
应用例子
- Google 开源的 Kubernetes，擅长容器管理与调度，为了保证可靠性，通常会部署 3 个节点用于数据备份。这 3 个节点中，有一个会被选为主，其他节点作为备。Kubernetes 的选主采用的是开源的 etcd 组件。而 etcd 的集群管理器 etcds，是一个高可用、强一致性的服务发现存储仓库，就是采用了 Raft 算法来实现选主和一致性的
优点
- 1.选举速度快、算法复杂度低、易于实现
- 2.选举稳定性比Bully算法好，因为当有新节点加入或节点故障恢复后，会触发选主，但不一定会真正切主，除非新节点或故障后恢复的节点获得投票数过半，才会导致切主
缺点
- 要求系统内每个节点都可以相互通信，且需要获得过半的投票数才能选主成功，因此通信量大
参考
- 分布式协议与算法实战-极客时间
- 分布式技术原理与算法解析-极客时间
- 软件架构设计 大型网站技术架构与业务架构融合之道
