数据库内核月报 - 2019 / 07

PgSQL · 新特性解读 · undo log 存储接口(上)

背景

PostgreSQL 数据库通过采用保存旧的元组来实现MVCC 机制,这就容易造成数据的膨胀。数据的膨胀不仅增加了存储的空间,而且可能降低查询的性能。为了解决这个问题,PostgreSQL 开源社区进行了一系列的讨论。

目前来看,社区内部比较认可的解决方案是构建一种新的存储格式,例如zheap。在EnterpriseDB 公司(后文简称为EDB)的对外分享中,也解释了为什么需要一种新的存储格式:

  • 所有数据库的MVCC 机制都需要保存旧版本的数据,但是具体的方法不同:
    • PostgreSQL 和Firebird 把新旧数据都直接存储在表中,通过一些辅助的字段来确定元组的对外可见性。
    • Oracle 和 MySQL 将旧数据保存在undo log 中。
    • SQL Server 将旧数据保存在tempdb 中。
  • 在表中存储旧的数据会使得清理变得困难,很多时候需要CLUSTER or VACUUM FULL。
  • 之前对VACUUM 的优化可以改善数据膨胀,但是不能完全避免它。

而zheap 这种新的存储格式致力于:

  • 更好控制数据膨胀:
    • 在原来的位置上直接更新数据避免数据膨胀。
    • 当commit 或者abort 之后重用空间,更少或者直接不需要引入VACUUM。
  • 更少的数据写:
    • hint-bits, freezing 等其他辅助信息的改变不会引发数据脏页,只有数据内容改变才会引发脏页写。
    • 当index 对应列更新,对应的index 标记为deleted 来支持原位置上更新数据。如果index 列没有更新,则不需要index 的操作。这也有利于控制数据膨胀。
  • 更小的数据大小:
    • 大多数的事务信息不再需要,大大缩小了元组的头部信息。
    • 减少了很多数据的对齐填充。

为了最终将zheap 这个新存储格式对应代码合入到社区主干,当前EDB 计划分几步走:

  • 提供可插拔的存储接口。PostgreSQL 12 已支持。
  • 提供undo log 相关机制和接口。
  • 提供zheap 存储格式。

其中的undo log 就是我们本文讨论的重点,目前该特性已经在社区的邮件列表中(邮件列表详见链接)提交了POC,同时引发了社区广泛的讨论。

但是为什么需要undo log 呢?目前来看,有以下几个可见的收益:

  • 当事务回滚时,undo log 可以快速回滚数据,相比之前的实现(标记该事务为没有提交,对应数据变成对外不可见的垃圾数据)大大减少数据膨胀。
  • 旧版本的数据存储在undo log 中,其清理或者重用,几乎对正常的数据访问无影响。
  • undo log 单独存储,可以设计高效的清理机制,避免数据膨胀。
  • undo log 解决了创建表的事务中崩溃后的孤儿文件残留的问题。

而从邮件列表中,我们可以看出社区对undo log 相关的讨论可以分成三个patch:

  • Undo log manager
  • Undo worker and transaction rollback
  • Cleaning up orphaned files using undo logs

本文主要讨论第一个patch 的逻辑和一些具体实现。在该patch 的简介中,介绍该patch 实现了一个undo log 的管理子系统,解决了以下几个问题:

  • 多个并发后台进程下和logs 一样高效地undo data 空间申请,。
  • 对无效的undo data 和queue 一样高效地清理。
  • 对undo data 和relation 一样高效地随机读访问。

值得注意的是,在这几个patch 的具体实现中,只涉及到了undo log 的管理控制机制和文件读写接口,但是并没有涉及到undo log 的具体内容和具体访问方法,这部分的内容由其上层的client code 来具体设计,例如zheap。

我们接下来主要分析上文说到的该patch 解决的三个问题。

物理存储结构

在该patch 中,undo log 被存储在$PGDATA/base/undo 下。另外用户可以设的GUC 参数undo_tablespaces 将对应undo log 保存在其他的tablespace 路径/undo 下。

undo log 文件名按照xxxxxx.xxxxxxxxxx 格式命名,其中每一位都是16进制数字。和redo log 相同,undo log 每个记录是由64 位的数字来表示其位点,对应去掉“.”的文件名。其中前24 位表示undo log 虚拟文件号,对应文件名的前6个数字。多个undo log 虚拟文件号可以允许undo log 的空间并行分配,减少锁的冲突。而后面的40位表示undo log 的文件内偏移,所以每个undo log 文件最大为1TB。

