raft算法是个啥

之前学Redis集群相关知识时候遇到过Raft算法，今天系统的学习一下Raft算法的一些细节。

在继续往下阅读之前可以，先看一个动画，简单了解下Raft算法。或者通过这个实操一下！

Raft概述

对于分布式算法，最经典的莫过于Paxos，但是它过于难懂，并且工程落地性的门槛很高。因此，后来有人又提出了Raft算法。和Paxos相比，它是一种易于理解、实现简单的leader-based共识算法， 算法设计出发点就是可理解性以及工程的落地性，它在性能、可靠性、可用性方面是不输于Paxos的。

共识算法就是保证一个集群的多台机器协同工作，在遇到请求时，数据能够保持一致。即使遇到机器宕机，整个系统仍然能够对外保持服务的可用性
Raft将共识问题分解三个子问题：

• Leader election 领导选举：有且仅有一个leader节点，如果leader宕机，通过选举机制选出新的leader；
• Log replication 日志复制：leader从客户端接收数据更新/删除请求，然后日志复制到follower节点，从而保证集群数据的一致性；
• Safety 安全性：通过安全性原则来处理一些特殊case，保证Raft算法的完备性。

所以，Raft算法核心流程可以归纳为：

• 首先选出leader，leader节点负责接收外部的数据更新/删除请求；
• 然后日志复制到其他follower节点，同时通过安全性的准则来保证整个日志复制的一致性；
• 如果遇到leader故障，followers会重新发起选举出新的leader。

Raft中的角色

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

• Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
• Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
• Candidate：Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。Raft算法角色状态转换如下：

Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息，它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。

Leader Election

Raft算法把时间轴划分为不同任期Term。每个任期Term都有自己的编号TermId，该编号全局唯一且单调递增。如下图，每个任务的开始都 Leader Election 领导选举。如果选举成功，则进入维持任务Term阶段，此时leader负责接收客户端请求并，负责复制日志。Leader和所有follower都保持通信，如果follower发现通信超时，TermId递增并发起新的选举。如果选举成功，则进入新的任期。如果选举失败，TermId递增，然后重新发起选举直到成功。

举个例子，参考下图，Term N选举成功，Term N+1和Term N+2选举失败，Term N+3重新选举成功。

具体的说，Leader在任期内会周期性向其他follower节点发送心跳来维持地位。follower如果发现心跳超时，就认为leader节点宕机或不存在。随机等待一定时间后，follower会发起选举，变成candidate，然后去竞选leader。选举结果有三种情况：
1、获取超过半数投票，赢得选举：

• 当Candidate获得超过半数的投票时，代表自己赢得了选举，且转化为leader。此时，它会马上向其他节点发送请求，从而确认自己的leader地位，从而阻止新一轮的选举；
• 投票原则：当多个Candidate竞选Leader时
  • 一个任期内，follower只会投票一次票，且投票先来先得；
  • Candidate存储的日志至少要和follower一样新（安全性准则），否则拒绝投票。

2、投票未超过半数，选举失败：

• 当Candidate没有获得超过半数的投票时，说明多个Candidate竞争投票导致过于分散，或者出现了丢包现象。此时，认为当期任期选举失败，任期TermId+1，然后发起新一轮选举；
• 上述机制可能出现多个Candidate竞争投票，导致每个Candidate一直得不到超过半数的票，最终导致无限选举投票循环；
• 投票分散问题解决：Raft会给每个Candidate在固定时间内随机确认一个超时时间（一般为150-300ms）。这么做可以尽量避免新的一次选举出现多个Candidate竞争投票的现象。

3、收到其他Leader通信请求：

• 如果Candidate收到其他声称自己是Leader的请求的时候，通过任期TermId来判断是否处理；
• 如果请求的任期TermId不小于Candidate当前任期TermId，那么Candidate会承认该Leader的合法地位并转化为Follower；
• 否则，拒绝这次请求，并继续保持Candidate。

简单地说，Leader Election领导选举通过若干的投票原则，保证一次选举有且仅可能最多选出一个leader，从而解决了脑裂问题。

Log Replication

选举Leader成功后，整个集群就可以正常对外提供服务了。Leader接收所有客户端请求，然后转化为log复制命令，发送通知其他节点完成日志复制请求。每个日志复制请求包括状态机命令 & 任期号，同时还有前一个日志的任期号和日志索引。状态机命令表示客户端请求的数据操作指令，任期号表示leader的当前任期。
follower收到日志复制请求的处理流程：

1、follower会使用前一个日志的任期号和日志索引来对比自己的数据：

• 如果相同，接收复制请求，回复ok；
• 否则回拒绝复制当前日志，回复error。

2、 leader收到拒绝复制的回复后，继续发送节点日志复制请求，不过这次会带上更前面的一个日志任期号和索引；

