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

  1. astore空间管理和回收
    openGauss中采用最大堆二叉树结构来记录和管理astore堆表页面的空闲空间,该最大堆二叉树结构按照页面粒度进行与存储介质的读写操作,并单独储存于专门的空闲空间位图文件中(free space map,简称FSM)。该FSM文件的结构如图4-8所示。

    所有页面分为叶子节点页面和内部节点页面两种。两种页面的页面内部结构完全相同,区别在于:对于叶子节点页面,其页面中记录的二叉树的叶子节点对应堆/索引表页面的空闲空间程度;对于内部节点页面,其页面中记录的二叉树的叶子节点对应下层FSM页面的最大空闲空间程度。
    使用FSM页面中的1个字节(即256档)来记录一个堆/索引页面的空闲空间程度。在FSM页面中不会记录任何堆/索引页面的页号信息,也不会记录任何根、子FSM节点页面的页号信息,这些信息主要通过以下的规则来计算得到:
    (1) 在一个FSM页面内部,二叉树节点按照从上到下、从左到右逐层排布,即:第一个字节为根节点的空闲程度,第二个字节为第一层内部节点最左边节点的空闲程度,依次类推。
    (2) 所有FSM页面在物理存储上采用深度优先顺序,即某个FSM页面之前所有的物理页面包括:该FSM页面所在子树的所有上层节点,加上该FSM页面所有左侧子树。
    (3)所有FSM叶子节点页面中的二叉树的叶子节点,对应堆/索引表页面的空闲空间程度,且根据从左到右的顺序,分别对应第1个、第2个、….、第n个堆/索引表物理页面。
    (4)除了(3)中这些FSM节点之外,其他FSM父节点保存子节点(子树)中空闲空间的最大值。
    根据上述算法,可以高效地查询出具有足够空闲空间的堆/索引页面的页面号,并将待插入的数据插入其中。
    FSM模块主要的对外接口和含义如表4-14所示。

此外,为了保证FSM信息的维护操作不会带来明显的开销,因此FSM的所有修改都是不记录日志的。同时,对于某个堆/索引页面对应的FSM信息,只在页面初始化和页面空闲空间整理(见本节后面介绍)两种场景下才会主动更新,除此之外,只有当新插入的数据发现该页面实际空间不足时才会被动更新该页面对应的FSM信息(也包括由于宕机导致的FSM页面损坏)。
空闲空间的管理难点在于空闲空间的回收。在openGauss中,对于astore存储格式,有3种回收空闲空间的方式,如图4-9所示。

  1. 轻量级堆页面清理
    当查询扫描到某个astore堆表页面时,会顺带尝试清理该页面上已经被删除的、足够老的元组(足够老是指在元组对于所有并发查询均为已经删除状态,具体参见事务处理章节)。由于只是顺带清理该页面内容,因此只能删除元组内容本身,元组指针还需要保留,以免在索引侧造成空引用或空指针(可参见4.2.5 行存储索引机制)。一个比较特殊的情况是HOT场景。HOT场景是指对于该表上所有的索引更新前后的索引键值均没有发生变化,因此对于更新后的元组只需要插入堆表元组而不需要新插入索引元组。对于同一个页面内一条HOT链上的多个元组,如果它们都足够老了,那么在清理时可以额外删除所有中间的元组指针,只保留第一个版本的元组指针,并将其重定向到第一个不用被清理的元组版本的元组指针。
    轻量级堆页面清理的接口是heap_page_prune_opt函数,关键的数据结构是PruneState结构体,定义代码如下:

TransactionId new_prune_xid; TransactionId latestRemovedXid; int nredirected; /* 待重定向的元组个数 */ int ndead; /* 待标记死亡的元组个数 */ int nunused; /* 待回收的元组个数 */ OffsetNumber redirected[MaxHeapTuplesPerPage * 2]; OffsetNumber nowdead[MaxHeapTuplesPerPage]; OffsetNumber nowunused[MaxHeapTuplesPerPage]; bool marked[MaxHeapTuplesPerPage + 1]; } PruneState;