最近对 TiDB 特别感兴趣，稍微研究了一下他们应用到的 Percolator 事务模型。
BigTable
BigTable 是一个分布式, 多维, 映射表。本质上说，BigTable 是一个键值（key-value）映射。主要有三个维度，分别是行、列、时间戳。
BigTable 存储映射为：(row:string, column:string, time:int64)→string
从存储的映射时间戳维度不难看出，BigTable 是支持可以多版本控制（MVCC）的。
BigTable支持单行的事务，可以保证一行多列的 ACID 特性。明显单行事务对于一个现代化系统来说略显不足，Percolator 借助 BigTable 实现了多行的分布式事务。
Percolator事务流程
Percolator事务分为两个阶段：预写（Pre-write）和提交（Commit），本质上相当于一个加强的2PC。
需要应用 Percolator 事务的 BigTable 的表中，都需要加入下面两个列族：
- L列： 也就是 Lock 列，需要记录该行数据的锁信息
- W列：也就是 Write 列，需要记录该行数据 Last Committed 的数据版本，用来做版本控制。
为什么说列族呢？首先 BigTable 一行中每一个列是允许存储多个时间版本的数据，方便实现例如：读已提交、读未提交、可重复度、序列化等事务隔离级别。
预写（Pre-write）
这里引用 Percolator 原文的一个例子，我们需要将 Bob 的账户中的 7 元转给 Joe 的账户中。
初始状态
首先我们看 bal:write 列，此时 Bob 和 Joe 最新的一个时间戳版本 6 都指向各自的 data@5，说明在 6 这个时间戳版本中： Bob 的账户余额有 10 元，Joe 的账户余额有 5 元。那么持有大于时间戳 6 的事务进行读未提交的时候，可以读到时间戳版本为 5 的 bal:data。
Pre-Write
在 Percolator 里面，首先需要把在同一个事务里面多个 Key 随机选出一个 Primary Key 和多个 Secondary Key。所在数据行分别称为 Primary Row 和 Secondary Row。
首先进行的是 Primary Row 的 Pre-Write 操作：
- 从 TSO 拿到当前时间戳 start_ts = 7
- 检查 <Bob bal:write> 列，如果有大于 7 的数据版本则提交失败，有则说明其他事务已经写入数据（写冲突），没有则继续处理
- 检查 <Bob bal:lock> 列，如果有小于 7 的数据版本锁则提交失败，有则说明其他事务已经占用数据，没有则加锁继续处理
- 设置 <Bob bal:data 7> 为 3
此时已经完成了 Primary Row 的 Pre-Write 操作。2~4 步骤需要在同一个 bigtable 事务里面进行原子操作。
可能会有疑问为什么在此时已经把数据列 <Bob bal:data 7> 写上了？其实由于 <Bob bal:write> 列最新的数据还未写入，在其他事务看来，这属于未提交内容，其他事务可以根据事务隔离级别有选择读取 <Bob bal:data> 的时间戳版本数据。
那么针对多个 Secondary Row 的 Pre-Write 也与 Primary Row 类似，只是锁的记录需要指向 Primary Row 的锁。这样子实现了去中心化的锁管理，把Secondary Lock 与 Primary Lock 关联了起来。
Secondary Row 的 Pre-Write 操作：
- 拿到 Primary Row 的 Pre-Write 中获得的时间戳 start_ts = 7。
- 检查 <Joe bal:write> 列，如果有大于 7 的数据版本则提交失败，有则说明其他事务已经写入数据（写冲突），没有则继续处理。
- 检查 <Joe bal:lock> 列，如果有小于 7 的数据版本锁则提交失败，有则说明其他事务已经占用数据，没有则加锁继续处理。
- 设置 <Joebal:data 7> 为 9。
多个 key 也是类似，在实际应用场景中，可以异步对多个 key 加锁，加快速度。
自此预写（Pre-write）过程已经完成了！
提交（Commit）
目前为止已经把想要修改到的数据已经加好锁了，接下来需要进行 Commit 操作。
首先进行的是 Primary Row 的 Commit 操作：
- 从 TSO 拿到当前时间戳 commit_ts = 8。
- 检查 <Bob bal:lock> 列，看锁是否存在，不存在则可能已经被清除了，取消事务；存在则继续。
- 以 commit_ts 为版本号，指向 bal:write 列的 start_ts 对应数据版本。也就是把 <Bob bal:write 8> 设置为 data@7。此步骤完成后，写入的数据版本已经生效，也就是对读已提交事务可见了。
- 删除锁信息，让其可写。
1~3步骤需要在一个 bigtable 事务里面进行原子操作。
Secondary Row 的 Commit 操作与 Primary Row 的类似。
随便聊点
事务隔离级别
与传统数据库事务隔离级别（读已提交、读未提交、可重复度、可序列化）相比，Percolator 提供了快照隔离级别。
优点：
- 保证事务中的读操作读到对应数据版本，避免产生不可重复读的问题。
- 保证多事务中的写操作不会更新到同一条记录。
缺点也比较明显：
- 写倾斜（Write）问题。
- 乐观事务会产生写热点问题。
锁管理
Percolator 抛弃中心锁管理，把锁信息分散数据当中。通过区分 Primary 和 Secondary，巧妙的设置了一个标志，后续的异常处理都可以通过这个标签来进行。
锁有可能有以下异常：
- Prewrite 中断，还进行 primary lock 或者写 secondary lock 到一半系统崩溃。
- Commit 中断，未进行 primary commit 或者 primary commit 到一半系统崩溃。
此时就需要用到锁清理，锁清理不需要另外开任务去管理和回收。只需要在读操作的时候遇到锁的时候特殊处理即可。减轻了锁维护的成本，也简化了整个锁的管理模型。
那是怎么处理的呢？
每个事务开启的时候都会从 TSO 获取事务开始时间 start_ts ，通过判断某一行数据的 lock 列是否在 (0, start_ts] 范围内为两种情况：
- 不在；说明此锁可读：首先读取 write 列小于 start_ts 的最大的数据，然后去读 data 列。
- 在；说明此锁不可读，此时如果按照锁可读情况处理的话，可能会产生读未提交的问题。
在锁不可读的情况下，也不可能无休止等待，在一定的延迟后，会进行以下操作：
- 遇到 primary lock 还在，可以进行锁清除。
- 遇到 secondary lock 还在，检查 primary lock。
- primary lock 还在，事务 commit 失败，回滚事务
- primary lock 不在，事务 commit 已经成功了，进行事务前滚（没错，就是前滚）。
Percolator 缺点
- 由于依赖 TSO，会发现网络交互比较多；TiDB 团队针对退出了 Async Commit，可以减少网络交互。
- 乐观锁存在热点读写回滚风暴问题；TiDB 团队针对此推出了悲观事务模型。
- 依赖读清理锁，会有写冲突问题。
