暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / PolarDB顾问精选｜跟着论文学习数据库2：MVCC

PolarDB顾问精选｜跟着论文学习数据库2：MVCC

PolarDB 2024-07-19
296

点击蓝字 关注我们

互联网发展到今天，高并发并不是什么新鲜话题，数据同时被读写是业务常态，比如电商系统中的商品库存、金融行业中的用户余额等，实现这一切离不开数据库 MVCC 能力，全称 Multi-Version Concurrency Control，多版本并发控制。

本文大约7500字，需要20分钟阅读。读完将会了解数据库高并发底层原理、从根上了解不同数据库的特性。文章适合资深开发、架构师、DBA等同学阅读。

01 MVCC 是什么
在高并发系统中，当多个应用请求同时读取和更新数据时，数据库必须确保每个请求看到的数据是正确的，并且不会相互冲突。为满足这要求，数据库为每个数据维护多个版本（Multi-Version），并对数据的并发读写控制（ Concurrency Control），这个能力就是 MVCC。它的核心理念就是：数据库的读不阻塞写，写不阻塞读。

MVCC 包含两方面：

  1. Multi-Versioning，MV：生成多版本的数据内容，使得不同请求（读写）可以获取响应版本数据。

  2. Concurrency Control，CC：并发控制，使得并行执行的内容能保持串行化结果。

关于 MVCC 的文章网上并不少，但是能对整个数据库领域技术实现原理、难点以及技术选型背后的优缺点做出详细的分析并不多。本文以

02 MVCC 技术原理
2017年，数据库顶会 VLDB 收录了卡内基梅隆大学（Carnegie Mellon University，简称CMU）教授 Andy 老师团队论文《An Empirical Evaluation of In-Memory Multi-Version Concurrency Control》¹ 。该论文对 MVCC 技术要点、实现方式及其选择原因进行了详细分析（见图1，本章所有图均出自该论文），并且对自研的 Peloton 数据库实现做了说明，以及横向测试了不同技术实现、产品、硬件下的相关性能。
图1
In this paper, we perform such a study for key transaction man-agement design decisions in of MVCC DBMSs: concurrency control protocol,  version storage, garbage collection, and  index management.For each of these topics, we describe the state-of-the-art implementations for in-memory DBMSs and discuss their trade-offs.

在这篇论文中，我们对MVCC  在数据库管理系统中中的关键事务管理设计决策进行了这样的研究：并发控制协议、版本存储、垃圾收集、索引管理。对于这些主题中的每一个，我们描述了内存DBMS的最新实现，并讨论了它们的权衡。

该论文认为 MVCC 主要实现主要基于四个关键模块，文章也用了大量笔墨详细介绍了这四块。

Concurrency Control Protocol 并发控制协议
Version storage 版本数据存储方式
Garbage Collection 垃圾清理机制
Index Management 索引管理
由于笔者能力有限，本文主要关注论文中描述 MVCC 概述中的事务、元组，以及上述四个关键模块。原论文还进行了相关不同技术实现的 MVCC 能力基准测试，以及不同硬件下的表现，建议有兴趣的同学还是直接阅读原文。
2.1 元数据

  • 事务

数据库在事务开始时给事务分配一个唯一的事务ID，事务ID是一个自然增长时间戳作为标识符（TID），并发控制协议（Concurrency Control Protocol）使用TID
标记事务获取数据的不同版本。

  • 元组

数据库中每个数据的数据头（Header）会包含数据的 metadata 信息，这些信息被称为元组（tuple）。如下图2所示：
txn-id: 数据的TID，用以实现写锁。
begin-ts & end-ts：标识该元组版本的生命起止时间。
pointer：指向同一行数据相邻（新/旧）版的指针，依靠指针，版本数据可以形成一个单向链表。

图2

