个人对percollator的理解

 它是什么

         Percolator 是谷歌在2010发表的论文«Large-scale Incremental Processing Using Distributed Transactions and Notifications» 介绍的分布式事务协议，仅靠客户端的协议和一个全局的授时时钟就能实现跨机器的分布式事务，可以说是为了Google Big Table量身定制的。关于Big Table是什么？它解决了什么问题可以参考Google BigTable到底解决什么问题？-云栖社区-阿里云   

 流程

        典型的二阶段提交，主要分为两个阶段，第一阶段是prewrite阶段，这个阶段做的事情主要是加锁和写入数据。第二阶段为commit阶段。

         对于任何一列数据C都会被映射为三个列(属性),C:data数据本身，C:lock记录锁信息，C:write用于记录提交版本。

        1、prewrite阶段

                a.在事务开始的时候会从TSO中获取一个timestamp作为这个事务的start_ts.TSO为一个全局性的授时服务系统。比如TIDB中的PD~~

                b、选择事务的primary。在一个事务中可能包含了很多个需要写入的语句(key)，这个时候会随机选择一个写入作为这个事务的primary，然后首先对这个primary进行prewrite。

                c、检查。对于每一个prewrite都会进行一些检查，首先会做Write-write conflict 检查，主要是用来检查改写入冲突，在[start_ts,max)直接，如果发现了相同的写入表示这个数据在本事务开始到prewrite这段时间已经被修改了，也就意味存在写写冲突，这个时候Percolator 会选择直接abort事务(在TIDB中有对应的参数可以选择是直接abort事务还是发起事务重试).

                在完成上述步骤之后会进行lock的检查，因为可能出现一种情况就是由另外一个事务也正在对同样的写入做prewrite，因为另外一个事务没有完成commit，用于记录提交版本的write列数据为空，另外一个事务修改的数据对这个事务来说是不可见的，也就能顺利的通过上面的写写冲突检查。

                下一步就是对数据列的写入，以 start_ts 作为 Bigtable 的 timestamp，将数据写入 data 列。由于此时 write 列尚未写入，因此数据对其它事务不可见。

                prewrite的最后一步就是加锁。在整个prewrite阶段，如果有任何一个地方发生冲突都会导致整个事务abort。

        2、commit阶段

                a、再次同TSO中获取一个时间戳作为commit_ts

                b、检查lock是否存在，如果锁已经被其它事务清理掉(触发 failover 可能导致该情况）就会导致commit阶段失败。

                c、用commit_ts作为时间戳，以 start_ts 作为 value 写 write 列。读操作会先读 write 列获取 start_ts，然后再以 start_ts 去读取 data 列中的 value。

                d、清除锁数据

        只要primary的两阶段commit完成就可以给客户端返回成功，其它的secondary可以进行异步操作。

    举例：

1、初始状态

    1、在初始状态中，bob、joe各分别有10$和2$,结合之前提到的对于任何一列数据C都会被映射为三个列，故bal具有bal:data列用于记录具体的数据，bal:lock用于记录对应的锁信息，bal:write用于记录提交版本信息。

          对于bob和joe来说，bal:data/lock/write均有5,6两行数据，这个是因为每一次事务都需要从TSO中获取两次版本号，5对于prewrite，6对应commit阶段。

2、

prewrite

这个时候对数据进行了修改，然后进行提交。首先进入commit的第一个阶段prewrite阶段，从TSO中获取一个版本7，这里有两个写入，一个是bob的写入一个是joe的写入，在这里随机选择了bob为primary。检查7~max是否有写写冲突，检查lock列上面是否有锁，从初始状态下可以得知没有写写冲突，lock列上面也没锁的存在。于是对数据进行写入，然后对lock列进行写入。版本7对应的write列为空是因为这个版本是在prewrite阶段进行的，还没做commit。

3、

secondary 的prewrite

对secondary 的prewrite过程类似于primary的rewrite，略

4、

commit阶段

4、所有写入都通过了prepare，现在进入第二阶段。这个时候继续向TSO获取版本，此时的获取的版本为8，检查primary的lock列是否存在，发现lock列存在（secondary 的prewrite图中）于是进行write列的写入，最终的写入也就变成了上图的情况。为什么joe的lock列还有呢？因为在完成了primary的写入之后这个事务就算提交成功了，secondary 可以进行异步的操作。

缺点

1、事务提交延时较大

2、写热点行的并发性损失

3、读数据的并发性损失

4、网络通信开销较大

        我觉得这个是重点，所以在TIDB中建议对于小事务来说建议进行打包提交，比如三个update都分开commit，那么网络交互就是直接的3倍~，如果可以把三个update打包一起提交性能上面会有明显的提升

5、清理无效行的开销

PS：写这些东西的目的是为了记录自己学习的过程，对内容的理解上面可能存在偏差，欢迎各位指正~

参考

Database · 原理介绍 · Google Percolator 分布式事务实现原理解读

Percolator论文学习 - 人生如逆旅，我亦是行人。

Google Percolator 事务模型的利弊分析 - 知乎