每个undo log 虚拟文件是由多个segment 组成,每个segment 目前是由128 个undo log 数据页面组成,默认大小为128 * 8kB,即1MB。特别注意:在文件系统中,每个segment 是一个实际的文件,而undo log 虚拟文件是一个虚拟的文件概念。

共享内存结构

因为每个连接都可能写入undo log,为了对undo log 进行管理,在共享内存中分配了一块共享内存结构来存储undo log 的管理信息。这块共享内存分为2部分:

  • UndoLogSharedData ,结构如下:
typedef struct UndoLogSharedData
{
	UndoLogNumber free_lists[UndoPersistenceLevels];
	UndoLogNumber low_logno; /* the lowest logno */
	UndoLogNumber next_logno; /* one past the highest logno */
	UndoLogNumber array_size; /* how many UndoLogControl objects do we have? */
	UndoLogControl logs[FLEXIBLE_ARRAY_MEMBER];
} UndoLogSharedData;
  • UndoLogNumSlots 个 UndoLogControl ,结构如下:
typedef struct UndoLogControl
{
	/*
	 * Protected by UndoLogLock and 'mutex'.  Both must be held to steal this
	 * slot for another undolog.  Either may be held to prevent that from
	 * happening.
	 */
	UndoLogNumber logno;			/* InvalidUndoLogNumber for unused slots */

	/* Protected by UndoLogLock. */
	UndoLogNumber next_free;		/* link for active unattached undo logs */

	/* Protected by 'mutex'. */
	LWLock	mutex;
	UndoLogMetaData meta;			/* current meta-data */
	XLogRecPtr      lsn;
	bool	need_attach_wal_record;	/* need_attach_wal_record */
	pid_t		pid;				/* InvalidPid for unattached */
	TransactionId xid;

	/* Protected by 'discard_lock'.  State used by undo workers. */
	LWLock		discard_lock;		/* prevents discarding while reading */
	TransactionId	oldest_xid;		/* cache of oldest transaction's xid */
	uint32		oldest_xidepoch;
	UndoRecPtr	oldest_data;
} UndoLogControl;

其中UndoLogNumSlots 目前取值为MaxBackends * 4,决定了当前多少个undo log 可以同时活跃状态,这也直接限制了最大(造成数据变化)的事务数。

UndoLogControl 结构中meta 是存储的对应undo log 虚拟文件的元信息,结构如下:

typedef struct UndoLogMetaData
{
	UndoLogNumber logno;
	UndoLogStatus status;
	Oid		tablespace;
	UndoPersistence persistence;	/* permanent, unlogged, temp? */
	UndoLogOffset insert;			/* next insertion point (head) */
	UndoLogOffset end;				/* one past end of highest segment */
	UndoLogOffset discard;			/* oldest data needed (tail) */
	UndoLogOffset last_xact_start;	/* last transactions start undo offset */

	/*
	 * If the same transaction is split over two undo logs then it stored the
	 * previous log number, see file header comments of undorecord.c for its
	 * usage.
	 *
	 * Fixme: See if we can find other way to handle it instead of keeping
	 * previous log number.
	 */
	UndoLogNumber prevlogno;		/* Previous undo log number */
	bool	is_first_rec;

	/*
	 * last undo record's length. We need to save this in undo meta and WAL
	 * log so that the value can be preserved across restart so that the first
	 * undo record after the restart can get this value properly.  This will be
	 * used going to the previous record of the transaction during rollback.
	 * In case the transaction have done some operation before checkpoint and
	 * remaining after checkpoint in such case if we can't get the previous
	 * record prevlen which which before checkpoint we can not properly
	 * rollback.  And, undo worker is also fetch this value when rolling back
	 * the last transaction in the undo log for locating the last undo record
	 * of the transaction.
	 */
	uint16	prevlen;
} UndoLogMetaData;

每个undo log 虚拟文件的元信息如果有变化会在checkpoint 时刷到磁盘上保证其持久化,这样在数据库崩溃恢复的时候能够提供足够的信息。

每个backend 启动时都会生成自己的MyUndoLogState 结构,保存了上述共享内存UndoLogSharedData 的指针,同时都会维护一个hash 表,可以映射undo log 虚拟文件号和对应的UndoLogControl,而且还保存了该undo log 虚拟文件的tablespace 和status。

undo log 空间申请

