巨杉内核笔记 | MVCC多版本控制原理

1

背景

随着分布式数据库在企业中的广泛应用，并且逐渐从解决海量数据的存储和读取这类边缘业务向核心交易业务应用的转变。在这类核心交易业务应用时，为了保证业务和数据的正确性，分布式数据库必须支持完善的分布式事务来保证业务并发处理过程中可能出现的数据不一致性问题。

完整的事务管理包括原子性、一致性、隔离性和持久性四个方面，即ACID特性。巨杉数据库SequoiaDB分布式事务管理中的隔离性避免了在多个同时执行的事务操作会话之间出现相互干扰的问题，满足了事务的标准要求及定义。本文主要介绍巨杉数据库SequoiaDB分布式事务隔离性中的隔离级别，以及MVCC多版本并发控制机制解决并发处理过程中出现幻读的实现原理。

2
 

隔离级别

巨杉数据库SequoiaDB 通过对只读操作访问的数据记录实行不同的加锁协议来实现不同的隔离级别。一般来说，隔离级别越高，只读操作的请求锁定就越严格，锁的持有时间越长。因此隔离级别越高，一致性就越高，但并发性就越低，同时对性能也相对影响越大。所有隔离级别中，巨杉数据库SequoiaDB 都将对插入、更新或删除的数据加上互斥锁。

SequoiaDB 目前支持四种隔离级别：

• 读未提交（Read Uncommitted，RU）：RU 级别是最低隔离级别，意味着不同会话之间能够互相读到未提交的修改信息。RU 级别中事务对读取的数据不加锁，因此可能会出现脏读、不可重复读以及幻读等情况。
• 读已提交（Read Committed，RC）：RC 级别为会话读取每条记录最新已被提交的状态，但可能存在不可重复读。RC 级别中，事务对读取的数据加短的共享锁，访问完即放锁，因此可能会出现不可重复读以及幻读等情况。
• 读稳定性（Read Stability，RS）：RS 级别为会话在事务中首次读取的记录，在该会话结束前不会被其他会话所修改。RS 级别中，事务对读取的数据加长的共享锁，事务结束时才放锁，因此可能会出现幻读的情况。
• 可重复读（Repeatable read，RR）：RR级别为会话在事务中首次读取的记录，在该会话结束前不会被其他会话的操作影响。RR级别中，通过MVCC多版本并发控制机制来实现读不加锁，读写不冲突，因此不会出现不可重复读，幻读现象等情况。

 3
 

加锁机制

巨杉数据库SequoiaDB 的隔离性是通过悲观锁机制来实现的，即对访问数据（包括集合空间、集合和数据记录）进行加锁来限制或阻止并发事务访问相同的数据。同时，巨杉数据库 SequoiaDB 支持意向锁机制来提高事务的并发度。

巨杉数据库SequoiaDB 支持三种类型的事务锁，事务锁表示对某个实体进行加锁。

• 共享锁 (S)：当前事务对数据记录加 S 锁之后，并发事务只能对数据记录执行只读操作。
• 更新锁 (U)：当前事务对数据记录加 U 锁之后，如果并发事务未声明它们要更新数据记录，那么它们只能对数据执行只读操作。
• 排他锁 (X)：当前事务对数据记录加 X 锁之后，并发事务将无法以任何方式访问数据记录。

同时，SequoiaDB 支持两种事务意向锁，事务意向锁表示需要对某个实体的子集进行加锁。

• 意向共享锁 (IS)：当前事务对集合加 IS 锁之后，可以读取集合内的数据记录（需要对访问的数据记录加 S 锁）；并发事务可以对相同的集合加意向锁，只要访问或者修改的数据与当前事务不同则可以并发进行。
• 意向排他锁 (IX)：当前事务对集合加 IX 锁之后，可以修改集合内的数据记录（需要对访问的数据记录加 X 锁）；并发事务可以对相同的集合加意向锁，只要访问或者修改的数据与当前事务不同则可以并发进行。

一般来说，SequoiaDB 需要对三级实体进行逐级加锁，集合空间、集合和数据记录（集合空间的子集是集合，集合的子集是数据记录）。当需要访问或者修改某数据记录时，需要对数据记录所在的集合空间、集合加相应的事务意向锁，最后对访问的记录加事务锁。例如事务需要访问集合 sample.employee 中的记录，首先需要对集合空间 sample 加 IS 锁，然后对集合 sample.employeee 加 IS 锁，最后对访问的记录加 S 锁。
事务锁可以作用在集合空间或者集合上，一般来说是对集合空间或者集合的元数据进行访问或者修改，如增删集合等操作。

• 事务锁或者事务意向锁作用在集合上时，可以成为表锁

