一. 概述

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

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

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

二、基本概念

事务ID

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

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

CSNLOG

CSNLOG用于记录事务提交的序列号。openGauss为每个事务id分配8个字节uint64的CSN号，所以一个8kB页面能保存1k个事务的CSN号。CSNLOG达到一定大小后会分块，每个CSNLOG文件块的大小为256kB。同xid号类似，CSN号预留了几个特殊的号。

#define COMMITSEQNO_INPROGRESS UINT64CONST(0x0) 表示该事务还未提交或回滚#define COMMITSEQNO_ABORTED UINT64CONST(0x1) 表示该事务已经回滚#define COMMITSEQNO_FROZEN UINT64CONST(0x2) 表示该事务已提交，且对任何快照可见#define COMMITSEQNO_FIRST_NORMAL UINT64CONST(0x3) 事务正常的CSN号起始值#define COMMITSEQNO_COMMIT_INPROGRESS (UINT64CONST(1) << 62) 事务正在提交中

三、Tuple

Tuple结构

元组（Tuple）即为实际存储的一行数据，他不只包括用户写入的数据，还包括一些其他的额外内容。

一行Tuple由tuple header、 tuple data组成，tuple data是用户写入的数据，tuple header保存其他内容。

Tuple header由23byte固定大小的前缀和可选的NullBitMap构成。

Tuple header里的字段含义如下所示，其中与 MVCC 相关的字段有 4 个:

• t_xmin：代表插入此元组的事务xid；
• t_xmax：代表更新或者删除此元组的事务xid，如果该元组插入后未进行更新或者删除，t_xmax=0；
• t_cid：command id，代表在当前事务中，已经执行过多少条sql，例如执行第一条sql时cid=0，执行第二条sql时cid=1；
• t_ctid：待研究，在 pg中为update后旧版本指向新tuple的指针。
• t_infomask：位掩码，主要保存了事务执行的状态，如XMIN_COMMITTED、XMAX_COMMITTED 等。同时也保存了 COMBOCID 这一非常重要的标识位，也是和游标相关的字段。
• 如果有允许为空的列，则存在null bitmap,可以通过t_infomask判断 t_infomask&0x0001, bitmap的大小与列个数有关。
• t_hoff 记录 header的大小，包含null bitmap,padding。
• tuple header后会有padding,使tuple header的大小为8的整数倍。

HeapTupleHeaderData 代码说明

./src/include/storage/bufpage.htypedef struct HeapTupleHeaderData {    union {        HeapTupleFields t_heap;        DatumTupleFields t_datum;    } t_choice;    ItemPointerData t_ctid; /* current TID of this or newer tuple */    /* Fields below here must match MinimalTupleData! */    uint16 t_infomask2; /* number of attributes + various flags */    uint16 t_infomask; /* various flag bits, see below */    uint8 t_hoff; /* sizeof header incl. bitmap, padding */    /* ^ - 23 bytes - ^ */    bits8 t_bits[FLEXIBLE_ARRAY_MEMBER]; /* bitmap of NULLs -- VARIABLE LENGTH */    /* MORE DATA FOLLOWS AT END OF STRUCT */} HeapTupleHeaderData;

TupleHeader的运行机制

下面介绍了数据库在insert、update、delete时，tuple header里的xmin和xmax的变化情况，当我们更新或删除一条元组时，为了实现多版本，并不会把旧的元组删除，而是将旧的元组标记为“delete”，简而言之：

• xmin保存了插入该元组的事务的xid，xmax保存了删除或是更新该元组的事务的xid，若一个tuple既没有被更新也没有被删除，则xmax=0.
• 当我们 insert 一条数据时，t_xmin 就会被设置成执行事务的 txid，并且一旦设置，便不会修改。
• 当我们删除一条数据时，不会把该元组删除，而是把t_xmax 被设置成执行事务的 txid。
• 当我们更新数据时，新数据不会覆盖旧有的数据，而是把旧元组的t_xmax 被设置成执行更新事务的 txid（标记为删除）。然后再插入一条新元组。

四、事务快照

事务快照是一个数据集合，保存了某个事务在某个特定时间点所看到的事务状态信息，包括哪些事务已经结束，哪些事务正在进行，以及哪些事务还未开始，我们可以通过 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 的元组而言，只要其事务提交了，那么对当前快照来说就是可见的。

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

SnapshotData核心代码说明

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[] */    ......}

五、MVCC快照可见性机制

5.1 快照判断可见性原理

CSN原理如图所示：

每个非只读事务在运行过程中会取得一个xid号，在事务提交时会推进CSN，同时会将当前CSN与事务的xid映射关系保存起来（CSNLOG）。图中，实心竖线标识取snapshot（快照）时刻，会获取最新提交CSN（3）的下一个值4。TX1、TX3、TX5已经提交，对应的CSN号分别是1、2、3。TX2、TX4、TX6正在运行，TX7、TX8是未来还未开启的事务。对于当前snapshot而言，严格小于CSN号4的事务提交结果均可见；其余事务提交结果在获取快照时刻还未提交，不可见。

