学习 Ratis(一):Raft 算法

Raft 一致性算法,使用了复制状态机,确保集群中的每个节点对相同序列的状态事务达成一致。

Raft 复制状态机通过复制日志实现。每个服务包含了日志,每个日志包含了相同的有序的命令,状态机处理日志中的命令计算状态。所以,保持复制日志的一致性就可以保证状态机的一致性。

Raft

Raft 集群包含多个服务,服务处于以下其中一种状态:

  • Leader 处理客户端交互和日志同步,任何时刻集群中最多有一个 Leader;
  • Follower 完全被动,不主动发起任何 RPC 调用;
  • Candidate Follower 用于选举新的 Leader。

Raft Server State

在 Raft,时间被分隔为不同的任期(Term),任期序号是不断增加且不会重复使用的整数。任期内包含了选举和普通操作。如果选举未能产生新的 Leader 则进入下一任期。

Raft Term

Raft 将一致性问题拆解为以下三个问题:

  • Leader 选举
  • 日志复制
  • 安全性

Leader 选举

Leader 通过维护与其它 Follower 的心跳,建立自己的权利。

Follower 在等待 Leader 心跳选举超时(随机选举超时 Randomized Election Timemout,在 150-300 ms 之间)之后,Follower 增加其当前任期并成为 Candidate。

Candidate 向集群中的所有服务发送 RequestVote RPC 进行选举,结果分为以下三种情况:

  • Candidate 获得了集群中大多数服务的投票,成为 Leader;
  • Candidate 发现任期比自己更大的 Leader,退为 Follower;
  • Candidate 在选举超时之后增加其当前任期进行下一轮选举。

对于相同任期,每个 Leader 以先到先服务的原则最多只能为一个 Candidate 投票。

如果 Leader 的日志比 Candidate 日志更完整,即 Leader 的当前任期大于 Candidate 当前任期或者任期相同 Leader 的当前索引大于 Candidate 当前索引,则 Leader 拒绝为 Candidate 投票。

($lastTerm_l$ > $lastTerm_c$) || (($lastTerm_l$ == $lastTerm_c$) && ($lastIndex_l$ > $lastIndex_c$))

Leader 发现任期比自己更大的 Leader,退为 Follower。

日志复制

Leader 接受客户端的请求,请求中包含复制状态机待执行的命令,Leader 将命令写入日志并通过 AppendEntries RPC 同步日志条目(Log Entry)给 Follower。当集群中大部分服务完成了日志条目的同步,即达到了已提交(committed)条件,Leader 应该日志条目到状态机,并返回执行结果给客户端。

安全性

TODO

参考