1 · raft#

https://raft.github.io

https://raft.github.io/raft.pdf

https://thesecretlivesofdata.com/raft

问题拆分：

1. leader election
2. log replication
3. safety
4. and membership changes

reducing the number of states to consider 减少需要考虑的状态，减少不确定性

1.1 · 总览

选举出领导：领导全权管理复制日志，从客户端获取，复制到其他服务器；

服务器状态：leader, follower, candidate 正常情况下，只有一个leader，其余都是follower follower不会进行请求，只会响应来自leader/follower的请求 leader处理所有来自客户端的请求 candidate状态，是用来选举leader的

时间分为任意长度的terms， terms以连续整数编号， 每一个term以一次选举开始，一个或多个的candidata会尝试成为leader， 如果一个candidate成功选举为leader，那么其负责这一term的剩余时间；

在某些情况下，选举会导致票数分裂，以无领导产生为结果， 一个新的选举会产生，也就是新的term；

状态变化：

flowchart
  Follower --1.timeout, start election--> Candidata
  Candidata --2.receive majority votes--> Leader

  Leader --3.discover higher term server --> Follower
  Candidata --4.discover current Leader or new term--> Follower

term 用作逻辑锁：持续递增，同步高term值的日志，Candidata/Leader回退Follower状态，低term值的Leader表示数据过期

RPC调用：RequestVote, Append-Entries(复制日志、心跳), 还有一个快照的RPC

1.2 · 1.选举领导#

心跳机制触发领导选举

跟随者只要收到领导或候选者的RPC，那么就一直是跟随者状态

领导会阶段性的发送心跳给跟随者， 如果一个跟随者在一段时间内没有收到领导发送的心跳，那么就会开启选举， 跟随者会增加自身的term，进入候选者状态， 候选者进行投票的RPC调用其他集群内的节点， 在这些情况下停止选举：1）获胜选举 2）其他节点是领导 3）没有获胜者，重新开始 1.候选者会在当前term赢得集群内大多数节点的投票而选举获胜； 2.等待投票期间，如果高term的领导节点发送心跳给候选者节点，候选者回退成跟随者状态，如果低于，则忽略 3.多个候选者且票数一致，则开启新一轮选举!!!!这种情况可能一直发生 解决3问题，跟随者进入候选者的超时时间是随机的，大概率保证只有一个候选者；候选者从新开始选举的超时时间也是随机的；

1.3 · 2.日志复制#

客户端向领导节点请求，领导节点记录请求执行的命令并追加到日志， 然后发送追加日志项RPC给集群内其他节点进行复制， 当领导节点认为安全的时候（比如大部份节点成功复制日志后）， 领导节点会应用这个命令，并响应命令结果到客户端， 如果其他节点失败了，领导节点会一直重试RPC请求集群内其他节点

日志项含命令，含term值（用于判断一致性），index位置

领导节点请求的追加项的RPC中，会含有index，当跟随者知道有log项被应用了，其也会应用在本地

日志属性：不同日志相同索引的值相同；如果索引N的值相同，那么N以前的值都相同

跟随者节点会在收到追加项（包含之前的索引）的RPC的时，检查索引；如果不符合，会拒绝

领导节点出问题的时候，可能导致日志不一致； 当日志不一致的时候，领导节点会强制跟随者和其一致：找到日志相同的最晚的哪个索引处，删除跟随者后续的日志项，复制领导者节点的； 领导节点维护了跟随者节点的nextIDX表，发送RPC后，如果跟随者节点拒绝了，则减1，在发送RPC，循环往复，直到匹配，此时日志就一致了； 跟随节点可以在拒绝的时候，返回冲突的第一个索引；

领导节点不会重写其日志；

正常来说，一个日志项会在一次RPC调用时间内完成，慢节点不会影响性能。

1.4 · 3.安全性#

一个跟随者节点可能变得不可用，此时领导节点已经提交了多个日志项； 然后这个跟随者节点可能选举成功，变成领导节点，就会覆写上诉的日志项；

Leader Completeness Property 领导者完整性属性 限制：如果一个节点成为了领导节点，必须包含其term前所有term的日志提交；

1.4.1 · 1. 选举限制#

从新领导节点当选的那一刻起，所有来自前几任任期的已提交条目都会出现在新领导节点。 保证：日志项的数据流只会从领导节点到跟随者节点。

在投票阶段，如果一个候选者节点没有先前提交的所有日志项，那会被阻止成为赢得选举。 请求投票RPC会包含候选者节点的日志信息，投票者会根据其本身日志，和候选者日志进行对比后，再进行投票。

1.4.2 · 2. 来自前一个term的提交日志#

领导节点当前term的日志被提交，需要集群内大多数节点已经保存， 如果在日志提交之前，领导节点崩溃了，未来的领导会尝试完成这个日志的复制；

即使大多数节点被保存，也可能被未来领导节点覆写：Figure 8 只有当前领导者的日志可以被提交。

1.4.3 · 3. 安全性保证 5.4.3#

假设：term N 的提交，没有被 term N+n 的领导节点保存： 矛盾1： 矛盾2： 验证了假设的不可行

结论： 只要有一个节点应用了一个日志，那么其他节点一定一致；

1.5 · 4. 跟随节点、候选者节点崩了#

重试AE或RV

Raft 的 RPC 是幂等的

1.6 · 5. 时间和可用性#

安全性与时间无关；但可用性无可避免的依赖时间；

时间在Raft的领导选举中很重要：

广播时间(RPC调用) << 选举timeout << 节点失败时间

1.7 · 6. 集群成员变更#

1.8 · 7. 日志压缩#

1.9 · 实现

0. 节点之间通过RPC调用，节点本身是一个RPC服务

1. 每个节点一启动就是跟随者节点状态：跟随者、候选者、领导

2. 候选时间超时，那么跟随者修改自身状态为候选者，并向集群内其他节点请求RPC投票

3. 候选者处理RPC响应

4. 超时时间到了，判断投票是否占多数，如果不是重新发起投票，是则成为领导节点

5. 用户请求领导节点

6. 领导节点将未提交的数据追加到自己日志，并RPC请求集群内其他节点

7. 跟随者节点处理RPC请求

8. 领导节点收到跟随者节点确认后，执行命令并更新commitIndex并返回用户？