Raft 8问
state
所有服务器上持久化：
（在响应RPC之前更新到持久化存储）
- currentTerm：服务器发现到的最新term，或者说是服务器当前term。（从0递增）
- votedFor：当前term中，投票给的Candidate服务器的ID号。（null表示没有投票给谁）
- log[]：日志实体。包含给状态机的命令、收到此log时的term。（序号从1开始）
所有服务器上非持久化：
- commitIndex：当前服务器上已提交最高日志序号，此序号被大部分服务器写入log[]，因此可理解为可以被提交到状态机的最大序号。处于少部分落后的服务器，则保存自身最大日志序号。（序号从0开始）
- lastApplied：应用到状态机的最高日志序号，此序号是当前服务器已经提交到状态机的最高序号。
leader上非持久化：
（每次选举完毕后，重新初始化）
- nextIndex[]：leader将要发送给每个服务器的log序号。（初始化为log[]最大序号 + 1，可能减少，由于服务器日志缺失）
- matchIndex[]：leader需要了解每个服务器当前已经复制到哪个log，此为该log序号。（从0递增）
RequestVote RPC
Candidates在拉票时调用。即Candidates调用其他服务器上的此函数。
Arguments：
- term：candidate的currentTerm
- candidateId：candidate id号
- lastLogIndex：candidate log[]中最新的序号
- lastLogTerm：lastLogIndex 对应的 term
Results：
- term：所在服务器的 currentTerm，用于候选人更新自身 term
- voteGranted：true 表示candidate 收到该选票
实现：
- args.term < currentTerm，返回 false。
- 如果 votedFor为空或者等于 candidateId，并且candidate log 和 当前服务器log一样新（args.lastLogTerm > lastLogTerm，或者 rf.lastLogTerm == args.LastLogTerm && rf.lastLogIndex <= args.LastLogIndex），给与投票。
AppendEntries RPC
leader 心跳和复制日志时调用。
Arguments：
- term：leader 的 currentTerm
- leaderId：follower 用于对 client 请求重定向
- prevLogIndex：当前复制的日志的前一条日志索引
- prevLogTerm：当前复制的日志的前一条日志 term
- entries[]：将要复制的日志实体
- leaderCommit：leader的CommitIndex。这里也说明CommitIndex只有leader知道准确信息，需要由leader在发送心跳或者日志复制RPC时更新其他所有服务器。
Results：
- term：当前服务器的 currentTerm。用于leader更新，一旦leader发现 term 高于自身，那么自动降级为follower。
- success：当前服务器上已有的 log[] 包含有 prevLogIndex 和 prevLogTerm 都一致的日志，则为 true
实现：
- args.term < currentTerm，返回 false。
- 如果找不到匹配 prevLogIndex 和 prevLogTerm 的日志，返回false。
- 如果log[] 与 prevLogIndex 和 prevLogTerm 发生冲突，则删除此条包括之后的所有日志。
- 向log[] 中添加日志。
- 如果 leaderCommit > commitIndex，设置 commitIndex = min(leaderCommit, 日志最大下标)
Rules for Servers
所有服务器：
- 如果 commitIndex > lastApplied，则增加 lastApplied，应用 log[lastApplied] 到状态机。
- 如果 RPC 请求或者响应包含的 term > currentTerm，则更新 currentTerm = term，并转为 follower。
Followers:
- 响应来自 candidates 和 leader 的 RPCs
- 如果在选举超时时间内，没有收到 leader 的心跳，或者 candidate 的投票请求，则转为 candidate。
Candidates：
- 转变为 candidate 时，发起选举：
- 增加 currentTerm
- 投票给自己
- 重置选举超时时间
- 向其他服务器发送 RequestVote RPCs
- 如果收到大部分的选票，则转为 leader
- 如果在此期间收到来自新 leader 的心跳消息 AppendEntries RPC，则转为 follower
- 如果选举超时，发起新一轮选举
Leaders：
- 在选举中，发送空 AppendEntries RPC（心跳）给所有服务器，重复执行该动作避免其他服务器触发选举超时
- 对外，响应客户端的请求，把日志加到 log[]；对上，响应状态机同步日志的动作。
- 如果自身拥有的最新日志序号，大于nextIndex[某个 follower]，则发送 AppendEntries RPC 并携带此log[nextIndex[followerId]]：
- 若返回成功，则更新 nextIndex[followerId] 和 matchIndex[followerId]
- 若返回失败，且原因时log不一致，则降低 nextIndex[followerId] 并重发。
- 如果存在一个数 N，N > commitIndex，大多数 matchIndex[i] >= N，且 log[N].term == currentTerm，则更新 commitIndex = N。随后通过心跳通知所有服务器。
Raft八问
参考链接：https://ongardie.net/static/raft/userstudy/
1、下图显示了Raft服务器的一个可能的日志配置(日志条目的内容没有显示;只是它们的索引和术语)。孤立地考虑每个日志，是否可以在正确的Raft实现中进行日志配置?如果答案是“不”，解释为什么不。
答：
（a）不可以，因为日志中term总是单调递增。log<3, 3>（log<index, term>）不可能在log<4, 2>的前面。
（b）可以。
（c）可以。可能在term4中没有日志记录，或者term4没有选出leader。
（d）错误。日志不可能含有空洞。具体来说，领导者只在他们的日志中追加内容，而附录entries中的一致性检查从来不会匹配一个空洞。
2、下图显示了一个 5 台服务器集群中的日志（日志内容未显示）。哪些日志记录可以安全地应用到状态机？请解释你的答案。
答：apply的要求是半数以上的节点commit这条日志，符合的有log<1, 1>、log<2,1>、log<3,2>、log<4,2>、log<5,2>（log<index, term>）。
我们需要理清哪些节点会可能称为leader，然后观察它是否会删除某些日志。
如果节点2当选（节点2符合当选要求，它的最新term为3，比节点3、4、5的都大，可以获取半数以上节点支持），那么它可能会强制要求节点3、4、5日志和它同步，即删除节点2的log<4, 2>、log<5, 2>，删除节点5的log<4, 2>（包括）以后的所有日志。
因此只有日志log<1, 1>、log<2, 1>可以安全的应用的状态机。
3、考虑下图，它显示了一个 6 台服务器集群中的日志，此时刚刚选出任期 7 的新 Leader（日志内容未显示，只显示日志的 index 和任期号）。对于图中每一个 Follower，给定的日志是否可能在一个正常运行的 Raft 系统中存在？如果是，请描述该情况如何发生的；如果不是，解释为什么。
答：
（a）不可能。log<5, 3>（log<index, term>）和leader中有同样的对应日志，说明其前面的所有日志，应当和leader一致，因为每次append日志都会检查前一条日志是否和leader的一样。
（b）不可能。log<6, 5>和leader中有同样的对应日志。
（c）可能。此节点可能是term6的leader，记录了一些log但没有同步给其他节点。
（d）不可能。term一定是递增的。
（e）可能。此节点可能是term1的leader。
4、假设硬件或软件错误破坏了 Leader 为某个特定 Follower 存储的 nextIndex 值。这是否会影响系统的安全？请简要解释你的答案。
答：不会。如果nextIndex变小，则会重复之前已经同步过的日志，并且能够安全通过一致性检查。如果变大，则会follower拒绝请求，leader收到失败信息后会逐步减小nextIndex值。
日志一致性检查：每个AppendEntries消息中都包含期望的前一条日志的下标和term，如果发现下标或者term不一致，则认为一致性检查失败。
5、假设你实现了 Raft，并将它部署在同一个数据中心的所有服务器上。现在假设你要将系统部署到分布在世界各地的不同数据中心的每台服务器，与单数据中心版本相比，多数据中心的 Raft 需要做哪些更改？为什么？
答：我们需要设置更高的选举超时时间：我的预期广播时间更高，选举超时时间应该比广播时间高得多，这样候选人就有机会在再次超时之前完成选举。
算法的其余部分不需要任何更改，因为它不依赖于时间。
6、每个 Follower 都在其磁盘上存储了 3 个信息：当前任期（currentTerm）、最近的投票（votedFor）、以及所有接受的日志记录（log[]）。
a. 假设 Follower 崩溃了，并且当它重启时，它最近的投票信息已丢失。该 Follower 重新加入集群是否安全（假设未对算法做任何修改）？解释一下你的答案。
b. 现在，假设崩溃期间 Follower 的日志被截断（truncated）了，日志丢失了最后的一些记录。该 Follower 重新加入集群是否安全（假设未对算法做任何修改）？解释一下你的答案。
答：
（a）不安全。可能会导致在一个term内，同一个follower投了两次票，可能会产生两个leader，发生严重问题。
（b）将允许已提交的日志条目不存储在仲裁（quorum）中，然后允许其他日志条目提交为相同的CommittedIndex。
（b）举例，三个节点：
S1成为leader在term2，并追加log<1, 2>（log<index, term>）在S1和S2。
S1设置commitedIndex为1，并返回给客户端该日志（log<1, 2>）已提交。
S2重启并丢失了log<1, 2>。
S3成为leader在term3，因为它的日志和S2的一致（都没有log<1, 2>）。
S3追加log<1, 3>在S2和S3。
S3也设置committedIndex为1，并返回客户端已提交。
这样导致committedIndex发生错误。
7、如视频中所述，即使其它服务器认为 Leader 崩溃并选出了新的 Leader 后，（老的）Leader 依然可能继续运行。新的 Leader 将与集群中的多数派联系并更新它们的任期，因此，老的 Leader 将在与多数派中的任何一台服务器通信后立即*。然而，在此期间，它也可以继续充当 Leader，并向尚未被新 Leader 联系到的 Follower 发出请求；此外，客户端可以继续向老的 Leader 发送请求。我们知道，在选举结束后，老的 Leader 不能提交（commit）任何新的日志记录，因为这样做需要联系选举多数派中的至少一台服务器。但是，老的 Leader 是否有可能执行一个成功 AppendEntries RPC，从而完成在选举开始前收到的旧日志记录的提交？如果可以，请解释这种情况是如何发生的，并讨论这是否会给 Raft 协议带来问题。如果不能发生这种情况，请说明原因。
答：可以发生，不会产生问题。
举例，有5个节点：
S1有着空日志，并且在term2成为leader，收到了S1、S2和S3的投票。
S1追加日志log<1, 2, X>（log<index, term, value>），在S1和S2上。
S2带着日志log<1, 2, X>并在term3成为leader，收到了S2、S4和S5的投票。
S1完成日志追加log<1, 2, X> 在S3上。同时，S1认为log<1, 2, X>完成了提交，尽管它实际上不是leader。
leader要求必须是拥有最新的日志，即Raft要求的args.lastLogTerm > lastLogTerm，或者 rf.lastLogTerm == args.LastLogTerm && rf.lastLogIndex <= args.LastLogIndex。所以一旦某个leader当选，说明它的日志比过半节点的日志都要更新。
题目中所述的旧日志要么可以提交（过半节点保存），那么此时leader必然保存此日志；要么无法提交（过半节点没有保存），那么此时leader是否保存该节点都不重要。
8、在配置变更过程中，如果当前 Leader 不在 C-new 中，一旦 C-new 的日志记录被提交，它就会*。然而，这意味着有一段时间，Leader 不属于它所领导的集群（Leader 上存储的当前配置条目是 C-new，C-new 不包括 Leader）。假设修改协议，如果 C-new 不包含 Leader，则使 Leader 在其日志存储了 C-new 时就立即*。这种方法可能发生的最坏情况是什么？
答：有两种情况。
- 假设一个可能的实现——一旦服务器不再是其当前配置的一部分，它就不再是候选服务器。问题是，C-old中的另一个服务器可能会被选为leader，将C-new添加到它的日志中，然后立即退出。
更糟糕的是，这种情况可能会在大多数C-old服务器中重复出现。它不能再重复了，因为一旦大多数C-old存储C-new条目，由于日志完整性检查，没有该条目的C-old服务器无法当选(C-old+new所需的大多数C-old将不再将其投票给该服务器)。
在此之后，必须选择C-new中的服务器，集群将继续运行。所以最坏的情况是运行到大约（|C-old| / 2 ）额外的选举和选举超时时间。 - 设一个简单的实现允许不属于其当前配置的服务器仍然成为候选服务器。在这种情况下，可能发生的最糟糕的事情是leader在退出时再次当选(它的日志仍然是完整的)，然后再次退出，然后无限重复。