Raft 算法浓缩
Raft 论文给出了下面的表格，用于总结 Raft 算法精华 。
| 特性 | 解释 |
|---|---|
| 选举安全特性 | 对于一个给定的任期号，最多只会有一个领导人被选举出来 |
| 领导人只附加原则 | 领导人绝对不会删除或者覆盖自己的日志，只会增加 |
| 日志匹配原则 | 如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同 |
| 领导人完全特性 | 如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中 |
| 状态机安全特性 | 如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志 |
实际上，这些精华都是一条条限制推出来的。让我们一起看看是怎么推出来的。
选举安全特性
描述： 对于一个给定的任期号，最多只会有一个领导人被选举出来
如何实现？
Raft 规定：每个节点最多只会对一个任期号投出一张选票，按照先来先服务的原则（随机时间的重要性），同时，当一个候选人从整个集群的大多数节点获得了针对同一个任期号的选票，那么他就赢得了这次选举并成为领导人。
领导人只附加原则
描述：领导人绝对不会删除或者覆盖自己的日志，只会增加。
这个不需要保证别的规则保证，服务器自己搞定。
日志匹配原则
描述：如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同。
如何实现？
Raft 维护着以下特性：
- 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
- 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。
第一个特性来自这样的一个事实，领导人最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。
第二个特性由附加日志 RPC 的一个简单的一致性检查所保证。在发送附加日志 RPC 的时候，领导人会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。
领导人完全特性
解释：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中。
规则保证：
当一个 leader 提交了某条日志，然后崩溃了，候选者如果想当选 leader，必须满足以下条件：
- 首先比较任期号，谁都任期号大，谁就新。
- 如果任期号相同，那谁的日志长，谁就新。
- 获取过半投票者的选票。
同时，需要满足：leader 只能在自己当前任期的日志满足多数规则时，才能提交。
所以，当之前的 leader 成功提交最后一条日志，后面的候选者，必须包含过半已提交的最后一条日志的投票者的选票，才能成为 leader。
状态机安全特性
描述： 如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志。
解释：
通过领导人完全特性，我们就能证明状态机安全特性，即如果已经服务器已经在某个给定的索引值应用了日志条目到自己的状态机里，那么其他的服务器不会应用一个不一样的日志到同一个索引值上。
在一个服务器应用一条日志条目到他自己的状态机中时，他的日志必须和领导人的日志，在该条目和之前的条目上相同，并且已经被提交。
现在我们来考虑在任何一个服务器应用一个指定索引位置的日志的最小任期；日志完全特性保证拥有更高任期号的领导人会存储相同的日志条目，所以之后的任期里应用某个索引位置的日志条目也会是相同的值。因此，状态机安全特性是成立的。
参考
Raft paper 中文翻译 —— 寻找一种易于理解的一致性算法（扩展版）
EOF