Percolator — 大规模增量处理

一句话

Percolator 在 Bigtable 之上加了两样东西——跨行跨表的 ACID 事务（快照隔离，snapshot isolation）和观察者 / 通知机制（observers / notifications）——把谷歌网页索引从「用 MapReduce 整批重建」改造成「增量处理：来一篇、只更新受影响的那一小部分」。上线后（这套系统即 Caffeine）在处理同样吞吐的前提下，把搜索结果中文档的平均年龄降低了约 50%。

Glossary · 术语表

坐标

作者 Daniel Peng 与 Frank Dabek，谷歌，论文发在 OSDI 2010。它上承谷歌「老三件套」——建在 Bigtable（存储）之上、替换掉 MapReduce（批处理）搭的索引流水线，并借助类似 Chubby（Paper 20）的轻量锁服务做故障判定；被视作谷歌「新三驾马车」之一（与 Pregel、Dremel 并列）。它把「大规模分布式事务」从学界的「不可能高效」变成了工业现实，直接启发了后来的 TiDB / TiKV 等分布式数据库——它们的事务模型几乎照搬了 Percolator。

问题与动机

谷歌的网页索引本质是一套流水线：爬到一个网页 → 抽取内容、算 PageRank、聚类去重 → 更新倒排索引。2010 年前，这套流水线是用 MapReduce 整批跑的：把当时的整个网络仓库（数十 PB）当输入，跑一连串 MapReduce，产出一整版新索引。

痛点是批处理的粒度：MapReduce 要求把输入整个扫一遍。哪怕这一轮只有极小一部分网页真的变了，你也得重新处理整个仓库——因为一个新网页可能改变别的网页的排名、聚类归属，牵一发而动全身，批处理没法「只算受影响的部分」。结果就是：一个网页从爬到、到进入线上索引，要等上一整轮全量重算（数天量级）。想更新更快，就得更频繁地全量重算，成本高到不可行。

那为什么不干脆上一个数据库、来一篇网页就发一个事务改几行？因为规模：当时没有任何 DBMS 能在几千台机器上撑住这个体量的随机读写吞吐。于是问题变成：能不能在能扛住规模的存储（Bigtable）之上，补出「只更新受影响部分」所需的两样能力——多行事务，和「谁变了通知谁」的触发机制？

核心思想 / 方法

为什么是「事务 + 通知」这两样

增量处理的本质是：维护一堆互相依赖的数据，当上游变了、把变化「渗」到下游。做这件事，你需要两样：一是多行事务——一次更新常要一致地改多处，不能改一半就崩（否则索引出烂账）；二是通知——你得知道「谁变了、接下来该唤醒哪段计算」，否则只能又回到「全扫一遍找变化」的老路。Percolator 就是把这两样，架在 Bigtable 之上。

能力一：Bigtable 上的快照隔离事务

Bigtable 只保证单行原子。Percolator 要跨行、跨表做 ACID，办法是给每个数据列额外配几个「元数据」列，把锁和版本信息直接存进 Bigtable 里，再用一个两阶段提交协议把它们串成事务。核心用到三种列：

• data（数据）：某时间戳下这个格子的实际值。Bigtable 天生按时间戳存多版本。
• lock（锁）：标记「此格有一个未提交的事务正占着」。事务里所有被写的格子中，指定一个当「主锁」（primary lock），其余是「副锁」（secondary），每个副锁记着主锁在哪。
• write（写记录 / 提交点）：一个指针，指向「已提交的那个 data 版本」的时间戳。读操作只认 write——没有 write 记录的数据，读者看不见。

每个事务从一个全局服务时间戳预言机（timestamp oracle）拿两个时间戳：开始时拿 start_ts，提交时拿 commit_ts。读，就读「时间戳 < start_ts 的最新已提交版本」——这就构成它的一致快照。写，则分两阶段：

• 预写（Prewrite）：给每个要写的格子上锁（选一个当主锁）、把新值写进 data（打上 start_ts）。上锁前先检查两件事：有没有 start_ts 之后别人已提交的 write（有 = 写写冲突，中止）；有没有别人的锁还占着（有 = 撞锁，退避重试）。
• 提交（Commit）：拿 commit_ts，先提交主锁那一格——检查主锁还在，然后原子地写下 write 记录（指向 start_ts 的数据）并抹掉主锁。这一步是整笔事务的「生效瞬间」：主锁一提交，交易就算数了。之后再从容地把各副锁逐个转成 write 记录。

