Cockroach的MVCC实现机制

Cockroach的事务本质就是《 MVCC事务机制：Snapshot Isolation 》一文中所讲到的Serial Snapshot Isolation机制 , 但存在一点出入：

Serial Snapshot Isolation是在事务提交阶段做冲突检测，而 Cockroach 是在事务执行阶段做冲突检测

在讲 Cockroach 事务实现机制之前，先看看 Cockroach 事务机制中的几个概念：

• 事务ID：每个事务都有一个事务ID，作为事务的唯一标识。

• 事务的状态：pending， aborted， committed。

• 事务的隔离级别：SI、SSI 。

• 事务表(Transaction Table)： 记录整个系统中所有事务的状态，以及处于committed状态事务提交的时间。

事务运行流程中的相关概念：

• 事务开始

  每个事务开始的时候会分配一个initi timestamp和一个优先级别。但是一个事务并不是拥有唯一的 initial timestamp 和优先级别

• 事务restart

  事务冲突时，冲突的一个事务需要restart，restart时，把当前事务abort，重新启动一个新的事务，此时事务的initial timestamp与优先级别可能会发生变化。但是对用户看来，就是一个事务

• 事务candidate commit

  事务除了在开始会分配一个initial timestamp，还会分配一个 candidate commit timestamp ，初始值为 initial timestamp，它在事务执行过程中可以被修改(只能变大)。当事务执行写操作的时候，会在key值中加入intend flag 标签和candidate commit timestamp，表示事务会在candidate commit timestamp 这个时间提交。

• 事务commit

  一个事务的是否真正commit 在与此事务是否在transaction table中将事务的状态更新为commited。此时会去掉key值中的intend flag，用于判断是否提交，但是transaction table里面的状态才是真正衡量一个事务是否提交的标志.

Key的格式：

• 未提交事务的数据Key格式

key + intend + candidate commit timestamp

• 已提交数据的Key的内存格式：

key + latest read timestamp

• 持久化后，每个key/values 按照事务提交时间记录了多个版本格式：

​ key + version1（ timestamp）
​ key+ version2（ timestamp）

Cockroach 事务实现原理

如果每个事务串行执行，事务的处理就会变的极为简单：加全局锁，执行事务。但是这种的方式效率过于底下，甚至导致不相干的事务都只能串行处理。为了提升性能，需要尽可能提升事务处理的并发度，同时又能满足事务的隔离级别要求。事务并发处理会碰到如下三种场景：

• 读写冲突

• 写写冲突

• 写读冲突

读写冲突

​读写冲突顾名思义，对某一行或者某几行进行读取时，存在另外一个事务同时对这一行或者这几行执行写操作。

​在数据读时，内存的Key会记录一个latest read timestamp，这是最后一次读操作对应事务的initial timestamp(事务的开始时间)，该事务每执行一个读操作，都会使用initial timestamp 与Key值中的latest read timestamp 进行比较，把该Key值latest read timestamp 更新为max(initial timestamp， original latest read timestamp)。

在存在读写冲突时，需要关心如下几点：

• 读取数据的Key(内存状态)上是否存在intend标记

• 写事务的暂定提交时间(candidate commit timestamp)和读事务的initial timestamp的先后

• 写事务在事务表(transaction table)是否处于提交状态

• 写事务的隔离级别

• 写事务的优先级别

处理流程如下：

写写冲突

写写冲突顾名思义，当前事务A对某一行或者某几行执行写操作时，存在另外一个事务B同时对这一行或者这几行执行写操作。

那么在事务运行的过程中，需要关心的几点有：

• 事务A待写入数据的Key(内存状态)上是否存在intend标记

• 事务B的在数据表中的状态是否提交

• 事务A和事务B的优先级别

• 事务A写入数据的Key在存储在磁盘的最新版本(timestamp)

处理流程如下：

写读冲突

写读冲突顾名思义，当前事务A对某一行或者某几行进行写操作时，存在另外一个事务B同时对这一行或者这几行执行读操作。

相对于读写冲突和写写冲突，写读冲突处理起来要简单很多，那么在事务运行的过程中，需要关心的几点有：

• 事务待写入数据的Key(内存状态)的last read timestamp

• 事务待写入数据的Key(内存状态)的candidate commit timestamp

处理流程如下：

理论分析

开篇讲到Serial Snapshot Isolation是在事务提交阶段做冲突检测，而 Cockroach 是在事务执行阶段做冲突检测。我们还需要从理论上分析上面的冲突处理流程是否符合MVCC的基础规则。

再回顾一下MVCC事务机制：

Snapshot Isolation 中描述的write snapshot isolation涉及两个规则：

• 规则一： RW-spatial Overlap ： txnj writes into row r and txni

• 规则二：Ts(txni) < Tc(txnj) <Tc(txni)

Similarity to snapshot isolation ，write-snapshot isolation assigns unique start and commit timestamp to transactions and ensures that txni reads the latest version of data with commit timestamp phi < Ts(txni)

write snapshot isolation 为每个事务分配一个开始的时间戳，一个事务提交时间戳，保证每一个（读写）事务读到一行版本的提交时间戳要小于事务的开始时间

​在上面冲突处理流程中可以看到 Cockroach 写到Transaction Table里面的事务提交时间并不是事务运行的结束的时间，而是把事务的提交时间提前。当 Ts(txni) == Tc(txni)的时候，没有任何一个事务txnj满足Ts(txni) < Tc(txnj) <Tc(txni)，假设一个事务开始时，initial timestamp 与candidate commit timestamp 都是2，如果这个事务正常提交(不发生冲突)，这个事务结束的时候(假设这个时候绝对时间为4)，但是 Cockroach 在Transaction Table写入的事务在timestamp = 2的时候提交。也就是 Cockroach 里面记录事务提交时间要比事务真实运行时提交的时间要早。这样就可以满足上面的规则要求。

​但是什么场景下允许这样做而不影响数据的一致性呢？关键在于数据库运行期间，没有其他事务关心这个事务在什么时间提交。或者说在事务运行的时间区间内，该事务修改的行没有被处在这个时间区间内的snapshot 读到过，如果出现这样的事务，SSI事务要么把自己abort掉，要么把对方的事务abort掉。

​简单描述就是：一个SSI事务如果提交成功，那么它的Ts与Tc是相等的(Ts相当于它的initial timestamp ，Tc是它的final commit timestamp)。在 Cockroach 的SSI的事务是不允许自己的candidate commit time 往后推，如果SSI事务能够提交成功，那么它的candidate commit time 是跟initial commit time相等的，write snapshot isolation规则二中就不可能有一个事务txnj 满足 Ts(txni) < Tc(txnj) <Tc(txni)。也就是说一个cockroach的SSI事务提交的时候，不可能有其它事务修改了SSI事务读取的行。下篇文章将列举一些典型例子来进一步阐述该机制。

本文源自： NoSQL漫谈(nosqlnotes.com)

除非特别注明，本站文章均为原创，转载请注明出处和链接。

MVCC事务机制：Snapshot Isolation