事务想要更新数据的元组信息，需要查看字段 txn-id
是否等于0，如果是的话，将TID
填到这个字段。其他事务想对该数据持有写锁，就会发现 txn-id
字段不是0也不是自己 TID
，就知道已有其他事务占据这个元组的写锁。写完后需要将该元组 txn-id
设置为0。
字段 begin-ts
和 end-ts
的时间戳代表这个元组版本的生命周期。他们的初始值会设置为0。当这个元组被删除了， begin-ts
会被设置 INF
。pointer
字段是存储相邻（上一个或下一个）版本（如果有）的地址的指针。

2.2 并发控制协议

数据库都有一个并发控制协议，用于协调并发事务的执行，负责事务是否可以访问或修改特定版本的元组，以及事务是否可以提交它的改动。

并发控制协议解决的是不同事务间执行顺序和结果的问题（而不是多版本数据），也就是通过锁或者时间顺序保持事务读写数据的串行性。论文介绍了四种协议：Timestamp Ordering (MVTO)、Two-phase Locking (MV2PL)、Concurrency Control (MVOCC) 和 Serialization Certifier (MVSC) ，本文重点介绍前三种， Serialization Certifier 可在论文中进一步了解。
  • MVTO

Timestamp Ordering 实现，数据的元组除了维护三个字段read-ts
、 begin-ts
、 end-ts
，还加加了 read-ts
字段，它记录的是上一个读取它的事务TID
。见图3

图3

当事务T要读取到符合要求的那一条元组信息。首先事务的 TID
在对应元组中的 begin-ts
和 end-ts
之间，如图3所示，事务T要读到Ax，满足10 < Tid < 20。其次还需要确保Ax的元组写锁没被其他事务占住（即txn-id
是0或者是TID
）。因为，MVTO 不允许事务读到没有提交的元组版本。在读取A的版本数据Ax时，如果Ax的read-ts
小于TID
，则将该字段修改为TID
。否则，该版本数据被其他事务占有写锁，事务读取旧版本而不更新read-ts
字段。

在MVTO实现下，事务总是更新最新版本元组。如图二所示，如果没有事务持有BX版本的写锁，并且BX版本的Tid
大于其read-ts
字段值，则事务T创建新版本Bx+1。如果满足这些条件，数据库将创建该数据新的元组版本Bx+1，并将其txn-id
设置为TID
。当T提交时，数据库将BX+1元数据版本的begin-ts
和end-ts
字段分别设置为TID
和INF
，将BX版本的end-ts
字段设置为TID
。

  • MV2PL
Two-phase Locking 通过元组的begin-ts
和end-ts
字段来决定该版本记录是否可见。是否可写，由锁来控制。元组除了维护三个字段：read-ts begin-ts end-ts
，还会加一个字段 read-cnt
，它记录的是上一个读取它的事务TID
。见图4。
图4

想要读元数据A，和上述协议一样要找到一个可见的版本，当找到可见版本时，将元组的read-cnt
的值增加1，当然需要在txn-id
等于0的情况下，否则该版本是被持有修改中的写操作。如图4。

同样的一个事务想要更新BX时，需要确认BX的txn-id
字段为 0 或者当前TID
，且read-cnt
字段为 0。当事务提交时，数据库会分配一个时间戳（Tcommit）来更新新版本的begin-ts
字段，并释放事务持有的所有的锁。如图4。

  • MVOCC
Optimistic Concurrency Contro （乐观并发控制）思想，数据库认为事务大概率不会冲突，因此一个事务在读或更新元组时，不需要获取元组的锁。见图5。

图5
OCC的方案分为三个基本流程，Read、Validate、Write，Validate 过程中需要检测其ReadSet是否被其他事务更新过，如果检测通过，则在Write阶段写入新版本。
  • 小结
MVTO 和 MV2PL 数据行结构相似。MVTO 的并发读写规则是以时间先后顺序来控制的，它虽然有锁的表现，但是本质是时间顺序的体现。而在 MV2PL 中，read-cnt
描述的是当前版本数据行的读锁个数，并不关心这些读锁是来自未来的事务还是以前的事务。因此read-cnt
可以看作一个共享锁，这是两者主要区别。

