Part A

Extended Raft

raft-extended.pdf

https://github.com/maemual/raft-zh_cn/tree/master

Abstract

Raft一致性算法将一致性问题分解为3个相对独立的子问题

1. 主机选举
2. 日志复制
3. 安全性（状态）

Raft Basics

典型的Raft集群会有5台机器，机器可处于以下三种状态：

1. leader 主机
   1. 处理所有的客户端请求，并将其
2. candidate 候选
3. follower 从机
   1. 如果有客户端请求到达从机，将其重定向到主机。
   2. 被动，只对leader和candidate的请求做出响应。

Raft划分的时期（Term）时长为随机长度，每个时期中，candidate将投票选出最多一个leader。如果投票结果不能确定leader，则重新开始一个新的时期和选举（election）。

不同的机器可能会在不同的时间发现时期之间的过渡（旧时期的结束和新时期开始），甚至可能没有注意到要去选举以及新的时期。时期在这里就像一个逻辑定时器，帮助机器去发现过时的信息（比如过期的leader消息），每台机器将存储一个随时间推移而单调增加的currentTerm变量，代表时期编号，每次机器之间通信时，如果发现自己的时期编号比别人小，那么就跟进新的时期编号。如果机器接受到一个带有过期的时间编号的消息，会拒绝处理请求。

Raft集群机器之间的交流靠RPC，最基本的一致性算法只需要两种RPC：

• RequestVote
  • 由candidate在选举期间发起
• AppendEntries
  • 由leader发起
  • 用来通知follower复制日志条目
  • 还用来做心跳检测（空日志条目）

后面还会介绍一种RPC，用于让follower复制状态快照（snapshot）InstallSnapshot RPC

Leader Election

Raft通过心跳机制来触发leader election

当follower启动后，保持follower状态直到在一段合理的时间内没有收到来自当前leader的心跳消息，（这种现象称为election timeout），就可以推断leader大概挂了，可以进行选举。

选举开始时，follower首先要增加currentTerm以标识新时期的开始，并转为candidate状态。然后它为自己投票且并行地向集群中的其他机器发起RequestVoteRPC。candidate状态只会在以下三种情况中发生转变：

• 自己获得了大部分的来自同一个时期的集群机器的投票，赢得了选举。（每个机器在一个时期中，根据先到先得的方式，投出最多一次票）。赢得选举后，就会转为leader，然后向所有其他服务器发送心跳消息来确立leader权和防止新的选举发生。
• 正在等待投票时，收到了来自其他机器的一个AppendEntriesRPC，如果来源机器的term至少与自己的term一样大，就将其识别为合法的leader，并转为follower状态。否则拒绝比自己的term小的RPC，并继续保持candidate状态。
• 最后一种是选出来的candidate打平了（split votes，分裂投票），那么肯定不会有candidate获得多数人的投票，等会儿每个candidate将超时，就发起新的一轮选举（还是需要增加currentTerm）。
  • 这里存在可能无限重复的打平并发起新投票的可能。
    • 解决方法一：为了从一开始就尽量避免分裂投票，我们通过将candidate的选举超时时长随机化（例如在150-300ms之间），之后也通常只会有一个candidate先超时，然后认为它赢得选举，并发送心跳以组织其他机器超时，这样就极大的减少了split votes的发生。即便分裂投票还是以很小的概率不幸发生了，每个candidate在自己的选举超时后就再次重新随机化自己的选举超时时间，发起新的选举。
    • rank机制，每个机器初始有一个唯一的rank值，当打平后，更高的rank值的机器成为leader，但是会发生一些比较细节的问题，所以第一种更好用。

Log Replication

leader被确认后就开始处理客户机的请求。每个客户机的请求都包含一个需要被副本状态机（replicated state machines）执行的命令，leader将这条命令作为新条目添加到它的log中，然后并行地向其他服务器发起AppendEntriesRPC来复制条目。当条目都被安全地复制后，leader再将这个条目应用到自己的状态机并将执行结果返回给客户端。如果follower挂了或者在磨洋工、网络丢包，leader会在所有follower存储所有的log前一直重试AppendEntriesRPC（即便leader可能已经向客户端做出了回应）。

Log的组织形式如Figure6：每个日志条目存储了一条状态机指令和leader接受它时的term编号，这个term编号用于检测日志之间的一致性去保证Figure3中列出的一些属性。此外，log index作为日志条目在日志中的标识符。