• 事务锁作用在数据记录上时，可以称为记录锁

4
 

MVCC多版本并发控制

MVCC（Multi-version Cocurrent Control）多版本并发控制技术是一种利用多个不同版本的数据实现并发控制的技术，其思想是为每次事务生成一个新版本的数据，在读数据时选择不同版本的数据可以实现对事务结果的完整性读取。在使用MVCC时，每个事务都是基于一个已生效的基础版本进行更新，事务可以并行进行，历史版本数据从而可以组装成一种链状结构。

巨杉数据库 SequoiaDB 中的MVCC多版本并发控制技术基于内存老版本和事务回滚段实现的。在MVCC多版本并发控制技术实现过程中，会涉及到全局时间戳、全局事务ID、全局事务可见性等技术特性。下面分别对这些技术实现原理进行描述说明。

4.1MVCC多版本实现原理

巨杉数据库 SequoiaDB 中的MVCC多版本并发控制技术基于内存老版本+优化的事务回滚段实现。具体架构设计如4-1图所示：

该方案的设计思想为：在记录锁上附加一个存储原版本数据和索引相关的结构（oldVersionContainer）。所有事务写操作（修改、删除、插入）会在该结构中保存一个事务开始前的记录的拷贝，同时包含所有改动过索引的原始版本。当事务中的读操作试图获取记录锁时，如果记录正在被修改，读取锁失败时将通过回调函数获取该锁的原始版本结构（oldVersionContainer），从而获取上次提交后的数据。在事务提交时，释放记录锁之后异步回收存储老版本记录和索引的空间，用户可以选择打开异步删除涉及到的待删除数据。同时在该锁或记录被下一个写操作用到时，这些记录都会被同步回收。

记录结构中存在一个全局的时间戳或全局事务ID来标识记录的每次变化，也即该记录的版本。对于全局时间戳和全局事务ID后面再进行详细介绍。

4.2 回滚段机制

巨杉数据库 SequoiaDB 在实现MVCC多版本并发控制使用了优化的事务回滚段机制。回滚段机制通过将内存中的“老版本数据”持久化到磁盘上，保证数据库在掉电等异常情况下不会影响事务的正常操作。具体设计如4-2图所示：

回滚段中所有记录会被存放在一张大表中，通过CSID+CLID+RID进行哈希索引，相同的记录通过指针链在一起，新的记录放在链头，链尾的记录是最老的版本，这样极大的提高了查询性能。回滚段使用系统集合空间，名为”SYSRBS”。另外，其内部会使用1个集合，命名格式为”SYSRBSXXXX”，其中XXXX为循环编号，范围为0~4096。

巨杉数据库会在启动时检查是否支持MVCC，如果支持，则会检查”SYSRBS”集合空间是否存在，不存在的话则会创建此集合空间。如果回滚段的集合空间和集合均存在，则根据当前RBS集合（currentRBSCL）和最后空闲RBS集合（lastFreeRBSCL）信息顺序创建下一个SYSRBSCLXXXX。另外每个数据节点维护各自独立的回滚段对应的集合空间”SYSRBS”。

为了更进一步提高读取速度，巨杉数据库将磁盘回滚段与内存老版本相结合，最新的老版本还是挂在记录锁的oldversionContainer上，其它更老的版本放磁盘上。这样满足大多数据短事务只用读内存的老版本，无需再读磁盘，从而提供了读取速度。考虑到主节点异常的情况，多版本控制需要将记录老版本数据的回滚段也同步至备节点，当备节点升为主节点后，可以通过回滚段重建老版本。

回滚段数据清理操作主要发生在事务关闭后，数据已经不再需要保留。对于已经提交的事务T1，如果当前系统中所有打开的事务都不会再读取这个事务T1修改的数据，只读取这个事务T1之后事务修改的数据，则这个事务T1在回滚段中的数据均可清理。对于执行回滚的事务T2，回滚段中数据需要直接清理，清理完成后才可关闭事务，否则这些数据可能会被其他事务访问到。数据库后台的异步线程负责回收老版本记录和索引节点内存，清理时当事务ID小于全局最小事务ID(lowTranID)时，内存老版本要将其保存的老版本写入RBS。而磁盘老版本的清理则是从最后空闲集合(lastFreeRBSCL)开始，逐个对比表的最大事务ID（MaxGTID），如果小于全局最小事务ID，则可以删除这个表（即SYSRBSCLXXXX）。

4.3 全局时间戳

在分布式集群中，由于网络延时等原因会导致时间不一致。而在分布式事务中的MVCC实现过程中，需要依赖于严格的时间戳，为了实现这种严格的时间戳，则需要分布式的时间协议，以能够保证整个分布式事务中所有事件（事务开始，事务预提交，事务提交）的先后关系。即将分布式事务中的所有事务过程都放在一个有向轴上描述他们的时间先后关系，所有的事务过程是有序的。

