[toc]

Raft 论文解读

Q&A

Q: 如果一个older leader不知道新的leader被选出来了怎么办？

A : 因为new leader被选出，那么或有超过一半的服务器知道有新的leader了，所以当older leader发送AppendEntries RPC时，不会有超过一半的accept，所以该entry不会被提交，但是会在少部分服务器的log中存在

1. Introduction

提到了Paxos算法非常困难而raft比较容易理解，最初raft发明的初衷是understandbility,希望这个算法容易理解。

在设计Raft的时候为了简单做了一些分解，将leader election, log replication 和 safety这三个部分拆开，另外还做了一些state space reduction(相比较于Paxos，raft减少了一些不确定性和servers互相通信保持一致的方法)。

Raft和Viewstamped Replication有很多相似，但是多了下面的一些新特性

• strong leader: Raft使用一个更强制的leader属性，例如log只能从leader发送到其他的server
• leader election：Raft使用随机timer来选举leader，通过稍微修改一下心跳包的机制来实现
• membership changes：Raft使用一种新的机制joint consensus来解决集群中服务器的变化，通过两次term之间服务器会有重叠的方法

2. Replicated state machines

[图片上传失败...(image-8a68ba-1652515917505)]

replicated state machine 在single leader的系统中经常使用，每一个server都会有一个operation log记录操作，leader接收client的操作，通过一个共识模块来保证所有follower的log中日志和leader是一样的，这样的结果就是，所有的机器都按同样的顺序执行相同的指令，理论上来说这样下来所有机器的状态也都是相同的，就达到了replication的目的

3. What's wrong with Paxos?

Paxos的优点：支持多决策(multi-Paxos)，safety，liveness(?不理解，中文是活跃性)，支持集群中的服务器发生更改，被证明是正确的并且是高效的

Paxos的缺点：1.很难理解，作者认为是Paxos将每一个操作都单独看成一个单独的决策而导致的，Paxos算法的两个阶段不够直观并且不能够单独开来理解，multi-Paxos算法更是增加了额外的复杂度。 2. 很难构建一个这样的系统实现，一个原因是因为原作者之提出了single-decree Paxos，对于multi-Paxos只提了一个草图，而不同的人对于multi-Paxos提出了不同的算法。另外由于最初的Paxos论文是single-decree的也就是说，每次只做一个决定，这和现实生活是不一样的，所有人们往往都是从Paxos算法开始，最后的结果和Paxos算法有很大的区别。另外，因为Paxos算法是没有leader的，这在做多决策的时候，往往有一个leader来协调这些决策会使得系统设计更加的简单

4. Designing for understandability

Raft的设计目标：

• 提供完整实际的基础来帮助构建系统，减少设计者的复旦
• 在所有情况下都是安全的，并且在大多数情况下可用
• 在通常情况下高效
• 最重要的目标：understandility，容易理解，并且非常直观

在设计时使用两种主要的技术

1. decomposition：将问题分解成可以被相对独立的解决和解释的子问题，raft将一致性分解为了leader election, log replication, safety, and membership changes这些问题
2. simplify the state space：减少状态空间，大概的意思就是减少需要考虑的情况，减少nondeterministic的情况。在raft设计中，logs不允许有holes(空位)，并且限制了servers之间可能出现不一致的情况数量。虽然nondeterministic是不可避免的，例如随机化就会导致不确定性，设计者采用“choose any; it doesn’t matter”的思想来解决这些问题。

5. The Raft consensus algorithm

raft将共识的问题分解为三个子问题：

• Leader election：一个新的leader要被选出，在当前的leader宕机时
• Log replication：leader必须要接受client的请求并且将他们复制到集群上，强迫其他服务器的log和自己一致
• Safety：如果一个server的log在index I上放的是操作A，任何其他server在该index上都是放的操作A

5.1 Raft basics

一个Raft集群会包含许多servers(通常是5个，这样可以容忍2台服务器宕机)。

[站外图片上传中...(image-2315e9-1652515917505)]

一台服务器有以下三个状态，leader，follower和candidate，只有leader才处理clients的请求，并将它们转发给其他follower，follower是被动的，不会发出请求，只会回复leader和candidate的请求。candidate是为了选出新的leader的状态。

[图片上传失败...(image-941a04-1652515917505)]

raft将时间分为一个个term(任期)，用连续的数字来表示，每一个任期由一个election开始，每次选举至多有一个leader选出，可能同时有两个candidate把选票分了，导致没有选出leader，这种情况一个新的term会快速开始(term++)，然后开始下一轮选举

