土法炼钢兴趣小组的算法知识备份

【分布式系统百科】Percolator 模型：Google 的乐观事务方案

2026-04-13 · distributed · #percolator #distributed-transactions #bigtable #tidb #snapshot-isolation #mvcc

文章导航

分类入口
distributed
标签入口
#percolator#distributed-transactions#bigtable#tidb#snapshot-isolation#mvcc

目录

你在运营一个搜索引擎。全网有万亿级别的网页，你需要维护一份倒排索引（inverted index）。一种做法是 MapReduce 全量重建——把整个网页库扫一遍，从头生成索引。这确实能保证一致性，但问题是：全量重建一次需要几天，而在这几天里，新抓取的网页无法被检索到。

换一种做法：增量更新。每次只处理新抓取到的网页，更新受影响的索引条目。这要快得多，但引入了一个棘手的问题——一个网页的变更可能影响多个索引条目（多个关键词的倒排列表），你需要保证这些条目要么全部更新，要么都不更新。否则，索引会处于不一致状态：某些关键词能搜到这个网页，另一些搜不到。

这就是分布式事务（distributed transaction）的需求：跨越多行、多机器的原子更新。

Google 的 Bigtable 不提供跨行事务。它只保证单行操作的原子性。2010 年，Google 发表了 Percolator 论文，描述了如何在 Bigtable 之上构建一个支持快照隔离（Snapshot Isolation）的跨行事务系统。这个系统不是一个通用数据库——它是一个增量处理框架（incremental processing framework），专门用来解决上述的索引更新问题。事务功能是手段，不是目的。

Percolator 的设计思路有一个核心洞察：把事务的协调状态编码到数据本身中。 传统两阶段提交（2PC）依赖一个专用的协调者（coordinator）节点来记录事务状态。如果协调者挂了，事务的命运就不确定了——参与者不知道该提交还是回滚。Percolator 把”事务是否已提交”这个信息写在 Bigtable 的行里，任何客户端都能读到，从而消除了对专用协调者的依赖。

这篇文章完整拆解 Percolator 的设计：三列（column）结构如何编码事务状态、两阶段提交的详细流程、冲突检测与锁清理、Go 语言简化实现、TiDB 对 Percolator 模型的工程改进，以及 Percolator 与经典 2PC 的本质区别。

一、Percolator 论文的背景与动机

Google 的索引更新问题

Google 在 2010 年发表了论文 “Large-scale Incremental Processing Using Distributed Transactions and Notifications”。论文的第一作者是 Daniel Peng，第二作者是 Frank Dabek。

论文要解决的问题很具体：Google 的网页索引（web index）需要持续更新。互联网每天都有大量网页被创建、修改、删除。搜索引擎的索引必须反映这些变化，否则用户搜到的就是过时的信息。

在 Percolator 之前，Google 用 MapReduce 来构建索引。MapReduce 是批处理（batch processing）模型——读取整个输入数据集，处理后输出完整的结果。对于网页索引来说，就是把所有已知网页扫一遍，重新生成整个倒排索引。

这个做法的问题是延迟。论文中提到的数据规模：数十 PB 的数据，分布在数千台机器上。全量 MapReduce 任务需要运行数天。一个网页从被抓取到出现在搜索结果中，延迟可能长达数天。

增量处理的核心诉求是：当一小部分输入数据发生变化时，只重新计算受影响的输出部分。对于索引来说，如果一个网页被修改了，只需要更新这个网页相关的倒排列表，而不需要重建整个索引。

为什么 Bigtable 不够用

Bigtable 是 Google 的分布式存储系统，提供了一个按行键（row key）排序的键值存储（sorted key-value store）。每一行可以有多个列族（column family），每个列下面可以存多个版本（version），用时间戳（timestamp）区分。

Bigtable 的关键特性是单行原子性：对同一行的读-修改-写（read-modify-write）操作是原子的。但 Bigtable 不提供跨行事务——你无法原子地修改两行数据。

对于索引更新来说，这是不够的。考虑一个具体场景：

网页 P 的标题从 "分布式系统入门" 变为 "分布式事务入门"

需要的原子操作：
1. 从关键词 "系统" 的倒排列表中删除 P
2. 向关键词 "事务" 的倒排列表中添加 P
3. 更新网页 P 的元数据记录

这三个操作涉及三个不同的行（三个不同的 row key）。
如果只完成了操作 1 和 3，但操作 2 失败了，
搜索 "事务" 找不到 P，搜索 "系统" 也找不到 P——网页 P 从索引中"消失"了。

这就是 Percolator 要解决的问题：在 Bigtable 之上构建跨行事务。

关键设计约束

Percolator 的设计有几个重要约束，理解这些约束才能理解它为什么长成这样：

第一，必须建立在 Bigtable 之上。 Google 已经在 Bigtable 上投入了巨大的基础设施。Percolator 不能要求替换存储层，只能在现有的 Bigtable API 上做文章。这意味着 Percolator 只能利用 Bigtable 提供的原语：单行原子读写、列族、多版本时间戳。

第二，规模优先，延迟其次。 Percolator 处理的是后台的增量索引任务，不是在线 OLTP 请求。单个事务的延迟可以在数十毫秒的量级，但系统必须能处理数十 PB 的数据规模。

第三，事务冲突率低。 在索引更新场景中，大部分网页的更新是独立的——两个不同网页的索引条目很少冲突。这意味着乐观并发控制（Optimistic Concurrency Control，OCC）是合理的选择：先假设没有冲突，提交时再检查。如果冲突率高，乐观方案会导致大量回滚，性能反而不好。

第四，Percolator 不是通用数据库。 它不提供 SQL 接口，不支持交互式事务（用户在事务中间做决策），不支持跨表查询。它是一个编程框架，开发者用它来编写增量处理逻辑——每个处理逻辑是一个 Observer，当某些数据发生变化时被触发执行。

论文中 Percolator 的吞吐量约为 MapReduce 的 1/30，但索引更新的平均延迟从数天缩短到了数十分钟。这个权衡对 Google 的索引更新场景是值得的——搜索结果的时效性远比处理吞吐量重要。

二、Bigtable 上的事务：三列设计

Percolator 的核心思想是利用 Bigtable 的多版本机制和列族机制，在每一行上附加额外的元数据列，用来跟踪事务状态。具体来说，Percolator 为每一行维护三个列族：data、lock、write。

Bigtable 的版本机制

先回顾 Bigtable 的版本模型。Bigtable 中，每个单元格（cell）由三部分定位：(row_key, column, timestamp)。同一个 (row_key, column) 下可以存在多个版本，每个版本由一个时间戳标识。读取时可以指定读取某个时间戳的版本，或者读取最新版本。

