分布式
, ,
Source
Edit
History

6.824思路整理

Catalogue
  1. 1. 要点
  2. 2. Raft的状态机安全性保证方法思路
  3. 3. 实现细节
    1. 3.1. 并行go func
    2. 3.2. 关于Figure 8
    3. 3.3. 其他细节
  4. 4. KVRaft的线性语义实现思路
    1. 4.1. 线性一致性
  5. 5. KVRaft快照安装的线性一致性保证

要点

  1. Figure 8
  2. 线性一致性
  3. 快照安装时的线性一致性保证

Raft的状态机安全性保证方法思路

  1. AppendEntries RPC的一致性检测方法（检查待复制日志的前一条日志是否匹配）保证了日志从leader到follower单向流动。保证了单向流动，我们就需要只需要考虑谁能成为leader的问题。

  2. leader完整性性质：选举时，只有包含所有已提交日志的candidate才能够被选为leader。实现分为两步：

    1. 实现方式是比较candidate与投票者的日志，candidate的日志必须新于投票者的日志才能够获得投票。然而，仍然存在问题：如果一个leader提交了之前任期的日志，那么这条日志可能会被新的leader截断，即这个新leader并没有满足leader完整性（论文图8的情况）
    2. 为了解决这个问题，raft不允许leader直接提交之前任期的日志，只允许通过提交当前任期的日志来间接提交之前任期的日志。被提交日志的任期更大，保证了旧任期的日志不会被覆盖。
    3. 基于上述两个性质，论文对leader完整性性质使用了反证法进行了精确证明。

  3. 通过上述性质，所有server的日志都能够保持一致，并且所有被提交的日志都能够被保留（raft的一致性解决的核心问题）。由此，所有的状态机都能够以日志被提交的顺序apply所有被提交的日志，保证了状态机的安全性。

参与者和候选者宕机：

  • leader重试指令是安全的。AppendEntries RPC和RequestVote RPC的流程已经被设计为可以重复执行的。

选举超时设定：

  • broadcastTime << electionTime << MTBF

  • 前一个小于号保证了选举至少需要等待一次RPC调用的往返时间之后才会超时，否则选举将无法进行

  • 后一个小于号保证了选举不会等到节点故障之后才超时，否则已经投票的follower将会发生故障，这一票将失去意义

实现细节

并行go func

在循环使用go func并行发送RPC时需要注意代码的正确性：

  • go func之后不需要Wait，如果Wait，则外层函数需要等待每个go func都收到响应才能返回

  • 外层函数在调用go func之后需要释放锁，这样go func才能获取锁

  • go func中用到的可变变量（循环变量，rf的成员）需要拷贝一份，或者通过传参的方式传给go func

  • go func在调用RPC前尽量不要获取锁，而是通过外层函数拷贝/传参获取参数，以保证RPC尽快发送

  • go func在调用RPC之后需要获取锁检查响应值，首先需要检查发送者是否仍为对应任期的leader，然后再执行论文中的响应步骤

关于Figure 8

Figure 8的实现需要两部分：

  • leader更新commitIndex的时候，必须保证新commit的日志是自己任期的
  • 新上任的leader需要提交一条no-op，以快速提交之前任期的log

然而，6.824的测试用例当中规定了上层的每条指令必须出现在log的指定index处，因此no-op无法实现，只能实现第一条。实现第一条之后，Figure 8的正确性也能够保证，而日志提交的速度需要依赖于其他优化手段。

其他细节

Student Guide中还提到了许多细节，需要逐一完善：

  • 需要判断响应的任期。响应的任期应该与请求的任期和leader的当前任期均匹配，否则响应就是过期的。
  • 机器有可能在持久化快照和持久化日志之间崩溃，导致日志是过期的（包含已经快照的条目）。为此，需要在读取持久化信息的时候截断过期的日志。
  • 对leader响应AppendEntriesRPC时nextIndex的更新步长进行优化。

6.824的实现中似乎并不会出现第二个问题。持久化状态和快照的代码如下：

