MIT 6.824 - Lab 3 (1): Students' Guide to Raft（续）

Posted on 2022-05-30 Word count in article: 4k Reading time ≈ 7 mins.

Students’ Guide to Raft 是 MIT 6.824: Distributed Systems 之前的助教写给学生看的实验生存指南。在 MIT 6.824 - Lab 2 (1): Students’ Guide to Raft 中介绍了关于 Lab 2 的部分，本文将继续介绍关于 Lab 3 的部分。

在 Lab 3 中，我们需要实现一个基于 Raft 的 Key-Value 数据库，本文描述了某些对实现可能有帮助的细节。

提交客户端操作

实现客户端请求时可能会先直接发一个请求给客户端所认为的主节点，然后对应的服务端等待 Raft 应用日志，接着服务端执行客户端的请求逻辑，最后再把结果返回给客户端。这种方式适合单客户端的系统，不过不适合多客户端并发的系统。在多客户端请求下，每个客户端请求都有可能修改系统状态，即使各 Raft 节点的日志保持一致，由于各客户端请求间可能相互交替执行，服务端本地状态可能和 Raft 节点的最新日志不一致，除非使用全局的锁隔离各客户端请求，不过系统会退化为串行程序。

文中建议将服务端当做状态机处理，每个客户端的请求本质上都是将状态机从一个状态转变为另一个状态。服务端中有一个专门的线程来处理客户端请求，该线程每次获取一个客户端请求，然后将其提交给 Raft，之后收到 Raft 应用日志的通知后，按顺序将客户端命令应用到服务端的本地状态机中，这里虽然看起来也是串行处理客户端请求，不过由于 Raft.Start() 方法会立即返回，当有大量请求时，Raft 在实现时会批量发送日志。这个线程是整个服务端中唯一能修改本地状态机的地方，所以服务端的 RPC 就简化为了向任务队列中提交任务，并且当 applyCh 接收到可以执行的日志时，将日志所对应的命令应用到本地状态机中，然后响应客户端。

不过，这也带来了一个问题：什么时候知道某个客户端请求执行完成了？这在一切正常的情况下非常简单，因为我们是按序将客户端请求提交给 Raft，所以最后从 applyCh 中出来的日志的顺序就是提交客户端请求的顺序。不过，当前客户端所通信的服务端有可能在中途不再是主节点，所以客户端所发送的日志有可能被丢弃，此时客户端需要能够知道发生了异常，然后尝试换一个服务端。

一个简单的方法是记录提交客户端请求时 Raft 返回的日志索引，然后从 applyCh 收到对应索引的日志时，判断该条日志是否对应最初的客户端请求（可以向 ApplyMsg.Command 添加额外的信息来标识是否是当初的请求）。如果不是同一条请求，则说明发生了异常。

识别重复请求

因为客户端异常重试的机制存在，所以服务端需要能识别出重复的客户端请求：例如某个客户端发送 APPEND 请求，当前服务端成功执行但是客户端没有收到响应，客户端会选择一个新的服务端发送请求，新的服务端需要确保 APPEND 请求不会被执行两次。因此，每个客户端请求需要一个唯一的标识，使得服务端能够识别已经执行的请求。另外，由于客户端会选择不同的服务端发送请求，各服务端需要对已执行的客户端请求达成共识。

有很多方法来为客户端请求生成唯一的标识符。一种简单并且相对有效的方法是先给每个客户端分配一个唯一的标识符，然后给每一个请求附带一个递增的序列号。如果某个客户端重新发送请求，则会复用之前的请求序列号。各服务端需要维护每个客户端最新的请求序列号，如果服务端发现客户端的请求序列号已处理，则直接忽略该请求。

难以定位的边界条件

如果按照上述的方式实现，有可能会遇到两个难以定位的问题。

重复出现的日志索引

Raft.Start() 会返回所添加的日志的索引，不过在实际实现时可能会认为这个索引不会重复返回，或者遇到重复的索引时会认为前一个相同索引的日志所对应的请求已经执行失败。不过实际上这两种看法都不正确，即使没有个任何一个服务端发生异常。

假设有 S1 到 S5 五个节点，一开始 S1 是主节点，并且没有日志，然后系统发生以下交互：

