Raft 算法相关

[andj4cn]

抛出原论文：

Raft uses the voting process to prevent a candidate from winning an election unless its log contains all committed entries. A candidate must contact a majority of the cluster in order to be elected, which means that every committed entry must be present in at least one of those servers. If the candidate ’ s log is at least as up-to-date as any other log in that majority (where “ up-to-date ” is defined precisely below), then it will hold all the committed entries... 这是说，leader 必须包含所有已提交的日志，那么选择时候选节点必须是 up-to-date 的。

Raft determines which of two logs is more up-to-date by comparing the index and term of the last entries in the logs. If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date. 这是说，判断 up-to-date 的标准是，term 号越大越新； term 号一致则日志越长越新。

我想问下，满足这个 up-to-date 标准，为什么该候选节点就包含了所有的已提交日志了？

[misaka19000]

term 越高，说明这个节点与 leader 进行数据同步的时间越近，自然其 commitIndex 越准确；这是前提，因为 commit 只能由 leader 进行
如果两个节点的 term 一致，说明他们都有同一个 leader，同一个 leader 的 commitIndex 是一致的，所以选择 commitIndex 较大的那个

[yemenchun1]

因为假设某节点会 win the election 但是有一些 committed 的 log 它没有，那么根据 committed 的标准，一定会有等于一半总节点数的活着的节点含有了这个 committed 的 log。而因为这些节点有该节点没有的而且 committed 的 log, 那么这些其他节点就要么比该节点 term 大，要么与该节点同 term 但比该节点 log 长，因此则会比该节点更 up-to-date，从而导致有大于等于一半总节点数（有 committed log 的那些节点和失联的 leader 节点）的节点不给他 vote, 使其不能 win the election. 最后会是那些有更多 committed 的 log 的节点 win the election. 因此，win the election 的节点一定是含有所有 committed 的 log 的节点。不知道说的对不对，欢迎讨论。如果这回答写在知乎上，一定会有人说怎么又中英文混写了，不过会说这话的人估计也不会点进来这个问题，23333

[andj4cn]

@yemenchun1 有一个地方我不太明白，就是`其他的包含当前节点没有的 committed 的 log， 那么这些其他节点就要么比该节点 term 大，要么与该节点同 term 但比该节点 log 长` 这个是为什么呢？求指教

[yemenchun1]

我之前说的不清楚，我丢失了一个“最后一个 entry ”，如果我重新说一遍这句话，我会这么说：`其他的包含当前节点没有的 committed 的 log， 那么这些其他节点就要么<最后一个 entry>的 term 比该节点<最后一个 entry>的 term 大，要么与该节点<最后一个 entry>同 term 但<log>比该节点 log 长`。原文："Raft determines which of two logs is more up-to-date by comparing the index and term of the last entries in the logs. If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up to date"。你看现在你懂没懂？还没明白的话我再继续解释

[yemenchun1]

@andj4cn 记住你会比较两个 term，第一个 term 是 node 本身的 term，如果这个 term 小了，会被直接拒绝 vote，被拒绝的 node 会 step back as follower。但是，尽管如此，如果这个 node 足够幸运，他还有机会在 update 了自己的 term 之后再次 request vote, 因为他已经把自己的 term 更新成别人比较高的 term 了，所以而后比较的将是第二个 term，即 last_log_entry 的 term，在这里才用到 up-to-date 的比较原则。你看你懂了没？

[yemenchun1]

@andj4cn 我刚刚又考虑了一下，我发现你有一个地方理解可能有所偏差，Raft 不会说哪个节点 up-to-date 了，而是说某一个节点比另一个节点更 up-to-date，就是说 more up to date than another node 或者说 at least as up to date as another node. 另外也不是说某一个 node 比另一个 node 更 up-to-date 就表示这个 node 有所有 committed entries, 而是说某一个 node 要比 any other node*都*更 up-to-date 才能表示这个 node 有所有 committed entries. 你看下我理解的你的理解和你实际的理解是不是相同？

[yemenchun1]

@andj4cn 有了我在 6L 所说的这个基础，你再看下你的问题，就是说成功的 candidate 必须比 any other node 都更 up to date, 也就是说一个 entry 只要 committed 了，只要还有一个活着的 peer 有这个 entry，那么这个 candidate 就也得有这个 entry，否则他就没有比这个 peer 更 up to date （这里可以考虑下反证）。如果假设所有有这个 committed entry 的 peer 全死了，也就是说 > 1/2 的 peer 都死了，那么这个 candidate 就会得不到足够的投票。在前面两种情况下无论哪种，这个 candidate 都不能成为 leader。如果还有疑问，可以再继续讨论

[yemenchun1]

@andj4cn 反证的过程可以考虑：没有 committed entry 的 node 因为自己更 up to date 而成为 leader -> leader 会保留自己有的 entries 而删掉自己没有的 entries -> follower 的 committed 的 entry 因为 leader 没有而需要被删掉（!!!!） 那么这个 committed entry 他就不是个 committed entry。