一、背景

Percolator是Google在2010年发表的论文《Large-scale Incremental Processing Using Distributed Transactions and Notifications》中提出的一种分布式事务解决方案。在论文中该计划是用来解决搜索引擎的增量索引问题的。

Percolator反对ACID语义，并实现了Snapshot Isolation的事务隔离级别，所以能够将其看作是一种通用的分布式事务解决方案。Percolator基于google本人的Bigtable来实现的，其本质上是一个二阶段提交协定，利用了Bigtable的行事务。

二、架构

Percolator 蕴含三个组件：

Client：Client 是整个协定的控制中心，是两阶段提交的协调者（Coordinator）；
TSO：一个全局的授时服务，提供全局惟一且递增的工夫戳（timetamp）；
Bigtable：理论长久化数据的分布式存储；

2.1. Client

二阶段提交算法中有两种角色，协调者和参入者。在Percolator中，Client充当协调者的角色，负责发动和提交事务。

2.2. Timestamp Oracle (TSO)

Percolator依赖于TSO提供一个全局惟一且递增的工夫戳，来实现Snapshot Isolation。在事务的开始和提交的时候，Client都须要从TSO拿到一个工夫戳。

2.3 Bigtable

Bigtable从数据模型上能够了解为一个multi-demensional有序Map，键值对模式如下：

(row:string, column:string,timestamp:int64)->string

key由三元组 (row, column, timestamp) 组成，value能够是认为byte数组。

在Bigtable中，一行 (row) 能够蕴含多个 (column)，Bigtable提供了单行的跨多列的事务能力，Percolator利用这个个性来保障对同一个row的多个column的操作是原子性的。Percolator的元数据存储在非凡的column中，如下：

（图片来自：https://research.google）

咱们次要须要关注三个column，c:lock ， c:write ， c:data ：

c:lock ，在事务Prewrite的时候，会在此column中插入一条记录
c:write ，在事务commit的时候，会在此column中插入一条记录
c:data ，存储数据自身

2.4 Snapshot Isolation

事务中所有的读操作都会读到一个 consistent snapshot 的数据，等同于Repeated Read隔离级别；
两个并发事务同时对同一个cell写入时，只会有一个事务可能提交胜利；
当一个事务提交时，如果发现本事务更新的一些数据，被其余比其start time大的事务批改之后，则roll back事务，否则commit事务；
存在write skew问题，两个事务读写的数据集有重叠，然而写入的数据集没有重叠，这种状况下，两个事务都能够胜利commit，然而互相都没有看见对方写入的新数据，这达不到serializable的隔离级别。然而snpashot isolation绝对serializable有更好的读性能，因为读操作只须要读快照数据即可，不须要加锁。

三、事务处理

3.1 写入逻辑

Percolator应用两阶段提交算法（2PC）来提交事务，这两个阶段别离为 Prewrite 和 Commit。

在Prewrite阶段：

1）从TSO中获取一个timestamp，将其作为事务的start_ts；

2）对事务中须要写入的每行数据，都会在lock列中写入事务的start\_ts，并在data列中写入新的数据并附带start\_ts，例如下面的14:"value2"。这些locks中会有一个被选作为primary lock，其余locks叫做secondary locks。每个secondary lock都蕴含一个指向primary lock的指针。

1. 如果须要写入的数据中曾经有一个比start_ts 更大的新版本数据，那么以后的事务须要rollback；
2. 如果须要插入lock的行数据中曾经存在一个lock，那么以后事务须要rollback。

在Commit阶段：

1）从TSO中获取一个timestamp，将其作为事务的commit_ts；

2）将primary lock删除，同时在write列中写入commit_ts，这两个操作须要是原子的。如果primary lock不存在了，那么commit失败；

3）对所有的secondary locks反复上述步骤。

上面看一个具体的例子，还是一个经典的银行账号转账的例子，从账号Bob中转账7 dollar到账号Joe中：

1、在事务开始之前，两个账号Bob和Joe别离有10 dollars和2 dollars。

（图片来自：https://research.google）

2、在Prewrite阶段，往Bob的lock列中写入一个lock (7: I am primary)，这个lock为primary lock，同时在data列中写入数据 7:$3。

（图片来自：https://research.google）

3、在Prewrite阶段，持续写入secondary locks。往Joe的lock列中写入lock (7:primary@Bob.bal)，这个lock指向之前写入的primary lock，同时在data列中写入数据 7:$9。