5.2 MVCC快照可见性判断流程

给定一个XID和一个当前时刻快照snapshot，判断该XID对应的事务对于该快照是否可见。

变量说明

• snapshot.xmin：获取快照时记录当前活跃的最小的XID
• snapshot.xmax：当前最新提交的“事务ID（latestCompleteXid） + 1”
• snaphot.csn：当前最新提交的“CSN + 1”（NextCommitSeqNo）

MVCC快照可见性判断的简易流程如下所示：

1. XID大于等于snapshot.xmax，该事务ID不可见
2. XID小于snapshot.xmin时，说明该事务ID在本次事务启动前已经结束了，需要查询事务的提交状态，并在元组头上设置相应的标记位
3. XID比snapshot.xmin和snapshot.xmax之间时，需要从CSN-XID映射种读取事务结束的CSN；如果CSN有值且比snapshot.csn小，表示该事务可见，否则不可见。
4. 

5.3 提交流程

1. 设置CSN-XID映射commit-in-progress标记
2. 原子更新NextCommitSeqNo值。
3. 生成redo日志，写CLOG，写CSNLOG。
4. 更新PGPROC，将对应的事务信息从PGPROC中移除，XID设置为InvalidTransactionId，xmin设置为InvalidTransactionId。
5. 

5.4 基本的可见性判断

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

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

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

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

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

5.4.1 xmin 的状态为 ABORTED

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

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

5.4.2 xmin 的状态为 IN_PROGRESS

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

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

5.4.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 之间的关系。

六、可见性判断函数与获取快照的时机

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

同时，我们可能通过在不同的时机获取快照来实现不同的事务隔离级别：

• 对于可重复读（RR）来说，只有事务的第一条语句才生成快照数据，随后的语句只是复用这个快照数据，以保证在整个事务期间，所有的语句对不同的堆元组具有相同的可见性判断依据。
• 对于读已提交（RC）来说，事务中的每条语句都会生成一个新的快照，以保证能够对其他事务已经提交的元组可见。

七、关键数据结构和函数

SnapshotData

获取快照时会记录当前活跃的最小的xid，记为snapshot.xmin。当前最新提交的“事务id(latestCompleteXid) + 1”，记为snapshot.xmax。当前最新提交的“CSN号 + 1”(NextCommitSeqNo)，记为snapshot.csn。

typedef struct SnapshotData {    SnapshotSatisfiesFunc satisfies;  /* 判断可见性的函数；通常使用MVCC，即HeapTupleSatisfiesMVCC */    TransactionId xmin; /*当前活跃事务最小值，小于该值的事务说明已结束  */    TransactionId xmax; /*最新提交事务id（latestCompeleteXid）+1，大于等于该值说明事务还未开始，该事务id不可见  */    TransactionId* xip; /*记录当前活跃事务链表，在CSN版本中该值无用  */    TransactionId* subxip; /* 记录缓存子事务活跃链表，在CSN版本中该值无用  */    uint32 xcnt; /* 记录活跃事务的个数（xip中元组数）在CSN版本中该值无用  */    ...    CommitSeqNo snapshotcsn; /* 快照的CSN号，一般为最新提交事务的CSN号+1(NextCommitSeqNo)，CSN号严格小于该值的事务可见。  */    ...    CommandId curcid; /*事务块中的命令序列号，即同一事务中，前面插入的数据，后面可见。  */    uint32 active_count; /* ActiveSnapshot stack的refcount */    uint32 regd_count;   /* RegisteredSnapshotList 的refcount*/    void* user_data;     /* 本地多版本快照使用，标记该快照还有线程使用，不能直接释放 */    SnapshotType snapshot_type; /*  openGauss单机无用  */} SnapshotData;

HeapTupleSatisfiesMVCC

