数据库分布式事务

1. 前言
   CAP 性质, 所谓 “C” 即 Consistency（一致性，可以理解为写成功的数据，总是能读得出来），“A” 即 Availability（可用性，可以理解为少部分节点故障，对外服务不受影响），“P” 即 Partition tolerance（分区容错性，可以理解为节点之间发生了网络分区，无法通信，也不影响系统响应的正确性）。
   ACID，这个可以更正式地解释什么叫符合业务“预期”的结果。所谓 “A” 即 Atomicity（原子性，可以理解为一个事务内的所有操作，要么全部成功，要么全部失败，不存在中间状态），“C” 即 Consistency（虽说与 CAP 的 "C" 是一个单词，含义却完全不同：这里的 "C" 可以理解为数据完整性的约束，具体如下文所言，保持系统的 invariants），“I” 即 Isolation（隔离性，可以理解为并发事务之间，各自内部的操作状态对对方是不可见的），“D” 即 Durability（持久化，可以理解为一旦写成功的数据，不会因为进程 failover 等异常而导致状态丢失）。
   最终，一个成熟的分布式事务的实现通常需要考虑三部分：1）最上层的是原子提交协议，主流的自然是鼎鼎大名的 2 PC - 两阶段提交协议；2）中间层是并发访问控制协议，用于提升事务的并发读写效率；3）最下面的是基于共识的复制协议，保证服务的可容错性。
   [图片]
   事务的上述两类典型应用场景也分化出两大技术方向，其一者，旨在推行分布式事务的通用模型。在这个通用模型中，参与者是事务管理器（TM，Transaction Manager），资源管理器（RM，Resource Manager），甚至还有事务协调器（TC，Transaction Coordinator）。业界也沉淀了一系列有关 TM 与 RM 之间通信的接口协议规范，譬如 XA，TCC 等; 其二者 - 关于如何在一个分布式系统内实现不用数据分区之上的分布式事务。
   接下来，我们会先介绍实现分布式事务的标准范式 —— 2 PC，以及评估分布式事务等级最为重要的标准 —— Isolation；然后是一段进阶学习，如何通过引入多版本并发控制机制 —— MVCC，让分布式事务兼具优秀的隔离性以及良好的并发访问性能
2. 事务隔离
   2.1 事务隔离问题
   业界把并发事务可能导致的破坏系统 invariants 的典型行为归纳如下：
3. Dirty Write，脏写：两个并发事务，互相干扰，最终结果是两个事务各自覆盖了对方的一部分写，实际上两个事务均没有生效。脏写是被各种事务实现默认禁止的现象，这个是底线；
4. Dirty Read，脏读：该现象是 SQL-92 定义事务隔离级别时候列举的三大“现象”之一，即一个事务的中间状态被人读取到（这个事务尚不一定成功，最终可能会被回滚）；
5. Fuzzy Read，不可重复读：该现象是 SQL-92 定义事务隔离级别时候列举的三大“现象”之二，即一个事务中前后两次读取同一个数据记录，两次读取的结果不一样；
6. Phantom，幻读：该现象是 SQL-92 定义事务隔离级别时候列举的三大“现象”之三，即一个事务中针对同一条件多次查询一组数据，结果两次查询之间被其他并发事务新插入（或者删除）了数据记录，并且是满足查询条件的数据记录，这就导致查询结果集的数量发生了变化。幻读大多发生在范围查询、聚合、统计等业务场景；
7. Write Skew，写偏斜：根据相同的读记录集合，两个并发事务分别写了不相交的写记录集合，最终导致整体的系统 invariants 被打破。这里最经典的例子是医院排班，两个医生 A、B 同时看到今晚有人值班，然后俩人均以身体不适为由请假，最终导致晚上医院没人值班了。
   最理想的效果当然是并发事务之间的运行结果和串行执行结果完全一致, 这样也就能避免上述所有问题, 当然性能也是最差的, 业界使用串行隔离的有VoltDB，Etcd，ZooKeeper，这些软件均采用单线程来执行事务，继而提供了最为严格的隔离性保证。(注意, Redis仅单机串行, 不严格保证全局串行)
   2.2 2PC
   在 2 PC 实现中，通常存在两类角色，事务协调者（Transaction Coordinator）以及资源管理器（Resource Manager），前者负责收集并管理事务执行过程中状态，后者负责执行具体读写子任务。在2PC中, 第一步 Prepare 阶段事实上是在每个资源管理器留下有关事务的痕迹：一者是类似“锁”的痕迹，这样能够解决写-写冲突，甚至是写-读冲突；二者是数据记录的增量修改本身要留痕，但是这个留痕需要一方面要保证可全量恢复，另一方面在事务成功提交之前还不能被其它读请求“看到”。第二步 Commit 阶段的一个小巧思是面向失败的设计：假如本事务执行过程中被其他角色认为过期了，本事务的痕迹将被强制清理，故而本事务在提交之前务必检查一下痕迹是否依旧存在，检查通过方可提交。
   2.3 隔离级别
   传统意义上来说，事务有三大隔离级别，ANSI SQL-92 有详细定义，它们分别是:

