数据库内核月报

数据库内核月报 - 2017 / 10

PgSQL · 特性分析 · MVCC机制浅析

Author: 卓刀

背景

我们在使用PostgreSQL的时候,可能会碰到表膨胀的问题(关于表膨胀可以参考之前的月报),即表的数据量并不大,但是占用的磁盘空间比较大,查询比较慢。为什么PostgreSQL有可能发生表膨胀呢?这是因为PostgreSQL引入了MVCC机制来保证事务的隔离性,实现数据库的隔离级别。

在数据库中,并发的数据库操作会面临脏读(Dirty Read)、不可重复读(Nonrepeatable Read)、幻读(Phantom Read)和串行化异常等问题,为了解决这些问题,在标准的SQL规范中对应定义了四种事务隔离级别:

当前PostgreSQL已经支持了这四种标准的事务隔离级别(可以使用SET TRANSACTION语句来设置,详见文档),下表是PostgreSQL官方文档上列举的四种事务隔离级别和对应数据库问题的关系:

Isolation Level Dirty Read Nonrepeatable Read Phantom Read Serialization Anomaly
Read uncommitted Allowed, but not in PG Possible Possible Possible
Read committed Not possible Possible Possible Possible
Repeatable read Not possible Not possible Allowed, but not in PG Possible
Serializable Not possible Not possible Not possible Not possible

需要注意的是,在PostgreSQL中:

在PostgreSQL中,为了保证事务的隔离性,实现数据库的隔离级别,引入了MVCC(Multi-Version Concurrency Control)多版本并发控制。

MVCC常用实现方法

一般MVCC有2种实现方法:

两种方法各有利弊,相对于第一种来说,PostgreSQL的MVCC实现方式优缺点如下:

PostgreSQL中MVCC的具体实现

为了实现MVCC机制,必须要:

接下来,我们会按照上面的顺序,首先介绍多版本元组的存储结构,再介绍事务快照、数据可见性的判断以及数据库隔离级别的实现。

多版本元组存储结构

为了定义MVCC 中不同版本的数据,PostgreSQL在每个元组的头部信息HeapTupleHeaderData中引入了一些字段如下:

struct HeapTupleHeaderData
{
	union
	{
		HeapTupleFields t_heap;
		DatumTupleFields t_datum;
	}			t_choice;

	ItemPointerData t_ctid;		/* current TID of this or newer tuple (or a
								 * speculative insertion token) */

	/* 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 */

	/* MORE DATA FOLLOWS AT END OF STRUCT */
};

其中:

#define HEAP_HASNULL        0x0001    /* has null attribute(s) */
#define HEAP_HASVARWIDTH        0x0002    /* has variable-width attribute(s) 有可变参数 */
#define HEAP_HASEXTERNAL        0x0004    /* has external stored attribute(s) */
#define HEAP_HASOID        0x0008    /* has an object-id field */
#define HEAP_XMAX_KEYSHR_LOCK    0x0010    /* xmax is a key-shared locker */
#define HEAP_COMBOCID        0x0020    /* t_cid is a combo cid */
#define HEAP_XMAX_EXCL_LOCK    0x0040    /* xmax is exclusive locker */
#define HEAP_XMAX_LOCK_ONLY    0x0080    /* xmax, if valid, is only a locker */
/* xmax is a shared locker */
#define HEAP_XMAX_SHR_LOCK  (HEAP_XMAX_EXCL_LOCK | HEAP_XMAX_KEYSHR_LOCK)
#define HEAP_LOCK_MASK    (HEAP_XMAX_SHR_LOCK | HEAP_XMAX_EXCL_LOCK | \
                         HEAP_XMAX_KEYSHR_LOCK)
#define HEAP_XMIN_COMMITTED    0x0100    /* t_xmin committed 即xmin已经提交*/
#define HEAP_XMIN_INVALID        0x0200    /* t_xmin invalid/aborted */
#define HEAP_XMIN_FROZEN        (HEAP_XMIN_COMMITTED|HEAP_XMIN_INVALID)
#define HEAP_XMAX_COMMITTED    0x0400    /* t_xmax committed即xmax已经提交*/
#define HEAP_XMAX_INVALID        0x0800    /* t_xmax invalid/aborted */
#define HEAP_XMAX_IS_MULTI        0x1000    /* t_xmax is a MultiXactId */
#define HEAP_UPDATED        0x2000    /* this is UPDATEd version of row */
#define HEAP_MOVED_OFF        0x4000    /* moved to another place by pre-9.0                    * VACUUM FULL; kept for binary                     * upgrade support */
#define HEAP_MOVED_IN        0x8000    /* moved from another place by pre-9.0                * VACUUM FULL; kept for binary                  * upgrade support */
#define HEAP_MOVED (HEAP_MOVED_OFF | HEAP_MOVED_IN)
#define HEAP_XACT_MASK        0xFFF0    /* visibility-related bits */

上文HeapTupleHeaderData中的t_heap存储着元组的一些描述信息,结构如下:

typedef struct HeapTupleFields
{
TransactionId t_xmin;   /* inserting xact ID */
TransactionId t_xmax;   /* deleting or locking xact ID */

union
{
   CommandId t_cid;   /* inserting or deleting command ID, or both */
   TransactionId t_xvac; /* VACUUM FULL xact ID */
}    t_field3;
} HeapTupleFields;

其中:

这里需要简单介绍下PostgreSQL中的事务ID:

PostgreSQL主要就是通过t_xmin,t_xmax,cmin和cmax,ctid,t_infomask来唯一定义一个元组(t_xmin,t_xmax,cmin和cmax,ctid实际上也是一个表的隐藏的标记字段),下面以一个例子来表示元组更新前后各个字段的变化。

