MIT 6.824/6.5840 分布式系统 Lab 3 - Raft 论文阅读

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

Raft 是一种经典的分布式共识算法（Consensus algorithm）。

#复制状态机

复制状态机是一组服务器上，计算相同的状态，而且可以容忍部分机器下线的状态机。 复制状态机是解决分布式系统中一系列容错问题的基础，例如选主。 通常通过 Replicated Log 实现，共识算法的职责就是维护 Replicated Log 的一致性。

实际应用中，对于共识算法的要求：

  • 正确性：在非拜占庭条件下，永远不会返回错误的结果；
  • 可用性：只要多数机器正常工作，就可以正常工作；
  • 一致性不依赖于操作的时序，最坏情况下，只会导致可用性的问题；
  • 快速：一般情况下，一旦大多数机器响应了一轮 RPC，命令即可完成；

#Paxos 的问题

  • 难以理解

#Raft 共识算法

Raft 将共识问题分解成三个子问题：（1）选主、（2）日志复制、（3）安全性；

#Raft 基本定义

Raft 规定的节点状态：

  • Follower：被动响应 C 和 L 的请求；
  • Leader：处理所有客户端的请求；
  • Candidate：选主过程中使用；

Raft 将时间划分为任意长度的任期（Term），任期用连续整数编号，起到逻辑时钟的功能。每个任期开始时先进行选举，选举出来的 Leader 会在这个任期内进行服务；否则继续下一个任期和选举。

#选主

Raft 利用心跳机制触发选主，Leader 会周期性地给所有 Follower 发送心跳宣布权威性。如果 Follower 一段时间没有收到心跳，则会开始尝试发起选主。

选主过程中，Follower 会将 Term++，然后请求所有 Peer 投票（自己当然会给自己投票）。结果可能有几种：

  1. 收到的选票数量超过半数：自己成为 Leader；
  2. 收到了 Term 更大的 Candidate 或者 Leader 的任意 RPC：自己被强制降级为 Follower，发起的选举失效；
  3. 收到的选票数量不到半数：没有 Leader，继续下一轮选举；

节点投票时遵循简单的规则：

  • 每个 Term 最多投给一个人
  • 先来后到

Raft 采用随机选举超时，保证多个节点不会在同一时间启动选举。

#日志复制

当一个 Leader 被选出来之后，就开始负责这些事情：

  • 给每个 Follower 发送日志：同步 Log；
  • 决定什么时候可以提交 Log：当 Leader 确信一条日志已经被同步到多数机器上，则认为可以提交它，Raft 机制保证了剩余机器最终将会提交相同的日志，即所谓最终一致性。

Raft 的Log Matching Property：

  • 两个不同 Log 中的条目，如果 term 和 index 相同，则存储的 command 相同；
  • 两个不同 Log 中的条目，如果 term 和 index 相同，则之前的所有 log 相同；

在 Raft 执行过程中，由于机器崩溃重启，Follower 可能会缺失部分 Log，可能会有多的未提交的 Log，也可能两者兼有； 这种情况下，Leader 会覆盖Follower 上不一致的 Log：首先两者会找到第一条不一致的 Log，然后 Leader 发送后续的 Log 给 Follower。 nextIndex就是 Leader 用于记录每一个 Follower 同步位置的变量，初始值为 Leader 的 nextLogIndex。然后会根据AppendEntries的结果减小nextIndex。

一个可能的优化点是：Follower 反馈更加精确的冲突日志数量。作者怀疑这种策略在现实情况中的必要性。

Raft 的Leader Append-Only Property：Raft Leader 从来不需要更改或者删除自己的日志；

#安全性

上面描述的 Raft 不足以保证命令的顺序性，原因是多个日志冲突的 Follower 可能会交替成为 Leader，导致已经提交的 Log 被覆盖。为此还需要增加一个新的限制：

  • Leader Completeness Property：Candidate 必须拥有前一个 Term 中所有已经提交的Log，才能被选为 Leader；

#选主限制

Raft 利用选主过程保证Leader Completeness Property，RequestVote RPC 请求中会包含 Candidate 的 Log 信息，如果 Log 不够新，则在投篇时会被多数节点拒绝。

Raft 定义的“新（Up-to-date）”：

  • 如果最后一条 Log 的 Term 不同，Term 大的更新
  • 否则，Log 长的更新

#提交前一个 Term 的 Log

只是 Log 被同步到多数节点，仍然不足以能够提交这个 Log。

Raft 要求：只有当前 Term 的 Log 才通过多数原则确认提交，非当前 Term 的不会这样。

#安全证明

略

#Follower 和 Candidate 崩溃重启

略

#时序和可用性

略

#集群成员变更 & 联合共识

集群变更配置的场景是很常见的。

TODO

#日志压缩