写点什么

Raft 算法浅析

  • 2022 年 7 月 11 日
  • 本文字数:2726 字

    阅读完需:约 9 分钟

作者: HHHHHHULK 原文来源:https://tidb.net/blog/1c1f7fe3

Raft 浅析

一. Raft 简介

概括成一句话:保证 log 完全相同地复制到多台服务器上。


只要每台服务器的日志相同,那么在不同服务器上的状态机以相同顺序从日志中执行相同命令,所得到的结果必然相同。


Raft 共识算法的工作就是管理这些日志。

1. 角色状态

  • Leader:处理所有客户端请求、日志复制。同一时刻最多只能有一个可行的 Leader;

  • Follower:完全被动的(不发送 RPC,只响应收到的 RPC)——大多数服务器在大多数情况下处于此状态;

  • Candidate:用来选举新的 Leader,处于 Leader 和 Follower 之间的暂时状态;


系统正常运行时,只有一个 Leader,其余都是 Followers。


状态转换化图:


2. 任期

时间被划分成一个个的任期 (Term),每个任期都由一个数字来表示任期号,任期号单调递增并且永远不会重复。



一个正常的任期至少有一个 Leader,通常分为两部分:


  • 任期开始时的选举过程;

  • 正常运行的部分;


有些任期可能没有选出 Leader(如图 Term 3),这时候会立即进入下一个任期,再次尝试选出一个 Leader。


每个节点维护一个 currentTerm 变量,表示系统中当前任期。currentTerm 必须持久化存储,以便在服务器宕机重启时将其恢复。


任期能够帮助 Raft 识别过期的信息。例如:如果 currentTerm = 2 的节点与 currentTerm = 3 的节点通信,我们可以知道第一个节点上的信息是过时的。只会使用最新任期的信息。

3. RPC

Raft 中服务器之间所有类型的通信通过两个 RPC 调用:


  • RequestVote:用于选举;

  • AppendEntries:用于复制 log 和发送心跳;

二. Leader 选举

1. 启动

  • 节点启动时,都是 Follower 状态;

  • Follower 被动地接受 Leader 或 Candidate 的 RPC;

  • 如果 Leader 想要保持权威,必须向集群中的其它节点发送心跳包(空的 AppendEntries RPC);

  • 等待选举超时 (electionTimeout,一般在 100~500ms) 后,Follower 没有收到任何 RPC:

  • Follower 认为集群中没有 Leader

  • 开始新的一轮选举

2. 选举

当一个节点开始竞选:


  • 增加自己的 currentTerm

  • 转为 Candidate 状态,其目标是获取超过半数节点的选票,让自己成为 Leader

  • 先给自己投一票

  • 并行地向集群中其它节点发送 RequestVote RPC 索要选票,如果没有收到指定节点的响应,它会反复尝试,直到发生以下三种情况之一:

  • 获得超过半数的选票:成为 Leader,并向其它节点发送 AppendEntries 心跳;

  • 收到来自 Leader 的 RPC:转为 Follower;

  • 其它两种情况都没发生,没人能够获胜 (electionTimeout 已过):增加 currentTerm,开始新一轮选举;

3. 图例说明

3.1. 节点均正常

  1. 开始启动,节点都是 Follower 状态:



  1. s4 先到达选举超时时间成为 candidate,当前任期 currentTerm 从 1 变为为 2,并向其他节点发起 RequestVote RPC 请求



  1. 其他节点收到 s4 的投票请求后,投出赞同票(其他节点在收到 S4 的投票前都没有出现选举超时的情况)



  1. s4 成为 Leader,并开始向其他节点发送心跳包:


3.2. Leader 节点故障

再来看下 Leader 节点故障了,剩下四个节点参与选举。


  1. s4 故障,其他 follower 节点选举超时:



  1. s2 达到选举超时时间,变为 candidate,任期从 2 变为 3,给自己投一票,并发起投票请求:



  1. s1,s3,s5 的 currentTerm 都是 2,收到 s2 的请求后发现 s3 的 currentTerm 是 3,于是把自己的 currentTerm 升为 3,并投出赞成票:



  1. s2 成为 leader 发心跳包,其他 follower 节点回包:


三. 日志复制

1. 日志结构


