背景

倒排索引是 Google 搜索引擎中最为关键的技术之一。应对海量数据时，高效的索引创建和索引的实时更新都是必须解决的难题。Google 设计了 MapReduece 系统解决了海量数据索引创建的问题，但 MR 并没有解决增量数据的实时更新问题。

因此，Google 设计 Percolator 的初衷是：支持海量数据存储、并行随机读写、跨行事务的分布式数据库。

由于 Percolator 构建在不支持跨行事务的 BigTable 之上，基于 BigTable 达到 Percolator 的设计目标便是其要解决的核心问题，本文主要描述 Percolator 系统中的事务相关设计。

特点

Percolator 提供了跨行、跨表的、基于快照隔离的 ACID 事务。

Snapshop isolation

Percolator 使用 Bigtable 的时间戳记维度实现数据的多版本化从而达到了 snapshot isolation，优点是：

对于读：读操作都能够从一个带时间戳的稳定快照获取 对于写：较好地处理写 - 写冲突：若事务并发更新同一个记录，最多只有一个会提交成功

快照隔离的事务均携带两个时间戳：

（图中小空格）与

（图中小黑球）。上图中：

• 

  ，所以事务 1 的更新对 2 不可见

• 事务 3 可以看到事务 2 和 事务 1 的提交信息

• 事务 1 和 事务 2 并发执行：如果两者更新同一个记录，至少有一个会失败

Lock

Percolator 后端存储基于 BigTable。由于 Bigtable 没有提供便捷的冲突解决和锁管理方案，Percolator 需要实现一套独立的锁管理机制。必须满足以下条件：

能直面机器故障：若一个锁在两阶段提交时消失，系统可能将两个有冲突的事务都提交。

高吞吐量：上千台机器会同时请求获取锁。 低延时：每个读操作都需要读取一次锁

事务

存储 - COLUMN

Percolator 在 BigTable 上抽象了五个 COLUMN，其中三个跟事务相关

LOCK COLUMN

事务产生的锁，未提交的事务会写本项，记录 primary lock 的位置。事务成功提交后，该记录会被清理。记录内容格式：

：数据的 key

：事务开始时间戳

：事务 primary 引用。在执行 Percolate 事务时，会从待修改的 keys 中选择一个 (随机选择) 作为

，其余的则作为

DATA COLUMN

存储实际用户数据，数据格式为

：真实的 key

：事务的开始时间戳

： 用户数据值

WRITE COLUMN

已提交的数据信息，存储数据所对应的时间戳。数据格式

：数据的 key

：事务提交时间戳

：事务开始时间戳，可根据 key + start_ts 在 DATA COLUMN 中找到数据 value

关键在于 WRITE COLUMN，只有该列正确写入后，事务的修改才会真正被其他事务可见。读请求会首先在该 COLUMN 中寻找最新一次提交的 start timestamp，这决定了接下来从 DATA COLUMN 的哪个 key 读取最新数据。

事务提交关键流程

Prewrite

Prewrite 是事务两阶段提交的第一步：

1. 客户端首先从 Oracle 获取全局唯一时间戳作为当前事务的

   

   ；

2. 客户端会从所有 key 中选出一个作为

   

   ，其余的作为

   

   。并将所有的 key/value 数据写入请求并行地发往对应的存储节点。存储节点对 key 的处理如下：

\1.

冲突检查：从 WRITE COLUMN 列中获取当前 key 的最新数据，若其

大于等于

，说明在该事务的更新过程中其他事务提交过对该 key 的修改，返回WriteConflict错误 \2. 检查 key 是否已被锁，如果是，返回KeyIsLock的错误 \3. 向 LOCK COLUMN 列写入

为当前 key 加锁。若当前 key 被选为 primary，

标记为

。若为 secondary，则指向

的信息 \4. 向 DATA COLUMN 列写入数据​

Commit

Prewrite 成功后，进入事务的第二阶段 Commit。

1. 从 Oracle 获取时间戳作为事务的提交时间

   

2. 向 primary key 所在的存储节点发送 commit 请求

3. 步骤 2 正确完成后该事务即可标记为成功，接下来异步并行地向 secondary keys 所在的节点发送 commit 请求

