数据库内核月报 － 2019 / 07

背景

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 操作（即如何崩溃恢复）。由于篇幅限制，这些内容将在下期月报进行分享。