Raft论文阅读笔记

介绍

Paxos算法较为复杂，并且不易于应用到工业界，因此诞生了Raft算法，其首要目标是可理解性，Raft算法主要分解为几个部分：领导者选举、日志复制、安全性、成员变更等。Raft算法有一些独特的特性：

强领导者：日志entry只从领导者发送给其他服务器
领导者选举：Raft算法采用一个随即计时器来选举领导人
成员关系调整：Raft算法采用一种共同一致的方法来处理集群成员变换的问题，此时集群依然可以工作。

属性解释

状态

所有服务器上的持久性状态

(在响应 RPC 请求之前，已经更新到了稳定的存储设备)

参数	解释
currentTerm	服务器已知最新的任期（在服务器首次启动时初始化为0，单调递增）
votedFor	当前任期内收到选票的 candidateId，如果没有投给任何候选人则为空
log[]	日志条目；每个条目包含了用于状态机的命令，以及领导人接收到该条目时的任期（初始索引为1）

所有服务器上的易失性状态

参数	解释
commitIndex	已知已提交的最高的日志条目的索引（初始值为0，单调递增）
lastApplied	已经被应用到状态机的最高的日志条目的索引（初始值为0，单调递增）

领导人（服务器）上的易失性状态

(选举后已经重新初始化)

参数	解释
nextIndex[]	对于每一台服务器，发送到该服务器的下一个日志条目的索引（初始值为领导人最后的日志条目的索引+1）
matchIndex[]	对于每一台服务器，已知的已经复制到该服务器的最高日志条目的索引（初始值为0，单调递增）

追加条目（AppendEntries）RPC：

由leader调用，用于日志条目的复制，同时也被当做心跳使用

参数	解释
term	领导人的任期
leaderId	领导人 ID 因此跟随者可以对客户端进行重定向（译者注：跟随者根据领导人 ID 把客户端的请求重定向到领导人，比如有时客户端把请求发给了跟随者而不是领导人）
prevLogIndex	紧邻新日志条目之前的那个日志条目的索引
prevLogTerm	紧邻新日志条目之前的那个日志条目的任期
entries[]	需要被保存的日志条目（被当做心跳使用时，则日志条目内容为空；为了提高效率可能一次性发送多个）
leaderCommit	领导人的已知已提交的最高的日志条目的索引

返回值	解释
term	当前任期，对于领导人而言它会更新自己的任期
success	如果跟随者所含有的条目和 prevLogIndex 以及 prevLogTerm 匹配上了，则为 true

receiver的实现

如果term < currentTerm， return false
在接收者日志中如果能找到一个和 prevLogIndex 以及 prevLogTerm 一样的索引和任期的日志条目则继续执行下面的步骤否则return false
如果一个已经存在的条目和新条目发生了冲突，那么就删除这个已经存在的条目以及它之后的所有条目
追加的条目暂未存在日志中
如果leaderCommit > commitIndex，设置commitIndex = min(leaderCommit, index of last new entry)

请求投票（RequestVote）RPC：

由候选人负责调用用来征集选票（5.2 节）

参数	解释
term	候选人的任期号
candidateId	请求选票的候选人的 ID
lastLogIndex	候选人的最后日志条目的索引值
lastLogTerm	候选人最后日志条目的任期号

返回值	解释
term	当前任期号，以便于候选人去更新自己的任期号
voteGranted	候选人赢得了此张选票时为真

receiver的实现

如果term < currentTerm， return false
如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他

服务器规则

所有服务器

如果commitIndex > lastApplied，则 lastApplied 递增，并将log[lastApplied]应用到状态机中
如果接收到的 RPC 请求或响应中，任期号T > currentTerm，则令 currentTerm = T，并切换为跟随者状态

跟随者

响应来自候选人和领导人的请求
如果在超过选举超时时间的情况之前没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志，或者是给某个候选人投了票，就自己变成候选人

候选者

在转变成候选人后就立即开始选举过程
- 自增当前的任期号（currentTerm）
- 给自己投票
- 重置选举超时计时器
- 发送请求投票的 RPC 给其他所有服务器
如果接收到大多数服务器的选票，那么就变成领导人
如果接收到来自新的领导人的附加日志（AppendEntries）RPC，则转变成跟随者
如果选举过程超时，则再次发起一轮选举

领导者

