[分布式事务] 1 - Percolator

其实一直没搞懂 percolator 所属的类别

好，今天我们来看 Percolator。

不知道为什么检索了许多有关分布式事务的博客，很少有介绍分布式事务提交协议时带上 Percolator 的。可能因为 Percolator 是基于 BigTable、针对增量更新操作事务设计的，不太适合其他分布式事务的场景。虽然有点好奇为何 TiKV 选择了这样一个提交协议，但是我们还是先看 Percolator 的工作原理¹，然后才好分析它的优缺点，以及 TiKV 在此基础上做了什么改动。

引

Percolator 本身是谷歌为了提高他们网页索引更新的效率而设计的，这一场景主要特点有数据规模大（PB级别）、数据分布在数千个节点中（使用BigTable存储）、实时性需求低（用户会晚一些看到搜索结果更新，这影响并不大）、数据更新的部分相对较小。

论文中其实也提到，可以实现一个不支持事务的增量更新系统，但是有事务的ACID性质有助于判断系统应处于什么状态，有利于保持索引表的一致性和 up to date。我们本身就是想介绍这是怎样一个分布式提交协议、如何支持分布式事务的性质，因此就不花太多笔墨介绍为何需要分布式事务了，来看重点吧。

Percolator 是采用一种两阶段提交的方式来进行事务的提交，且在 BigTable 中存储多个版本的数据（基于时间戳的MVCC）来提供 Snapshot Isolation 的隔离级别。但它的提交与之前所说的 2PC 过程还是有挺大区别的，而且使用时间戳的同时还用了锁来进行并发控制这一点也让人费解，下面我们一点点来介绍。这里的介绍和相关论文解读均出自分布式领域萌新（本人）的一家之言，如果理解有误也请见谅。~~也许该考虑一下评论区了~~

Percolator 提交过程

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

这是来自论文里的 Percolator 字段示意图，一条记录除了原本的k/v字段之外，还增加了 lock 和 write 两个字段用于并发控制；除此之外其实还有 norify 和 ack_O 字段用于 Notification，但展示 lock 和 write 就足够我们理解 Percolator 提交分布式事务的过程，额外的字段这里我们暂且不提。

data 字段是实际存储 value 的地方；
lock 字段用于表示对某个key加锁，key 的 lock 字段存在值时表示该 key 被锁上，释放锁时清空该字段的值。之所以用一个字段来表示锁，论文是这样考虑的：Percolator 是作为 client 访问 BigTable，无法直接控制 BigTable 对某部分数据加锁，因而相当于需要自己实现 lock manager。Percolator 对这样一个组件的要求是：锁的信息需要持久化、高吞吐量、分布式且能够负载均衡。BigTable 足够满足以上需求，于是他们合计直接将锁存在 BigTable 中，也就是现在这样用一个字段标识锁的做法。
write 字段是用来标识事务是否完成提交的。如果事务成功提交，则会在 write 字段增加一行数据，内容为本次提交事务对应的版本号。

关于为什么需要锁的一些分析：参考数据库系统概念第六版 15.4.2 时间排序协议小节最后保证可恢复调度部分、15.6.1 多版本时间戳排序，以及习题15.30，时间戳排序协议为了防止不可恢复调度的出现（比如以下的调度在时间戳排序中允许出现，但是却是不可恢复的），
1
2
3
4
5
6
7
|T1      |T2      |
|--------|--------|
|read(A) |        |
|write(A)|        |
|        |read(A) |
|        |commit  |
|read(B) |        |
可以采用以下方法:

使用 lock 将读取未提交数据的操作推迟到更新该数据的事务提交之后

使用一个 commit bit 表示事务正在修改某数据项，用于推迟读操作

教材上说使用多版本时间戳排序同样不能保证可恢复性（TODO：为何，此处T2读到的是旧版的数据A，而非T1修改后的数据A，应当是可恢复的吧），如果要保证调度可恢复，依然需要采用上述改动中的一种。听上去推迟读操作似乎与我们本身理解 MVCC 无需阻塞读写操作的优势发生了冲突，但为了保证数据库的一致性这是必要的牺牲。另外，使用锁之后，我们很容易验证每次 Get 操作总是能获取所有时间戳小于它的所有事务的所有修改。（TODO：是否MVCC两阶段锁中，后出现的读事务可能没读到先前的写事务的修改？）

因此 Percolator 的两阶段提交过程如下：

PreWrite 阶段尝试为所有要修改的数据申请锁，然后检查是否存在以下冲突：
- write 字段的时间戳大于当前事务，说明有其他事务先于本事务修改了该数据并完成提交，为了防止更新丢失，本事务需要回滚；
- 某个数据上的锁已存在，说明其他事务在修改该数据，本事务回滚。
若不存在冲突则进入 Commit 阶段，事务清除 lock 字段中存储的锁，然后在 write 字段中记录事务的开始时间戳，完成提交过程。

需要注意的是如小节开头表格中展示的那样，每个字段写入时都要附带一个写入时间戳，在 Percolator 中由一个 timestamp oracle 来进行时间戳的分配。

同时读操作也如上所说，读事务查看[0, start_timestamp]时间范围内是否存在锁（写事务加锁时会附带时间戳），如果有则等待写事务释放数据的锁，然后才开始读最新版本的数据；如果没有则可直接读取最新的数据。

