【FoundationDB 内核】Resolver 与 OCC：冲突范围、窗口与自动重试

第 7 篇 把提交流水线走到「Resolver 判冲突」这一跳；本篇打开这一跳。核心问题：两个并发事务何时必须有一个失败，检测依据是什么，失败后谁负责重试。

FoundationDB 默认隔离是严格可串行化下的乐观并发控制（OCC）：执行期不加锁，提交时由 Resolver 检查。Developer Guide 用一句话概括判据：若某事务读过的值在它开始之后、提交之前被其他已提交事务改过，则本事务冲突失败。SIGMOD 2021 Algorithm 1 把同一判据写成对近期写历史的范围查询。

本文是「FoundationDB 内核」系列第 8 篇（共 18 篇）。上一篇：写事务流水线；下一篇：严格可串行化与 5 秒限制；→ 系列目录

版本锚定：FoundationDB 7.x。与 TiKV 的对照仅限隔离与冲突检测机制；不复制 distributed/39 中未在本系列复现的性能数字。

一、Conflict ranges：系统实际跟踪的是什么

Developer Guide Conflict ranges 一节写明：为检测冲突，系统跟踪每个事务读过和写过的 key 范围。点读、点写会被收成单点 range；范围读把整个区间纳入 read conflict range。

默认行为：

「冲突」在文档中的定义偏向 read-write：先提交者写了后提交者读过的位置。Developer Guide 特意提醒：熟悉「写写冲突」数据库的人常会困惑——FDB 的基础检测不是「两个写撞车就失败」，而是「你的读是否过期」。

flowchart LR
  subgraph TxnA["Transaction A"]
    RA["Read conflict ranges"]
    WA["Write conflict ranges"]
  end
  subgraph Hist["Resolver recent write history"]
    H["key range -> last commit version"]
  end
  RA -->|"intersects write with version in (readVer, commitVer)"| Abort["Abort A"]
  WA -->|"on success: update history"| Hist

SIGMOD 2021 Algorithm 1：对事务 \(T\) 的每个读范围 \(r\)，若历史中存在与 \(r\) 相交、且提交版本大于 \(T\) 的 read version 的写，则 abort；否则把 \(T\) 的写范围以 commit version 记入历史并允许提交。

二、Resolver：无状态角色上的有界写历史

2.1 职责与分片

官方 Architecture：Resolver 判断事务是否与已提交事务冲突；做法是在内存中保留约 最近 5 秒的已提交写，并用新事务的读集与之比较。Key 空间在多个 Resolver 间划分，冲突检测可并行；全部 Resolver 通过才算通过。

SIGMOD 2021 §2.4.2：历史结构实现为带版本信息的概率 SkipList；单 key 亦视为 range，从而范围读能挡住幻读（phantom）。

2.2 为何需要 5 秒窗口

Resolver 不能无限保留写历史。MVCC 可读版本窗口与冲突历史窗口对齐到约 5 秒：超时事务会以 transaction_too_old 等形式失败（Known Limitations）。这把：

• Resolver 内存；
• Storage 上多版本；
• 恢复时需要搬运的日志量；

都变成有界问题。第 9 篇专门论证这与恢复有界性的关系；本篇只强调：OCC 的「近期写集」不是无限日志。

2.3 假阳性：部分 Resolver 已记账

Architecture Transaction Commit：若一个 Resolver 已接受写集更新、另一个判冲突导致整事务失败，前者仍可能让后续事务与「未真正提交」的写集相交而失败。论文同样承认 false positive。缓解来自两点：生产冲突率通常很低；历史在 MVCC 窗口后过期。这是分片 OCC 的工程税，不是文档疏漏。

三、时间线：冲突窗口落在哪

设事务 \(T\) 的 read version 为 \(r\)，commit version 为 \(c\)（由 Sequencer 分配且 \(c > r\)）。\(T\) 冲突当且仅当存在已提交事务 \(U\)，其 commit version \(v_u\) 满足

\[ r < v_u < c \]

且 \(U\) 的写范围与 \(T\) 的读范围相交。

sequenceDiagram
  participant T as Txn T
  participant U as Txn U
  participant Res as Resolver

  Note over T: obtain read version r
  T->>T: read keys (build read ranges)
  U->>Res: commit at v_u, r < v_u
  Res-->>U: success (writes enter history)
  T->>Res: commit at c, check reads vs history
  Res-->>T: not_committed

因此：

• 拉长事务（更早的 \(r\)、更晚的 \(c\)）放大与别人写集相交的机会；
• 缩小读集（更细 key、snapshot read、避免大范围扫）降低冲突；
• 原子操作去掉「先读后写」造成的自相关冲突，适合计数器类热点（论文 §2.6、Developer Guide Atomic operations）。

官方 Minimizing conflicts：高频更新应打散到多 key；计数器用原子操作；不得已再用 snapshot read 并显式补必要的 conflict range。

四、自动重试与客户端契约

4.1 @transactional 与错误类

Python 等绑定的 @fdb.transactional 在事务冲突或瞬时故障时重试整段函数。Developer Guide 区分：

• 数据库操作受 ACID 约束；
• 客户端本地副作用（打印、改内存结构、调外部 API）不会自动撤销。

因此可重试事务应尽量幂等。Architecture 还指出：恢复期间可能出现 commit_result_unknown——客户端可能已提交成功却未收到确认；重试可能导致「逻辑上执行两次」，除非业务幂等或使用官方后续提供的幂等相关机制（以所用 API 版本文档为准）。

示意（形态来自官方 Developer Guide，非本机输出）：

import fdb
fdb.api_version(710)

@fdb.transactional
def increment(tr, key):
    raw = tr[key]
    value = int(raw or b"0")
    tr[key] = str(value + 1).encode()

