介绍Percolator论文。
类Percolator系统的环境:
一个KV存储
在Percolator中是BigTable,在TiDB中是TiKV。
BigTable可以理解为下面的一个KV映射1
(row:string, column:string, timestamp:int64)->string
在Bigtable中已经提供了针对单行的跨column的事务能力。当然,对于Percolator的跨行跨表的事务,这还是不够的。
一个全局授时服务器(TSO)
在Percolator中叫Timestamp Oracle。在TiDB中由PD提供。
这个授时服务可以给每个事务一个全局的时间戳,从而解决时序的问题。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列,如下图所示:
- lock
表示一个没提交的事务正在写这个cell。包含了primary lock的位置。 - write
表示是已提交的数据。存放了BigTable的时间戳。
Demo
先来看一个Demo。Bob给Joe转账7块钱。一开始Joe有2块钱,Bob有10块钱。
- 写
bal:lock
加锁Bob的账户,并且这个锁是primary的。此外,写了bal:data
为3,也就是扣了7块钱的Bob。 - 下面加锁Joe的账户,在
bal:lock
里面写一个对Bob账户的primary锁的引用。这样在事务挂掉之后,能够知道primary lock在哪里,并且把它清理掉。 - 下面进入提交阶段,首先操作primary lock所在的Bob的账户。需要将
bal:lock
清理掉,bal:write
写上对应的ST。通过这个ST就能找到实际的数据bal:data
。
在这之后,Reader们就能看到Bob账户上只有3块钱了。 - 下面对Secondary也进行写记录和删除锁的处理。
【Q】看完Demo,有几个问题:
- 为什么要引入primary lock?
这个是为了方便进行失败回滚。当事务提交时,会清空primary lock。因此可以认为如果primary lock还在,则事务尚未提交。
例如老事务挂了,留下了一片狼藉的现场。此时,一个新事务可能会访问到老事务残留的secondary lock,对应有两种情况:- 指向的primary lock还在,认为这个事务还没有提交成功。
- 指向的primary lock不在了,认为这个事务提交成功。那么必须先继续提交老事务。
- 如果说secondary lock被清了一半,怎么办呢?
没问题,后面会讲 - 写write列和清空lock是要原子的么?
- 在还没有修改Secondary时就可以访问新版本数据了,这个不破坏一致性么?
同问题2
实现
Percolator事务的模型也是2PC,下面就分两步来看实现,其实就是对Demo的形式化。
整个实现是一个Transaction类,包含几个成员:
writes_
这个事务的所有写入。writes_[0]
是primary。
一个Percolator事务类似于1
2
3
4
5
6BEGIN
DML/DQL
...
DML/DQL
Prewrite
Commitstart_ts_
整个事务的ST时间戳,在事务创建时初始化。Set
往writes_
里面加数据。Get
读Commit
提交,首先调用一阶段的Prewrite,如果全部成功,执行二阶段提交。Prewrite
一阶段,会被Commit调用。
Commit 1
Commit的前几行是封装了一阶段的Prewrite,省得用户自己去调用了:
- 选择
writes_[0]
作为primary
,剩余的作为secondaries
- 对primary做Prewrite
- 对所有secondaries做Prewrite
1 | 41 bool Commit() { |
【Q】先对primary进行Prewrite这个行为是必要的么?此外,在Commit 2阶段也能看到类似的现象。我们放到Commit 2这部分讲。
Prewrite
传入的两个参数,primary是writes_[0]
,primary lock会在它上面。
我们需要lock所有被写的cell,在这之前,先对于所有的cell检查下面两类冲突:
- 【Line 32】如果发现cell的write列在自己的ST之后已经存在一条记录,执行abort
这实际上是有其他事务已经提交了修改,事务write-write冲突了。根据SI,需要abort。
【Q】这里有个疑问,SI不是要到提交的时候再检查冲突么? - 【Line 34】如果发现cell的lock列上有另外的记录,无论timestamp是什么,执行abort
有可能是一个已经提交的事务,并且它的CT比我们ST还要小,但没来得及清理锁,所以并不是冲突。
Percolator认为这个不常见,所以还是abort。
在文章中还提到可能有失败事务的情况。
可以发现,检查冲突实际上就是处理write列和lock列。
如果没有以上两类冲突,才继续进行:
- 【Line36】更新data列,写入ST,以及真正的值
w.value
。 - 【Line37】更新lock列,写入primary锁的row和col。
1 | 27 bool Prewrite(Write w, Write primary) { |
接下来,进入Commit 2阶段。
Commit 2
后面就是提交的第二阶段:
- 【Line48】向TSO请求时间戳,作为CT
- 检查lock是否还存在
【Line53】注意,根据“Failure”章节的论述,这里锁可能已经被其他事务清理了。 - 对于primary lock
一旦primary对reader可见,说明事务提交了。- 【Line55】更新write列
write列中存放了ST和CT。
存放ST的原因是可以通过ST找到数据,即data列。 - 【Line57】移除锁
- 【Line58】提交BigTable的行事务,这里就是所谓的commit point。
- 【Line55】更新write列
- 对于所有secondary lock
- 【Line62】更新write列
- 【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 | 41 bool Commit() { |
【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。那么就分为两种情况:
- st1 此时已经提交了,那么 ct1 肯定小于 ct2,假设不成立
- st1 此时还没提交
- 如果此时 st1 已经持有 lock,则 st2 不能上锁成功,假设不成立
- 所以此时 st1 会卡在【line 35】,一直到 st2 提交完
但这个情况成立么?其实不会,因为我们注意到 Line 39 的 T.Commit()
,可以看出从31到38行的代码都是作为 bigtable 事务被整体提交的。
Get
首先检查[0, ST]区间内有没有锁。
如果有,说明另一个事务在写,这个读取事务就要等锁被释放(也就是事务完成)后才能继续执行。注意,不能在这里返回旧数据,否则可能导致幻读。
【Line19】 如果没有锁,就读取最后一次写的数据latest_write
,并且返回对应的data【Line22】。如果没有读到数据,就返回no data。
1 | 8 bool Get(Row row, Column c, string* value) { |
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 | Transaction W Transaction TR |
分析
Refernce
- Large-scale Incremental Processing Using Distributed Transactions and Notifications
Percolator论文 - http://mysql.taobao.org/monthly/2018/11/02/
阿里数据库月报,对Percolator有较为详细的介绍 - https://www.jianshu.com/p/05194f4b29dd
一个简单翻译和个人理解