8. 读已提交（Read Committed），它保证了读数据时只能读到已经提交的数据，从而没有所谓脏读现象。

   • 在Oracle 11g、PostgreSQL、SQL Server 2012、 MemSQL属于默认隔离级别
   • 常见实现是加行锁--记录锁和MVCC实现
   • 无法解决不可重复度

9. 可重复读（Repeatable Read），一个事务一旦开始，事务过程中读取的所有数据不允许被其他事务修改, 主要解决不可重复读。

   • 早期业界使用比较多的是 S2PL（Strict Two-Phase Locking），即通过引入读锁（S-Lock），写锁（X-Lock）来避免可重复读现象, 无论是 S-Lock，还是 X-Lock，在事务结束之前均不会释放导致效率问题
   • 一方面死锁概览增加, 需要额外死锁检测机制
   • 一方面读写相互阻塞也越来越明显

   • 对于幻读问题, 基于S2PL也可以加间隙锁, 即对对应索引区间加意向锁甚至锁整个范围, 问题是并发事务冲突概率会更高

     • 现有主流方案是使用MVCC实现--但是需要引入GC清理版本链
   • 每条事务带有版本号(全局递增时间戳)
   • 所有读请求返回版本号小于等于事务提交时间的数据版本

   • 对写请求总是创建新版本, 且需要新于所有并发读事务

     • 为了应对幻读, 主要看MVCC实现时的快照版本粒度, 是数据项粒度(会产生幻读)还是事务粒度
   • 如果事务执行过程读写请求只坚持一个版本号, 根据这个版本号读取, 那么可以规避幻读(每个事务开始获取start_ts, 读取只能看到commit_ts <= start_ts的版本)
   • 业界也称这种隔离级别为 Snapshot Isolation快照隔离--已经成为目前数据库领域主流的事务隔离级别
   • 无法解决写偏斜, 因为快照隔离仅保证写集不冲突
10. 可串行化（Serializable）, 系统中所有的事务以串行化的方式逐个执行，保障数据一致性，避免脏读、不可重复读、幻读、写偏斜等现象。
    2.5 总结
    MVCC+2PL代表的还是一种悲观加锁式的可串行化隔离技术, 所以还是存在死锁问题, 需要具备死锁检测能力, 相较于 MVCC + 2 PL 这种悲观加锁式的可串行化隔离技术，还有一种乐观式的可串行隔离技术 - SSI（Serializable Snapshot Isolation），SSI 提供了可串行化隔离，性能只比可重复读这一弱隔离级别的性能差一点儿(Dependency Serialization Graph 的技术，通过分析并发事务之间读/读，读/写，写/写之间的依赖关系，形成一个有向图，假如图中无环，那么这批事务就可以串行化调度)
    但是该方案工程实现比较困难, 目前已知的是PostgreSQL 和 CockroachDB 两大生产级数据库将 SSI 作为其可串行化隔离级别的事务实现机制。
