一、背景

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