S1 收到两个客户端请求 C1 和 C2
S1 分别返回日志索引1和2给 C1 和 C2
S1 发送包含了 C1 和 C2 的 AppendEntries 请求给其他从节点，其中 S2 收到请求，其余节点均未收到
S3 成为候选节点
S1 和 S2 不会投票给 S3，但是 S4 和 S5 会，所以 S3 成为新的主节点
S3 收到新的客户端请求 C3
S3 调用 Start() 方法并返回日志索引1给 C3
S3 发送包含 C3 的 AppendEntries 请求给 S1，S1 丢弃 C1 和 C2 的日志后添加 C3
S3 在给其他从节点发送 AppendEntries 请求前发生异常
S1 成为候选节点，由于它的日志最新，所以再次成为主节点
S1 收到新的客户端请求 C4
S1 调用 Start() 方法并返回日志索引2给 C4（在之前的步骤中，日志索引2也返回给了 C2）
S1 在给其他从节点发送 AppendEntries 请求前发生异常，此时 S2 成为候选节点
S1 和 S3 不会投票给 S2，但是 S4 和 S5 会，所以 S2 成为新的主节点
S2 收到新的客户端请求 C5
S2 调用 Start() 方法并返回日志索引3给 C5
S2 成功将 AppendEntries 请求发送给其他所有从节点，在后续的心跳中，leaderCommit = 3

最终 S2 的日志为 [C1, C2, C5]，此时所有节点在索引位置2处的日志为 C2，这就为开头的两个观点提供了反例：Start() 方法可能返回重复的日志索引，以及遇到重复的索引时不代表前一个相同索引的日志所对应的请求已经执行失败。

四方死锁

课程的另一个助教 Steven Allen 发现在实现 Lab 3 时很容易遇到一个四方死锁问题。

不管具体的 Raft 代码如何实现，一般来说都会有一个类似于 Raft.Start() 的方法来使得应用程序添加日志，以及很有可能有一个单独的线程将位于 [lastApplied + 1, commitIndex] 范围内的日志通过 apply() 方法发送给应用程序（Students’ Guide to Raft 这篇文章写于2016年，在最新的课程中 Raft 通过 applyCh 来发送日志）。这两个方法很可能都需要持有锁 a。而在应用程序中，很可能会在某个 RPC 中调用 Raft.Start() 方法，然后同样可能有个线程会等待 Raft 的日志应用通知，当这个线程收到通知后，就可以响应客户端。由于这两个方法需要通信（例如，RPC 方法需要知道什么时候客户端请求执行完成），所以很可能也都需要持有锁 b。

上述的方法用 Go 描述如下：

func (a *App) RPC(args interface{}, reply interface{}) {
    // ...
    a.mutex.Lock()
    i := a.raft.Start(args)
    // update some data structure so that apply knows to poke us later
    a.mutex.Unlock()
    // wait for apply to poke us
    return
}

func (r *Raft) Start(cmd interface{}) int {
    r.mutex.Lock()
    // do things to start agreement on this new command
    // store index in the log where cmd was placed
    r.mutex.Unlock()
    return index
}

func (a *App) apply(index int, cmd interface{}) {
    a.mutex.Lock()
    switch cmd := cmd.(type) {
    case GetArgs:
        // do the get
	// see who was listening for this index
	// poke them all with the result of the operation
    // ...
    }
    a.mutex.Unlock()
}

func (r *Raft) AppendEntries(...) {
    // ...
    r.mutex.Lock()
    // ...
    for r.lastApplied < r.commitIndex {
      r.lastApplied++
      r.app.apply(r.lastApplied, r.log[r.lastApplied])
    }
    // ...
    r.mutex.Unlock()
}

假设此时系统处于以下状态：

App.RPC 获取锁 a.mutex 然后调用 Raft.Start
Raft.Start 正在等待锁 r.mutex
Raft.AppendEntries 持有锁 r.mutex，然后调用 App.apply

此时就发生了死锁，因为：

Raft.AppendEntries 在 App.apply 返回前无法释放锁 r.mutex
App.apply 在获取锁 a.mutex 前无法返回
a.mutex 在 App.RPC 返回前无法被释放
App.RPC 在 Raft.Start 返回前无法返回
Raft.Start 在获取锁 r.mutex 前无法返回
Raft.Start 需要等待 Raft.AppendEntries 释放锁 r.mutex

有几种方法来避免死锁。其中最简单的就是在 App.RPC 中，调用 a.raft.Start 之后再尝试获取锁。不过这可能会带来个问题，在 a.raft.Start(args) 和 a.mutex.Lock() 执行之间可能触发 app.Apply，造成错失日志通知。所以另一种方法是从 Raft.AppendEntries 中分离出 r.app.apply，由一个单独的线程来调用 r.app.apply，这就保证了服务端不会错过日志的通知，同时又避免了死锁。

参考

Students’ Guide to Raft