11. MCVV
    MVCC ：数据库中维护的是一个一个逻辑对象，每个逻辑对象均维护了多个物理版本，这样就能够允许对同一对象的并行操作在不同的物理版本上进行。MVCC 管理对象的基本粒度是 Tuple（即元组，数据表中的一个单独记录或者行), 针对任一 Tuple，会存在一个逻辑对象与对应的 N 个物理版本实体。
    MVCC 机制下的一个 Tuple（元组）的物理版本的布局格式
    [图片]

3.1 MVTO: 写写冲突，读读不冲突，有写拒绝读，未来读拒绝当前写
MVTO = MVCC + Time Ordering，这个可谓 MVCC 最早的版本。

• 读: 当某个事务 T 要读一个逻辑 Tuple A，DBMS 将会检索其所有的物理版本，如果 T(id) 落在了某个物理版本的 [begin-ts, end-ts]，那么该物理版本就是事务 T 要访问的。如果写锁没有被其他事务持有, 就可以进行读取, 并更新Ax的read-ts为Tid(如果Tid比Ax当前read-ts大)

• 写: 写操作总是在 Tuple 最新的物理版本上实施（判断的依据是该物理版本的 end-ts 字段为 INF）需要满足下面两个条件:

  • 1）物理版本 B(x)的写锁没有被其它事务占据；
  • 2）本事务的序号T(id)大于物理版本 B(x)的 read-ts 字段。
  • 事务 T 将给物理版本 B(x)加写锁（相应的 txn-id 字段置为T(id)），然后创建一个新的物理版本 B(x+1)，同样也给物理版本 B(x+1)加写锁（相应的 txn-id 字段置为T(id)）。当最终要提交事务 T 的时候，DBMS 将把最新的物理版本 B(x+1)的 begin-ts 和 end-ts 分别置为T(id)和 INF，将上一个物理版本 B(x)的 end-ts 置为T(id)。另外，还需要把物理版本 B(x)和 B(x+1) 的写锁全部释放（txn-id 字段置 0）
    [图片]
    3.2 MVOCC: 写写冲突，读读不冲突，有写拒绝读，先决写拒绝乐观读。
    MVOCC = MVCC + Optimistic Concurrency Control, 即乐观锁思路:事务里面的读写操作先本地做，在正式提交 DBMS 的时候再做校验，这样也大幅压缩了事务持锁周期。
• 读: MVOCC 类似 MVTO，读请求需要根据事务序号 T(id) 落在某个物理版本的 [begin-ts, end-ts]，并且该物理版本 A(x) 的写锁并没有被其它事务持有，则 A(x) 进入 ReadSet
• 写: 写请求则是找到最新的物理版本（end-ts 字段为 INF），如果该物理版本 B(x) 的写锁没有被其它事务持有，则事务 T 将给物理版本 B(x) 加写锁（相应的 txn-id 字段置为 T(id)），然后创建一个新的物理版本 B(x+1)，同样也给物理版本 B(x+1) 加写锁（相应的 txn-id 字段置为 T(id) ），然后 B(x) 进入 WriteSet。

• 校验: 提交时, DBMS 再给事务 T 分配一个时间戳 T(commit)（用来给 WriteSet 中新创建的物理版本定义生命期，此值尽可能地新，以减少对并发读的干扰）

  • DBMS 会检查一下事务 T 对应的 ReadSet 中的各个 Tuple 的物理版本们，是否被更新了（被其它事务更新，并且人家事务已经率先一步完成提交）。
  • 检查通过，方可进入后续的「Commit」阶段，所有的 WriteSet 中的新创物理版本，B(x+1) 的 begin-ts 和 end-ts 分别置为 T(commit) 和 INF，将上一个物理版本 B(x) 的 end-ts 也置为 T(commit) 。另外，还需把物理版本 B(x) 和 B(x+1) 的写锁全部释放（txn-id 字段置 0）。

