1.1 Raft详解
Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。
1.2 Raft角色
跟随者（Follower）：普通群众，默默接收和来自领导者的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。
候选人（Candidate）：候选人将向其他节点请求投票 RPC 消息，通知其他节点来投票，如果赢得了大多数投票选票，就晋升当领导者。
领导者（Leader）：霸道总裁，一切以我为准。处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们不要”发起新的选举，不用找新领导来替代我。
1.3 Raft机制
这幅图展现了跟随者、候选者和领导者之间的状态转换关系，下面主要介绍他们的转换流程。
跟随者
如果他能持续从领导者或者候选者接收到有效的RPCs，那么他的状态就不会变。一直保持跟随者身份。但如果没有持续接受，也就是在一段时间没收到有效的RPCs，那就选举超时，他会变成候选者。
候选者
要变为候选者，也就意味着他要开启一轮新的选举。那么跟随者会增加自己的任期号，转为候选者。
成为候选者后，自己会并行发送一个为自己投票的RPCs请求 给其他服务器。
成为候选者的整个过程也会保持当前状态，知道满足下面三个条件
- 他赢得选举，转变为领导制
- 其他节点赢了，他转为跟随者
- 一段时间没有任何人获胜。说明选票被瓜分，重复执行。
1.3.1 初始状态
如下图所示，有三个节点(Node) a、b、c，任期都是0
Raft 算法实现了随机超时时间的特性，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。比如 A 节点等待超时的时间间隔 150 ms，B 节点 200 ms，C 节点 300 ms。那么 a 先超时，最先因为没有等到领导者的心跳信息，发生超时。如下图所示，三个节点的超时计时器开始运行。
1.3.2选举领导人
当 A 节点的超时时间到了后，A 节点成为候选者，并增加自己的任期编号，Term 值从 0 更新为 1，并给自己投了一票。
- Node A：Term = 1, Vote Count = 1。
- Node B：Term = 0。
- Node C：Term = 0。
我们来看下候选者如何成为领导者的。
- 第一步：节点 A 成为候选者后，向其他节点发送请求投票 RPC 信息，请它们选举自己为领导者。
- 第二步：节点 B 和 节点 C 接收到节点 A 发送的请求投票信息后，在编号为 1 的这届任期内，还没有进行过投票，就把选票投给节点 A，并增加自己的任期编号。
- 第三步：节点 A 收到 3 次投票，得到了大多数节点的投票，从候选者成为本届任期内的新的领导者。
- 第四步：节点 A 作为领导者，固定的时间间隔给 节点 B 和节点 C 发送心跳信息，告诉节点 B 和 C，我是领导者，组织其他跟随者发起新的选举。
- 第五步：节点 B 和节点 C 发送响应信息给节点 A，告诉节点 A 我是正常的。
领导人任期问题：
- 自动增加：跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会增加自己的任期号，如上图所示，节点 A 任期为 0，推举自己为候选人时，任期编号增加为 1。
- 更新为较大值：当节点发现自己的任期编号比其他节点小时，会更新到较大的编号值。比如节点 A 的任期为 1，请求投票，投票消息中包含了节点 A 的任期编号，且编号为 1，节点 B 收到消息后，会将自己的任期编号更新为 1。
- 恢复为跟随者：如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。这种场景出现在分区错误恢复后，任期为 3 的领导者受到任期编号为 4 的心跳消息，那么前者将立即恢复成跟随者状态。
- 拒绝消息：如果一个节点接收到较小的任期编号值的请求，那么它会直接拒绝这个请求，比如任期编号为 6 的节点 A，收到任期编号为 5 的节点 B 的请求投票 RPC 消息，那么节点 A 会拒绝这个消息。
- 一个任期内，领导者一直都会是领导者，直到自身出现问题（如宕机），或者网络问题（延迟），其他节点发起一轮新的选举。
- 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，投完了就没了。
防止多个节点同时发起投票：
为了防止多个节点同时发起投票，会给每个节点分配一个随机的选举超时时间。这个时间内，节点不能成为候选者，只能等到超时。比如上述例子，节点 A 先超时，先成为了候选者。这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。
触发新的一轮选举：
如果领导者节点出现故障，则会触发新的一轮选举。如下图所示，领导者节点 B 发生故障，节点 A 和 节点 B 就会重新选举 Leader。
- 第一步 ：节点 A 发生故障，节点 B 和节点 C 没有收到领导者节点 A 的心跳信息，等待超时。
- 第二步：节点 C 先发生超时，节点 C 成为候选人。
- 第三步：节点 C 向节点 A 和 节点 B 发起请求投票信息。
- 第四步：节点 C 响应投票，将票投给了 C，而节点 A 因为发生故障了，无法响应 C 的投票请求。
- 第五步：节点 C 收到两票（大多数票数），成为领导者。
- 第六步：节点 C 向节点 A 和 B 发送心跳信息，节点 B 响应心跳信息，节点 A 不响应心跳信息。
1.3.3 日志复制
- 客户端向领导者发请求
- 领导者将新的日志附加到自己日志并发送心跳给跟随者
- 跟随着确认收到并反馈
- 领导者收到大多数反馈就更新确认状态机，通知所有跟随着更新自己的状态机
安全性（Raft可能会出现的各类问题）
- 宕机，节点重新选取
- 网络分区，双领导问题
- leader收到客户端请求，还未复制到跟随着节点发生故障，启动选取
- leader收到客户端请求，成功复制到跟随着但尚未收到确认发生故障，拥有最新数据的节点成为领导者
- 两份日志任期号不同，按日期号大的进行更新
- 如果投票时跟随者的日志比候选人的新，那么拒绝该人的投票请求
1.3.4 Raft动画
上述动画：https://thesecretlivesofdata.com/raft/#home
Raft动画：https://raft.github.io/
1.3.5 Raft优化问题
1 Raft算法的选主改进
随着系统节点数的增加，各节点随机固定的超时时间的重复几率也会增加，加上众多节点间的网络延时，必然会导致整个系统的分区化，即同时在各分区产生一个伪Leader（得到部分投票但不满足当选Leader所必须投票数量）分票，从而导致这一轮选主失败，进入下一轮重新选举。
思路：添加信誉机制进行选主，其中信誉机制可与机器学习中的决策树进行结合，通过决策树分类出信誉度较高的节点，
2 根据Raft算法的机制设计出拜占庭容错协议
思考有恶意节点进入该如何进行处理！
评论