Percolator 用这个多版本机制来实现多版本并发控制（Multi-Version Concurrency Control，MVCC）。每个事务有一个开始时间戳（start_ts）和一个提交时间戳（commit_ts），事务只能看到 start_ts 之前已经提交的数据版本。

三个列族的角色

data 列：存储实际的数据值。 每个版本用 start_ts 作为时间戳。当事务在 Prewrite 阶段写入数据时，它把新值写到 data 列的 start_ts 版本下。注意，此时数据已经写入了，但事务还没提交——这个值对其他事务来说暂时不可见，因为还没有对应的 write 记录。

data 列内容示例：
  timestamp=7 → "bal=3"    （事务 T1 在 Prewrite 阶段写入）
  timestamp=5 → "bal=10"   （更早的事务写入的已提交值）

lock 列：存储锁信息。 当事务在 Prewrite 阶段锁定某行时，它在 lock 列写入一条记录，时间戳为 start_ts。锁的内容包含一个指向主键（primary key）的引用。如果当前行本身就是主键，锁的内容标记为 “primary”。

lock 列内容示例：
  timestamp=7 → "primary"         （这行是主键）
  timestamp=7 → "→Bob.bal"        （这行是副键，主键是 Bob.bal）

锁的存在意味着有一个事务正在修改这行数据，但还没决定是否提交。其他事务遇到这个锁时，需要等待或者尝试清理（如果锁持有者已经死了）。

write 列：存储提交记录。 当事务提交时，它在 write 列写入一条记录，时间戳为 commit_ts，内容是 start_ts。这条记录的含义是：“在 commit_ts 这个时间点，有一个起始于 start_ts 的事务提交了数据。你要读实际的值，去 data 列的 start_ts 版本找。”

write 列内容示例：
  timestamp=8 → "data@7"     （commit_ts=8 的提交指向 data 列 ts=7 的版本）
  timestamp=6 → "data@5"     （更早的提交记录）

为什么三列是必要且充分的

三列的设计看起来有些冗余——为什么不直接在 data 列里加个标志位表示”已提交”？

原因在于原子提交点（atomic commit point）的需求。一个分布式事务涉及多行数据，但 Bigtable 只保证单行原子性。Percolator 需要一种方式来表达”整个事务已经提交”这个全局状态，而且这个状态的变更必须是原子的。

三列的设计把这个问题解决了：

  1. Prewrite 阶段写入 data 和 lock——这是试探性的，事务还没提交。
  2. Commit 阶段对主键的操作是：删除 lock + 写入 write——这是一次单行操作，Bigtable 保证其原子性。这一步就是整个事务的原子提交点。
  3. 其他事务在读取数据时，通过检查 write 列来判断哪些 data 版本是已提交的。

如果只有 data 和 write 两列，没有 lock 列，就无法实现 Prewrite 阶段的冲突检测——你不知道某个未提交的 data 版本是被哪个事务写入的，也无法判断那个事务是否还活着。

如果只有 data 和 lock 两列，没有 write 列，就无法高效地实现快照读——你不知道某个 data 版本是否已经被成功提交，需要检查锁是否已经被清理，这会使读路径变得复杂且低效。

列的视觉化展示

下图展示了一个转账事务（Bob 向 Joe 转 7 元）在执行过程中，三个列族的状态变化：

Percolator 三列设计：事务生命周期

在事务开始前（阶段 ①），Bob 的余额为 10，Joe 的余额为 0，这些值都已经提交，write 列中有对应的提交记录。Prewrite 后（阶段 ②），新的数据值已经写入 data 列（Bob 的新余额 3，Joe 的新余额 7），同时 lock 列写入了锁——Bob 行标记为 primary，Joe 行的锁指向 Bob 行。Primary Commit 后（阶段 ③），Bob 行的锁被删除，write 列写入提交记录，此时事务已经不可撤销地提交了，但 Joe 行的锁还在。Secondary Commit 后（阶段 ④），Joe 行的锁也被清理，所有数据对外完全可见。

start_ts 与 commit_ts 的关系

每个事务有两个关键时间戳：

时间戳预言机是一个集中式服务，负责生成全局严格单调递增的时间戳。这是 Percolator 的一个已知瓶颈——所有事务都需要联系 TSO 获取时间戳。但在 Google 的场景中，这个瓶颈是可以接受的，因为 TSO 的负载基本上只是一个计数器的递增操作，单机每秒可以生成数百万个时间戳。

三、两阶段提交流程详解

Percolator 的事务提交分为两个阶段：Prewrite 和 Commit。这和经典 2PC 的 Prepare/Commit 结构类似，但实现机制完全不同。

Prewrite 阶段

Prewrite 阶段的目标是：锁定所有要修改的键，写入新的数据值，检查是否有冲突。

事务开始时，客户端从 TSO 获取 start_ts。然后在本地缓冲所有的写操作，直到事务准备提交。Prewrite 阶段，客户端把缓冲区里的写操作逐一发送到对应的 Bigtable 行。

步骤如下：

第一步：选定主键。 从事务涉及的所有键中选一个作为主键（primary key），其余的是副键（secondary key）。主键的选择是任意的，但主键在 Commit 阶段有特殊角色——主键的提交是整个事务的原子提交点。

第二步：对每个键执行 Prewrite 操作。 先处理主键，再处理副键。对每个键执行以下步骤（这是一次 Bigtable 单行事务）：

Prewrite(key, value, start_ts, primary_key):
  1. 冲突检测 — 写写冲突：
     检查 write 列，是否存在 timestamp > start_ts 的记录。
     如果存在，说明在本事务开始之后，已经有其他事务修改并提交了这个键。
     → 中止事务（write-write conflict）

  2. 冲突检测 — 锁冲突：
     检查 lock 列，是否存在任何时间戳的锁记录。
     如果存在，说明有其他事务正在修改这个键（还未提交或中止）。
     → 中止事务（或者等待/尝试清理，取决于实现策略）

  3. 写入数据：
     在 data 列写入 (start_ts → value)

  4. 写入锁：
     在 lock 列写入 (start_ts → primary_key 的引用)
     如果当前键就是 primary，内容标记为 "primary"

如果任何一个键的 Prewrite 失败（检测到冲突），整个事务中止。客户端需要清理已经 Prewrite 成功的键上的锁和数据。

为什么先 Prewrite 主键？因为主键的锁是”事务存活”的标志。如果主键的 Prewrite 失败，事务一定失败，不需要继续处理副键。

Commit 阶段

Prewrite 全部成功后，事务进入 Commit 阶段。

第一步：获取 commit_ts。 从 TSO 获取一个新的时间戳作为 commit_ts。commit_ts 必须大于 start_ts。

第二步：提交主键。 这是整个事务中最关键的一步。对主键执行以下操作（一次 Bigtable 单行事务）：

