OPED 是 (我自己发起的) One Paper Each Day 挑战, 即每天读一篇 Paper, 领域不限.

这是 OPED 挑战的第五篇, 论文为 Large-scale Incremental Processing Using Distributed Transactions and Notifications

这篇论文还是蛮复杂的, 我感觉要详细的描述实在太花时间了, 最近工作又很忙, 要是以后有机会再补坑吧. 这里就简单介绍一下核心思想.

Google 的 Web Index

Google 搜索服务为了提供全网的数据, 并且保证新鲜度, 需要尽可能快的去爬取网页信息. 在从前, Google 使用定期运行的 MapReduce 任务处理全量数据. 这个数据体量, 即使以 Google 的资源, 也需要跑好几个小时. 也就是说, 一个新的网页, 要是运气不好, 需要过好几个小时才能被搜索到. Googler 们就不乐意了, 这也太慢了啊, 说出去都不好意思, 我们需要优化! 我们需要 impact! 我们需要升职.

那么怎么优化呢? 这个思路其实很浅显, 既然全量数据处理起来这么慢, 我们就尝试增量地处理数据呗. 这篇论文就实现了这个想法.

为什么需要分布式事务

由于是增量式的, 并且为了提高吞吐量, 就会导致有多个线程并发写同一个数据 (比如有多个新的网页都指向了同一个网页, 处理这些新网页的线程都会更新被指向网页的 page rank). 为了让开发者能够更好的去理解整个开发模型, 这篇论文提出的新方法提供了分布式事务的语义.

Precolator 概述

这篇论文提出了一个新的处理 index 的引擎 Precolator (注意它只用于 index 这个具体的业务). 它主要包含了 Workers, Bigtable 这两个组件. (原论文特意将 GFS 也列出来作为一个组件, 因为是 Bigtable 的底层文件系统, 但是由于是对上层透明的, 我觉得没必要专门列出来.)

  1. Workers 主要负责监听数据的变化执行相应的操作.
  2. Bigtable 是数据存储方案.

除了以上这两个组件, Precolator 还依赖了两个轻量级的服务: TimeServer 和 LockService. TimeServer 只需要提供一个递增的时间戳即可, LockService 只是用来尽可能减少事务回滚, 不影响正确性. 因此这两个服务可以承受很高的 QPS.

怎么使用 Bigtable 实现分布式事务

这就是这篇论文的精华所在了. 众所周知, Bigtable 只提供了每一个行的原子操作, 对于跨多个行的写操作, 是没法保证事务性的. 那么怎么用 Bigtable 实现分布式事务呢?

这个实现有点复杂, 简单说来, 对于 Precolator 中的每一个 (逻辑) column, 都对应到 Bigtable 的多个 (物理) columns. 这些 column 包括:

  1. {column}-lock: 表示这个 cell 有一个未 commit 的事务在写. 它包含了主锁的位置.
  2. {column}-write: 表示这个 cell 的数据已经 commit, 保留了 commit 的时间戳.
  3. {column}-data: 表示这个 cell 实际的数据.
  4. {column}-notify: 表示这个 cell 有数据更新.
  5. {column}-ack-{worker}: 表示这个 cell 已经被 worker 处理过了.

上面的描述提到了两个概念一个是 cell, 一个是主锁. Cell 很容易理解, 它就是 Precolator / Bigtable 中 (row, column, version) 对应到的数据. 那什么是主锁呢, 它是整个分布式事务算法的一个核心. 至于什么是主锁, 下面会介绍.

实际上看到上面的列的描述, 我觉得你心里已经有个大概的实现方式了, 在提交一个事务之前, 去 check 所有要写的列对应的 lock 在每一行是否被占用了. 要是发现被占用了, 就说明有 transaction conflict, 需要 rollback 和重试 (注意这里 rollback 实际上啥也不用做, 只要 {column}-write 没有表示 commit 即可). 要是没有占用, 就给每一行上锁.

然后事情没有那么简单. 给每一行上锁不是原子的啊, 不会有死锁问题嘛? 死锁问题其实好解决. 我们可以强制规定一个统一的上锁顺序, 就不会有死锁的问题了. 至于可能导致的活锁, 我们可以通过加入随机性解决.

解决了上锁的问题, 我们在思考一下, 如果提交的时候出了错怎么办? 比如到了实际提交的时候, 我们 commit 了一部分行的改动, 但是之后服务出错了, 怎么办? 很显然, commit 期间出错会有几个问题:

  1. 锁没有释放
  2. 写不是原子的 (有的改动 commit 了, 但是有一部分没有)

为了解决这些问题, 我们就需要使用主锁这个概念了. Precolator 会选取所有改动中的第一行对应的锁, 作为主锁. 在 commit 的时候会先 commit 主锁对应的改动, 然后释放主锁. 之后的改动是否应该 commit 都以这个主锁有没有释放为准. 比如要是 commit 期间出现了故障, 之后的 commit 没有顺利提交. 在恢复的时候, 我们可以遍历所有的锁, 找出它们主锁的位置. 如果主锁已经释放了, 这意味着它们也应该被释放 (并 commit 对应的改动).

总结

我个人觉得这篇论文的精华就是如果使用一个只支持行级别事务的 “数据库” 来实现跨行事务. 其中主锁的概念尤为重要. 这有点让我想起当年使用 App Engine 来主键索引强一致来实现强一致的二级索引了.