Raft 协议（ 一）

Raft 协议

开源代码：https://github.com/wenweihu86/raft-java

Raft 协议是工程上使用比较广泛的一致性， 去中心化的，高可用的分布式协议。

raft 是一个共识算法， 所谓共识算法，是对某个事件达成一致的看法。

Raft 论文

• http://thesecretlivesofdata.com/raft/

Raft 算法简介

• 问题分解 复制集中点一致性这个问题，分解为各个可以被独立解释的子问题。包括 leader election, log replication,  safety , membership changes。
  
• 状态简化 对算法做出一些限制， 减少需要考虑的状态数，使得算法更加清晰。
  

leader election

• leader 所有请求的处理者，接收客户端发起的操作请求，写入本地日志后同步到其他集群其他节点
• follower 请求的被动更新者，从leader 接收更新请求，写入到本地日志。如果客户端的操作请求发送到了发送给 follower, 会先从 follwer 发送到 leader
• candidate 如果 follower 在一定的时间没有接收到 follower 的心跳， 此时进入leader  election, 本节点切换为 candidate 直到选主结束。

状态转移图：

1. 所有节点启动时都是 follower  状态， 在 一段时间如果没有收到来自 leader 的心跳，follower 切换为 candidate , 并发起选举。
2. 如果收到了 majority 的选举票（包含自己的一票），那么切换为 leader 状态。
3. 如果发现其他节点比自己更新，则主动切换为 follower

系统中只会存在一个 leader, 如果一段时间内没有 leader, 那么大家通过选举的方式选出 leader. leader 不停的向 follower 发出心跳，表面 leader 的存活状态， 如果l leader 故障，follower 会切换成 candidate 选举出新 leader。

term

每个 leader 有一个新的履职期， 这个履职期称为一届任期， 叫做 term。

任期（term) 是从选举开始算，然后有一段或长或短的工作期（normal operation), 任期充当了一个逻辑时钟的概念， term3 的意思是还没有选举出 leader就已经结束了， 然后发起了一个新的选举 term4。

选举过程

follower 在 timeout 时间内，没有收到来自 leader 的心跳，则会发起选举：

• 增加节点本地的 current term, 切换为 candidate 状态
• 投自己一票
• 并行的发送给其他节点 RequestVotes RPCs
• 等待其他节点的回复

1. 收到了 大多数选票（majority ),那么赢得选举，切换状态为 leader
2. 被告知别人已经当选，则切换为 follower
3. 一段时间还是没有收到 majority 的投票结果，保持 candidate 状态，重新发出选举。

• 每个任期，一个节点只能投票一次
• 候选人知道的信息不能比自己少
• fisrtcome- first-serverd 先到先得

log replication

当系统有了leader, 系统应用进入了工作区， 客户端的一切请求会发送到 leader, leader 来调度这些并发请求到顺序，并且保证 leader 和 follower 状态的一致性。

raft 的做法就是，将这些请求的顺序告诉 follower, leader 和 follwer 以相同的顺序来执行这些请求， 保持状态一致。所谓强一致性， 并不是指集群中任意时刻状态都一致。而是指一个目标， 让一个分布式系统看起来只有一个数据副本， 并且读写都是原子的， 这样应用层可以忽略系统多个数据间的同步问题。

共识算法，就是来保证一致性的。共识算法保证在小部分节点故障的 <=(N-1)/2 节点故障的情况下，系统仍然可以对外提供服务。

共识算法，是通过复制状态机来实现。所有节点从同一个状态 state 出发，经过相同的 log, 最终达到一致的状态 state.

相同的初始状态+相同的输入 = 相同的结束状态。

Raft 负责保证集群所有节点 log 一致性。leader 具有较强的领导力， 所有 log 都必须交给 leader 节点处理，并由 leader 复制给其他节点。这个过程叫做日志复制。

日志复制机的流程：

leader 选举出来后，就承担了领导整个集群的责任，开始接受客户端请求，并将操作包装成日志，发送给其他节点。

• leader 为客户端提供服务， 客户端的每个请求都包含一条被状态复制机执行的指令。
• leader 把该指令作为一个新的日志附加到自身的日志集合。然后向其他节点发起附加请求条目（AppendEntries RPC)。来要求其他节点将日志附加到自己的本地日志集合中。
• 当这条日志确保被安全复制，即 （N/2 +1) 节点有复制后，leader 将该日志 apply 到他本地的状态机中，然后把操作成功的结果返回给客户端。
• 

每个 logEntry 包含了 command, 还有 leader 的 term ，五个节点的日志并不完全一致， Raft 保证了高可用，但是并不强一致性，而是最终一致性。leader 会不断尝试给 follower 发送 log entries，直到所有节点都相同。raft日志复制: https://raft.github.io/

安全性

对选举的限制

每个 candidate 必须在 RequestVote RPC 中携带自己的最新日志，如果 follower 发现candidate 日志还没有自己的新， 那么就拒绝投给该 candidate

也就是说 candidate 想要赢得选举，必须得到大多数节点的投票，那么它的日志一定不能落后大多数节点。又因为一条日志只有被复制到大多数节点才能被 COMMIT, 也就是说 赢的选举的 candidate 一定拥有所有 commited 节点的日志。

对提交的限制

除了对选举限制外，还需要对 commit 增加一些限制。

当 leader 得知某条日志被集群过半的节点复制成功时，就可以进行 commit，committed 日志一定最终会被状态机 apply。

leader 并不能随时随地 commit 旧任期的留下的日志，即便旧任期已经复制到大部分节点，

上图从左到右按时间顺序模拟了问题场景。

• 阶段a：S1 是 leader，收到请求后将 (term2, index2) 只复制给了 S2，尚未复制给 S3 ~ S5。
• 阶段b：S1 宕机，S5 当选 term3 的 leader（S3、S4、S5 三票），收到请求后保存了 (term3, index2)，尚未复制给任何节点。
• 阶段c：S5 宕机，S1 恢复，S1 重新当选 term4 的 leader，继续将 (term2, index2) 复制给了 S3，已经满足大多数节点，我们将其 commit。
• 阶段d：S1 又宕机，S5 恢复，S5 重新当选 leader（S2、S3、S4 三票），将 (term3, inde2) 复制给了所有节点并 commit。注意，此时发生了致命错误，已经 committed 的 (term2, index2) 被 (term3, index2) 覆盖了。为了避免这种错误，我们需要添加一个额外的限制：

Leader 只允许 commit 包含当前 term 的日志。

针对上述场景，问题发生在阶段c，即使作为 term4 leader 的 S1 将 (term2, index2) 复制给了大多数节点，它也不能直接将其 commit，而是必须等待 term4 的日志到来并成功复制后，一并进行 commit。

• 阶段e：在添加了这个限制后，要么 (term2, index2) 始终没有被 commit，这样 S5 在阶段d将其覆盖就是安全的；要么 (term2, index2) 同 (term4, index3) 一起被 commit，这样 S5 根本就无法当选 leader，因为大多数节点的日志都比它新，也就不存在前边的问题了。

以上便是对算法增加的两个小限制，它们对确保状态机的安全性起到了至关重要的作用。至此我们对 Raft 算法的核心部分，已经介绍完