3.3 MV2PL: 写写冲突，读读不冲突，有写拒绝读，有读拒绝写
MV2PL = MVCC + Two-phase Locking，这个机制看名称就知道，悲观锁的流派, 增加了读锁的字段，read-cnt，用来记录当前有多少事务在读这个物理版本。

• 读: 根据事务序号 T(id) 落在某个物理版本的 [begin-ts, end-ts]，并且该物理版本 A(x) 的写锁并没有被其它事务持有，那么增加该物理版本的 read-cnt 数值，A(x) 进入 ReadSet。\
• 写: 还是找到最新的物理版本（end-ts 字段为 INF），如果该物理版本 B(x) 的写锁没有被其它事务持有并且其读锁也没有被其它事务持有（read-cnt 字段为 0），则事务 T 将给物理版本 B(x) 加写锁（相应的 txn-id 字段置为 T(id) ），然后创建一个新的物理版本 B(x+1)，同样也给物理版本 B(x+1)加写锁（相应的 txn-id 字段置为 T(id) ），然后 B(x) 进入 WriteSet。
• 提交时: DBMS 给事务 T 分配一个时间戳 T(commit), 所有的 WriteSet 中的新创物理版本， B(x+1) 的 begin-ts 和 end-ts 分别置为 T(commit) 和 INF，将上一个物理版本 B(x) 的 end-ts 也置为 T(commit) 。另外，还需要把物理版本 B(x) 和 B(x+1) 的写锁全部释放（txn-id 字段置 0）。此外，ReadSet 中各物理版本也需要逐个释放读锁。

[图片]

• 追加式: 即在需要更新一个元组（Tuple）时候，DBMS 直接在主表中申请一个新的空白数据行，然后将该 Tuple 最新版本的数据复制一份到新申请的数据行空间，最后将变更内容应用到新申请的这一行。

  • O2N（从老到新）：版本数据从老到新排列。索引项中指针指向的是该 Tuple 最老的版本数据，因此当有 UPDATE 操作时，索引项中指针指向无需更改，代价则是每次获取较新的版本数据需要遍历整条链表；

    • 效率高度依赖GC机制, 如果垃圾回收能够将单链表维持在较短长度，那么查询性能将有显著提升

  • N2O（从新到老）：版本数据从新到老排列。索引项中指针指向的是该 Tuple 最新的版本数据，因此当有 UPDATE 操作时，索引项中指针指向需要更改，收益则是可以很快获取到较新的版本数据，无需遍历整条链表；

    • 索引项指针频繁修改问题, 思路正如 Bw-Tree/Bε-tree 的优化：通过引入一个间接指向层，采用一个叫做 MappingEntry 的对象的值来指向某个 Tuple 版本数据链表的起点, 当某个 Tuple 的新版本数据产生时，只有这里间接指向层的 MappingEntry 对象记录的值需要改变，而索引项中指向 MappingEntry 的指针则不需要变更。这种优化极大利好拥有较多 SECONDARY INDEDX 的表
      [图片]

