# 从 LoopX 出发，补上数据库与分布式系统的推理底座

学习讲义 · 2026-10-01 · 公开审阅版

这份材料面向已经能构建真实系统、希望把工程直觉变成可检验推理的开发者。重点是数据库、分布式系统、函数式编程与 Agent 系统之间的连接。示例均为教学模型；涉及 LoopX 时明确区分已有实现、PR 提案与尚未验证的目标。

配套材料：[练习、讨论与学习路线](./练习与讨论.md)；[可运行实验](./recovery_lab.py)。

## 阅读地图

第一遍按 1—4、9—11、15 的顺序，先得到恢复与权限主线。第二遍读 5—8、12—14，补事务、存储、复制与性能。第三遍完成配套练习，再回到真实代码。

1. [一个动作的三种事实](#1-一个动作的三种事实)
2. [故障模型与时间](#2-故障模型与时间)
3. [状态机、不变量与进展](#3-状态机不变量与进展)
4. [FP 与类型系统负责哪一段](#4-fp-与类型系统负责哪一段)
5. [数据库替应用承担什么](#5-数据库替应用承担什么)
6. [隔离级别与并发历史](#6-隔离级别与并发历史)
7. [锁、CAS 与提交时验证](#7-锁cas-与提交时验证)
8. [持久化、日志与恢复](#8-持久化日志与恢复)
9. [幂等与 exactly-once 的范围](#9-幂等与-exactly-once-的范围)
10. [租约、fencing 与旧执行者](#10-租约fencing-与旧执行者)
11. [跨系统提交、投递与补偿](#11-跨系统提交投递与补偿)
12. [一致性、共识、CAP 与 FLP](#12-一致性共识cap-与-flp)
13. [存储引擎、索引与扩展](#13-存储引擎索引与扩展)
14. [排队、重试与资源控制](#14-排队重试与资源控制)
15. [回到 LoopX 的具体问题](#15-回到-loopx-的具体问题)
16. [与其他领域的交叉](#16-与其他领域的交叉)
17. [怎样建立可信的正确性证据](#17-怎样建立可信的正确性证据)

## 1. 一个动作的三种事实

考虑一个 Agent 调用 provider，把一次工作结果写回。要分别记录三个问题：

1. **世界状态：** provider 是否已经完成了写入？
2. **知识状态：** 调用方是否拿到了足以确认结果的证据？
3. **授权状态：** 当前执行者是否仍然有权发起下一次写入？

例如，provider 已写入，响应丢失，执行者的租约又过期。此时可能同时成立：

```text
外部结果：已提交
本地认知：结果未知
当前权限：禁止新执行
```

单个 `success: boolean` 无法表达它。把三者合并，通常会导致“未收到成功 → 当作失败 → 重新执行”，或“看到历史成功 → 当作当前仍有权限”。

用一条时间线检查：

```text
客户端                     Provider
  | ---- 请求 op-7 --------> |
  |                         | 持久化业务变化
  |                         | 持久化 op-7 的结果
  | <--- 响应在途中丢失 ---- X
  | 超时                    |
```

客户端只看到超时，至少存在三种可能：请求没到；正在执行；已经提交。**超时是观察结果，不是外部事务结论。** 取消请求也不能自动撤回已提交动作。

恢复协议的责任，就是在允许的观察与操作中消除这份不确定性。能按同一 operation id 回查就回查；provider 支持原子幂等时，可以在授权允许下重试同一操作；两者都不支持的高风险效果，需要进入可见的待核对状态。重新生成一个 id 只是把未知结果藏起来。

这里的核心不是“重试技巧”，而是**知识不足时，哪些动作仍然合法**。[AWS 的幂等 API 设计](https://aws.amazon.com/builders-library/making-retries-safe-with-idempotent-APIs/)提供了请求身份、参数绑定与迟到请求的实际案例。

## 2. 故障模型与时间

“能容错”必须补完整：容忍什么、多少次、发生在哪些位置？

| 故障 | 可能留下的状态 | 不能直接推出的结论 |
| --- | --- | --- |
| 进程退出 | 内存丢失，OS 缓存和磁盘可能还在 | 不能据此证明掉电持久性 |
| 整机掉电 | 尚未稳定持久化的数据可能丢失 | 不能把 `write()` 返回当成稳定落盘 |
| 响应丢失 | 远端可能已提交 | 不能当作远端失败 |
| 网络分区 | 两侧可能都活着但互不可见 | 不能当作另一侧已死 |
| 长时间暂停 | 旧 worker 稍后恢复，继续旧指令 | 不能只靠“租约应该过期了”保护资源 |
| 数据腐坏、恶意响应 | 内容本身不可信 | crash-only 协议不自动覆盖 Byzantine 故障 |

教学和日常控制面设计通常先处理 crash/restart、延迟、丢失、重复、乱序，并明确存储与身份信任假设。安全攻击模型要另外建立，不能靠 Raft 或数据库事务顺便解决。

### 时钟有不同用途

Wall clock 表达日历时间，可能因校时跳变；monotonic clock 适合测量本机经过时间，但不同机器的值不能直接比较，重启后的可比性也需具体平台契约。lease 到期时间应由协议明确的时间权威判断，不能随意拿 worker 自报时间代替。

跨进程最可靠的先后依据常常是因果关系：A 发出消息，B 收到后执行，A 的发送先于 B 的接收。Lamport clock 满足 `a → b` 时 `L(a) < L(b)`，反过来不成立；数值较小不自动说明有因果关系。[Lamport, Time, Clocks, and the Ordering of Events](https://lamport.azurewebsites.net/pubs/time-clocks.pdf)

LoopX 的 revision、turn id、lease generation、projection cursor 因而不应混成一个“时间戳”。它们分别回答版本、逻辑操作、授权代次与消费进度等问题。

## 3. 状态机、不变量与进展

状态机可以写成：

$$
S_{t+1}=T(S_t,C_t,F_t)
$$

`S` 是拥有者认可的状态，`C` 是命令，`F` 是显式输入的观察事实。外部副作用的执行结果应作为后续事实进入，而不是假装纯函数已经修改了世界。

**不变量（invariant）是每个可达状态都必须满足的性质。** 例如：同一逻辑操作的配额扣减至多一次；没有合法授权的执行者不能提交新效果；展示层失效不能撤销已提交业务事实。

归纳式证明思路只有两步：初始状态满足 `I(S)`；每个允许的迁移都保证 `I(S) ⇒ I(S')`。实际困难在于，遗漏的并发交错和外部操作不一定在你画的迁移图中。

### 状态合法，不代表历史合法

`Todo { status: "done", receipt: "r1" }` 形状可以合法，但可能来自一个无权完成它的 worker。类型检查验证的是值结构；历史是否经过合法路径，还需要状态前置条件、身份绑定和提交处校验。

把 `Todo done`、`Turn settled`、`Goal accepted` 和 `result delivered` 分开：一次 Turn 可以提交阶段性进展而不完成 Todo；Todo 完成也不意味着最终产物已经送达用户。独立维度用积类型组合；相互排斥且字段相依的情况用和类型表达。

### Safety 与 liveness

- **Safety：** 坏事永不发生，例如不重复扣减、不接受旧 owner 的新写入。
- **Liveness：** 在给定假设下，好事最终发生，例如有权限、有预算、依赖恢复且得到公平调度后，待处理工作最终推进。

无限等待通常能保护一部分 safety，却不能满足 liveness。把所有失败一律重试可以制造活动，也可能破坏 safety。

对于长期任务，进展承诺必须写出条件：provider 会恢复吗？relay 会再次运行吗？用户 gate 会被解除吗？预算是否足够？“永远自动完成”没有这些前提就不是可审计的工程承诺。[TLA+ 课程的状态机、事务提交与 liveness 章节](https://lamport.azurewebsites.net/video/videos.html)

## 4. FP 与类型系统负责哪一段

FP 最有用的落点，是把决策从 IO、时钟、随机数和隐式全局状态中提出来：

```ts
// 教学接口，不是 LoopX 现有 wire schema。
type Readback =
  | { kind: "committed"; operationId: string; receipt: Receipt }
  | { kind: "absent"; witness: AbsenceWitness }
  | { kind: "unknown"; reason: string };

type Decision =
  | { kind: "hold"; reason: string }
  | { kind: "checkpoint"; receipt: Receipt }
  | { kind: "retry_same_operation"; operationId: string };

// 不读取时钟，不做网络请求，不修改共享对象。
declare function decide(
  state: Readonly<PreparedState>,
  observed: Readback,
  policy: Readonly<Policy>
): Decision;
```

`unknown` 分支要求显式处理；`checkpoint` 分支必须携带 receipt。比起 `ok? / retried? / receipt?` 的任意组合，这会缩小误用空间。`readonly` 是编译期约束，通常也不是递归深冻结；边界输入仍需 decoder，别名共享与隐藏 mutation 仍需留意。

```mermaid
flowchart LR
    A[外部输入和历史记录] --> B[Decoder / 合法领域值]
    B --> C[纯决策函数]
    C --> D[带类型的执行意图]
    D --> E[执行器 / 提交时校验]
    E --> F[数据库或外部 Provider]
    F --> G[结果与持久证据]
    G --> C
```

这几个环节分别解决不同问题：

- decoder 检查“这个值是否符合输入契约”。
- pure reducer 检查“给定这些事实，规则允许什么”。
- 执行器与存储边界检查“现在提交时，相关事实是否仍成立”。
- provider 与 journal 提供“这件事到底发生了什么”的证据。

**纯决策不解决 stale snapshot。** 两个纯函数读到同一份“剩余一个名额”快照，都能正确地计算“可以领取”；若提交处没有竞争控制，系统仍会发出两个名额。

smart constructor 建立的合法值也有寿命。例如 `Authorized` 在创建时满足约束，不表示权限撤销后仍可写。可以保留生成时的 revision/generation，提交时再验证相关契约。

### Effect 描述、组合与外部事务

`Writeback → Spend → Closeout` 作为 effect 程序，有利于审查顺序和短路行为。但 `flatMap` 只约束程序中的组合，不能自动让三个远端系统加入一个原子事务；换成 TypeScript 也不会创造持久性。

一个可序列化 command union 加解释器，已经可以带来很多价值。只有真的需要 handler 控制 continuation 等语义时，才需要进一步讨论完整的 algebraic effects。把每个 callback 都改名为 effect，既不增加保证，也不减少复杂度。

对 LoopX 而言，Python 迁 TS 的价值应表现为：同一条规则只剩一个 owner、合法状态更容易表达、真实执行路径可验证、旧判断被删除。语言比例不是验收目标。

## 5. 数据库替应用承担什么

数据库把一些原本需要应用自己实现的承诺集中到一个经过验证的边界：关联修改的一致提交、并发控制、持久化恢复、索引与查询。但它只能保护实际进入该边界的数据和操作。

ACID 可以用一笔任务领取事务理解：

| 性质 | 任务领取例子 | 应用仍需负责 |
| --- | --- | --- |
| Atomicity | claim、预算预留和本地事件一起生效或一起回滚 | 外部 API 是否参与同一原子边界 |
| Consistency | 已定义的约束在事务前后成立 | 约束是否完整，业务逻辑本身是否正确 |
| Isolation | 并发领取按选定隔离模型观察彼此 | 哪个隔离级别足以保护实际不变量 |
| Durability | 确认提交后，在声明的故障模型下可恢复 | sync 配置、存储故障、复制与备份策略 |

ACID 的 C 是应用/数据库完整性约束；CAP 的 C 通常讨论线性一致的访问历史；Agent 的“答案正确”又是另一种语义正确性。不要只用“一致性”三个字覆盖所有含义。

### 找到提交点与原子范围

“把操作写在一个函数里”没有原子性保证。“包进一个 SQL transaction”只覆盖同一事务实际管理的资源。事务中发了邮件，然后 SQL rollback，邮件不会被收回来。

在设计时画一条线：线内哪些事实一起提交，线外哪些动作必须通过可恢复协议交付。先问“能否把不变量放进同一个事务”，再讨论分布式协调。这通常比先选一个框架更有效。

另外，SQL `COMMIT` 的响应也可能丢失。服务端结果是否已持久化与客户端是否知道，仍是两个问题；数据库替你执行了事务，不代表客户端没有不确定提交。

## 6. 隔离级别与并发历史

先看一个不需要复杂术语的错误。系统必须至少保留一个值班 worker，开始时 A、B 都在值班：

| 时刻 | 事务 T1 | 事务 T2 |
| --- | --- | --- |
| 1 | 读到 A、B 都在线 | |
| 2 | | 读到 A、B 都在线 |
| 3 | 因为 B 在，令 A 下线 | |
| 4 | | 因为 A 在，令 B 下线 |
| 5 | 提交 | 提交 |

它们修改不同记录，没有直接的同一行写冲突，但最终无人值班。任何串行顺序下，后一个事务都会看到只剩一个 worker，因此不应下线。这叫 **write skew（写偏差）**。

映射到 LoopX：多个 Agent 各自读到“还有别的负责者”“剩余预算足够”“存在后继任务”，分别修改不同记录，仍可能破坏跨记录规则。

### MVCC 是机制，隔离级别是承诺

MVCC 保留多个版本，使读者能看到一个符合规则的快照。它能减少读写互相阻塞，却不自动保证任意多行判断可串行化。旧版本还需要回收，长事务可能延缓清理。[CMU 的 MVCC 讲义](https://15445.courses.cs.cmu.edu/fall2025/notes/20-multiversioning.pdf)

以 PostgreSQL 18 为具体例子：Read Committed 的普通查询按语句取得快照；Repeatable Read 使用稳定事务快照，但仍可能出现序列化异常；Serializable 增加依赖检查，可能要求整个事务重试。不同数据库同名级别的细节可能不同。[PostgreSQL 隔离级别](https://www.postgresql.org/docs/18/transaction-iso.html)

一个实用决策顺序：

1. 能否用单条条件更新表达不变量？
2. 是否需要锁住一个共同的协调记录，令相关决策串行化？
3. 是否需要 Serializable 来保护更复杂的读写依赖？
4. 无论哪一种，失败时怎样重读和重算？事务里有没有不可回滚的外部效果？

### 可串行化要检查整个历史

考虑两个事务：各自先读 `x`，将读值作为事务最终返回值，再把 `x` 固定设成 1，然后提交。初始 `x=0`。并发时双方都可能读到 0，最后 `x=1`；串行运行最后同样是 1，但第二个事务必须读到 1。

因此，**最终状态一样，不足以说明可串行化**。需要存在一个符合事务语义的串行历史，解释读值与写入等观察。对常见冲突可串行化模型，读写依赖图无环是一个有力判据，但不要把它当成所有 MVCC 历史的无条件唯一判定法。[并发控制理论讲义](https://15445.courses.cs.cmu.edu/fall2025/notes/17-concurrencycontrol.pdf)

学习这节的验收很直接：不看答案，能画出一次 write skew，并说出你采用的修复机制在哪个共同边界阻止它。

## 7. 锁、CAS 与提交时验证

锁让竞争者在一个受保护区域排队；OCC 允许先计算，再检查依据是否过期。二者都是实现不变量的手段，要看冲突范围、锁持有时间和重试成本。

最小的 CAS 可以用 SQL 条件更新表达：

```sql
-- 教学示例：只有调用方仍持有读到的 version，更新才可能命中。
UPDATE work_items
SET state = :new_state, version = version + 1
WHERE id = :id AND version = :expected_version;
```

必须检查命中行数，并以事务成功提交为准。命中 0 行意味着依据已失效，需要重读并重新决定；不能只把 expected_version 改成最新数字后强推原来的结论。

### 一个 version 保护不了没纳入检查的依赖

如果决策还依赖用户 gate、goal revision 和预算，单独比较 Todo 的 version 不够。可以在同一事务中检查相关行，使用共同锁/版本，或使用合适的隔离模型。版本范围也不能无脑扩大到全局，否则不相关的工作会互相冲突。

这与 TOCTOU（检查时与使用时之间的竞争）是同一个问题：

```text
先验证权限 → 等待模型 30 秒 → 无条件执行
```

等待期间权限可能变化。长计算通常放到事务外，提交处重新验证影响正确性的前置条件。对外部 provider，验证和效果之间若还有空隙，还需要 provider 自身的条件写、token 或幂等契约。

### ABA 与版本含义

状态可能从 A 变 B 再回 A，比较内容看起来没变，期间却已经发生了所有权切换。单调 generation/version 可以保留这种历史变化。内容 hash 适合绑定载荷，不能单独代表新鲜度。

`operation id` 标识同一逻辑动作，`version` 标识数据版本，`generation` 标识授权代次。这几个数字即使长得相似，也不能互换。

多个锁还要考虑死锁：T1 先锁 A 再等 B，T2 先锁 B 再等 A。固定加锁顺序、缩短事务、处理数据库中止结果，比“每处都加锁”更完整。[PostgreSQL 显式锁文档](https://www.postgresql.org/docs/18/explicit-locking.html)

## 8. 持久化、日志与恢复

可以把一次写入粗略分成：应用内存、系统缓存、稳定存储。函数返回、`write()` 返回、事务确认，分别处在哪个位置，要看实现和配置。

WAL 的关键是顺序约束：相关日志先进入稳定存储，再允许对应脏数据页落盘。提交时可先保证恢复所需日志持久化，数据页随后写出，崩溃后据日志恢复。group commit 可以让多个事务共用一次 flush。[PostgreSQL WAL](https://www.postgresql.org/docs/18/wal-intro.html)

这不是“有一个日志文件就安全”。需要明确记录格式、提交标记、flush ordering、损坏检测、恢复算法与回收条件。SQLite 的 rollback journal 与 WAL 使用不同机制实现原子提交，不能把一种模式的细节套到另一种。[SQLite 原子提交说明](https://www.sqlite.org/atomiccommit.html)

### 几种常被混用的日志

| 机制 | 记录的主要对象 | 主要服务的问题 |
| --- | --- | --- |
| WAL | 数据库恢复需要的记录 | 崩溃后的存储状态恢复 |
| Domain event / event sourcing | 已接受的业务事实 | 业务历史与状态重建，若系统选择它作为权威 |
| Outbox | 与业务事务绑定的待交付消息 | 提交后可靠投递 |
| Effect journal | 某次外部动作的身份、阶段与结果证据 | 中断后决定回查、重试或继续 |
| 普通 trace/log | 诊断信息 | 排查；默认不具备权威状态契约 |

某个记录可以兼具多个角色，但必须逐项证明；文件名不会赋予保证。Event sourcing 也不要求“一切都只能从头重放”，snapshot 可加速恢复，但要绑定 log position、schema 和校验规则。

### Checkpoint 与备份

Checkpoint 缩短恢复路径或推进日志合并，不表示旧日志立即可删。reader、replica、backup 或审计可能仍依赖它。业务去重记录也一样：若迟到重试仍可能到达，提前删除会重新打开重复执行窗口。

SQLite WAL 允许读写并发，但单个数据库文件仍只有一个同时进行的 writer；长读事务会影响 checkpoint 进度。掉电持久性还受同步配置影响，不能仅凭启用 WAL 宣称全部具备。[SQLite WAL](https://www.sqlite.org/wal.html)

备份要覆盖独立故障域，并实际恢复演练。复制可能把误删除同步出去；WAL 与主数据同盘也可能一起损坏。RPO 表示可容忍的数据损失窗口，RTO 表示可容忍的恢复时间；它们需要测量，不由“有备份”三个字自动满足。

对于文件状态机，atomic rename 的可见原子性与掉电后的持久性也要分开；文件和目录的同步、同文件系统限制等需要按平台验证。教学异常、进程 kill、虚拟机断电属于不同层次的故障注入。

## 9. 幂等与 exactly-once 的范围

数学上的幂等可以写成：

$$
f(f(x))=f(x)
$$

设置某状态为固定值可能幂等，执行 `balance -= 1` 通常不幂等。真实 API 的问题更复杂：相同意图重复到达，应当只有一次业务效果，并能返回足以归因的历史结果。

### 幂等键需要一个接受协议

一个够用的设计至少回答：

- key 的作用域是什么：哪个租户、资源和操作类型？
- 相同 key、不同 payload 如何处理？通常应拒绝冲突，而不是静默返回旧成功。
- 去重记录与业务变更是否原子提交？
- 两个相同请求同时到达时，谁获得执行权？
- 结果保留多久，过期重试怎么办？
- 客户端崩溃后，如何找回同一个 key？

典型的本地事务模式是：

```text
BEGIN
  查找 operation_id
  已存在且 payload 相同 → 返回已记录结果
  已存在但 payload 不同 → 拒绝
  不存在 → 接受这次操作
           修改业务记录
           保存 operation_id、payload 绑定与结果
COMMIT
```

实现还需要唯一约束/锁或等价并发机制。`SELECT 没有 → 执行 → INSERT` 若不在正确的原子与隔离边界内，仍可能让两个请求都执行。把 key 放在日志里，仅仅提高了可观察性。[幂等 API 的原子性、参数冲突与保留期](https://aws.amazon.com/builders-library/making-retries-safe-with-idempotent-APIs/)

### 一次调用、一次投递、一次效果

“至少一次投递”允许重复消息；“至多一次投递”可能丢消息。应用需要讨论的是哪个可观察业务效果最多或恰好发生一次，以及在什么恢复假设下最终发生。

可以有十次网络调用，但一个逻辑扣减；也可以消息只送达一次，却在处理器内错误扣减两次。Exactly-once 必须指明作用范围、身份、事务边界和故障假设。

Kafka 的事务可把输出记录和消费位置放进同一 Kafka 事务；写到外部系统时，仍需目的系统协作或相应协议。由此不能直接推出“Kafka 消费者发邮件也只有一封”。[Kafka Message Delivery Semantics](https://kafka.apache.org/41/design/design/#message-delivery-semantics)

### `absent` 比一个 404 强得多

恢复时的 absent 应是 provider 契约下足够可靠的“该逻辑操作未提交”证据。查询一个滞后副本没找到，不够；查错租户或 key，也不够。

甚至一次线性一致的“当前没有”，也不能单独排除一个仍在途的旧请求稍后提交。协议还需要：旧尝试已被可靠终止/隔离，或者 provider 对同一操作实行原子幂等。否则“回查为空 → 重试”与旧尝试仍可能产生两个效果。

这也是阅读 LoopX resolver 时必须追问的内容：**是谁给 `absent` 定义语义，具体 provider 如何证明它？** 一个 TS 联合类型无法替 provider 完成这份证明。

## 10. 租约、fencing 与旧执行者

Lease 通常给一个执行者有限时间的使用权，减少永久锁死。难点在于：权威认为 lease 过期时，旧执行者不一定已经停止。

```text
1. A 领取资源，generation = 7。
2. A 长时间暂停。
3. A 的 lease 到期，B 领取，generation = 8。
4. B 写入新结果。
5. A 恢复，携带旧数据继续写。
```

如果写入处只相信“A 曾经领到过任务”，新结果会被旧 owner 覆盖。

Fencing 的做法，是在受保护资源的写入边界携带并检查 token。资源已经接受 generation 8 的写入后，应拒绝 generation 7 的新写入；检查与变更需要在同一个受保护边界完成。[Kleppmann 对 fencing 的原始论述](https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html)

### Fencing 的细节决定保证强度

**只记“见过的最大 token”**，能阻止新 token 已在资源生效后到达的旧写。但在资源尚未见到新 token 的窗口里，它不一定能知道旧 lease 已过期。

若要求“权威移交生效后，旧 generation 的任何新提交都失败”，需把移交与资源的当前 generation 校验可靠地连接：例如同一 authority 事务中检查当前代次，或在交接完成前先安装资源 fence。跨数据库与外部 API 时，要单独证明这个连接。

所以，以下设计都不充分：只在 worker 发请求前比较一次 token；只在日志里记录 token；只保证发号单调，但资源不检查；把随机 UUID 当作有序 fence。

### Lease、权限、幂等与历史回执

Lease 解决当前协调所有权；authorization 解决允许做什么；幂等解决重复逻辑操作；receipt 记录某次操作的结果。四者不能互相替代。

旧 worker 可以在读取权限允许时查询自己过去的 receipt，以消除不确定性；这不代表它仍有权执行新的效果。重新领取后也不能为了“顺利重试”改变旧操作身份。

撤销权限与在途动作之间也有窗口。控制面通常能明确阻止下一次 dispatch；已经被外部系统接受的动作是否还能撤销，取决于它的取消协议。产品的 Stop 应准确表达“请求停止”“已停止新增动作”“在途结果待核对”等层次。

## 11. 跨系统提交、投递与补偿

### Transactional Outbox

设任务状态在数据库里，完成通知发到消息系统。直接写两处总有缺口：

```text
先写 DB，后发消息：中间崩溃 → 状态完成，消息没发。
先发消息，后写 DB：中间崩溃 → 用户收到完成，状态没提交。
```

Outbox 把“业务变化”和“待发送消息”放进同一 DB 事务；relay 随后投递。业务提交于是留下可恢复的投递责任。relay 若发送成功后、标记完成前崩溃，仍可能重复发送，所以消费者需要幂等接受。[Transactional Outbox 模式](https://microservices.io/patterns/data/transactional-outbox.html)

```mermaid
flowchart LR
    A[业务事务] --> B[任务状态与 Outbox 一起提交]
    B --> C[Relay 可重试投递]
    C --> D[消费者原子去重并应用]
    D --> E[更新交付进度]
```

如果消费者去重表和消费者业务变更不在同一事务，仍会出现“标记收过但没处理”或“处理了但没标记”。只解决生产端双写不等于端到端完成。

### 投影的幂等与顺序

事件 11 先到、事件 10 后到，即使每个只应用一次，旧 snapshot 仍可能覆盖新状态。幂等不能代替顺序。

对于包含完整状态的同一 aggregate snapshot，可以在原子发布时拒绝较旧 revision。对于 delta，不能直接丢掉旧序号：跳过 delta 10 再应用 11 可能缺失必要变化，需要顺序缓冲、补洞或从权威重建。跨 aggregate 的 cursor 也不自动给出全局一致快照。

读自己的写入，可以拿写入 receipt 的 revision 等待投影追到该版本，或直接读 authority。投影 lag 应被暴露，不能悄悄升格为权威。

### 2PC、Saga 与工作流

| 机制 | 核心责任 | 需要付出的代价或边界 |
| --- | --- | --- |
| 2PC | 参与者对同一事务的 commit/abort 达成原子决定 | prepare 后可能阻塞，需持久化协议状态并恢复决策；隔离另有实现要求 |
| Saga | 多个本地提交之间，用前进恢复或业务补偿处理失败 | 中间结果可见；补偿也会失败，且不一定等价于回到从未执行 |
| Durable workflow | 保存流程进度、输入/结果与恢复位置 | 外部 activity 的幂等、授权和业务可接受性仍需定义 |

2PC 的 prepare 是参与者协议的一部分，通常意味着对后续 commit/abort 承诺的持久准备；LoopX effect journal 中的 `prepared` 只是本地执行意图/阶段记录，不能因为同名就视作远端已进入 2PC。

Saga 的补偿是新的业务操作。例如撤销一项预订可能有费用；已经被人阅读的通知无法通过删消息使其“从未发生”。补偿顺序、重复补偿与人工介入都属于契约。进一步阅读：[Garcia-Molina 与 Salem 的 Sagas 原始论文](https://www.cs.princeton.edu/techreports/1987/070.pdf)。

Temporal 通过历史与确定性命令匹配恢复 workflow；这能保存执行进度，但不直接判断一篇研究报告是否充分、一项用户要求是否仍成立。[Temporal Workflow Replay](https://docs.temporal.io/workflow-execution#replays)

## 12. 一致性、共识、CAP 与 FLP

这些概念的价值，在于让承诺可精确比较。先问操作对象和历史，再使用名词。

### 四种经常混淆的保证

| 概念 | 关心什么 | 一个区分点 |
| --- | --- | --- |
| 线性一致性 linearizability | 每个操作仿佛在调用与返回之间某个瞬间发生，并尊重不重叠操作的现实先后 | 写成功返回后才开始的读，不能返回被该写覆盖的更旧值，若没有介入的新写 |
| 可串行化 serializability | 多操作事务的历史可由某个串行执行解释 | 不单独要求该顺序尊重现实时间 |
| 严格可串行化 strict serializability | 事务可串行化，并尊重事务间现实先后 | 同时讨论事务与新鲜度 |
| 最终一致 eventual consistency | 停止更新并满足传播/合并假设后，副本最终收敛 | 不自动给出收敛时限、读己之写或跨键不变量 |

不要把线性一致性概括成“所有服务器每时每刻内存完全相同”。它约束外部可见的操作历史，内部实现可以有延迟副本，但必须约束哪些副本如何回答请求。[Herlihy 与 Wing 的定义，先读 §1—3.1](https://pdos.csail.mit.edu/6.824/papers/p463-herlihy.pdf)；[事务级严格可串行化的说明](https://jepsen.io/consistency/models/strong-serializable)

### 共识与复制状态机

复制状态机的基本思路：副本以一致顺序应用同一组命令，状态迁移确定，就能得到一致结果。共识帮助副本在失败条件下确定可接受的命令顺序。

这正好连接 FP：确定性 reducer 适合作为 apply 核心；时钟、随机值和模型输出若直接在每个副本内部重新取样，同一命令就可能产生不同状态。必要的非确定性结果应通过受控方式进入被排序的数据。

Raft 将 leader election、log replication 和 safety 条件组织起来。多数派的交集是关键，但“随便一条日志写到两个节点就算安全提交”不成立；term、投票与日志匹配规则共同保护历史。单节点本地 WAL 也不等于共识日志。[Raft 论文 §2、§5、§8](https://raft.github.io/raft.pdf)

三副本多数派通常需要两个节点响应；能在模型假设下容忍一个 crash，并不等于三个磁盘在同一机器上具有三个独立故障域，也不覆盖 Byzantine 响应。读操作还需要相应的新鲜度协议，不能默认任意 follower 都能提供线性一致读。

### CAP

当网络允许分区，对于需要协调的读写对象，无法同时保证线性一致的结果和每个非故障节点上的请求都得到符合服务语义的响应。这里的 availability 不是业务报表里的“99.9% SLA”，拒绝或返回错误不能用来绕过定理。

LoopX 中可以为不同操作选择不同退化行为：失联时允许读取标注陈旧度的展示数据；对无法证明当前 owner 的保护性写入拒绝或等待。无需用一个“系统是 CP/AP”的标签概括全部 API。[Gilbert 与 Lynch 对 CAP 的解释](https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf)

### FLP

FLP 说明：在完全异步的消息模型中，允许一个进程 crash 的确定性共识协议，不能对所有允许执行同时保证安全与终止。它没有说实际系统不能达成共识。工程协议在进展上依赖额外的时序/最终稳定性假设，或采用其他明确的模型变化。[FLP 原论文，先读摘要与引言](https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf)

最实用的学习结果是：看到“必定最终成功”时，开始寻找它的可用性、公平性和时间假设；看到超时时，不把慢进程直接证明为死进程。

## 13. 存储引擎、索引与扩展

先掌握一条查询经过哪些层：请求解码 → 查询计划 → 索引/数据页 → buffer/cache → 存储 → 结果序列化。数据库不是一个固定延迟的字典。

### B+ tree、LSM 与放大

B+ tree 用高扇出树减少页访问，适合点查与有序范围查询。索引能减少读取，但每次写入也要维护索引和相关页。复杂度之外还要考虑页布局、缓存命中与实际 IO。

LSM 将写入先缓冲，再形成不可变有序文件，通过 compaction 合并。它把部分随机写代价转移成后台合并，代价可能表现为写放大、读放大、空间放大与 compaction 干扰。Bloom filter 可减少无效查找；它的概率性误报不会凭空创造存在的记录，命中仍要检查数据。

不必先自己实现一个存储引擎。先能解释一次热查询为什么扫描、为何某个索引没被使用、更新一行为什么引发大量写入。需要系统补底层时，再读 [CMU 15-445 的 Storage、Indexes、Query Planning 课程](https://15445.courses.cs.cmu.edu/fall2025/schedule.html)。

### 一个真实控制面查询

假设调度器频繁查询：

```sql
SELECT id FROM tasks
WHERE goal_id = :goal AND status = 'ready'
ORDER BY priority DESC, created_at ASC
LIMIT 20;
```

设计索引要从这个读取模式出发，观察过滤、排序和数量是否可以由索引承担。解释计划、真实数据分布与相同负载下的 base/head 比较，比“加了索引应该更快”可靠。

过多索引会让每次状态迁移变贵；把整个 Goal snapshot 重写成大 JSON 则可能让一个小字段变化付出整份数据的序列化和写放大。是否规范化到行级，要同时考虑原子边界、查询模式与迁移成本。

### SQLite、PostgreSQL、分片

SQLite 的价值包括部署简单、进程内访问与本地事务；PostgreSQL 的价值包括服务化并发、多客户端与成熟数据库运维能力。不能从产品名字直接推断特定负载的吞吐，更不能把“上 PG”当作跨 provider 幂等的修复。

选型先测：并发写事务数量和持锁时间、单 Goal 热点、p95/p99 延迟、数据增长、恢复时间、备份需求、故障域与运维能力。

分片可以减少独立 Goal 之间的竞争，却可能把一个共享预算拆到多个事务边界。一个全局 hot row 也不会因为有很多 shard 就自动扩展。副本用于冗余/读扩展，分片用于分散数据或负载，两者不要混称“横向扩容”。

## 14. 排队、重试与资源控制

控制面里经常有一个共享瓶颈：单 writer、一个 Node bridge、串行执行的调度循环，或少量外部连接。流量接近服务能力时，等待会先恶化。

在简化的 M/M/1 模型中，若到达率为 λ、服务率为 μ，且 λ < μ：

$$
\rho=\frac{\lambda}{\mu},\qquad E[T]=\frac{1}{\mu-\lambda}
$$

这里假设 Poisson 到达、独立指数服务时间和一个服务器；不能拿它直接预测真实长尾。它提供一个直觉：μ=100/s 时，λ 从 50/s 增到 90/s，平均系统时间从 20ms 增到 100ms。利用率只增加了 40 个百分点，系统停留时间却增加了五倍。[CMU 的 M/M/1 讲义](https://www.cs.cmu.edu/~harchol/Perfclass/NotesFall25/chpt12prep.pdf)

Little's Law 的 `L = λW` 是另一个检查量纲的工具：在稳定、边界一致的系统中，平均在途数量等于吞吐乘平均停留时间。测 RPC、完整 Turn 或用户任务时，不能把不同边界的数混进同一个式子。

### 重试会改变负载

每层最多三次尝试，若三层独立重试，最坏可能产生 27 次底层尝试。外层 deadline、每次 timeout、backoff、jitter 与统一 retry budget 要一起设计。重试条件还要区分暂时不可用、确定性输入错误和未知提交。

Backpressure 控制进入速度，admission control 决定接纳哪些工作，quota 限制资源预算，fairness 防止某些工作长期饥饿。它们与 lease 的所有权规则有关联，却不是同一个概念。

如果要保证硬预算不超支，通常需要在开始前预留资源，或使用可证明不会超卖的分配协议；完成后才累计 spend 只能提供事后记账。多个 worker 同时开跑时，这个区别尤其明显。

LoopX 的迁移还存在语言桥接成本：把小纯函数拆成很多 Python→TS RPC，可能增加序列化与排队。减少重复语义是值得的，但迁移边界应尽量对应完整决策或生命周期，成本要在真实入口测量。合并调用的优化也不能撤掉必要的提交前校验。

## 15. 回到 LoopX 的具体问题

本节基线为 `main@85dc7cec83f923c1ef5d6148957f5836ed400251` 与 [PR #5417](https://github.com/loopx-project/loopx/pull/5417) 的 `58b3dfc079528f69a8d2b5a6a400055b5a492699`。后者是教学用审阅版本；这里不把 PR 提交视为已发布，也不推断其他 provider 的资格。

### 语义控制面与语义执行引擎

语义控制面回答：目标与验收是什么，哪项工作现在有意义，谁对它负责，允许的动作和预算是什么，下一步义务是什么。

执行引擎回答：把被允许的动作放到哪个执行者上，怎样准备和执行，怎样记录结果，在中断后如何确定继续、回查或等待。

数据库提供这些协议依赖的事务、持久性和并发工具。它不会替系统定义“这个 Todo 是否完成”；模型可以提出方案，也不因此拥有任意改变状态的权限。

```text
目标与证据 → 有版本的领域判断 → 授权动作 → 外部执行
    ↑                                  ↓
    └──── 受检结果、持久事实与新义务 ──────┘
```

这个分层允许把“聪明但不确定的提案”与“受约束的状态变更”连接起来。但领域判断是否正确，仍需要业务验收和独立证据；类型与事务只能保护已经编码的规则。

### 四个值得逐行理解的入口

| 入口 | 阅读问题 |
| --- | --- |
| [共享 settlement identity 与 receipt](https://github.com/loopx-project/loopx/blob/58b3dfc079528f69a8d2b5a6a400055b5a492699/loopx/control_plane/effect_program.ts) | 相同操作如何认定？unbound 和 bound 的区别在哪里？哪些 receipt 能解释哪些阶段？ |
| [TS provider admission/recovery](https://github.com/loopx-project/loopx/blob/58b3dfc079528f69a8d2b5a6a400055b5a492699/loopx/control_plane/turn_driver/settlement_provider.ts) | returned 与 readback 为什么要区分？unknown 为什么 hold？显式错误 effect ref 在哪里拒绝？ |
| [Python IO interpreter](https://github.com/loopx-project/loopx/blob/58b3dfc079528f69a8d2b5a6a400055b5a492699/loopx/control_plane/turn_driver/settlement.py) | 哪些动作由 TS 授权？prepare/checkpoint/abort 哪个先落盘？异常后保留什么？ |
| [恢复回归测试](https://github.com/loopx-project/loopx/blob/58b3dfc079528f69a8d2b5a6a400055b5a492699/tests/test_loopx_turn_settlement_recovery.py) | 崩溃点插在哪里？测试读什么持久证据，证明没有重复效果？ |

第一次读，不要从文件顶部一路看到尾。拿一条“已提交但响应丢失”的轨迹，在四个文件之间追踪它。

### PR #5417 为什么是一个 FP × 分布式系统例子

此前存在这样的危险组合：provider 返回正向提交标志但包含无效 completion；Python 提前 checkpoint，或者包装器把它改写成“拒绝”并清除 prepared。后续重试便可能把实际已发生的效果再做一次。

新边界让 TS 在 checkpoint 前接受或拒绝证据；无法接受的已提交结果保留 prepared，进入恢复，而不是假装外部效果没发生。Python 负责把 provider 返回值或 readback 传回来，再执行被授权的 IO。

具体串联了五件事：ADT 让动作与结果分支明确；纯函数集中决策；稳定 effect identity 绑定恢复；journal 保存本地阶段；provider readback 帮助解释未知结果。每一件都必要，但没有任何一件单独给出端到端 exactly-once。

注意两个兼容与验证边界：legacy payload 可以省略 effect ref，显式提供却不匹配时才拒绝，因此不能宣传成“所有 provider 都已完整绑定身份”；File journal 与 CLI 路径的故障测试也不等于 PostgreSQL、租约移交或全系统掉电验证。

该 PR 的行为与验证范围应以公开 diff、测试和检查结果为准；测试数量不构成数学证明，也不自动覆盖其他后端。

### 用六个问题检查下一项 LoopX 设计

1. 哪份状态是 authority，哪些只是投影或诊断？
2. 要保护的业务不变量是什么，是否横跨多个 owner？
3. operation id、数据 revision、lease generation 各自绑定什么？
4. 相关判断在提交时怎样再次成立？
5. 效果已发生而响应/receipt 丢失时，谁负责消除不确定性？
6. 结果怎样被下一消费者采用，并最终反馈到原始用户入口？

这套问题可以直接用于 [状态定义](https://github.com/loopx-project/loopx/blob/85dc7cec83f923c1ef5d6148957f5836ed400251/docs/product/core-control-plane/state-definitions.md) 与 [组合恢复 RFC](https://github.com/loopx-project/loopx/blob/58b3dfc079528f69a8d2b5a6a400055b5a492699/docs/architecture/rfcs/composable-state-machines-recovery-verification-v0.md) 的审阅。

## 16. 与其他领域的交叉

### FP × CRDT：组合律决定能否自由分发

结合律允许改变分组，交换律允许改变顺序，幂等律允许重复合并。三者解决不同的执行自由度。整数加法满足结合与交换，却不幂等；重复计数仍会出错。

典型 state-based CRDT 的 merge 是 join，满足这些代数性质，并要求更新符合该数据类型的增长条件；operation-based CRDT 则有不同的投递与因果前提，不能把同一组条件无差别套用。[Shapiro 等人的 CRDT 报告 §2](https://dsf.berkeley.edu/cs286/papers/crdt-tr2011.pdf)

“已收集证据的集合”可以设计成容易合并的结构；“这份证据现在足够批准执行”会受撤销、范围与新版本影响，往往需要额外协调。CALM 把单调性与无协调计算联系起来，但它不是“所有业务都能改成最终一致”的许可。[Hellerstein 与 Alvaro 的 CALM 介绍](https://rise.cs.berkeley.edu/blog/an-overview-of-the-calm-theorem/)

尤其要小心：append-only 的历史包含越来越多事实，并不意味着基于历史计算的“当前有效权限”也是单调的。撤销事实的加入会使先前可执行的动作变成不可执行。

### 数据库 × 编译器：把语义保持作为迁移目标

编译器把源程序变成另一种表示，正确性关心可观察行为是否保持。Python→TS 的控制面迁移也可以按这个方式审查：相同可信输入下，允许的动作、失败类别和顺序是否保持；故意改变的语义有哪些；历史数据如何解码。

源语言实现可能本来就有 bug，所以 parity 是兼容证据，不是最高裁判。需要独立写出的领域不变量来决定哪些差异是修复，哪些是回归。

### 数据库 × Agent memory：知识不能偷偷获得执行权

检索出的经验适合提供候选策略、历史事实线索与失败模式。它可能过期、被撤销、属于别的 goal，或者只是模型总结。向量相似度不建立资源权限，也不说明当前版本仍满足前置条件。

memory item 的 source、revision、scope 和 validity 可以帮助验证适用性；在执行前仍需读取对应权威。将旧成功轨迹当成新执行许可，正是把 evidence 与 authority 混用。

### Durable workflow × Agent planning：确定性地管理非确定性

模型调用可以作为外部非确定性操作，其结果被记录后进入后续决策。恢复时使用历史结果；重新规划时才产生新调用，并明确新意图与新版本。

重放不是把 temperature 设为 0 后重新问模型。模型版本、工具环境和外部数据变化都可能改变结果。能重放控制决策，也不等于能逆转已经发生的真实世界动作。

### 分布式系统 × 多 Agent 协作：ACK 的层次

消息已发送、消息已入收件箱、接收者已领取、结果已产生、结果已验证、下游已采用、用户已收到，是不同事件。

有一个 `delivered=true` 字段时，先问它对应哪一层。协作协议需要稳定的 artifact revision、依赖关系、接收责任和验收结果。把十个 worker 都启动起来，只证明它们存在；证明协作需要追踪一个具体依赖如何进入下游结果。

### 控制理论 × 长程 Agent：反馈延迟与稳定性

把 Agent 看作带延迟的执行器、把投影看作观察通道，可以解释一些现象：旧投影导致重复派工；短周期重规划来不及观察效果，造成振荡；无限增加任务会堆积欠账。

可借用反馈周期、阻尼、背压和观测延迟的直觉，但在没有模型和验证前，不应声称系统满足某个控制理论稳定性定理。适合落地的动作包括版本化观察、有限并发、最小重规划间隔和可见 backlog。

## 17. 怎样建立可信的正确性证据

“测试通过”需要继续问：测试的 oracle 从哪里来，故障插在哪里，没测的历史有哪些？

| 层次 | 适合回答 | 不能替代 |
| --- | --- | --- |
| 类型与 decoder | 非法组合能否构造/进入 | 提交时的新鲜度与权限 |
| 纯函数例子与 property test | 规则在生成输入上是否满足性质 | 真实存储和并发时序 |
| 有界状态探索 | 指定 actor/操作/故障范围内是否有反例 | 无界 liveness 与实现对应性 |
| 真实后端故障测试 | 实际提交/恢复边界的行为 | 其他后端或更强故障模型 |
| 生产入口与用户旅程 | 一整条工作是否可用、可解释、可恢复 | 所有可能执行的形式化证明 |

### 从一个独立不变量开始

以“同一个 op 最多扣减一次”为例，独立记录 provider 中的业务效果次数，不要只断言调用方返回了 `ok`。调用方可能返回成功两次；也可能返回失败，外部其实已扣减两次。

故障至少覆盖：准备前、准备后执行前、效果提交后响应前、响应后 checkpoint 前、checkpoint 后返回前。再加重复/冲突请求、unknown readback、陈旧 generation 与乱序投影。

把一个正确实现故意改坏，例如删除 payload 绑定或 generation 条件，测试应失败。这叫 sensitivity/mutation 思路；它能发现“无论实现对错都绿”的装饰性测试。

### 模型与实现的关系

一个模型说“提交是原子的”，实际代码却先写业务再写 receipt，模型检查可能全部通过。因此还需要 refinement 论证：实现中的哪些事件映射为模型的一步，哪些属于可忽略内部步骤，失败窗口怎样映射。

有界模型可以穷举“两位 worker、一个操作、至多若干步”的状态空间；它发现的反例有价值，但不能自动外推到任意 worker 和任意长期执行。证明与测试的力度都应和声明相匹配。[TLA+ 课程的 Implementation 与 Refinement 部分](https://lamport.azurewebsites.net/video/videos.html)

### 一份设计的最小推理卡

下一次讨论新机制时，写下这八行：

```text
对象与用户结果：
唯一状态/决策 owner：
需要保持的不变量：
操作身份与版本：
原子提交点：
允许的故障与不确定结果：
恢复路径及进展假设：
能够推翻设计的最小反例与验证：
```

能填完整，再选择库、数据库或抽象。填不出来的地方，就是学习和设计需要继续推进的地方。

## 来源与使用说明

原讲义记录的来源核对日期为 2026-10-01；本次公开整理检查了文本与引用，未重新下载所有外链。PostgreSQL 链接固定为 18 文档；课程分别使用 CMU Fall 2025 和 MIT Spring 2026 页面。课程是可选的系统补充，不要求先学完再继续开发。本文按相关章节与契约阅读来源，不声称完成了全部课程或论文证明。

理论/文档链接放在对应概念处，配套文件给出具体阅读顺序。LoopX 引用固定到上述 commit；这些版本是教学基线，不代表当前最新版。教学实验不导入 LoopX，不连接任何活动 Goal，也不构成 LoopX 生产资格证据。

正文采用 CS-Notes 常见的“判断 → 机制 → 例子 → 边界”组织方式。所有教学时序、练习与实验由原讲义构造，实验的通过范围另见配套说明。