存储引擎源码解析 | 磁盘引擎(3)

4.2.3 astore

1. astore整体框架
   astore整体框架如图4-2所示。如上所述，作为行存储子格式之一，astore需要实现自己的堆表存取（访存）管理接口、堆表页面结构、堆表元组结构、元组多版本机制，以及空闲空间管理和回收机制。

2. astore堆表页面元组结构
   本节介绍astore堆表的页面和元组结构。
   所谓堆表，是指元组无序存储，数据按照“先来后到”的方式存储在页面中的空闲位置。作为对比，在索引表中，元组根据索引键键值的排序，在页面内部有序存储，且各个页面之间在逻辑上也是有序存储的。堆表存储数据主体，索引表仅存储索引键键值以及对应的、完整元组的物理位置（即完整元组在堆表中的页面号和页内偏移）。
   1） astore堆表元组结构
   astore堆表元组结构的定义部分代码如下：

ShortTransactionId t_xmin; /* 插入元组事务的事务号 */
ShortTransactionId t_xmax; /* 删除元组事务的事务号 */
union {
CommandId t_cid; /* 插入或删除命令在事务中的命令号 */
ShortTransactionId t_xvac;
} t_field3;
} HeapTupleFields;

该结构体只是元组头部的定义，元组内容跟在该结构体后面，距离元组头部起始处的偏移由“t_hoff”成员保存。上面元组头部结构体部分成员信息，同时也构成了该元组的系统字段（字段序号小于0的那些字段）。对各个结构体成员的含义说明如下。
（1） t_xmin，插入元组的事务号（32位）。对应系统字段序号是MinTransactionIdAttributeNumber（-3）。
（2） t_xmax，删除元组的事务号（32位）。如果元组还没有被删除，那么为零。对应系统字段序号MaxTransactionIdAttributeNumber（-5）。
（3） t_cid，插入或删除元组的命令号。对应系统字段序号MinCommandIdAttributeNumber（-4）和MaxCommandIdAttributeNumber（-6）。
（4） t_ctid，当前元组的页面和页面内元组指针下标。如果该元组被更新，为更新后元组的页面号和页面内元组指针下标。
（5） t_infomask2，元组属性掩码，包含元组中字段个数、HOT（heap only tuple，堆内元组）更新标记、HOT元组标记等。
（6） t_infomask，元组另一个属性掩码，包含是否有空字段标记、是否有变长字段标记、是否有外部TOAST（the oversized-attribute storage technique，过长字段存储技术）标记、是否有OID字段标记、是否有压缩标记、插入事务是否提交/回滚标记、删除事务是否提交/回滚标记、是否被更新标记等。如果OID标记存在，那么元组OID从“t_hoff”偏移位置之前4个字节获得，对应系统字段序号ObjectIdAttributeNumber（-2）。
（7） t_hoff，元组数据距离元组头部结构体起始位置的偏移。
（8） t_bits，所有字段的NULL值bitmap。每个字段对应t_bits中的一个bit位，因此是变长数组。
上述元组结构体在内存中使用时嵌入在一个更大的元组数据结构体中，该结构体的定义代码如下。除了保存元组内容的t_data成员之外，其他的成员保存了该元组的一些其他系统信息，这些信息构成了该元组剩余的一些系统字段内容：

uint32 t_len; /* 包括元组头部和数据在内的元组总大小 */
ItemPointerData t_self; /* 元组行号 */
Oid t_tableOid; /* 元组所属表的OID */
TransactionId t_xid_base;
TransactionId t_multi_base;
HeapTupleHeader t_data; /* 指向元组头部 */
} HeapTupleData;

该结构体主要成员的含义如下。
（1） t_len，元组长度。
（2） t_self，元组所在页面号和页面内元组指针下标，对应系统字段序号SelfItemPointerAttributeNumber（-1）。
（3） t_tableOid，该元组所属表的OID，对应系统字段序号TableOidAttributeNumber（-7）。
介绍了astore堆表元组结构，下面介绍常用的astore堆表元组操作接口。如表4-11所示。