不同的服务器可能会在不同的时间发现term的变化，每一个server都会存储一个current term的变量，每次server之间交流时都会带上这个变量，如果一个server的current term比另外一个小，那就会换成大的term，如果一个candidate或是leader发现自己的term过时了，它会立刻变为follower的状态，如果一个server'收到了一个带着旧的term的请求，它会拒绝该请求

Raftserver使用RPC来交流，主要用两个RequestVote 和 AppendEntries，还有一个是用来传输snapshot的

5.2 Leader election

Raft 使用心跳包的机制来触发选举，leader会周期性发送AppendEntries的RPC但是不带有任何log

entries来抑制follower触发选举，如果一个follower很长时间没有收到心跳包(election timeout)，他会认为leader挂了，然后将自己的term++，进入Candidate状态，想其它的servers发送RequestVoteRPC 开始选举，并且会先投自己一票。选举有三个结果：1.它赢了变成了leader；2.它输了，另外一个服务器变成了leader；3.这轮选举没有选出leader

当一个candidate收到超过半数的选票是，它就会变成leader，它会向所有的server发送心跳包确立自己的权威并且抑制其他的server发生选举

当一个candidate在等待投票的过程中，收到了其他server的AppendEntries RPC，如果该RPC中的term number 大于等于 candidate的term number，candidate认为leader已经选出来了，就回退到follower的状态。如果RPC中的term小于candidate的term，candidate 拒绝该RPC并且继续保持在candidate状态

第三种情况是，这轮term没选出leader，因为可能有很多个candidate来分选票，导致没有一个candidate获得超过一半的选票，这时，candidate的选举timer会超时，然后将term++，重新开始新的一轮选举

Raft使用randomized elections timeout来确保split votes的情况很少出现，即使出现了，也可以使用randomized elections timeout来解决这个问题

最初raft的作者使用一种rank的机制，在选举时低rank的服务器会给高rank的服务器让步，但是这样会有一些可用性的问题，并且调整了很多次都没有完全解决，于是就换用了randomized retry 的方法

5.3 Log replication

[图片上传失败...(image-f2507e-1652515917505)]

所有的机器上都有一个log，每一个log中的一格有一个index标志位置，里面会存储一个entry和一个term号表示该entry是什么时候被leader received的。

leader会将client发给他的entry转发给其他server，让他们把entry加入log，当leader收到了超过一半的server的回复时，这条log entry就是committed的状态了，leader就会执行entry，返回结果给client，并且通知其他server也执行entry。leader会保存一个最大的已经committed的index，并且会在AppendEntries RPC信息中带上这个信息

[图片上传失败...(image-8fc0b7-1652515917505)]

Raft的log有以下的性质，构成了Log Matching Property：

• If two entries in different logs have the same index and term, then they store the same command.
• If two entries in different logs have the same index and term, then the logs are identical in all preceding entries

第一点是因为，一个leader在一个term中最多只能在log的某个位置写入一个entry，并且之后就不会修改了

第二点因为，leader在发送AppendEntries RPC时，leader会将new entry的上一条entry的term和index包含在RPC中，servers回去看该index里有没有该term号的命令，如果没找到，就会拒绝执行new entry，也就是说，我一定要有上一条的log，我才可以把下一条log加进来

整个过程就像一个归纳的过程，因为一开始的状态满足Log Match Property，并且每一步都会保证它满足Log Match Property，所以最后的状态是只要server成功返回，那么该server从该index往前的命令都是和leader一样的

有时候，leader接收了client的entry，然后在它将entry转发给所有server之前就宕机了，这样就有部分server没有收到这个entry，就会造成不一致，这样的情况会有很多，如下图所示

[图片上传失败...(image-d237bb-1652515917505)]

在Raft中，leader通过强制让follower的log复制自己的log来解决不一致性，任何和leader log有冲突的地方都会用leader log覆盖。为了实现这点，leader需要知道log和它在哪些地方都是相等的，然后将follower开始出现不相等的地方全部删除，然后将leader后面的log entry全部发给follower。这些事情都是在AppendEntries RPC中完成的，leader会为每一个follower维护一个nextIndex变量，指示下一步该发哪个index的log给follower，leader会首先将这个值初始化为自己上一个写入entry的index + 1,在Figure 7 中就是11.如果一个follower发现自己的log和leader的不一样，那么他就reject该AppendEntries RPC，然后leader会将nextIndex--，然后重试，直到成功为止，哪此时的位置就是它们两个可以达成共识的位置，然后就可以将leader 后续的log发给它来同步了

5.4 Safety

