论文笔记：[OSDI'10] Large-scale Incremental Processing Using Distributed Transactions and Notifications

Percolator[1]在基于Bigtable[2]系统，在不改变Bigtable自身实现的前提下，通过行级事务和多版本控制，实现了Snapshot Isolation级别的跨行事务。此外，论文还描述了一种基于Bigtable实现的可靠的消息通知机制。

比较有特色的是，Percolator在实现上述2个功能时，并没有侵入去改变Bigtable的实现，而是在Bigtable外围通过包装去实现，这在有些情况下是一种非常方便的做法，但是一般会带来性能损失。

本文只叙述Percolator事务相关的部分。

预备知识

Bigtable的数据模型和事务支持

我们先回顾一下Bigtable的数据模型：

如上图所示，数据可以由以下层级关系确定：

1. row name，例如 com.cnn.www

2. column families，例如 anchor

3. column，例如 contents: 和 anchor:cnnsi.com

4. timestamp，例如 $t_3$，$t_5$ 和 $t_6$

Bigtable支持行级事务，尽管在[2]中没有明说是什么样的事务隔离性级别，但是从[1]对于Primary加锁的相关叙述中可以推测出应该是Serialisability级别的。

Snapshot Isolation简介

在[3]中非形式化的描述了Snapshot Isolation。简单而言，一次Snapshot Isolation的Transaction具有2个重要的时间结点：Start-Timestamp和Commit-Timestamp。在整个Transaction开始时，也即Start-Timestamp，对整个系统中的数据取快照，在Transaction进行过程中读取的所有数据，以及写入的所有变更都来自于这个快照。如果在提交时，也即Commit-Timestamp，发现有其他Transaction已经提交了，则Abort，否则成功。

在[4][5]和[6]中有关于Snapshot Isolation的形式化表述。

Snapshot Isolation相关展开的话题比较多，包括以下几个主要方面：

1. 提升隔离性：One-copy Snapshot Isolation，Serializable Snapshot Isolation

2. 各种变种和优化

3. 和新硬件的结合优化

相关话题见：Snapshot Isolation综述，论文笔记：[CONCUR'15] A Framework for Transactional Consistency Models with Atomic Visibility 和 CAP，ACID，我们能做什么。

P.S. Postgres中MVCC的实现见[10]。[3]提到了Snapshot Isolation是对于[7]中Multiversion Mixed Method的一种扩展。但是Snapshot Isolation也可以用其他方式实现，例如[11]中提供了使用读写锁实现Snapshot Isolation的方法。

Percolator是如何实现跨行事务的

Percolator依赖于底层BigTable实现Multi-version和行级事务，在此基础上实现了跨行事务。

主要流程

假设存在一个Timestamp Oracle Service可以提供单调递增的时戳。Bigtable Transaction提供行内强一致性级别事务。Bigtable使用Timestamp Oracle Service提供的时戳作为cell的版本号。我们基于上述设施介绍如何实现Percolator Transaction。

1. 当Percolator Transaction开始时，取得一个时戳Start-Timestamp

2. 进入读阶段

   1. 当发起读请求时，总是取得Start-Timestamp之前最后一次Committed的版本的值

   2. 当发起写请求时，总是将写请求缓存到本地

3. 当Percolator Transaction提交时

   1. 进入加锁阶段，对所有被写请求影响的cell加锁（通过写一个特殊的cell）

   2. 取得一个时戳Commit-Timestamp

   3. 进入提交阶段，以Commit-Timestamp作为写版本，将缓存在本地的写请求Flush到远程并去除受影响的cell上的锁

以上过程中，无论是读请求还是写请求，都需要Bigtable行级事务的支持。

由于BigTable并不支持真正的行级锁，这里锁的实现方式是使用一个特殊的列：c:lock（这里 : 比较容易引起歧义，在BigTable中使用 : 分割 ColumnFamily 和 ColumnName，可以认为这里使用了另一个特殊符号进行分割，例如： cf:cn+lock）。这样的话，原来的数据也需要相应变化一下，约定使用列 c:data 存储真实数据（的不同版本）。由于我们想要支持跨行事务，最终Percolator事务提交的时候，我们还需要一个特殊的列来标记 Committed：c:write。

Percolator还进行了一些变化，以避免为每一个Percolator事务分配唯一标识。通过（任意）指定一个write请求的cell在加锁时，这个锁是Primary的，事务中的其他Lock都是Secondary Lock，并且指向这个Primary Lock。这个设计相当于用Primary Lock唯一标志这个Percolator事务，使用BigTable可靠的记录（追踪）了整个事务，这个记录可以用于错误恢复时读取整个事务的状态。

Percolator的具体算法参考原论文，下面讲解一下论文中给出的例子。

Table 1. Initial State

key	bal:data	bal:lock	bal:write
Bob	6:	6:	6: data @ 5
	5: $10	5:	5:
Joe	6:	6:	6: data @ 5
	5: $2	5:	5:

如Table 1所示，初始状态中存有2行数据：Bob和Joe。他们最后一次Committed的Version都是5，他们现在都没有被加锁。观察其数据列，得到他们现在的状态：Bob有\$10，Joe有\$2。假设读取的Cell的版本区间上存在“有效”的锁（“有效”见后面错误恢复），则需要等待锁释放后再读取。

现在Bob想要转账\$7给Joe，所有的读取请求无需加锁，直接按照当前时间的快照进行查询，即读到了Table 1中的状态：Bob有\$10，Joe有\$2。此时判定可以进行转账操作，于是开始进行写入。所有的写请求都会先Buffer到本地，等到提交阶段再进行，这样可以保证在提交阶段时知道所有需要加锁的Cell。转账操作需要分别影响Bob的bal和Joe的bal。

假设我们总是将第一次写操作影响的Cell认为是Primary Lock Object，首先从Bob的账户中减去\$7，则第一次写入可以同时做加Primary Lock和记录写请求的工作，如Table 2所示。

加锁时有2种情况会导致加锁失败：

1. 在Transaction开始后，已经有其他人提交了其他的Transaction，并且也写入了这一Cell（意味着Write-Write冲突）

2. 别人已经在这个Cell上加锁了，并且这个锁此时仍然是“有效”（“有效”见后面错误恢复）的（意味着Percolator Transaction是Non-blocking的）

Table 2. The transfer transaction begins by locking Bob’s account

key	bal:data	bal:lock	bal:write
Bob	7: $3	7: I am primary	7:
	6:	6:	6: data @ 5
	5: $10	5:	5:
Joe	6:	6:	6: data @ 5
	5: $2	5:	5:

Primary lock成功后，接下来的所有写操作都需要加锁，并且将锁指向Primary Lock以供错误检测和恢复使用。

Table 3. The transaction now locks Joe’s account and writes Joe’s new balance

key	bal:data	bal:lock	bal:write
Bob	7: $3	7: I am primary	7:
	6:	6:	6: data @ 5
	5: $10	5:	5:
Joe	7: $9	7: primary @ Bob.bal	7:
	6:	6:	6: data @ 5
	5: $2	5:	5:

如果所有写入请求加锁成功，那么就可以进入提交阶段。提交时首先提交Primary Lock锁住的内容，见The transaction has now reached the commit point。

Table 4. The transaction has now reached the commit point

key	bal:data	bal:lock	bal:write
Bob	8:	8:	8: data @ 7
	7: $3	7:	7:
	6:	6:	6: data @ 5
	5: $10	5:	5:
Joe	7: $9	7: primary @ Bob.bal	7:
	6:	6:	6: data @ 5
	5: $2	5:	5:

然后再提交其他Lock锁住的内容：

Table 5. The transaction completes by adding write records and deleting locks at the secondary cells

key	bal:data	bal:lock	bal:write
Bob	8:	8:	8: data @ 7
	7: $3	7:	7:
	6:	6:	6: data @ 5
	5: $10	5:	5:
Joe	8:	8:	8: data @ 7
	7: $9	7: primary @ Bob.bal	7:
	6:	6:	6: data @ 5
	5: $2	5:	5:

错误恢复

Percolator相当于使用Client进行Coordinate，但是将所有需要的数据都（通过Embed的方式）Persist到Bigtable中了，因此只要能够检测到Failure，就有足够的信息进行恢复。这里的难点在于如何确定另一个Client真的Fail了，并且这个Client还得必须是Fail-Stop模型的（例如一个Client仅仅是慢，但是被别人认定为Fail了，此时这个Client必须得自行Stop）。Percolator Worker（也就是上面提到的Client），基于Chubby服务[12]进行Lease-Reclaim来保证上述提到的Failure detect和Fence机制。

剩下的问题就比较简单了，根据Primary Lock的情况分为2种：

1. 如果Primary Lock已经Committed了，则需要继续Rollout这个Transaction，将所有发现的Cell都提交

2. 如果Primary Lock还没有Commit，则需要将这个Transaction Rollback，将所有发现的Cell都Rollback

论文中没有提到具体怎么发现这些受影响的Cell，推测可能的方法有：

1. 在Get数据时Lazily的检测是否需要Rollout/Rollback这个Cell（这个是必须处理的情况）

2. 将Transaction影响到的Cell记录到某个地方（由于在加Primary Lock的时候已经知道都有哪些Cell需要加锁了，所以这个方法是可行的）

3. 定期进行全表扫描回收

其他优化

由于需要保证Timestamp是全序递增的，Timestamp oracle一般采用集中式的方案，因此可能会成为性能瓶颈，需要特别的优化。

Percolator中Timestamp oracle采用预分配的方式，直接分配出一批timestamp，并且将其中最大的一个持久化到可靠存储中。这种预分配的方式可以使得接下来一段时间内的分配都只需要进行内存访问；如果发生重启，则直接从可靠存储中读取最大的一个可能已经分配的Timestamp继续分配即可。

为了节约通信开销，Percolator Worker通过Batching聚合的方式从Timestamp oracle分配一批Timestamp。

性能比较

Percolator Transaction在不考虑重试和错误处理的情况下

1. 每次读请求需要读

   1. 基础的Version Range

   2. 有可能存在的锁

   3. 锁指向的Primary Lock

2. 每次写请求需要

   1. 读write是否有新提交（Write-Write冲突）

   2. 读lock是否有锁冲突

   3. 写数据更新和锁

   4. 提交

可见读写放大还是比较严重的。Percolator和裸Bigtable性能对比如论文中Figure 8所示：

Table 6. The overhead of Percolator operations relative to Bigtable

	Bigtable	Percolator	Relative
Read/s	15513	14590	0.94
Write/s	31003	7232	0.23

优缺点

个人认为，Percolator的优点在于非侵入式的给一个支持Multi-version和行级事务的存储系统增加了多行（多表）事务的能力；缺点在于

1. 需要业务修改表结构

2. 性能比较低

3. 不能有非Transaction的写入和Transaction有任何读/写冲突

4. 错误恢复比较复杂

5. Timestamp Oracle可能单点失效

References

• [1] PENG D, DABEK F. Large-scale Incremental Processing Using Distributed Transactions and Notifications[J]. OSDI’10, 2010, 2006: 1–15.

• [2] CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: A distributed storage system for structured data[J]. 7th Symposium on Operating Systems Design and Implementation (OSDI ’06), November 6-8, Seattle, WA, USA, 2006: 205–218.

• [3] BERENSON H, BERNSTEIN P, GRAY J, et al. A critique of ANSI SQL isolation levels[J]. ACM SIGMOD Record, 1995, 24(2): 1–10.

• [4] ADYA A. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions[J]. 1999: 198.

• [5] CROOKS N, PU Y, ALVISI L, et al. Seeing is Believing: A Client-Centric Specification of Database Isolation[J]. Podc, 2017(June): 73–82.

• [6] CERONE A, BERNARDI G, GOTSMAN A. A Framework for Transactional Consistency Models with Atomic Visibility[J]. 26th International Conference on Concurrency Theory, {CONCUR} 2015, Madrid, Spain, September 1.4, 2015, 2015, 42(Concur): 58–71.

• [7] BERNSTEIN P A, GOODMAN N. Concurrency Control in Distributed Database Systems[J]. ACM Computing Surveys, 1981, 13(2): 185–221. 较早的mvcc总结

• [8] BERNSTEIN P A, GOODMAN N, HADZILACOS V. Concurrency Control and Recovery in Database Systems[M]. ACM Transactions on Database Systems, Addison-Wesley Pub. Co, 1987. mvcc的书

• [9] WU Y, ARULRAJ J, LIN J, et al. An empirical evaluation of in-memory multi-version concurrency control[J]. Proceedings of the VLDB Endowment, VLDB Endowment, 2017, 10(7): 781–792.

• [10] MOMJIAN B. MVCC Unmasked[EB/OL]. (2019). http://momjian.us/main/writings/pgsql/mvcc.pdf.

• [11]Raad, A., Lahav, O., & Vafeiadis, V. (2019). On the Semantics of Snapshot Isolation. In Logic Programming (Vol. 1, pp. 1–23). Springer International Publishing. https://doi.org/10.1007/978-3-030-11245-5_1

• [12] BURROWS M. The Chubby lock service for loosely-coupled distributed systems[J]. OSDI ’06: Proceedings of the 7th symposium on Operating systems design and implementation SE - OSDI ’06, 2006: 335–350.