postgres=# create table test(id int);
CREATE TABLE
postgres=# insert into test values(1);
INSERT 0 1
postgres=# select ctid, xmin, xmax, cmin, cmax,id from test;
 ctid  | xmin | xmax | cmin | cmax | id
-------+------+------+------+------+----
 (0,1) | 1834 |    0 |    0 |    0 |  1
(1 row)
postgres=# update test set id=2;
UPDATE 1
postgres=# select ctid, xmin, xmax, cmin, cmax,id from test;
 ctid  | xmin | xmax | cmin | cmax | id
-------+------+------+------+------+----
 (0,2) | 1835 |    0 |    0 |    0 |  2
(1 row)
postgres=# select * from heap_page_items(get_raw_page('test',0));
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid
----+--------+----------+--------+--------+--------+----------+--------+-------------+------------+--------+--------+-------
  1 |   8160 |        1 |     28 |   1834 |   1835 |        0 | (0,2)  |       16385 |       1280 |     24 |        |
  2 |   8128 |        1 |     28 |   1835 |      0 |        0 | (0,2)  |       32769 |      10496 |     24 |        |

从上面可知,实际上数据库存储了更新前后的两个元组,这个过程中的数据块中的变化大体如下: image.png

Tuple1更新后会插入一个新的Tuple2,而Tuple1中的ctid指向了新的版本,同时Tuple1的xmax从0变为1835,这里可以被认为被标记为过期(只有xmax为0的元组才没过期),等待PostgreSQL的自动清理辅助进程回收掉。

也就是说,PostgreSQL通过HeapTupleHeaderData 的几个特殊的字段,给元组设置了不同的版本号,元组的每次更新操作都会产生一条新版本的元组,版本之间从旧到新形成了一条版本链(旧的ctid指向新的元组)。

不过这里需要注意的是,更新操作可能会使表的每个索引也产生新版本的索引记录,即对一条元组的每个版本都有对应版本的索引记录。这样带来的问题就是浪费了存储空间,旧版本占用的空间只有在进行VACCUM时才能被回收,增加了数据库的负担。

为了减缓更新索引带来的影响,8.3之后开始使用HOT机制。定义符合下面条件的为HOT元组:

更新一条HOT元组不需要引入新版本的索引,当通过索引获取元组时首先会找到最旧的元组,然后通过元组的版本链找到HOT元组。这样HOT机制让拥有相同索引键值的不同版本元组共用一个索引记录,减少了索引的不必要更新。

事务快照的实现

为了实现元组对事务的可见性判断,PostgreSQL引入了事务快照SnapshotData,其具体数据结构如下:

typedef struct SnapshotData
{
    SnapshotSatisfiesFunc satisfies;    /* tuple test function */
    TransactionId xmin;        /* all XID < xmin are visible to me */
    TransactionId xmax;        /* all XID >= xmax are invisible to me */
    TransactionId *xip;    //所有正在运行的事务的id列表
    uint32    xcnt;    /* # of xact ids in xip[],正在运行的事务的计数 */
    TransactionId *subxip;           //进程中子事务的ID列表
    int32    subxcnt;        /* # of xact ids in subxip[],进程中子事务的计数 */
    bool    suboverflowed;    /* has the subxip array overflowed? */
    bool    takenDuringRecovery;    /* recovery-shaped snapshot? */
    bool    copied;            /* false if it's a static snapshot */
    CommandId    curcid;    /* in my xact, CID < curcid are visible */
    uint32    speculativeToken;
    uint32    active_count;    /* refcount on ActiveSnapshot stack,在活动快照链表里的
*引用计数 */
    uint32    regd_count;    /* refcount on RegisteredSnapshots,在已注册的快照链表
*里的引用计数 */
    pairingheap_node ph_node;    /* link in the RegisteredSnapshots heap */
    TimestampTz  whenTaken;    /* timestamp when snapshot was taken */
    XLogRecPtr   lsn;        /* position in the WAL stream when taken */
} SnapshotData;

这里注意区分SnapshotData的xmin,xmax和HeapTupleFields的t_xmin,t_xmax

事务快照是用来存储数据库的事务运行情况。一个事务快照的创建过程可以概括为:

其中根据xmin和xmax的定义,事务和快照的可见性可以概括为:

satisfies是PostgreSQL提供的对于事务可见性判断的统一操作接口。目前在PostgreSQL 10.0中具体实现了以下几个函数:

上述几个函数的参数都是 (HeapTuple htup, Snapshot snapshot, Buffer buffer),其具体逻辑和判断条件,本文不展开具体讨论,有兴趣的可以参考《PostgreSQL数据库内核分析》的7.10.2 MVCC相关操作。

此外,为了对可用性判断的过程进行加速,PostgreSQL还引入了Visibility Map机制(详见文档)。Visibility Map标记了哪些page中是没有dead tuple的。这有两个好处:

另外visibility map相对整个relation,还是小很多,可以cache到内存中。

隔离级别的实现

PostgreSQL中根据获取快照时机的不同实现了不同的数据库隔离级别(对应代码中函数GetTransactionSnapshot):

总结

为了保证事务的原子性和隔离性,实现不同的隔离级别,PostgreSQL引入了MVCC多版本机制,概括起就是:

如上文所讲,PostgreSQL的MVCC实现方法有利有弊。其中最直接的问题就是表膨胀,为了解决这个问题引入了AutoVacuum自动清理辅助进程,将MVCC带来的垃圾数据定期清理,这部分内容我们将在下期月报进行分析,敬请期待。