数据库内核月报

数据库内核月报 － 2018 / 11

Database · 原理介绍 · Google Percolator 分布式事务实现原理解读

Author: yicong

前言

Percolator 是谷歌在2010发表的论文«Large-scale Incremental Processing Using Distributed Transactions and Notifications» 介绍的分布式事务协议。本文是对该协议的解读，忽略了论文中和分布式事务无关的其他部分；侧重于完整的介绍其分布式事务的并发控制协议和 failover 的细节，并阐明细节背后的原理。

背景

Percolator 是在 Bigtable 之上实现的，可以说是为 Bigtable 定制的，它以 Client library 的方式实现。Percolator 利用 Bigtable 的单行事务能力，仅仅依靠客户端侧的协议和一个全局的授时服务器 TSO 就实现了跨机器的多行事务。

Bigtable 是谷歌在[2]中介绍的一个分布式的结构化数据存储系统，它被设计用来处理海量数据，按[2]的描述，在那个年代集群的规模就达到数千台机器，存储规模达到 PB 级。

从数据模型的角度，Bigtable 可以理解为是一个稀疏的，多维的持久化的键值对Map，一个键值对的格式如下：

` (row:string, column:string,timestamp:int64)->string`

key 是行关键字（row），列关键字（column），以及时间戳（timestamp）的组合，value 是任意的 byte 数组。

在 Bigtable 中，一行 row 可以包含多个 column，Bigtable 提供了针对单行的跨 column 的事务能力，Percolator 中多处利用了 Bigtable 单行事务来保证对同一个 row 多个操作的原子性。

Percolator 通过一个全局的授时服务器 TSO 给予事务一个全局的时间戳来解决分布式环境下事务的全局时序问题；通过经典的两阶段提交来解决分布式事务原子提交的问题。Percolator 不仅仅是一个改进版的两阶段提交，它涵盖的内容更多，可以认为是一个完整的分布式事务解决方案，它还包括了依据全局时间戳实现 Snapshot Isolation 隔离级别的并发控制协议，并给出了在故障发生如何进行自动 failover 的细节。

架构

Percolator 包含三个组件：

  1. Client：Client 是整个协议的控制中心，是两阶段提交的协调者（Coordinator）。
  2. TSO：一个全局的授时服务，提供全局唯一且递增的时间戳 （timetamp）。
  3. Bigtable：实际持久化数据的分布式存储

Percolator Client 对外暴露的接口和 Bigtable 一样，一个写（Write）格式如下：

Write{Row row, Column col, string value}；

可以把 {row, col} 理解为 user key，一个事务可以包含多个 Write。 Write 所在事务的 timestamp 作为 Bigtable 键中的 timestamp; Transaction 的 timestamp 都由 TSO 统一授予。用户指定的 Perocolator 中的 Column 在 Bigtable 中会映射到如下多个 Column： Percolator-存储格式.png lock 列用于存储锁信息，data 列用户存储 value，write 列用于存储 Commit 的 timestamp 以及标记该行已经 Committed。

流程

一个事务的所有 Write 在提交之前都会先缓存在 Client，然后在提交阶段一次性写入；Percolator 的事务提交是标准的两阶段提交，分为 Prewrite 和 Commit 。在每个 Transaction 开启时会从 TSO 获取 timestamp 作为 start_ts，在 Prewrite 成功后 Commit 前从 TSO 获取timestamp 作为 commit_ts。协议伪代码如下图：

Percolator 协议.png

Prewrite

  1. 在事务开启时会从 TSO 获取一个 timestamp 作为 start_ts。
  2. 选择一个 Write 作为 primary，其它 Write 则是 secondary；primary 作为事务提交的 sync point 来保证故障恢复的安全性（详情见 Failover 章节）。

  3. 先 Prewrite primary，成功后再 Prewrite secondaries；先 Prewrite primary 是 failover 的要求（详情见 Failover 章节）。 对于每一个 Write:

    ​ 3.1. Write-write conflict 检查： 以 Write.row 作为 key，检查 Write.col 对应的 write 列在 [start_ts, max) 之间是否存在相同 key 的数据 。如果存在，则说明存在 write-write conflict ，直接 Abort 整个事务。 ​
    ​ 3.2. 检查 lock 列中该 Write 是否被上锁，如果锁存在，Percolator 不会等待锁被删除，而是选择直接Abort 整个事务。这种简单粗暴的冲突处理方案避免了死锁发生的可能。 ​
    ​ 3.3. 步骤 3.1，3.2 成功后，以 start_ts 作为 Bigtable 的 timestamp，将数据写入 data 列。由于此时 write 列尚未写入，因此数据对其它事务不可见。 ​
    ​ 3.4. 对 Write 上锁：以 start_ts 作为 timestamp，以 {primary.row, primary.col} 作为 value，写入 lock列 。{Priamry.row, Primary.col} 用于 failover 时定位到 primary Write。