1
2
3
4
5
6
7
8
// Save both Raft state and K/V snapshot as a single atomic action,
// to help avoid them getting out of sync.
func (ps *Persister) SaveStateAndSnapshot(state []byte, snapshot []byte) {
	ps.mu.Lock()
	defer ps.mu.Unlock()
	ps.raftstate = clone(state)
	ps.snapshot = clone(snapshot)
}

在测试环境中，使一个节点崩溃的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
func (cfg *config) crash1(i int) {
    cfg.disconnect(i)
	cfg.net.DeleteServer(i) // disable client connections to the server.
    ...
    // a fresh persister, in case old instance
	// continues to update the Persister.
	// but copy old persister's content so that we always
	// pass Make() the last persisted state.
	if cfg.saved[i] != nil {
		cfg.saved[i] = cfg.saved[i].Copy()
	}
    ...
}

测试环境在崩溃一个节点时，只是将这个节点从模拟网络中断开连接并删除。至于持久化的数据，则会拷贝一份，供重启节点时使用。可见，节点崩溃时并没有进程层面的崩溃，故SaveStateAndSnapshot函数中由互斥锁保护的两行代码一定会被原子地执行，从而raftstate和snapshot的状态在当前测试环境中一定是匹配的。

KVRaft的线性语义实现思路

线性一致性

  • 线性一致性的解释：线性一致性和 Raft | PingCAP

  • 示例图：

    图例 2

  • 线性一致性的定义为，Client在对同一个数据执行操作（读或写）时满足下列三个条件：

    • 瞬间完成（或者原子性）
    • 发生在 Inv 和 Resp 两个事件之间
    • 反映出“最新”的值

  • 理解：

    • 第一和第二条指的是，虽然从Inv到Resp有一段时间，但是操作是在这段时间内的某一个“时间点”完成的。不过线性一致性并没有规定这个点位于线段的哪个位置，可以是Inv和Resp之间的任意位置
    • 第三点指的是，如果在某个时间点，数据的值发生了更新，那么这个时间点之后的读操作必须都能读到这个值。例如图中的Client B和Client C，Client C读的时间点肯定位于Client B写的时间点之后，因此C肯定读到2。反之，Client D读和Client B写的先后顺序未知，因此D可能读到1或2。

  • 线性一致性的实现思路：

    • 读请求的处理。需要使用LogRead、ReadIndex、LeaseRead三种方法之一来处理读请求。

      • LogRead：读请求需要提交日志。有磁盘开销和网络开销
      • ReadIndex：读请求需要：(1) 获得大多数节点的心跳回复；(2) 状态机至少需要apply发起读请求时的commitIndex。没有磁盘开销，有网络开销。
      • LeaseRead：(1) Leader选取一个比ElectionTimeout小的租期，在租期内不会发生选举，跳过了ReadIndex的(1)。(2) WaitFree：Leader在上任后提交一条no-op，保证leader的状态机是最新的，从而可以跳过ReadIndex的(2)，无需等待commitIndex和lastApplied。

    • 重复请求的处理。Clerk发送的请求有可能是重复的：其他server已经提交了该请求，但是Clerk没有收到响应。这就导致server的状态机可能重复apply一个请求。为此，需要给每个客户端加上UUID，给客户端的每个请求加上序列号，在server中维护每个客户端最新apply的请求序列号。如果从raft接收到重复序列号则不apply，直接给客户端响应ok。

KVRaft快照安装的线性一致性保证

  • 快照的步骤分为两种情况：

    • server自己进行快照：server发送index和snapshot给raft，请求快照；raft如果检测到快照是更新的，就截断日志。
    • 然而，有的follower可能会由于掉队而缺少快照，这时他需要从leader接收快照：raft接收leader的InstallSnapshot RPC；raft向server上传快照，要求server安装。

  • 在第二种情况中会出现问题：raft在接收到快照之后，在状态机安装快照之前，可能会apply其他更新的log。这时状态机安装快照相当于状态的回退，导致一部分已经被apply的状态丢失，造成missing element。

  • 解决方法是改变安装快照的流程：server向raft发送CondInstallSnapshot询问是否可以安装快照，raft检查到快照在commitIndex之内则拒绝安装。