heap_getattr操作接口在代码上做了多处优化：
（1） 判断待访问的字段序号是否大于元组头部保存的元组实际字段个数；如果大于，则通过访问pg_attribute系统表得到。该优化来自快速追加表字段特性。该特性允许用户在不需要重写一张表所有行的情况下，在一张表的最后增加一个或多个带默认值约束的字段。
（2） 如果该元组的字段全部非空并且待查询字段之前所有的字段都是定长的，那么在上一个heap_getattr查询该字段的操作过程中，会缓存该字段在元组中的字节偏移；之后再次查询时，当满足元组字段全部非空的情况下会使用上述缓存的偏移位置直接读取字段内容。
（3） 读取元组头部的NULL值bitmap，如果该字段对应的bitmap中的比特位非0，则直接返回NULL值。
2） astore堆表页面结构
由于整体行存储格式默认的介质管理器是磁盘文件系统，因此采用了和文件系统类似的段页式设计，最小I/O单元为一个页面，这样可以在大多数场景下获得比较好的I/O性能和较低的I/O开销。一个astore堆表页面默认大小为8kB，其结构如图4-4所示。

在一个astore堆表页面中，页面头部分对应HeapPageHeaderData结构体。其中，pd_multi_base以及之前的部分对应定长成员，存储了整个页面的重要元信息；pd_multi_base之后的部分对应元组指针变长数组，其每个数组成员存储了页面中从后往前的、每个元组的起始偏移和元组长度。如图4-4所示，真正的元组内容从页面尾部开始插入，向页面头部扩展；相应的，记录每条元组的元组指针从页面头定长成员之后插入，往页面尾部扩展；整个页面中间形成一个空洞，供后续插入的元组和元组指针使用。
对于一个astore堆表的一条具体元组，有一个全局唯一的逻辑地址，即元组头部的t_ctid，其由元组所在的页面号和页面内元组指针数组下标组成；该逻辑地址对应的物理地址，则由ctid和对应的元组指针成员共同给出。通过页面、对应元组指针数组成员、页面内偏移和元组长度的访问顺序，就可以完整获取到一条元组的完整内容。t_ctid结构体和元组指针结构体的定义代码如下。

typedef struct ItemPointerData {
BlockIdData ip_blkid; /* 页号 */
OffsetNumber ip_posid; /* 页面偏移，即对应的页内元组指针下标 */
} ItemPointerData;

如上两级的元组访问设计，主要有两个优点。
（1） 在索引结构中（参见“4.2.5 行存储索引机制”小节），只需要保存元组的t_ctid值即可，无须精确到具体字节偏移，从而降低了索引元组的大小（节约两个字节），提升索引查找效率；
（2） 将页面内元组的地址查找关系自封闭在页面内部的元组指针数组中，和外部索引解耦，从而在某些场景下可以让页面级空闲空间整理对外部索引数据没有影响，降低空闲空间回收的开销和设计复杂度。具体实现机制在“5. astore空间管理和回收”小节中介绍。
astore堆表页面头具体结构体定义代码如下：

PageXLogRecPtr pd_lsn; /* 页面最新一次修改的日志lsn */
uint16 pd_checksum; /* 页面CRC */
uint16 pd_flags; /* 标志位 */
LocationIndex pd_lower; /* 空闲位置开始出（距离页头） */
LocationIndex pd_upper; /* 空闲位置结尾处（距离页头） */
LocationIndex pd_special; /* 特殊位置起始处（距离页头） */
uint16 pd_pagesize_version;
ShortTransactionId pd_prune_xid;
TransactionId pd_xid_base;
TransactionId pd_multi_base;
ItemIdData pd_linp[FLEXIBLE_ARRAY_MEMBER];
} HeapPageHeaderData;