一旦成为领导者，发送空的AppendEntries RPC给其他所有服务器，在一定的空余时间之后不停的重复发送，以防止跟随者超时。
如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端
对于一个跟随者，最后日志条目的索引值大于等于 nextIndex（lastLogIndex ≥ nextIndex），则发送从 nextIndex 开始的所有日志条目：
- 如果成功，更新相应跟随者的nextIndex和matchIndex
- 如果因为日志不一致而失败，则nextIndex递减并重试
假设存在 N 满足N > commitIndex，使得大多数的 matchIndex[i] ≥ N以及log[N].term == currentTerm 成立，则令 commitIndex = N

服务器节点状态

Raft集群中只有三种角色：领导者、候选者、跟随者。Raft算法中每一段任期只有一个领导者节点，每一段任期从一次选举开始，一个或多个候选者参加选举，赢得选举将在接下来的任期充当领导者。跟随者只响应其他服务器的请求。下图为三种状态的转换关系：

Raft节点状态变更关系

领导者选举

Raft 使用一种心跳机制来触发领导人选举。领导者节点会定期向其他节点发送心跳包，如果一个跟随者在一段时间没有接收到信息，这被称为选举超时，此时认为集群中没有可用领导者，并且该节点会发出选举。

选举过程

跟随者增加自己的当前任期并且切换到候选者状态，然后他会并行的向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。候选者会继续保持此状态直到出现以下三种事件：

此候选者赢得了本次选举
其他服务器节点赢得本次选举
无节点赢得选举

选举规则

每个服务器最多会对一个任期号投出一次选票，按照先来先服务的原则，但是要求大多数的选票规则确保最多只有一个候选者赢得选举。
在等待投票的时候，候选者可能会从其他服务器接收到声明它为领导者的AppendEntries RPC，如果这个节点的任期号大于当前候选者的任期号，那么候选者承认领导者合法并回到跟随者状态，如果，否则拒绝本次RPC，并且保持候选者状态。
如果出现候选者票数一样，则增加当前任期号来开始一轮新的选举。（Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况）

日志复制

客户端的每一个请求，领导者节点都需要将该请求封装成一个entry，并且附加到日志中去，然后发起AppendEntries RPC给其他节点，让他们复制这个entry，复制完成后，领导者会将这个entry应用到它的状态机中，然后将执行结果返回给客户端。如果跟随者因为自身原因未完成，领导者会不断尝试发送RPC，直至所有跟随者存储了该entry。

每个entry由任期号和请求组成，任期号用于检查是否出现不一致的情况。如下图所示：

领导者节点对每一个跟随者维护了一个 nextIndex参数，这表示下一个要发送给跟随者的日志entry的index值，当一个候选者成为领导者节点时，它将初始化所有的 nextIndex值为自己的最后一条entry的index + 1。当领导者一致性检查失败后，领导者就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得领导者和跟随者的日志达成一致。

优化：算法可以通过减少被拒绝的附加日志 RPCs 的次数来优化。例如，当附加日志 RPC 的请求被拒绝的时候，跟随者可以(返回)冲突条目的任期号和该任期号对应的最小索引地址。借助这些信息，领导人可以减小 nextIndex 一次性越过该冲突任期的所有日志条目；这样就变成每个任期需要一次附加条目 RPC 而不是每个条目一次。

安全性

选举限制

Raft算法要求选举产生的新领导者拥有最全的日志entry，RequestVote RPC中包含了候选者的日志信息，通过相应的策略选择最全entry的候选者。

时间

集群需要满足以下条件：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

广播时间：从一个服务器并行的发送RPC给集群中的其他服务器并接受响应的平均时间
选举超时时间：一次选举活动允许的最大时间
平均故障间隔时间：两次故障之间的平均时间

日志压缩

几个方法：

快照：将整个系统的状态以快照的形式写入到持久化存储中。然后到那个时间点之前的日志全部丢弃，快照技术被使用在 Chubby 和 ZooKeeper 中。
增量压缩：每次只对一小部分数据进行操作

安装快照 RPC：

由领导人调用以将快照的分块发送给跟随者。领导人总是按顺序发送分块。

参数	解释
term	领导人的任期号
leaderId	领导人的 ID，以便于跟随者重定向请求
lastIncludedIndex	快照中包含的最后日志条目的索引值
lastIncludedTerm	快照中包含的最后日志条目的任期号
offset	分块在快照中的字节偏移量
data[]	从偏移量开始的快照分块的原始字节
done	如果这是最后一个分块则为 true