4. 存储节点对于客户端请求的处理：

\1. 获取 key 的 lock, 检查其合法性，若非法，则返回失败 \2. 将​

写入 WRITE COLUMN \3. 从 LOCK COLUMN 中删除 key 的锁记录以释放锁

值得说明的是，一旦

节点提交成功后，整个事务就算提交成功了。

在某些实现中（如 TiDB），Commit 阶段并非并行执行，而是先向

节点发起 commit 请求，成功后即可响应客户端成功且后台异步地再向

发起 commit。

读取

WRITE COLUMN 记录了 key 的提交记录，当客户端读取一个 key 时，会从 WRITE COLUMN 中读根据 key 查找记录的

，再根据

作为新的 key 从 DATA COLUMN 中读取 value。

存储节点对读请求处理流程如下：

1. 检查区间

   

   内 Lock 是否存在，若存在，则返回错误。在该区间内有 lock 意味着有未提交的事务，客户端需要等到持有该锁的事务提交了才能读取到最新的数据

2. 如果不存在有冲突的 Lock，获取 WRITE COLUMN 中合法的最新提交记录

   

3. 根据步骤 2 获取的信息，从 DATA COLUMN 中获取到相应的数据

   

异常处理 - 清理锁

在 Prewrite 阶段检测到锁冲突时会直接报错（读时遇到锁就等直到锁超时或者被锁的持有者清除，写时遇到锁，直接回滚然后给客户端返回失败由客户端进行重试），锁清理是在读阶段执行。有以下几种情况时会产生垃圾锁：

\1. Prewrite 阶段：部分节点执行失败，在成功节点上会遗留锁 \2. Commit 阶段：Primary 节点执行失败，事务提交失败，所有节点的锁都会成为垃圾锁 \3. Commit 阶段：Primary 节点执行成功，事务提交成功，但是在 secondary 节点上异步 commit 失败导致遗留的锁 \4. 客户端奔溃或者客户端与存储节点之间出现了网络分区造成无法通信

对于前三种情况，客户端出错后会主动发起 Rollback 请求，要求存储节点执行事务 Rollback 流程。这里不做描述。

对于最后一种情况，事务的发起者已经无法主动清理，只能依赖其他事务在发生锁冲突时来清理。

Percolator 采用延迟处理来释放锁

事务 A 运行时发现与事务 B 发生了锁冲突，A 必须有能力决定 B 是一个正在执行中的事务还是一个失败事务。因此，问题的关键在于如何正确地判断出 LOCK COLUMN 中的锁记录是属于当前正在处于活跃状态的事务还是其他失败事务遗留在系统中的垃圾记录 ？

梳理事务的 Commit 流程一个关键的顺序是：事务 Commit 时，1). 检查其锁是否还存在；2). 先向 WRITE COLUMN 写入记录再删除 LOCK COLUMN 中的记录。

假如事务 A 在事务 B 的 primary 节点上执行，它在清理事务 B 的锁之前需要先进行锁判断：如果事务 B 的锁已经不存在（事实上，如果事务 B 的锁不存在，事务 A 也不会产生锁冲突了），那说明事务 B 已经成功提交。如果事务 B 的 primary lock 还存在，说明事务没有成功提交，此时清理 B 的 primary lock。

假如事务 A 在事务 B 的 secondary 节点上执行，如果发现与事务 B 存在锁冲突，那么它需要判断到底是执行 Roll Forward 还是 Roll Back 动作。

判断的方法是去 Primary 上查找 primary lock 是否存在：

如果存在，说明事务 B 没有成功提交，需要执行 Roll Back：清理 LOCK COLUMN 中的锁记录； 如果不存在，说明事务已经被成功提交，此时执行 Roll Forward：在该 secondary 节点上的 WRITE COLUMN 写入内容并清理 LOCK COLUMN 中的锁记录。

几种情形分析：