leader可以决定哪些日志条目是可以被安全地应用到状态机中。这些合法的日志条目称为被提交的日志条目（committedentries）。Raft保证提交的条目是持久化的，并且最终会被所有可用的状态机执行。当创建某个条目的leader成功地让大部分服务器复制了这个条目，就会“提交”这个条目及其之前的所有条目。follower直到日志条目被提交后，就会将其应用于自己的状态机。

Raft维护了以下两条属性，这些属性构成了Figure3中的日志匹配属性（Log Mathing Property）

如果不同日志中的两个条目具有相同的index和term

• 那么这两个条目存储的是相同的命令。
  • 一个leader在一个给定的term中最多创建一个具有给定index的条目，并且日志条目永远不会改变它们在日志中的位置。
• 那么上述日志中所有在它们之前的条目也是相同的。
  • 当发送AppendEntries RPC时，leader传日这个日志中紧接着新条目之前的条目的index和term。如果follower在其日志中没有找到具有相同index和term的条目，那么它将拒绝新条目。
  • 日志的初始空状态满足了日志匹配属性，并且每当日志被扩展时，一致性检查都会保留日志匹配属性。因此，每当AppendEntries成功返回时，leader知道follower的日志与自己的日志在新条目之前是相同的。

在正常运行期间，leader和follower的日志保持一致，所以AppendEntries一致性检查从未失败。

然而，leader崩溃会使日志不一致（老leader可能没有完全复制其日志中的所有条目）。这些不一致会在一系列leader和follower的崩溃中加剧。Figure 7 说明了follower的日志可能与新leader的日志不同的方式。follower可能会丢失leader的条目，可能会有leader没有的额外条目，或者两者都有。日志中缺失和多余的条目可能跨越多个terms。

在Raft中，leader通过强迫follower的日志重复自己的日志来处理不一致的情况。这意味着follower日志中的冲突条目将被leader日志中的条目覆盖。为了使follower的日志与自己的日志保持一致，leader必须找到两个日志中最后的保持着一致的日志条目，并删除follower日志中该点之后的任何条目，并将该点之后leader的所有条目发送给follower。

当leader第一次上台时，它将所有的nextIndex值初始化为其日志中最后一条的index。如果follower的日志与leader的日志不一致，那么在下一个AppendEntries RPC中，AppendEntries一致性检查将失败。在拒绝之后，leader会递减NextIndex并重试AppendEntries RPC。最终，nextIndex将达到一个leader和follower日志匹配的点。当这种情况发生时，AppendEntries将成功，这将删除follower日志中任何冲突的条目，并从leader的日志中添加条目（如果有的话）。一旦AppendEntries成功，follower的日志就与leader的日志一致了。

如果愿意的话，协议还可以通过减少失败的Append Entries RPCs次数来进行优化。例如，当拒绝AppendEntries RPCs时，follower可以将冲突的条目的term和此属于该term的第一个条目返回给leader。这样leader就可将nextIndex直接减去所有冲突的条目最早的条目。一个term内的日志条目冲突只需要一次AppendEntries RPCs就可以，而不需要像之前那样每个条目一次AppendEntries RPCs。但是在实际应用中，我们认为此优化时完全没必要的。因为AppendEntries RPCs请求失败并不是经常发生，并且好像也不会有很多冲突的日志条目。

Safety

到目前为止所描述的机制还不足以确保每个状态机以相同的顺序执行完全相同的命令。例如，当leader提交几个日志条目时，一个follower可能无法使用，然后它可能被选为leader，并用新的条目覆盖这些条目，导致不同的状态机可能执行不同的命令序列。

本节通过增加了哪些服务器可以被选为leader的限制，完善了Raft算法。确保了任何给定term的leader都包含了之前term中committed的所有条目（Figure 3中的leader完整性属性）,考虑到选举限制，我们会使committed的规则更加精确。最后，我们提出一个leader完整性属性的证明草图，并说明它如何引导副本状态机的正确行为。

Election restriction（选举限制）

Raft保证从每一个新leader当选的那一刻，以前的所有committed的条目都在其身上，而不需要向这个leader传输什么条目。也就是说日志条目应该只从leader流向follower，且leader不会覆盖自己的条目。