前面的章节讲述了如何选举和如何做log replication，但是这样还是会有问题，例如一个follower可能宕机了，然后错过了一些entry，然后它被选成了leader，于是它用自己的log来强迫别人跟它同步，这样就会出问题了。

问题出在将这样的follower选成了leader，所以这章添加了一些限制，关于什么样的follower才有资格成为leader，这些限制保证leader有Leader Completeness Property这个性质，即对于一个给定term的entry，你可以在term号更高的leader中找到它

5.4.1 Election restriction

在任何leader-based的共识算法中，leader最终一定会有所有的committed log entries，在一些算法中，leader开始可以允许只有一部分committed entries，但是在选举中或是选举后的一段时间，leader会有所有的committed log entries，但这种方法引入了大量额外的机制和复杂性。Raft使用一个更简单的机制：它保证leader拥有上个term所有的committed log entries，这样就不需要将log entry发给leader，数据只会有leader流向follower

Raft在投票的过程中实现上面这一点，一个candidate只有包含了所有的committed log entries才能赢得选举，并且它必须获得超半数的follower的支持，这就意味了每个committed log entry至少在这些半数服务器中出现过一次。如果该candidate的log状态至少和它们一样新(at least as up-to-date as any other log)，那么它就会包含所有的committed log entries，也就可以赢得选举。在Candidate发送RequestVote RPC时，会将自己的log最大的index和term发过去，follower会那这些和自己做比较，如果哪个log的term大，哪个就更新，如果term一样，那更长的log(index更大)就更新

5.4.2 Committing entries from previous terms

假如一个leader将entry复制到了大半部分的服务器，然后在提交之前挂了，新的leader选出了，然后新的leader会尝试完成那个entry的replcation，新的leader没法知道这个entry是否被提交了，Figure 8 展示了这样的场景：log entry已经存储在大半的服务器当中，但是还是被重写了。
[图片上传失败...(image-95c8ba-1652581155892)]

为了解决这个问题，Raft不会通过计算副本数量的方式来提交一起term的entry，只有当前term的entry才能通过这种方式提交，一旦leader提交了一个当前term的entry，根据Log Matching Property之前的log都会算作提交，所以上个term的log也算是间接被提交了

Raft 在提交规则上引入了额外的复杂性，因为log entry会保持原来的term当一个leader在重复以前term的entry时

5.4.3 Safety argument

[站外图片上传中...(image-ca88b7-1652515917505)]

该小节作者通过反证法证明了Raft的Leader Completeness是成立的，假设term T的leader提交了一个log，但是这个log首次不在term U(U > T)的leader中，也就是说在T之后U之前的leader都有这条entry

1. 在leaderU 选举的时候，它一定没有这个entry，因为leader是append-only的，所以如果一旦它成为了leader，他就不会覆盖或者删除自己的log
2. leaderT将这个log entry成功复制到了过半的服务器中，leaderU获得了过半服务器的投票，所以至少有一个server同时有这个log entry并且投票给了leaderU，如Figure 9所示，这个voter(Figure 9 中的S3)是推导出矛盾的关键
   [站外图片上传中...(image-3600c8-1652515917505)]
3. voter一定已经accepted leaderT的log entry在投票给U之前，否则因为U比T大，voter会拒绝accept 该log entry
4. voter 在给leaderU投票时还存着这个entry，因为每个中间的leader都有这个entry(基于假设),leader不会删除entries，followers只会在和leader冲突时删除entry
5. voter投票给了leaderU，说明leaderU的log至少和voter的一样新，这会导致两个矛盾之一
6. 首先，如果voter和leaderU有一样的last log term，那么leaderU的log至少和voter的一样新，所以它也会有该entry，这是一个矛盾
7. 否则，leaderU的last log term一定要比voter的大(根据选举规则)，U也比T大，因为voter的last log term至少是T，因为它有T的那条entry。创建了leaderU最后一条日志的leader也一定有那条leaderT的entry(基于假设)，然后，基于Log Matching Property，LeaderU的log也会有那条entry，得到另一个矛盾

Log Matching Property

If two entries in different logs have the same index and term, then they store the same command.

If two entries in different logs have the same index and term, then the logs are identical in all preceding entries

1. 上述过程证明了矛盾，所以比term T大的leader必须有所有在Term T提交的entry
2. Log Matching Property保证了未来的leader会有间接提交的entry，例如Figure 8(d)的index2位置