• 增量式: 该机制为版本数据存储维护两张表：一曰主表（Master Table），一曰增量存储空间（Delta Storage），索引项指针指向主表中的版本数据（业界通常的实现，主表维护的是最新版本数据），然后将版本数据链条上其它版本数据（以增量日志方式）存储在额外的 Delta Storage 空间。例如，业界的 MySQL InnoDB 和 Oracle 实现中，Delta Storage 具体是指用于 rollback 的数据段。故而，在更新逻辑数据行时，DMBS 先在 Delta Storage 申请一段空间，然后将被改动的属性的老版本数据写入其中，注意，这里不需要写入完整 Tuple 行。最后 DMBS 再在主表上原地更新（注意！这里是原地更新！） Master 版本的数据行。

  • Delta Storage 在执行某个 Tuple 的 UPDATE 操作时，表现会很出色，特别当 UPDATE 只是操作了数据行的子集属性（这个很常见的），这样 Delta Storage 就大大减少了内存的分配占用，并且也不存在外联数据版本（TEXT/BLOB 等类型）存储量过大问题。
  • 在读为主的场景中，为了获得 Tuple 的某个版本数据，DMBS 需要从各个字段的版本数据链中获取到对应版本的字段值（需要频繁访问 Delta Storage），然后再进行拼凑，这就就带来了额外的访问开销。
    [图片]
    综上所述, 追加式（Append-only）存储机制在分析场景表现更佳，因为其将版本数据存储在连续空间，这样当进行大范围的扫描时可以有效提升缓存命中率，包括对于配合硬件的预读优化也很友好。追加式存储机制给索引管理系统暴露的是实际的物理版本，这样的索引管理预留了优化空间（例如上文提到的间接指向层，避免频繁修改索引项指针）。
    无论是 Append-only，还是 Delta Storage，这些版本存储机制都要求 DBMS 从中心化的数据结构（Main table、Delta Storage）为每个事务分配内存。为了避免并发访问竞争，DBMS 可以对每个集中式的存储结构分而治之，所谓数据分区也，然后各自维护一系列单独的内存空间。这样，每个工作线程从单独的存储空间获取内存，因此可以消除此间的集中式访问竞争。
• GC
  MVCC 机制在执行事务 UPDATE 操作时候就会创建 Tuple 新的物理版本，所以垃圾回收至关重要, 通常我们可以把 GC 机制分成三步：

• 找到已过期的物理版本；

  • 被已中止的事务创建
  • 该物理版本不存在于任何其他事务的select范围内(DBMS会检查物理版本的end-ts标记, 如果小于所有活跃事务id, 即已经过期)
• 将这些过期的物理版本从相应的 version chain 中移出，必要的话还要从索引项的指针指向上移除；
• 回收这些物理版本的存储空间；
  为了记录所有活跃事务的id, 所以DBMS还是需要一个中心化存储这些信息, 为了强化性能, 一个常规优化是引入粗粒度的epoch, 每个事务创建时不仅分配一个递增的事务id, 还会分配一个active epoch值(由DBMS维护在一个FIFO队列中), 每个epoch记录关联事务的个数, 如果某个事务完成(正常or中止), epoch计数器减1, 如果DBMS在以下条件会回收该epoch关联的物流版本:
• 处于非活跃状态
• 事务计数器为0
• 前序epoch不持有任何活跃事务
  那么现在只剩如何清除过期版本了, 即如何遍历:

• 基于元组粒度: 通常 DBMS 会引入背景线程周期性地扫描数据库以检测出 Tuple 的过去物理版本, 该机制虽然简单但是效率不高，GC 性能在数据量增长时无法同步提升。(当前基于 MVCC 的 DBMS 中最常用的 GC 方案)

  • 业界比较好的实践是让 DBMS 维护一个 bitmap，映射发生过数据改动的 BLOCK（Tuple 元组旧的物理版本产生了，该版本将进入 GC 视野），这样 GC 的背景线程就可以跳过上一次 GC 以来没有发生过数据变更的 BLOCK，提升扫描效率。
  • 还有一种是DBMS 在执行事务的时候，本身就会遍历 version chain。这个过程中，worker thread 顺带就把过期的物理版本识别出来，记录在一个全局的数据结构中, 这样 GC 背景线程就不需要亲自下场揪出过期版本了。(不过，这种遍历机制只是跟 Append-only (O2N) 比较搭配，因为这种存储机制就是从 Tuple 最旧的物理版本开始遍历的，不会漏掉本 Tuple 已过期的版本)
    [图片]