若两客户端并发执行 increment，Resolver 会让其中一方因读集过期而 not_committed，装饰器重跑函数。把 print 或扣外部账放进该函数，冲突重试时会重复执行——这是客户端契约问题，不是 Resolver 漏检。

4.2 读事务几乎不走 Resolver

SIGMOD 2021 §2.4.1：只读事务在 read version 上可串行，客户端可本地「提交」而不打扰集群写路径。它们不与别人产生提交期冲突，也不把自己的写写入 Resolver 历史。这解释了为何读多写少负载下 OCC 压力主要来自写事务的读集，而不是「每个 SELECT 都打 Resolver」。

4.3 显式冲突范围：组合事务时的细控

Developer Guide 给出典型配方：原子加法本身不产生 read conflict，但若业务要求「重置发生时递增必须失败」，可对计数器 add_read_conflict_key，把重置写进冲突图。又如：大范围扫描只需保护真正返回的那一个 key 时，可用 snapshot 范围读，再对结果 key 显式加读冲突。这些 API 把「隔离强度」从默认严格可串行化局部调低或调高，但不会绕开 Sequencer 版本与 TLog 提交点。

五、与 TiKV Percolator SI 对照

站内 tikv-htap 第 10 篇 与 distributed/30 已拆 Percolator。此处只对照冲突与隔离，不重讲三 CF。

写偏斜（write skew）是经典区分：两个事务各读对方将写的数据、各自写自己的 key，在 SI 下可能都提交，却破坏「约束在串行下成立」。FDB 默认把读集纳入冲突，此类交叉读会冲突失败。若误用 snapshot read 去掉读冲突，隔离会降到接近「只保护你显式声明的集合」——Developer Guide 把 snapshot 定位为有意削弱隔离以换吞吐。

flowchart TB
  subgraph FDB["FoundationDB"]
    F1["Sequencer versions"]
    F2["Resolver OCC on ranges"]
    F3["Strict serializability default"]
  end
  subgraph TiKV["TiKV optimistic"]
    T1["TSO start_ts / commit_ts"]
    T2["Percolator locks in Regions"]
    T3["Snapshot isolation default"]
  end
  F1 --> F2 --> F3
  T1 --> T2 --> T3

六、冲突与延迟的组成（机制，非 benchmark）

Developer Guide Latency 把客户端感知拆成：取 read version 的等待、各次读、以及 commit 耐久等待。它明确：取版本阶段的排队不增加冲突（事务尚未开始）；真正拉长冲突窗口的是「第一次读之后到 commit 之前」的时间。因此官方建议并行发起多个读（futures），缩短 \(c-r\) 墙钟间隔。本系列未复现其「约若干毫秒」的示例数字，只保留因果结构：冲突概率是窗口与争用的函数，不是「OCC 天生慢」。

七、学术谱系、工程间隙与开放问题

谱系：Kung & Robinson（TODS 1981）定义 OCC：验证阶段检查读集是否仍有效。Berenson et al.（SIGMOD 1995）系统刻画 ANSI SQL 隔离现象，后续工作区分 SI 与可串行化。FoundationDB 用全局版本 + 提交期范围 OCC 直接对准严格可串行化；Percolator（OSDI 2010）用数据内嵌锁状态服务大规模增量更新，工程上常落在 SI。两条谱系解决的「谁保存冲突状态」不同：中心化近期历史 vs 分片锁表。

工程间隙：论文承认生产多租户负载冲突率常低于 1%，OCC 因此好用；这不是定理。热点计数器若不改用原子操作或打散，会把 Resolver 变成重试放大器。分片 Resolver 的假阳性在论文与官方文档中均有记录，但缺少公开的、跨版本的假阳性率测量标准。

开放问题：在何种 key 争用模型下，FDB 式中心 OCC 的重试放大劣于 Percolator 悲观锁或 Calvin 式确定性调度？这是事务系统设计里长期开放的经验问题；本系列第 9、17、18 篇从限制与选型角度继续收束，不在此编造阈值。

八、常见误解

九、小结

三句话小结：

1. Resolver 用约 5 秒内的已提交写范围，检查事务读集是否在 \((readVersion, commitVersion)\) 内被改过；命中则 not_committed。
2. 冲突范围可由普通读/写自动生成，也可被 snapshot、原子操作与显式 API 收窄或加宽，从而在隔离与冲突率之间移动。
3. 与 TiKV Percolator SI 相比，FDB 默认更强隔离、冲突状态集中在 Resolver；高冲突时两边都要靠应用侧减读集或换并发策略，而不是「换个系统名就消失」。

下一篇进入 严格可串行化与 5 秒限制：实时顺序、版本窗口与恢复有界性。

上一篇：写事务流水线

下一篇：严格可串行化与 5 秒限制

返回 系列目录

参考资料

论文（A 级）

1. Zhou et al. FoundationDB…. SIGMOD 2021（§2.4.2 Algorithm 1、假阳性与 Resolver 分片）。
2. Kung & Robinson. On Optimistic Methods for Concurrency Control. TODS 1981.
3. Peng & Dabek. Large-scale Incremental Processing…. OSDI 2010（Percolator；对照用）。
4. Berenson et al. A Critique of ANSI SQL Isolation Levels. SIGMOD 1995（隔离现象术语）。

官方文档（A 级）

5. FoundationDB 7.x, Developer Guide — Conflict ranges、Atomic operations、Minimizing conflicts、Latency。
6. FoundationDB 7.x, Architecture — Resolvers、Transaction Commit。
7. FoundationDB 7.x, Known Limitations — 5 秒事务上限。

站内对读

8. 第 7 篇写流水线、第 9 篇严格可串行化。
9. tikv-htap/10、distributed/30。