9.raft共识性算法-Part.1

raft共识性算法-Part.1

最近在做 MIT 6.824 的 lab，其中 lab3 要求我们基于给出的代码框架，实现自己的 raft 算法。做该 lab 的时候遇到了不少困难，这是一个相当有趣又充满挑战的任务，有些地方必须要反复阅读论文并揣摩其中的意思才能理解。

如果你也在做这个 lab，不建议用 AI 逃课，论文中的 Part5 是必须要读的，否则实现代码的时候思路会很混乱。

论文连接：https://raft.github.io/raft.pdf

本篇文章主要聚焦于论文的第五部分，也就是 raft 算法的核心实现部分给出个人的理解。

The Raft consensus algorithm 核心总结

这张图（原文 Figure2）简明地总结了该算法，也是全文最重要的部分。总结为下面的文字部分：

State

所有服务器上的持久化状态（在响应 RPC 之前就更新到稳定存储）：

• currentTerm：服务器看到的最新 term（初始为0，之后单调递增）
• voteFor：在当前term下，服务器把票投给了谁？candidateId
• log[]：log entries；其中每个 log entry 包括 - command（要发给状态机的命令）、term（leader 收到 log entry 时的 term）

所有服务器上的易变状态：

• commitIndex：提交过的 log entry 的最高索引 index（commit 标识着共识，committed log entry 最终会被执行）
• lastApplied：已应用于状态机的 log entry 的最高索引 index（apply 表示真正执行了）

leader 上的易变状态（选举后重置）：

• nextIndex[]：对每个服务器 i，nextIndex[i] 是下一个应该发送到该服务器的 log entry 的索引 index
• matchIndex[]：对每个服务器 i，matchIndex[i] 是已在该服务器上复制过的 log entry 的最高索引 index（初始为0，之后单调递增）

RequestVote RPC（candidate 用它来请求其他 server 投票）

Arguments：

• term：candidate 的 term
• candidateId
• lastLogIndex：candidate 的最新 log entry 的索引 index
• lastLogTerm：candidate 的最新 log entry 的 term

Results：

• term：currentTerm，用于 candidate 发现自己可能不是最新的，更新自己
• voteGranted：bool，是否收到该服务器的票

接收方需要实现：

1. 如果 term < currentTerm，返回 false
2. 如果 voteFor == null or voteFor == candidateId，并且 candidate 的 log 与接收方的 log 一样新，就投票给它

这里的一样新：谁的 log 更新，取决于谁的 term 更新，如果 term 相同，取决于 index 更大，一样新就是 log 的 term 和 index 都一样

AppendEntries RPC（leader 用它来追加日志和发送心跳）

Arguments：

• term：leader 的 term
• leaderId：便于将 client 打到 follower 的请求重定向给 leader
• prevLogIndex：leader 要发送新的 log entry 给 follower，prevLogIndex 是紧接着这些要发送的日志的前一条 log entry 的索引
• prevLogTerm：和上一条类似，prevLogIndex 索引处的 log entry 的 term
• entries[]：要发送的 log entries（心跳时为空，为了提高效率可能一次性发送多个日志条目）
• leaderCommit：leader 的 commitIndex

Results：

• term：currentTerm，用于 leader 发现自己可能不是最新的，更新自己
• success：bool，判断 follower 的 log entry 是否匹配 prevLogIndex 和 prevLogTerm

接收方需要实现：

1. 如果 term < currentTerm，返回 false
2. 如果接收方在匹配的 prevLogTerm 下 log entry 的索引不与 prevLogIndex 匹配，返回 false
3. 如果已经存在 log entry 和发送方发送的 log entry 冲突（索引相同但是 term 不同），删除已经存在的 log entry 及其后面的所有 log entries
4. 添加 log 中不存在的任何新的 log entries
5. 如果 leaderCommit > commitIndex，更新接收方的 commitIndex = min(leaderCommit, 最新 log entry 的 index)

Rules for Servers

All Servers:

1. 如果 commitIndex > lastApplied：递增 lastApplied，状态机执行这些 log[lastApplied]
2. 如果 RPC request or reply 中的 term > currentTerm：更新当前服务器 currentTerm = term，降级为 follower

Followers：

1. 响应 RPC from candidate and leader
2. 如果选举计时器超时：convert to candidate

Candidates：

1. 升级为 candidates 时，发起选举：
   • currentTerm++
   • 给自己投一票
   • 重置选举计时器
   • 发送 RequestVote RPC 给其他所有的服务器
