分布式系统 15：把客户端命令接到容错 KV
客户端发出 Add(x,5)。集群已经提交并应用，x 从 0 变成 5，但返回值在传输途中丢失。客户端重试时，另一位 leader 收到了相同请求。Raft 可以把两次提交都正确复制，却不会自动识别它们代表同一个业务操作。如果状态机再次相加，日志完全一致，业务结果仍然错误。
第 14 篇 已经建立读屏障与配置边界。本篇把客户端身份、状态机、快照和回复接在同一份 Raft 核心上，并使用独立顺序规范检查客户端历史。判断对象从“日志是否一致”推进到“成功返回的读写能否解释为合法的顺序执行”。课程结构参考 MIT 6.5840 Spring 2026 的 Raft→RSM→KV→快照路径；当年课程接口使用版本化 Put/Get，本篇的 ClientID、Sequence 和 Add 是原创教学选择，不是该课程作业答案。Stanford CS244B 的论文研讨与独立项目要求提供了研究和评估形态。MIT 2026 Lab 4、MIT 2026 Lab 2、Stanford 2024 项目说明
一个逻辑操作，可以有多次尝试
逻辑请求携带 (ClientID, Sequence, Kind, Key, Value)。客户端重试时，这五项保持不变；每次传输另分配 AttemptID，记录发送给哪个节点。ClientID 预先分配且不复用，一个客户端同时最多有一个未完成逻辑操作，Sequence 随新操作递增。客户端若重启后遗失原请求身份，服务端无法仅凭“看起来相同的参数”保证把它合并成旧请求。
flowchart TB
OP["逻辑操作 A/1：Add x 5"] --> A1["Attempt 1 → leader 1"]
OP --> A2["Attempt 2 → leader 2"]
A1 --> LOG["日志可有多个位置保存 A/1"]
A2 --> LOG
LOG --> APPLY["状态机按 A/1 去重"]
APPLY --> ONE["一次业务修改，保存首次结果"]超时只说明客户端没有得到确定结果。它不能区分请求尚未提交、已提交未应用、已应用未返回，以及回复在传输中丢失。实验将这些尝试记录在传输轨迹中；逻辑历史从首次调用开始，到客户端真正收到确定回复才结束。WrongLeader 或丢失的回复不会被记成一次成功写，也不会被误记成“写确定没有发生”。Raft 扩展论文，§8、etcd v3.6 API guarantees，Operation completed
这仍不是无限期的 exactly-once 服务承诺。永久分区下请求可能永远无法完成；客户端身份丢失、复用或去重记录被删除，也会改变保证。本篇仅在固定身份、保留全部去重结果、非拜占庭节点的有限模型内讨论业务效果不重复。
结果必须与修改一起进入状态机
应用状态包含 KV、Applied 和 Seen。Seen 的键是逻辑请求身份，值保存完整请求载荷及首次结果。首次执行命令时修改 KV 并记录结果；再次应用同身份同载荷时，返回旧结果，仅推进 Applied。同身份却不同载荷，返回确定性的 identity-conflict，不修改 KV，也不覆盖原缓存。
Put 将键设为指定整数，Add 返回相加后的值。值域明确为有符号 64 位整数：Add 超出范围时返回 overflow，保留原值，并缓存这个拒绝结果。不能让 Go 的整数回绕偶然成为未声明的业务语义。Get 不进入写日志，通过读屏障获取状态。
假设 A/1 的 Add 首次返回值应为 5，但回复丢失；B/1 随后 Put(x,50)；A/1 再次进入日志。此时返回当前 x=50 也不正确，重试应得到它自己的首次结果 5。只保存“已经处理过”这个布尔标记不够，只保存每个客户端最新一条结果也可能误答迟到的旧 Sequence。
sequenceDiagram
participant A as 客户端 A
participant S as 复制状态机
participant B as 客户端 B
A->>S: A/1 Add(x,5)
Note over S: x=5；Seen[A/1]=结果5
S--xA: 回复5丢失
B->>S: B/1 Put(x,50)
S-->>B: 结果50
A->>S: 重试A/1 Add(x,5)
Note over S: 命中完整身份与载荷，不再修改x
S-->>A: 原结果5，当前x仍为50去重必须成为确定性状态机的一部分。仅在 leader 的请求处理器中保存 Seen，切主后就会失效。不同副本也不能分别依据各自墙钟删除会话，否则同一命令会在某些副本重新执行、另一些副本跳过。本篇不做会话 GC，空间随已处理请求数量增长。若以后加入确认水位、过期和注册，应把规则变成确定性的复制输入，并拒绝已经过期的旧身份。作者博士论文，客户端会话与线性化语义
在 Raft 已提交前缀不丢失、各副本按同一顺序确定性应用的前提下，可以对已应用前缀归纳：空前缀没有任何写效果；首次遇到某个写 ID 时，状态机完成修改或确定性拒绝，并保存结果；之后相同 ID 的日志不会再次修改 KV。合法快照与重放同时保留 Seen、KV 和 Applied，因此重建后仍维持这条不变量。它证明的是声明模型内的至多一次写效果。返回前的提交和应用约束、新鲜读屏障及应用等待，还要共同满足客户端的真实时间顺序，才可能得到完整线性一致性结论；本篇有限历史 checker 不替代这部分全实现证明。
提交、应用与回复是三个事件
服务端收到写请求后，先登记等待者，再把编码后的命令交给 Raft。日志提交只是允许状态机执行的前提；应用完成得到结果，才能生成成功回复。网络调度器决定回复是否被客户端收到。即使是单线程教学驱动，也要明确这个顺序，避免单节点或快速应用路径在等待者登记前已经交付结果。
flowchart TB
REQ["请求到达：先登记等待者"] --> PROPOSE["Propose：追加日志"]
PROPOSE --> SAVE["保存完整持久状态映像"]
SAVE --> COMMIT["多数确认后提交"]
COMMIT --> APPLY["连续应用：KV + Seen + Applied"]
APPLY --> RESULT["生成对应请求的结果"]
RESULT --> NET{"回复被送达？"}
NET -->|"否"| PENDING["客户端逻辑操作仍 pending"]
NET -->|"是"| DONE["记录客户端返回事件"]等待者不能只按日志索引关联。旧 leader 在索引 i 追加 A，尚未提交就被隔离；新 leader 可以在同一索引提交 B。旧节点追赶后应用 B，若按 i 唤醒 A 的等待者，就会把 B 的结果误答给 A。本篇匹配完整请求载荷与身份，配置和 no-op 不产生业务写回复。
实验保留旧等待者以直接检验这个风险：A 的未提交 Add 被 B 的 Put50 替换，A 不应收到 50；随后把原 Add 路由到新 leader，它可以作为尚未生效的逻辑请求执行并返回 55。错误对照只按 index 关联，独立历史检查器会拒绝由此产生的结果。
回复本身也可能重复。A/1 已结束、A/2 已调用但未完成时，再送达 A/1 的旧回复，不应修改 KV，不应结束 A/2，也不应清除 A/2 的客户端活动记录。驱动复制一条实际产生的旧回复来检查这条边界，不能仅凭“重复回复被忽略”就假定身份关联正确。
快照同时保存 KV 与去重结果
快照格式带版本号、KV、完整 Seen 和 Applied。只有应用状态准确覆盖到 k，才能调用核心的 SnapshotAt(k,data)，由核心填写对应 term 和配置。恢复时先验证应用快照的 Applied 等于快照边界，再按连续顺序重放到 durableCommit。尚未提交的后缀不能提前执行。
flowchart TB
IMAGE["快照：version + KV + Seen + Applied=k"] --> RESTORE["验证并恢复边界k"]
LOG["Raft后缀 k+1 … durableCommit"] --> REPLAY["连续重放已提交条目"]
RESTORE --> REPLAY
REPLAY --> SERVICE["恢复后可处理读写"]
BAD["错误快照只保留KV，遗漏Seen"] --> RETRY["旧Add被当新请求再执行"]只保留 KV，会让回复丢失的 Add 在恢复后再次相加；只保留 Applied，却没有相应状态，则会跳过本该重建的数据。作者勘误明确指出，lastApplied 的持久性应与状态机一致。等待请求、RPC 上下文和读轮次属于易失协调状态，不随快照恢复。作者 Updates and Errata
本篇恢复实验复用累计 State 与 Snapshot 接口，在内存中保存映像、销毁 Node 和应用状态，再重新构造。它验证映像内容与重放边界，不是新的真实进程、文件系统或断电测试。真实文件保存顺序和进程切点证据仍由第 13 篇承担。
读必须穿过协议和应用两层屏障
Get 延续第 14 篇的只读路径。leader 需要先有本任期提交，再为本次尝试产生独立探测轮次，收集有效多数并获得 ReadReady。应用层还须等 Applied 至少到 ReadIndex，再读取 KV 返回。逻辑请求身份与协议轮次不能混用：写重试保留原身份，新读探测使用新轮次。
flowchart TB
GET["逻辑Get的本次尝试"] --> ROUND["本任期提交 + 新读轮次"]
ROUND --> ACK["有效多数确认"]
ACK --> READY["ReadReady：ReadIndex=r"]
READY --> CHECK{"Applied ≥ r？"}
CHECK -->|"否"| WAIT["实际尝试回复：不得成功"]
WAIT --> CHECK
CHECK -->|"是"| VALUE["读取当前KV并回复"]屏障测试不能先执行所有日志，再调用回复函数，然后声称应用等待有效。实验先让新 leader 提交前缀但保持应用落后，真正调用 respond，确认没有回复；随后推进应用，再次调用才获得值。去掉 Applied 检查的错误版本会返回旧值，历史检查器应拒绝。
分区场景中，旧 leader 的本地 x=9，新多数派已完成 Put(x,27)，之后客户端才向旧主发起 Get。旧主的读探测因协议链路分区被丢弃，不能成功；重试路由到新主后返回 27。直接读取旧主内存的错误对照返回 9，与真实时间先后冲突。修复分区并同步日志后，旧副本也应用到 27。
网络模型有明确边界：Raft 消息进入显式队列，协议链路按分区规则丢弃；客户端发送、回复丢弃与重复由调度器单独控制。这里没有真实 socket，也没有给所有客户端 RPC 建立通用网络层。有限调度不能代替覆盖任意网络历史的证明。
独立历史检查器如何处理未知结果
检查器只读取客户端逻辑调用与返回，不使用日志顺序、commit、Applied 或 Seen 决定答案。独立顺序规范维护一个 KV 映射，定义 Put、Add、Get 和 overflow。最多八个逻辑操作，枚举符合真实时间约束的顺序，比较已知返回；超限和非法历史明确返回 unsupported 或输入错误。
与第 6 篇 的完整历史检查器不同，本篇允许 pending。它枚举哪些 pending 操作纳入见证，在历史末尾为纳入者补规范允许的响应，省略其余 pending，再寻找合法顺序。所有已返回的操作必须保留。身份冲突属于另一组直接状态机边界测试，当前正常历史 checker 不把这种拒绝伪装成成功 Put。
flowchart TB
H["输入：已完成操作 + pending调用"] --> SELECT["枚举pending纳入子集"]
SELECT --> EDGE["建真实时间前驱：返回早于调用"]
EDGE --> DFS["枚举拓扑顺序并执行独立KV规范"]
DFS --> MATCH{"所有已知结果匹配？"}
MATCH -->|"是"| WITNESS["接受并输出见证"]
MATCH -->|"所有选择都否"| REJECT["拒绝"]若 pending Put1 已调用，随后另一客户端 Get 返回 1，检查器必须允许把那次未回复写纳入见证。直接删除所有 pending，会把这个合法历史误报为错误。若后续 Get 返回 0，也可以省略该 pending 写，或将它放到读之后，不能强制每次没有回复的写都已生效。
相反，如果 Get=1 已完成，之后才调用 pending Put1，就不能用这次未来写解释过去的值。被纳入见证的 pending 也必须排在其调用前已经完成的操作之后。这是 2021 年对原始线性一致性定义勘误的关键点：顺序约束来自扩展历史的 complete(H′)，不应只给原先就 completed 的目标操作建立前驱。Sela、Herlihy、Petrank，Linearizability: A Typo，v2，§4、§7
检查器自测包含 pending 可观察写、pending 可省略、未来写不能解释过去读、已完成 Put 后陈旧读，以及重复事件、重复身份、同客户端重叠操作和规模上限。故意删除 pending 的错误版本会误拒前一个合法例子；故意漏掉 completed→pending 前驱的版本会接受未来写反例。两种错误方向相反，不能用一个永远接受或永远拒绝的检查器通过它们。
实验怎样避免验证假象
最初的重复执行对照只有未回复的 Add、随后完成的 Put50，以及 Add 重试返回 55。检查器判断它仍可线性化：Add 的调用区间与 Put 重叠，可以把逻辑 Add 放到 Put 之后。这个判断是正确的，错误在实验预期。
修正后的轨迹在 Put50 之前加入另一客户端真实完成的 Get=5。这个读要求 Add 已产生可观察效果，不能再把唯一一次逻辑 Add 放到 Put 之后解释 55。正常版本重试返回原结果 5、最终值 50；去掉去重的版本返回 55，检查器拒绝。首次失败与修正都保留在验证附件中，未削弱规范来迁就实现。
| 轨迹 | 正常观察 | 明确错误对照 |
|---|---|---|
| 丢回复、切主、另写、重试 | 重试返回首次结果5，最终值50 | 删除去重得到55，历史拒绝 |
| 快照与重建 | 重试仍为5 | 恢复遗漏Seen得到10，历史拒绝 |
| 同索引命令替换 | 原等待者不被误答，重试后55 | 只按index回复50，历史拒绝 |
| ReadReady但应用落后 | 响应被阻塞，追上后9 | 跳过应用屏障返回旧值，历史拒绝 |
| 分区旧主读 | 无新多数不能成功；新主返回27 | 直接读旧内存9，历史拒绝 |
源码位于 examples/distributed-systems/kv15/。它直接导入累计 raft 包，没有修改核心或复制另一套 Raft；状态机与 checker 分别实现业务运算，避免用被测实现充当顺序规范。
1 | |
2026-09-20，固定目录 race 二进制的完整场景运行退出 0，正常轨迹和明确错误对照均得到预期 verdict，静态分析也通过。可查看 命令、失败记录与实际输出 和 原始资料及论断核验。它验证有限教学轨迹，不是完整协议形式证明，也不是 etcd 产品端到端观察。
etcd v3.6.0 的 Put API 没有通用 ClientID/Sequence 字段，客户端重试拦截器也区分可重复与不可重复操作。不能从“底层使用 Raft”推导它替任意业务提供无限期去重；实际重试语义还取决于具体 API、客户端策略和应用身份设计。etcd v3.6.0 RPC 定义、固定版本重试拦截器
两道练习
练习一：为什么 Put 不足以证明去重？ 同一个 Put(x,5) 执行两次，最后读到 5，是否证明它只执行了一次？
不能。相同赋值掩盖了重复效果。Add 和返回值能让重复执行可观察，但历史仍需建立足够顺序约束：如果未回复 Add 与其他操作重叠，有时仍可重新排序解释结果。因此还应检查首次效果被另一操作观察的时点，以及缓存结果是否稳定。
练习二：快照已经保存 KV，为什么还要 Seen？ 回复丢失的 Add 已使 x=5，快照保存了 x=5，日志也已压缩。恢复后收到原身份的重试，若 Seen 不在快照中，会发生什么？
服务端只能把它当作未见过的请求，再次相加到 10。即使所有副本都做同样的错误转换，日志一致性仍不能修复业务语义。KV、Seen 与 Applied 共同描述已经执行的前缀，必须一起恢复。
下一篇将继续讨论协议验证，把确定性故障注入与历史检查连接到有限状态搜索，寻找故意遗漏持久化或投票约束后的最小反例。
