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
    一个简单翻译和个人理解