当前位置: 首页 > 工具软件 > Percolator > 使用案例 >

Percolator 2PC模型

李敏学
2023-12-01

介绍

Percolator 用于Google的检索系统。Google爬取的网页建立的索引,通过Percolator系统建立索引。
Google的检索系统维护了上千台机器,有数十PB数据。
Percolator优化了增量处理(incremental processing)的问题: 很多网页是已经爬取过的,爬取的新网页或者旧网页更新了,如果可以增量更新到原有系统,会更节省资源。
Percolator提供了支持ACID特性的事务。
Percolator提供的是快照隔离级别(Snapshot Isolation)。
Percolator基于Bigtable做的,Bigtable提供了强一致性和基础事务功能。

设计

两个基础组件:

  • timestamp oracle: 高效的提供严格递增的时间戳功能,可以达到每秒钟100W。
  • lightweight lock service。一个轻量级锁服务。

时间戳组件提供了生成单调递增序列的功能。目前有谷歌的原子时钟、中心节点方式和HLC的方式。

Percolator没有事务管理节点,因此也没有全局的死锁检测。
Get()操作会获取读锁,如果此时有写锁,会阻塞。

NOTE 读数据加锁很关键。通过加锁冲突,发现2PC提交一半的事务。

Bigtable的单行atomic特性
提供单独行的read-modify-write原子操作。

行锁信息
行锁信息作为Bigtable的特殊字段存在,Bigtable会将其持久化,在异常时可以恢复出来。
行锁信息持久化这个功能非常关键,只有持久化行锁信息,才能知道数据异常恢复时,是否有对应的事务未提交或需要回滚。

Percolator会缓存写操作(update/delete),第一阶段提交时(prewrite),尝试对所有行加锁。如果没有冲突,进行第二阶段提交。

二阶段提交

  1. 缓存所有的写操作, vector<Write> writes_;
  2. 选择任意一个写操作作为primary,其它的操作为secondary;
  3. primary操作做prewrite操作;
  4. 对所有的secondaryprewrite操作;
  5. 获取commit时间戳;
  6. 校验锁是否当前事务所有;
  7. 设置数据生效时间(将commit时间戳写到行上);
  8. 释放primary的行锁;
  9. Bigtable提交单行事务(应该是atomic特性中的内容);
  10. 设置所有secondary数据生效,清理所有secondary行锁(这一步可以由其它线程执行,如果当前事务出现异常的话)。

prewrite操作

  1. 检查是否已经有新的已经提交的数据,有的话就abort;
  2. 检查写操作是否有锁冲突,如果有冲突就abort;
  3. 将当前时间戳和值信息写到行信息上;
  4. 将primary行信息和时间戳记录到锁信息上,相当于加锁。NOTE:所有secondaries行都会记录primary lock到当前行;
  5. Bigtable提交事务。

2PC的关键点

  • primary row:事务的提交或回滚状态取决于primary row,也只需要通过primary row来确定。

如何保证Get操作返回事务起始时间戳之前的所有提交数据?
在提交之前,prewrite阶段,先对修改的行数据上了锁,读数据的时候肯定要等锁。事务提交后会解锁,"同时"会将提交的时间戳设置到行数据上。
这里的"同时"是由Bigtable atomic特性保证的。

TiDB的描述

1) 事务提交前,在客户端 buffer 所有的 update/delete 操作。 2) Prewrite 阶段:

首先在所有行的写操作中选出一个作为 primary,其他的为 secondaries。

PrewritePrimary: 对 primaryRow 写入L列(上锁),L列中记录本次事务的开始时间戳。写入L列前会检查:

是否已经有别的客户端已经上锁 (Locking)。
是否在本次事务开始时间之后,检查 W 列,是否有更新 [startTs, +Inf) 的写操作已经提交 (Conflict)。
在这两种种情况下会返回事务冲突。否则,就成功上锁。将行的内容写入 row 中,时间戳设置为 startTs。

