目的
- 支持分布式事务，跨行、跨节点
前提要求
- 下层存储引擎需要支持单行事务
- 需要有一个全局授时组件
基本思路
google在用于更新网页索引的时候提出了percolator事务，可以认为是一种优化版的2PC，client充当了部分coodinator的角色，采用了乐观锁的事务模型，检测到冲突则回滚或者重试。它将2PC的coordinator进行了分割，对于发起prepare和commit的指令等无状态操作交给了client来实现，而对于持久化的事务状态则下沉到了存储引擎中。本质上可以认为Percolator是一个用于客户端事务libary，不再需要一个全局的事务管理器。
隔离级别
可以实现RR，tidb称之为RR，但和MySQL的RR有细微区别，本质上是SI。
每一个事务都有一个开始时间戳（ST）和提交时间戳（CT），一个事务只允许看见CT小于自己的ST的事务的数据（既然存在CT也意味着必然事务已经提交）。
time
------------------------------------------------------------------------------>
|---------T1--------·|
|------------------T2-------------|
|-------------T3----------|
对于如上的几个事务T2,T2,T3. T2应该看不见T1写入的数据，无论T1是否提交，但是T3应当能够看见T1与T2写入的数据。但是需要注意的是这的ST和CT都是从授时中心获取的单调递增的逻辑时间戳，而非真实的物理时间。
Percolator基于的存储格式
google Percolator 底层存储基于Bigtable，其存储有列族的概念（下面以CF代指）,同一个列族的数据存储在一起。每个逻辑上的行分为多个列族，每个列族可以分为多个列，而其中每一列的数据以时间戳倒序排序。
下面为一个典型的Percolator事务模型的行
| key | data | lock | write |
|---|---|---|---|
| Bob | 6: 5:$10 |
6: 5: |
6:data@5 5: |
| Joe | 6: 5:$2 |
6: 5: |
6:data@5 5: |
key为整个行的key，data为该行的数据。而Percolator要求额外的两个CF为：Lock和Write。Lock顾名思义表示该行的锁，而write表示写入这行数据的事务提交的时候时间戳CT。
基本步骤
论文中给出了一个转账的示例来表示事务的基本步骤，假设上面的Bob需要转账7元给Joe.那么首先进入第一阶段:Prewrite
prewrite
1. 对primary行进行加锁
prewrite对应2PC的prepare阶段。首先随机选择一行作为primary,以事务开始间戳为版本，对其进行加锁，写入锁以及Bob转账后的余额。假设选择Bob的账户行为primary：
| key | data | lock | write |
|---|---|---|---|
| Bob |
7:3 6: 5:10 |
7:I am Primary 6: 5: |
7: 6:data@5 5: |
| Joe | 6: 5:$2 |
6: 5: |
6:data@5 5: |
2.对其他行进行加锁
剩余的其他参加事务的行作为secondary行，分别对其进行加锁，这里只有Joe:
| key | data | lock | write |
|---|---|---|---|
| Bob |
7:3 6: 5:10 |
7:I am Primary 6: 5: |
7: 6:data@5 5: |
| Joe |
7:9 6: 5:2 |
7:primary@Bob 6: 5: |
7: 6:data@5 5: |
在这一步之后，转账后的数据其实已经写入了其中（版本时间戳为7的数据），并且每一行都加上了锁。其他行的锁都保存了primary行的信息，以便通过primary行判断事务的状态。
commit
1. 提交prmary行
进行commit的时候，客户端通过Bigtable的单行事务，清楚primary行的锁，并且以提交时间戳在write写入提交标志。
| key | data | lock | write |
|---|---|---|---|
| Bob |
8: 6: 5:10 |
8: 7: 6: 5: |
8:data@7 7: 6:data@5 5: |
| Joe |
7:9 6: 5:2 |
7:primary@Bob 6: 5: |
7: 6:data@5 5: |
Write CF的写入是整个事务提交的标志，这个操作的完成就意味着事务已经完成提交了。
write中写入的数据指向Bob真正存放余额的地方, 这里看上去写了一整行新数据，但是由于Bigtable列族的特性并没有耗费额外的存储空间。
2. 释放其他的行.
| key | data | lock | write |
|---|---|---|---|
| Bob |
8: 6: 5:10 |
8: 7: 6: 5: |
8:data@7 7: 6:data@5 5: |
| Joe |
8: 6: 5:2 |
8: 7: 6: 5: |
8data@7: 7: 6:data@5 5: |
实际上，即使在执行这一步前，客户端挂了而没能处理这些行的锁也没有问题。当其他事务读取到这样的行的数据的时候，通过锁可以找出primary行，从而判断出事务的状态，如果已经提交，则可以清除锁写入提交标志。
伪代码步骤
论文中用C++风格的伪代码进行了Percolator事务流程的表达，整个事务被封装成了一个class，先来看其中需要用到的成员：
class Transaction {
// Write结构体表示一个写入操作，哪个key下的哪一个列，写入什么值
struct Write { Row row; Column col; string value; };
// writes 则为在这个事务中缓存的所有写入的集合
vector<Write> writes ;
// 事务开始的时间戳ST
int start ts ;
Transaction() : start ts (oracle.GetTimestamp()) fg
//下面是各个实现函数，见下文
...
}
事务中需要用到的数据结构比较少，只保存了事务开始的时间戳和写入集合。
Percolator作为一个2PC优化版本，本质上依然分为两个阶段Prewrite和Commit，Prewrite的伪代码如下：
bool Prewrite(Write w, Write primary) {
// 列族名
Column c = w.col;
// google的Percolator基于bigtable的单行事务，因此这里用bigtable::Txn表示发起单行事务
bigtable::Txn T = bigtable::StartRowTransaction(w.row);
// Abort on writes after our start timestamp . . .
if (T.Read(w.row, c+"write", [start ts， +Inf])) return false;
// . . . or locks at any timestamp.
if (T.Read(w.row, c+"lock", [0, 1])) return false;
T.Write(w.row, c+"data", start ts , w.value);
T.Write(w.row, c+"lock", start ts ,
{primary.row, primary.col}); // The primary’s location.
return T.Commit();
}
Prewrite首先开启一个单行事务进行冲突检测
- 如果在自己的开始时间戳ST之后有已经提交的事务写入了该行数据，则认为检测到冲突，回滚当前事务。
- 如果在自己之前已经有其他事务对这行进行加锁，认为存在冲突，回滚当前事务。
如果不存在冲突，则在bigtable的单行事务中修改该行，将这行数据上锁。注意，这只是对于参与分布式事务的其中某一行的加锁。函数的第二个参数primay表示某一个被选为主行的数据，其他所有行的锁都指向这个primary。
下面再来看整体上的提交流程的伪代码：
bool Commit() {
Write primary = writes [0];
vector<Write> secondaries(writes .begin()+1, writes .end());
// 对所有参与事务的行执行Prewrite
// 先对随机选出的某一个primary行加锁，再对其他行加锁。
if (!Prewrite(primary, primary)) return false;
for (Write w : secondaries)
if (!Prewrite(w, primary)) return false;
// 提交时间戳CT
int commit ts = oracle .GetTimestamp();
// Commit primary first.
Write p = primary;
bigtable::Txn T = bigtable::StartRowTransaction(p.row);
// 失去了锁，可能被别人终止了,事务回滚
if (!T.Read(p.row, p.col+"lock", [start ts , start ts ]))
return false; // aborted while working
// 向primary行的Write CF写入提交标志，时间戳为CT
T.Write(p.row, p.col+"write", commit ts,
start ts ); // Pointer to data written at start ts .
//擦除primary的锁
T.Erase(p.row, p.col+"lock", commit ts);
if (!T.Commit()) return false; // commit point
// Second phase: write out write records for secondary cells.
// 在其他行同样进行写入Write CF并且擦除锁
for (Write w : secondaries) {
bigtable::Write(w.row, w.col+"write", commit ts, start ts );
bigtable::Erase(w.row, w.col+"lock", commit ts);
}
return true;
}
事务开始的时候会随机选取一行作为primary，这一行的write CF实际上作为了整个事务
commit时的标志，一旦该CF写入，则认为整个事务已经提交了。事务的提交过程依然可以像2PC一样分为两个阶段：
- 第一阶段：对每一行调用Prewrite进行加锁，其中非primary行的锁有primay行的位置。
- 第二阶段：检查primay行的锁是否还被自己持有，如果依然持有，就可以进行提交操作。提交操作首先用单行事务向primay行写Writie CF并且擦除primay的锁，一旦这个操作完成，就可以认为事务已经提交了。后续再释放其他行的锁。如果此时有其他事务访问尚擦除锁的非primay行，可以通过锁找到primary行从而得知是否事务已经提交。如过已经提交可以直接清除掉这个锁。
读取的伪代码：
bool Get(Row row, Column c, string* value) f
while (true) {
bigtable::Txn T = bigtable::StartRowTransaction(row);
// Check for locks that signal concurrent writes.
if (T.Read(row, c+"lock", [0, start ts ])) {
// There is a pending lock; try to clean it and wait
BackoffAndMaybeCleanupLock(row, c);
continue;
}
// Find the latest write below our start timestamp.
latest write = T.Read(row, c+"write", [0, start ts ]);
if (!latest write.found()) return false; // no data
int data ts = latest write.start timestamp();
*value = T.Read(row, c+"data", [data ts, data ts]);
return true;
}
读取操作，先看是否有尚未提交的锁，如果有的话，需要等待提交后。或者达到满足认为应该终止这个事务的条件，将未提交事务终止。然后根据自己的ST去寻找可见的数据行。这里有个认为应该终止某些事务的条件，在原论文中google更新网页索引时的事务会在chubby上注册临时节点，因此可以知道事务是否存活。但是tidb中并没有这个，官方文档中称 TiKV 在存储节点本地添加了一个简单的 Scheduler 层，在 2PC 读写遇到锁的时候并不是粗暴的直接回滚返回，而是尝试在本地排队等一下 ，如果超时或者其他异常，再返回客户端重试，具体实现需要再研究。
一些想法
Percolator事务是一种乐观锁机制，所有的修改操作都缓存在客户端，最后commit的时候再一次性写入，会受到能缓存的数据量的制约。同时，按文档描述事务提交存在超时机制，如果超时，已经持有的锁也可能被其他事务清除，因此大事务提交时间过长也会有问题。从模型上来讲tidb不应该用于大事务（比如在一个事务中删除两亿条数据之类的）。另外，乐观锁机制在发生冲突的时候会产生事务回滚，代价比较大，因此应该避免过多的热点竞争。例如存在一个全局计数器，每一个事务都会在执行过程中对这个计数器进行+1操作，这种场景下冲突会极其激烈，造成大量回滚重试，效率较低。