Commit_Primary(primary_key, start_ts, commit_ts):
  1. 检查 lock 列在 start_ts 是否还存在属于本事务的锁。
     如果锁不存在（被其他事务清理了），→ 事务失败。

  2. 在 write 列写入 (commit_ts → start_ts)
     这条记录告诉读者："commit_ts 时刻提交了一个写操作，数据在 data 列的 start_ts 版本"。

  3. 删除 lock 列在 start_ts 的锁记录。

  步骤 2 和 3 在同一个 Bigtable 单行事务中执行，是原子的。

这一步是整个分布式事务的原子提交点。 一旦主键的 write 记录写入成功且锁被删除，事务就被视为已提交——即使副键上的锁还没清理。

第三步：提交副键。 对每个副键执行类似操作：写入 write 记录，删除锁。这些操作可以异步执行，甚至可以在后台慢慢做。因为事务的提交状态已经由主键决定了，副键的提交只是”收尾工作”。

Commit_Secondary(secondary_key, start_ts, commit_ts):
  1. 在 write 列写入 (commit_ts → start_ts)
  2. 删除 lock 列在 start_ts 的锁记录

如果客户端在提交副键的过程中崩溃了呢？没关系。副键上残留的锁会被后续访问这些键的其他事务发现并清理（roll forward），我们在下一节详细讨论这个机制。

原子提交点的精妙之处

经典 2PC 的原子提交点是”协调者在自己的日志中写下 commit 决定”。这个决定存储在协调者自己的持久化存储中。如果协调者挂了，其他节点在协调者恢复之前无法确定事务的状态。

Percolator 的原子提交点是”主键行上的 Bigtable 单行事务：写入 write 记录 + 删除 lock”。这个状态存储在 Bigtable 中——一个高可用、持久化的分布式存储系统。任何客户端都可以读取主键行来判断事务的状态：

这就是 Percolator 消除专用协调者的关键：事务状态被编码在数据中，可以被任何参与者读取。

快照读（Snapshot Read）

读操作同样依赖三列结构。当事务以 start_ts 读取某个键时：

Get(key, start_ts):
  1. 检查 lock 列，是否存在 timestamp <= start_ts 的锁。
     如果存在，说明有一个更早的事务正在修改这个键，但还没提交。
     等待该锁被清理（或在超时后尝试清理）。

  2. 在 write 列中找到 timestamp <= start_ts 的最新记录。
     假设找到的记录是 (commit_ts=6 → start_ts=5)。

  3. 根据 write 记录中的 start_ts（本例为 5），
     到 data 列中读取 timestamp=5 的版本。

  4. 返回该值。

这就是快照隔离的实现：每个事务只看到 start_ts 之前已提交的数据。write 列中 commit_ts > start_ts 的记录对本事务不可见。

完整事务生命周期

下图展示了一个写事务（Client）和一个读事务（Reader）的完整交互时序，覆盖 Prewrite、Commit 和 Snapshot Read 三个阶段：

sequenceDiagram
    participant Client
    participant TSO
    participant Bigtable
    participant Reader

    rect rgb(220, 235, 250)
    Note over Client, Bigtable: Prewrite 阶段
    Client->>TSO: get start_ts
    TSO-->>Client: start_ts = 5
    Client->>Bigtable: prewrite key1（primary）<br/>写 data@5 + lock@5
    Bigtable-->>Client: ok
    Client->>Bigtable: prewrite key2（secondary）<br/>写 data@5 + lock@5（指向 primary=key1）
    Bigtable-->>Client: ok
    end

    rect rgb(220, 250, 220)
    Note over Client, Bigtable: Commit 阶段
    Client->>TSO: get commit_ts
    TSO-->>Client: commit_ts = 10
    Client->>Bigtable: commit primary key1<br/>写 write@10→5 + 删除 lock@5
    Bigtable-->>Client: ok
    Note right of Client: 原子提交点完成
    Client->>Bigtable: commit secondary key2<br/>写 write@10→5 + 删除 lock@5
    Bigtable-->>Client: ok
    end

    rect rgb(250, 240, 220)
    Note over Reader, Bigtable: Snapshot Read
    Reader->>TSO: get start_ts
    TSO-->>Reader: start_ts = 12
    Reader->>Bigtable: 读取 key1：检查 lock（无 ts<=12 的锁）
    Bigtable-->>Reader: 无锁
    Reader->>Bigtable: 读取 key1：查找 write 列 ts<=12 的最新记录
    Bigtable-->>Reader: write@10→5
    Reader->>Bigtable: 读取 key1：读取 data@5
    Bigtable-->>Reader: 返回值
    end

该时序图清晰地呈现了 Percolator 事务的三个核心阶段。Prewrite 阶段先写主键再写副键，每次写入同时创建 data 和 lock 两条记录；Commit 阶段先提交主键（这是原子提交点），再提交副键，每次提交写入 write 记录并删除对应的 lock。Snapshot Read 遵循”检查锁 - 查找 write - 读取 data”的三步流程，保证读事务只能看到 start_ts 之前已提交的版本。

四、冲突检测与锁清理

写写冲突检测

Percolator 实现的是快照隔离（Snapshot Isolation，SI），而不是可串行化（Serializability）。快照隔离只阻止写写冲突（write-write conflict）——如果两个并发事务修改了同一个键，只有先提交的那个成功，后提交的那个被中止。

冲突检测发生在 Prewrite 阶段。对每个要写入的键，检查 write 列中是否存在 timestamp > start_ts 的提交记录。如果存在，说明在本事务的快照之后，已经有其他事务修改并提交了这个键。这构成写写冲突，当前事务必须中止。

注意一个微妙的点：这个检查只检查 write 列，不检查 data 列。因为 data 列中可能存在其他事务 Prewrite 但尚未提交的数据，这些数据不构成冲突——那个事务可能最终会被中止。真正构成冲突的是已经提交的写入。

快照隔离不阻止写偏斜（write skew）异常。例如两个事务 T1 和 T2，T1 读 x 写 y，T2 读 y 写 x，两个事务修改的键不同，不会触发写写冲突检测，但可能导致不一致的结果。如果需要防止写偏斜，应用层必须使用显式的 SELECT FOR UPDATE 或其他机制（TiDB 的悲观锁模式可以解决这个问题）。

锁冲突与锁清理

当一个事务在 Prewrite 阶段遇到另一个事务的锁时，它不能简单地等待——因为持有锁的事务可能已经崩溃了。如果无条件等待，就可能死锁或永久阻塞。

Percolator 的锁清理机制基于以下推理链：

情况一：检查主键的状态。 副键上的锁包含一个指向主键的引用。通过读取主键行的状态，可以判断原事务的命运：