对于一个 Write，3 中多个步骤都是在同一个 Bigtable 单行事务中进行，保证原子性，避免两个事务对同一行进行并发操作时的 race；任意 Write Prewrite 失败都会导致整个事务 Abort；Prewrite 阶段写入 data 列的数据对其它事务并不可见。

Commit

如果 Prewrite 成功，则进入 Commit 阶段：

  1. 从 TimeOracle 获取一个 timestamp 作为 commit_ts。

  2. 先 Commit primary , 如果失败则 Abort 事务：

    ​ 2.1. 检测 lock 列 primary 对应的锁是否存在，如果锁已经被其它事务清理（触发 failover 可能导致该情况），则失败。 ​
    ​ 2.2. 步骤 2.1 成功后以 commit_ts 作为 timestamp，以 start_ts 作为 value 写 write 列。读操作会先读 write 列获取 start_ts，然后再以 start_ts 去读取 data 列中的 value。 ​
    ​ 2.3. 删除 lock列中对应的锁。

  3. 步骤 2 成功意味着事务已提交成功，此时 Client 可以返回用户提交成功，再异步的进行 Commit secondary 。Commit seconary 无需检测 lock 列锁是否还存在，一定不会失败，只需要执行 2.2 和 2.3。

Snapshot Isolation

Percolator 实现的隔离级别是Snapshot Isolation，Snapshot Isolaton 是一种在多个数据库被广泛采用的隔离级别，它最早见于数据库领域的经典论文 [3]，从隔离性的角度完胜 Read-Committed，和 Repeatable-Read 互有胜负，Snapshot Isolation 存在写偏斜（Write-skew） 但是不存在幻读（Phantom）, 而 Repeatable-Read 正好相反。在介绍 Percolator 如何保证 Snapshot-Isolation 之前先来看 Snapshot Isolation 的要求，根据 [3] 的描述，Snapshot Isolation要求：

  1. 当一个事务 T1 准备提交时获取一个 Commit-timestamp（commit_ts），大于所有已存在的 Commit-timemstap 和 Start-timestamp（start_ts）。
  2. First-committer-wins。一个事务T1能够提交成功当且仅当在[T1.start_ts, T2.commit_ts] 范围内不存在另一个事务T2，T2 和T1 修改了同一行，T1.start_ts < T2.commit_ts < T1.commit_ts，即 T2 在 [T1.start_ts, T1.commit_ts] 之间提交，且T2提交成功。不然 T1 应当 Abort。
  3. Snapshot-read。事务的读操作都满足 Snapshot-read：即对于一个事务T1而言，所有 commit_ts <= T1.start_ts的事务的修改都对T1可见，所有commit_ts > start_ts的事务的修改都对T1不可见。

Percolator 的 start_ts 和 commit_ts 都由全局 TSO 分配，天然保证了 1；这里重点介绍如何保证后面两点。

First-commiter-win

对于 First-committer-wins，Percolator 通过在 Prewrite 阶段进行 write-write conflict 检查，对每个 Write 上锁，结合全局时间戳的性质保证了这一点。下面通过简单的证明来看看 Percolator 是如何保证这一点：

假设存在两个事务 T1和T2 违反了 First-committer-wins 约束，即：T1 的某个 Write w1 和 T2 的某个 Write w2 修改了同一行 ，且T1.start_ts < T2.commit_ts < T1.commit_ts，但T1和T2都提交成功。 接着论证这不可能发生：

  1. 考虑 T1 Prewrite w1 成功但是尚未提交的时刻 t0
  2. w1 通过 Write-write conflict 检查意味着 write 列[T1.start_ts, max]之间不存在相同 row 的数据，由于T2.commit_ts > T1.start_ts，这意味着 t0 时刻 T2.w2 并未完成写 write 列，即 T2 未完全提交。
  3. w1 Prewrite 成功意味着 w1 上锁成功；由于锁的独占语义，这意味着 t0 时刻 T2.w2 并未上锁。
  4. 由 2 知 t0 时刻 T2.w2 未完全提交，由假设知 T2 最终提交成功，由 3 知 t0 时刻 T2.w2 并未上锁，故 t0 时刻 T2.w2 必定尚未 Prewrite 成功。
  5. 由于 t0 时刻 T1.w1 独占锁直到 T1 提交完成，而 t0 时刻 T2.w2 尚未 Prewrite 成功，这意味着 T2.w2 只能等到 T1.w1 独占的锁释放后才能 Prewrite 成功，即 T2.w2 Prewrite 成功发生在 T1 提交之后 ；这意味着 T2 的提交发生在 T1 的提交之后，全局 TSO 会保证 T2.commit_ts > T1.commit_ts，这和假设矛盾；即证 Percolator 保证了 First-commiter-wins。