2. 如果收到了超过半数服务器的票，成为 leader
3. 如果收到了来自另外一个新 leader 的 AppendEntries RPC，降级为 follower（新 leader：指 term 新）
4. 如果选举计时器超时：发起新的选举

Leader：

1. 选举时：不断发送心跳给每个服务器，以防选举计时器超时
2. 如果从客户端收到了命令：添加 log entry 到本地 log，在 log entry 被实际执行之后再返回response
3. 对于要发送的 follower，如果 leader 最新的 log entry 索引 >= nextIndex[i]（说明 follower 落后），发送从 nextIndex[i] 索引开始的log entries AppendEntries RPC
   • 如果成功发送，更新 nextIndex[i] 和 matchIndex[i]
   • 如果由于日志不一致导致发送失败，递减 nextIndex 然后重试
4. 如果存在 N，满足 N > commitIndex && 超过半数的 matchIndex[i] >= N && log[N].term == currentTerm，设置 commitIndex = N

始终成立的属性

原文 Figure3 的内容：

1. Election Safety：在同一 term 最多只有一个 leader 当选
2. Leader Append-Only：leader 从来不会覆盖或者删除 log 中已经存在的条目，只会追加新的条目
3. Log Matching：如果两个 log 包含了一个相同 term 且相同 index 的条目，那么在该索引之前的所有条目也全部相同
4. Leader Completeness：如果在一个给定的 term 内提交了一个 log entry，那么后续其他更高 term 的 leader 的日志中都会包含该 log entry
5. State Machine Safety：如果一个服务器执行了一条给定索引处的 log entry，那么其他服务器永远不会在这个索引处执行不同的 log entry

Raft basics 5.1

一个 raft 集群包含一些服务器，5个是一个经典的数字，可以容忍有两个服务器出错。在任何时间，每个服务器都处于三个状态中的一种：leader，follower，candidate。在正常情况下，有一个服务器是 leader，其他都是 follower。follower 是被动的：他们不会主动发送请求，只会简单的响应从 leader 和 candidate 发送的请求。leader 处理客户端的所有请求（如果一个客户端尝试与 follower 通信，follower 会把请求重定向到 leader）。第三种状态：candidate，用于选举新的 leader。下图展示了状态转换情况：

服务器状态图。followers 只会接受其他服务器的请求，如果一个 follower 接受不到任何联系，他会变成 candidate 并发起一次选举。candidate 如果收到了集群中过半服务器的选票就会变成新的 leader。leader 通常会一直运行直到自身故障。

raft 把时间分成特定长度的 terms，如下图所示：

时间被分成了 terms，每个 term 开始于一次选举。在一轮选举成功之后，单个 leader 会管理整个集群直到这个 term 结束（term 没有固定时长的，如果系统运行正常，那么就会一直处于这个 term）。如果选举失败了，那么该 term 这段时期没有 leader（下个 term 会重新选举）。terms 的转换可能在不同的服务器上于不同的时间被观察到。

Terms 被用连续的整数编号，每个 term 开始于一次选举，在这次选举内，一个或者多个 candidate 尝试竞争成为 leader。如果其中一个 candidate 赢得了选举，他就会成为这个 term 剩余期间的 leader。在某些情况下，一次选举可能会发生分票。此时，这个 term 可能会没有 leader，一个新的 term（便随着一个新的选举）将会很快发生。raft 确保在一个 term 内最多只有一个 leader。

不同的服务器可能在不同的时间观察到 terms 的转换，在某些情况下一个服务器可能没有观察到选举，甚至没有观察到整个 term。terms 在 raft 中扮演着逻辑时钟的角色，允许服务器检测过时的信息，比如过期的leader。每个服务器存储了 currentTerm 字段（自增字段）。任何情况下，服务器之间通信都需要交换 currentTerm 信息，如果一个服务器的 currentTerm 比其他服务器小，那么它就会更新它的 currentTerm 为更大值。如果一个 candidate 或者 leader 发现它的 currentTerm 过期了，他会立刻降级为 follower。如果一个服务器接受了一个带有过期 term 的请求，他会拒绝这次请求。

raft 服务器通过 RPCs 相互通信，基础的共识性算法只需要两种 RPCs（RequestVote 和 AppendEntries）。RequestVote RPCs 在选举时被 candidate 执行；AppendEntries RPCs 被 leader 执行，用于复制日志或者提供心跳给其他服务器。高阶段提供了第三种 RPCs 用于在服务器之间做快照传输。如果服务器在规定时间内没有收到响应，它们会重试 RPCs 请求。为了更好的性能，服务器通常并行发送 RPCs 请求。