遇到副键上的锁 (start_ts=T, primary=P):
  
  读取主键 P 在时间戳 T 的状态：

  Case A: P 的 lock 列在 T 没有锁，但 write 列有 commit 记录
    → 原事务已经提交（主键已经 commit，但副键的 commit 还没完成）
    → Roll forward（前滚）：为这个副键写入 write 记录，删除锁

  Case B: P 的 lock 列在 T 没有锁，write 列也没有 commit 记录
    → 原事务已经被中止（主键的锁被清理了，但没有 commit）
    → 清理这个副键的锁和 data

  Case C: P 的 lock 列在 T 有锁，且锁未超时
    → 原事务可能还在运行中
    → 等待或退避（backoff）

  Case D: P 的 lock 列在 T 有锁，但锁已超时（TTL expired）
    → 原事务的执行者可能已经崩溃
    → 清理主键的锁，然后清理这个副键的锁

情况二：遇到主键上的锁。 如果一个事务在 Prewrite 阶段遇到的锁就是另一个事务的主键锁，处理逻辑类似但更简单——因为主键锁的状态直接反映了事务的状态。如果锁未超时，等待；如果已超时，清理。

TTL 机制

每个锁都有一个存活时间（Time-To-Live，TTL）。锁的创建者（事务的执行者）在写入锁时设置 TTL。如果在 TTL 到期后锁还没有被清理（即事务还没有提交或中止），其他事务可以安全地认为锁的持有者已经崩溃，并强制清理锁。

TTL 的设置需要权衡：

实践中，TTL 通常设置为几秒到几十秒，并且可以被锁的持有者通过心跳（heartbeat）机制续期。TiDB 的实现中，事务在运行过程中会定期更新锁的 TTL（通过更新主键锁的 min_commit_ts 字段），防止长事务被误清理。

锁的生命周期状态机

下图描述了 Percolator 中锁从创建到消亡的所有可能路径：

stateDiagram-v2
    [*] --> NoLock: 初始状态

    NoLock --> Locked: Prewrite 成功<br/>写入 lock 列 + data 列

    Locked --> Committed: 持有者执行 Commit<br/>删除 lock + 写入 write
    Locked --> RolledBack: 持有者主动 Abort<br/>清理 lock + data
    Locked --> CleanedByOther: TTL 过期<br/>其他事务强制清理 lock + data

    Committed --> [*]
    RolledBack --> [*]
    CleanedByOther --> [*]

    note right of Locked
        锁持有者可通过心跳续期 TTL，
        防止慢事务被误判为崩溃。
    end note

    note right of CleanedByOther
        清理前必须检查主键状态：
        主键已提交则前滚（roll forward），
        主键未提交则回滚（rollback）。
    end note

这个状态机展示了锁的四种终态路径。正常情况下，锁由持有者自己提交（Committed）或主动回滚（RolledBack）；异常情况下，如果持有者崩溃且 TTL 过期，其他事务会介入清理（CleanedByOther）。值得注意的是，CleanedByOther 的清理操作并非简单删除——清理者必须先检查主键的 write 列来判断原事务是否已在主键上完成提交，据此决定是前滚还是回滚。

崩溃时刻的边界条件分析

Percolator 的容错设计需要处理事务执行者在不同阶段崩溃的情况。以下逐一分析各种边界条件。

场景一：Prewrite 完成后、Commit 之前崩溃

假设事务 T1（start_ts=5）要修改 key A（主键）和 key B（副键）。T1 完成了 Prewrite 阶段后崩溃：

T1 崩溃前的状态：
  key A (primary):  data@5 = valueA,  lock@5 = {primary: A, ttl: 30s}
  key B (secondary): data@5 = valueB,  lock@5 = {primary: A, ttl: 30s}
  write 列：无新记录（Commit 未执行）

此时 key A 和 key B 上都留有锁，但由于主键 A 的 write 列没有 commit_ts=5 的提交记录，任何检查者都可以确定 T1 未提交。当锁的 TTL 过期后，其他事务可以安全回滚 T1：清理 lock 列和 data 列中 timestamp=5 的记录。

场景二：事务 T2 遭遇 T1 的残留锁

接上例，事务 T2（start_ts=20）想写入 key B。T2 在 Prewrite 阶段检查 key B 时发现 T1 的锁：

T2 的锁解析过程：
  1. T2 读取 key B 的 lock 列，发现 lock@5 = {primary: A, ttl: 30s}
  2. T2 检查当前时间是否超过锁的 TTL
     - 如果 TTL 未过期：T2 退避等待（backoff），稍后重试
     - 如果 TTL 已过期：进入步骤 3
  3. T2 读取主键 A 的状态：
     a. 检查 A 的 write 列是否有 start_ts=5 的提交记录
        → 没有（T1 未提交）
     b. 检查 A 的 lock@5 是否存在
        → 存在（T1 的主键锁还在）
  4. T2 清理主键 A 的 lock@5 和 data@5（回滚 T1 的主键）
  5. T2 清理副键 B 的 lock@5 和 data@5（回滚 T1 的副键）
  6. T2 现在可以安全地对 key B 执行自己的 Prewrite

整个过程中，T2 通过读取 Bigtable 中的数据来判断 T1 的命运，无需联系任何协调者节点。

场景三：主键已提交、副键未提交时崩溃（前滚）

这是最微妙的边界条件。假设事务 T3（start_ts=30, commit_ts=35）修改 key C（主键）和 key D（副键）。T3 成功提交了主键 C，但在提交副键 D 之前崩溃：

T3 崩溃后的状态：
  key C (primary):  data@30 = valueC,  write@35 = {start_ts: 30}
                    lock@30 已被删除（Commit 时清理）
  key D (secondary): data@30 = valueD,  lock@30 = {primary: C, ttl: 30s}
                     write 列无新记录

此时事务 T3 实际上已经提交——因为主键 C 的 write 列已经有了提交记录。副键 D 上残留的锁是一个”过时”的锁。当事务 T4 遇到 key D 上的锁时：

T4 的前滚过程：
  1. T4 读取 key D 的 lock@30，得到 primary=C
  2. T4 读取主键 C 的 write 列，发现 write@35 = {start_ts: 30}
     → T3 已经提交！
  3. T4 执行前滚（roll forward）：
     为 key D 写入 write@35 = {start_ts: 30}，删除 lock@30
  4. key D 的状态与正常提交完全一致

这就是 Percolator 的优雅之处：前滚操作使副键达到了与正常提交完全相同的最终状态，不会丢失任何已提交的数据。这也解释了为什么 Percolator 要求所有副键的锁都指向主键——主键的状态是判断事务命运的唯一权威来源。

时间戳预言机（TSO）

时间戳预言机是 Percolator 的核心组件之一。它提供一个全局严格单调递增的时间戳序列。每个事务需要两次访问 TSO：

  1. 事务开始时获取 start_ts
  2. 事务提交时获取 commit_ts