这部分的逻辑在UndoRecPtr UndoLogAllocate(size_t size, UndoPersistence persistence) 函数中,其参数size 为申请的空间大小,persistence 为申请的具体持久化级别(包含UNDO_PERMANENT,UNDO_UNLOGGED,UNDO_TEMP与relation data 的持久化级别对应),返回一个undo log 的可插入位点,其具体的流程可以概括为:

  1. 从MyUndoLogState 中获取当前该持久化级别的undo log 虚拟文件的控制信息UndoLogControl,如果为空或者tablespace 变化了,则需要去申请新的undo log 虚拟文件并填充它的控制信息:

    a. 确认tablespace,persistence 等信息,从共享内存的UndoLogSharedData中找到对应的空闲undo log 虚拟文件号。 b. 如果当前有空闲的undo log 虚拟文件号,则会通过上文的hash 表获取对应的UndoLogControl 控制信息。如果hash 表中未找到,则通过遍历UndoLogSharedData 中的logs 来获取对应的UndoLogControl 控制信息,并且将undo log 虚拟文件号和UndoLogControl 的映射关系存储在上文的hash 表中,便于下次检索。这步会去比对tablespace,persistence 等信息,很可能虽然有空闲的undo log 文件,但其tablespace,persistence属性不对。 c. 如果未找到期望的undo log 虚拟文件,则需要分配最近最新的undo log 虚拟文件,同时更新其元信息。插入一条xl_undolog_create 类型的WAL 日志记录。下期月报会介绍当前支持undo log 的几种WAL 日志记录类型。 d. 更新获取的undo log 虚拟文件的UndoLogControl 信息,并更新MyUndoLogState。

  2. 如果获取的undo log 的xid 为空,则为undo log 的第一个record,更新其控制信息。当持久化级别为UNDO_PERMANENT时,则插入一条xl_undolog_attach 类型的WAL 日志记录。
  3. 如果当前的segment 不够存储size 大小的记录时:

    a. 如果当前的undo log 虚拟文件(1TB)不足存储size 大小的记录,则将当时的undo log 虚拟文件释放,将undo log 虚拟文件置为空,并重新执行步骤1。 b. 如果当前的undo log 虚拟文件足够存储size 大小的记录,则需要申请一个新的segment。即在文件系统中申请一个数据填充为0 、大小为UndoLogSegmentSize 的新文件。同时插入一条xl_undolog_extend 类型的WAL 日志记录,更新undo log 虚拟文件元信息中的end 位点。

  4. 将得到的undo log 虚拟文件号和insert 位点拼接,返回64位插入位点。

这样,我们就得到了可分配size 空间的undo log 插入位点。从上文可知,通过这个位点我们就可以进行对应的undo log 写操作。不过这里只提供了一个接口,具体实现需要对应的client code 来实现。

可以看出,为了加快undo log 申请空间的速度,这里做了一些设计:

  • 每个后台进程保存undo log 虚拟文件号到 UndoLogControl 的hash 映射。因为在整个空间申请的过程中,需要高频地访问和更新UndoLogControl,增加hash 表的设计将这个过程复杂度变低,更加高效。
  • 变量本地化。MyUndoLogState 保存着本进程undo log 空间申请的绝大多数信息,大多数时间无需加锁,非常高效。
  • 锁比较细粒度。很多地方的设计将锁更加细粒度,例如因为WAL 日志中恢复行为的不一致,将undo log 和relation data 一样也分为了不同的持久化级别,并分开进行存储其空闲队列和本地的活跃队列。
  • 可多进程并行批量分配物理空间。根据当前的实现,每个backend 每次可扩容(真正的文件操作)一个segment 大小的空间,即上文的1MB,而且多个backend 可以并行分配。

不过因为该patch 还在讨论中,所以在代码实现中有一些TODO 和有疑问的地方,例如:

  • MaxBackends * 4 个UndoLogControl 控制信息是否足够?
  • 申请新的undo log 虚拟文件时是否需要加锁?

undo log 的清理