• 基于事务粒度: 当该事务创建的所有物理版本对于现有活跃事务均不再可见（这个判断条件，前面说过，看 end-ts）如果一个 epoch 关联的所有事务均已过期，也即该 epoch 时代结束，而一个 epoch 时代结束意味着该 epoch 期间所有事务产生的所有物理版本均可以被安全清理。

  • DBMS 不能仅仅跟进每个 epoch 相关的活跃事务个数了，而要关心每个 epoch 其中的每个事务的 WriteSet, 复杂度比较高。
    [图片]
    如果存在长事务，DBMS 的性能会有较大影响，因为长事务意味着它开始之后的所有版本数据都得不到清理，这时候版本数据链就会变得很长，直到长事务完成或者被中止掉。
• 索引管理
  所有支持 MVCC 的 DBMS 都将版本数据和索引数据分开存储。我们可以将索引看作 KEY-VALUE 键值对，键是被索引的数据行中的字段值，值是索引对应的数据行的指针。
  在主键索引中, 由于主键总是不变的, 因此索引的 Value 总是指向版本数据链的起点, 在主键索引中, 索引键值对指针变更也和DBMS的版本数据存储方式相关:
• 对于 Delta 存储，主表永远都是存的 master 版本数据，它是原地更新的，主表中数据行位置不发生改变，因此索引项 Value 记录的指针也没有发生改变；

• 对于 Append-only 存储，版本数据链有两种不同方向：

  • O2N（从老到新），新的版本数据 Append 在版本链的末端，因此索引的 Value 指针始终指向链表的起点不变。只有在发生 GC 的时候才会调整指针地址；
  • N2O（从新到老），每当产生新版本时，都需要调整索引值的指针，此时 DBMS 一般会在索引上进行 DELETE & INSERT 操作；
    对于二级索引, 由于历史版本的存在, 索引Value可能发生改变, 通常来说会用一些方法减少管理的复杂度:
• 逻辑指针: 建立中间表, 保持索引Value不变, 例如指向主键(InnoDB), 所以如果表存在许多二级索引, 那么优化收益就很明显, 不需要频繁变更, 只需要变更主键索引指向, 当然读的话需要根据主键索引回表。
  [图片]
• 物理索引: DBMS也可以为二级索引的指针记录实际元组地址, 这种只适合Append-only 的版本存储机制，当更新表中的某个 Tuple 的时候，DBMS 会更新所有相关二级索引的指针指向（一个二级索引，甚至可以对应多项物理指针）。优点是查询方便读取效率高, 缺点是管理复杂。
  [图片]
  Uber 的工程师对 Postgres 吐槽点满满，原因即在于 Postgres 使用了物理指针管理二级索引，在使用过程中，Uber 的应用场景里会有非常多的二级索引，并且 Postgres 的二级索引是指向磁盘中的版本链起点的，故而在版本链起点发生变动时，多个二级索引的指针均需要修改，这个行为对于 Uber 写多读少的负载访问性能影响很大。最终，Uber 做了个决定，从 Postgres 迁移至 MySQL（有趣的是，Uber 起初使用的就是 MySQL，然后招募了一群熟悉并且热衷 Postgres 的工程师们，最后 ...... ）
• 业界方案
  6.1 Percolator
  Percolator 诞生的原因很朴素：Google 搜索的索引系统需要存储数十 PB 的数据（注：这个是 2010 年甚至更早时间的数据），传统的关系型数据库承载不了如此规模的存储量，故而 Bigtable 这类具备良好水平扩展性的 NoSQL 数据库便应运而生, 但是Nosql数据库对SQL检索的支持和事务能力比不上关系型数据库, BigTable只支持单行事务, 所以需要拓展, 故而谷歌工程师抽象Percolator, 支持跨机器的多行分布式事务。
  [图片]
  从数据模型角度, BigTable可以理解为一个稀疏多维的键值对, 一个键值对格式如下, 一个row可以包含多个column
  [图片]
  为了实现跨行的分布式事务, Percolator中一列"c."在bigTable就映射"c:lock","c:write","c:data"等多列, 其中lock是持久化的锁, write可以认为是数据最新可见版本, data即数据本身。
  [图片]
  Percolator 事务实现是标准的两阶段提交，分为 Prewrite 和 Commit 两阶段。在每个 Transaction 开始时会从 TSO 获取 timestamp 作为 start_ts，在 Prewrite 成功后 Commit 前，再从 TSO 获取 timestamp 作为 commit_ts。另外，在最终调用 Commit 之前，Transaction 的所有数据都缓存在客户端。
  [图片]
  6.1.1 写
