Raft学习笔记
在室友提议之下，开启Raft by Rust（挖坑）之旅。
第一步，当然是读raft论文了。此前并没有接触过分布式协议，只对paxos略有耳闻，初读起来还颇为生涩，故将心得/总结记录于此，若有错误，欢迎指正。
有条件建议读英文版，中文不少地方翻译生硬。
Leader竞选
三种节点：Follower、Candidate 和 Leader。Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms~300ms，如果在这个时间内没有收到 Leader 的心跳包，就会变成 Candidate，进入竞选阶段。
分布式系统的最初阶段只有 Follower 没有 Leader。Node A 等待一个随机的竞选超时时间之后，没收到 Leader 发来的心跳包，因此进入竞选阶段。
然后Node A 发送投票请求给其它所有节点。
其它节点会对请求进行回复，如果超过一半的节点回复了，那么该 Candidate 就会变成 Leader。
之后 Leader 会周期性地发送心跳包给 Follower，Follower 接收到心跳包，会重新开始计时。（在一段时间内没有收到 Leader 的心跳包，就会变成 Candidate，进入竞选阶段）
如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票。但由于每个节点设置的随机竞选超时时间不同，因此下一次再次出现多个 Candidate 并获得同样票数的概率很低。
日志复制
不愧是jmpotato大佬，建议我们手撸一个rpc出来，虽然这么小的Demo确实不太好意思用别人的框架，但此前没有接触过RPC使用，估计会比较吃力。
来自客户端的修改都会被传入 Leader。注意该修改还未被提交，只是写入日志中。
Leader 会把修改复制到所有 Follower，并等待大多数的 Follower 也进行了修改，然后才将修改提交。此后Leader 会通知的所有 Follower 让它们也提交修改，此时所有节点的值达成一致。
实现及细节
这部分对论文里提到的一些实现上的细节做笔记。
然而由于学车，我的Rust学习还是个半吊子。
就快过年了（叹气
安全性论证
这部分摘抄论文原话：
U 一定在刚成为 leader 的时候就没有那条被提交的日志条目了（leader 从不会删除或者覆盖任何条目）。
Leader T 复制该日志条目给集群中的过半节点，同时，leader U 从集群中的过半节点赢得了选票。因此，至少有一个节点（投票者）同时接受了来自 leader T 的日志条目和给 leader U 投票了，如图 9。该投票者是产生矛盾的关键。
该投票者必须在给 leader U 投票之前先接受了从 leader T 发来的已经被提交的日志条目；否则它就会拒绝来自 leader T 的 AppendEntries 请求（因为此时它的任期号会比 T 大）。
该投票者在给 leader U 投票时依然保有这该日志条目，因为任何 U 、T 之间的 leader 都包含该日志条目（根据上述的假设），leader 从不会删除条目，并且 follower 只有跟 leader 冲突的时候才会删除条目。
该投票者把自己选票投给 leader U 时，leader U 的日志必须至少和投票者的一样新。这就导致了以下两个矛盾之一。
首先，如果该投票者和 leader U 的最后一个日志条目的任期号相同，那么 leader U 的日志至少和该投票者的一样长，所以 leader U 的日志一定包含该投票者日志中的所有日志条目。这是一个矛盾，因为该投票者包含了该已被提交的日志条目，但是在上述的假设里，leader U 是不包含的。
否则，leader U 的最后一个日志条目的任期号就必须比该投票者的大了。此外，该任期号也比 T 大，因为该投票者的最后一个日志条目的任期号至少和 T 一样大（他包含了来自任期 T 的已提交的日志）。创建了 leader U 最后一个日志条目的之前的 leader 一定已经包含了该已被提交的日志条目（根据上述假设，leader U 是第一个不包含该日志条目的 leader）。所以，根据日志匹配特性，leader U 一定也包含该已被提交的日志条目，这里产生了矛盾。
因此，所有比 T 大的任期的 leader 一定都包含了任期 T 中提交的所有日志条目。
日志匹配特性保证了未来的 leader 也会包含被间接提交的日志条目，例如图 8 (d) 中的索引 2。
定时及可用性
Leader 选举是 Raft 中定时最为关键的方面。 只要整个系统满足下面的时间要求，Raft 就可以选举出并维持一个稳定的 leader：
广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）