Menu

PostgreSQL 中的 MVCC (01)——基本可见性判断

SmartKeyerror on PostgreSQL Database

在数据的并发读写过程中，由于写入并不是原子性的，因此当一个线程正在写时，如果另一个线程进行读操作的话就很有可能产生数据不一致的问题。 比如数据的前半部分写入了，但是后半部分尚未写入，那么在读取时就会取到中间值，也就是脏数据，典型案例就是 64 位整型的写入将会分为两次写入。

解决这个问题的最简单方式就是使用读写锁，多个线程可以并发的读，不可并发地读写。但是对于数据库这类应用来说。对读写的并发有着更高的要求，因为通常而言应用都是读多写少，并且写入的代价是读取代价的几倍之多，一旦有数据写入并阻塞读取时，可能会导致较高的延迟，因此就有了多版本并发控制，它使得读写可以并发进行，读取不会阻塞写入，同时写入也不会阻塞读取。

1. 概述

多版本并发控制（Multi-Version Concurrency Control, MVCC）是一种通过冗余多份历史数据来达到并发读写目的的一种技术，在写入数据时，旧版本的历史数据将不会被删除，那么此时并发的读仍然能够读取到对应的历史数据，这样就使得读和写能够并发运行，并且不会出现数据不一致的问题。

在实现 MVCC 时，主要有两种方式:

  1. 在写入数据时将旧数据迁移到另一个地方，比如回滚段（undo log）。其他线程在读取改行数据时，从回滚段中将旧数据读出来，如 MySQL 和 Oracle。
  2. 另一种方式直接将新数据插入到相关表页中，在同一个存储区域中保存数据的多个版本，PostgreSQL 便是使用该种方法实现的。

2. 事务 ID

多版本并发控制既然会保留一份数据的多个版本，那么就需要能够区分出哪个版本是最新的，哪个版本是最旧的。一个最朴素的想法就是给每一个版本添加一个时间戳，用时间戳来比较新旧，但是时间戳不稳定，万一有人修改了服务器的配置，事情就乱套了。因此，PostgreSQL 使用了一个 32 位无符号自增整数来作为事务标识以比较新旧程度。

我们可以通过 txid_current() 函数来获取当前事务的标识:

postgres=# select txid_current();
 txid_current 
--------------
          507
(1 row)

3. Tuple 结构

紧接着我们需要了解堆元组的组成结构，堆元组由 HeapTupleHeaderData、NULL 值位图以及用户数据所组成，如下图所示:

Alt text

与 MVCC 相关的字段只有 4 个，其含义如下:

  • t_xmin: 保存了插入该元组的事务的 txid
  • t_xmax: 保存删除或者是更新该元组的事务的 txid，若一个 tuple 既没有被更新也没有被删除的话，该字段的值为 0
  • t_cid: 即 Command ID，表示在当前事务中，执行当前命令之前共执行了多少条命令，从 0 开始计数。t_cid 的主要作用就在于判断游标的数据可见性，将在后文详细描述
  • t_infomask: 位掩码，主要保存了事务执行的状态，如 XMIN_COMMITTED、XMAX_COMMITTED 等。同时也保存了 COMBOCID 这一非常重要的标识位，也是和游标相关的字段。

接下来就通过一些小实验来理清这些字段的具体含义，在此之前需要引入一个小工具: pageinspect。pageinspect 是官方所编写的一个拓展工具，可用于查看数据库一个 page 的全部内容

https://www.postgresql.org/docs/current/pageinspect.html

postgres=# CREATE EXTENSION pageinspect;
CREATE EXTENSION

postgres=# CREATE TABLE t(a int);
CREATE TABLE

postgres=# insert into t values(1);
INSERT 0 1

postgres=# create view info t as select lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid from heap_page_items(get_raw_page('t', 0)) order by tuple;

3.1 插入: t_xmin

t_xmin 与创建相关，当我们 insert 一条数据时，t_xmin 就会被设置成执行事务的 txid，并且一旦设置，便不会修改:

postgres=# begin;
BEGIN
postgres=# select txid_current();               -- 获取当前事务 txid
 txid_current 
--------------
          582
(1 row)
postgres=# insert into t values (1);            -- 插入数据
INSERT 0 1
postgres=# select * from info_t;                -- 获取 t_xmin
 tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------
     1 |    582 |      0 |     0 | (0,1)
(1 row)

Alt text

可以看到，t_xmin 被设置成了 582，因为该元组就是被 txid 为 582 的事务所插入的。同时 t_xmax 被设置成 0，因为没有更新和删除。

3.2 删除: t_xmax