• 事务开启时，即从 TSO 获取一个 timestamp 作为 start_ts_；
• 选择第一个 Write 请求作为 primary，其它 Writes 请求则是 secondaries；

• 先 Prewrite primary，成功后再继续 Prewrite secondaries。注意，为什么首先 Prewrite primary，这是有讲究的，后面 Failover 章节会详细解释。对于每个 Write 请求，以 Bigtable 行事务形式执行的 Prewrite 的逻辑如下：

  • 以 Write.row 作为 key，检查 Write.col 对应的 “write” 列在 [start_ts, ∞] 之间是否存在数据。如果存在，则说明存在写/写冲突，直接中止整个事务；
  • 以 Write.row 作为 key，检查 Write.col 对应的 “lock” 列是否被上锁，如果锁存在，直接中止掉整个事务。这种做法略显粗暴，不过确实简单有效；
  • 以 start_ts_ 作为 Bigtable 的 timestamp，将数据写入 “data” 列。由于此时 write 列尚未写入，因此数据对其它事务不可见；
  • 以 start_ts_ 作为 Bigtable 的 timestamp，以 {primary.row, primary.col} 作为 value 写入 “lock” 列。注意，这里一个事务内的所有写请求的 “lock” 列记录的都是 primary 信息，具体解释见 Failover 章节；
• 如果一个事务内的所有 Write 请求均能够 Prewrite 成功，则进入 Commit 阶段，再次从 TSO 获取一个 timestamp 作为 commit_ts；

• 先 Commit primary，注意，这里同样以 Bigtable 行事务能力执行，如果失败则中止整个事务：

  • 以 primary.row 作为 key，检查 primary.col 对应的 “lock” 列的锁是否存在，如果锁已经被其它事务清理，则本事务失败；
  • 以 commit_ts 作为 Bigtable 的 timestamp，以 start_ts_ 作为 value 写 “write” 列。相关的读请求会先读 “write” 列获取 start_ts_，然后再以 start_ts_ 去读取 “data” 列中数据；
  • 以 primary.row 作为 key，删除 primary.col 对应 “lock” 列中对应的锁；

• 到了这里，该事务事实上已经成功，对于剩余的 secondaries，异步的进行：将 start_ts_ 作为 value 写 “write” 列；删除 “lock” 列中对应的锁。不用担心，本事务所有写操作的可见性已经没有问题，secondaries 的这里的异步操作也一定会成功，这正是引入 primary lock 精巧之处；

  • 下次有读操作访问该 secondary 时，会发现 lock 存在，于是去查 primary。
  • 发现 primary 已提交 → 帮助完成该 secondary 的提交（写 write + 删 lock）。
  • 这种机制称为 “lazy cleanup” 或 “recovery by readers”。

6.1.2 读

1. 事务开启时，即从 TSO 获取一个 timestamp 作为 start_ts_；
2. 读请求同样依赖 Bigtable 的行事务能力。首先，其以 row 作为 key，检查 column 对应的 “lock” 列在 [0，start_ts] 区间是否存在锁，如果有，那么就等待并根据需要在必要的时候主动清理锁。反正要等到这里的锁释放了，继而可以放心地基于 Bigtable 的行事务能力做干净的读；
3. 以 row 作为 key，检查 column 对应的 “write” 列在 [0，start_ts] 区间是否存在数据：如果没有，那么说明没有读到数据；如果存在，则根据 timestamp 的指示，到 “data” 列读取相应版本的数据；
   6.1.3 失败
   Percolator 的事务执行过程可能面临两类错误：一类是底层 Bigtable 的 TabletServer 错误，这个无需 Percolator 多虑，Bigtable 作为一个分布式系统本身能够处理并自愈，坚决保证锁信息的持久化；另一类比较棘手，是 Client 遭遇了错误，残留了一些锁信息，阻碍后续的其它事务请求，对于这种情况Percolator 的方法比较朴素，采用了一种异步清理机制。
   假如事务 A 在执行过程出了问题，Client 挂了，残留了某些锁信息。事务 B 在执行过程需要加锁，遇到了冲突, 如果B确定A事务失败, 就可以主动清理锁, 问题是如何检测, 这里就会使用上文提到的primary lock(每个事务都选择一个写请求对象（默认就选择第一个）作为提交（commit）与清理（cleanup）的同步点（synchronizing point）)
