1. 简介
单机数据库事务是在⼀个节点上完成的，分布式数据库事务需要多个节点协调完成。为了满⾜ ACID，分布式数据库在实现事务时需
要考虑更多复杂因素。
两阶段提交（two-phase commit）是⼀种⽤于实现跨多个节点的原⼦事务提交的算法，即确保所有节点提交或所有节点中⽌。
2. Percolator
这⾥介绍⼀个有代表性的 2PC 模型：Percolator。
2.1 背景
Percolator 是⾕歌在 2010 发表的论⽂ «Large-scale Incremental Processing Using Distributed Transactions and Notifications»
介绍的分布式事务协议。
Percolator 构建在 Bigtable 之上，利⽤ Bigtable 的单⾏事务能⼒和 TSO 实现了 Snapshot Isolation 隔离级别的跨节点多⾏事务。
⽤⼾指定的 Percolator 中的⼀个 Column 在 Bigtable 中会映射到如下多个 Column：
lock 列⽤于存储锁信息，write 列⽤于存储已提交的 start_ts，data 列⽤于存储 value。
2.2 事务流程
Begin
⼀个事务开启时会从 TSO 获取⼀个 timestamp 作为 start_ts。
Set
事务的所有 Write 在提交之前都会先缓存在内存，然后在提交阶段⼀次性写⼊，这种⽅式称为 Buffering Writes until Commit。
Get
事务在读取时，需要先检查对应 lock 列在 [0, start_ts) 之间是否存在锁信息。如果锁存在，则检查锁是否过期，如果过期则
cleanup锁，否则阻塞。如果锁不存在，先读 write 列在 [0, start_ts) 之间最新的 start_ts 作为可⻅最⼤版本，再读 data 列的可⻅
最⼤版本数据并返回。
Commit
1. Phase 1: Prewrite
a. 选择⼀个 Write 作为 primary，其它 Write 则是 secondaries；primary commit 作为事务提交的 commit point。
b. 先 prewrite primary，成功后再 prewrite secondaries。对于每⼀个 Write：
i. 检查对应的 write 列在 [start_ts, ∞) 之间是否存在数据。如果存在，则说明有 write-write conflict，直接 abort 整个事
务。
ii. 检查对应的 lock 列在 [0, ∞) 之间是否存在锁信息。如果存在，直接 abort 整个事务。这种冲突处理⽅案避免了死锁的发
⽣。
iii. 以 start_ts 作为 timestamp，对 Write 上锁：以 {primary.row, primary.col} 作为 value，写⼊ lock 列。并将数据写⼊
data 列。由于此时 write 列尚未写⼊，因此数据对其它事务不可⻅。
2. Phase 2: Commit
a. 从 TSO 获取⼀个 timestamp 作为 commit_ts。
b. 先 commit primary , 如果失败则 abort 事务。
i. 检查 primary lock 是否存在，如果已经被其它事务清理（事务超时可能导致该情况），则 abort 整个事务。
ii. 以 commit_ts 作为 timestamp，先以 start_ts 作为 value 写 write 列，再删除 lock。
c. 步骤 b 成功意味着事务已提交成功，此时可以返回事务提交成功，再异步 commit secondaries。
2.3 举例
下图表⽰ Alice 向 Bob 转 $7 的过程：
2.4 ⼀些问题
2.4.1 写热点⾏问题
1. 当客⼾端宕机后，他会遗留未开始提交的事务持有的锁，⽽这个锁都要到事务超时后，才能被其他事务的读操作清除，这就增加
了其他并发执⾏的事务发⽣写冲突被回滚的⼏率。
2. 另外还存在活锁的情况，就是 T1 和 T2 相互冲突来回取消。
对于 google 的 web index 数据来说，可能出现热点⾏的⼏率较⼩，但是对于通⽤的 DBMS 来说，热点⾏是经常会出现的。
2.4.2 写阻塞读问题
Percolator 的设计下，当⼀个读事务遇到 lock 的时候需要等待 resolve lock 之后才能进⾏读取，否则可能会破坏快照隔离。因为有
可能读的时候有其他已经获取了 commit_ts 且⼩于这个读事务的 start_ts，但 commit 操作还未完成。核⼼原因是：从 TSO 取
commit_ts 和 commit 操作这两个步骤并不是原⼦的。
