共识算法 - Raft算法
1. 什么是 Raft 算法
Raft 是一种为了管理复制日志的共识算法。这个日志可以理解为一个比喻，相当于一个指令。允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。
Raft 算法和其他共识算法最相关的就是前面 2 个模块：领导人选举和日志复制
2.领导人选举
每个server都可能会在 3 个身份之间切换：
- 领导者
- 候选者
- 跟随者
而影响他们身份变化的则是 选举。
当所有服务器初始化的时候，都是 跟随者，这个时候需要一个 领导者，所有人都变成 候选者，直到有人成功当选 领导者。
角色轮换如下图：
image
而领导者也有宕机的时候，宕机后引发新的
选举，所以，整个集群在选举和正常运行之间切换，具体如下图：
image
从上图可以看出，选举和正常运行之间切换，但请注意， 上图中的 term 3 有一个地方，后面没有跟着
正常运行 阶段，为什么呢?
答：当一次选举失败（比如正巧每个人都投了自己），就执行一次 加时赛，每个 Server 会在一个随机的时间里重新投票，这样就能保证不冲突了。所以，当 term 3 选举失败，等了几十毫秒，执行 term 4 选举，并成功选举出领导人。
接着，领导者周期性的向所有跟随者发送心跳包来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。
要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后请求其他服务器为自己投票。那么会产生 3 种结果：
a. 自己成功当选
b. 其他的服务器成为领导者
c. 僵住，没有任何一个人成为领导者
注意：
- 每一个 server 最多在一个任期内投出一张选票（有任期号约束），先到先得。
- 要求最多只能有一个人赢得选票。
- 一旦成功，立即成为领导人，然后广播所有服务器停止投票阻止新得领导产生。
僵住怎么办？ Raft 通过使用随机选举超时时间（例如 150 - 300 毫秒）的方法将服务器打散投票。每个候选人在僵住的时候会随机从一个时间开始重新选举。
以上，就是 Raft 所有关于领导选举的策略。
3. 日志复制
一旦一个领导人被选举出来，他就开始为客户端提供服务。
客户端发送日志给领导者，随后领导者将日志复制到其他的服务器。如果跟随者故障，领导者将会尝试重试。直到所有的跟随者都成功存储了所有日志。
下图表示了当一个客户端发送一个日志给领导者，随后领导者复制给跟随者的整个过程。
image
4 个步骤：
- 客户端提交
- 复制数据到所有跟随者
- 跟随者回复 确认收到
- 领导者回复客户端和所有跟随者 确认提交。
可以看到，直到第四步骤，整个事务才会达成。中间任何一个步骤发生故障，都不会影响日志一致性。
4.Raft对比ZAB协议
共同点：
- 都是共识算法，写数据时都需要大部分成功才能把日志应用到状态机。
- 都有选主、日志对齐、数据广播的流程。
- 都把数据分成快照+日志。
区别
- primary-backup system or state machine system：raft是state machine system，zab是primary-backup system
- 处理只读请求：raft的读请求与写请求处理逻辑一样，zab用租约使得可以读任意副本
- 选主方式：raft比较last_log_index以及last_log_term保证选出的leader已经拥有最完整的数据，zab仅通过节点标识选主，所以需要之后的recovery过程，不过实现中zab也采用了类似于raft的选主方式
- 恢复方向：raft单向，仅从leader到follower补齐log；zab双向，leader需要从follower接收数据来生成initial history
- 当leader发给follower的数据出现超时：Raft会不断重试，并且接口是幂等的；ZooKeeper的follower会断开与leader之间的连接，重新加入该集群。
5. 总结
Raft 算法分成了2部分：领导选举，日志复制。
领导选举基于一个随机的时间来保证不会冲突（如果冲突的话）。
而日志复制则类似于 2PC。