2.3 版本存储

MVCC中，每次的更新都会创建一个新的版本数据。版本数据中的指针负责指向前一个版本的数据或后一个版本的数据，以此形成一个单向的版本链。文章介绍了三种存储方式了，分别是：Append-only Storage （只追加存储）、Time-travel Storage （时间履行存储）、Delta Storage (增量存储)。
  • Append-only Storage
在该方案中，表所有元组版本都存储在相同的存储空间中，代表产品有Postgres。这种模式下，要更新现有元组，数据库首先从表中获取用于存储新元组版本的空槽。然后，将当前版本的内容复制到新版本。最后，修改新存储元组版本中的槽信息。Append-only 又有两种不同的实现：Oldest-to-Newest（O2N ），Newest-to-Oldest（N2O）
在 O2N 的结构下，在链的头部是元组最老版本。这种模式下的查询，数据库需要遍历长的版本链从而找到最新版本，指针来不断寻找也很慢，并且读到了不需要的版本浪费了CPU缓存，如果垃圾回收能够将单链表维持在较短的长度，那么查询的性能是可以有提升的，否则就会很耗费时间。
在 N2O 的结构下，在链的头部是元组最新版本。因为绝大多数事务需要都是元组的最新版本，所以不需要遍历版本链。缺点是，当元组出现修改时版本链的头部需要更新，相应的表的索引（包含主键索引、二级索引）都需要更新。见图6。
由于 Append-only 是完整的存储数据行，即使数据行中只有少量字段发生了变更。另外，如果表中带有非内联数据（如BLOB、TEXT字段），即使事务没有修改它，也会导致引入大量的重复，导致表数据膨胀。Postgres表膨胀这样也是原因之一。

图6

  • Time-Travel Storage
Time-Travel 方案和 Append-only 比较相似，版本数据都是链表记录数据行，两者主要区别是：Time-Travel 方案下的历史的版本数据是另一个存储空间存储。在主表上，只有最新的主版本数据，而历史数据的链表存放在一张Time-Travel
表中。代表产品有 SQLServer。

当想要更新元组时，数据库先在time-travel
表中将主版本元组信息拷贝到该位置。另外，该方案也避免索引上的指针频繁更新，因为索引指向主版本，此时主版本没有变化。因此，这种方式避免维护数据库索引的负担，无论何时事务更新了元组。同时，对于获取元组的当前版本的查询效率也比较高。见图7。

图7

  • Delta Storage
在该方案中，数据库在主表维护元组的主版本外，在另一个delta
存储空间存储delta
版本，这个存储空间在MySQL  和 Oracle 称之为回滚段（rollback segment
），如 MySQL InnoDB 中的undo log
。

大部分这类数据库选择在主表中存储当前版本（也就是最新版本）。当更新一个元组时，从delta
存储空间申请一个连续空间用于创建一个新的delta
版本。该delta
版本只会记录更改的元组的原先值，而不会记录整个元组（这一点有别于 time-travle storage）。然后数据库直接更新主表上主版本的内容。见图8。

图8
这种方案对于更新操作很理想，因为减少了内存的分配。但是对于偏向与读的场景负担大。当进行获取一个元组的多个属性的读操作时，数据库需要遍历版本链，必须从各个字段的版本数据链中获取到对应版本的字段值，再进行拼凑，这就带来了一定的额外开销。
  • 小结
综上所述，不同的版本数据存储方案都有各自适应的场景。例如Append-only
存储在一些数据分析场景下更佳，因为版本数据存储在连续的空间中，当进行大范围的扫描时可以提高缓存的命中率，而且还可以配合硬件预读进行优化。但是这种方案访问元组的旧版本的查询会遭受更高的开销，因为数据库需要通过元组的链来查找正确的版本。
另外，存储完整数据行的方案（Append-only、Time-Travel
）可以暴露物理的版本数据给索引管理系统，为索引管理提供了更多可选的方案，而Delta存储中就没有物理的版本数据行，在以上方面的对比处于劣势。

