Raft 作者亲自出的 Raft 试题，你能做对几道？

本文转自知乎：https://zhuanlan.zhihu.com/p/268571088

1.（4 分）下面的每张图都显示了一台 Raft 服务器上可能存储的日志（日志内容未显示，只显示日志的 index 和任期号）。考虑每份日志都是独立的，下面的日志可能发生在 Raft 中吗？如果不能，请解释原因。

2.（6 分）下图显示了一个 5 台服务器集群中的日志（日志内容未显示）。哪些日志记录可以安全地应用到状态机？请解释你的答案。

3.（10 分）考虑下图，它显示了一个 6 台服务器集群中的日志，此时刚刚选出任期 7 的新 Leader（日志内容未显示，只显示日志的 index 和任期号）。对于图中每一个 Follower，给定的日志是否可能在一个正常运行的 Raft 系统中存在？如果是，请描述该情况如何发生的；如果不是，解释为什么。

4.（5 分）假设硬件或软件错误破坏了 Leader 为某个特定 Follower 存储的 nextIndex 值。这是否会影响系统的安全？请简要解释你的答案。

5.（5 分）假设你实现了 Raft，并将它部署在同一个数据中心的所有服务器上。现在假设你要将系统部署到分布在世界各地的不同数据中心的每台服务器，与单数据中心版本相比，多数据中心的 Raft 需要做哪些更改？为什么？

6.（10 分）每个 Follower 都在其磁盘上存储了 3 个信息：当前任期（currentTerm）、最近的投票（votedFor）、以及所有接受的日志记录（log[]）。

a. 假设 Follower 崩溃了，并且当它重启时，它最近的投票信息已丢失。该 Follower 重新加入集群是否安全（假设未对算法做任何修改）？解释一下你的答案。

b. 现在，假设崩溃期间 Follower 的日志被截断（truncated）了，日志丢失了最后的一些记录。该 Follower 重新加入集群是否安全（假设未对算法做任何修改）？解释一下你的答案。

7.（10 分）如视频中所述，即使其它服务器认为 Leader 崩溃并选出了新的 Leader 后，（老的）Leader 依然可能继续运行。新的 Leader 将与集群中的多数派联系并更新它们的任期，因此，老的 Leader 将在与多数派中的任何一台服务器通信后立即下台。然而，在此期间，它也可以继续充当 Leader，并向尚未被新 Leader 联系到的 Follower 发出请求；此外，客户端可以继续向老的 Leader 发送请求。我们知道，在选举结束后，老的 Leader 不能提交（commit）任何新的日志记录，因为这样做需要联系选举多数派中的至少一台服务器。但是，老的 Leader 是否有可能执行一个成功 AppendEntries RPC，从而完成在选举开始前收到的旧日志记录的提交？如果可以，请解释这种情况是如何发生的，并讨论这是否会给 Raft 协议带来问题。如果不能发生这种情况，请说明原因。

8.（10 分）在配置变更过程中，如果当前 Leader 不在 C-new 中，一旦 C-new 的日志记录被提交，它就会下台。然而，这意味着有一段时间，Leader 不属于它所领导的集群（Leader 上存储的当前配置条目是 C-new，C-new 不包括 Leader）。假设修改协议，如果 C-new 不包含 Leader，则使 Leader 在其日志存储了 C-new 时就立即下台。这种方法可能发生的最坏情况是什么？

---

这里仅贴部分答案，供学习使用，需要查看更多的，请看原作者的公众号：多颗糖

3. 答案

答案：

(a) 不能。如果在不同的日志中的两条记录拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。 <5, 3> 在 Leader 和 a 中都存在，但是前面的日志却不相同。

(b) 不能。同上，<6, 5> 在 Leader 和 b 中都存在，但是前面的日志却不相同。

(c) 可能。c 可能是第 6 任期的 Leader，其起始日志为 <1,1>, <2,1> 并且可能在其日志中写了一堆记录，而没有与我们第 7 任期的当前 Leader 进行通信。这也假设当前 Leader 的 <3,3>、<4,3>、<5,3>、<6,5> 这几个日志记录在第 5 任期没有被写入，这是可能的。

(d) 不能。在一个日志中，任期只能是单调递增的。

(e) 可能。例如，e 是任期 1 的 Leader，提交了日志 <1,1> 和 <2,1>，然后与其它服务器失联（网络分区），但还在继续处理客户端请求。

4. 答案

答案：

不会。

如果 nextIndex 的值太小，Leader 将发送额外的 AppendEntries 请求。每个请求都不会对 Follower 的日志产生任何影响（它们将进行一致性检查，但不会和 Follower 日志中的记录产生冲突，也不会向 Follower 提供该 Follower 没有存储的任何日志记录），成功的响应将告诉 Leader 应该增加其 nextIndex。

如果 nextIndex 的值太大，Leader 也将发送额外的 AppendEntries 请求，对此，一致性检查将会失败，从而导致 Follower 拒绝该请求，Leader 将会递减 nextIndex 值并重试。

无论哪种方式，这都是安全的行为，因为两种情况下都不会修改关键的状态。

7. 答案

答案：

可能。仅当新 Leader 也包含正在提交的日志时，才会发生这种情况，所以不会引起问题。

下面是一个在 5 台服务器发生这种情况的例子：

•带有空日志的 S1 成为任期 2 的 Leader，票选来自 S1，S2 和 S3•S1 将 index=1, term=2, value=X 追加写到它自己和 S2•S2 的日志中包含 index=1, term=2, value=X，S2 成为任期 3 的 Leader，票选来自 S2，S4 和 S5•S1 将 index=1, term=2, value=X 追加写到 S3•此时，S1 已经完成了对 index=1, term=2, value=X 的提交，即使它不再是当前任期的 Leader

这种行为是安全的，因为任何新的 Leader 也必须包含该日志记录，因此它将永远存在。

该日志记录必须存储在给新 Leader（记为 L）投票的服务器 S 上，并且必须在 S 给新 Leader 投票之前存储在 S 上，日志完整性会检测，S 只能在以下情况投票给 L： L.lastLogTerm > S.lastLogTerm 或者 (L.lastLogTerm == S.lastLogTerm and L.lastLogIndex >= S.lastLogIndex)

如果 L 是 S 之后的第一任 Leader，那么我们必须处于第二个条件下，那么 L 一定包含了 S 拥有的所有日志记录，包括我们担心的那个记录。

如果 L' 是 S 之后的第二任 Leader，那么 L' 只有从 L 那里接收到了日志，它最新的任期号才可能比 S 大。但是 L 在把自己的日志复制到 L' 时也一定已经把我们担心的那条日志复制到 L' 了，所以这也是安全的。

而且，这个论点对未来所有的 Leader 都成立。