将 primaryRow 的锁上好了以后,进行 secondaries 的 prewrite 流程:

类似 primaryRow 的上锁流程,只不过锁的内容为事务开始时间及 primaryRow 的 Lock 的信息。
检查的事项同 primaryRow 的一致。
当锁成功写入后,写入 row,时间戳设置为 startTs。

3) 以上 Prewrite 流程任何一步发生错误,都会进行回滚:删除 Lock,删除版本为 startTs 的数据。

4) 当 Prewrite 完成以后,进入 Commit 阶段,当前时间戳为 commitTs,且 commitTs> startTs :

commit primary:写入 W 列新数据,时间戳为 commitTs,内容为 startTs,表明数据的最新版本是 startTs 对应的数据。
删除L列。
如果 primary row 提交失败的话,全事务回滚,回滚逻辑同 prewrite。如果 commit primary 成功,则可以异步的 commit secondaries, 流程和 commit primary 一致, 失败了也无所谓。

异常

清理异常事务的锁信息

客户端在提交事务的时候挂了,事务上的锁信息就会遗留在那里,所以要有方法将它们清理掉。
Percolator使用的清理方法是当A事务遇到了与它冲突的B事务,A就会判断B是不是已经挂了,然后清理掉它相关的锁。

怎么解决A事务判断B事务是否失败与B事务正在提交的冲突(race condition)?

使用primary lock。就是上面介绍选出来的primary写操作对应的锁。执行回滚或提交操作都需要操作primary lock。Bigtable可以保证清理或提交只有一个会成功。
如果某个异常事务的primary lock已经释放,可以将这个事务提交。

怎么判断一个事务是不是正常的(liveness)?

正在运行的worker向Chubby lockservice写入token,其它事务通过这个token来判断事务是不是正常的。如果token对应的时间太旧,就认为事务已经异常。
当然,事务会定时更新token的时间。只清理异常事务的锁信息。

总结

2PC一个很大的缺点是在提交的第二个阶段,如果部分节点失败了,这个事务的状态是无法判断的,提交成功的节点认为事务已经提交了,后续这个事务也没办法恢复了。
Percolator中提出的2PC模型,目的是为了在某个事务出现异常时,有方法让事务自动roll-forward或roll-back。关键点就在于primary row,2PC最困难的地方就是无法让多条动作同时成功或失败,但是某一个动作的成功或失败是可以确认的,所以事务中其它数据的状态都参考primary row,通过其状态判断事务的状态。就像多线程多进程并发同步的mutex等,最核心依赖的其实就一个CAS(compare-and-exchange)操作。
Percolator的另一个优化是在提交的第二个阶段,除了primary row是同步提交,其它节点的数据都可以异步执行,提高了2PC的效率。

问题

假设某个事务修改了多行数据,并且分布在多个分片上。如果部分分片宕机异常,恢复后,其它线程访问到异常数据时,会通过异常数据行的内容找到primary row,然后根据primary row的是否已经提交来决定是roll-forward或roll-back。在多版本系统中,容易判断primary row是否已经提交。比如异常的行对应版本是100,那么判断primary row当前版本是否已经超过100即可。
问题是,在单版本(single-value)系统中,怎么判断primary row对某个事务是否已经提交?
问题2:在MVCC系统中,如果通过判断某个版本对应的primary row是否已经提交,那么旧版本怎么回收的?在primary row中关联事务数据,通过事务查找所有关联的行?
这个问题在YugaDB中也得到了解决,其使用额外的表专门记录事务信息。事务在提交的时候,在事务表中创建一条相关的数据,这条数据中记录的事务状态是成功,那么事务就是成功,否则就是失败的,需要回滚[4]。

参考

  1. Percolator 和 TiDB 事务算法
  2. 《Large-scale Incremental Processing Using Distributed Transactions and Notifications》
  3. 《A Critique of ANSI SQL Isolation Levels》
  4. Yes We Can! Distributed ACID Transactions with High Performance
 类似资料: