Percolator论文阅读

介绍Percolator论文。

类Percolator系统的环境:

  1. 一个KV存储
    在Percolator中是BigTable,在TiDB中是TiKV。
    BigTable可以理解为下面的一个KV映射

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

    在Bigtable中已经提供了针对单行的跨column的事务能力。当然,对于Percolator的跨行跨表的事务,这还是不够的。

  2. 一个全局授时服务器(TSO)
    在Percolator中叫Timestamp Oracle。在TiDB中由PD提供。
    这个授时服务可以给每个事务一个全局的时间戳,从而解决时序的问题。

  3. Client
    作为分布式事务的协调者。在TSO的支持下,这个协调者实现了SI的隔离级别。
    所以这个协调者并不是在BigTable里面的,而其他数据库的控制节点和数据节点是放到一起的。
    Percolator里面的每个节点都会向BigTable进行读写。

Snapshot Isolation

数据库系统中的事务这篇文章中介绍了快照隔离(Snapshot Isolation, SI)。
在实现SI时,需要记录两个时间戳,事务开始ST和事务提交CT。SI保护了WW冲突,其他事务在[ST,CT]中的写会和本事务产生冲突。

如下图所示,SI要求在ST1开始的事务,能看到所有CT2先于(因此ST2肯定也先于)自己的ST1事务的修改。

2.2 Transactions

因为Percolator的协调者是BigTable外部的Client,所以需要自己维护锁。锁具有replicated、distributed、balanced、persistent的要求,BigTable作为存储是支持的,所以这个锁作为meta列一同存放在BigTable的中。

其实有4个Meta列,如下图所示:

  1. lock
    表示一个没提交的事务正在写这个cell。包含了primary lock的位置。
  2. write
    表示是已提交的数据。存放了BigTable的时间戳。

Demo

先来看一个Demo。Bob给Joe转账7块钱。一开始Joe有2块钱,Bob有10块钱。

  1. bal:lock加锁Bob的账户,并且这个锁是primary的。此外,写了bal:data为3,也就是扣了7块钱的Bob。
  2. 下面加锁Joe的账户,在bal:lock里面写一个对Bob账户的primary锁的引用。这样在事务挂掉之后,能够知道primary lock在哪里,并且把它清理掉。
  3. 下面进入提交阶段,首先操作primary lock所在的Bob的账户。需要将bal:lock清理掉,bal:write写上对应的ST。通过这个ST就能找到实际的数据bal:data
    在这之后,Reader们就能看到Bob账户上只有3块钱了。
  4. 下面对Secondary也进行写记录和删除锁的处理。

【Q】看完Demo,有几个问题:

  1. 为什么要引入primary lock?
    这个是为了方便进行失败回滚。当事务提交时,会清空primary lock。因此可以认为如果primary lock还在,则事务尚未提交。
    例如老事务挂了,留下了一片狼藉的现场。此时,一个新事务可能会访问到老事务残留的secondary lock,对应有两种情况:
    1. 指向的primary lock还在,认为这个事务还没有提交成功。
    2. 指向的primary lock不在了,认为这个事务提交成功。那么必须先继续提交老事务。
  2. 如果说secondary lock被清了一半,怎么办呢?
    没问题,后面会讲
  3. 写write列和清空lock是要原子的么?
  4. 在还没有修改Secondary时就可以访问新版本数据了,这个不破坏一致性么?
    同问题2

实现

Percolator事务的模型也是2PC,下面就分两步来看实现,其实就是对Demo的形式化。
整个实现是一个Transaction类,包含几个成员:

  1. writes_
    这个事务的所有写入。writes_[0]是primary。
    一个Percolator事务类似于

    1
    2
    3
    4
    5
    6
    BEGIN
    DML/DQL
    ...
    DML/DQL
    Prewrite
    Commit
  2. start_ts_
    整个事务的ST时间戳,在事务创建时初始化。

  3. Set
    writes_里面加数据。

  4. Get

  5. Commit
    提交,首先调用一阶段的Prewrite,如果全部成功,执行二阶段提交。

  6. Prewrite
    一阶段,会被Commit调用。

Commit 1

Commit的前几行是封装了一阶段的Prewrite,省得用户自己去调用了:

  1. 选择writes_[0]作为primary,剩余的作为secondaries
  2. 对primary做Prewrite
  3. 对所有secondaries做Prewrite
