本系列目录
MIT 6.824 学习笔记
线性一致性：Lab 3 的正确性标准
---
什么是线性一致性#
线性一致性（Linearizability）是分布式系统里最强的一致性保证。
直觉理解：从外部观察者的角度看，所有操作好像是在一台单机上按某个顺序执行的，而且每个操作都是瞬间完成的。
更精确的定义：对于任意一组并发操作，存在一个合法的顺序执行序列，使得：
- 这个序列和每个操作的实际执行时间兼容（如果操作 A 在操作 B 开始之前就完成了，那么在序列里 A 在 B 之前）
- 这个序列在单机上执行的结果和实际观察到的结果一致
具体例子#
例子 1：满足线性一致性
时间轴:
客户端 1: Put(x, 1) ─────完成─────
客户端 2: Get(x) ─返回 1─客户端 2 的 Get 在客户端 1 的 Put 完成之后才开始，所以必须返回 1。这满足线性一致性。
例子 2：违反线性一致性
时间轴:
客户端 1: Put(x, 1) ─────完成─────
客户端 2: Get(x) ─返回 0─ ← 违反！例子 3：并发操作，两种结果都合法
时间轴:
客户端 1: Put(x, 1) ─────────────────────
客户端 2: Put(x, 2) ─────────────────────
客户端 3: Get(x) ─返回 1 或 2─两个 Put 是并发的，Get 返回 1 或 2 都合法（取决于哪个 Put 先被执行）。
Porcupine：线性一致性检测工具#
Lab 3 的测试用 Porcupine 来验证线性一致性。Porcupine 会记录所有操作的开始时间、结束时间和结果，然后检查是否存在一个合法的线性化顺序。
测试失败时的输出：
linearizability check timed out, assuming not linearizable或者：
history is not linearizable这说明你的实现违反了线性一致性。
常见的线性一致性违反#
违反 1：读到了过时的数据
Put(x, 1) 完成
Get(x) 返回 "" （应该返回 1）原因：Get 操作没有通过 Raft 提交，直接读了本地状态，而本地状态可能是过时的。
修复：Get 操作也要通过 Raft 提交（提交一个 Get 操作，等它被 apply 后再读取）。
违反 2：重复执行导致状态不一致
Append(x, "a") 执行了两次（因为重试）
Get(x) 返回 "aa" （应该返回 "a"）原因：没有去重，重试的请求被执行了两次。
修复：用 ClientID + SeqNum 去重。
为什么 Get 也要通过 Raft#
你可能会想：Get 只是读操作，不修改状态，为什么要通过 Raft？
原因：如果直接读本地状态，可能读到过时的数据。
场景：
- 服务器 A 是旧 Leader，服务器 B 是新 Leader
- 客户端向 B 发了
Put(x, 1)，B 提交了 - 客户端向 A 发了
Get(x)，A 还不知道自己不是 Leader 了 - A 直接读本地状态，返回 ""（旧值）
通过 Raft 提交 Get 操作，可以确保读到的是最新的值（因为 Get 操作被提交时，之前所有的 Put 都已经被 apply 了）。
如何读懂 Porcupine 的错误输出#
错误信息的两种形式#
形式 1：超时
linearizability check timed out, assuming not linearizablePorcupine 在规定时间内找不到合法的线性化顺序，认为不满足线性一致性。通常说明违反很严重（操作历史太复杂）。
形式 2：明确不满足
history is not linearizablePorcupine 确认不存在合法的线性化顺序。
两种情况都说明你的实现有 bug，需要调试。
Porcupine 生成的可视化文件#
测试失败时，Porcupine 会在当前目录生成一个 HTML 文件（通常叫 linearizability.html）。用浏览器打开，你会看到一个操作时间线图：
操作时间线示意图：
时间 →
客户端1: [Put(x,1)────────────────]
客户端2: [Put(x,2)────────────]
客户端3: [Get(x)→"1"] ← 红色（违反！）
客户端4: [Get(x)→"2"] ← 绿色（合法）
说明：
- 每条横线代表一个操作，从调用时刻延伸到返回时刻
- 绿色 = 在某个合法顺序中可以解释
- 红色 = 无论怎么排序都无法解释如何找到违反的操作：
- 找到红色的操作
- 看它的返回值
- 对比它调用时刻之前已经完成的操作，判断它应该返回什么值
三种常见违反模式及调试方法#
模式 1：读到了过时的值（Stale Read）
时间线：
Put(x, "1") 完成
Get(x) 返回 "" ← 应该返回 "1"诊断：Get 没有通过 Raft，直接读了本地状态。
定位：
// 检查 Get handler 是否调用了 rf.Start()
func (kv *KVServer) Get(args *GetArgs, reply *GetReply) {
// 错误：直接读
reply.Value = kv.data[args.Key] // ← 这里有问题
// 正确：通过 Raft
index, _, isLeader := kv.rf.Start(Op{Type: "Get", Key: args.Key, ...})
// 等待 apply...
}模式 2：重复执行（Duplicate Execution）
时间线：
Append(x, "a") 调用 → 超时 → 客户端重试
Append(x, "a") 再次执行
Get(x) 返回 "aa" ← 应该返回 "a"诊断：去重逻辑有 bug，重试的请求被执行了两次。
定位：
// 检查 applyLoop 里的去重逻辑
if op.SeqNum <= kv.lastSeq[op.ClientID] {
// 重复请求，直接返回缓存结果
// 注意：这里要用 <= 而不是 <
}常见错误：
- 用
<而不是<=（边界条件错误） - 去重表没有在快照里保存（重启后丢失去重状态）
- 客户端重试时递增了 SeqNum（应该保持相同的 SeqNum）
模式 3：旧 Leader 回复了客户端（Stale Leader Response）
时间线：
客户端向旧 Leader 发 Put(x, "1")
新 Leader 处理了 Put(x, "2")
旧 Leader 回复了 Put(x, "1") 成功（但实际上没有提交）
Get(x) 返回 "2" ← 客户端以为 "1" 已提交，但实际上没有诊断：RPC handler 在等待 channel 时没有验证自己还是 Leader，或者等到了错误 index 的结果。
定位：
// 检查 applyLoop 通知时是否验证了 op 内容
case msg.CommandIndex:
op := msg.Command.(Op)
// 必须验证这条日志确实是我们提交的那条
if op.ClientID != waitingOp.ClientID || op.SeqNum != waitingOp.SeqNum {
// 这个 index 被其他 op 占了（Leader 换届后重新提交）
ch <- Result{Err: ErrWrongLeader}
return
}调试线性一致性失败的完整流程#
1. 运行失败的测试，保存输出
go test -race -v -run TestLinearizability3A 2>&1 | tee test_output.txt
2. 找到 HTML 文件
ls *.html # 或者 ls /tmp/*.html
3. 用浏览器打开，找到红色操作
4. 记录红色操作的：
- 类型（Get/Put/Append）
- 参数（key, value）
- 返回值
- 调用时刻和返回时刻
5. 对照上面三种模式，判断是哪种违反
6. 加日志，在 applyLoop 里打印每次 apply 的操作
log.Printf("[%d] apply op=%v key=%s val=%s clientID=%d seqNum=%d",
kv.me, op.Type, op.Key, op.Value, op.ClientID, op.SeqNum)
7. 重新运行，对照日志和时间线图