t_xmax 与删除有关，当我们删除一条数据时，t_xmax 就会被设置成执行事务的 txid:

postgres=# truncate table t;
TRUNCATE TABLE
postgres=# insert into t values (1);            -- 插入数据
INSERT 0 1

postgres=# begin;
BEGIN
postgres=# select txid_current();               -- 获取当前事务 txid
 txid_current 
--------------
          588
(1 row)
postgres=# delete from t;                       -- 删除数据
DELETE 1
postgres=# select * from info_t;
 tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------
     1 |    587 |    588 |     0 | (0,1)
(1 row)

Alt text

当我们使用 DELETE FROM 删除数据时，数据只是逻辑上被标记删除，实际上就是设置目标元组的 t_xmax 为执行 DELETE 命令事务的 txid，这些被标记为已删除的元组将会在 VCAUUM 过程中被物理清除。

3.3 更新: t_xmin + t_xmax

在 PostgresSQL 中，元组的更新并不是原地的，也就是说新数据不会覆盖旧有的数据，而是通过将旧数据标记为删除，新插入一条数据的方式来完成更新。也就是说，假如说我们对 100 条数据进行更新的话，最终会在文件中产生 200 条数据，其中有 100 条被标记为删除。

postgres=# truncate table t;
TRUNCATE TABLE
postgres=# insert into t values (1);            -- 插入数据
INSERT 0 1

postgres=# begin;
BEGIN
postgres=# select txid_current();               -- 获取当前事务 txid
 txid_current 
--------------
          591
(1 row)
postgres=# update t set a = 2;                  -- 更新数据
UPDATE 1
postgres=# select * from info_t;
 tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------
     1 |    590 |    591 |     0 | (0,2)
     2 |    591 |      0 |     0 | (0,2)
(2 rows)

Alt text

4. 事务快照

事务快照是一个数据集合，保存了某个事务在某个特定时间点所看到的事务状态信息，包括哪些事务已经结束，哪些事务正在进行，以及哪些事务还未开始，我们可以通过 txid_current_snapshot() 函数来获取当前的事务快照:

postgres=# select txid_current_snapshot();
 txid_current_snapshot 
-----------------------
 580:584:581, 583
(1 row)

txid_current_snapshot() 的文本表示含义为 xmin:xmax:xip_list，其中 xmin 表示所有小于它的事务要么已提交，要么已经回滚，即事务结束。xmax 则表示第一个尚未分配的 txid，即所有 txid >= xmax 的事务都还没有开始。而 xip_list 则是使用逗号分割的一组 txid，表示在获取快照时还是进行的事务。

以 580:584:581, 583 该快照为例，在判断可见性时，所有 txid < 580 的并且已提交的 tuple 都是对当前快照可见的。所有 txid >= 584 的 tuple 不管其状态如何，对当前快照都是不可见的。同时，由于 581 和 583 在获取快照时仍然处于活跃状态，因此对于该快照也是不可见的。最后，对于 txid 为 580 以及 582 的元组而言，只要其事务提交了，那么对当前快照来说就是可见的。

Alt text

当然，这只是一个非常粗糙的判断规则，并没有考虑到元组是否被删除、是否被当前事务所创建、是否是对游标的可见性判断等情况。

PostgreSQL 使用结构体 SnapshotData 来表示所有类型的快照，并且通过函数 GetSnapshotData() 来获取事务快照。该函数最重要的功能就是填充 xmin、xmax 以及 xip 这三个核心字段:

typedef struct SnapshotData {
    SnapshotType snapshot_type; /* type of snapshot */

	TransactionId xmin;			/* all XID < xmin are visible to me */
	TransactionId xmax;			/* all XID >= xmax are invisible to me */

	/*
	 * 正在运行的事务 txid 列表
	 * note: all ids in xip[] satisfy xmin <= xip[i] < xmax
	 */
	TransactionId *xip;
	uint32		xcnt;			/* # of xact ids in xip[] */

    ......
}

5. 基本的可见性判断

在 PostgreSQL 中，事务一共有 4 种状态，分别是:

  • TRANSACTION_STATUS_IN_PROGRESS: 事务正在运行中
  • TRANSACTION_STATUS_COMMITTED: 事务已提交
  • TRANSACTION_STATUS_ABORTED: 事务已回滚
  • TRANSACTION_STATUS_SUB_COMMITTED: 子事务已提交

其中子事务的情况本文暂且不做考虑，同时本小节也不讨论关于 cid 的可见性判断，也就是游标的可见性判断，与游标相关的可见性判断将于在下篇文章中描述。

