Raft协议

一、目的（与Paxos相同）

保证日志完全相同地复制到多台服务器上，以实现状态机复制的算法。
解决了Paxos的难理解性和工程上的难以实现。

二、名字来源

可靠Reliable、复制Replicated、冗余Redundant、容错Fault-Tolerant——>
R{eliable|eplicated|edundant} And Fault-Tolerant 取首字母Raft。

三、服务器状态

1、领导者：处理所有的客户端请求和日志复制，同一时刻最多只能有一个正常工作的领导者。
2、跟随者
3、候选者：领导者与跟随者之间的状态。

四、基本实现

1、任期

是一个逻辑时间，用来解决时序问题。
每台服务器维护一个currentTerm变量，表示最新任期号，持久化存储。

2、RPC调用

Raft算法中服务器通信主要通过两个RPC调用实现
（1）RequestVoteRPC 领导者选举
（2）AppendEntriesRPC领导者用来复制日志和发送心跳

3、领导者选举

（1）领导者需要周期性向跟随者发送心跳包（空的AppendEntries消息），如果跟随者在选举超时时间（electionTimeout，一般为100-500ms)没有收到任期更大的RPC请求，认为集群中没有领导者，开始新选举。

（2）节点开始竞选流程如下图：

（3）选举过程中需要保证共识算法的两个特性：安全性（只会有一个领导者被选举出来）和活性（最终能选出一个领导者）。
保证安全性：a.每个节点在同一任期只能投一次票，给第一个满足条件的RequestVote请求。需要每个节点新增一个投票信息变量votedFor，表示当前任期头拍给了哪个候选者，为空表示没有投票。votedFor需要持久化存储，否则会导致一个节点投票给不同候选者。
b.获得超过半数投票的才能成为领导者。
保证活性：如果选举失败，使用活锁，即节点随机选择超时时间重试。

4、日志复制

（1）日志格式
每个节点存储自己的日志副本(log[ ]), 日志中的每个日志条目（Log Entry)包括：
索引：该日志条目在整个日志中的位置。
任期号：日志条目首次被领导者创建时的任期。
命令：应用于状态机的命令。

（2）Raft算法通过索引和任期号唯一标识一条日志目录。

（3）日志必须持久化存储
一个节点必须先将日志条目安全写到磁盘中，才能向系统中其他节点发送请求或回复请求。

（3）记录已提交（committed)
如果一条日志被存储在超过半数的节点上，则认为该记录已提交（committed)，意味着状态机可以安全的执行该记录。类似Paxos中的已批准（chosen)。

（4）日志复制流程
客户端发送命令——领导者追加该日志并持久化存储——领导者发送AppendEntries消息——a.超过半数响应，领导者认为该日志已提交，应用apply到自己的状态机，向客户端返回响应。注：领导者位置LeaderCommit参数，一旦提交了一个日志记录，会在后续的AppendEntries消息中通知跟随者。该参数代表领导者已提交的最大日志索引，跟随者也提交小于该值的日志，并应用到自己的状态机。
b.不成功，领导者反复尝试发送AppendEntries消息。

（5）Raft日志特性
a.如果两个节点日志在相同索引位置上任期号相同，认为命令相同，并且从日志开头到这个索引位置之间的日志也都相同。
b.如果给定的记录已提交，那么所有前面的记录也已提交。注：这条是Raft算法和Paxos算法的不同之处，Paxos算法允许日志不连续地提交，但Raft算法的日志必须连续地提交。
一致性检查：为了实现日志特性，Raft算法通过AppendEntries消息来检测之前的一个日志条目——每个AppendEntries消息请求包含新日志条目之前的一个日志条目的索引(prevLogIndex)和任期(prevLogTerm);跟随者收到请求后，会检查自己最后一条日志的索引和任期号是否与请求消息中的prevLogIndex和prevLogTerm相匹配，如果匹配则接收该记录，否则拒绝。

5.领导者更替

Paxos选举领导者是选id最大的服务器。
Raft选择最有可能包含所有已提交日志的节点，即日志最新并且最完整。
方法：候选者C在RequestVote消息中包含自己最后一条日志的索引lastIndex和任期lastTerm，收到投票请求的服务器V，比较谁的日志更完整 （lastTermV > lastTermC ) || (lastTermV == lastTermC) && (lastIndexV > lastIndexC).表示V更新，将拒绝C的投票请求。

三、Raft与Paxos的区别

1.表现形式

Raft提出的目标是可理解性，尝试寻找一种比Paxos更容易学习和理解的方式来描述算法。

2.简单性

（1）Raft按顺序提交日志，Paxos允许日志不按顺序提交，但需要一个协议来填补可能因此出现的日志漏洞。
（2）Raft中的所有日志副本都有相同的索引、任期和命令，而Paxos中这些任期可能有所不同。

3.领导选举算法

Paxos中选举算法是比较服务器id的大小，服务器id较大的节点胜出。