Percolator 模型及其在 TiKV 中的实现
一、背景
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，键值对形式如下：
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 的有效范围应该是：
commit_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 事务模型的利弊分析
4. Database · 原理介绍 · Google Percolator 分布式事务实现原理解读 (taobao.org)
作者：vivo 互联网数据库团队-Wang Xiang
版权声明: 本文为 InfoQ 作者【vivo互联网技术】的原创文章。
原文链接:【http://xie.infoq.cn/article/1997999aa9977620031de2987】。文章转载请联系作者。
官方公众号：vivo互联网技术，ID：vivoVMIC 2020.07.10 加入
分享 vivo 互联网技术干货与沙龙活动，推荐最新行业动态与热门会议。
评论