（图片来自：https://research.google）

4、在commit阶段，先革除掉primary lock，并在 write 列中应用新的timestamp (也就是commit_ts) 写入一条新的记录，同时革除 lock 列中的数据。

（图片来自：https://research.google）

5、在commit阶段，革除掉secondary locks，同时在 write 列中以新的timestamp写入新的记录。

（图片来自：https://research.google）

3.2 读取逻辑

1）获取一个工夫戳ts。

2）查看以后咱们要读取的数据是否存在一个工夫戳在[0, ts]范畴内的锁。

如果存在一个工夫戳在[0, ts]范畴的锁，那么意味着以后的数据被一个比以后事务更早启动的事务锁定了，然而以后这个事务还没有提交。因为以后无奈判断这个锁定数据的事务是否会被提交，所以以后的读申请不能被满足，只能期待锁被开释之后，再持续读取数据。
如果没有锁，或者锁的工夫戳大于ts，那么读申请能够被满足。

3）从write列中获取在[0, ts]范畴内的最大 commit\_ts 的记录，而后依此获取到对应的start\_ts。

4）依据上一步获取的start_ts，从data列获取对应的记录。

3.3 解决Client Crash场景

Percolator的事务协调者在Client端，而Client是可能呈现crash的状况的。如果Client在提交过程中出现异常，那么事务之前写入的锁会被留下来。如果这些锁没有被及时清理，会导致后续的事务无限度阻塞在锁上。

Percolator采纳 lazy 的形式来清理锁，当事务 A 遇到一个事务 B 留下来的锁时，事务 A 如果确定事务 B 曾经失败了，则会将事务 B 留下来的锁给清理掉。然而事务 A 很难百分百确定判断事务 B 真的失败了，那就可能导致事务 A 正在清理事务 B 留下来的锁，而事务 B 其实还没有失败，且正在进行事务提交。

为了避免出现此异样，Percolator事务模型在每个事务写入的锁中选取一个作为Primary lock，作为清理操作和事务提交的同步点。在清理操作和事务提交时都会批改primary lock的状态，因为批改锁的操作是在Bigtable的行事务下进行的，所有清理操作和事务提交中只有一个会胜利，这就防止了后面提到的并发场景下可能呈现的异样。

依据primary lock的状态就能够确定事务是否曾经胜利commit：

如果Primary Lock不存在，且 write 列中曾经写入了 commit_ts，那么示意事务曾经胜利commit；
如果Primary Lock还存在，那阐明事务还没有进入到commit阶段，也就是事务还未胜利commit。

事务 A 在提交过程中遇到事务 B 留下的锁记录时须要依据事务 B 的Primary Lock的状态来进行操作。

如果事务 B 的Primary Lock不存在，且 write 列中有 commit_ts 了，那么事务

A 须要将事务 B 的锁记录 roll-forward。roll-forward操作是rollback操作的反向操作，也就是将锁记录革除，并在 write 列中写入 commit_ts。
如果事务 B 的Primary Lock存在，那么事务 A 能够确定事务 B 还没有胜利commit，此时事务 A 能够抉择将事务 B 留下锁记录革除掉，在革除掉之前，须要将事务 B 的Primary Lock先清理掉。
如果事务 B 的Primary Lock不存在，且 write 列中也没有 commit_ts 信息，那么阐明事务 B 曾经被 rollback 了，此时也只须要将事务 B 留下的锁清理掉即可。

尽管下面的操作逻辑不会呈现不统一的状况，然而因为事务 A 可能将存活着的事务 B 的Primary Lock清理掉，导致事务 B 被rollback，这会影响到零碎的整体性能。

为了解决这个问题，Percolator应用了Chubby lockservice来存储每个正在进行事务提交的Client的存活状态，这样就能够确定Client是否真的曾经挂掉了。只有在Client真的挂掉了之后，抵触事务才会真的革除掉Primary Lock以及抵触锁记录。然而还可能呈现Client存活，然而其实其曾经Stuck住了，没有进行事务提交的动作。这时如果不清理掉其留下的锁记录，会导致其余抵触事务无奈胜利提交。

为了解决这种场景，每个存活状态中还存储了一个wall time，如果判断wall time太旧之后，则进行抵触锁记录的解决。长事务则须要每隔肯定的工夫去更新这个wall time，保障其事务不会因而被rollback掉。