TSO 的实现相对简单——本质上是一个计数器。为了容错，计数器的值需要持久化（或者使用 lease 机制确保恢复后不会回退）。Google 内部的 TSO 实现细节论文没有详细公开，但 TiDB 的 PD（Placement Driver）中的 TSO 实现是开源的，采用的是 etcd lease + 批量分配的方案。

TSO 是一个潜在的性能瓶颈和单点故障：

垃圾回收

随着时间的推移，data 列和 write 列会积累大量的历史版本。Percolator 需要一个垃圾回收（Garbage Collection，GC）机制来清理不再需要的旧版本。

GC 的基本策略：选定一个 safe point（安全时间点），保证所有活跃事务的 start_ts 都大于这个 safe point。然后清理 safe point 之前的旧版本——只保留每个键在 safe point 之前的最新已提交版本，删除更旧的版本。

GC 规则：
  对于每个键 K：
    找到 write 列中 commit_ts <= safe_point 的所有记录
    保留其中 commit_ts 最大的那条（及其对应的 data 版本）
    删除其余的 write 记录和对应的 data 版本
    删除任何 commit_ts <= safe_point 且没有对应 write 记录的 data 版本（已中止事务的残留）

TiDB 中的 GC 由一个专门的 GC Worker 后台进程执行，通过 PD 协调 safe point 的推进。

五、Go 语言简化实现

下面是 Percolator 事务逻辑的简化 Go 实现。这段代码展示了核心算法，使用了一个简化的存储接口来抽象 Bigtable 操作。

package percolator

import (
    "errors"
    "fmt"
)

// 简化的存储接口，对应 Bigtable 的单行原子操作
type Storage interface {
    // 在指定列写入一个版本
    Put(row, col string, ts uint64, val []byte) error
    // 读取指定列中 ts <= maxTS 的最新版本
    Get(row, col string, maxTS uint64) (val []byte, ts uint64, ok bool)
    // 删除指定列的某个版本
    Delete(row, col string, ts uint64) error
    // 检查指定列中是否存在 ts 在 [minTS, maxTS] 范围内的记录
    HasAnyInRange(row, col string, minTS, maxTS uint64) bool
}

// Write 表示事务中的一次写操作
type Write struct {
    Row string
    Val []byte
}

// Transaction 表示一个 Percolator 事务
type Transaction struct {
    store   Storage
    startTS uint64
    writes  []Write
}

// NewTransaction 创建一个新事务，startTS 从 TSO 获取
func NewTransaction(store Storage, startTS uint64) *Transaction {
    return &Transaction{
        store:   store,
        startTS: startTS,
        writes:  nil,
    }
}

// Set 缓冲一次写操作（事务提交前不实际写入存储）
func (txn *Transaction) Set(row string, val []byte) {
    txn.writes = append(txn.writes, Write{Row: row, Val: val})
}

// Get 执行快照读：读取 startTS 时刻的已提交值
func (txn *Transaction) Get(row string) ([]byte, error) {
    // 1. 检查是否有 ts <= startTS 的锁（说明有未提交事务）
    if _, _, ok := txn.store.Get(row, "lock", txn.startTS); ok {
        // 简化处理：实际实现中应尝试清理或等待
        return nil, fmt.Errorf("row %s is locked by another transaction", row)
    }

    // 2. 在 write 列找到 ts <= startTS 的最新提交记录
    writeVal, _, ok := txn.store.Get(row, "write", txn.startTS)
    if !ok {
        return nil, nil // 该行不存在或从未被写入
    }

    // 3. 解析 write 记录中的 startTS，到 data 列读取实际值
    dataTS := decodeWriteRecord(writeVal)
    dataVal, _, ok := txn.store.Get(row, "data", dataTS)
    if !ok {
        return nil, fmt.Errorf("data missing for row %s at ts %d", row, dataTS)
    }
    return dataVal, nil
}

// Prewrite 对所有缓冲的写操作执行 Prewrite
// primaryRow 是主键行（通常选 writes[0].Row）
func (txn *Transaction) Prewrite(primaryRow string) error {
    for _, w := range txn.writes {
        if err := txn.prewriteRow(w.Row, w.Val, primaryRow); err != nil {
            return fmt.Errorf("prewrite failed on row %s: %w", w.Row, err)
        }
    }
    return nil
}

func (txn *Transaction) prewriteRow(row string, val []byte, primaryRow string) error {
    // 冲突检测 1：检查 write 列中 ts > startTS 的记录（写写冲突）
    if txn.store.HasAnyInRange(row, "write", txn.startTS+1, ^uint64(0)) {
        return errors.New("write-write conflict: newer commit exists")
    }

    // 冲突检测 2：检查 lock 列中是否存在任何锁
    if _, _, ok := txn.store.Get(row, "lock", ^uint64(0)); ok {
        return errors.New("lock conflict: another transaction holds a lock")
    }

    // 写入 data 列
    if err := txn.store.Put(row, "data", txn.startTS, val); err != nil {
        return err
    }

    // 写入 lock 列
    lockVal := encodeLockRecord(primaryRow)
    if err := txn.store.Put(row, "lock", txn.startTS, lockVal); err != nil {
        return err
    }
    return nil
}

// Commit 提交事务，commitTS 从 TSO 获取
func (txn *Transaction) Commit(commitTS uint64) error {
    if len(txn.writes) == 0 {
        return nil
    }
    primaryRow := txn.writes[0].Row

    // 第一步：提交主键（原子提交点）
    if err := txn.commitPrimary(primaryRow, commitTS); err != nil {
        return fmt.Errorf("primary commit failed: %w", err)
    }

    // 第二步：提交副键（可以异步执行，失败可容忍）
    for _, w := range txn.writes[1:] {
        // 副键提交失败不影响事务结果，后续读者会 roll forward
        _ = txn.commitSecondary(w.Row, commitTS)
    }
    return nil
}

func (txn *Transaction) commitPrimary(row string, commitTS uint64) error {
    // 检查主键锁是否还在（可能被其他事务清理了）
    lockVal, _, ok := txn.store.Get(row, "lock", txn.startTS)
    if !ok {
        return errors.New("primary lock missing, transaction aborted by another")
    }
    // 确认锁属于本事务
    if decodeWriteRecord(lockVal) != 0 {
        // 简化：实际实现需验证锁确实是自己的
    }

    // 原子操作：写入 write 记录 + 删除 lock
    writeVal := encodeWriteRecord(txn.startTS)
    if err := txn.store.Put(row, "write", commitTS, writeVal); err != nil {
        return err
    }
    if err := txn.store.Delete(row, "lock", txn.startTS); err != nil {
        return err
    }
    return nil
}

func (txn *Transaction) commitSecondary(row string, commitTS uint64) error {
    writeVal := encodeWriteRecord(txn.startTS)
    if err := txn.store.Put(row, "write", commitTS, writeVal); err != nil {
        return err
    }
    return txn.store.Delete(row, "lock", txn.startTS)
}

