raft
解决的问题： 一致性
用途：Fault Tolerant 在部分节点宕机后仍能正常服务
按照论文所述，原生的Paxos算法使用了一种点对点（peer-to-peer）的方式，所有节点地位是平等的。在理想情况下，算法的目的是制定一个决策，这对于简化的模型比较有意义。但在工业界很少会有系统会使用这种方式，当有一系列的决策需要被制定的时候，先选出一个leader节点然后让它去协调所有的决策，这样算法会更加简单快速。
关键阶段：
Leader Election：基于心跳
副本状态：
- Leader 接受client的更新请求，本地处理后再同步至其他副本
- Follower 从Leader接受更新请求，然后写入本地日志文件
- Candidate 如果Follower副本在一段时间内没有收到Leader副本的心跳，则判断Leader可能已经故障，此时启动选主过程，此时副本会变成Candidate状态，直到选主结束。
怎么选主
时间被分为很多连续的随机长度的term(任期)，term有唯一的id。每个term最多只有一个leader
Candidate 接收Leader心跳超时，启动选举
Raft集群启动时，所有节点都是follower，term为1
Follower 一段时间（为避免同一时间启动同时发起选举，超时时间每个节点随机生成）内没有收到任何Leader心跳，认为没有可用的leader，启动选举（term+1，状态改为candidate，发送RequestVote RPC）
投票
启动时，每个节点针对每个term只能投出一张票，并且按照先到先得的原则。这个规则确保只有一个candidate会成为leader。
已经有数据后，为保证被选为新leader的节点拥有所有已提交的log entry，candidate在发送RequestVoteRPC时，会带上自己的最后一条日志记录的term_id和index，其他节点收到消息时，如果发现自己的日志比RPC请求中携带的更新，拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term id更大，则更新，如果term id一样大，则日志更多的更大(index更大)。
投票后term+1
投票结果
1.选举成功（Step: receives votes from majority of servers）
当candicate从整个集群的大多数（N/2+1）节点获得了针对同一term的选票时，它就赢得了这次选举，立刻将自己的身份转变为leader并开始向其它节点发送心跳来维持自己的权威。
2.选举失败（Step: discovers current leader or new term）
当candicate在等待投票回复的时候，可能会突然收到其它自称是leader的节点发送的心跳包，如果这个心跳包里携带的term ≥ candidate当前的term，那么candidate会承认这个leader，并将身份切回follower。这说明其它节点已经成功赢得了选举，我们只需立刻跟随即可。但如果心跳包中的term比自己小，candidate会拒绝这次请求并保持选举状态。
3.选举超时（Step: times out, new election）
如果有多个follower同时成为candidate，选票是可能被瓜分的，如果没有任何一个candidate能得到大多数节点的支持，那么每一个candidate都会超时。此时candidate需要增加自己的term，然后发起新一轮选举。如果这里不做一些特殊处理，选票可能会一直被瓜分，导致选不出leader来。这里的“特殊处理”指的就是前文所述的随机化选举超时时间。
Log Replication - 选主以后
正常情况
当Leader接受客户端发来的请求，每个请求包含一条需要被replicated state machines执行的命令。leader会把它作为一个log entry append到日志中，然后给其它的server发AppendEntriesRPC请求。
当Leader确定一个log entry被safely replicated了（大多数副本已经将该命令写入日志当中），就apply这条log entry到状态机中然后返回结果给客户端。如果某个Follower宕机了或者运行的很慢，或者网络丢包了，则会一直给这个Follower发AppendEntriesRPC直到日志一致。
当一条日志是commited时，Leader才可以将它应用到状态机中。Raft保证一条commited的log entry已经持久化了并且会被所有的节点执行。
重新选主后恢复一致
新Leader产生后，就以Leader上的log为准。其它的follower要么少了数据，要么多了数据，要么既少了又多了数据。
因此，需要有一种机制来让leader和follower对log达成一致，leader会为每个follower维护一个nextIndex，表示leader给各个follower发送的下一条log entry在log中的index，初始化为leader的最后一条log entry的下一个位置。
leader给follower发送AppendEntriesRPC消息，带着(term_id, (nextIndex-1))， term_id即(nextIndex-1)这个槽位的log entry的term_id，follower接收到AppendEntriesRPC后，会从自己的log中找是不是存在这样的log entry，如果不存在，就给leader回复拒绝消息，然后leader则将nextIndex减1，再重复，知道AppendEntriesRPC消息被接收。
只允许主节点提交包含当前term的日志，历史数据冲突问题通过AppendEntriesRPC回溯解决
Log Compaction
避免系统重启时需要花很长的时间进行回放。
Raft采用对整个系统进行snapshot来处理，snapshot之前的日志都可以丢弃。Snapshot技术在Chubby和ZooKeeper系统中都有采用。
Raft使用的方案是：每个副本独立的对自己的系统状态进行Snapshot，并且只能对已经提交的日志记录（已经应用到状态机）进行snapshot。
当leader需要发给某个follower的log entry被丢弃了(因为leader做了snapshot)，leader会将snapshot发给落后太多的follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用新的RPC，InstalledSnapshot。
广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）