Snapshot-read

在分布式环境中实现全局 Snapshot-read 并不容易，难点来源于分布式事务并不是按照 commit_ts 的顺序提交的；两个事务 T1 和 T2，T1.commit_ts < T2.commit_ts，但是 T2 提交完成可能发生在 T1 之前。例如如下的执行历史：

T1 T2
Prewrite w1{row1, col1, value1}  
Get commit_ts  
  Get start_ts
  Read {w1.row, w1.col1}
Commit  

由于 T2 获取 start_ts 在 T1 获取 commit_ts 之后，T2 应当读取到 T1.w1 的修改，但是由于 T1 尚未 Commit，修改尚未对 T2 可见，如果 T2 直接发起读取就会违背 Snapshot-read。

Percolator 巧妙的利用了获取 commit_ts 发生在所有 Write Prewrite 成功后，即事务包含的所有Write 均 Prewrite成功必定发生在获取 commit_ts 之前这个时序上的 happen-before 关系和全局 TSO 的单调递增性，具体的：

  1. 先进行锁检查：针对某一行（row）的读取操作，先检查对应的 lock 列 [0, start_ts] 范围内是否存在锁。
  2. 如果步骤 1 发现锁不存在，则可以安全的读取；不然等到锁被清理（可能是被动的等待，也可能是进入 failover 流程主动清理）。

再回顾上述所举例的历史：

  1. 一个事务 T1.commit_ts < T2.start_ts，由于 TSO 的单调递增性，意味着 T1 获取 commit_ts 的动作必定发生在 T2 获取 start_ts 之前
  2. 而事务 Prewrite 成功还发生在事务获取 commit_ts 之前，这意味着 T1.w1 Prewrite 成功发生在 T2 获取 start_ts 之前。
  3. 而事务发起读操作是发生在事务获取 start_ts 之后， 因此在 T2 的读操作发生时，T1.w1 的 Prewrite 必定已经成功，如果此时 T1.w1 未提交，那么 T2 的读操作就会因为锁检查而被阻塞。反之只要 lock 列上不存在锁，T1.w1 必定已经提交了。

这样就保证了 Snapshot-read 语义。反过来理解，如果 T1.w1 的 Prewrite 发生在 T2 获取 start_ts 之后，也就意味着 T1 的 commit_ts 必定大于 T2.start_ts，T2 本就不应该读取到 T1.w1 的修改。

Failover

对于分布式事务一个完备的 failover 机制要求满足两点：

  1. Safety：针对 Percolator场景即是同一个事务的两个 Write，不存在一个 Write 的状态为 Committed，另一个则是 Aborted。
  2. Liveness: 所有 Write 最终都会处于 Committed 或者 Aborted。

Liveness 要求 failover 最终能够被触发，对此 Percolator 采用 lazzy 的方式，一个事务的 failover 由另一个事务的读操作触发：如果一个事务读某个 key 时发现该 key 被锁住，Snapshot-read 要求等待锁删除后才能发起读取；在等待超过一段时间后，会认为锁住该 key 的事务可能由于 Client crash 或者网络分区等原因而 hang 住，尝试通过回滚或者继续提交锁对应的事务的方式来清理锁。

对于一个分布式事务，保证 Safety 并不容易；针对 Percolator 的场景，由于异步网络的存在，永远都无法确定 Client 是否真正 crash。Failover 机制需要处理 failover 和 Client 的正常提交流程并发执行的问题，需要避免发生 failover 触发导致事务 T1 回滚，但是实际上存活的 Client 则继续提交 T1。在异步网络下，这样的 race 需要处理的状态空间通常是比较庞大，在任意情况下保证 Safety 并不容易。

