Percolator是Google为实现在海量数据集中更新少量增量数据而创建的一个事务模型。大家知道,Bigtable是Google的分布式存储系统,Google使用Bigtable来存储Web的索引,但遗憾的是Bigtable不支持mulit-row transaction, Percolator的出现就是为了弥补这一缺陷。在Google的系统中,Percolator以Client Library的形式实现,客户只需调用Percolator的相关接口来访问Bigtable就可以了,Bigtable不用做任何改动,最大程度避免了系统间的耦合。

Percolator并不复杂,虽然Google那篇论文有14页,其实真正讲Percolator事务模型的只有三四页,前面几页讲Google的业务背景,Percolator产生的因缘;后面部分讲的就是评估效果,使用Percolator和Mapreduce的效果对比等。简单来看,它就是实现了一个去中心化的两阶段递交(2PC)。 在TiDB中, 它的主要实现逻辑只有1000多行Go代码。

Percolator主要是通过在数据行中添加两列:lock列和write列(percolator columns)来实现对事务的2pC控制(论文中提到五个列,其它三个列是结合了Google的业务场景作其它用途), Percolator的2PC称为:Prewrite和Commit。首先需要说明一下这两个列的作用:

  • lock
    用于存储加锁信息。尚未递交的事务,其加锁信息存放在这个字段。
  • write
    用于存储可见数据的版本(timestamp),对读请求指引当前可见数据。

看了上面的关于这两列的描述,你可能还是一头雾水。下面引用论文中的一个例子,五幅图来阐述Percolator的事务模型。

p1
首先我们看第一幅图。一个账户表中,Bob有10美元,Joe有2美元。我们可以看到Bob的记录在write字段中最新的数据是data@5, 它表示当前最新的数据是ts 5那个版本的数据, ts 5版本中的数据是10美元,这样读操作就会读到这个10美元。同理,Joe的账号也是这样。

p2

现在我们要做一个转账操作,从Bob账户转7美元到Joe账账户(第二幅图)。这需要操作多行数据,这里是两行。首先需要加锁,Percolator从要操作的行中随机选择一行作为Primary Row, 其余为Secondary Row,首先对Primary Row加锁, 成功后再对Secondary Row加锁,这里不详细阐述加锁过程,任何加锁失败事务都会失败。从上图我们看到,在ts为7的行(Bob账户)lock列写入了一个锁:I am primary, 该行的write列是空的,数据列值为3(10-7=3)。 此时ts=7 为startTS 。

p3

然后对Joe账户加锁,同样是ts=7, 在joe账户的加锁信息中包含了指向Primary lock的引用,这样这些行处于同一个事务就关联起来了。 Joe的数据列写入9(2+7=9), write列为空,至此完成Prewrite阶段。

p4

接下来事务就要Commit了。 Primary Row首先执行Commit, 只要Primary Row commit成功了,事务就成功了。Secondary Row失败了也不要紧,后续会有补救措施。 Commit操作首先清除Primary Row的锁, 然后写入ts=8的行(因为时间是单向递增的,这里是CommitTS),该行可以称为Commit Row, 因为它不包含数据,只是在write列中写入data@7 , 标识ts=7的数据已经可见了,此刻以后的读操作可以读到版本ts=7的数据了。

p5
接下来就是commit Secondary Row了, 通Primary Row的逻辑是一样的。Secondary Row成功commit, 事务就完成了。

如果Primary Row commit成功,Secondary Row commit失败会怎么样,数据的一致性如何保障? 由于Percolator没有中心化的事务管理器组件,处理这种异常,只能在下次读操作发起时。如果一个读请求发现要读的数据存在Secondary锁, 它会根据Secondary Row锁去检查其对应的Primary Row的锁是不是还存在,若存在说明事务还没有完成;若不存在则说明,Primary Row已经Commit了, 它会清除Secondary Row的锁, 使该行数据变为可见状态(commit)。 这是一个Roll forward的概念.

我们可以看到,在这样一个存储系统中,并非所有的行都是数据,还包含了一些事务控制行,或者称为Commit Row. 它的数据Column为空,但Write 列包含了可见数据的TS。 它的作用是标示事务完成,并指引读请求读到新的数据。 随着时间推移,会产生大量冗余的数据行,无用的数据行会被GC线程定时清理。

参考:
https://pingcap.com/blog-cn/percolator-and-txn/