3、如此循环往复，直到找到一个共同的任期号&日志索引。此时follower从这个索引值开始复制，最终和leader节点日志保持一致；

4、 日志复制过程中，Leader会无限重试直到成功。如果超过半数的节点复制日志成功，就可以认为当前数据请求达成了共识，即日志可以commit提交了。

综上，Log Replication 日志复制有两个特点：

• 如果在不同日志中的两个条目有着相同索引和任期号，则所存储的命令是相同的，这点是由leader来保证的；
• 如果在不同日志中的两个条目有着相同索引和任期号，则它们之前所有条目完全一样，这点是由日志复制的规则来保证的。

举个例子，最上面表示日志索引，这个是保证唯一性。每个方块代表指定任期内的数据操作，目前来看，LogIndex 1-4的日志已经完成同步，LogIndex 5的正在同步，LogIndex6还未开始同步。Raft 日志提交的过程有点类似两阶段原子提交协议2PC，不过和2PC的最大区别是，Raft要求超过一半节点同意即可commited，2PC要求所有节点同意才能commited。

日志不一致问题：在正常情况下，leader和follower的日志复制能够保证整个集群的一致性，但是遇到leader崩溃的时候，leader和follower日志可能出现了不一致的状态，此时follower相比leader缺少部分日志。

为了解决数据不一致性，Raft算法规定follower强制复制leader节日的日志，即follower不一致日志都会被leader的日志覆盖，最终follower和leader保持一致。简单的说，从前向后寻找follower和leader第一个公共LogIndex的位置，然后从这个位置开始，follower强制复制leader的日志。但是这么多还有其他的安全性问题，所以需要引入Safety 安全性规则。

Safety

当前的Leader election 领导选举和Log replication 日志复制并不能保证Raft算法的安全性，在一些特殊情况下，可能导致数据不一致，所以需要引入下面安全性规则。
1、Election Safety 选举安全性：避免脑裂问题

Raft算法规定，所有的数据请求都要交给leader节点处理，要求：

• leader只能日志追加日志，不能覆盖日志；
• 只有leader的日志项才能被提交，follower不能接收写请求和提交日志；
• 只有已经提交的日志项，才能被应用到状态机中；
• 选举时限制新leader日志包含所有已提交日志项。

3、Log Matching 日志匹配特性

这点主要是为了保证日志的唯一性，要求：

• 如果在不同日志中的两个条目有着相同索引和任期号，则所存储的命令是相同的；
• 如果在不同日志中的两个条目有着相同索引和任期号，则它们之间所有条目完全一样。

4、 Leader Completeness 选举完备性：leader必须具备最新提交日志

Raft规定： 只有拥有最新提交日志的follower节点才有资格成为leader节点。 具体做法：candidate竞选投票时会携带最新提交日志，follower会用自己的日志和candidate做比较。

• 如果follower的更新，那么拒绝这次投票；
• 否则根据前面的投票规则处理。这样就可以保证只有最新提交节点成为leader。

因为日志提交需要超过半数的节点同意，所以针对日志同步落后的follower（还未同步完全部日志，导致落后于其他节点）在竞选leader的时候，肯定拿不到超过半数的票，也只有那些完成同步的才有可能获取超过半数的票成为leader。

5、State Machine Safety 状态机安全性：确保当前任期日志提交

考虑到当前的日志复制规则：

• 当前follower节点强制复制leader节点；
• 假如以前Term日志复制超过半数节点，在面对当前任期日志的节点比较中，很明显当前任期节点更新，有资格成为leader。

所以，Raft对日志提交有额外安全机制：leader只能提交当前任期Term的日志，旧任期Term（以前的数据）只能通过当前任期Term的数据提交来间接完成提交。简单的说，日志提交有两个条件需要满足：

• 当前任期；
• 复制结点超过半数。

下面举个例子来解释为什么需要这个原则，如下图：

在阶段a，term为2，S1是Leader，且S1写入日志（term, index）为(2, 2)，并且日志被同步写入了S2；

在阶段b，S1离线，触发一次新的选主，此时S5被选为新的Leader，此时系统term为3，且写入了日志（term, index）为（3， 2）;

S5尚未将日志推送到Followers就离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）可以被提交了。

在阶段d，S1又下线了，触发一次选主，而S5有可能被选为新的Leader（这是因为S5可以满足作为主的一切条件：1. term = 5 > 4，2. 最新的日志为（3，2），比大多数节点（如S2/S3/S4的日志都新），然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了。

增加上述限制后，即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被提交，因为它是来自之前term（2）的日志，直到S1在当前term（4）产生的日志（4， 4）被大多数Followers确认，S1方可提交日志（4，4）这条日志，当然，根据Raft定义，（4，4）之前的所有日志也会被提交。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志（4，4）。

参考资料

1. https://zhuanlan.zhihu.com/p/32052223
2. http://dockone.io/article/2434665