4. 事务 A 提交之前，一定检查一下它是否继续持有 primary lock；

5. 事务 B 做清理之前，也一定要先检查 primary lock 是否还在，如果在，就可以安全清理；

   • 事务 A 的 Client 挂掉的时机已经过了 commit point，也就是至少 primary write 已经提交，那么事务 B 就有义务继续推进事务 A
   • 另一种情形，事务 A 的 primary 对应的 “lock” 列还在，事务 B 可以确定此时事务 A 还没有提交，可以安全地回滚。
   • 其他: 虽然 Percolator 提供的清理机制，从安全性上没啥问题, 但如果事务A只是阻塞会导致业务侧不必要的重试, 所以Percolator 探索了一些探活机制，Percolator 中每个 worker 也向 Chubby 写一个 token，通过定期心跳续活，过期则自动被 Chubby 清理掉。故而其它 workers 可以通过观察某个 worker 的 token 文件来判定它是否处于存活态。

   6.1.4 隔离性
   Percolator 事务的默认隔离级别是 Snapshot Isolation，自然可以解决“脏读”，“不可重复读”等问题，但是对于“幻读”，“写偏斜”等问题，Percolator 无法直接避免。

6.2 Tidb
Tidb的事务, 比较类似Percolator, 当一个事务在会话中启用后, 所有读写都会基于MVCC机制访问数据, 写入的内容缓存在事务内存里, 直到收到commit语句, Tidb Server开始使用Percolator的两阶段事务协议将更改提交到TiKV。

[图片]

• 并发地发送 Prewrite 请求给 TiKV，并等待全部响应；
• 从 TSO 再次获取时间戳，作为提交阶段的时间戳标记（Commit TS）；
• 完成 primary key 的提交；
  [图片]
  这种机制的关键困难在于: 一, 如何确认所有的keys都已经完成了prewrite请求, 二, 如何确认一个事务对应的Commit TS, 目前Tidb的机制如下:
• 第一: 在引入异步提交改动前, 整个事务的状态可以通过primary key的状态确定, 所有的secondary keys也保存了指针指向primary key, 引入异步提交后, primary key也需要存储所有secondary keys指针(原先只要确认primary key的lock列是否存在即可确认状态, 现在需要多检查一步secondary keys的状态) 因此Tidb要求事务中包括的Keys数量不能太多, 否则primary可能被压垮, 在Tidb实现中, 异步提交事务最大支持256keys, key大小不能超过4096字节。
  [图片]
• 第二: 如何确认一个事务对应的Commit TS, 事实上Tidb事务支持Snapshot Isolation, 以及Serialization Isolation两种选择, 所以这里Commit TS计算很有讲究。具体Tidb实践是, 每个数据项引入应该Max Ts属性, 每次事务读取会拿自己的事务时间戳更新这个值, 因此对于一个恢复中的事务, Tidb Server会收集事务中各数据项的Max TS, 取最大值加一(为了支持RR), 这个值与TSO获取的时间戳对比, 取最大作为Commit TS(尽可能避免被其他读事务被阻塞)。这样可以保证Failover 恢复的事务不会打破快照隔离, 因为当前本事务确认的Commit TS大于以往所有事务读的时间戳。

参考: https://mp.weixin.qq.com/s/-4xY1A5Qd5KpJDX8KUJGSA