Leader election 5.2

Raft 使用心跳机制来触发选举。当服务器启动的时候，它们最初作为 followers，只要服务器能从 leader 或 candidate 收到合法的 RPCs 请求，就会一直保持 follower 状态。leader 定期发送心跳（不带有日志条目的 AppendEntries RPCs）给所有 followers 以维护它们的状态。如果一个 follower 在一定时间内（称为 election timeout）没有收到请求，它就会认为 leader 出故障了，然后发起新的一轮选举来选出一个新的 leader

开启一次选举时，follower 会自增它的 currentTerm，然后转化为 candidate。他会先给自己投一票，然后通过并发的 RequestVote RPCs 请求，发送请求给集群中的所有其他服务器，candidate 会保持 candidate 状态，直到出现下面三种情况：

1. 它赢得了选举
2. 另一个服务器成为了 leader
3. 一段时间过去了，选举no winner

以下段落将分别讨论这三种情况：

1. candidate 赢得了选举条件是他收到了当前 term 下整个集群中的大多数选票（过半的票）。每个 server 在一个 term 中最多给 candidate 投一票，基于先到先得原则（5.4 添加了投票的额外限制）。过半原则确保了在一个 term 内最多只有一个 candidate 会赢得选举。一旦一个 caniddate 赢得了选举，就会变为 leader。然后这个 leader 对其他的所有服务器发送心跳来建立起他的 leader 身份，并且防止新的选举
2. 在等待其他服务器投票的过程中，candidate 可能收到来自另外一个server的 AppendEntries RPC，这个 server 宣称自己已经成为了 leader。如果这个 leader 的 term（RPC 的参数）比当前 candidate 的 term 更大或相等，candidate 会认可这个 leader，自己降级为 follower。如果 RPC 参数中的 term 比当前 candidate 的 term 小，candidate 会拒绝这次 RPC 请求然后继续保持 candidate 状态
3. 如果 candidate 即没有 win 也没有 lose 这次选举：因为很多 followers 在同一时间成为 candidate，出现了分票，导致没有 candidate 能获取过半的票。这种情况下，每个 candidate 将会超时过期，然后开始一轮新的选举（term++），并执行另外一次 RequestVote RPCs。然而，如果不采取额外措施，这种分票现象可能会不断重复出现。

raft 通过随机的 election timeout 来确保分票现象是低概率的，并且可以被快速的修复。为了避免第一次分票现象，election out 被设置为一个固定区间内的随机值（例如：150 - 300 ms）。这样可以分散服务器，便于在大多数情况下，仅仅只有一个服务器会超时。它赢得了选举然后在其他服务器触发超时之前发送心跳。同样的机制也被用于处理已经发生的分票现象，每个 candidate 在一次选举开始时重置它的随机 election timeout，等待其中一个 candidate 的 election timeout 超时，然后开启下一次选举。

Log replication 5.3

一旦 leader 被选举产生，它就开始接受客户端的请求。每个客户端请求包含一条将会被复制状态机执行的命令，leader 把命令作为一个新的 log entry 添加到 log 中。然后并发向其他的服务器发送 AppendEntries RPCs 来复制这条 log entry。当这条 entry 被安全地复制了（下文有提及），leader 会执行这条 enrty 然后返回执行结果给客户端。如果 followers 崩溃了或者运行缓慢，或者网络包丢失，leader 会无限期地重新尝试发送 AppendEntries RPCs （即便是在 leader 已经响应了客户端之后），直到所有的 follower 最终都储存了所有日志条目。

logs 用下图所示的方式组织：

logs 有许多条目（entries）组成，这些条目按次序编号。每个 enrty 包含了他被创建时的 term（图中方框内的数字）和一条指令（用于给状态机执行）。如果一个 entry 可以被状态机安全地执行，这条 entry 被认为是 committed 的。

每个 log entry 存储了状态机指令和 term（当这条 entry 被 leader 接受时的 leader term）。log entry 中的 term 用于检测日志之间的不一致，确保 Figure3 中的某些属性成立。每个 log entry 同样有一个整数索引来明确他在该 log 中的位置。

