聊聊实现分布式事务

可串行化是指多个事务并发执行的结果，能够等价于某一个串行执行结果。

多个事务访问同一个对象，可能出现依赖关系。如果事务T1先写A，事务T2再读A，那么T2依赖T1。把这些依赖关系整理出来用数据结构中的图表示，其中顶点代表事务，边代表依赖关系。比如T2依赖T1则图中有一条从T1到T2的边。这样的一张图，叫做"可串行化图"。

多个事务并行执行的history，画出可串行化图。可串行化隔离级别，等价于可串行化图中不会形成环路。

只读事务之间，是不会发生冲突的。只有读写或者写写的事务才会冲突。冲突有多种形式：读写冲突，写读冲突，写写冲突。这里分别就用RW/WR/WW表示。如果觉得“冲突”这个词用得不好，我们可以换成“不安全的并发”。

读写(RW)：事务T1先于T2，但T1读到了T2写的值，而不是T2写之前的值。这是一个“读未提交”。

写读(WR)：事务T1先于T2，T1写了一个值，T2读到的不是T1写的值而是更早的值。这是一个“读脏”。

写写(WW)：事务T1先于T2，两个都提交后，观察到的是T1写的那个值。这个是“丢失写”。

事务实现可串行化隔离级别的核心是阻止可串行化图中出现环。

接下来的这部分，讨论的是避免可串行化图中出现环的一种实现方式。

为每个事务分配一个版本。版本用来比较事务发生的谁先谁后。注意的是属于该事务的所有操作，都是这个版本。

这里用'版本'这个词，而不是时间戳，是怕误导大家的理解。其实是同一个概念，只是时间戳很容易联想到分布式系统的物理时钟，会有“时钟漂移”的问题。如果我说“大家要把时间戳理解是逻辑上的先后，物理时钟不能用来比较先后”，说法又不太严谨。干脆用'版本'。

同一个版本内的操作跨度的物理时间可能很长，因为事务从创建到提交要完成一系列的操作，会持续一段时间。但是这个事务执行的所有的操作，我们都是用创建时的版本来比较先后。

假设事件发生的真实时序：T1创建；T2创建；T2操作；T1操作；但我们比较的时候仍然会说T1操作是先于T2操作的。因为我们比较操作的先后用的是'版本'而不是时间。所有操作发生的时间，都是操作所属事务的'版本'创建时间。这里不容易理解。 注意事务是在创建时分配版本，而不是提交时，这也是一个要澄清的点。

这个算法阻止成环的方式就是避免与"将来"发生RW/WR/WW冲突，只有单向就不会成环了。我们具体的一个一个看。

读写：把最近一次的读操作的'版本'缓存下来。执行写操都要做判断，写的版本跟最近一次读操作版本的先后关系。如果读操作的版本比当前的写操作新，那么就是检测到RW冲突了。处理冲突的方式，需要abort掉冲突事务中的一个。

写读：数据都是MVCC的，每次写操作不会覆盖数据而是加一个版本。读操作总是读到版本时间小于它的最后一次写。

写写：写数据时遇到版本比自己更新的写操作，则意味着检测到了写写冲突。解决方式仍然是abort掉其中一个。

通过避免与“将来”发生RW/WR/WW冲突，来破坏可串行化图成环的条件。

上面的讨论只是在满足一个假设的条件下是成立的。其实忽略了一个场景，即事务不一定都会提交。

我们看写读。上面说读操作要读版本早于自己的最后一次写，这个说法有问题。分两种情况：

1. 我们读了最后一次写数据，但是这个写操作的事务最后abort掉，写并没提交，那我们就读未提交了。
2. 我们不要读最后一次写数据，而是读更早的已提交数据。但是最后一次写操作的事务成功了，那我们就读脏了。

这两种情况意味着，最后一次写数据我们读或者不读，都不行。因为现在还无法确定它将来会commit还是abort。怎么办呢？两种办法。一种是等！等写的结果出来，能确认最终状态了，就可以知道应该读到什么数据。另一种是不等，那就是abort掉冲突两者中的一个了。这分别是悲观和乐观的并发控制。