// --- 辅助函数 ---

// encodeWriteRecord 编码 write 列记录：commit_ts → start_ts 的映射
func encodeWriteRecord(startTS uint64) []byte {
    buf := make([]byte, 8)
    for i := 7; i >= 0; i-- {
        buf[i] = byte(startTS & 0xff)
        startTS >>= 8
    }
    return buf
}

// decodeWriteRecord 解码 write 列记录，获取 start_ts
func decodeWriteRecord(data []byte) uint64 {
    var ts uint64
    for _, b := range data {
        ts = (ts << 8) | uint64(b)
    }
    return ts
}

// encodeLockRecord 编码 lock 列记录：指向 primary key 的引用
func encodeLockRecord(primaryRow string) []byte {
    return []byte(primaryRow)
}

这段代码约 140 行，展示了 Percolator 事务的三个核心操作：

  1. Get：快照读。先查 lock 列确认没有未提交事务阻塞，再查 write 列找到最新的已提交版本，最后从 data 列读取实际值。
  2. Prewrite：对每个键检测写写冲突和锁冲突，然后写入数据和锁。
  3. Commit：先提交主键（原子提交点），再异步提交副键。

一个典型的使用流程：

// 使用示例：Bob 向 Joe 转账 7 元
func Transfer(store Storage, tso TSO) error {
    startTS := tso.GetTimestamp()
    txn := NewTransaction(store, startTS)

    // 读取当前余额
    bobBal, err := txn.Get("Bob.bal")
    if err != nil {
        return err
    }
    joeBal, err := txn.Get("Joe.bal")
    if err != nil {
        return err
    }

    // 计算新余额
    bobAmount := decodeAmount(bobBal) - 7
    joeAmount := decodeAmount(joeBal) + 7

    // 缓冲写操作
    txn.Set("Bob.bal", encodeAmount(bobAmount))
    txn.Set("Joe.bal", encodeAmount(joeAmount))

    // Prewrite（主键选择 Bob.bal）
    if err := txn.Prewrite("Bob.bal"); err != nil {
        return err // 事务中止
    }

    // Commit
    commitTS := tso.GetTimestamp()
    return txn.Commit(commitTS)
}

需要强调的是，上述 Go 代码是简化版本，省略了以下生产环境必需的逻辑：

六、TiDB 的 Percolator 实现分析

TiDB 是目前最知名的 Percolator 模型的工程实现。TiDB 是一个兼容 MySQL 协议的分布式数据库，其存储引擎 TiKV 使用 Percolator 的事务模型来实现分布式事务。理解 TiDB 的实现，可以看到 Percolator 从论文到生产之间需要跨越的工程鸿沟。

存储层的差异

Google 的 Percolator 建立在 Bigtable + GFS 之上。TiKV 建立在 RocksDB + Raft 之上。

RocksDB 是一个单机的 LSM-tree 存储引擎，提供有序键值存储。TiKV 在 RocksDB 之上实现了 Percolator 的三列结构，使用三个 Column Family（CF）来对应 Percolator 的三列：

Percolator 列 TiKV CF 说明
data CF_DEFAULT 存储实际数据值，key 编码为 {user_key}{start_ts}
lock CF_LOCK 存储锁信息，key 编码为 {user_key}
write CF_WRITE 存储提交记录，key 编码为 {user_key}{commit_ts}

注意 TiKV 中 lock 列的 key 不包含时间戳——因为同一个键在同一时刻最多只能有一把锁（多把锁意味着冲突），所以不需要时间戳来区分版本。

Raft 用于数据复制。TiKV 把数据分成多个 Region（类似于分片），每个 Region 是一个 Raft 组。Percolator 的每一步操作（Prewrite、Commit）都需要通过 Raft 复制到多数副本后才算成功。这意味着 Percolator 的每一步操作的延迟至少包含一次 Raft 提交的延迟（通常是一到两次网络往返）。

从正确性角度看，Raft 复制确保了即使单个 TiKV 节点崩溃，Percolator 的列数据也不会丢失。这相当于 Google 原始设计中 Bigtable + GFS 提供的持久性保证。

PD：TiDB 的时间戳预言机

TiDB 使用 PD（Placement Driver）组件来提供 TSO 服务。PD 是一个基于 etcd 的集中式调度器，TSO 只是其功能之一。

PD 的 TSO 实现采用了预分配策略：PD leader 启动时，向 etcd 写入一个 lease，预分配一段时间戳范围（例如 3 秒对应的逻辑时间戳数量）。在 lease 有效期内，PD 可以直接从内存中分配时间戳，不需要每次都写 etcd。当 lease 快到期时，续约并预分配新的范围。

这个设计的好处是：

  1. TSO 分配的热路径是纯内存操作，延迟极低（微秒级）。
  2. PD leader 崩溃后，新 leader 从 etcd 读取上一次的 lease 值，确保不会分配出重复或回退的时间戳。

客户端（TiDB server）也会批量获取时间戳——一次 RPC 请求获取一批时间戳，在本地分配给多个事务，减少与 PD 的交互次数。

悲观锁模式

这是 TiDB 相对于原始 Percolator 最重要的改进。

原始 Percolator 是纯乐观事务（Optimistic Transaction）——事务执行期间不加锁，所有的写操作只是缓冲在客户端内存中，提交时才检查冲突。这意味着：

  1. 如果两个事务修改了同一行，直到提交时才发现冲突，之前的所有计算都白费了。
  2. 对于冲突率高的场景（例如热点行的更新），乐观事务会导致大量回滚和重试，性能很差。
  3. MySQL 的应用开发者习惯了 SELECT FOR UPDATE（悲观锁），迁移到纯乐观模式需要修改应用代码。

TiDB 在 Percolator 的基础上增加了悲观锁模式（Pessimistic Transaction）。在悲观模式下：

乐观模式流程：
  BEGIN → 读写操作（本地缓冲）→ Prewrite → Commit

悲观模式流程：
  BEGIN → 每次写操作时立即加悲观锁 → Prewrite（将悲观锁升级为 Prewrite 锁）→ Commit

悲观锁的实现方式是在 TiKV 的 CF_LOCK 中写入一种特殊类型的锁（LockType::Pessimistic），这种锁不写入 data 列的数据。在 Prewrite 阶段，如果发现已经持有悲观锁，就直接升级为 Prewrite 锁并写入数据，不需要做冲突检测（因为加悲观锁时已经检测过了）。

悲观锁的好处：

Async Commit 优化

原始 Percolator 的 Commit 阶段有一个延迟瓶颈：必须等待主键 commit 成功后才能向客户端返回”事务已提交”。这意味着 commit 的延迟至少包含一次 Raft 写入的延迟。