leader 决定了何时为在状态机上执行 log entry 的安全的时机，此时的 log entry 被视为 committed 的。raft 保证了 committed entries 具有持久性，确保这些 entries 最终会被所有可用的状态机执行。一旦创建这条 log entry 的 leader 把它复制到了过半的服务器上，这条 log entry 就是 committed 的（例如上图中的 entry 7，在 3 个 server 中存储）。这也会提交 leader 的 log 中的所有先前的 entries，包括被先前旧 leader 创建的 entries。这种提交是安全的。leader 会跟踪它所知的被提交过的 log entry 的最高索引，并在未来的 AppendEntries RPCs（包括心跳）中包含该索引，以便其他服务器最终能够获知。一旦 follower 知道一条 log entry is committed，它就会将这条 entry 在本地的状态机上执行（按照 log 的顺序）。

我们设计的 raft 日志机制旨在在不同的服务器上维持日志的高一致性。这不仅简化了系统的行为，使其更加容易预测，而且这是确保安全性的重要组成部分。raft 维护了以下属性，这些属性构成了 Figure3 种的日志匹配属性：

• 如果在不同 log 中的 两个 entries 有相同的索引和 term，则它们存储相同的命令
• 如果在不同 log 中的 两个 entries 有相同的索引和 term，则 log 在此之前的所有 entries 都是相同的

第一条属性来源于以下事实：一个 leader 基于给定的 index 和 term 最多创建一个 entry，并且 entry 在 log 中的 位置永远不会改变。第二条属性来源于：AppendEntries 的简单一致性检查。当发送一个 AppendEntries RPC 时，leader 会在发送信息中包含 prevLogIndex 和 prevLogTerm（prevLogIndex 和 prevLogTerm 是 leader 的 log 中，他接下来要发送的新 entries 的前一条 entry 的索引和 term）。如果 follower 在自己的 log 中没有找到给定 prevLogIndex 和 prevLogTerm 对应的 entry，她就会拒绝这些新的 entries。一致性检查起到归纳步骤的作用：初始 logs 的空状态满足 Log Matching Property，一致性检查在 logs 扩展时维持了 Log Matching Property。结果，只要 AppendEntries 返回 success，leader 就会知道 follower 的 log 和 leader 自身的 log 在新的 entries 之前完全相同。

通常情况下，leader 和 follower 的日志是保持一致的，因此 AppendEntries 的一致性检查将永远不会失败。然而，leader 故障可能会导致日志的不一致（旧 leader 可能没有来得及复制它 log 中的所有 entries）。这种不一致性可能会在一系列的 leader 和 follower 故障中不断累积。下图展示了 follower 和新的 leader 的 log 之间可能存在的差异。follower 中可能缺失 leader 中有的 entries，follower 中也可能包含 leader 中没有的 entries，甚至这两种情况可以同时发生。这些 log 中缺失或多余的 entries 可能跨越多个 terms。

当 leader 任职时，下面 a - f 的情况都可能发生在 follower 的 logs 中。每个方框代表一个 log entry，其中的数字代表这条 entry 的 term。一个 follower 可能缺少 entries（如 a - b），可能有多余的未提交的 entries（如 c - d），或者两种情况同时发生（如 e - f）。例如，情况（f）可能由以下产生：f 的服务器从 term2 开始作为 leader，在它自己的 log 中添加了一些 entries，但在提交它们之前崩溃了。它很快又重启了，重新成为了 term3 的 leader，然后又在它自己的 log 中添加了更多的 entries。但 term2 和 term3 中的 entries 都还没被来得及提交，该服务器再次崩溃并在接下来的几个 term 中持续宕机。

在 raft 中，leader 通过强制让 follower 的 log 复制 leader 自己的 log 来解决这种不一致。这意味着 follower logs 中冲突的 entries 将会被 leader 的 log 覆盖。5.4 证明这种行为是安全的（当和另外一个限制条件结合使用）

为了让 follower 的日志和 leader 自己保持一致，leader 必须找到它与 follower 匹配的最新的 log entry，删除在此之后的 follower 的 log 中所有的 entries，然后把 leader 在此之后的所有 entries 发送给 follower。这些行为发生在响应 AppendEntries 的一致性检查的 response 中。leader 为每个 follower 维护一个 nextIndex[i] 字段，标识了 leader 将要发送给 follower 的下一个 entry 的索引。当 leader 第一次任职时，他会初始化所有 nextIndex 的值为它最新 log entry 索引的下一个索引（以上图为例，nextIndex[i]就是 11）。如果 follower 的 log 和 leader 不一致（一致的判断是通过 AppendEntries 中的 prevLogIndex 和 prevLogTerm 与 follower 中的 log entries 匹配），在下一次 AppendEntries RPC 中 AppendEntries 一致性检查会失败。在拒绝 AppendEntries 之后，leader 会递减 nextIndex[i] 然后重试 AppendEntries RPC。最终 nextIndex[i] 会到达一个索引，使 leader 和 follower 的 logs 相匹配，此时 AppendEntries 会成功，这会移除 follower 的 log 中后面所有冲突的 entries，然后从 leader 的 log 中添加 entries。一旦 AppendEntries 成功，follower 的 log 就和 leader 一致了，并在这个 term 的后续时间保持这种状态。

