Raft 算法

Raft 一致性算法

有限状态机图

基本概念

  • Leader 领袖
  • Candidate 候选人
  • Follower 群众

领袖选举

  • 一开始所有节点都是群众
  • 会有一个计时器，计时结束后仍没有收到心跳，会将自己设为候选人，任期 +1, 先投自己一票，然后请求别人为自己投票; 如果收到了心跳，会重置计时器
  • 其他的群众接收到请求投票的消息，若他还没有投票，且请求方的任期比自己本地的要大，会把自己的一票发给第一个投票请求；否则要明确不投票给他
  • 当一个候选人获取到半数以上的投票，则他将成为 Leader，并通过心跳通告给其他节点，候选人接收到任期更高的心跳转为群众，群众接收到心跳就会重置选举定时器

日志复制

  • 每一个客户端的请求都将被解析成一条需要复制状态机执行的指令

  • Leader 现将指令存到日志文件中去

  • 并行的向其他节点发起 AppendEntries RPC，要求其复制；如果未返回成功则要一直重试

  • Leader 确保安全复制后，将日志应用（提交）到状态机中，向客户端返回执行结果

    • 一旦领导人创建的条目已经被复制到半数以上的节点上了，那么这个条目就称为可被提交的，为安全

  • Leader 通过心跳，将已提交的索引值返回给其他节点，其他节点根据这个信息，把日志应用到本地状态机

Raft 通过以下机制保证不同节点日志的一致性：

  1. 不同日志的两个条目有相同的索引号和任期号，则存储的命令一致
  2. 不同日志有相同的索引和任期号，则他们之前的所有条目都是完全一样的；因为每次 Follower 追加新日志条目的时候，都会检查前一条（前一条的信息也包含在 RPC 请求当中）

安全性 QA

可用性与时序

异常情况

参考资料

https://cloud.tencent.com/developer/article/1525566

Raft Scope Raft 算法模拟