这部分的逻辑是在UndoLogDiscard(UndoRecPtr discard_point, TransactionId xid) 函数中实现,其中discard_point 是要清理的undo log 位点,xid是该undo log 位点对应的xid,具体流程如下:

  1. 获取undo log 虚拟文件对应的UndoLogControl。
  2. 如果undo log 虚拟文件已经写满,并且清理的位点等于当前undo log 虚拟文件的insert 位点,则标记为该undo log 虚拟文件需要全部清理。
  3. 清理buffer pool 中对应的buffers。其中buffers 是从旧的清理位点到现在请求的清理位点之间所有undo log 数据页的buffers。这里需要注意的是其中不包含新清理位点所在的undo log 数据页(可能仍然包含数据),但是如果该undo log 虚拟文件满了,则包含新位点所在的undo log 数据页,即该undo log 虚拟文件最后一个segment 的最后一个数据页。其中这个过程需要对每个undo log 数据页执行以下的步骤:

    a. 根据提供的信息构造buffer tag(undo log 的读写小节中会具体介绍)。 b. 根据buffer tag 在缓存hash 表中搜索该undo log 数据页,如果搜索到,则释放对应的缓存描述符,并将对应buffer 置为free,否则直接返回。

  4. 如果是旧清理位点和新清理位点跨越了segment,需要涉及到文件的操作,则需要对新旧清理位点之间的所有的segments 文件进行如下操作:

    a. 告知undofile_sync 该文件可能会丢失,同时将该文件的fsync 请求发送给checkpoint。 b. 如果该segment 可以循环(当前undo log 虚拟文件没有空闲的segment 并且该undo log 虚拟文件是活跃状态),则将该segment 文件重命名,同时更新undo log 虚拟文件的end 位点;否则对该segment 文件执行unlink 操作。

  5. 插入一条xl_undolog_discard 类型的WAL 日志记录。如果是步骤4中跨越了segment 的情况,则必须要将WAL 日志flush 到磁盘,保证WAL 日志在数据落盘之前落盘。
  6. 当需要对undo log 全部清理的时候,需要将UndoLogSharedData 中对应的UndoLogControl slot 释放。

从这部分的实现上,我们可以看出:

  • undo log 可以批量进行清理。
  • undo log segment 文件可以复用。
  • 无需保证对文件的修改立刻生效(fsync),只需要记录到WAL 日志中即可。

这无疑会使得清理比较高效,但是当前的实现也存在一些问题:

  • 必须保证新的清理位点之前的undo log 数据没有任何的进程将会访问。
  • 当前每次回收只能回收一个segment。

undo log 的读写

其实目前并没有实现undo log 文件基于buffer pool 的读写,根据作者的说明,这部分需要client code 自己去实现。但是该patch 实现了SMGR 兼容的读写访问接口,这就使得使用buffer pool 访问undo log 成为可能。从undo log 的清理中也可以看出,清理的时候会去清理buffer pool 中的undo log 数据页。

而为了实现SMGR 兼容的读写访问接口:

  • 在smgr 中增加undo log 的存储接口函数定义和具体实现。
  • 将一个undo log 数据页转换为和relation data 数据页相同的唯一访问标示。

我们知道relation data 文件可以由RelFileNode 结构唯一标示其物理位置,即RelFileNode 保存着访问具体文件的物理位置的所有信息,其结构如下:

typedef struct RelFileNode
{
	Oid			spcNode;		/* tablespace */
	Oid			dbNode;			/* database */
	Oid			relNode;		/* relation */
} RelFileNode;

而根据上文的定义,undo log 也是具有tablespace 属性的,所以可以对应RelFileNode 结构中的spcNode,而undo log 虚拟文件号可以对应relNode。其实根据这两个就可以唯一标示其文件的物理位置,但是为了区分relation data 和 undo log,把undo log 的dbNode 属性设为固定值9。

这样,undo log 虚拟文件可以使用和relation data 文件相同的结构RelFileNode 来唯一标示其物理位置。而每个relation data 数据页可以通过BufferTag 结构来唯一标示其物理位置,其具体结构如下:

typedef struct buftag
{
	RelFileNode rnode;			/* physical relation identifier */
	ForkNumber	forkNum;
	BlockNumber blockNum;		/* blknum relative to begin of reln */
} BufferTag;

很明显,undo log 数据页也是有blockNum 属性的,而undo log 数据页没有各种fork 的概念,这里把其forkNum 设置为默认值MAIN_FORKNUM。

这样我们就可以使用相同的结构BufferTag 来唯一标示undo log 数据页和relation data 数据页的物理机位置,同时都可以通过该结构来访问共享内存中的buffer pool。

不过值得一提的是,因为undo log segment 文件的fd 的数量可控,所以并没有使用vfd 的技术。

总结

可以看出,因为undo log 中本质上存储的是旧的数据,所以在实现上也是尽量把undo log 作为一种数据来管理,包括:

  • 可以使用buffer pool。
  • 每次数据变更(这里主要指文件相关的操作)前都需要先写WAL 日志。
  • checkpoint 会定期fsync undo log 文件的变更。

这样能尽量复用原来的一些实现,而且相对来说也比较符合undo log 的定义。

至此,我们基本摸清了undo log 的存储管理相关的实现,但是未涉及与checkpoint 的联动、对应WAL 日志的内容以及对应的redo 操作(即如何崩溃恢复)。由于篇幅限制,这些内容将在下期月报进行分享。