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]中的写会和本事务产生冲突。

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时就可以访问新版本数据了,这个一致么?

实现

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

  1. writes_
    所有的写入。writes_[0]是primary。
  2. start_ts_
    ST时间戳,在事务创建时初始化。
  3. Set
    writes_里面加数据。
  4. Get
  5. Prewrite
    一阶段,会被Commit调用。
  6. Commit
    提交,首先调用一阶段的Prewrite,如果全部成功,执行二阶段提交。

Prewrite

我们需要lock所有被写的cell。

对于所有的cell检查下面两类冲突:

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

可以发现,实际上就是分别检查write列和lock列。
如果没有以上两类冲突,我们就更新cell的data列,并且写入上锁的信息。接下来,进入Commit阶段

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

Commit的前几行是封装了一阶段的Prewrite,省得用户自己去调用了。后面就是提交的第二阶段:

  1. 向TSO请求CT
  2. 对于primary
    一旦primary对reader可见,说明事务提交了。
    1. 更新write列
      write列中存放了ST和CT。存放ST的原因是可以通过ST找到数据,即data列。
    2. 移除锁
    3. 提交BigTable的行事务
  3. 对于所有secondary
    1. 更新write列
    2. 移除锁
    3. 【Q】这边不要提交行事务了么?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
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 }

Get

首先检查[0, ST]区间内有没有锁。如果有,说明另一个事务在写,那么我们就要等这个锁被释放,实际上也就是等事务完成了。
【Line19】 如果没有锁,就读取最后一次写的数据latest_write,并且返回对应的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需要能够清除遗留的锁。这个清除的过程是Lazy的

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