Raft的投票机制只让那些包含了所有committed条目的的candidate可以被选举成功。candidate还要与集群中的大多数进行通信，这意味着每个commit条目至少存在于一个服务器中。如果candidate的日志和不晚于这个大部分群体中的任何一个服务器的日志，那么它也肯定包含所有的commit条目。在RequestVoteRPC中可以传入candidate的信息，投票者来决定是否投票。

**怎么比较日志的新or旧？**Raft通过比较日志中最后的条目的index和term来确定哪个最新。

• 如果最后一个条目的term不同，tern较晚的肯定是新的。
• 如果日志最后的term一样，那么拥有更长的日志的就是最新的。

以前的commit条目

之前说了，一旦一个条目被存储在集群中的大部分服务器上，那么这个条目对就应该在leader上是被提交的。如果一个leader在commit成功前挂了，新的leader会尝试完成对该条目的复制，。虽然这个条目存在大部分的服务器中，但是新leader并不能确认这个之前的条目是否被commit。Figure 8 展示了新leader覆盖旧leader条目的情况

就是为了解决Figure 8的问题，Raft不通过计算条目被复制的数量来提交以前的日志条目。只有leader的当前term的日志条目才这么做，一旦当前term的条目以这种方式被提交，由于日志匹配机制，所有之前的条目被间接提交。

当leader复制前几个term的条目时，日志条目应保持其原来的term。

Safety argument（安全性证明）【反证法】

略

Follower，candidate发生崩溃

follower和candidate的崩溃处理比leader要简单得多，而且它们的处理方式都是一样的。如果一个follower或candidate崩溃了，那么未来发送给它的RequestVote和AppendEntries RPC将会失败。Raft通过无限期地重试来处理这些失败；如果崩溃的服务器重新启动，那么RPC将成功完成。如果服务器在完成RPC后但在响应前崩溃，那么它将在重新启动后再次收到相同的RPC。Raft RPC是幂等的，所以这不会造成任何损失。例如，如果一个follower收到一个AppendEntries请求，其中包括已经存在于其日志中的日志条目，那么它将忽略新请求中的这些条目。

时序与可用性

我们对Raft的要求之一是安全不能依赖于时间：系统不能因为某些事件的发生比预期快或慢而产生不正确的结果。然而，可用性（系统及时响应客户的能力）必须不可避免地取决于时间。例如，如果消息交换的时间超过了服务器崩溃之间的典型时间，那么candidate就不会保持足够长的时间来赢得选举；没有一个稳定的leader，Raft就无法取得进展。

leader选举是Raft中时机最关键的方面。只要系统满足以下时间要求，Raft就能选出并维持一个稳定的leader：<font style="color:rgb(99, 111, 132);background-color:rgb(254, 255, 255);">broadcastTime ≪electionTimeout ≪MTBF</font>

broadcastTime是一台服务器向集群中的每台服务器并行发送RPC并接收其响应的平均时间。

electionTimeout选举超时时间。

``

广播时间和MTBF是底层系统的属性，而选举超时是我们必须选择的。Raft的RPC通常要求接收者将信息坚持到稳定的存储中，所以广播时间可能在0.5ms到20ms之间，这取决于存储技术。因此，选举超时可能是在10ms和500ms之间。一般情况下服务器MTBF是几个月或更长时间，很容易满足时间要求。

集群成员变化

实际情况下我们的集群成员经常变化，比如更换挂了的服务器以及改变复制级别（？）。

任何服务器直接从旧的配置直接转换到新的配置的方案都是不安全的。一次性原子地转换所有服务器是不可能的，所以在转换期间整个集群存在划分成两个独立的大多数群体的可能性。

为了避免这种情况，我们采用二阶段提交更改配置来保证安全。这个二阶段有几种实现方式

• 有的系统采用先禁用旧配置，使得系统停止处理客户端请求，二阶段启用新配置。
• 在Raft中，我们的集群首先切换到一个过渡配置（我们称之为joint consensus，译为：共同一致）一旦这个joint consensus被提交了，系统就会过渡到新配置。

joint consensus结合了旧配置和新配置。

日志压缩

时间久了日志太多肯定不是好事。

• 增量压缩的方法，例如日志清理或者日志结构合并树，都是可行的。这些方法每次只对一小部分数据进行操作，这样就分散了压缩的负载压力。首先，他们先选择一个已经积累的大量已经被删除或者被覆盖对象的区域，然后重写那个区域还活跃的对象，之后释放那个区域。和简单操作整个数据集合的快照相比，需要增加复杂的机制来实现。
• 快照（snapshot）是最简单的压缩方法。在快照系统中，整个系统的状态都以快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃。快照技术被使用在 Chubby 和 ZooKeeper 中，接下来的章节会介绍 Raft 中的快照技术。