TiDB 引入了 Async Commit 优化，核心思想是：在 Prewrite 阶段就确定 commit_ts，并把 commit_ts 写入所有的锁中。 这样，当所有键的 Prewrite 都成功后，事务实际上已经可以被视为已提交——因为所有需要的信息都已经持久化了。

传统 Percolator：
  Prewrite all keys → Get commit_ts → Commit primary → Return success
  延迟 = Prewrite + Commit Primary（至少 2 次 Raft 写入）

Async Commit：
  Prewrite all keys（每个锁带上 commit_ts 和 secondary key 列表）→ Return success
  后台异步：Commit primary → Commit secondaries
  延迟 = Prewrite only（1 次 Raft 写入）

Async Commit 的 commit_ts 计算稍有不同。由于 commit_ts 需要在 Prewrite 阶段就确定，它使用的是 max(所有 Prewrite 返回的 min_commit_ts) 而不是从 TSO 获取的新时间戳。这需要 TiKV 在 Prewrite 时返回一个 min_commit_ts（基于该 Region 最近的读时间戳计算），以确保快照隔离的正确性。

1PC 优化

如果一个事务的所有键都落在同一个 TiKV Region 中，TiDB 可以跳过 Prewrite 阶段，直接在一次 RPC 中完成事务——即 1PC（One Phase Commit）。

1PC 的原理：既然所有键在同一个 Raft 组中，Raft 本身就保证了原子性（Raft 日志要么全部 apply，要么都不 apply）。不需要 Percolator 的两阶段协议来在多个 Raft 组之间协调。

1PC 直接写入 data 和 write 列，跳过 lock 列。延迟只有一次 Raft 写入。

Pipelined 悲观锁

TiDB 还优化了悲观锁的加锁延迟。在标准流程中，加悲观锁需要等待 Raft 提交（确保锁持久化）。Pipelined 悲观锁允许 TiKV 在锁写入本地内存后就返回成功，不等待 Raft 提交。

这降低了加锁延迟（从 Raft 延迟降低到本地内存写入延迟），但代价是：如果 TiKV leader 在锁持久化之前崩溃，锁会丢失，事务需要重试。对于大部分场景来说，这个权衡是值得的——Raft leader 崩溃是低概率事件。

性能特征

TiDB 官方文档中给出的典型延迟数据（供参考，实际数据取决于硬件配置和网络环境）：

操作 典型延迟 瓶颈
TSO 获取 < 1ms PD leader 内存分配 + 网络 RTT
Prewrite（单 Region） 2-5ms Raft 提交（1 次 fsync + 网络 RTT）
Commit Primary 2-5ms Raft 提交
小事务端到端（乐观） 10-20ms 2 次 TSO + Prewrite + Commit
小事务端到端（Async Commit） 5-10ms 1 次 TSO + Prewrite
小事务端到端（1PC） 3-5ms 1 次 TSO + 1 次 Raft 写入

可以看到，TiDB 的优化方向是持续减少事务提交路径上的网络往返和 Raft 提交次数。从最初的 Percolator 两阶段（4 次 Raft 写入以上）到 1PC 的单次 Raft 写入，延迟降低了一个数量级。

七、Percolator 与经典 2PC 的本质区别

Percolator 本质上是一种两阶段提交协议，但它和教科书里的经典 2PC 有根本的架构差异。

经典 2PC 的架构

经典 2PC 有一个专用的协调者（coordinator）节点和多个参与者（participant）节点。协调者负责驱动事务的提交：

经典 2PC：
  阶段 1 (Prepare)：
    协调者 → 所有参与者：PREPARE
    参与者 → 协调者：YES/NO
    协调者把 PREPARE 结果记录到自己的 WAL（Write-Ahead Log）

  阶段 2 (Commit/Abort)：
    协调者决定 COMMIT 或 ABORT
    协调者把决定记录到自己的 WAL  ← 这是原子提交点
    协调者 → 所有参与者：COMMIT 或 ABORT
    参与者执行并回复 ACK

关键问题在于：协调者的 WAL 是事务状态的唯一来源。 如果协调者在写入 COMMIT 决定之后、发送 COMMIT 消息之前崩溃了，参与者们不知道事务的最终状态——它们已经投了 YES 票，锁定了资源，但不知道该提交还是回滚。这就是经典 2PC 的阻塞问题（blocking problem）。

Percolator 的架构

Percolator 没有专用的协调者节点。事务由客户端（或称 worker）驱动，但客户端不是”协调者”——因为事务状态不存储在客户端上。

Percolator：
  阶段 1 (Prewrite)：
    客户端 → Bigtable：对每个键执行 Prewrite（冲突检测 + 写 data + 写 lock）

  阶段 2 (Commit)：
    客户端 → Bigtable：提交主键（删 lock + 写 write） ← 这是原子提交点
    客户端 → Bigtable：提交副键（删 lock + 写 write） ← 可异步，可容忍失败

关键差异：原子提交点在 Bigtable 中（主键行的单行事务），不在客户端上。 客户端崩溃后，事务的状态可以通过读取主键行来确定。任何客户端或后台清理进程都可以接管未完成的事务：

这意味着 Percolator 不存在经典 2PC 的阻塞问题。事务的恢复不依赖于某个特定节点的状态——任何能访问 Bigtable 的进程都可以执行恢复。

对比表

维度 经典 2PC Percolator
协调者 专用节点，维护事务状态 无专用节点，事务状态在数据层
原子提交点 协调者 WAL 中的 COMMIT 记录 主键行的单行 Bigtable 事务
协调者崩溃 参与者阻塞，等待恢复 任何进程可接管恢复
事务恢复 只有原协调者（或其备份）能恢复 任何客户端可读取主键状态并恢复
锁粒度 参与者上的资源锁 每行的 lock 列
通信模式 协调者与参与者之间的请求-响应 客户端直接与存储层交互
隔离级别 取决于实现 快照隔离（SI）
全局时钟 通常不需要 需要 TSO（时间戳预言机）
并发控制 通常是悲观锁 乐观并发控制（原始设计）
参与者状态 In-doubt 状态，需锁定资源 锁在 Bigtable 中可被外部检查
容错代价 需要协调者高可用（如 Raft） 依赖存储层高可用（如 Bigtable/GFS）
延迟 2 次网络往返 至少 2 次 TSO 访问 + 数次存储访问

数据即协调：Percolator 的核心范式转换

Percolator 与经典 2PC 的区别不仅仅是”去掉了协调者”这么简单。它代表了一种根本性的范式转换：事务协调元数据与应用数据共存于同一个存储系统中。

