理解 raft 算法

raft 算法是一种共识算法,其解决的分布式环境中的数据一致性的问题

leader election

在 raft 算法中,每个节点有三种状态:

  • Follower
  • Candidate
  • Leader

所有的节点初始都是 follower ,如果 follower 节点没有收到任何 leader 节点的消息,这些节点将变成 candidate ,candidate 节点开始向其他节点请求投票,节点会返回投票信息,如果一个 candidate 获得所有节点中的多数投票,则他会变成 leader 状态,这个过程称之为 leader election

在 raft 中有两个 timeout 设置控制着 election 的进行。

第一个是 election timeout,意思是 follower 要等待成为 candidate 的时间,这个时间是一个介于 150ms 到 300ms 的值,这个时间结束之后 follower 变成 candidate 开始选举,首先是自己对自己投票,然后向其他节点请求投票,如果接收节点在收到投票请求时还没有参与过投票,那么他会把票投给这个请求投票的 candidate,然后重置自身的 election timeout,一旦一个 candidate 拥有所有节点中的大多数投票,他变成一个 leader。

第二个是 heartbeat timeout,一旦一个 candidate 成为 leader,他开始向其他 follower 发送 append entries,这些消息发送的频率是通过 heartbeat timeout 指定,follower 会响应每条的 append entry,整个 election 会一直进行直到 follower 停止接受 heartbeat 并且变成 candidate 开始下一轮 election。

假设 leader 故障了,follower 不再收到 heartbeats,新一轮 election 开始,整个过程重复上述步骤。

需要节点中的多数节点的投票才能成为 leader 保证了在每轮选举中只有一个 leader 可以胜出,如果一轮选举中有两个节点同时成为 candidate 将会导致 split vote 发生,如果此时两个 candidate 都收到了相同的票数,他们重置 election timeout 重新开启新一轮选举。

log replication

leader 成功选举之后,之后 client 的请求都先经过 leader,每个请求的更改以日志的形势保存在 leader 节点,但这些更改是 uncommitted 状态,为了对这些更改进行提交,leader 首先 replicate 这些更改到 follower,等到 follower 中的大部分提交之后才会 commit 这些更改,commit 之后通知 follower 更改已经 commited,这个系统现在达到了一致的状态,这个过程称之为 log replication

network partitions

raft 算法可以应对 network partitions。

比如由于网络分区导致了 C、D、E 和 A、B 隔离,各自分区中会重新开始选举形各自形成新的 leader

在各自分区之内,各自 leader 会收到不同的 client 发送的请求,由于在 B 分区内,leader 无法获得多数节点的投票,因而 leader B 上发生的更改不会被提交,等网络分区修复之后,A 和 B 的 term 比较小,他们会自动下线,回滚之前的提交,等待新的 leader 发送 hearbeat

参考