保证 Safety 的一个核心点是如何判定一个分布式事务是否已经被提交：即什么情况下，可以判定事务已 Committed，什么情况下判定事务未 Committed，可以发起 rollback。Percolator 的解法是选择一个 Write 作为 primary，以 primary 作为整个事务的 sync point。具体的：

  1. 在 Prewrite 阶段先 Prewrite primary
  2. 在 Commit 阶段先 Commit primary。
  3. Primary committed 意味着事务 Committed；在 failover 触发时，尝试清理事务 T1 的某个 Write T1.w1 的锁之前会先确认 T1 primary Write 的状态；如果判定 T1 primary Write 未 Committed，则判定 T1 未Committed，会执行 rollback：先清理 primary lock，然后在清理 T1.w1 的锁。如果 判定 T1 primary Write 已 Committed，则判定 T1 已 Committed，执行 roll-forward：从 primary 获取 commit_ts，提交 T1.w1，也达到清理锁的目的。

针对 3 展开描述，具体的：

  1. 通过 lock 列存储的 T1.primary 的信息 {primary.row, primary.col} ，并获取 T1.start_ts。

  2. 通过 {primary.row, primary.col, T1.start_ts} 查询 lock 列上 T1.primary 的锁是否存在，如果锁存在那么 T1 一定未 Committed，可以执行 rollback，先清理 T1.primary 的锁，再清理 T1.w1 的锁。检查 lock 列上 primary 锁是否存在和清理 T1.primary 的锁在一个 Bigtable 单行事务中执行，保证原子性。 由于先清理 primary 锁，即使此时 Client 此时已经 Prewrite 成功，进入 Commit 阶段， Commit primary 也会由于锁已被清理而失败（见 Commit 流程步骤2）。

  3. 如果步骤 2 判定 primary 的 lock 列不存在，需要考虑如下三种可能：

    ​a. primary 未 Prewrite

    ​b. primary 已 Committed

    ​c. primary 已 Aborted

    在 Prewrite 阶段先写 primary 确保 a 不可能发生，T1.w1 存在意味着 primary 必定 Prewrite 成功。笔者并未发现 Percolator 论文关于区分 b, c 的细节，也未发现 Abort 时所执行的动作的细节。故下面是笔者按自己的理解补充的可行方案：此时需要去检查 primary 的 write 列是否存在，由于此时并不知道 commit_ts，因此需要：检查 write 列 [T1.start_ts, max] 范围内是否存在 row 相同且 value 等于 T1.start_ts 的数据。由于 start_ts 的唯一性，存在即可判定 primary 的 write 列存在，即 T1 已 Committed，不存在则认为 T1 已经 Aborted。这也意味着 Percolator 在 Abort 时可以只清理 lock 列，无需持久化一条额外的 Aborted 记录。

  4. 如果步骤 3 判定 T1 已 Committed，那么需要执行 roll-forward，从 primary 的 write 列获取 T1 的 commit_ts，针对 T1.w1 写入 write 列后清理锁；如果步骤 3 判定 T1 未 Committed，进行 rollback ，过程同步骤2。

总结

Percolator 基于 Bigtable 的单行事务提供了多行事务的能力，继承了谷歌一如既往的风格，无论并发控制还是 failover 都设计得简洁而优雅，但又强而有力，即严格保证了的 Snapshot Isolation 隔离级别，也保证了 failover 的 Safety。另一方面，从性能的角度它也存在一些不足，它为 Bigtable 定制的特点导致其采取持久化 lock 列和将数据拆成 data 和 write 两列的设计，这些设计对读写吞吐会有不同程度的影响。 同时 Percolator 提交操作从开始到返回用户成功需要 3 次 (IO + RPC) (Prewrite primary + Prewrite secondaries + Commit primary)，虽然简化了 failover 的流程，但是延时较高。可以看到在谷歌新一代的分布式数据 Spanner 中就采用了不同的策略，例如锁是不持久的，这又是另一个故事了。

从工程的角度，Percolator 还是缺失了一些细节，例如 GC。Percolator failover 机制依赖事务 primary Write 的 write 列来判断事务是否已提交，哪怕从多版本的角度 primary Write 的 write 列可以被 GC，但是从 failover 的角度在 GC 前还需要确保事务所有的 secondary Writes 都已经 Committed；Percolator 并未提到这点，也许对于 Bigtable 而言根本不需要 GC，但是如果要把 Percolator 应用到其它支持多版本的存储系统上，这也是必须得解决的一个问题。

参考资料

[1] « Large-scale Incremental Processing Using Distributed Transactions and Notifications »

[2] « Bigtable: A distributed storage system for structured data »

[3] « A Critique of ANSI SQL Isolation Levels »