如果需要，可以优化协议来减少 AppendEntries RPCs 的拒绝次数。例如，当拒绝一个 AppendEntries 请求时，follower 可以在返回值中包含冲突 entry 的 term 和这个 term 任期存储的第一个 entry 的索引。laeder 可以通过这条信息来递减 nextIndex[i] 来跳过该 term 的所有冲突 entries，而不是每个 entry 都要通过 RPC 确认一次。但实际上，这种优化不是必要的，因为故障发生的频率很低，也不会存在大量不一致的条目

通过这种机制，当 leader 任职时，不需要采取特殊的行为来恢复日志的一致性。它只需要正常运行，日志根据给 AppendEntries 一致性检查返回的错误，自动整理汇聚。leadr 永远不会覆盖或者删除它自己已经存在的 log entries

这种日志复制机制体现了理想的共识机制特性：只要过半的服务器正常运行，raft 就可以接受、复制、执行新的 log entries。通常情况下一条新的 entry 可以通过一轮 RPCs 调用复制到集群中的过半的节点上，某个运行缓慢的 follower 不会影响整个系统的表现。

Safety 5.4

先前的章节描述了 raft 的 leader 选举和日志复制机制。然而，这些机制目前不足以确保每个状态机都会精确地按照相同的顺序，执行相同的指令。例如，某个 follower 发生故障变得不可用，同时 leader 提交了一系列的 log entries，后来这个故障的节点恢复并被重新选举为了 leader，它追加了新的 entries。结果，不同的状态机可能会执行不同的命令序列。

这个章节完善了 raft 算法，添加了一个节点可以被选为 leader 的限制条件。这个限制条件确保了任何 term 下的 leader 拥有在此 term 之前的所有 committed entries。基于该限制条件，我们为提交制定了更精确的规则。最后，我们给出了 Leader Completeness（领导者完备属性）的证明概要，展示了它是如何引导复制状态机做出正确的行为的。

Election restriction 5.4.1

在任何基于 leader 的共识算法中，leader 必须最终保存所有已经提交的 log entries。在某些共识算法中，例如 Viewstamped Replication，即使 leader 最初并不包含所有已提交的条目，也可以被选出。这些算法包含额外的机制来识别缺失的条目，并在选举过程中或选举后不久将其传输给新的领导者。然而，这会导致大量的额外机制和复杂性。raft 采用了一种更简单的方式，确保在选举之时，任何新的 leader 就都必须具备先前 terms 中所有已经提交的 entries，而不需要发送额外的 entries 给 leader。这意味着 log entries 是单向传输的，只能从 leader 传输到 follower，并且 leader 从来不会覆盖它们的 logs 中已经存在的 entries。

raft 使用投票过程来确保只有拥有全部 committed entries 的 candidate 才会被选为 leader。一个 candidate 必须与集群中的过半服务器通信才能胜出，意味着每个 committed entry 都必须出现在这些过半服务器中的至少一个。如果 candidate 的 log 至少与这些过半服务器中任何 log 一样新（新的定义见下文），那么这个 candidate 就会包含全部的 committed entries。RequestVote RPC 实现了该限制：RPC 中包含了 cadidate 的日志信息，如果 follower 发现自己的 log 比 candidate 的 log 更新，follower 就会拒绝投票。

raft 判断两个 logs 哪一个更新是通过比较最后一条 log entry 的 index 和 term，如果 last entries 有不同的 term，那么拥有更大 term 的就更新；如果 term 相同，谁的日志更长（index 更大）谁就更新

Committing entries from previous terms 5.4.2

正如像 5.3 节描述的那样，在当前 term 下，一旦一条 entry 存在于过半的服务器上，leader 就会认为这条 enrty 是 committed 的。如果 leader 在提交这条 entry 之前故障了，未来的 leader 将会尝试完成这条 entry 的复制任务。然而，新的 leader 不能因为这条 entry 在先前任期 term 中存在于过半的服务器上就认为这个 entry 在新的 term 内是 committed 的。下图展示了一种情况：旧的 log entry 存储在了过半的服务器上，但是新的 leader 仍然可能把这些 log entries 覆盖掉。