Figure 12 展示了 Raft 中快照的基础思想：每个服务器独立地创建快照，只包括commited日志。主要的工作包括将状态机的状态写入到快照中。Raft 也包含一些少量的元数据到快照中：最后被包含索引指的是被快照取代的最后的条目在日志中的index（状态机最后应用的日志），最后被包含的任期指的是该条目的term。保留这些数据是为了支持快照后紧接着的第一个条目的附加日志请求时的一致性检查，因为这个条目需要前一日志条目的索引值和任期号。为了支持集群成员更新（上一小节的内容），快照中也将最后的一次配置作为最后一个条目存下来。一旦服务器完成一次快照，他就可以删除最后索引位置及其之前的所有日志和快照了。

尽管通常服务器都是独立地创建快照，但是leader必须偶尔的发送快照给一些落后的follower。这通常发生在当leader已经丢弃了下一条需要发送的日志条目时。幸运的是这种情况不是常规操作：一个与leader保持同步的follower通常都会有这个条目。然而一个运行非常缓慢的follower或者新加入集群的服务器（第 6 节）将不会有这个条目。这时让这个follower更新到最新的状态的方式就是通过网络把快照发送给他们。

InstallSnapshot RPC

由leader调用，将快照的分块发送给follower。

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

结果	解释
term	当前任期号（currentTerm），便于领导人更新自己

接收者实现：

1. 如果term < currentTerm就立即回复
2. 如果是第一个分块（offset 为 0）就创建一个新的快照
3. 在指定偏移量写入数据
4. 如果 done 是 false，则继续等待更多的数据
5. 保存快照文件，丢弃具有较小索引的任何现有或部分快照
6. 如果现存的日志条目与快照中最后包含的日志条目具有相同的索引值和任期号，则保留其后的日志条目并进行回复
7. 丢弃整个日志
8. 使用快照重置状态机（并加载快照的集群配置）

当跟随者通过这种 RPC 接收到快照时，他必须自己决定对于已经存在的日志该如何处理。通常快照会包含没有在接收者日志中存在的信息。在这种情况下，跟随者丢弃其整个日志；它全部被快照取代，并且可能包含与快照冲突的未提交条目。如果接收到的快照是自己日志的前面部分（由于网络重传或者错误），那么被快照包含的条目将会被全部删除，但是快照后面的条目仍然有效，必须保留。

这种快照的方式背离了 Raft 的强领导人原则，因为跟随者可以在不知道领导人情况下创建快照。但是我们认为这种背离是值得的。领导人的存在，是为了解决在达成一致性的时候的冲突，但是在创建快照的时候，一致性已经达成，这时不存在冲突了，所以没有领导人也是可以的。数据依然是从领导人传给跟随者，只是跟随者可以重新组织他们的数据了。

我们考虑过一种替代的基于领导人的快照方案，即只有领导人创建快照，然后发送给所有的跟随者。但是这样做有两个缺点。第一，发送快照会浪费网络带宽并且延缓了快照处理的时间。每个跟随者都已经拥有了所有产生快照需要的信息，而且很显然，自己从本地的状态中创建快照比通过网络接收别人发来的要经济。第二，领导人的实现会更加复杂。例如，领导人需要发送快照的同时并行的将新的日志条目发送给跟随者，这样才不会阻塞新的客户端请求。

还有两个问题影响了快照的性能。首先，服务器必须决定什么时候应该创建快照。如果快照创建的过于频繁，那么就会浪费大量的磁盘带宽和其他资源；如果创建快照频率太低，他就要承受耗尽存储容量的风险，同时也增加了从日志重建的时间。一个简单的策略就是当日志大小达到一个固定大小的时候就创建一次快照。如果这个阈值设置的显著大于期望的快照的大小，那么快照对磁盘压力的影响就会很小了。

第二个影响性能的问题就是写入快照需要花费显著的一段时间，并且我们还不希望影响到正常操作。解决方案是通过写时复制的技术，这样新的更新就可以被接收而不影响到快照。例如，具有函数式数据结构的状态机天然支持这样的功能。另外，操作系统的写时复制技术的支持（如 Linux 上的 fork）可以被用来创建完整的状态机的内存快照（我们的实现就是这样的）。

客户端交互