基本概念与定义

巨杉数据库 SequoiaDB 引入了时间戳管理机制来实现全局事务对跨数据分片的事务的协调和管理，这种时间戳管理机制包括全局时间协议和全局逻辑时间。

• 全局时间协议

全局时间协议（STP，Serial Time Protocol）是巨杉数据库SequoiaDB内部逻辑时间同步的协议。STP以机器为单位提供逻辑时钟服务，维护逻辑时间戳用于全局事务处理，并且该协议不依赖NTP协议实现逻辑时间戳同步，维护的逻辑时间戳严格递增，提供的逻辑时钟服务非中心化，具体如4-3-1-1图所示。

全局时间协议以时间节点（STP Node）为单位提供逻辑时钟服务。在巨杉数据库SequoiaDB中的CATALOG、COORD、DATA节点所在的机器即为时间节点。时间节点有两类角色：

• STP Server：可以做为同步源的时间节点，定义STP Server主节点上的本地逻辑时间为全局逻辑时间。
• STP Client：只能向同步源同步时间的时间节点。

指定多个STP Server组成STP Server组，组内根据协议进行选主，主节点做为同步源。STP Client节点与STP Server的主节点进行时间同步。

• 全局逻辑时间

全局逻辑时间戳（Logical Timestamp，LT）是巨杉数据库SequoiaDB 内部用于表示时间但区别于实际时间的逻辑时间戳。时间戳以递增的方式进行获取，单位为纳秒（nanosecond）。由于时间同步、网络延迟等造成的逻辑时间容错误差，称为时间容错误差（Logical Time Error，LTError），因此，在巨杉数据库 SequoiaDB 中逻辑时间包括逻辑时间戳和时间误差（LT，LTError），而真实的逻辑时间实际可能落在区间（LT-LTError，LT+LTError）范围内。
在巨杉数据库SequoiaDB中，各节点对应的逻辑时间相关定义如下：

• LLT(Local Logical Timestamp)：每个节点（CATALOG、COORD、DATA）维护自己的本地逻辑时间（最小单位：microsecond）。
• ULT(Universal Logical Timestamp): 定义STP Server组主节点的本地时间为全局逻辑时间（最小单位：nanosecond）。
• LRT(Local Real Timestamp)：本地真实时间（UTC时间）。

为了保证整个集群全局时间的一致与准确性，编目节点（CATALOG）、协调节点（COORD）和数据节点（DATA）需要定时与本机器的STP Node节点进行时间同步。而同步时间定义了以下规则：

• ULT在STP Server节点初始化生成，STP Server主节点本身的时间容错误差LTError为0，并且STP Server主节点为其他时间杰STP Node维护时间容错误差。
• 各个时间节点STP Node通过互相同步时间和协商进行时间同步，同步的间隔为ULTSyncInterval（默认：60秒）。
• 同步结果需要使时间差小于最大时间容错误差MaxTimeError（默认：1ms），每个时间节点的时间容错误差根据时间差同步、网络状态进行动态调整。

全局时间的定义及规则确认之后，则可以将其用于分布式事务的实现当中。巨杉数据库分布式事务采用二段提交机制实现，结合二段提交的原理，定义了以下几类事务时间：

• TBT(Transaction Begin Timestamp)：事务开始时间。
• TPCT(Transaction Pre-Commit Timestamp)：事务的预提交(Pre-Commit)时间。
• TCP(Transaction Commit Timestamp)：事务的提交时间。

其中，同一个事务的TBT和TPCT之间需要有一个事务时间间隔，此间隔取本地当时时间容错误差LLTError。另外由于事务A和事务B可能分别从不同节点发起，因此事务A和事务B相关时间之间可能存在误差，如果时间相差在2*max（LLTError-A，LLTError-B）内，则认为时间误差内两个时间相等。

全局逻辑时间同步

全局逻辑时间同步基于NTP算法。具体如4-3-2图所示：

同步过程中，Client向Server发送请求并计算延时。如上图，定义T1为Client发送请求时的逻辑时间戳，T2为Server接受时的逻辑时间戳，T3为Server发送回复时的逻辑时间戳，T为Client接收时的逻辑时间戳。定义发送和接受两段延迟：发送延迟skew_s=T2-T1，接受延迟skew_r=T4-T3。因此，网络延迟为delay=skew_s+skew_r，且网络延迟小于给定的时间容错误差LTError可被接受，在STP Node节点时间同步时自动调大时间容错误差。