1
2
3
4
5
6
7
41 bool Commit() {
42 Write primary = writes_[0];
43 vector<Write> secondaries(writes_.begin()+1, writes_.end());
44 if (!Prewrite(primary, primary)) return false;
45 for (Write w : secondaries)
46 if (!Prewrite(w, primary)) return false;
...

【Q】先对primary进行Prewrite这个行为是必要的么?此外,在Commit 2阶段也能看到类似的现象。我们放到Commit 2这部分讲。

Prewrite

传入的两个参数,primary是writes_[0],primary lock会在它上面。

我们需要lock所有被写的cell,在这之前,先对于所有的cell检查下面两类冲突:

  1. 【Line 32】如果发现cell的write列在自己的ST之后已经存在一条记录,执行abort
    这实际上是有其他事务已经提交了修改,事务write-write冲突了。根据SI,需要abort。
    【Q】这里有个疑问,SI不是要到提交的时候再检查冲突么?
  2. 【Line 34】如果发现cell的lock列上有另外的记录,无论timestamp是什么,执行abort
    有可能是一个已经提交的事务,并且它的CT比我们ST还要小,但没来得及清理锁,所以并不是冲突。
    Percolator认为这个不常见,所以还是abort。
    文章中还提到可能有失败事务的情况。

可以发现,检查冲突实际上就是处理write列和lock列。
如果没有以上两类冲突,才继续进行:

  1. 【Line36】更新data列,写入ST,以及真正的值w.value
  2. 【Line37】更新lock列,写入primary锁的row和col。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
27 bool Prewrite(Write w, Write primary) {
28 Column c = w.col;
29 bigtable::Txn T = bigtable::StartRowTransaction(w.row);
30
31 // Abort on writes after our start timestamp . . .
32 if (T.Read(w.row, c+"write", [start_ts_ , ∞])) return false;
33 // . . . or locks at any timestamp.
34 if (T.Read(w.row, c+"lock", [0, ∞])) return false;
35
36 T.Write(w.row, c+"data", start_ts , w.value);
37 T.Write(w.row, c+"lock", start_ts ,
38 {primary.row, primary.col}); // The primary’s location.
39 return T.Commit();
40 }

接下来,进入Commit 2阶段。

Commit 2

后面就是提交的第二阶段:

  1. 【Line48】向TSO请求时间戳,作为CT
  2. 检查lock是否还存在
    【Line53】注意,根据“Failure”章节的论述,这里锁可能已经被其他事务清理了。
  3. 对于primary lock
    一旦primary对reader可见,说明事务提交了。
    1. 【Line55】更新write列
      write列中存放了ST和CT。
      存放ST的原因是可以通过ST找到数据,即data列。
    2. 【Line57】移除锁
    3. 【Line58】提交BigTable的行事务,这里就是所谓的commit point。
  4. 对于所有secondary lock
    1. 【Line62】更新write列
    2. 【Line63】移除锁

【Q】为什么在处理primary的时候就提交行事务T.Commit()了?先对primary进行Prewrite这个行为是必要的么?
原因是primary的lock列和write列是判断整个事务状态的金标准。在primary写完write、清完lock之后,就认为事务已经提交,所以就T.Commit()了。后面往secondary写,只是起到通知作用。
假如往secondary写失败了,也不会影响到整个事务的提交。因为secondary还是会将请求redirect到primary上,然后就能发现primary的已提交状态。

【Q】写write删lock是原子操作么?如果不是原子操作,它们的顺序是必然的么?是的,因为这是一个 bigtable 事务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
41 bool Commit() {
...
47
48 int commit ts = oracle.GetTimestamp();
49
50 // Commit primary first.
51 Write p = primary;
52 bigtable::Txn T = bigtable::StartRowTransaction(p.row);
53 if (!T.Read(p.row, p.col+"lock", [start_ts , start_ts ]))
54 return false; // aborted while working
55 T.Write(p.row, p.col+"write", commit ts,
56 start_ts ); // Pointer to data written at start_ts .
57 T.Erase(p.row, p.col+"lock", commit ts);
58 if (!T.Commit()) return false; // commit point
59
60 // Second phase: write out write records for secondary cells.
61 for (Write w : secondaries) {
62 bigtable::Write(w.row, w.col+"write", commit ts, start_ts );
63 bigtable::Erase(w.row, w.col+"lock", commit ts);
64 }
65 return true;
66 }

【Q】ST和CT的关系是什么,会出现ST1<ST2但是CT1>CT2的情况吗?也就是说 st2 对应的更晚被启动,但是更早被提交,并且在这之前的 st1 反而在它提交之后还能成功提交?其实不会,我们考虑:
如果 st2 被提交,说明 st2 设置的lock,没有被清掉。从而 st2 需要能成功设置 lock。从而 st2 事务在 prewrite 时,没有 ts 大于 st2 的 write,在 [0, ∞] 没有 lock。因为 st1<st2,所以实际要求就是在 [0, ∞] 没有 lock。那么就分为两种情况:

  1. st1 此时已经提交了,那么 ct1 肯定小于 ct2,假设不成立
  2. st1 此时还没提交
    1. 如果此时 st1 已经持有 lock,则 st2 不能上锁成功,假设不成立
    2. 所以此时 st1 会卡在【line 35】,一直到 st2 提交完

但这个情况成立么?其实不会,因为我们注意到 Line 39 的 T.Commit(),可以看出从31到38行的代码都是作为 bigtable 事务被整体提交的。

Get

首先检查[0, ST]区间内有没有锁。
如果有,说明另一个事务在写,这个读取事务就要等锁被释放(也就是事务完成)后才能继续执行。注意,不能在这里返回旧数据,否则可能导致幻读
【Line19】 如果没有锁,就读取最后一次写的数据latest_write,并且返回对应的data【Line22】。如果没有读到数据,就返回no data。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
8  bool Get(Row row, Column c, string* value) {
9 while (true) {
10 bigtable::Txn T = bigtable::StartRowTransaction(row);
11 // Check for locks that signal concurrent writes.
12 if (T.Read(row, c+"lock", [0, start_ts_])) {
13 // There is a pending lock; try to clean it and wait
14 BackoffAndMaybeCleanupLock(row, c);
15 continue;
16 }
17
18 // Find the latest write below our start timestamp.
19 latest_write = T.Read(row, c+"write", [0, start_ts_]);
20 if (!latest_write.found()) return false; // no data
21 int data ts = latest_write.start_timestamp();
22 *value = T.Read(row, c+"data", [data_ts, data_ts]);
23 return true;
24 }

Failure

BigTable能处理自身的问题,但还需要处理Client的Failure。
如果在提交事务时Client挂了,Percolator需要能够清除遗留的锁,否则可能导致后续的事务被hang住。这个清除的过程是Lazy的,如果事务A在执行时遇到了事务B的冲突锁,那么A会判定事务B是否宕掉,并清除锁。

A在清除锁时,如果事务B实际并没有宕掉,而且正准备利用这个锁提交事务,会产生race。primary lock就是来解决这个问题的。因为清理或者提交事务都需要通过这个primary lock,所以事务A的清除锁和事务B的利用锁提交事务只有一个可能成功。

特别注意,在事务B提交前,需要检查lock是否还在【Line53】,然后才能写write。同理,在事务A清理前,也需要检查primary lock是否存在,如果存在,则可以安全清理掉这个primary lock(看起来挺奇怪的,如果一个锁存在,就清理掉这个锁)。

还有一种情况,当事务已经写完至少一个write列后发生崩溃,此时可能lock还没有全清理完,write可能没有全写完。此时需要roll forward这个事务。

总之,整个判断的原则就是lock有没有被write取代。

Lazy clean和Liveness

因为eager clean会导致事务回滚,带来性能开销。所以只有在该事务的锁被认为是属于某个dead worker时,才会被清理。

Timestamps

TSO(Timestamp Oracle)服务会阶段性地分配一段区间,并将这段区间的最大值持久化,剩下的时候就可以直接从内存提供服务。当TSO服务重启时,timestamp就会来到持久化了的最大值上。

为了减少TSO的压力,每个Percolator worker会batch自己的请求为一个RPC发送给TSO服务。当TSO的负载变大时,Percolator的batch大小也会变大。

Percolator的事务性要求Get()操作会返回它的ST前所有已经被提交的写。考虑一个事务R在TR读,另一个事务W在TW提交了写,且TW < TR,则R能看到W的写。因为TW < TR,那么TW一定在TR的batch,或者TR之前的batch中。因此可以得到下面的顺序

1
W lock -> W request TW -> R get TR -> R read

实际上,在R读取前,W至少已经写完所有的lock了。所以R要么读到锁,要么读到已经被写完的数据。

从这里,也可以看出加锁的意义之一。考虑下面的执行顺序,如果不加锁,R就不能知道W在写。因为Commit(row1)的CT是小于Get(row)的ST的,根据SI,TR需要能读到Commit(row1)的结果。如果R不管不顾直接读了,而Commit(row1)又是在读取之后发生的,那么R实际上就读到了Commit(row1)之前的结果。

1
2
3
4
5
6
Transaction W       Transaction TR
Prewrite(row1)
W request TW
R get TR
Get(row) with TR
Commit(row1)

分析

Refernce

  1. Large-scale Incremental Processing Using Distributed Transactions and Notifications
    Percolator论文
  2. http://mysql.taobao.org/monthly/2018/11/02/
    阿里数据库月报,对Percolator有较为详细的介绍
  3. https://www.jianshu.com/p/05194f4b29dd
    一个简单翻译和个人理解