这里我们采用的方式是不等，abort掉了重启事务。读操作总是读最后一个已提交的值。如果发现有未提交的写，并且版本在这次读操作之前，则abort掉一个。写操作也是类似的，只允许覆盖已提交的数据，如果遇到尚未提交的写，则要处理冲突。

冲突的时候，具体的abort哪一个事务会用一个算法，加入一定随机性，并且被abort多次以后它不被abort的概率应该升高，这样保证事务不会永远执行不成功。

冲突有时不可避免，简单版本算法我们会abort冲突事务

级联的abort在这里应该是不会遇到，因为有多版本不会依赖未提交的写。前面说了可串行化的关键是无环，说了一个如何避免成环的算法以及如何处理冲突，接下来说一点实现相关的东西。

首先是事务状态。每个事务开始时都会建一个自己的记录，维护当前事务的状态。事务的状态可能是PENDING的，COMMIT或者ABORT的。PENDING是进行中的事务，后面两种是结束的事务。这个状态变量是一个最小粒度的记录，底层可以用raft之类的协议来保证一致性，做一个原子的提交。其实这个动作就是两阶段提交，第二阶段的提交操作：原子地改一个事务的记录状态，从PENDING到COMMIT，当然也可以是ABORT。

那前面从创建事务记录，到事务的各种操作，只要是不冲突都是可以进行下去的。这些过程其实就是两阶段提交的第一阶段，准备阶段。由于所有的写操作都是带版本的写，而不会覆盖原数据，事务之间是不会相互影响的。提交失败的也不需要专门做回滚，那些ABORT的事务制造的数据，周期性地做清理就行了。

对于OLTL类的数据库，可以让写不影响读，读总是读到最后一次已提交的版本，写事务在最后提交时刻如果检测到冲突就ABORT掉，读的吞吐就可以很高。

事务状态是用来做两阶段提交的，知识一定不要学得太死，提交仅仅就是改一个状态而已，两阶段提交也并不意味着吞吐低。

接下来是写意向(write intent)。事务去写一个数据时，不是直接的修改，是留下一个写的意向。意向要留在数据上面，并且有事务自己版本信息(其实就是多版本的概念)。这样子，当其它事务读或者写操作，遇到这个意向，它就知道有事务也正在操作相同的数据，需要避免冲突。

再澄清的概念是关于锁。锁是一个概念上的东西，大致就是用来对某个受保护东西提供排它性访问。如果从这个角度，我们可以说目前的读写操作都是无锁的。但是呢，当一个事务操作执行时遇到数据上存在写意向，那它面临着操作冲突。前面说过了解决冲突，一种是等，另一种是abort事务。如果采用的是等，那是不是又等价于锁的概念了呢？等价于“这个资源被锁保护了，我需要等待锁被释放”。如果是abort，大家可以类比CAS的概念，不断重试直到不发生冲突，这又是无锁了。所以说，锁是一个概念上的东西，知识不要学得太死。

然后讨论时间。

前面说过了，每个事务都要分配一个'版本'，版本其实是时间戳。分布式系统里面，各台机器之前的时钟是无法保证同步的，因此无法直接使用本地时钟。

一种方式是timestap oracle。其实就是用中心化的时钟服务器来分配版本。当然有它不好的地方，单点问题和性能问题。好的地方就是容易理解。前文部分说的都是说的用中心化的时间做版本，应该很好看懂。

在之前的基础上，我们想优化两个点：一个是只读事务永不阻塞；另一个是去掉中心化时钟。

先说如何让只读事务不被阻塞。前面假定的是事务在创建的时候会分配一个时间戳(之前用的'版本'，从现在开始可以用时间戳这个词了)，用它来比较操作的先后。这个时间戳一旦分配了就不会变。现在我们去掉这个限制，即，事务分配的时间戳是可以变的。现在我们先假设机器之间时钟是一致的，然后我们可以使用本地时钟了。

