(浅尝辄止的)Raft学习记录

Posted on Edited on In

暑假期间来学习一下 Raft 并实现 MIT 6.824 的几个lab

Raft 论文阅读

raft 使用 term 作为逻辑时钟

term 规则：

  • 每个服务器会存储一个 current term 时钟
  • 低 term 的服务器接收到高 term 服务器信息时更新自己的term
  • leader 或 candidate 接收到更高 term 的信息时退化 为 follower
  • 更低 term 的信息会被直接忽略

term 规则保证了 Leader 永远是集群中更新最快(term最大)的节点

Leadership election

Follower 行为：

  • 进行 election timeout
  • 接收 有效 append entry RPC  (包括heartbeat) 来重置 timeout
  • 当进行投票后，也应该重置 timeout
  • 当 election timeout 结束 转变为 Candidate

Candidate 行为：

  • 给自己投票并 发送 RequestVote RPC 进行 timeout
  • 当得到超过集群规模半数的成员投票时，Candidate 竞选成功，转变为 Leader
  • 当得到别人的 heartbeat （说明已产生 Leader）时，直接退化为 Follower
  • 当 time out 发生 (即发生分票，无法产生 Leader) Leader 会增加自己的 term，开始新一轮选举

Leader 行为：

  • 发送 heartbeat

Log Replication

Leader 使用 AppendEntries RPC 发送 log

当一个 log 被超过半数成员接收时，称为 committed 此时 Leader 可以执行这个 log

当一个 log entry 被 committed 它之前的所有 entry 也自动被committed

对于 log entries 有如下两条性质，可以保证实现上述的  commit rule

  • If two entries in different logs have the same index and term, then they store the same command.
  • If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.

Inconsistency 处理 ：

AppendEntries RPC 会进行consistency check 当 Leader 和 Follower 的 nextIndex 之前的 entry 无法匹配时，会不断递减 nextIndex 直到匹配 （最低为0），随后再将 Leader 的 log entry 复制给 Follower

Leader Append-Only 性质：Leader永远只会增加，而不会修改，删除自己的 log entry

\<img alt="" data-attachment-key="ETMKQDDZ" src="attachments/ETMKQDDZ.png" ztype="zimage">

论文的 Figure8 直观地描述了一个重要的性质（及违反它的后果），即 Leader 只能 直接 commit 自己当前 Term 的 log，而对于之前 Term 并未 commit 的 log，我们应当在当前 Term 的 log 被 commit 后，使用 commit rule 的第二条来自动 commit 它的所有前驱 log。否则会造成已经被commit 的 log 被覆盖（当leader允许 commit 非当前 Term 的 log 时，意味着 Follower 的最后 commit log 可能是非最新 Term， 此时由 log 覆盖的规则，只要有较新 Term 的 log 便可以覆盖它）在这里体现了 Term 机制是如何维护共识，即拥有较高 Term 的 Server （可认为是 Leader）永远拥有对较低 Term 的修改权力。  

Log compaction

Server 上存储的 Log 数量不可能无限增加，为了节约硬盘资源 (同时加快恢复速度)，我们必须有驱逐过时 Log 的机制。在 Raft 中，我们使用 Snapshot 快照。

\<img alt="alt text" data-attachment-key="4MK8TG6D" src="attachments/4MK8TG6D.png" ztype="zimage">

在一个 Snapshot 中，server 只需要存储少量的 metadata ，如 最后一个被包含的 Log 的 Index 及 Term 信息， 即可保证 绝大部分情况下 Raft 算法正常的运作。当创建一个 Snapshot 后，Server 便可以将已被加入 Snapshot 的 Log 安全删除。

但存在一个例外情况，当 Leader 向一个 Follower 发送的 AppendEnteries RPC 包含已经被写入 Snapshot 的 log ，此时 Leader 就只能转而向 Follower 发送 Snapshot。这种情况仅出现在 和 Leader 同步极其落后的 Follower 中，因为绝大部分情况 Leader Snapshot 一个 log 时，这个 log 已经被 Follower 所拥有了。在 发送 Snapshot 的 RPC handler 中，follower 需要根据 Snapshot 和自身 log 的更新情况来决定，若出现了自己未拥有的信息，则直接用 snapshot 代替当前所有信息，否则部分同步 snapshot

对于 snapshot 的进一步思考：snapshot 过程中并不存在 “新” 的信息产生，而只是 server 重新整合自己的信息，因此它并不破坏共识机制，同时数据仍然只从 Leader 单向流向 Follower。因此它虽然和 Raft 的 strong leader 原则不符，但不破坏 Raft的性质。