raft算法
- raft算法
raft算法
1. 引言
共识算法(consensus algorithm)运行一组机器作为一个可以承受部分成员故障的连贯整体工作。因此，它们在构建可靠的大型软件系统中发挥着关键作用。在过去的十年中，Paxos一直主导着关于共识算法的讨论：大多数共识的实现都是基于Paxos或受到它的影响，Paxos已经成为教授学生共识概念的主要工具。
不幸的是，尽管人们多次尝试让 Paxos 更容易理解，但它仍然相当难以理解。此外，它的架构需要复杂的变更才能支持实际的系统。因此，系统构建者和学生们在理解 Paxos 时都感到很吃力。
在我们自己与 Paxos 算法苦苦斗争之后，我们着手寻找一种新的共识算法，它能够为系统构建和教育提供更好的基础。我们的方法不同寻常之处在于，我们的主要目标是可理解性：我们能否为实际系统定义一种共识算法，并以一种比 Paxos 算法明显更容易学习的方式来描述它呢？此外，我们希望该算法有助于培养对系统构建者至关重要的直觉。重要的不仅仅是算法要能起作用，而且要让它为何起作用变得显而易见。
这项工作的结果是一种名为 Raft 的共识算法。在设计 Raft 时，我们应用了特定的技术来提高可理解性，包括分解（Raft 将领导者选举、日志复制和安全性分开）和状态空间缩减（与 Paxos 相比，Raft 减少了不确定性的程度以及服务器之间不一致的方式）。在两所大学对 43 名学生进行的一项用户研究表明，Raft 比 Paxos 明显更容易理解：在学习了这两种算法之后，这些学生中有 33 人能够更好地回答关于 Raft 的问题，而不是关于 Paxos 的问题。
Raft 在很多方面与现有的共识算法相似（最值得注意的是，与 Oki 和 Liskov 的 Viewstamped Replication [29, 22] 相似），但它也有几个新颖的特点：
- "强领导"：Raft 采用了一种比其他共识算法更强的领导形式。例如，日志条目仅从领导者流向其他服务器。这简化了复制日志的管理，并使 Raft 更容易理解。
- 领导选举：Raft 使用随机定时器来选举领导者。这仅在任何共识算法都已需要的心跳机制基础上增加了少量机制，同时能简单快速地解决冲突。
- 成员变更：Raft 用于更改集群中服务器集合的机制采用了一种新的联合共识方法，在过渡期间，两种不同配置的大多数成员相互重叠。这使得集群在配置更改期间能够继续正常运行。
我们认为，无论是出于教育目的还是作为实现的基础，Raft 都优于 Paxos 和其他共识算法，主要理由有以下几点：
- 它比其他算法更简单、更易理解；
- 它的描述足够完整，能够满足实际系统的需求；
- 它有几个开源实现，并被一些公司所使用；
- 它的安全属性已被正式指定并得到证明；
- 它的效率与其他算法相当。
论文的包含下面一些话题
- 第2节： 介绍了复制状态机问题
- 第3节： 讨论了 Paxos 的优缺点
- 第4节: 描述了我们提高可理解性的一般方法
- 第5-8节：介绍了 Raft 共识算法
- 第9节：对 Raft 进行评估
- 第10节：并讨论了相关工作
2. 复制式状态机
3. Paxos的问题
在过去十年间，莱斯利・兰伯特（Leslie Lamport）的 Paxos 协议几乎成了共识算法（consensus）的代名词：它是课程中最常讲授的协议，而且大多数共识实现都将其作为起始点。
Paxos 首先定义了一个能够就单个决策（例如单个复制日志条目）达成一致的协议。我们将这个子集称为单决议 Paxos（single - decree Paxos）。然后，Paxos 组合该协议的多个实例以促成一系列决策，例如日志（多 Paxos，multi - Paxos）。Paxos 确保安全性和活性（liveness），并且支持集群成员关系的变更。其正确性已得到证明，而且在正常情况下是高效的。
Paxos算法的缺点如下：
- 第一个缺点是 Paxos 是出了名的难以理解。
- 第二个缺点没有考虑真实系统的实现，很难用于实际系统。
基于上述问题，作者认为Paxos既不能为开发真实系统提供良好的基础，又不适用于教学。而考虑到大型软件系统中共识的重要性，我们决定自己设计一种替代 Paxos、有更好特性的共识算法。Raft 就是这一实验的产物。
4. 面向可理解性的设计
设计 Raft 时我们有几个目标：
- 必须为构建真实系统提供完整基础，能显著降低系统开发者所需的设计工作；
- 必须在所有情况下确保安全（不会导致冲突），在典型场景下确保可用；
- 对于常见操作必须很高效，
- 必须确保可理解性（understandability），这才是我们最重要的目标，同时也是最大的挑战。
5. raft一致性算法
5.1 raft算法基础
5.1.1 raft状态机
一个 Raft 集群包含若干个服务器；通常有五个，这使得系统可以容忍两个节点发生故障。
在任何特定时间，每个服务器都处于三种状态之一：领导者（leader）、跟随者（follower）或者候选者（candidate）。
- 在正常运行时，只有一个领导者，其他所有服务器都是跟随者。
- 跟随者是被动的，它们自身不发出请求，而只是响应来自领导者和候选者的请求。
- 领导者处理所有客户端请求， 如果客户端与一个跟随者联系，跟随者会将其重定向到领导者。
- 候选者是一个特殊状态，用于选举新的领导者。
下图展示了这些状态及其转换：
5.1.2 raft任期
下一个要介绍的概念是任期。Raft 算法将时间划分为任意长度的任期，任期用连续的整数编号。每个任期都以一次选举开始，在选举中，一个或多个候选人尝试成为领导者。如果一个候选人在选举中获胜，那么它将在该任期的剩余时间里担任领导者。在某些情况下，选举会导致选票分散。在这种情况下，该任期将结束且没有领导者；一个新的任期（伴随着新的选举）很快就会开始。Raft 算法确保在一个特定任期内最多只有一个领导者。
关于raft，有以下几点需要说明：
- 每个任期的开始都是从选举开始，选举时可能有多个都试图成为leader。
- 某个candidate赢得选举之后，就会成为该任期内的leader。
- 每个节点都记录了当前的任期号（currentTerm），这个编号时随着时间单调递增。
- 节点通信时，会带上自己的任期号
- 如果自己的任期号小于其他节点的，要立即将自己的任期号更新为更大的任期号。
- 如果一个candidate或leader发现自己的任期过期了，要立即切换到follower状态。
- 如果一个节点收到了携带过期任期编号的请求，会拒绝这个请求。
5.1.3 raft节点通讯
raft服务器RPC进行通讯，主要通讯交互是两种：
- RequestVote： 由candidates在选举期间发起
- AppendEntries： 由leader发起，用于复制日志条目以及提供一种心跳（heartbeat）形式。
5.2 Leader选举
Raft 使用心跳机制来触发领导者选举。
- 当服务器启动时，它们以跟随者（follower）状态开始。只要服务器从领导者或候选人那里接收到有效的远程过程调用（RPC），它就会保持在跟随者状态。
- 领导者会定期向所有跟随者发送心跳（空的AppendEntries消息）以维护其权威性。
- 如果一个跟随者在一段称为选举超时（election timeout）的时间内没有收到任何通信，那么它会假定没有有效的领导者，并开始进行选举以选出新的领导者。
5.2.1 选举过程
对于一个follower，当其发生选举超时时，将开始选举，具体过程如下
- 增加它的当前任期
- 将状态机切换到candidate状态。
- 然后选举自己作为leader，同时并发地向集群其他节点发送RequestVote RPC
对于该follower，其选举结果可能由如下三种：
- 该follower赢得此次选举，成为leader
- 另一个节点赢得此次选举，成为leader
- 选举超时，没有产生有效leader
5.2.2 选举成功的条件
如果候选人在同一任期内获得了整个集群中大多数服务器的选票，它就赢得了选举。在给定的任期内，每个服务器最多为一个候选人投票，遵循先到先得的原则。多数原则确保了在特定任期内最多只有一个候选人能够赢得选举。一旦候选人赢得选举，它就成为领导者。然后它向所有其他服务器发送心跳消息以确立其权威并防止新的选举。
在等待投票期间，一个 candidate 可能会从其他服务器收到一个 AppendEntries RPC 声称自己是 leader。这个 leader 的任期 term 包含在 RPC 消息中，根据term值，分两种情况处理：
- 该term大于等于这个 candidate 的 currentTerm：那该 candidate 就承认 这个 leader 是合法的，然后回归到 follower 状态。
- 该term小于这个 candidate 的 currentTerm：拒绝这个 RPC ，仍然留在 candidate 状态。
第 3 种可能的结果是：该 candidate 既没有赢得也没有输掉这次选举。 如果多个 followers 在同一时间成为 candidates，投票就会很分散，最终没有谁能赢得大多数选票。 当发生这种情况时，每个 candidate 都会超时，然后各自增大 term 并给其他节点发送 RequestVote 请求，开始一轮新选举， 但如果没有额外的预防措施，这种投票分裂的情况看可能会无限持续下去。
5.2.3 如何避免无限循环的投票分裂
Raft 使用随机化的选举超时时间来确保选票分散（split votes）的情况很少发生并且能够被快速解决。
为了从一开始就防止选票分散的情况，选举超时时间是从一个固定区间（例如，150 - 300 毫秒）中随机选择的。这样可以分散服务器的超时时间，使得在大多数情况下只有一台服务器会超时；这台服务器赢得选举并在其他服务器超时之前发送心跳信息。同样的机制也被用于处理选票分散的情况。每个候选人在选举开始时重新启动其随机化的选举超时时间，并在该超时时间结束后才开始下一次选举；这降低了在新选举中再次出现选票分散的可能性。9.3 节表明这种方法可以快速选出领导者。
作者这里提到了曾经设计过使用排名系统来解决选票分散问题，即每个候选人被分配一个唯一的排名，该排名用于在相互竞争的候选人之间进行选择。如果一个候选人发现另一个具有更高排名的候选人，它将返回跟随者状态，以便更高排名的候选人可以更容易地赢得下一次选举。但是这种方法在可用性方面产生了一些微妙的问题。如果高排名的服务器出现故障，低排名的服务器可能需要超时并再次成为候选人，但如果它太快这样做，可能会重置选举领导者的进度）。我们对该算法进行了多次调整，但每次调整后都会出现新的极端情况。最终我们得出结论，随机重试方法更加直观和易于理解。
综上所述，作者选择了使用随机化选举超时时间解决选票分散问题。
5.3 日志复制
5.3.1 复制的流程
一旦选举出领导者，它就开始处理客户端请求。每个客户端请求都包含一个要由复制状态机执行的命令。领导者将该命令作为新条目追加到其日志中，然后并行地向其他每个服务器发出附加条目（AppendEntries）RPC 以复制该条目。当该条目已被安全复制（如下所述）时，领导者将该条目应用于其状态机，并将该执行结果返回给客户端。如果跟随者崩溃或运行缓慢，或者网络数据包丢失，领导者会无限期地重试附加条目 RPC（即使在它已经响应客户端之后），直到所有跟随者最终存储所有日志条目。
5.3.2 日志的组织方式
日志的组织方式下图所示。每个日志条目存储一个状态机命令，以及该条目被领导者接收时的任期编号。日志条目中的任期编号用于检测日志之间的不一致性。每个日志条目还拥有一个整数索引，用于标识其在日志中的位置。
5.3.3 提交日志
Raft 协议保证已提交的条目是持久化的，并且最终将由所有可用的状态机执行。
日志可以被提交的前提是该日志已经被复制到大多数服务器上(半数以上)。
5.4节会讨论leader变更之后应用这个规则时的情况，那时将会看到这种对于 commit 的定义也是安全的。
5.3.4 匹配日志
如果不同 log 中的两个 entry 有完全相同的 index 和 term， 那么意味着：
- 这两个 entry 一定包含了相同的命令
- 在所有前面的条目中这些日志都是相同的。
5.3.5 日志不一致的场景
正常情况下，leader 和 follower 的 log 能保持一致，但 leader 挂掉会导致 log 不一致 （leader 还未将其 log 中的 entry 都复制到其他节点就挂了）。 这些不一致会导致一系列复杂的 leader 和 follower crash。 Figure 7 展示了 follower log 与新的 leader log 的几种可能不同：
在上图中：
- 每个方框代表一个日志项
- a-b代表follower缺失了部分日志
- c-d代表follower产生了额外的未提交日志
- e-f既缺失日志又产生了未提交日志
上图中f的场景可能是这样的：服务器是任期2的领导者，在其日志中添加了若干条目，然后在提交任何条目之前崩溃；它迅速重启，成为任期3的领导者，并在其日志中又添加了一些条目；在任期2或任期3的任何条目被提交之前，该服务器再次崩溃，并在之后的几个任期内一直处于宕机状态。
5.3.6 避免 log 不一致：AppendEntries 中的一致性检查
Raft 处理不一致的方式是强制 follower 复制一份 leader 的 log， 这意味着 follower log 中冲突的 entry 会被 leader log 中的 entry 覆盖。 Section 5.4 将会看到再加上另一个限制条件后，这个日志复制机制就是安全的。
解决冲突的具体流程：
- 找到 leader 和 follower 的最后一个共同认可的 entry，
- 将 follower log 中从这条 entry 开始往后的 entries 全部删掉，
- 将 leader log 中从这条记录开始往后的所有 entries 同步给 follower
5.3.7 客户端提交一条操作到集群的过程
该节是论文中没有过多提到的一部分，主要讨论客户端和raft集群的交互过程：
5.4 安全性
5.4.1 限制一：包含所有已提交 entry 的节点才能被选为 leader
在任何基于 leader 的共识算法中，leader 最终都必须存储了所有的已提交 entry。
在某些共识算法中，例如Viewstamped Replication，一个节点即使并未包含全部的 已提交 entries 也仍然能被选为 leader。这些算法有特殊的机制来识别缺失 entries， 并在选举期间或选举结束后立即发送给新 leader。不幸的是，这会导致额外的复杂性。
Raft 采取了一种更简单的方式：除非前面所有 term 内的已提交 entry 都已经在某个节点上了，否则这个节点不能被选为 leader（后面将介绍如何保证这一点）。 这意味着无需从 non-leader 节点向 leader 节点同步数据，换句话说 log entries 只会从 leader 到 follower 单向流动。
那这个是怎么做到的呢？通过投票过程。
- 首先，刚才已经提到，除非 log 中已经包含了集群的所有已提交 entries，否则一个 candidate 是不能被选为 leader 的。
- 其次，还活着的（即参与选举的）节点中，至少有一个节点保存了集群的所有已提交 entries （因为覆盖大多数节点的 entry，才算是提交成功的）。
- 那么，只要一个 candidate 的 log 与大多数节点相比至少不落后（at least as up-to-date，这个词下文会有精确定义），那它就持有了集群的所有已提交记录。
因此，只要能确保这里提到的"至少不落后"语意，就能确保选出来的 leader 拥有集群的所有已提交 entries。 RequestVote RPC 实现了这个过程：请求中包含了发送方的 log 信息，如果当前 节点自己的 log 比对方的更新，会拒绝对方成为 leader 的请求。具体到实现上， 判断哪个 log 更加新，依据的是最后一个 entry 的 index 和 term：
- 如果 term 不同，那 term 新的那个 log 胜出；
- 如果 term 相同，那 index 更大（即更长）的那个 log 胜出。
5.4.2 限制二：
下面是一个时间序列展示了为什么领导者不能使用旧任期的日志条目来确定提交状态。
对于该图的解释如下：
- 在图(a)中, S1是当前的leader，将index=2的日志复制到了S2。
- 在图(b)中, S1挂了，S5被S3/S4/S5选举为新的leader，任期为3，然后S5在index=2的位置接受了一个来自客户端的新的entry。
- 在图(c)中, S1又被选举为下一任leader，任期为4。然后S1继续同步挂掉之前的那个entry(index=2)，它被成功同步到大部分节点上(S1/S2/S3)，但还未提交；
接下来，分两种情况：
- 在图(d)中，如果此时S1再此崩溃，S5可能会被选举为领导者(来自S2，S3，S4，S5的选票)，那么S5会用自己在任期3的index=2的日志覆盖其他节点上的日志。试想对于这种场景，倘若在图(c)中提交日志<2，2>，那么可能存在提交日志被覆盖的场景，这是不可以被接受的。
- 在图(e)中，如果S1没有崩溃，客户端又提交了一个新的entry，并且复制到了大多数服务器上，则此刻可以提交。因为这个场景下，S5没有可能成为leader。
5.4.3 安全性论证
鉴于完整的 Raft 算法，我们现在可以更精确地论证领导者完备性属性成立（这个论证基于安全性证明；见第 9.2 节）。我们假设领导者完备性属性不成立，然后证明一个矛盾。
假设任期 T 的领导者（leaderT）提交了一个来自其任期的日志条目，但该日志条目没有被某个未来任期的领导者存储。考虑最小的任期 U＞T，其领导者（leaderU）没有存储该条目。
- 已提交的条目在 leaderU 被选举时一定不在其日志中（领导者永远不会删除或覆盖条目）。
- leaderT 将该条目复制到了集群中的大多数服务器上，并且 leaderU 从集群中的大多数服务器获得了选票。因此，至少有一个服务器（"投票者"）既接受了来自 leaderT 的条目，又为 leaderU 投了票，如图 9 所示。这个投票者是得出矛盾的关键。
- 投票者一定是在为 leaderU 投票之前就接受了来自 leaderT 的已提交条目；否则它会拒绝来自 leaderT 的附加条目请求（它的当前任期会比 T 更高）。
- 当投票者为 leaderU 投票时，它仍然存储着该条目，因为每一个介于其间的领导者都包含该条目（根据假设），领导者永远不会删除条目，而跟随者只有在条目与领导者冲突时才会删除条目。
- 投票者将其选票投给了 leaderU，所以 leaderU 的日志一定与投票者的日志一样是最新的。这会导致两种矛盾情况之一。
- 首先，如果投票者和 leaderU 具有相同的最后一个日志任期，那么 leaderU 的日志长度一定至少与投票者的日志长度相同，所以它的日志包含投票者日志中的每一个条目。这是一个矛盾，因为投票者包含已提交的条目，而假设 leaderU 不包含。
- 否则，leaderU 的最后一个日志任期一定大于投票者的。此外，它一定大于 T，因为投票者的最后一个日志任期至少是 T（它包含来自任期 T 的已提交条目）。创建 leaderU 的最后一个日志条目的早期领导者的日志中一定包含已提交的条目（根据假设）。然后，根据日志匹配属性，leaderU 的日志也必须包含已提交的条目，这是一个矛盾。
- 这就完成了矛盾的证明。因此，所有大于 T 任期的领导者都必须包含在任期 T 中已提交的来自任期 T 的所有条目。
- 日志匹配属性保证了未来的领导者也将包含间接提交的条目，例如图 8 (d) 中的索引 2。
5.5 Follower/candidate 故障
到目前为止，我们一直关注领导者故障。跟随者和候选者的崩溃比领导者崩溃更容易处理，并且它们都以相同的方式处理。如果一个跟随者或候选者崩溃，那么未来发送给它的请求投票和附加条目 RPC 将失败。Raft 通过无限期重试来处理这些故障；如果崩溃的服务器重新启动，那么 RPC 将成功完成。如果一个服务器在完成 RPC 后但在响应之前崩溃，那么它在重新启动后将再次收到相同的 RPC。Raft RPC 是幂等的，所以这不会造成任何危害。例如，如果一个跟随者收到一个附加条目请求，其中包括已经存在于其日志中的日志条目，它会在新请求中忽略这些条目。
5.6 时序
Raft中最依赖时序的就是leader的选举。只要系统满足如下时序条件，Raft就一定可以选出一个稳定的leader：
- broadcastTime：一个节点并发给其他节点发送请求并收到响应的平均时间；
- electionTimeout： 5.2 小节定义的选举超时时间；
- MTBF：单个节点的平均故障时间（average time between failures）
这个不等式表达的意思很好理解：
- 广播耗时要比选举超时低一个数量级，这样 leader 才能可靠地发送心跳消息给 follower，避免它们发起来新的选举。 考虑到选举超时是随机化的，这个不等式也使得投票分裂不太可能发生。
- 选举超时要比 MTBF 低几个数量级，这样系统才能稳步前进。 当 leader 挂掉后，系统大致会经历一个 election timeout 时间段的不可用，我们希望这个时间段只占到总时间段的很小一部分。
broadcastTime 和 MTBF 都是底层系统的特性，而 electionTimeout 是我们需要设置的。
- Raft 一般要求接收方将请求持久化到稳定存储中，因此取决于存储技术，broadcastTime 可能需要 0.5ms ~ 20ms。
- 因此，electionTimeout 通常选择 10ms ~ 500ms。
- 典型的节点 MTBF 是几个月或更长时间，因此很容易满足时序要求。
6. 集群成员发生变更
7. 日志压缩
在正常操作期间，Raft 的日志会随着更多客户端请求的加入而增长，但在实际系统中，它不能无限制地增长。随着日志变得越来越长，它会占用更多空间并且回放需要更多时间。如果没有某种机制来丢弃日志中积累的过时信息，这最终将导致可用性问题。
快照（Snapshotting）是进行压缩（compaction）的最简单方法。在快照中，整个当前系统状态被写入到稳定存储中的一个快照里，然后截至该点的整个日志被丢弃。Chubby 和 ZooKeeper 中使用了快照技术，本节的其余部分将描述 Raft 中的快照技术。
增量式的压缩方法，例如日志清理（log cleaning）和日志结构合并树（log-structured merge trees）也是可行的。这些方法一次处理一部分数据，因此它们随着时间的推移将压缩的负载更均匀地分散开来。它们首先选择一个积累了许多已删除和被覆盖对象的数据区域，然后更紧凑地重写该区域中的有效对象，并释放该区域。与快照相比，这需要大量额外的机制和复杂性，而快照通过始终对整个数据集进行操作简化了问题。虽然日志清理需要对 Raft 进行修改，但状态机可以使用与快照相同的接口实现日志结构合并树。
下图展示了 Raft 中快照的基本概念。每个服务器独立地进行快照操作，仅涵盖其日志中已提交的条目。大部分工作包括状态机将其当前状态写入快照。
Raft 在快照中还包含少量元数据
- 最后被包含的索引是快照所替代的日志中的最后一个条目的索引（即状态机已应用的最后一个条目），
- 最后被包含的任期是这个条目的任期。
这些被保留下来是为了支持对快照之后的第一个日志条目的 AppendEntries 一致性检查，因为那个条目需要前一个日志的索引和任期。为了实现集群成员变更（第 6 节），快照还包括截至最后被包含索引时日志中的最新配置。一旦服务器完成写入快照，它可以删除所有直到最后被包含索引的日志条目，以及任何先前的快照。
虽然服务器通常独立地进行快照，但领导者偶尔必须向落后的跟随者发送快照。这种情况发生在领导者已经丢弃了它需要发送给某个跟随者的下一个日志条目时。幸运的是，在正常操作中这种情况不太可能发生：一个与领导者保持同步的跟随者应该已经拥有了这个条目。然而，一个异常缓慢的跟随者或者一个新加入集群的服务器（第 6 节）则不会。使这样一个跟随者更新到最新状态的方法是让领导者通过网络向它发送一个快照。
领导者使用一种名为 "InstallSnapshot" 的新远程过程调用（RPC）将快照发送给落后太多的跟随者；见图 13。当一个跟随者通过这个 RPC 接收到一个快照时，它必须决定如何处理其现有的日志条目。
通常情况下，快照会包含接收者日志中尚未存在的新信息。在这种情况下，跟随者会丢弃其整个日志；因为它都被快照所取代，并且可能存在与快照冲突的未提交条目。相反，如果跟随者接收到一个描述其日志前缀的快照（由于重传或错误），那么被快照覆盖的日志条目将被删除，但快照之后的条目仍然有效并且必须被保留。
这种快照方法偏离了 Raft 的强领导原则，因为跟随者可以在领导者不知情的情况下进行快照。然而，我们认为这种偏离是合理的。虽然有一个领导者有助于在达成共识时避免冲突的决策，但在进行快照时共识已经达成，所以不存在冲突的决策。数据仍然只能从领导者流向跟随者，只是跟随者现在可以重新组织他们的数据。
我们考虑了一种以领导者为基础的替代方法，即只有领导者会创建一个快照，然后将这个快照发送给每个跟随者。然而，这有两个缺点。首先，将快照发送给每个跟随者会浪费网络带宽并减慢快照过程。每个跟随者已经拥有生成自己快照所需的信息，并且对于一个服务器来说，从其本地状态生成一个快照通常比通过网络发送和接收一个快照要便宜得多。其次，领导者的实现会更加复杂。例如，领导者需要在向跟随者复制新的日志条目时并行地向他们发送快照，以免阻塞新的客户端请求。
还有两个问题会影响快照的性能。
首先，服务器必须决定何时进行快照。如果服务器太频繁地进行快照，会浪费磁盘带宽和能源；如果它快照的频率太低，就有耗尽存储容量的风险，并且会增加在重启期间重放日志所需的时间。一个简单的策略是当日志达到固定的字节大小时进行快照。如果这个大小被设置为明显大于预期的快照大小，那么快照的磁盘带宽开销就会很小。
第二个性能问题是写入快照可能需要大量时间，而我们不希望这会延迟正常操作。解决方案是使用写时复制技术，这样在不影响正在写入的快照的情况下可以接受新的更新。例如，用函数式数据结构构建的状态机自然支持这一点。或者，可以使用操作系统的写时复制支持（例如，Linux 上的 fork）来创建整个状态机的内存快照（我们的实现使用了这种方法）。
8. 客户端交互
本节描述了客户端如何与 Raft 进行交互，包括客户端如何找到集群领导者以及 Raft 如何支持线性一致性语义。这些问题适用于所有基于共识的系统，并且 Raft 的解决方案与其他系统类似。
8.1 如何寻找leader
在Raft协议中，所有的请求都需要发送给leader，客户端如何知道leader呢？客户端的操作流程大致如下：
- 当一个客户端首次启动时，它会连接到一个随机选择的服务器。
- 如果客户端的第一选择不是领导者，那么该服务器将拒绝客户端的请求，并提供它所知道的最近领导者的信息（AppendEntries 请求中包含领导者的网络地址）。
- 如果连接的是领导者，则可以直接通讯。
- 如果领导者崩溃，客户端的请求将超时；然后客户端会再次随机选择服务器进行尝试。
8.2 线性化语义
我们对 Raft 的目标是实现线性一致性语义（每个操作似乎在其调用和响应之间的某个时刻瞬间、确切地执行一次）。然而，正如目前所描述的，Raft 可能会多次执行一个命令：例如，如果领导者在提交日志条目后但在响应客户端之前崩溃，客户端将使用新的领导者重试该命令，导致它被执行第二次。
解决方案是让客户端为每个命令分配唯一的序列号。然后，状态机跟踪每个客户端已处理的最新序列号以及相关的响应。如果它接收到一个序列号已经被执行过的命令，它会立即响应而无需重新执行该请求。
8.3 只读操作
只读操作可以在不写入任何内容到日志中的情况下进行处理。然而，如果没有额外的措施，这将有返回陈旧数据的风险，因为响应请求的领导者可能已经被一个它不知道的新领导者所取代。线性一致性的读操作不能返回陈旧数据，并且 Raft 需要两个额外的预防措施来保证这一点而无需使用日志。
首先，一个领导者必须拥有关于哪些条目已提交的最新信息。领导者完整性属性保证领导者拥有所有已提交的条目，但在其任期开始时，它可能不知道哪些是已提交的条目。为了找出这些，它需要提交一个来自其任期的条目。Raft 通过让每个领导者在其任期开始时将一个空白的无操作条目提交到日志中来处理这个问题。
其次，领导者在处理只读请求之前必须检查它是否已被罢免（如果一个更新的领导者已被选举出来，它的信息可能是陈旧的）。Raft 通过让领导者在响应只读请求之前与集群中的大多数节点交换心跳消息来处理这个问题。或者，领导者可以依靠心跳机制来提供一种租约形式，但这将依赖于时间来保证安全性（它假设时钟偏差是有界的）。
9. 实现和评估(非本文重点)
我们已经将 Raft 实现为一个存储 RAMCloud 配置信息并协助 RAMCloud 协调器进行故障转移的复制状态机的一部分。Raft 的实现包含大约 2000 行 C++ 代码，不包括测试、注释或空行。源代码是免费提供的。还有大约 25 个独立的第三方开源 Raft 实现处于不同的开发阶段，它们基于本文的草稿。此外，各种公司正在部署基于 Raft 的系统。本节的其余部分使用三个标准来评估 Raft：可理解性、正确性和性能。
9.1 可理解性
为了衡量 Raft 相对于 Paxos 的可理解性，我们在斯坦福大学的高级操作系统课程和加州大学伯克利分校的分布式计算课程中，对高年级本科生和研究生进行了一项实验研究。我们录制了一个关于 Raft 的视频讲座和另一个关于 Paxos 的视频讲座，并创建了相应的测验。Raft 讲座涵盖了本文除日志压缩之外的内容；Paxos 讲座涵盖了足够的材料来创建一个等效的复制状态机，包括单法令 Paxos、多法令 Paxos、重新配置以及在实践中需要的一些优化（如领导者选举）。测验测试了对算法的基本理解，还要求学生对边界情况进行推理。每个学生观看一个视频，进行相应的测验，观看第二个视频，然后进行第二个测验。大约一半的参与者先进行 Paxos 部分，另一半先进行 Raft 部分，以考虑到个人表现的差异以及从研究的第一部分中获得的经验。我们比较了参与者在每个测验中的得分，以确定参与者是否对 Raft 有更好的理解。
我们试图使 Paxos 和 Raft 之间的比较尽可能公平。这个实验在两个方面对 Paxos 有利：43 名参与者中有 15 人报告说他们之前有一些使用 Paxos 的经验，并且 Paxos 的视频比 Raft 的视频长 14%。正如表 1 所总结的，我们已经采取措施来减轻潜在的偏差来源。我们所有的材料都可供审查。
平均而言，参与者在 Raft 测验中的得分比在 Paxos 测验中高 4.9 分（在可能的 60 分中，Raft 的平均得分是 25.7 分，Paxos 的平均得分是 20.8 分）；图 14 显示了他们的个人得分。配对 t 检验表明，在 95% 的置信度下，Raft 得分的真实分布的均值至少比 Paxos 得分的真实分布的均值大 2.5 分。
我们还创建了一个线性回归模型，该模型基于三个因素来预测一个新学生的测验分数：他们参加了哪个测验、他们之前对 Paxos 的经验程度以及他们学习这些算法的顺序。该模型预测，测验的选择会产生有利于 Raft 的 12.5 分的差异。这明显高于观察到的 4.9 分的差异，因为许多实际的学生有之前的 Paxos 经验，这对 Paxos 有很大帮助，而对 Raft 的帮助则略小。奇怪的是，该模型还预测已经参加过 Paxos 测验的人在 Raft 测验中的分数会低 6.3 分；虽然我们不知道为什么，但这在统计上似乎确实是显著的。
我们在参与者完成测验后也对他们进行了调查，以了解他们觉得哪种算法更容易实现或解释；这些结果如图 15 所示。绝大多数参与者报告说 Raft 更容易实现和解释（每个问题有 41 人中的 33 人这样认为）。然而，这些自我报告的感受可能不如参与者的测验分数可靠，并且参与者可能受到我们关于 Raft 更容易理解这一假设的知识的影响而存在偏差。 关于 Raft 用户研究的详细讨论可在31中找到。
9.2 正确性
我们为第 5 节中描述的共识机制开发了一个形式化规范和安全性证明。形式化规范 [31] 使用 TLA + 规范语言 [17] 使图 2 中总结的信息完全精确。它大约有 400 行，作为证明的主题。对于任何实现 Raft 的人来说，它本身也很有用。我们使用 TLA 证明系统 [7] 机械地证明了日志完整性属性。然而，这个证明依赖于尚未经过机械检查的不变量（例如，我们没有证明规范的类型安全性）。此外，我们还写了一个状态机安全属性的非正式证明 [31]，它是完整的（仅依赖于规范）并且相对精确（大约有 3500 个字）。
9.3 性能
Raft 的性能与其他共识算法（如 Paxos）类似。对于性能来说，最重要的情况是当一个已确立的领导者正在复制新的日志条目时。Raft 通过使用最少数量的消息（从领导者到一半集群的单次往返）来实现这一点。也有可能进一步提高 Raft 的性能。例如，它很容易支持批量处理和流水线请求，以实现更高的吞吐量和更低的延迟。文献中已经为其他算法提出了各种优化方案；其中许多可以应用于 Raft，但我们将这留待未来的工作。
我们使用我们的 Raft 实现来测量 Raft 的领导者选举算法的性能，并回答两个问题。首先，选举过程是否能快速收敛？其次，在领导者崩溃后可以实现的最小停机时间是多少？
为了测量领导者选举，我们反复使一个由五台服务器组成的集群的领导者崩溃，并记录检测到崩溃并选举出一个新领导者所需的时间（见图 16）。为了生成一个最坏的情况，每次试验中的服务器具有不同的日志长度，所以一些候选者没有资格成为领导者。此外，为了促使选票分散，我们的测试脚本在终止领导者进程之前触发了一次来自领导者的同步心跳 RPC 广播（这近似于领导者在崩溃之前复制一个新日志条目的行为）。领导者在其心跳间隔内均匀随机地崩溃，这个心跳间隔是所有测试中最小选举超时时间的一半。因此，最小可能的停机时间大约是最小选举超时时间的一半。
图 16 中的上图显示，在选举超时时间中加入少量的随机性就足以避免选举中的选票分散情况。在没有随机性的情况下，由于有很多分散的选票，在我们的测试中，领导者选举持续的时间总是超过 10 秒。仅仅增加 5 毫秒的随机性就有很大帮助，使得停机时间的中位数为 287 毫秒。使用更多的随机性可以改善最坏情况下的表现：当有 50 毫秒的随机性时，最坏情况下的完成时间（经过 1000 次试验）为 513 毫秒。
图 16 中的下图显示，通过减少选举超时时间可以减少停机时间。当选举超时时间为 12 - 24 毫秒时，选举出一个领导者平均只需要 35 毫秒（最长的一次试验花费了 152 毫秒）。然而，将超时时间降低到这个点以下会违反 Raft 的时间要求：领导者难以在其他服务器开始新的选举之前广播心跳。这可能会导致不必要的领导者变更并降低整个系统的可用性。我们建议使用一个保守的选举超时时间，如 150 - 300 毫秒；这样的超时时间不太可能导致不必要的领导者变更，并且仍然能够提供良好的可用性。
10. 相关工作
已有大量与共识算法相关的出版物，其中许多可归入以下类别之一：
- 兰伯特对 Paxos 的原始描述 [15]，以及试图更清晰地解释它的尝试 [16,20,21]。
- Paxos 的详细阐述，填补了缺失的细节并修改算法，为实现提供更好的基础 [26,39,13]。
- 实现共识算法的系统，如 Chubby [2,4]、ZooKeeper [11,12] 和 Spanner [6]。Chubby 和 Spanner 的算法尚未详细公布，尽管两者都声称基于 Paxos。ZooKeeper 的算法已被更详细地公布，但它与 Paxos 有很大不同。
- 可应用于 Paxos 的性能优化 [18,19,3,25,1,27]。
- 冲野和利斯科夫的视图戳复制（VR），这是与 Paxos 大约同时开发的另一种达成共识的方法。原始描述 [29] 与分布式事务协议交织在一起，但在最近的更新中，核心共识协议已被分离出来 [22]。VR 采用基于领导者的方法，与 Raft 有许多相似之处。
11. 结论
算法通常以正确性、效率和 / 或简洁性作为主要目标来设计。虽然这些都是有价值的目标，但我们认为可理解性同样重要。在开发人员将算法转化为实际实现之前，其他目标都无法实现，而实际实现不可避免地会偏离并扩展已公布的形式。除非开发人员对算法有深刻的理解并能对其产生直觉，否则他们很难在实现中保留其理想的特性。
在本文中，我们解决了分布式共识问题，在这个领域中，一个被广泛接受但难以理解的算法 ——Paxos，多年来一直挑战着学生和开发人员。我们开发了一种新算法 ——Raft，我们已经证明它比 Paxos 更容易理解。我们也相信 Raft 为系统构建提供了更好的基础。将可理解性作为主要设计目标改变了我们设计 Raft 的方式；随着设计的进展，我们发现自己反复使用一些技术，例如分解问题和简化状态空间。这些技术不仅提高了 Raft 的可理解性，还使我们更容易确信它的正确性。
问题
以下是我在读论文过程中产生的疑问，大多数问题可以在读完论文以后得到解答。
Raft协议中，client端发送请求到Raft集群的leader节点之后，什么时候会返回client端？
当Leader收到客户端的写请求，到将执行结果返回给客户端的这个过程，从Leader视角来看经历了以下步骤：
raft算法，有没有可能有多个candidate同时获得了多数票？
在 Raft 共识算法中，多个 candidate 节点同时获得多数票的情况是不可能的。
主要有两个原因：
- 单一投票规则
在每一轮选举（即每个任期 term）中，每个节点只能投票给一个 candidate。因此，一个节点不可能同时把票投给两个不同的 candidate。这意味着，多个 candidate 要同时获得多数票，在逻辑上是互斥的。
- 选举时间随机化
每个节点的 Election Timeout 是随机的，因此不同节点转变为 candidate 并发起选举的时间点通常不会相同。由于超时时间不同，首先发起选举的 candidate 很可能已经赢得了选举，其他节点在同一轮投票中无法再成为 leader。
raft算法中，节点根据什么规则投票?
节点在投票时遵循以下规则：
- 每个任期内只能投出一票：节点在任期内只能投给一个候选者。如果已经给一个候选者投过票，即使后来有其他候选者发出请求，节点也不会改变投票。
- 只有日志最新的候选者才能获得选票：节点会比较候选人的日志和自己的日志，确保候选人的日志不落后于自己的日志。
- 候选人的任期必须大于等于自己的任期：如果候选人的任期小于当前节点的任期，节点会拒绝投票。
Raft 算法在 CAP 理论中属于哪种系统
Raft 算法在 CAP 理论中通常被归类为 CA 系统（Consistency and Availability）。下面是对这一分类的详细解释：
1.CAP 理论概述
CAP 理论由 Eric Brewer 提出，指出在分布式系统中，不能同时满足以下三项特性：
- Consistency（一致性）：所有节点在同一时间看到相同的数据视图。
- Availability（可用性）：系统在任何时候都能够处理请求并返回响应，即使部分节点发生故障。
- Partition Tolerance（分区容忍性）：系统能够继续在网络分区的情况下工作。
根据 CAP 理论，任何分布式系统在面对网络分区的情况下，必须在一致性和可用性之间做出权衡。
2. Raft 算法的特性
一致性：Raft 通过强一致性保证机制，确保所有节点在任期内一致地更新日志和状态。这意味着在某一时刻，所有节点必须看到相同的数据。
可用性：Raft 在大多数情况下能够保持可用性。当集群中的节点能够正常通信时，Raft 可以继续处理请求并响应客户端。
分区容忍性：虽然 Raft 具有分区容忍性，但在发生网络分区时，它选择牺牲可用性以保持一致性。只有在能获得多数节点的情况下，Raft 才能成功选举出 leader，并执行写操作。若无法达到多数节点，则系统会拒绝请求，以确保一致性。
3. CA 系统的表现
在实践中，当网络分区发生时，Raft 会选择不允许某些节点参与投票，从而导致系统可能会变得不可用。此时，虽然分布式系统中的其他节点仍然可以响应请求，但它们不会对外提供可能与领导者状态不一致的写入。
总结
综上所述，Raft 算法在 CAP 理论中被归类为 CA 系统。它优先保证一致性和可用性，但在面对网络分区时，会牺牲可用性以确保数据的一致性。这种设计使得 Raft 算法在保证系统稳定性和数据一致性方面表现出色，尤其适用于对一致性要求较高的应用场景。
raft理论只适用于k-v系统吗？是否适用于关系型数据库
Raft 算法并不仅限于键值存储 (K-V) 系统，它实际上适用于任何需要高可用性和一致性的分布式系统，包括关系型数据库。
典型的例子是TiDB， 其官网描述了TiDB对于强一致性的实现。
Raft 是一种一致性协议，能提供强一致的数据复制保证，TiDB 最底层用 Raft 来同步数据。每次写入都要写入多数副本，才能对外返回成功，这样即使丢掉少数副本，也能保证系统中还有最新的数据。