节点作为 Primary 在事务 B 的 commit 阶段写 WRITE COLUMN 成功，但是删除 LOCK COLUMN 中的锁记录失败。如果是由于在写入过程中出现了进程退出，那么节点在重启后可以恢复出该事务并删除 LOCK COLUMN 节点作为 Primary 在事务 B 的 commit 阶段写 WRITE COLUMN 失败：意味事务 B 提交失败，那么事务 A 可以直接删除事务 B 在 LOCK COLUMN 中的锁记录 节点作为 Secondary 在事务 B 的 commit 阶段写 WRITE COLUMN 成功，但是清理 LOCK COLUMN 锁失败，因为在事务 commit 的时候先向 primary 节点发起 commit，因此，进入这里必然意味着 primary 节点上 commit 成功，即 primary lock 肯定已经不存在，因此，直接执行 Roll Forward 即可。

有一个场景值得探讨

假如事务 A（清理锁）和事务 B（提交）并发执行，可能出现的执行顺序是：A1->B1->A2->B2->B3，也即在事务 B 向 WRITE COLUMN 中插入记录之前其锁就被其他事务清理了，会不会出现什么问题？

可能产生的问题：如果此时有 start_ts 更大的读请求到来，由于事务 B 的锁记录已经不存在，因此它会认为事务 B 的 WRITE COLUMN 已经得到是最新内容，但是实际情况是 B 的 WRITE COLUMN 记录还未得到更新，造成了无法读取到最新的数据。

暂时还没想清楚这个问题是如何解决的？

示例

银行转账，Bob 向 Joe 转账 7 元。

首先以

查询 WRITE COLUMN 获取最新时间戳（小于 7 的最新时间戳），得到

。再从 DATA COLUMN 里面读取该时间戳的数据值

，同样获取到 Joe 的帐户下该时间戳下的值为

。

转账开始：使用

作为事务开始时间戳，将 Bob 选为本事务的

，写入 LOCK COLUMN 来锁定 Bob 的帐户，同时将数据

写入 DATA COLUMN。

与此同时，使用

锁定 Joe 的帐户，当前锁作为

并存储一个指向

的引用（当失败时，能够快速定位到锁，并根据其状态异步清理），并将 Joe 改变后的余额

写入到 DATA COLUMN

事务携带当前时间戳

进入 commit 阶段：WRITE COLUMN 列中写入记录

，删除

所在的 LOCK COLUMN 数据至此，读请求过来时将看到 Bob 的余额为 3。

依次在

中写入 WRITE COLUMN 数据项并清理锁，整个事务提交结束。在本例中，只有 Joe，写入的内容为

点评

Percolator 的事务方案对写友好，对读不友好

事务写 primary record 就相当于先把协调者的决议持久化，然后再异步持久化到参与者，减少了多参与者出现异常的等待，但协议的交互轮次并未减少 对于读而言，因为持久化决议分成先写 primary 再写其他参与者，导致参与者的加锁时间变长了。SI 隔离级别下，单机读分布式事务参与者因此会等待更长的时间。单机写的锁冲突也会加剧。

Percolator 的事务方案写性能本身也不算非常理想，体现在

协议基于 BigTable 设计，持久化次数多 如果 2pc 中 commit 时 primary 出问题，其他参与者也不可用且持锁的参与者再没有可能推进，依赖其他事务的锁清理机制。

参考

Shirly's Blogandremouche.github.io (opens new window)LoopJump's Blogloopjump.com (opens new window)Percolator 简单翻译与个人理解www.jianshu.com (opens new window)Codis 作者首度揭秘 TiKV 事务模型，Google Spanner 开源实现！dbaplus.cn (opens new window)

快速理解 Omid:Yahoo 在 HBase 上的分布式事务方案 - 数据库服务器 - 最新 IT 资讯_电脑知识大全_网络安全教程 - 次元立方网www.it165.net (opens new window)

全文完

本文由 简悦 SimpRead (opens new window) 优化，用以提升阅读体验

使用了 全新的简悦词法分析引擎 beta，点击查看 (opens new window)详细说明

背景 (opens new window)特点 (opens new window)Snapshop isolation (opens new window)Lock (opens new window)事务 (opens new window)存储 - COLUMN (opens new window)事务提交关键流程 (opens new window)读取 (opens new window)异常处理 - 清理锁 (opens new window)示例 (opens new window)点评 (opens new window)参考 (opens new window)