最终的事务抵触逻辑如下：

如果事务 B 的Primary Lock不存在，且 write 列中有 commit\_ts 了，那么事务 A 须要将事务 B 的锁记录 roll-forward。roll-forward操作是rollback操作的反向操作，也就是将锁记录革除，并在 write 列中写入 commit\_ts。
如果事务 B 的Primary Lock不存在，且 write 列中也没有 commit_ts 信息，那么阐明事务 B 曾经被 rollback 了，此时也只须要将事务 B 留下的锁清理掉即可。
如果事务 B 的Primary Lock存在，且TTL曾经过期，那么此时事务 A 能够抉择将事务 B 留下锁记录革除掉，在革除掉之前，须要将事务 B 的Primary Lock先清理掉。
如果事务 B 的Primary Lock存在，且TTL还未过期，那么此时事务 A 须要期待事务 B 的commit或者rollback后持续解决。

四、在TiKV中的实现及优化

4.1 Percolator在TiKV中的实现

TiKV底层的存储引擎应用的是RocksDB。RocksDB提供atomic write batch，能够实现Percolator对行事务的要求。

RocksDB提供一种叫做 Column Family(CF) 的性能，一个RocksDB实例能够有多个CFs，每个CF是一个隔离的key命令空间，并且领有本人的LSM-tree。然而同一个RocksDB实例中的多个CFs共用一个WAL，这样能够保障写多个CFs是原子的。

在TiKV中，一个RocksDB实例中有三个CFs：CF_DEFAULT、CF_LOCK、CF_WRITE，别离对应着Percolator的data列、lock列和write列。

咱们还须要针对每个key存储多个版本的数据，怎么示意版本信息呢？在TiKV中，咱们只是简略地将key和timestamp联合成一个internal key来存储在RocksDB中。上面是每个CF的内容：

F_DEFAULT: (key,start_ts) -> value
CF_LOCK: key -> lock_info
CF_WRITE: (key,commit\_ts) -> write\_info

将key和timestamp联合在一起地办法如下：

将user key编码为 memcomparable 的模式；
对timestamp按位取反，而后编码成big-endian的模式；
将编码后的timestamp增加到编码后的key之后。

例如，key key1和工夫戳 3 将被编码成 "key1\\x00\\x00\\x00\\x00\\xfb\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xfe"。这样同一个Key的不同版本在rocksdb中是相邻的，且版本比拟大的数据在旧版本数据的后面。

TiKV中对Percolator的实现与论文中稍有差异。在TiKV中，CF_WRITE中有4中不同的类型的数据：

Put ，CF_DEFAULT中有一条对应的数据，写入操作是一个Put操作；
Delete ，示意写入操作是一个Delete操作；
Rollback ，当回滚一个事务的时候，咱们不是简略地删除CF\_LOCK中的记录，而是在CF\_WRITE中插入一条Rollback的记录。
Lock

4.2 Percolator在TiKV中的优化

4.2.1 Parallel Prewrite

对于一个事务来说，咱们不以one by one的模式去做Prewrite。当咱们有多个TiKV节点时，咱们会在多个节点上并行地执行Prewrite。

在TiKV的实现中，当提交一个事务时，事务中波及的Keys会被分成多个batches，每个batch在Prewrite阶段会并行地执行。不须要关注primary key是否第一个Prewrite胜利。

如果在事务在Prewrite阶段产生了抵触，事务会被回滚。在执行回滚时，咱们是在CF_WRITE中插入一条Rollback记录，而不是Percolator论文中形容的删除对应地锁记录。这条Rollback记录示意对应的事务曾经rollback了，当一个后续的Prewrite申请到来时，这个Prewrite不会胜利。这种状况可能在网络异样的时候会呈现。如果咱们让Prewrite申请胜利，正确性还是能够保障，然而这个key会被锁定，直到锁记录过期之后，其余事务才能够再次锁定此key。

4.2.2 Short Value in Write Column

当咱们拜访一个value时，咱们须要先从CF\_WRITE中找到key对应最新版本start\_ts，而后从CF_DEFAULT中找到具体的记录。如果一个value比拟小的话，那么查找RocksDB两次开销相对来说有点大。