每个节点存储自己的日志副本 (log[]),每条日志记录包含:


  • 索引:该记录在日志中的位置

  • 任期号:该记录首次被创建时的任期号

  • 命令


日志必须持久化存储。一个节点必须先将记录安全写到磁盘,才能向系统中其他节点返回响应。


如果一条日志记录被存储在超过半数的节点上,我们认为该记录已提交(committed)——这是 Raft 非常重要的特性!如果一条记录已提交,意味着状态机可以安全地执行该记录。

2. 运行流程

  • 客户端向 Leader 发送命令,希望该命令被所有状态机执行;

  • Leader 先将该命令追加到自己的日志中;

  • Leader 并行地向其它节点发送 AppendEntries RPC,等待响应;

  • 收到超过半数节点的响应,则认为新的日志记录是被提交的:

  • Leader 将命令传给自己的状态机,然后向客户端返回响应

  • 此外,一旦 Leader 知道一条记录被提交了,将在后续的 AppendEntries RPC 中通知已经提交记录的 Followers

  • Follower 将已提交的命令传给自己的状态机

  • 如果 Follower 宕机 / 超时:Leader 将反复尝试发送 RPC;

  • 性能优化:Leader 不必等待每个 Follower 做出响应,只需要超过半数的成功响应(确保日志记录已经存储在超过半数的节点上),一个很慢的节点不会使系统变慢,因为 Leader 不必等他;

3. 日志一致性

Raft 尝试在集群中保持日志较高的一致性。


Raft 日志的 index 和 term 唯一标示一条日志记录


  • 如果两个节点的日志在相同的索引位置上的任期号相同,则认为他们具有一样的命令;从头到这个索引位置之间的日志完全相同;

  • 如果给定的记录已提交,那么所有前面的记录也已提交;

4. 图解

4.1. 选举结束,s2 成为 leader,当前 currentTerm 为 2,follow 节点的 matchIndex=0,nextIndex=1,commitIndex=0,lastApplied=0:



4.2. leader 节点 s2 接收到客户端请求,将命令封装成日志,然后在该节点添加日志记录,并将复制日志请求发给其他 follower:



4.3. 所有 follower 接收日志完成复制工作,这些节点的 matchIndex 变为 1,nextIndex 变为 2:



4.4. leader 确认提交,并告知所有 follower:



此时 leader 的 commitIndex 为 1:



而 follower 的 commitIndex 为 0:



4.5. 所有 follower 收到 leader 提交的请求,修改 commitIndex,表示已处于已提交状态:



此时可以看到 follower 的 commitIndex 变成 1:


5. 一致性检查

Raft 通过 AppendEntries RPC 来检测。


  • 对于每个AppendEntries RPC 包含新日志记录之前那条记录的索引 (prevLogIndex) 和任期 (prevLogTerm);

  • Follower 检查自己的 index 和 term 是否与 prevLogIndexprevLogTerm 匹配,匹配则接收该记录;否则拒绝;


四. Leader 当选条件

leader 的竞选资格:拥有最新的已提交的 log entry 的 Follower 才有资格成为 Leader。





五. Raft 与 Multi-Paxos

MySQL 8.0 MGR 实现数据一致性用的是 Paxos 算法,两者其实都是基于 leader 的一致性算法。


Raft 与 Multi-Paxos 中的概念:



Raft 与 Multi-Paxos 的不同点:


六. 总结

Raft 还有许多功能点比如它的日志压缩、客户端交互等值得深入学习,这边就不一一去研究了。接下来还是把更多的时间放在 TiDB 原理的研究和使用测试上。


最好的 Raft 参考文档:


Raft 论文:https://raft.github.io/raft.pdf


Raft 中文版:https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#51-raft- 基础


条分缕析 Raft 算法:https://segmentfault.com/a/1190000039264427


发布于: 刚刚阅读数: 3
用户头像

TiDB 社区官网:https://tidb.net/ 2021.12.15 加入

TiDB 社区干货传送门是由 TiDB 社区中布道师组委会自发组织的 TiDB 社区优质内容对外宣布的栏目,旨在加深 TiDBer 之间的交流和学习。一起构建有爱、互助、共创共建的 TiDB 社区 https://tidb.net/

评论

发布
暂无评论
Raft 算法浅析_TiDB 社区干货传送门_InfoQ写作社区