从kafka选举，redis-sentinel哨兵选举，zk的选举，一路跑到这了。
Raft 理论是分布式数据一致性算法，由斯坦福大学两位教授提出。论文就不贴了，反正我也看不懂。
试着用网络上粘贴的内容和自己的理解能力，来阐述这个协议的有关内容，给自己加深点印象。免得就饭吃了。
为了令进程实现高可用，我们可以对进程进行备份，而实现进程的主从备份主要有两种方法：
- State Transfer（状态转移）：主服务器将完整的状态内容都传输给备份服务器
- Replicated State Machine（备份状态机）：将需要备份的服务器视为一个确定性状态机 —— 主备以相同的状态启动，以相同顺序导入相同的输入，最后它们就会进入相同的状态、给出相同的输出
其中 Replicated State Machine 是较为常用的主从备份实现方式。常见的 Replicated State Machine 架构如下
- 客户端向服务发起请求，执行指定操作
- 共识模块将该操作以日志的形式备份到其他备份实例上
- 当日志安全备份后，指定操作被应用于上层状态机
- 服务返回操作结果至客户端
分布式共识算法的职责就是按照固定的顺序将指定的日志内容备份到集群的其他实例
上：
一 Raft 强一致性算法
在Raft体系中，有一个强leader，由它全权负责接收客户端的请求命令，并将命令作为日志条目赋值给其他服务器，在确认安全的时候，将日志命令提交执行。当leader故障时，会选举产生一个新的leader。在强leader的帮助下，Raft将一致性问题分解为了三个子问题：
1 Leader选举：当已有的leader故障时必须选出一个的leader
2 日志复制：leader接收来自客户端的命令,记录为日志，并复制给集群中的其他服务器，并强制其他节点的日志与leader保持一致。
3 安全safety措施: 通过一些措施确保系统的安全性，如确保所有状态机按照相同顺序执行相同命令的措施。
1） 基本概念：
一个Raft集群拥有多个服务器，典型值是5，这可以容忍两台服务器出现故障，服务器可能会成为三种角色：
leader，candidate，follower。
正常运行的情况下，会有一个leader，其他全为follower,follower只会响应leader和candidate的请求，而客户端的请求则全部由leader处理，即使有客户端请求了一个follower也会将请求重定向到leader。cadidate代表候选人，出现在选举leader阶段，选举成功后candidate将会成为新的leader,
（状态转换关系图）
1 集群刚启动时候，所有的节点都是follower。
2 在times out信号的驱使下，follower会转变成candidate去拉取选票，获得大多数选票后，就会成为leader，这时候如果其他候选人发现了新的leader已经诞生，就会自动转变为follower；
3 而如果另一个times out 信号发出时，还没有选举出leader，将会重新开始一次新的选举。可见，times out信号是是促使角色转换的关键因素，类似于操作系统中得到中断信号。
4 在Raft协议中，将时间分成那里一些任意长度的时间片，称为term，term使用连续递增的编号的进行识别，如果下图所示：
a：每一个term都从新的选举开始，candidate们会努力争取成为leader。一旦获胜，它就会在剩余term时间内保持leader状态，在某些情况下（term3）选票可能被多个candidate瓜分，形不成多数派，因此term可能直至结束都没有leader，下一个term很快就会来重新发起选举。
b：term也起到了系统中的逻辑时钟的作用，每一个server都存储了当前term的编号，在server之间进行交流的时候就会带有该term编号，如果1个server的编号小于另外一个，那么它就会将之间的编号更新为较大的那一个；如果leader或者candidate发现自己的编号不是最新的了，就会自动转变为 follower;如果接收到的请求term编号小于子的当前term将会拒绝执行。
c server之间交流通过RPC进行的。只需要实现2种RPC就能构建一个基本的Raft集群:
RequestVote RPC: 它由选举过程中的candidate发起，用于拉取选票。
AppendEntries RPC: 它由leader发起，用于复制日志或者发送心跳信号。
2) leader选举过程
a: Raft通过心跳机制发起leader选举。节点都是从follower状态开始的，如果收到了来自leader或candidate的RPC，那它就保持follower状态，避免争抢成为candidate。
b: Leader会发送空的AppendEntries RPC作为心跳信号来确立自己的地位，如果follower一段时间(election timeout)没有收到心跳，它就会认为leader已经挂了，发起新的一轮选举。
c: 选举发起后，一个follower会增加自己的当前term编号并转变为candidate。它会首先投自己一票，然后向其他的所有节点，并行的发起RequestVote RPC,之后candidate状态将可能发生如下3种变化:
c1> 赢得大选，成为Leader： 如果它在一个term内收到了大多数的选票，将会在接下来的剩余term时间内成为leader，然后就可以通过发送心跳确立自己的地位。（每一个server在一个term内只能投一张选票，并且按照先到闲的的原则投出）
c2>其他的server成为leader：在等待投票时，可能会收到其他server发出AppendEntries RPC 心跳信号，说明其他leader已经产生。这时通过比较自己的term编号和RCP过来的term编号，如果比对方大，说明leader的term过期了，就会拒绝该RPC，并继续保持候选人身份；如果对方编号不比自己小，则承认对方的地位转为follower。
c3> 选票被瓜分，选举失败： 如果没有candidate获取大多数选票，则本届选举失败，没有leader产生。candidate们等待超时后发起另一轮选举为了防止下一次选票还被瓜分，必须采取一些额外的措施，Raft采用随机的election timeout 的机制防止选票被持续瓜分。
随机election timeout ：节点在进入新的 Term 时，会在一个固定的区间内（如 150~300ms）随机选取自己在该 Term 所使用的 Election Timeout。通过随机化来错开各个节点进入 Candidate 状态的时机便能有效避免这种情况的重复发生
3） 日志复制过程
一旦leader被选举成功，就可以对客户端提供服务了。
a: 客户端提交每一条命令都会被按顺序记录到leader的日志中，每一条命令都包含term编号和顺序去索引，然后向其他的节点并行发送AppendEntires RPC 用以复制命令（如果命令丢失会不断重发）。
b: 当复制成功也就是大多数节点成功复制后，leader就会提交命令，即执行该命令并且将执行结果返回客户端，raft保证已经提交的命令最终也会被其他节点成功执行。
c: leader会保存有当前已经提交的最高日志编号。顺序性确保了相同日志索引处的命令是相同的，而且之前的命令也是相同的。当发送AppendEntries RPC时，会包含leader上一条刚处理过的命令，接收节点如果发现上一条命令不匹配，就会拒绝执行。
理想很丰满，现实可能很骨感
特殊故障：如果leader崩溃了（可能也是连续几个月不发薪水的原因），它所记录的日志没有完全的被复制，会造成日志不一致的情况，follower相当于比当前的leader可能会丢失几条日志，也可能会额外多出几条日志，这种情况可能会持续几个term。如下图所示:
框内的数字是term的编号，
a,b 丢失了一些命令，c、d 多出来一些命令，e、f 既有丢失也增多。这些都是可能的情况；
f节点在term2时候是leader，在此期间写入了几条命令，然后在提交之前崩溃了，在之后的term3中它很快重启并再次成为leader，又写入了几条日志，在提交之前又崩溃了，（命运多遄的娃啊），等他苏醒过来的时候新的leader来了，就形成了上图情形，那么冲突的日志将会被重写。为了让日志一致，先找到最新的一致的那条日志（如f索引为3的日志条目），然后把follower之后的日志全部删除，leader再把自己在那之后的日志一股脑的推送给follower，这样就实现了一致。而寻找该条日志，可以通过AppendEntries RPC，该RPC中包含着下一次要执行的命令索引，如果能和follower的当前索引对上，那就执行，否则就拒绝，然后leader将会主次递减索引，直到找到相同的那条日志。
然而这样也还是会有问题，比如某个follower在leader提交时宕机了，也就是少了几条命令，然后它又经过选举成了新的leader,这样它就会强制其他follower跟自己一样，使得其他节点刚刚提交的命令被删除，导致客户端提交的一些命令被丢失了。
（哎~ 我的少你们不能比的多）。这种情况显然不希望看到，Raft通过为选举过程添加一个限制条件，解决了上面提出的问题。
解决方案：
该限制确保leader包含之前的term已经提交过的所有命令，Raft通过投票过程确保只有拥有全部已经已提交的所有命令。Raft通过投票过程确保只有拥有全部已提交的日志的candidate能成为leader。（把门槛提高了，如果美国总统没有限制，可能满大街都是参选人吧）由于candidate为了拉选票需要通过RequestVote RPC 联系其他节点，而之前提交的命令至少会存在于其中某一个节点上，因此只要candidate的日志至少和其他大部分节点一样新就可以了，follower如果收到了不如自己新的candidate的RPC，就会将其丢弃。
还可能会出现另外一个问题，如果命令已经被复制到大部分节点上，但是还没来的及提交就崩溃了，这样后来的leader应该完成之前term未完成的提交。Raft通过让leader统计当前term内还未提交的命令，已经被复制的数量是否半数以上，然后进行提交。
总结：
1 选举过程中有三种角色，follower，candidate，leader。
2 消息类型有vote 投票消息，heart beat 心跳消息，Follower接收leader的心跳消息，重置选举计时器。
选举过程：
1 节点刚启动，默认是Follower状态
2 启动之后，开启选举超时定时器，节点切换到Candidate状态，发起选举请求
3 当candidate状态的节点，接收到超过半数的投票，则成为主节点，切换到Leader状态。每一轮选举，每个节点只能投一次票
4 Leader状态的节点向其他节点发送心跳消息，其他Candidate状态的节点切换回Follower状态，并重置选举超时定时器
5 Leader节点收到更高任期号（term号）的消息，切换到Follower状态。这种情况主要发生在有网络分区时。