Percolator 2PC模型
介绍
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)，尝试对所有行加锁。如果没有冲突，进行第二阶段提交。
二阶段提交
- 缓存所有的写操作,
vector<Write> writes_; - 选择任意一个写操作作为
primary，其它的操作为secondary; - 对
primary操作做prewrite操作; - 对所有的
secondary做prewrite操作; - 获取commit时间戳;
- 校验锁是否当前事务所有;
- 设置数据生效时间(将commit时间戳写到行上);
- 释放
primary的行锁; - Bigtable提交单行事务(应该是atomic特性中的内容);
- 设置所有
secondary数据生效，清理所有secondary行锁(这一步可以由其它线程执行，如果当前事务出现异常的话)。
prewrite操作
- 检查是否已经有新的已经提交的数据，有的话就abort;
- 检查写操作是否有锁冲突，如果有冲突就abort;
- 将当前时间戳和值信息写到行信息上;
- 将primary行信息和时间戳记录到锁信息上，相当于加锁。NOTE：所有secondaries行都会记录primary lock到当前行;
- 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]。
参考
- Percolator 和 TiDB 事务算法
- 《Large-scale Incremental Processing Using Distributed Transactions and Notifications》
- 《A Critique of ANSI SQL Isolation Levels》
- Yes We Can! Distributed ACID Transactions with High Performance