Percolator 并不像2PC中有一个集中式的协调器（这样的架构肯定没法扩展到谷歌需要的数千节点集群），而是由发起事务的客户端来进行事务的提交操作，比方说通过一个集群在执行爬虫任务，那么集群中的任何一个节点都能向 Percolator 发起事务的提交请求，从而避免了 2PC 中协调器单点故障的问题。不过由于客户端存在故障的可能，提交操作可能会卡在某个中间状态， Percolator 还需要处理这些异常状态。

客户端故障可能会造成事务未完成提交或事务提交后没有来得及清理锁，因此一个新事务执行时，如果遇到某个字段上有锁，需要判断给该字段加锁的 worker 是否还在正常执行，是否需要回滚或重做它的修改（以便能够释放锁传给新事务）；否则如果按照前面描述的两阶段提交过程直接回滚新事务的话，一个异常终止的事务就会阻塞后续所有事务的执行。

Percolator 采用的方法是在一个事务中选取一个 key 作为 primary，以 primary 的提交作为事务的提交点，其他 key 的 lock 字段存储的是 primary 的地址。如果新事务扫描到异常终止的事务留下来的锁，可以通过 primary 对应的 lock 字段判断这个事务是否进入提交状态：如果 primary lock 不存在，而对应的 write 字段已有更新，则该事务已进入提交，需要重做其它未完成的修改；如果 primary lock 存在，则事务还未提交，可以进行回滚。

不过到这里我们还是无法判断碰到一个 key 被锁住时，究竟是因为 worker 故障了，还是因为事务正在执行。如果我们每次碰到 key 被锁住时，都回滚之前事务的操作，很容易干扰正常事务的执行。Percolator 解决这一问题的策略是将 worker 状态存到 chubby 中来判断发起某个事务的 wroker 是否存活；只有检测到对应 worker 宕机之后才会按照上述方式清理 lock 并继续新事务的修改过程。也就是使用 primary 其实并不能告诉我们事务状态是否异常，且如果节点故障导致事务提交失败，重启后节点本身也并不会进行回滚操作，而是下一次事务开始提交时（可能是故障节点自己重启后进行，也可能使其它节点提交的事务），才将对应的 lock 和未提交 data 给清理掉。primary 本身只是作为判断事务是否提交的提交点而已。另外 Percolator 还给每个锁加上了有效期，失效的锁可以被直接清除；如果事务还在正常执行过程中，那么需要在锁过期之前更新它的有效时间，防止被直接清除。

// TODO：notify

关于时间戳的生成论文中略微介绍了一下，timestamp oracle 首先会生成一批可分配时间戳并将最大那个持久化到磁盘，然后按照升序将时间戳分配给事务。如果 oracle 重启，需要读取磁盘中记录的最大可分配时间戳，在它之后生成一批新的时间戳来分配，这样能够避免机器故障导致重复分配时间戳的问题，同时不用每次分配时间戳都记写入一次磁盘。但是论文似乎没有介绍 oracle 如何扩展的，整个 oracle 集群之间如何进行数据同步，根据论文发布的时间，猜想可能是用 Zookeeper 做的吧。分布式时间戳的分配在 TiDB 中也有涉及，有空再去看看他们怎么做。

以上就是 Percolator 提交的大概思想了，其他的细节比如 Notification 机制等下次再考虑是否展开介绍一下吧。下面我们来看看 TiKV 中有何改动。

Percolator in TiKV

TiKV 中基本是按照上面描述的过程实现的，当然底层存储用的是RocksDB，同样有对应 data/lock/write 的三个字段²,³，分别是 CF_DEFAULT/CF_LOCK/CF_WRITE。其中 CF_DEFAULT 和 CF_WRITE 的key值是由实际的 user key 与 timestamp 共同组成的，能够在底层的有序存储中将 timestamp 更大的 key 放在前面，以便扫描时能够先访问更新的 key。另外回滚事务时，采用的是在 CF_WRITE 中写入 ROLLBACK 标识完成，而不是删除对应的 value。

另外因为 TiKV 使用的存储引擎是 RocksDB （一个分布式存储引擎使用另一个单机存储引擎存储数据，哈哈，也符合不重复造轮子的原则），而 RocksDB 是使用 LSMTree 索引的，在读取数据时我们先读取 CF_WRITE 然后从其中获取 CF_DEFAULT 的数据，这就产生了两次IO过程。因此 TiKV 将较短的 value 直接存在 CF_WRITE 中，能够节省一次IO。而如果不使用 CF_DEFAULT 存储数据，在加锁时也需要把数据写在 CF_LOCK 中，然后删除锁时再把 k/v 搬到 CF_WRITE。所以这种优化只有才数据比较小的情况下才能采用。

Point Read 没看懂：为何能够直接读取最新版本的 value？并不是读一个未提交的数据，而是读已提交数据里最新的。但可恢复性呢？但是如果读已提交的，那 // TODO：多版本时间戳

// TODO：单行事务
// TODO：点查询会出现大量scan操作 ³ 疑问：不是有布隆过滤器提前筛选了吗？为什么还这么说

The End

引

Percolator 提交过程

Percolator in TiKV

CATALOG