在具体实现中，为了防止short values两次查找RocksDB，做了一个优化。如果value比拟小，在Prewrite阶段，咱们不会将value放到CF\_DEFAULT中，而是将其放在CF\_LOCK中。而后在commit阶段，这个value会从CF\_LOCK挪动到CF\_WRITE中。而后咱们在拜访这个short value时，就只须要拜访CF_WRITE就能够了，缩小了一次RocksDB查找。

4.2.3 Point Read Without Timestamp

对于每个事务，咱们须要先调配一个start\_ts，而后保障事务只能看到在start\_ts之前提交的数据。然而如果一个事务只读取一个key的数据，咱们是否有必要为其调配一个start_ts呢？答案是否定的，咱们只须要读取这个key的最新数据就能够了。

4.2.4 Calculated Commit Timestamp

为了保障Snapshot Isolation，咱们须要保障所有的transactional reads是repeatable的。commit_ts应该足够大，保障不会呈现一个事务在一次valid read之前被提交，否则就没发保障repeatable read。例如：

Txn1 gets start_ts 100
Txn2 gets start_ts 200
Txn2 reads key "k1" and gets value "1"
Txn1 prewrites "k1" with value "2"
Txn1 commits with commit_ts 101
Tnx2 reads key "k1" and gets value "2"

Tnx2读取了两次"k1"，然而失去了不一样的后果。如果commit\_ts从PD上调配的，那么必定不存在此问题，因为如果Txn2的第一次read操作产生在Txn1的Prewrite之前，Txn1的commit\_ts必定产生在实现Prewrite之后，那么Txn2的commit\_ts必定大于Txn1的start\_ts。

然而，commit\_ts也不能无限大。如果commit\_ts大于理论工夫的话，那么事务提交的数据新的事务可能读取步到。如果不向PD询问，咱们是不能确定一个工夫戳是否超过以后的理论工夫的。

为了保障Snapshot Isolation的语义以及数据的完整性，commit_ts的无效范畴应该是：

max(start_ts,max_read_ts_of_written_keys)<commit_ts<=now

commit_ts的计算方法为：

commit_ts=max(start_ts,region_1_max_read_ts,region_2_max_read_ts,...)+

其中region\_N\_max\_read\_ts为region N上所有读操作的最大工夫戳，region N为事务所波及的所有region。

4.2.5 Single Region 1PC

对于非分布式数据库来说，保障事务的ACID属性是比拟容易地。然而对于分布式数据库来说，为了保障事务地ACID属性，2PC是必须地。TiKV应用地Percolator算法就是一种2PC算法。

在单region上，write batches是能够保障原子执行地。如果一个事务中影响的所有数据都在一个region上，2PC是没有必要的。如果事务没有write conflict，那么事务是能够间接提交的。

五、总结

长处：

事务管理建设在存储系统之上，整体零碎架构清晰，零碎扩展性好，实现起来简略；
在事务抵触较少的场景下，读写性能还不错；

毛病：

在事务抵触较多的场景下，性能较差，因为呈现了抵触之后，须要一直重试，开销很大；
在采纳MVCC并发控制算法的状况下也会呈现读期待的状况，当存在读写抵触时，对读性能有较大影响；

总体上Percolator模型的设计还是可圈可点，架构清晰，且实现简略。在读写抵触较少的场景下，可能有还不错的性能。

六、援用

1. Codis作者首度揭秘TiKV事务模型，Google Spanner开源实现

2. Google Percolator 事务模型的利弊剖析

3. Large-scale Incremental Processing Using Distributed Transactions and Notifications – Google Research

4. Database · 原理介绍 · Google Percolator 分布式事务实现原理解读 (taobao.org)

作者：vivo互联网数据库团队-Wang Xiang

一、背景

二、架构

2.1. Client

2.2. Timestamp Oracle (TSO)

2.3 Bigtable

2.4 Snapshot Isolation

三、 事务处理

3.1 写入逻辑

3.2 读取逻辑

3.3 解决Client Crash场景

四、在TiKV中的实现及优化

4.1 Percolator在TiKV中的实现

4.2 Percolator在TiKV中的优化

4.2.1 Parallel Prewrite

4.2.2 Short Value in Write Column

4.2.3 Point Read Without Timestamp

4.2.4 Calculated Commit Timestamp

4.2.5 Single Region 1PC

五、总结

六、援用

三、事务处理