在经典 2PC 中，协调者是一个独立于数据存储的实体。它在自己的 WAL 中记录事务状态（prepare、commit、abort），这份状态与参与者上的实际数据是物理分离的。协调者的 WAL 是一个”影子系统”——它不存储任何业务数据，只存储关于事务的元信息。这种分离导致了一个根本性问题：当协调者不可达时，数据层无法自行推断事务的最终状态。

Percolator 彻底消除了这种分离。lock 列、write 列和 data 列存储在同一个 Bigtable 行中。事务是否已提交、锁是否还有效、数据的哪个版本是最新的——所有这些信息都可以通过读取数据行本身来获得。数据存储就是协调存储，读取数据的能力等同于读取协调状态的能力。

这种”数据即协调”的设计带来了深刻的容错含义：

  1. 恢复能力的民主化。 在经典 2PC 中，只有协调者（或其热备）能够恢复悬挂事务。在 Percolator 中，任何能访问 Bigtable 的进程——不管是原始的事务发起者、另一个客户端、还是后台清理线程——都具备完整的恢复能力。恢复不再是特权操作。

  2. 故障域的合并。 经典 2PC 的正确性依赖两个独立组件的可用性：协调者和数据存储。Percolator 将故障域合并为一个：只要 Bigtable 可用，事务系统就可用。这不是消除了故障的可能性，而是将两个独立的故障源合并为一个，简化了运维模型。

  3. 状态的可审计性。 由于事务协调状态就在数据中，运维人员可以直接扫描 Bigtable 的 lock 列来发现所有悬挂事务——不需要连接到某个协调者节点去查询它的内部状态。这种透明性在大规模生产环境中极为重要。

这种范式的代价是性能开销：每次事务操作都需要额外的列读写，而经典 2PC 的协调者可以将事务状态维护在内存中。但在 Google 的场景下——万亿级网页的增量索引更新——容错性和运维简单性的优先级远高于单事务延迟。

Percolator 的权衡

Percolator 不是对经典 2PC 的”全面改进”，它是在特定约束下的设计选择：

牺牲了什么： - 延迟：每个事务需要多次访问 TSO 和 Bigtable，延迟高于中心化协调者直接发消息。 - 隔离级别：只提供快照隔离，不是可串行化。可串行化需要额外的机制（如 TiDB 的悲观锁模式可以接近但不完全等同于可串行化）。 - TSO 依赖：引入了一个集中式的时间戳服务，虽然这个服务很轻量，但它是一个潜在的单点故障和性能瓶颈。

获得了什么： - 消除协调者单点故障：事务状态在数据层，不在任何特定节点上。 - 客户端无状态：客户端崩溃不会导致事务状态丢失。 - 利用现有基础设施：不需要构建新的存储系统，复用 Bigtable 的可靠性和可扩展性。 - 简单的恢复逻辑：事务恢复只需要读取主键状态，不需要复杂的日志回放。

Snapshot Isolation 的局限

Percolator 提供的是快照隔离，而不是可串行化。快照隔离存在以下已知的异常现象：

写偏斜（Write Skew）：两个事务 T1、T2 各自读了对方要修改的键，然后各自写了不同的键。两个事务都能成功提交，但结果可能违反应用层的约束。

初始状态：x = 1, y = 1
约束：x + y > 0

T1: read(x)=1, read(y)=1 → write(x = -1) → commit
T2: read(x)=1, read(y)=1 → write(y = -1) → commit

最终结果：x = -1, y = -1 → x + y = -2，违反约束
T1 和 T2 各自检查时约束成立，但组合后约束被破坏。

Percolator 不检测这种异常，因为 T1 和 T2 修改的键不同（T1 改 x，T2 改 y），不触发写写冲突检测。

在实践中，这意味着依赖 Percolator（或 TiDB 的乐观事务模式）的应用需要在设计层面避免写偏斜，或者使用 TiDB 的悲观锁模式来防止。

八、结论

Percolator 的核心贡献可以用一句话概括：把分布式事务的协调状态编码进数据本身。

这个设计的精妙在于它充分利用了已有基础设施（Bigtable 的单行原子性和多版本机制），用三个列族（data、lock、write）编码了完整的事务生命周期信息。主键的提交操作是一次 Bigtable 单行事务——这是整个分布式事务的原子提交点。任何能读取主键状态的进程都可以判断事务的结局，从而消除了对专用协调者的依赖。

但 Percolator 也有明确的局限：

  1. 时间戳预言机（TSO）是集中式瓶颈。 所有事务都需要从 TSO 获取时间戳，TSO 的吞吐量和可用性直接制约系统的事务处理能力。虽然 TSO 的操作非常轻量（本质上是一个递增计数器），但它仍然是一个需要高可用部署的关键组件。

  2. 原始设计仅支持乐观并发控制。 在冲突率高的场景下，大量事务会在 Prewrite 或 Commit 阶段被中止，导致严重的计算浪费。TiDB 通过增加悲观锁模式解决了这个问题，但这也增加了系统的复杂度。

  3. 快照隔离不等于可串行化。 写偏斜等异常在快照隔离下是合法的，应用层需要自行处理或使用额外的锁机制。

Percolator 的影响远超 Google 内部。TiDB/TiKV 直接采用了 Percolator 的事务模型，并在此基础上做了大量的工程优化（悲观锁、Async Commit、1PC）。CockroachDB 的事务模型也受到了 Percolator 的启发（虽然具体设计有显著差异，CockroachDB 使用了混合逻辑时钟而不是 TSO）。YugabyteDB 同样借鉴了 Percolator 的思路。可以说，Percolator 定义了一种在分布式键值存储上构建事务的范式。

下一篇文章将讨论 Google Spanner——另一种截然不同的分布式事务方案。Spanner 不使用集中式 TSO，而是用 TrueTime（基于原子钟和 GPS 的物理时钟方案）来生成全局一致的时间戳。Percolator 把事务状态放在数据中，Spanner 把时间的确定性放在硬件中——两种思路，两种权衡。

导航

参考资料

论文

源码

博客与文档

书籍

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-07-25 · distributed

【分布式系统实战】分布式事务不是你以为的那个 2PC

「用 2PC 就行了」——说这话的人大概没在生产环境里被 Coordinator 挂掉后全员阻塞的锁堵过三小时。2PC 的真实失败模式、Percolator 的精妙设计、Saga 与 TCC 的工程取舍，分布式事务远比教科书复杂。

2026-04-13 · distributed

【分布式系统百科】3PC 的理论改进与 Saga 的工程妥协

2PC 阻塞时协调者宕机怎么办？3PC 试图用额外一轮消息解决，却撞上网络分区。Saga 放弃全局锁，用补偿事务换取可用性。本文从 Skeen 论文推导 3PC 的非阻塞证明，分析其分区缺陷，再到 Saga 编排/协同、补偿陷阱、Temporal 工程实践和 TCC 资源预留——把分布式事务的理论与工程讲清楚。

By .