有了Leader Completeness的性质，我们可以证明Figure 3中的State Machine Saftey Property，即：如果一个服务器将给定index的日志条目应用到了其状态机中，那么不会有另一台应用了index相同但内容不同的日志条目的服务器。当服务器将一个entry应用到其状态机时，从这条entry往前所有的entry都应该与leader相同（因为Log Matching Property只要index i处的entry相同，那么之前的entry都相同），且该条目必须是被提交的。现在考虑任何服务器都应用了给定index的日志条目的最小的term；“日志完整性性质”确保了所有term更高的leader都保存了相同的这个条目，所以在之后的term中应用了该条目的服务器将会应用相同的值。因此，“状态机安全性性质”成立。

最后，Raft要求服务器按照日志index的顺序应用条目。结合“状态机安全性质”，这意味着服务器会精确地按照相同的顺序将相同的日志条目应用到它们的状态机中。

5.5 Follower and candidate crashes

之前的章节都在关注leader的宕机，follower和candidate的宕机要容易的多，都是用相同的办法处理的。如果一个follower或是candidate宕机了，这样发给他的RequestVote and AppendEntries RPCs 就会失败，发送者会不断的重试直到成功，等到宕机的server重启，就会收到相同的请求，因为RPC请求时幂等的，所以如果一些server已经完成了请求，但是没来及回复(例如已经将entry加到自己log中，然后就宕机了)，那也没有什么问题。

5.6 Timing and availability

Raft要求Safety属性不能依赖于timing(事件发生的时间点)，也就是说不管时间在什么时间点发生，都要保证Safety(此处的safety指的时一致性)。但是availability会受到timing的影响。

例如在leader election中，要满足下面的要求：

broadcastTime指定的server发送RPC并且收到回复的平均时间，electionTimeout指的是一场选举最多持续多久，MTBF指的是单台server发生两次故障的平均间隔时间，broadcastTime要比electionTimeout小一个数量级，这样leader才可以通过心跳包来有效抑制follower发生选举，electionTimeout要比MTBF少几个数量级的时间。当leader宕机时，系统会在electionTimeout的时间段内不可用

7. Log compaction

Raft的log会随着时间线的延长而无限制的增加，所以我们需要定期丢弃过时的log。Raft使用snapshot来解决这一个问题，一个快照记录了整个系统的状态，在这个快照记录点之前的所有log就可以删除

下图展示了Raft的log snapshot

[站外图片上传中...(image-32770b-1652515917505)]

如上图所示，快照会保存一部分metadata：

• last included index：快照最后一个log的index
• last included term：快照最后一个log的term

保存这两个数据是因为这两个在AppendEntries中需要用到

当leader已经丢弃了快照之前的log，但是他需要将log发给follower的时候，leader会偶尔将自己的快照发给服务器。正常情况下不会有这个问题，除非是一个落后很多的server或是一个刚刚加入集群的server

leader使用一个叫做InstallSnapshot的RPC来发送快照给follower，如下所示

[图片上传失败...(image-2465e5-1652581155892)]

当server收到leader的快照中包含了新的信息时，server就丢弃自己的log，并且使用leader的快照

如果收到的快照只是自己log的前缀，那么会删除该创建快照时的所有log(因为log的信息都在快照里面了)，但是会保留快照后面的log

曾经的设计只允许leader发送快照给follower，但是这样要传输所有的快照很浪费带宽，使快照操作变慢，并且这样会增加leader设计的复杂度

还有另外两个性能问题，第一个是创建快照的频率，不能太快也不能太慢，第二个是写一个快照要花很多时间，解决方法是使用copy-on-write

8. Client interaction

这个章节讲述了Raft是如何与client交互的，以及如何实现线性一致性(linearizable)的语义

client会先随机找一台server，如果那台server不是leader，就会拒绝请求并给client指出leader是谁

Raft的一个设计目标是实现线性一致性语义(each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response). 但是Raft可能执行一个指令很多遍，例如如果leader以及提交了log entry，在回复client之前挂了，client会向新的leader重试，导致执行被执行两遍。解决方案是给每一个client的请求附加一个序列号，如果server发现这个请求的序列号已经被执行了，那么它就不会重复执行这条指令

上面讨论的都是写操作(需要有log的)，如果是只读操作，也就是不会更改系统状态的操作，那就可以不用加到log中。但是，如果没有保障措施，会读到旧数据，因为leader在处理client时，可能自己已经不是leader了。文中提出了两个措施来解决这个问题，第一，leader需要知道哪些entry是已经提交的，Leader Completeness Property可以保证leader term之前的entry都是已经提交的，但是在刚刚成为leader时，他并不清楚是哪些（我认为是leader会有所有的committed log，但是不是leader的所有log都是committed的 ）。Raft通过leader在它term的开始发送一个no-op entry来获取信息。第二，leader在处理只读请求前必须确认自己还是不是leader，这个需求通过心跳包来完成