巨杉数据库SequoiaDB中以机器为单位部署STP Node节点，具体网络拓扑如下4-3-2图所示：

 STP Node中Server节点组内部进行选主，选举成功后分为Primary和Secondary角色。Primary节点负责维护全局逻辑时间ULT和本地时间容错误差LLTError，同时与STP Client时间节点进行同步。Secondary节点与Primary节点同步ULT。

4.4 全局事务ID

巨杉数据库 SequoiaDB 中的分布式事务采用二阶段提交协议，基于全局逻辑时间和MVCC多版本并发控制机制，支持基于时间容错误差全局一致性的MVCC可见性，在RR隔离级别中解决了不可重复读、幻读问题。在事务开始时，巨杉数据库 SequoiaDB 会为每个事务生成一个全局事务ID（GTID）。全局事务ID包含了事务发起的节点标识NodeId和事务的开始时间TBT等信息。

全局事务开始时，协调节点根据规则生成全局事务ID，生成全局事务ID过程中会从本机STP Node节点中获取事务开始时间，然后返回给客户端事务开始操作。具体流程如4-4图：

 当客户端提交事务时，巨杉数据库 SequoiaDB 协调节点接受到事务请求后，采用二阶段方式执行事务。具体执行流程如图4-4-2：

第一阶段（提交请求阶段）

协调器节点向所有参与事务处理的数据节点询问是否可以执行提交操作即发送预提交请求，在发送请求前会从本机STP Node节点获取预提交时间TPCT，然后开始等待各参与事务处理的数据节点的响应。参与事务处理的数据节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。

各参与事务处理的数据节点响应协调节点发起的询问。如果参与事务处理的数据节点的事务操作实际执行成功，则它返回一个“同意”消息；如果参与事务处理的数据节点的事务操作实际执行失败，则它返回一个“中止”消息。

第二阶段（提交执行阶段）

• 成功的情况

当协调器节点从所有参与事务处理的数据节点获得的相应消息都为“同意”时：

• 协调器节点向所有参与事务处理的数据节点发出“正式提交”的请求。
• 参与事务处理的数据节点正式完成操作，并释放在整个事务期间内占用的资源。
• 参与事务处理的数据节点向协调器节点发送“完成”消息。
• 协调器节点收到所有参与事务处理的数据节点反馈的“完成”消息后，完成事务。

• 失败的情况

如果任一参与事务处理的数据节点在第一阶段返回的响应消息为“中止”，或者协调器节点在第一阶段的询问超时之前无法获取所有参与事务处理的数据节点的响应消息时：

• 协调器节点向所有参与事务处理的数据节点发出“回滚操作”的请求。
• 参与事务处理的数据节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
• 参与事务处理的数据节点向协调器节点发送“回滚完成”消息。
• 协调器节点收到所有参与事务处理的数据节点反馈的“回滚完成”消息后，取消事务。

4.5 全局事务中MVCC可见性

巨杉数据库全局事务在RR隔离级别下，通过MVCC多版本并发控制中的可见性机制对比来解决多个事务之间出现的读问题。

在前面章节提到过，协调节点中的全局逻辑时间通过从本地STP节点获取，而全局逻辑时间包括时间戳和时间容忍误差。下面来看下巨杉数据库MVCC多版本并发控制根据全局逻辑时间进行的可见性对比。

假如读事务TR，事务开始时间T1，逻辑时间误差TRError；某记录老版本D，由写事务TW修改，TW的事务开始时间是T2，提交时间T2’，事务TW的逻辑时间误差TWError。逻辑时间误差取读事务TR、写事务TW最大逻辑时间误差TE=max( TRError, TWError )。

• 第一种情况

当T1 + TE < T2’：读事务TR在写事务TW提交前开始，读事务TR对记录老版本D不可见。如4-5-1图所示：

• 第二种情况

当T2’+ TE < T1：读事务TR在写事务TW提交后开始，读事务TR对记录老版本D可见。如4-5-2图所示：

• 第三种情况

T2’- TE <= T1 <= T2’+ TE：两个时间在误差范围内是相等的，读事务TR可以自己判断是否可见。如4-5-3图所示：

• 写事务TW在多个数据组上操作，有的数据组已经提交，有的数据组正在提交。
• 读事务TR第一次在某个数据组碰到TW修改的记录时TW已经提交，则判断可见。
• 读事务TR第一次在某个数据组碰到TW修改的记录时TW未提交，则判断不可见。
• 

   

   
  5
   

  总结

   

  巨杉数据库通过采用事务锁、内存老版本以及磁盘回滚段重建老版本的设计来实现了MVCC多版本并发控制技术，解决了OLTP应用场景中事务各种隔离级别存在的问题，同时极大的增加了系统的并发性能。