妙处在「主锁当总开关」：一笔事务改了几十个格子，但它算不算数，只由「主锁那一格有没有变成 write 记录」这一个原子动作决定。若客户端在提交主锁后、清理副锁前崩溃了，副锁虽还留着，但别的事务撞见它，会顺着副锁记的地址去查主锁：主锁已提交 → 帮它把这个副锁也提交（前滚 roll-forward）；主锁还在/已回滚 → 把这个副锁清掉（回滚 roll-back）。判定客户端是否真死，用一个类似 Chubby 的轻量锁服务加超时。于是不需要一个专门的事务管理器，清理是懒惰、去中心化的，由后来的事务顺手完成。

时间戳预言机：全局排队号发放器

快照隔离要求时间戳严格递增。Percolator 用一个专门的时间戳预言机服务集中发号。它不是每来一个请求就写一次磁盘——那样太慢；而是一次性把「已分配到的最大号」批量写进稳定存储，之后在这段区间内纯内存发号，攒够一批请求一起回。靠批处理，单台机器能发到每秒约 200 万个时间戳，足以支撑整个集群。（这是个中心化组件，但状态极小、可复制，且批量分摊后不成瓶颈。）

能力二：观察者与通知——让变化自己「渗」下去

光有事务还不够增量：你还得知道「哪块数据脏了、该唤醒哪段计算」。Percolator 给列加了观察者（observer）：程序员把「哪些列被写时、该跑什么逻辑」注册好；当某列被写入，就在它的 notify（通知）列打个标记。一批常驻的 worker 进程随机扫描这些通知标记，撞见就运行对应的观察者代码——而观察者自己又会写别的列、触发下一批通知，如此级联。像 Excel 改一格、依赖它的公式格连锁重算。为防重复触发与死循环，Percolator 保证每条通知至多触发一次观察者（用 ack 确认列去重）。这套「写→通知→观察者→再写」的链条，就是「增量把变化渗遍索引」的引擎——系统名 Percolator（渗滤）由此而来。

关键结果

Percolator 落地成了谷歌的网页索引系统 Caffeine，替换掉此前基于 MapReduce 的批处理索引。论文给出的核心结论：在处理相同数量文档 / 相同吞吐的前提下，把搜索结果中文档的平均年龄降低了约 50%——也就是新鲜度翻倍。系统跑在数千台机器上、管理 PB 级数据；时间戳预言机单机可达每秒约 200 万次发号。作者也诚实给出代价：相比 MapReduce 顺序扫描的高效，Percolator 每处理一篇文档要做数十次 Bigtable 随机读写，资源效率显著更低——这是用机器换新鲜度的明确取舍。

为什么重要 / 影响

它的历史意义有两层。第一，工程上：证明了「在能扛规模的存储之上，补出跨行事务 + 增量通知」这条路走得通，让谷歌搜索获得了此前不可能的新鲜度。第二，也更深远——它把「基于时间戳 + 锁列 + 主锁 2PC」的分布式事务范式，做成了可复制的工程模板。后来的开源分布式数据库 TiKV / TiDB 几乎照搬了 Percolator 的事务模型（start_ts / commit_ts、primary lock、懒惰清理），CockroachDB 等也受其影响。可以说，今天很多「跨节点还能做事务」的系统，血脉里都有 Percolator。它也是谷歌「新三驾马车」中，把强一致事务带回大规模系统的那一篇——为两年后的 Spanner（全球一致事务）铺了路。

局限与批评

• 只有快照隔离、不是可串行化：快照隔离会有写偏斜（write skew）异常——两个事务各读一致快照、各改不同行，合起来违反了某条跨行约束却都不报冲突。对索引场景够用，但不是最强的一致性。
• 资源效率低：每篇文档几十次随机 Bigtable 操作，加上时间戳往返、锁读写，单位工作量的开销远高于 MapReduce 的顺序扫描。它是拿吞吐 / 资源换延迟与新鲜度，不适合对成本极敏感、又无需增量的批量场景。
• 单事务延迟不受保证：设计目标是高吞吐下的新鲜度，不是低延迟 OLTP。一笔事务要多次 RPC，个体延迟偏高，不适合面向用户、有严格 SLA 的在线交易。
• 时间戳预言机是中心点：虽经批量分摊与复制缓解，它仍是逻辑上的全局单点，是可扩展性与容错设计里要小心对待的一环。
• 懒惰锁清理带来阻塞：客户端崩溃后残留的锁，要等下一个撞上它的事务、结合超时才被清理；期间相关行会被挡住，最坏情况需等超时。

要点