raft选举笔记

请求投票

currentTerm: 服务器最后一次知道的任期号

nextIndex ：对于每一个服务器，需要发送给他的下一个日志条目的索引值（初始化为领导人最后索引值加一）

matchIndex 对于每一个服务器，已经复制给他的日志的最高索引值

commitIndex ： 已知的最大的已经被提交的日志条目的索引值

lastApplied: 最后被应用到状态机的日志条目索引值（初始化为 0，持续递增)

applyIndex是状态机中的应用的日志，应用了才能给你最新的值

接收者实现：

1. 如果term < currentTerm就返回 false （5.1 节）
2. 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false （5.3 节）
3. 如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的 （5.3 节）
4. 附加任何在已有的日志中不存在的条目

5. 如果leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个

   ● (term)候选人的任期号< 当前机器的任期号 不投票

   ● 请求选票的候选人的 Id，候选人的日志至少和自己一样新，那么就投票给他

6. 候选者（任期日志）：

● 在转变成候选人后就立即开始选举过程还有speech

○ 自增当前的任期号（currentTerm）

○ 给自己投票

○ 重置选举超时计时器

○ 发送请求投票的 RPC 给其他所有服务器

● 如果接收到大多数服务器的选票，那么就变成领导人

● 如果接收到来自新的领导人的附加日志（AppendEntries）RPC，则转变成跟随者

● 如果选举过程超时，则再次发起一轮选举

1. 所有服务器：

   ● 如果commitIndex（已提交日志的索引值） > lastApplied（最后被应用到状态机的日志条目索引值-初始化为 0，持续递增），那么就 lastApplied 加一，并把log[lastApplied]应用到状态机中

   ● 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者 (领导者不可能收到比领导还大的任期，候选者收到大的任期)

2. 跟随者

   ● 响应来自候选人和领导者的请求

   ● 如果在超过选举超时时间（一般是心跳时间的10倍）的情况之前都没有收到领导人的心跳，或者是候选人请求投票的，就自己变成候选人

3. 领导人

   ● 一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时

   ● 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端（5.3 节）

   ● 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex，那么：发送从 nextIndex 开始的所有日志条目：--【人话：成为领导者以后，leader会和follower同步日志，不成功，就把当前follower的nextIndex-1，然后重试--leader会维护每个follower的nextIndex数组，类似于出现冲突，leader覆盖follower日志】

   ○ 如果成功：更新相应跟随者的 nextIndex 和 matchIndex

   ○ 如果因为日志不一致而失败，减少 nextIndex 重试

   ● 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令 commitIndex 等于这个 N （5.3 和 5.4 节）【人话： 也就是半数以上的follower的CommitIndex >=N, 且对应的日志记录还是当前term提交的，说明当前leader需要更新commitIndex】

apache ratis 在选举的时候做了两个优化 ： PreVote（预选投票）和优先级选举-

1. 预选投票为保证在网络分区情况下，不会出现经常性的选举。在正式的选举前，先进行一轮PreVote选举，只有通过了PreVote选举，才会增加Term进行正式的选举。
2. 优先级选举为防止出现多个Candidate候选者瓜分选票，设置每个节点的优先级，优先级高的会让优先级低的候选者成为跟随者。

（SOFAJRaft - 优先级选举）并维护优先级最大值，如果优先级高的节点宕机，（上一轮选举超时）进行对最大值衰减，防止选不出领导者。

Jepsen模拟网络分区，进程崩溃、CPU 超载，检测各种分布式系统在故障下是否仍然满足所预期的一致性

快照机制：（需要异步处理）

30分钟内有raft log提交时，才会进行snapshot

应用就算崩溃重启，那么它首先也会读取 snapshot 中的数据10，再去应用（状态机）2条i++的 raft log，最终数据也是12

leader:

1. 如何确认 leader 在处理这次 read 的时候一定是 leader 呢?

readIndex read

1. 将当前自己的 commit index 记录到一个 local 变量 ReadIndex 里面。
2. 向其他节点发起一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在自己仍然是 leader。
3. Leader 等待自己的状态机执行，直到 apply index 超过了 ReadIndex，这样就能够安全的提供 linearizable read 了。
4. Leader 执行 read 请求，将结果返回给 client。

● 走正常的： follow -> leader-> commit index -> 检测所有，超过半数raft log

【用户的请求过来，他请求的应该是最新的Commit的内容，但是Commit应用到stateMachine才能提供最新的内容】

● readIndex : follow -> leader-> commit index -> 检测所有，超过半数heartbeat -> 应用状态机读取值

Lease（租约） Read

● Heartbeat 有一定的开销

●  CPU 时钟误差（tikv 默认使用这个，认为大多数情况都是正确的。sofaraft默认使用的是readindex）

● 续约心跳有效期至（上次心跳时间+ 选举超时时间/ 时钟漂移），减少心跳开销

1. leader 选举成功之后，首先提交一个 no-op 的 entry（日志数据），保证 leader 的 commit index 成为最新的 --【no-op entry 提交之后，才可以对外处理 ReadIndex】