2.4 垃圾回收机制

通过前面介绍，我们知道数据库进行数据更新时，会创建多个版本的元组数据。如果不对这些数据做生命周期管理，数据库系统存储终将被耗尽。另外，由于过长的版本链，查询是扫描这些版本链也将消耗更多时间和资源。因此，数据库MVCC 的性能高度依赖于其  Garbage Collection
（垃圾收集，简称GC）机制。
GC 可以分作3个步骤：
    检测过时版本
    在链表中将它们断开连接（移除链表元素）
    释放空间

    检测过时版本数据有很多方法，例如检测版本行是否由异常的事务创建，或者检查版本行是否对所有活跃事务都不可见。对于后者，可以通过比较版本行的end-ts
    和活跃事务的TID
    来实现。

    MVCC 有两种GC实现，这两种实现在查找过期版本的方式上有所不同。第一种方法是元组级（ Tuple-level）GC，数据库单个元组的可见性。第二种是事务级（Transaction-level）GC，它检查由已完成的事务创建的任何版本是否可见。见图9。
    图9
    • Tuple-level
    元组级GC两种方式之：Background Vacuuming（VAC）、Cooperative Cleaning（COOP）。
    Background Vacuuming（VAC）使用一个后台线程，周期性地扫描数据库以寻找过时的版本。这种方案最简单的实现就是遍历版本数据链表，但是这样做的GC性能很难在数据量增长时同步提升，我们需要减少无目的的遍历，或者让遍历范围能缩小下来，因此它无法扩展到大型数据库。
    Cooperative Cleaning（COOP）的思路是改用worker线程进行GC。寻找版本数据时，worker线程也需要跟着版本链表进行遍历，在遍历过程中，如果发现过时版本数据，就直接进行清理。这种方法扩展性很好，因为GC线程不再需要检测过期版本，但它只适用于O2N仅追加存储。另一个挑战是，如果事务不遍历特定元组的版本链，那么系统将永远不会删除其过期版本。
    • Transaction-level
    事务维度的GC一般通过事务记录它读写数据行的集合，DBMS需要监控集合中的版本数据是否都过时了。当某个事务的版本数据集合对所有的活跃事务都不可见时，就可以将这个集合中的版本数据都进行GC清理。对比元组GC，这种方式更加简单，因为数据库可以立即回收对应事务的所有存储空间，缺点是数据库要跟踪每个时期的事务读/写集，而不是仅仅使用时期的成员计数器。
    • 小结
    Tuple-level
    的 VAC 是最常用的版本数据清理方案，通过增加GC线程的数量可以提升它的性能。但是对比Transaction-level GC
    ，这种方案在面对长事务/大事务的时候会对性能有较大的影响，因为长事务意味着它开始之后的所有版本数据都得不到清理，这时候版本数据链就会变得很长，直到长事务提交或者中止。

    2.5 索引管理

    支持MVCC 数据库都将版本信息与其索引分开。数据库把索引定义为键值对，其中键是元组的索引属性，值是指向该元组的指针。
    对于主键索引，索引项中的值指向元组的当前版本。例如在delta
    模式下，指向元祖的主版本在主表上，所以索引无需更新。对于append-only
    模式下，取决于版本链的顺序，例如N2O
    的顺序下，当新版本元组创建时，主键的索引项的值也会更新。如果主键被更改，数据库会在索引上进行删除再添加。
    对于二级索引，它更复杂，因为索引条目的键和指针都可以改变。数据库二级索引的两种管理方案在这些指针的内容上有所不同。第一种方法使用逻辑指针，这些指针使用间接映射到物理版本的位置。第二种是物理指针方法，值是元组的确切版本的位置。见图10。
    图10

    • Logical Pointers

    使用逻辑指针的主要思想就是，使用一个固定指针，索引项中指向的内容不变。正如该图所显示，DBMS使用一个间接层将元组的标识符（元组的ID）映射到版本链的头。但因为没有指向确切的版本，DBMS需要遍历版本链找到可见的版本。
    • Physical Pointers
    使用物理指针的主要思想就是，将版本的物理地址存储在索引条目中。这种方法仅适用于仅append-only
    ，因为数据库将版本存储在同一个表中，因此所有索引都可以指向它们。当更新表中的任何元组时，数据库会将新创建的版本插入到所有二级索引中。以这种方式，数据库从二级索引中搜索元组，而无需将二级索引与所有索引版本进行比较。
    • 小结
    由上可知，不同的索引管理方式也有各自适合的场景。对于Logical Pointer
    ，在写入频繁的场景下表现更好，因为辅助索引只需要在索引字段值发生改变时才会改变，在读取场景下，它还需要对不同的版本链进行对比，因为同一个逻辑值有可能对应不同的物理值；对于Physical Pointers
    ，频繁的更新场景会导致写入性能变差，但是在检索时就会有它的优势。
    另外，文章特别强调了“覆盖索引”其实并不能通过扫描单个索引得到Query结果，因为索引里面并没有版本数据。对于Append-only
    的设计，回到主表进行检索是必须的；而对于Delta存储，至少也需要在delda
    空间（例如undo log
    ）中查找对应版本。

    03 主流产品实现原理

    3.1 MySQL

    MySQL的 MVCC 主要依赖于：数据行中的隐式字段、undo log
    ，consistent read view
    （一致性读视图）²。它的具体流程如下：
    InnoDB存储引擎中的每行记录都包含一些隐藏字段，如DB_TRX_ID
    （最后修改该行的事务ID）、DB_ROLL_PT
    （指向该行上一个版本的回滚指针）、DB_ROW_ID
    （新行插入时的行ID）。数据库在每次更新一条记录时，旧值被复制到undo log
    中，形成版本链。每个版本包含了创建该版本时对应的事务ID。如图11。
    图11 来自 MySQL官方文档
    当事务执行快照读时，会产生一个ReadView，它是一个“读视图”，用于判断当前事务可见的数据版本。ReadView中包含了系统中活跃的（未提交或回滚的）事务ID列表等信息。通过比较ReadView与版本链中的trx_id，可以确定哪个版本的数据对当前事务可见。数据库每次数据修改时，都会在undo log
    中留下快照，用于读取旧版本信息。

    3.2 Postgres

    前面提到  Postgres 并没有 undo
    的概念，其文件页中以逻辑方式存放着在元组数据空间，每个元组都对应着该逻辑行数据的每一个版本，数据文件中存放着每一逻辑行的多个版本。其通过当前的事务快照和对应的元组版本号来判断该元组的有效性、可见性、可更新性。它的具体流程如下：
    每个版本的头部会记录着t_xmin
    （该版本的创建事务ID）和t_xmax
    （删除事务ID）、t_cid
    （包含cmin和cmax两个字段，标识在同一个事务中多个语句命令的序列值）等信息来唯一定义元组的版本 ，每次对元组的更改都会产生新版本的元组，版本之间会形成一条版本链，在版本链中，由旧到新。³ 如图12所示。

    图12 来自 mysql.taobao.org
    当一个事务插入一条数据时，PG 会将该事务的XID
    存储到行版本头部的xmin
    中，在提交之前，该事务插入的数据对于其他事务是不可见的。对于更新和删除操作，与更新不同的是它们会将XID存储到行版本的xmax
    中。事务只能读取比该事务XID
    小，并且已经提交的行版本数据。
    PG 的MVCC实现方法有利有弊。其中最直接的问题就是表膨胀，为了解决这个问题引入了AutoVacuum
    自动清理辅助进程，将MVCC带来的垃圾数据定期清理。

    3.3 Oracle

    Oracle的MVCC也是通过undo段来实现，和 MySQL 不同的是，Oracle是基于块级的，MySQL是基于行记录。
    Oracle undo log
    中保存了某个数据被修改之前的前映像的数据。当我们在数据中查询之前版本的数据时，oracle首先查询的过程会在undo
    中查找该数据块的前映像后，然后把前映像和当前块合并形成了一个CR block
    ，满足数据的一致性了。
    通过前面介绍我们知道，Oracle中的undo
    使用独立的表空间来存放，不管数据被修改了多少次，不会对业务数据段产生的影响，但是undo
    空间容量也是有限的，它有三种状态来管理生命周期，分别是ACTIVE UNEXPIRED EXPIRED
    ，活跃事务的段总是ACTIVE
    状态；已完成事务的，但是在UNDO_RETENTION
    周期内的是UNEXPIRED
    状态；已完成事务的UNDO，但已经过了UNDO_RETENTION
    保留周期的是EXPIRED
    状态。

    3.4 TiDB

    TiDB 底层使用的是单机存储引擎 rocksdb, 为了实现分布式事务接口，TiDB 又采用 MVCC 机制，基于 rocksdb 实现了高可用分布式存储引擎 TiKV。也就是当新写入（增删改）的数据覆盖到旧数据时，旧数据不会被替换掉，而是与新写入的数据同时保留，并以时间戳来区分版本⁴。主要流程如下：
    当事务开始时，TiDB 的 PD 组件会分配一个全局唯一的事务ID，也称为 start Timestam(StartTs)
    ，这是事务在整个生命周期内的版本基础。
    读操作根据其所在事务的Snapshot Read
    （快照读）原则，看到的是在事务开始时刻所有已提交事务的数据版本。读取时，会按照版本号找到最新的，但是低于当前事务时间戳的有效版本进行读取。
    写操作不直接覆盖原有数据，而是生成一个新的键值对，其中key 包含原始数据的键以及事务的 StartTS
    作为版本号。更新操作会在 MVCC 视图下创建新的版本，同时旧版本的数据得以保留。删除操作也是生成一个新的标记删除的版本，而非立即物理删除。
    随着事务不断提交和更新，MVCC 会产生多个数据版本，为了节省存储空间，TiDB 通过垃圾回收（GC）机制定期清理不再需要的历史版本，以释放存储空间。GC 过程会根据 Time To Live
    策略，删除超过指定生存时间且不再被任何未提交事务引用的旧版本。对于 delete
    或 update
    后的历史版本，在没有活跃事务依赖的情况下，可以通过 compaction
    过程将其移除。

    图14 来自TiDB 文章

    04 总结
    通过该论文学习，我们知道数据库 MVCC 的能力实现基于数据的元组信息，以及四个关键模块：并发控制协议、版本存储、垃圾收集、索引管理。
    并发控制协议用于协调并发事务的执行，控制是否允许事务在运行时访问或修改数据库中的特定元组版本，以及是否允许事务提交其修改。版本存储决定了数据库如何存储这些版本以及每个版本包含什么信息。数据库的性能依赖于垃圾收集，以及事务安全的方式回收内存的能力。最后介绍了索引如何保存版本信息——索引管理。

    05 参考

    1、https://www.vldb.org/pvldb/vol10/p781-Wu.pdf

    2、https://dev.mysql.com/doc/refman/8.0/en/innodb-multi-versioning.html
    3、http://mysql.taobao.org/monthly/2017/10/01/

    4、https://mp.weixin.qq.com/s/ulY2vsITlAGHvypYGMzCFQ

    polardbpolardb信息存储数据库事务事务管理
    文章转载自PolarDB，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

    评论