其中各个成员的含义如下。
（1） pd_lsn：该页面最后一次修改操作的预写日志结束位置的下一个字节，用于检查点推进和保持恢复操作的幂等性（幂等指对接口的多次调用所产生的结果和调用一次是一致的）。
（2） pd_checksum：页面的CRC校验值。
（3） pd_flags：页面标记位，用于保存各类页面相关的辅助信息，如页面是否有空闲的元组指针、页面是否已满、页面元组是否都可见、页面是否被压缩、页面是否是批量导入的、页面是否加密、页面采用的CRC校验算法等。
（4） pd_lower：页面中间空洞的起始位置，即当前已使用的元组指针数组的尾部。
（5） pd_upper：页面中间空洞的结束位置，即下一个可以插入元组的起始位置。
（6） pd_special：页面尾部特殊区域的起始位置。该特殊位置位于第一条元组记录和页面结尾之间，用于存储一些变长的页面级元信息，如采用的压缩算法信息、索引的辅助信息等。
（7） pd_pagesize_version：页面的大小和版本号。
（8） pd_prune_xid：页面清理辅助事务号（32位），通常为该页面内现存最老的删除或更新操作的事务号，用于判断是否要触发页面级空闲空间整理。实际使用的64位prune事务号由“pd_prune_xid”字段和“pd_xid_base”字段相加得到。
（9） pd_xid_base：该页面内所有元组的基准事务号（64位）。该页面所有元组实际生效的64位xmin/xmax事务号由“pd_xid_base”（64位）和元组头部的“t_xmin/t_xmax”字段（32位）相加得到。
（10） pd_multi_base：类似“pd_xid_base”字段，当对元组加锁时，会将持锁的事务号写入元组中，该64位事务号由“pd_multi_base”字段（64位）和元组头部的“t_xmax”字段（32位）相加得到。
（11） pd_linp：元组指针变长数组。
对于astore堆表页面的主要管理接口如表4-12所示。鉴于astore采用的元组多版本设计实现方式（参见“3. astore元组多版本机制”小节），删除操作并不会直接从页面中删除指定的元组，页面管理也没有提供这样的接口。对于被删除的、过于陈旧的元组，通过页面空闲空间整理流程（参见“5. astore空间管理和回收”小节）完成。

在astore堆表页面中，采用64位页面“pd_xid_base”字段和32位元组“t_xmin/t_xmax”字段组合设计方式的原因如下。
早期openGauss版本采用32位事务号，所以对于OLTP类系统事务号消耗速度很快。当消耗的事务号超过最大事务号一半左右时，整个系统会强制对所有元组进行防止事务号回卷的整理工作。这个过程将阻塞所有写查询，系统不可用。
为了解决这个问题，openGauss将事务号升级到64位。为了平滑兼容之前32位事务号的元组头部结构，没有改变元组的结构和长度，而是在32位事务号页面头部结构体的基础上，扩展增加了标识整个页面所有元组事务号范围的64位基准事务号“pd_xid_base”和“pd_multi_base”两个字段。同一个页面中所有元组实际的64位“xmin/xmax”字段，一定在“pd_xid_base”字段和“pd_xid_base+2322”之间。
可以通过astore堆表页面头部“pd_pagesize_version”字段中页面版本号来区分32位事务号页面和64位事务号页面：
（1） 版本号等于4，为32位事务号页面。
（2） 版本号等于5，为64位非堆表页面（如索引页面）。这类页面的页头无须保存64位事务号信息，因此和32位事务号页面采用相同的结构。这类页面中可能涉及的64位事务号信息，保存在页面尾部的“”pd_special”字段区域中。
（3） 版本号等于6，即为64位astore堆表页面。
对于从32位事务号系统升级上来的astore堆表页面，在部分页面访问场景中（如RelationGetBufferForTuple/heap_delete/heap_update/heap_lock_tuple），首先会判断访问的页面是否是4号版本。若是4号版本，则调用heap_page_upgrade尝试进行页面版本升级。当页面空闲空间足够放下扩展的两个成员（共16个字节）时，调用PageLocalUpgrade函数将页面格式升级到64位，且升级后的pd_xid_base字段和pd_multi_base字段一定为0；如果剩余空间不够，系统会给出报错或告警，并提示用户执行VACUUM FULL命令来手动升级页面。
对于需要修改元组事务号的操作（如heap_insert/heap_multi_insert/heap_delete/heap_update/heap_lock_tuple），需要判断新写入的64位事务号是否满足在页面的“pd_xid_base”和“pd_xid_base+232”之间。如果满足，则通过检查；否则，需要调整页面的“pd_xid_base”字段或“pd_multi_base”字段的值以满足上述条件。如果新写入的事务号和页面上现有任意一个元组的“xmin/xmax”事务号差距已经超过232，系统还会尝试对现有元组进行“freeze”（冻结）操作。如果“freeze”操作之后，上述事务号差距还是超过232，该查询会报错退出。
32位事务号astore堆表页面头结构代码如下所示，各成员含义可参考64位事务号页面头结构：

