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状态事务提交的时间。

事务运行流程中的几个关键状态:

  • start

    每个事务开始的时候会分配一个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

MVCC事务机制:逻辑时钟

MVCC事务机制:混合逻辑时钟

 

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注