一种情况展示了为什么 leader 不能使用来自旧 terms 的 log entries 来确定提交状态。在（a）中，S1 是leader，把 term2 的 log entry 复制到了部分服务器上。在（b）中，S1 崩溃了，S5 被选举为了 term3 新的 leader（收到了来自 S3，S4 的选票），接着 S5 在 index = 2 处接受到了一条新的 log entry（不同于之前的 term2，用颜色区别），在（c）中，S5 崩溃了，S1 恢复并成为了新的 leader，继续他的复制任务。在这种情况下，来自 term2 的 log entry 被复制到了过半的服务器上，但是还没有提交。此时在（d）中，S1 再次崩溃了，S5 又被选举为了新的 leader（S5 的 log entry 的 term 更新），然后他开始复制日志到其他服务器上，用 term3 的日志覆盖掉了其他服务器上的日志。然而，如果 S1 在第二次崩溃之前，把 term4 的 log entry 复制到了过半的服务器上，如（e）中所示，那么这条 entry is committed，在 S1 发生第二次崩溃时，S5就无法赢得选举。这种情况下所有先前的 log entries 才会全部提交。

为了消除图8中的情况，raft 永远不会仅仅通过复制数目提交来自先前 terms 的 log entries。只有当 log entries 来自当前 leader 任期时才会通过判断复制数目过半来提交；一旦一个来自当前 term 的 entry 被以这种方式提交，那么所有先前的的 entries 都也会被间接提交（由于 Log Matching 属性）。有一些这样的情况：leader 可以安全地推断出一条旧的 log entry 是 committed 的（比如所有服务器上都储存了这条 log entry），但是 raft 采用了更加保守的简化方式。

Safety argument 5.4.3

这部分是关于 leader completeness 的证明，感兴趣可以自己看原文。

Follower and candidate crashes 5.5

目前为止我们聚焦于 leader 故障。相对于 leader 故障，follower 和 candidate 的故障更加简单，它们被用同样的方式来处理。如果一个 follower 或者 candidate 发生故障，未来发送到该服务器的 RequestVote 和 AppendEntries RPCs 将会失败。raft 通过无限期不断重试来解决这些故障。如果故障的服务器重启，RPC 就会成功完成。如果一个服务器在处理 RPC 成功，但是在 responde RPC 之前故障，它将会在重启后收到一个相同的 RPC 请求。raft RPCs 是幂等的，因此这不会有错。例如，一个 follower 收到了一个 AppendEntries 请求，请求包含了已经存在于该服务器的 log entries，服务器会简单的忽略这些 entries。

Timing and availability 5.6

我们对 raft 的要求之一是：safty 必须不能依赖时间。系统不能因为某些事件发生的比预期时间快或者慢就产生错误的结果。然而，可用性（系统及时响应客户端的能力）不可避免地依赖于时间。例如，如果信息交换花费了太长时间，超过了服务器通常崩溃之间的时间，candidate 将没有足够的时间来赢得一次选举。没有稳定的 leader，系统就会不可用。

raft 中时间是很关键的，leader 选举只体现了其中一方面。只要系统满足下面的时间要求，raft 将会顺利选举并维护一个 leader：

broadcastTime <= electionTimeout <= MTBF

• broadcastTime 是一个 server 并行向集群中所有 server 发送 RPCs 并收到回复所需要的平均时间
• electionTimeout 是选举计时器的超时时间
• MTBF 是每两个服务器发生故障的平均时间

broadcastTime 应该比 electionTimeout 小一个数量级，以便 leader 可以稳定发送心跳来防止 follower 发起新的选举；由于 electionTimeout 采用随机生成的方式，这种不确定性也降低了分票的概率。electionTimeout 应该比 MTBF 小几个数量级以便系统可以稳定运行。当 leader 故障时，系统将会有一段时间变得不可用，大概是 electionTimeout 的时长，我们希望这段时间只占据系统全部运行时间的一小部分。

broadcastTime 和 MTBF 是系统的潜在属性，而 electionTimeout 是我们可以实际控制的。raft 的 RPCs 通常需要接受者把信息持久化到稳定存储，因此 broadcastTime 可能在 0.5 —— 20 ms 范围内，取决于存储技术。结果，electionTimeout 可能会在 10 —— 500 ms 范围内。通常 MTBFs 长达几个月甚至更长，很容易满足时间规定要求。