PageXLogRecPtr pd_lsn;
uint16 pd_checksum;
uint16 pd_flags;
LocationIndex pd_lower;
LocationIndex pd_upper;
LocationIndex pd_special;
uint16 pd_pagesize_version;
ShortTransactionId pd_prune_xid;
ItemIdData pd_linp[FLEXIBLE_ARRAY_MEMBER];
} PageHeaderData;

3. astore元组多版本机制
   openGauss行存储表支持多版本元组机制，即为同一条记录保留多个历史版本的物理元组以解决对同一条记录的读、写并发冲突（读事务和写事务工作在不同版本的物理元组上）。
   astore存储格式为追加写优化设计，其多版本元组产生和存储方式如图4-5所示。当一个更新操作将v0版本元组更新为v1版本元组之后，如果v0版本元组所在页面仍然有空闲空间，则直接在该页面内插入更新后的v1版本元组，并将v0版本的元组指针指向v1版本的元组指针。在这个过程中，新版本元组以追加写的方式和被更新的老版本元组混合存放，这样可以减少更新操作的I/O开销。然而，需要指出的是，由于新、老版本元组是混合存放的，因此在清理老版本元组时需要的清理开销会比较大。因此，astore存储格式比较适合频繁插入、少量更新的业务场景。

下面结合图4-6，介绍openGauss中行存储格式多版本元组的运行机制：

（1） 首先事务号为10的事务插入一条值为value1的新记录。对应的页面修改为：在0号物理页面的第一个元组指针指向位置，插入一条“xmin”字段为10、“xmax”字段为0、“ctid”字段为（0，1）、“data”字段为value1的物理元组。该事务提交，将CSN从3推进到4，并且在CSN日志中对应事务号10的槽位处记下该CSN的值。
（2） 然后事务号为12的事务将上面这条记录的值从value1修改为value2。对应的页面修改为：在0号物理页面的第二个元组指针指向位置，插入另一条“xmin”字段为12、“xmax”字段为0、“ctid”字段为（0，2）、“data”为value2的物理元组。同时保留上面第一条插入的物理元组，但是将其“xmax”字段从0修改为12，将其“ctid”字段修改为（0，2），即新版本元组的物理位置。该事务提交，将CSN从7推进到8，并且在CSN日志中对应事务号12的槽位处记下该CSN的值。
（3） 最后事务号为15的事务将上面这条记录的值从value2又修改为value3，对应的页面修改为：（假设0号页面已满）在1号物理页面的第一个元组指针指向位置，插入一条“xmin”字段为15、“xmax”字段为0、“ctid”字段为（1，1）、“data”字段为value3的物理元组；同时，保留上面第1、第2条插入的物理元组，但是将第2条物理元组的“xmax”字段从0修改为15，将其“ctid”字段修改为（1，1），即最新版本元组的物理位置。该事务提交，将CSN从9推进到10，并且在CSN日志中对应事务号15的槽位处记下该CSN的值。
（4） 对于并发的读事务，其在查询执行开始时，会获取当前的全局CSN值作为查询的快照CSN。对于上面同一条记录的3个版本的物理元组来说，该读查询操作只能看到同时满足如下两个条件的这个物理元组版本。
元组“xmin”字段对应的CSN值小于等于读查询的快照CSN。
元组“xmax”字段为0，或者元组“xmax”字段对应的CSN值大于读查询的快照CSN。
比如，若并发读查询的快照CSN为8，那么这条查询将看到value2这条物理元组；若并发读查询的快照CSN为11，那么这条查询将看到value3这条物理元组。
对于不同的行存储子格式，上述多版本元组的格式和存储方式可能有所不同，但是可见性判断和并发控制方式都是如图4-6中所示的。通过上面介绍的元组可见性判断流程，可以发现：并发的读事务会根据自己的查询快照在同一个记录的多个历史版本元组中选择合适的那个来返回。并且即使是在可重复读的事务隔离级别下，只要使用相同的快照总可以筛选出相同的那个历史版本元组。在整个过程中读事务不阻塞任何对该记录的并发写操作（更新和删除）。
更详细的元组可见性判断流程将在第5章中详细介绍。

最后，对于astore行存储格式，更新一条记录的详细执行流程如图4-7所示，该图可以帮助读者更形象地理解多版本元组的产生流程，以及写、写并发下的处理逻辑。