前面说写读冲突，当读操作发现在它之前有未提交写就是冲突了，解决冲突有两种，一种是等，另一种是abort。当时我们说的是采用abort。去掉事务时间戳不可变的限制以后，我们有了另一种处理办法：把冲突的写操作的那个事务时间戳往后推。这其实是等的一种变种，不过不是让读操作等写操作提交，而是读操作不阻塞，推迟写操作。

理解'把事务的时间戳往后推'特别关键，这句话好好读几遍。可串行化要求的是和某一种串行执行的顺序等价，至于和哪一种等价我们并不介意。一个包含写操作的事务可能由于时间戳被推过很多次，推过之后顺序就跟创建事务时变了，不过没关系。如果事务T1读到了T2写的值，那么T1的时间戳肯定是大于T2的，即使T1事务其实先于T2启动：可能是这种情况，T1启动，T2启动，T2写操作，T1发现T2已写但尚未提交的数据，于是把T2的事务时间戳推后。

可以把事务时间戳往后推之后，我们达到了这种效果：读操作永不阻塞，也不会因为跟写操作冲突而被abort。写可能需要等待读，或者被abort。事务的提交时间戳将是被推多次后最终那个时间戳。我们完成了第一个优化，只读事务不阻塞。接着再看第二个优化，机器之间时钟其实是有漂移的时候，如何使用本地时钟。

Google的TrueTime，这是个很屌东西，它就是用本地机器上的物理时钟来比较时序。能这么做是因为它用硬件保证了，各机器之间的误差在一个上限，大概是前后7ms的样子。有了这个保证之后，比如说我们看到一个事务A的时间戳比事务B小了7ms以上，那事务A肯定是比B先的。再比如说读事务遇到了冲突的写，我们将写的那个事务时间戳推到未来的7ms之后，它就肯定是在读后面了。算法上其实用NTP也能做，但是NTP的时间误差上限保证不了，或者说为了处理时间戳先后问题要等几百毫秒，那性能就不可接受了。

我们看一看可以推事务的时间戳，使用本地时钟以后，现在RW/WR/WW冲突是怎么样的。

• 读操作遇到了写的时间戳在遥远的将来，可安全地读，无冲突。
• 读操作遇到了写在较近的将来，这种情况要小心，因为考虑到时钟漂移，写操作可能其实已经发生了。所以只好abort掉这个写事务了。
• 读操作遇到写，时间戳在过去。我们需要查事务的状态，如果是已提交，那么就读到这个值。如果是未提交，那么可以把这个写的时间戳往后推。
• 写遇到未提交的写，那肯定是冲突，要abort掉其中一个的。
• 写遇到已提交的写，并且对方时间戳比自己新。abort自己，重启。
• 写遇到了时间戳在将来的读，把自己推到读时间戳之后。

还有一个问题是如何为只读事务选取一个时间戳。我们需要读的时间戳，大于所有已提交的包含写的事务的时间戳，这样才能保证读到一个安全的快照。那么会遇到一个问题是读需要等待，等待到真实时间走到比已知的最大时间戳大7ms。

我们不想让读等待，有一种变通的处理办法是推后写事务的提交时间，即本来写已经完成了并提交了，但是会推迟一点点才释放锁。亦是指本来事务完成的时间是T，但是记录事务的完成时间戳会是T+7ms，这样就可以消除时钟漂移的影响，读可以直接用本地时间读不用等待。

以上就是去掉了中心化的时钟，允许推事务时间戳以后的算法，实现了只读事务不阻塞。

最后是本文的总结。本文是关于分布式事务的实现，其实是Google的Spanner那一套。从简单的可串行化开始，接着用预先分配事务时间戳的算法来帮助理解，然后去掉中心化时钟的限制，讲了一个读不阻塞的可串行化的分布式事务。

• 事务实现可串行化隔离级别的核心是阻止可串行化图中出现环
• 通过避免与“将来”发生RW/WR/WW冲突，来破坏可串行化图成环的条件
• 冲突有时不可避免，简单版本算法我们会abort冲突事务
• 复杂版去掉了中心化的时钟，允许推事务时间戳以后，实现了只读事务不阻塞