Percolator模型及其在TiKV中的实现

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

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

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：

事务 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后继续处理。

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。例如：

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)