---
Percolator 事务隔离级别SI
Percolator提供跨表、跨行的分布式事务，隔离级别为快照隔离（snapshot-isolation）。快照隔离级别中，如果两个事务同时修改同一个行，那么事务冲突，其中一个事务必须回滚然后重试。
传统的数据库定义了 4 种隔离级别（RU、RC、RR、Serializable），但是随着技术的不断发展，上面4种已经不能完全包含所有的隔离情况，所以出现了的snapshot isolation(快照隔离)。快照隔离多采用mvcc实现，记录事务开始的时间点，将这个时间点之前的数据看作是一个快照，所有读操作都只读取该时间点之前的数据。当然本次事务中update/insert/delete的操作对本次事务也是可见的。但是该事务之后新的事务所产生的数据对本次事务是不可见的(并发场景下)。
快照隔离中读操作不涉及锁操作，所以一定程度了提高了性能。但是快照隔离引出了一个新的问题: 写偏斜（write skew），快照隔离可能会造成数据的不可串行化（non-serializable），进而导致数据的不完整性。
例如：一个银行客户有一个支票账户 X 和一个储蓄账户 Y ，当从支票账户中取款的金额超过了该账户的余额时就会自动从储蓄账户转账过来，约束条件为 X + Y >= 0 初始化值为 X = 50, Y = 50 假设事务 T1 和事务 T2 操作的顺序如下：
T1: r1(x, 50) r1(y, 50) w1(x, -20)c1
T2: r2(x, 50) r2(y, 50) w2(y, -40)c2
由例可知，T1 和 T2 为并发事务。当 T1 提交时计算 X + Y = (-20) + 50 = 30; 当 T2 提交时计算 X + Y = 50 + (-40) = 10, 因此在快照隔离条件下，两个事务都符合完整性约束条件，可以正常提交，然而提交 T1 和 T2 后的结果是 （-20）+ （-40）= -60, 违反了完整性约束条件，这种现象称为写偏斜。
2PC 提交延时扩大
导致一个 Percolator 事务提交延时很大的主要原因是：一个事务 T 在提交期间，需要再次更新它插入、更新、删除的每一行，写上提交时间戳(commit-ts)并且去除锁信息。相比 OLTP 的 DBMS 提交时间扩大，因为通常一个事务插入、更新的行可能有很多，在正常的事务 insert/update/delete 语句修改过这些行之后，还要在事务提交时刻再次修改一遍，这涉及到 buffer pool 可能要重新把这些行所在的页从外存装入内存，然后逐行获取行锁然后修改，并且这些修改仍然要记录事务日志，并且提交本地事务时候还要再次刷盘。这样，事务提交延时就会更大。对于 2PC 来说，上述这些开销一样都少不了。
写热点数据的并发性损失
由于没有事务管理器维护事务状态，当客户端宕机后，它遗留的未开始提交的事务持有的锁，以及一个事务因为写冲突而 abort 后它持有的锁，都要到事务超时后，才能被其他事务的 read 操作清除，这就增加了其他并发执行的事务发生写冲突被回滚的几率，从而降低了系统并发性，浪费了系统资源。
另外，percolator 的‘锁’(乐观锁)，其实不是真正的事务锁，因为它并不能导致试图获取锁的事务阻塞等待这个锁，也不能在持有锁的事务放锁（通常是结束时）时调度等待的事务获取锁继续执行。Percolator 的锁只是一个‘被修改的标志’，一旦事务 T1 要修改一行 X 却发现它已经被 T2 锁住了，T1 就只能回滚了，无法在锁上面阻塞等待 T2 结束后再继续。
也就是说 Percolator 的读写都是用 mvcc 做并发控制的，与 PostgreSQL 相同。这带来的问题就是如果大量并发事务更新热点数据，那么系统 TPS 会很低，只能排队执行并且发生大量事务回滚。对于 Google 的 web index 数据来说，可能没有热点行，但是对于通用的 DBMS 来说，热点数据是经常会出现的。
读数据的并发性损失
Percolator 的数据行可见性判断也与传统的 MVCC 有所不同，这导致它读取数据行也可能需要等待，从而损失了并发性能。要知道 MVCC 最重要的优点就是读操作不阻塞，以确保读的性能。
传统 DBMS 的 MVCC 中，一个事务 T1 的 snapshot 记录的是它‘拍’这个快照时刻活跃事务的集合，通常以这样的方式表示：{ts-min, ts-max}, [ative-t0, active-t1... Active-tN]，这里 ts-min 表示比 ts-min 小的事务全部已经提交（所以 T1 必然可以看到它们的改动）， ts-max 表示比 ts-max 大的一定还没有启动（所以 T1 必然无法看到它们的改动）， active-ti 数组中是活跃的事务 id 列表，这些事务的改动 T1 也是看不到的。如果一个事务 T2.id 在此快照中（即 T2.id 在数组中或者 T2.id > ts-max），那么 T1 看不到 T2 生成的行版本，否则 T1 可以看到 T2 生成的行版本。
而 Percolator 事务模型中，按说其 MVCC 可见性判断应该是给定事务 T1,T2，当且仅当 T2.start-ts > T1.commit-ts，T2 才能看到 T1 的改动。但是从 Get() 函数的伪代码以及论文中的描述来分析判断，实际情况似乎是如果 T2.start-ts > T1.start-ts，那么 T2 就 *应该* 看到 T1 的改动。于是，当 T2 需要读取 1 行的时候发现其 lock 字段的可见的版本有锁（此时该版本必然是最新版本并且其write record 必然还没有写入 commit-ts），T2 就要等待 T1 提交后再读取。此时 T2.start-ts 与 T1.commit-ts 的大小关系哪个大都有可能。总之这样等待就会损失并发性。为什么这种情况下 T2 不去读取那个最新的已提交的行版本呢？ 我认为这才是正确的做法，这样做也才能让 write record 的 commit-ts 有意义。
之所以需要在每个行提交时刻写入 commit-ts，还是因为 Percolator 事务没有全局的事务管理器，每个客户端存储着自己的事务状态。所以系统无法获知此刻有哪些活跃的事务，也就无法为事务创建快照，只能在行中写入提交时间戳，才能做 MVCC 读。
网络通信开销较大
一个 Percolator 事务执行过程中，有大量的跨节点网络通信，具体来说包括：获取两次事务 timestamp(start-ts, commit-ts)，每次写入一行时与 Bigtable 系统的通信（Bigtable 本身也是一个分布式的，所以实际每写一行的网络通信很可能会更多）。事务提交时，每一行要再次写 Bigtable，通信开销翻倍。为了降低通信成本，合并了对同一行多个字段（比如写行时写入 lock 和 data 字段, 提交时清除 lock 字段和写 write record）的更新操作为单一的调用，如果没有这个优化，那么通信成本还要再次翻倍。另外，每次要读取一行时，如果 lock 字段是指向 primary row 的指针，那么还要再次读取 primary row 的 lock 字段。要 知道一个事务只有 1 个 primary row，其余写入的行都是 secondary row，也就是说大概率一旦行上面有锁，就需要再多一次网络通信（读取这行对应的 primary row 的 lock 字段）。
清理无效行的开销（GC）
Percolator 系统还需要一组 purge 后台进程，把那些被标记为删除或者过期的数据（根据行版本的commit-ts来判断）的行版本 GC 掉。由于行的所有版本都是存储在 Bigtable 系统的数据表中的，所以后台的 purge 任务也会对 Bigtable 系统构成很大的负载。这个问题是 PostgreSQL 也有的问题。Innodb没有这个问题是因为数据表上面永远只有最新版本的行，老版本的行是通过undo日志临时生成的。Innodb Undo 日志集中存放在 undo 表空间中，清理的代价要低很多。
