Lab4A 核心是要实现「线性化」语义

Client

Client 必须在 RPC 超时，或者 Server 返回自己不是 Leader 的情况下，自动切换到下一个 Server：

  1. 向「Leader」发送 RPC
  2. 检查响应结果
    • 如果 Err = ErrWrongLeader，修改 ck.LeaderID = ck.LeaderID + 1，重新从步骤 1 开始
    • 如果 Err = ErrNotFinish，睡眠「最大操作」时间，切换到下一个 Server，重新从步骤 1 开始
    • 如果 Err = OK，更新 Epoch，返回结果
  3. 如果 RPC 超时，那么切换到下一个 Server，重新从步骤 1 开始

上面的处理方式比较简单，更「生产可用」的处理方式（例如 Redis、Kafka 的分布式实现）：

  1. 集群中每一个节点都有整个集群的元数据
  2. Client 缓存集群元数据
  3. Client 在请求时，依据缓存的元数据来请求，而不是每次轮询

在本次 Lab 中，「元数据」比较简单，指的是 Leader 的「网络位置」

Server

为了保证「线性一致性」，Server 需要有辨别某一个请求是否是 重复请求 的能力

如何辨别？这一点事实上已经在 Lab2 中实现过：即维护 Client 与 CommandEpoch 的映射关系

Client 每次请求时，需要带上自己的 ID，以及本次请求的 Epoch

Epoch 是一个单调递增的值，会随着 Client 请求逐渐递增

当 Client 发现某次请求失败，会使用 相同的 Epoch 重新尝试执行该 Command

Server 可以利用 Client 与 CommandEpoch 的映射关系 来辨别某个请求是否重复：如果某个请求的 Epoch 与之前缓存的 Epoch 相等，或者更小，说明这个请求是过期的请求

CommandHandler RPC

要实现线性化语义，单个 Server 必须 线性处理客户端的请求，更进一步的，Server 对 Start 方法的调用是「线性化」的

具体逻辑如下：

  1. 如果此次请求不是 get 请求，则 校验此次请求是不是一个重复的请求，如果是，直接返回缓存的执行结果
  2. 向 Raft 集群发送 Start，如果 Start 返回不是 Leader，直接返回结果给客户端
  3. 删除上一次回复的缓存
  4. 等待 Raft 集群完成该 Command 的共识
  5. 返回结果给客户端

Start 发送的命令定义如下：

type Op struct {
	// Your definitions here.
	// Field names must start with capital letters,
	// otherwise RPC will break.
	Type  TypeRequest
	Key   string
	Value string

	ClientID    int64
	ClientEpoch int64
}

applier

Server 使用一个 后台 goroutie，即 applier，将 Raft 提交的日志条目应用到状态机，以及更新 Client 的 ID 与 Epoch 的映射关系 和 响应结果的缓存

为了确保任意时刻，同一个网络分区内的 Server，保存的 Client 的 ID 与 Epoch 的映射关系是一致的，Server 间需要同步 Client 的 ID 与 Epoch 的映射关系，以及 响应结果的缓存，这点可以通过 Raft 的同步机制来实现

具体来说，每一轮循环：

  1. 从 applyCh 获取一条日志
  2. 更新 applyIndex
  3. 判断这个 Command 是不是一个重复的 Command：
    • 如果是，直接忽略，从缓存的 lastReply 获取本次返回结果
    • 否则：
    1. 将日志应用到状态机
    2. 以状态机的返回结果作为本次返回结果
    3. 缓存此次响应结果的缓存（如果不是 Get 请求）
  4. 更新 Client 的 ID 与 Epoch 的映射关系
  5. 判断自己是不是 Leader，如果是 Leader，发送 reply 到 channel

正确性验证

由于 Lab4A 完整测试一次需要耗时仅 5min，并且测试会占用比较多的 CPU 资源，这里没有进行大量的 Lab4A 测试

完整测试 10 次，并且 TestPersistPartitionUnreliableLinearizable4A（Test: unreliable net, restarts, partitions, random keys, many clients (4A) …）测试 100 次，均通过：

image

image

踩的坑

客户端请求超时处理

在 TestOnePartition4A 测试中，遇到了一个错误：

2024/05/26 09:21:31 client-1274618360016164535-1: received response from server-1
    test_test.go:100: Get(1): expected:
        15
        received:
        16
--- FAIL: TestOnePartition4A (2.66s)
FAIL
FAIL	6.5840/kvraft	4.009s
FAIL

经过画图分析，最后 get(1) 的返回值应该为 16，难道是测试用例出问题了吗？

并不是，如果最后一个 get(1) 的返回值为 15 的话，说明客户端应该具有超时处理的能力，也就是说：如果一个 RPC 时间太长，客户端应该尝试将请求发送到另一个 Server

一开始我认为 labrpc 的实现已经包含了超时处理，然而并没有

因此，我们需要手动做 超时控制

no-op 日志

有一个情况：Leader 刚发完 AE 请求，网络就被分区了，即使 Follower 成功 append 到本地，Leader 也无法更新 commitIndex

然后，集群选举出新的 Leader，由于 Term 改变，新的 Leader 无法更新 commitIndex，除非客户端发来一个新的请求，Leader 才能间接提交之前的日志

因此，Leader 刚选举出来，除了发送心跳外，还应该发送一条 no-op 日志，以此间接提交之前的日志

但是，在添加 no-op 日志后，Lab3B 测试全挂了。。遂放弃

没有 no-op 日志，可能存在请求无限等待的情况，只有一个新的请求来了，才能打破这个局面

Client 的 ID 与 Epoch 的映射关系，需要在 applier 更新，而不是在 RPC Handler 更新

这一点主要是在 Follower 这端考虑的

因为一个客户端的请求，最终只会在 Leader 上执行，如果在 RPC Handler 更新映射关系的话，Follower 就无法同步 Leader 本地的「映射关系」，进而无法识别一个 command 是否为重复的 command，这样存在重复 apply 相同 command 的问题

因此，「映射关系」应该在 applier 更新，这样 Follower 就可以同步 Leader 内存中存储的「映射关系」

这里也侧面反映了，applier 在向状态机应用 command 时，也需要检查 command 是否重复（也是在 Follower 这段考虑的）

注意：「映射关系」应该仅在 applier 更新，否则 Leader 的 applier 可能永远无法应用某个 command

applier 也需要判断一条 Command 是否重复

这一点也是在 Follower 这端考虑的

因为一个客户端的请求，最终只会在 Leader 上执行，如果仅仅在 RPC Handler 检查是否重复，Follower 还是会应用重复的日志

Lab3（Raft）本身有 bug

Raft 某些难以复现的 bug 可能在 Lab3 的测试用例中展现不出来，但是在 Lab4A 就原形毕露了

至少我发现了此前实现的 Raft 有以下几个 bug：

  • Apply（提交）乱序
  • RequestAppendEntries RPC 乱序，未能正确处理，导致日志被覆盖

image

为啥在 Lab3 测试不出来这些问题？因为 Lab4 的测试用例考虑到了 网络分区 的情况

在 网络分区 + 不稳定的网络 这两个条件下，一些隐藏的问题就可能会暴露出来