static bool HeapTupleSatisfiesMVCC(HeapTuple htup, Snapshot snapshot, Buffer buffer){    // 取元组头    HeapTupleHeader tuple = htup->t_data;    ...    // 根据hint bit，若xmin没有被标记为已提交：可能被标记为回滚，或者还未标记    if (!HeapTupleHeaderXminCommitted(tuple)) {        // 如果xmin已经被标记为invalid，说明插入该元组的事务已经回滚，直接返回不可见        if (HeapTupleHeaderXminInvalid(tuple))              return false;        // xmin还未标记，并且xmin为当前事务，说明是在同一个事务内的插入命令和扫描命令，则需要去判断CID        // 同一个事务内，后面的查询可以查到当前事务之前命令插入的并且未删除的结果        if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(page, tuple))) {            if ((tuple->t_infomask & HEAP_COMBOCID) && CheckStreamCombocid(tuple, snapshot->curcid, page))                return true; /* delete after stream producer thread scan started */            // 当前扫描命令之后的某条命令才插入            if (HeapTupleHeaderGetCmin(tuple, page) >= snapshot->curcid)                return false; /* inserted after scan started */            // 到这里说明当前扫描命令之前已经插入            // 根据hint bit，xmax被标记为invalid            if (tuple->t_infomask & HEAP_XMAX_INVALID)                return true;            ...            // 当前扫描命令之后的某条命令删除了该元组            if (HeapTupleHeaderGetCmax(tuple, page) >= snapshot->curcid)                return true; /* deleted after scan started */            else                return false; /* deleted before scan started */        }         // xmin还没打标记，并且不是当前事务        else {            // 通过csnlog判断事务是否可见，并且返回该事务的最终提交状态            visible = XidVisibleInSnapshot(HeapTupleHeaderGetXmin(page, tuple), snapshot, &hintstatus, buffer, NULL);            // 如果该事务提交，则打上提交的hint bit用于加速判断            if (hintstatus == XID_COMMITTED)                SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED, HeapTupleHeaderGetXmin(page, tuple));            // 如果事务回滚，则打上回滚标记            if (hintstatus == XID_ABORTED) {                ...                SetHintBits(tuple, buffer, HEAP_XMIN_INVALID, InvalidTransactionId);            }            // 如果xmin不可见，则该元组不可见            if (!visible) {                ...                return false;            }        }    }     // 根据hint bit，若xmin已经被标记为已提交，则通过函数接口CommittedXidVisibleInSnapshot判断是否对本次快照可见    else {        /* xmin is committed, but maybe not according to our snapshot */        if (!HeapTupleHeaderXminFrozen(tuple) &&            !CommittedXidVisibleInSnapshot(HeapTupleHeaderGetXmin(page, tuple), snapshot, buffer)) {            if (...) {                return false; /* treat as still in progress */            }        }    }  // 到此为止认为xmin visible，继续判断xmax的可见性    recheck_xmax:    // 根据hint bit，xmax已经被标记为invalid，即已经回滚    if (tuple->t_infomask & HEAP_XMAX_INVALID) /* xid invalid or aborted */        return true;        ... // 还有一些其他状态判断        // 根据hint bit，xmax没有被标记为commited    if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED)) {        bool sync = false;        TransactionId xmax = HeapTupleHeaderGetXmax(page, tuple);        // 如果xmax为当前事务        if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(page, tuple))) {            // 如果删除该元组的命令后发生于快照扫描时刻            if (HeapTupleHeaderGetCmax(tuple, page) >= snapshot->curcid)                return true; /* deleted after scan started */            else                return false; /* deleted before scan started */        }        visible = XidVisibleInSnapshot(HeapTupleHeaderGetXmax(page, tuple), snapshot, &hintstatus, buffer, &sync);        /*         * If sync wait, xmax may be modified by others. So we need to check xmax again after acquiring the page lock.         */        if (sync && (xmax != HeapTupleHeaderGetXmax(page, tuple))) {            goto recheck_xmax;        }        // 根据hintstatus在元组头部打标记 hint bit        if (hintstatus == XID_COMMITTED) {            SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED, HeapTupleHeaderGetXmax(page, tuple));        }        if (hintstatus == XID_ABORTED) {            ...            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);        }        if (!visible) {            if (...) {                if (sync && (xmax != HeapTupleHeaderGetXmax(page, tuple))) {                    goto recheck_xmax;                }                    return true; /* treat as still in progress */            }        }    }     // 根据hint bit，xmax被标记为commited    else {        /* xmax is committed, but maybe not according to our snapshot */        if (!CommittedXidVisibleInSnapshot(HeapTupleHeaderGetXmax(page, tuple), snapshot, buffer)) {            if (...) {                return true; /* treat as still in progress */            }        }    }    return false;}

HeapTupleHeaderData

./src/include/storage/bufpage.htypedef struct HeapTupleHeaderData {    union {        HeapTupleFields t_heap;        DatumTupleFields t_datum;    } t_choice;    ItemPointerData t_ctid; /* current TID of this or newer tuple */    /* Fields below here must match MinimalTupleData! */    uint16 t_infomask2; /* number of attributes + various flags */    uint16 t_infomask; /* various flag bits, see below */    uint8 t_hoff; /* sizeof header incl. bitmap, padding */    /* ^ - 23 bytes - ^ */    bits8 t_bits[FLEXIBLE_ARRAY_MEMBER]; /* bitmap of NULLs -- VARIABLE LENGTH */    /* MORE DATA FOLLOWS AT END OF STRUCT */} HeapTupleHeaderData;