在读取堆元组的时 PostgreSQL 将使用 HeapTupleSatisfiesMVCC() 函数判断是否对读取的 tuple 可见，其函数签名如下:

static bool
HeapTupleSatisfiesMVCC(Relation relation, HeapTuple htup, Snapshot snapshot,
					   Buffer buffer)

接下来的可见性规则其实就是对该函数的拆解。

5.1 xmin 的状态为 ABORTED

首先来看一个最简单的情况，但我们开启一个事务并已经获取了一个快照，并且需要对一个 tuple 进行可见性判断时，如果发现该 tuple 的 xmin 所对应的事务状态为 ABORTED，即已经回滚了，那么这一条“废数据”对当前快照当然不可见。

if (!HeapTupleHeaderXminCommitted(tuple)) {     /* 事务状态为未提交 */
    if (HeapTupleHeaderXminInvalid(tuple)) {    /* 事务已终止 */
        return false;                           /* 不可见 */
    }
}

5.2 xmin 的状态为 IN_PROGRESS

当创建元组的事务正在进行时，按理来说这部分数据对当前快照是不可见的，但是唯一的例外就是当前事务自己创建了该元组，并在后续使用 SELECT 语句进行了查看。那么此时，该元组对于当前快照来说就是可见的:

if (!HeapTupleHeaderXminCommitted(tuple)) {
    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple))) {
        if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* 未被当前事务删除 */
            return true;
    }
    
    /* 该元组在进行中，并且插入语句不由当前事务执行，则不可见 */
    return false;
}

5.3 xmin 的状态为 COMMITTED

当创建元组的事务已提交，如果该元组没有被删除，以及不在当前快照的活跃事务列表中的话，那么是可见的。

/* xmin is committed, but maybe not according to our snapshot */
if (!HeapTupleHeaderXminFrozen(tuple) &&
    XidInMVCCSnapshot(HeapTupleHeaderGetRawXmin(tuple), snapshot))
    return false;  /* 创建元组的事务在获取快照时还处理活跃状态，故快照不应看到此条元组 */

/* by here, the inserting transaction has committed */

if (tuple->t_infomask & HEAP_XMAX_INVALID)	/* 元组未被删除，即 xmax 无效 */
		return true;

/* 元组被删除，但删除元组的事务正在进行中，尚未提交 */
if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED)) {

    /* 若删除行为是当前事务自己进行的，则删除有效，但是仍然需要进行游标的判断 */
    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple))) {
        if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
			return true;	/* deleted after scan started */
		else
			return false;	/* deleted before scan started */
    }

    /* 删除行为不是本事务执行的，并且在删除元组的事务在获取快照时还处理活跃状态，故删除无效 */
    if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
			return true;
} else {
    /* 删除元组事务已提交，但是在删除元组的事务在获取快照时还处理活跃状态，故删除无效 */
    if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
			return true;		/* treat as still in progress */
}

/* 删除元组事务已提交且不在快照的活跃事务中，即删除有效，不可见 */
return false;

xmin 的状态为 COMMITTED 的情况要稍微复杂一些，需要综合考虑 xmax、xip 以及 cid 之间的关系。

6. 可见性判断函数与获取快照的时机

最后，我们来看一下可见性判断函数，在不同的场景下，我们观察一个堆元组的视角也不尽相同，因此就需要调用不同的可见性判断函数来判断其可见性:

可见性判断函数 作用
HeapTupleSatisfiesMVCC 读取堆元组时所使用的可见性函数，是使用最为频繁的函数
HeapTupleSatisfiesUpdate 更新堆元组时所使用的可见性函数
HeapTupleSatisfiesSelf 不考虑事务之间的“相对时间因素”（即xip）
HeapTupleSatisfiesAny 全部堆数据元组都可见，常见的使用场景是建立索引时（观察HOT链）
HeapTupleSatisfiesVacuum 运行 vacuum 命令时所使用的可见性函数

同时，我们可能通过在不同的时机获取快照来实现不同的事务隔离级别。例如对于可重复读（RR）来说，只有事务的第一条语句才生成快照数据，随后的语句只是复用这个快照数据，以保证在整个事务期间，所有的语句对不同的堆元组具有相同的可见性判断依据。而对于读已提交（RC）来说，事务中的每条语句都会生成一个新的快照，以保证能够对其他事务已经提交的元组可见。

7. Reference

  • Mvcc Unmasked - Bruce Momjian, https://momjian.us/main/writings/pgsql/mvcc.pdf
  • The Internals of PostgreSQL, Concurrency Control, https://www.interdb.jp/pg/pgsql05.html

SmartKeyerror

日拱一卒，功不唐捐

China https://smartkeyerror.com