openGauss数据库源码解析系列文章——存储引擎源码解析（三）

上篇图文openGauss数据库源码解析系列文章——存储引擎源码解析（二）中，从astore和行存储索引机制两点对磁盘引擎进行了分享，本篇接着从磁盘引擎的行存储缓存机制、cstore、日志系统三方面展开介绍。

（五）行存储缓存机制

|图1 行存储缓存和淘汰机制示意图|

行存储堆表和索引表页面的缓存和淘汰机制主要包含以下几个部分：

1. 共享缓冲区内存页面数组下标哈希表

用于将远大于内存容量的物理页面与内存中有限个数的内存页面建立映射关系。该映射关系通过一个分段、分区的全局共享哈希表结构实现。哈希表的键值为buftag（页面标签）结构体。该结构体由“rnode”、“forkNum”、“blockNum”三个成员组成。其中“rnode”对应行存储表物理文件名的主体命名；“forkNum”对应主体命名之后的后缀命名，通过主体命名和后缀命名，可以找到唯一的物理文件；而“blockNum”对应该物理文件中的页面号。因此，该三元组可以唯一确定任意一个行存储表物理文件中的物理页面位置。哈希表的内容值为与该物理页面对应的内存页面的“buffer id”（共享内存页面数组的下标）。

typedef struct buftag {
    RelFileNode rnode; /* 表的物理文件位置结构体 */
    ForkNumber forkNum; /* 表的物理文件后缀信息 */
    BlockNumber blockNum; /* 页面号 */
} BufferTag;

2. 共享buffer desc数组

该数组有“g_instance.attr.attr_storage.NBuffers”个成员，与实际存储页面内容的共享buffer数组成员一一对应，用来存储相同“buffer id”（即这两个全局数组的下标）的数据页面的属性信息。该数组成员为BufferDesc结构体，具体定义代码如下：

typedef struct BufferDesc {
    BufferTag tag; /* Buffer页面标签 */
    pg_atomic_uint32 state; /* 状态位、引用计数、使用历史计数 */
    int buf_id;    /* Buffer下标 */
    ThreadId wait_backend_pid;
    LWLock* io_in_progress_lock;
    LWLock* content_lock;
    pg_atomic_uint64 rec_lsn;
    volatile uint64 dirty_queue_loc;
} BufferDesc;

（1）tag成员是该页面的（relfilenode，forknum，blocknum）三元组。

（2）state成员是该内存状态的标志位，主要包含BM_LOCKED（该buffer desc结构体内容的排他锁标志）、BM_DIRTY（脏页标志）、BM_VALID（有效页面标志）、BM_TAG_VALID（有效tag标志）、BM_IO_IN_PROGRESS（页面I/O状态标志）等。

（3）buf_id成员，是该成员在数组中的下标。

（4）wait_backend_pid成员，是等待页面unpin（取消引用）的线程的线程号。

（5）io_in_progress_lock成员，是用于管理页面并发I/O操作（从磁盘加载和写入磁盘）的轻量级锁。

（6）content_lock成员，是用于管理页面内容并发读写操作的轻量级锁。

（7）rec_lsn成员，是上次写入磁盘之后该页面第一次修改操作的日志lsn值。

（8）dirty_queue_loc成员，是该页面在全局脏页队列数组中的（取模）下标。

3. 共享buffer数组

4. bgwriter线程组

该数组有“g_instance.attr.attr_storage.bgwriter_thread_num”个线程。每个“bgwriter”线程负责一定范围内（目前为均分）的共享内存页面的写入磁盘操作，如图4-11中所示。如果全局共享buffer数组的长度为12，一共有3个“bgwriter”线程，那么第1个“bgwriter”线程负责“buffer id 0 - buffer id 3”的内存页面的维护和写入磁盘；第2个“bgwriter”线程负责“buffer id 4 - buffer id 7”的内存页面的维护和写入磁盘；第3个“bgwriter”线程负责buffer id 8 - buffer id 11的内存页面的维护和写入磁盘。每个“bgwriter”进程在后台循环扫描自己负责的那些共享内存页面和它们的buffer desc状态，将被业务修改过的脏页收集起来，批量写入双写文件，然后写入表文件系统。对于刷完的内存页，将其状态变为非脏，并追加到空闲buffer id队列的尾部，用于后续业务加载其他当前不在共享缓冲区的物理页面。每个“bgwriter”线程的信息记录在BgWriterProc结构体中，该结构体的定义代码如下：

typedef struct BgWriterProc {
    PGPROC *proc;
    CkptSortItem *dirty_buf_list;
    uint32 dirty_list_size;
    int *cand_buf_list;
    volatile int cand_list_size;
    volatile int buf_id_start;
    pg_atomic_uint64 head;
    pg_atomic_uint64 tail;
    bool need_flush;
    volatile bool is_hibernating;
    ThrdDwCxt thrd_dw_cxt;
    volatile uint32 thread_last_flush;
    int32 next_scan_loc;
} BgWriterProc;

（1）dirty_buf_list为存储每批收集到的脏页面buffer id的数组。dirty_list_size为该数组的长度。

（2）cand_buf_list为存储写入磁盘之后非脏页面buffer id的队列数组（空闲buffer id数组）。cand_list_size为该数组的长度。

（3）buf_id_start为该bgwriter负责的共享内存区域的起始buffer id，该区域长度通过“g_instance.attr.attr_storage.NBuffers g_instance.attr.attr_storage.bgwriter_thread_num”得到。

（4）head为当前空闲buffer id队列的队头数组下标，tail为当前空闲buffer id队列的队尾数组下标。

（5）next_scan_loc为上次bgwriter循环扫描时停止处的buffer id，下次收集脏页从该位置开始。

5. pagewriter线程组

typedef struct PageWriterProc {
    PGPROC* proc;
    volatile uint32 start_loc;
    volatile uint32 end_loc;
    volatile bool need_flush;
    volatile uint32 actual_flush_num;
} PageWriterProc;

（1）proc成员为“pagewriter”线程属性信息。

（2）start_loc为分配给本线程待写入磁盘的脏页在全量脏页队列中的起始位置。

（3）end_loc为分配给本线程待写入磁盘的脏页在全量脏页队列中的结尾位置。

（4）need_flush为是否有脏页被分配给本“pagewriter”的标志。

（5）actual_flush_num为本批实际写入磁盘的脏页个数（有些脏页在分配给本“pagewriter”线程之后，可能被“bgwriter”线程写入磁盘，或者被DROP（删除）类操作失效）。

6. 双写文件

（1）计算“buffer tag”对应的hash值和分区值。

（2）对“buffer id”哈希表加分区共享锁，并查找“buffer tag”键值是否存在。

（3）如果“buffer tag”键值存在，确认对应的磁盘页面是否已经加载上来。如果是，则直接返回对应的“buffer id + 1”；如果不是，则尝试加载到该“buffer id”对应的buffer内存中，然后返回“buffer id + 1”。

（4）如果“buffer tag”键值不存在，则寻找一个“buffer id”来进行替换。首先尝试从各个“bgwriter”线程的空闲“buffer id”队列中获取可以用来替换的“buffer id”；如果所有“bgwriter” 线程的空闲buffer id队列都为空队列，那么采用clock-sweep算法，对整个buffer缓冲区进行遍历，并且每次遍历过程中将各个buffer的使用计数减一，直到找到一个使用计数为0的非脏页面，就将其作为用来替换的buffer。

（5）找到替换的“buffer id”之后，按照分区号从小到大的顺序，对两个“buffer tag”对应的分区同时加上排他锁，插入新“buffer tag”对应的元素，删除原来“buffer tag”对应的元素。然后再按照分区号从小到大的顺序释放上述两个分区排他锁。

（6）最后确认对应的磁盘页面是否已经加载上来。如果是，则直接返回上述被替换的“buffer id + 1”；如果不是，则尝试加载到该“buffer id”对应的buffer内存中，然后返回“buffer id + 1”。

行存储共享缓冲区访问的主要接口和含义如表1所示。

（六）cstore

1. cstore整体框架

2. cstore存储单元结构

（1） CU的CRC值，为CU结构中除CRC成员之外，其他所有字节计算出的32位CRC值。

（2） CU的magic值，为插入CU的事务号。

（3） CU的属性值，为16位标志值，包括CU是否包含NULL行、CU使用的压缩算法等CU粒度属性信息。

（4） 压缩后NULL值位图长度，如果属性值中标识该CU包含NULL行，则本CU在实际数据内容开始处包含NULL值位图，此处储存该位图的字节长度，如果该CU不包含NULL行，则无该成员。

（5） 压缩前数据长度，即CU数据内容在压缩前的字节长度，用于读取CU时进行内存申请和校验。

（6） 压缩后数据长度，即CU数据内容在压缩后的字节长度，用于插入CU时进行内存申请和校验。

（7） 压缩后NULL值位图内容，如果属性值中标识该CU包含NULL行，则该成员即为每行的NULL值位图，否则无该成员。

（8） 压缩后数据内容，即实际写入磁盘的CU主体数据内容。

每个CU最多保存对应字段的MAX_BATCH_ROWS行（默认60000行）数据。相邻CU之间按8KB对齐。

3. cstore多版本机制

（1）CU间的可见性：每个CU对应CUDESC表（astore行存储表）中的一行记录（一对一），该CU的可见性完全取决于该行记录的可见性。

（2）同一个CU内不同行的可见性：每个CU的内部可见性对应CUDESC表中的一行（多对一），该行的bitmap字段为最长MAX_BATCH_ROWS个bit的删除位图（bit 1表示删除，bit 0表示未删除），通过该位图记录的可见性和多版本，来支持CU内不同行的可见性。同时由于DML操作都是行粒度操作的，因此对于行号范围相同的、不同字段的多个CU均对应同一行位图记录。

（3）CU文件读写并发控制：CU文件自身为APPEND-ONLY，只在追加时对文件大小扩展进行加锁互斥，无须其他并发控制机制。

（4）同一个字段的不同CU，对应严格单调递增的cu_id编号，存储在对应的CUDESC表记录中，该cu_id的获取也通过上述文件扩展锁来进行并发控制。

（5）对于cstore表的单条插入以及更新操作，同时也提供与每个cstore表对应的delta表（astore行存储表），来接受这些新插入的或更新后的元组，以降低CU文件的碎片化。

表3 CUDESC表的结构

|图5 cstore表并发插入示意图|

1） 并发插入操作：

2） 并发插入和查询操作：

4. cstore访存接口和索引机制

cstore访存接口如表4所示，主要包括扫描、插入、删除和查询操作。

|图7 cstore表查询流程示意图|

cstore表插入执行流程，可以参考图8所示。其中灰色部分内的具体流程可以参考图5、图6中所示。当满足以下3个条件时，可以支持delta表插入：

（1） 打开enable_delta_store GUC参数。

（2） 该批向量数组为本次导入的最后一批向量数组。

（3） 该批向量数组的行数小于delta表插入的阈值。

|图8 cstore表插入流程示意图|

cstore表的删除流程主要分为两步。

（1） 如果存在delta表，那么先从delta表中删除满足谓词条件的记录。

（2） 在CUDESC表中更新待删除行所在CU的删除位图记录。

openGauss的cstore表支持psort和cbtree两种索引。

psort索引是一种局部排序聚簇索引。psort索引表的组织形式也是cstore表，该cstore表的字段包括索引键中的各个字段，再加上对应的行号（TID）字段。如图9所示，将一定数量的记录按索引键经过排序聚簇之后，与TID字段共同拼装成向量数组之后，插入psort索引cstore表中，插入流程和上面cstore表插入流程相同。

|图9 psort索引插入原理图|

查询时如果使用psort索引扫描，会首先扫描psort索引cstore表（扫描方式和上面cstore表扫描流程相同）。在一个psort索引CU的内部，由于做了局部聚簇索引，因此可以使用基于索引键的二分查找方式，快速找到符合索引条件的记录在该psort索引中的行号，该行的TID字段值即为该条记录在cstore主表中的行号。上述流程如图10所示。值得一提的是由于做了局部聚簇索引，因此在索引cstore表扫描过程中，在真正加载索引表CU文件之前，可以通过CUDESC中的min max做到非常高效的初筛过滤。

|图10 psort索引查询原理图|

cstore表的cbtree索引和行存储表的B-Tree索引在结构和使用方式上几乎完全一致，相关原理可以参考行存储索引章节（“行存储索引机制”节），此处不再赘述。

openGauss cstore表索引对外提供的主要接口如表5所示。

考虑到cstore列存储格式主要面向只读查询居多的OLAP类业务，因此openGauss提供只读的共享CU缓冲区机制。

openGauss中CU只读共享缓冲区的结构如图11所示。和行存储页面粒度的共享缓冲区类似，最上层为共享哈希表，哈希表键值为CU的slot类型、relfilenode、colid、cuid、cupointer构成的五元组，哈希表的记录值为该CU对应的缓冲区槽位slot id（对应行存储共享缓区的buffer id）。在全局CacheDesc数组中，用CacheDesc结构体记录与slot id对应的缓存槽位的状态信息（对应行存储缓冲区的BufferDesc结构体）。在共享CU数组中，用CU结构体记录与slot id对应的缓存CU的结构体信息。

与行存储固定的页面大小不同，不同CU的大小可能是不同的（行存储页面大小都是8 K），因此上述CU槽位只记录指向实际内存中CU数据的指针。另一方面为了保证共享内存大小可控，通过另外的全局变量来记录已经申请的有效槽位中所有CU的大小总和。

|图11 CU只读共享缓存结构示意图|

CU只读共享缓冲区的工作机制如图12所示。

（1） 当从磁盘读取一个CU放如Cache Mgr时，需要从FreeSlotList里拿到一个free slot（空闲槽位）存放CU，然后插入到哈希表中。

（2） 当FreeSlotList为NULL的时，需要根据LRU算法淘汰掉一个slot（槽位），释放CU data占的内存，减小CU总大小计数，并从hash table中删除，然后存放新的CU，再插入哈希表中。

（3） Cache内存大小可以配置。如果内存超过设置的Cache大小，需要淘汰掉适量的slot，并释放CU data占用的内存。

（4） 支持缓存压缩态的CU或解压态的CU两种模式，可以通过配置文件修改，同时只能存在一种模式。

|图12 CU只读共享缓存读取示意图|

与CU只读共享缓冲区相关的关键数据结构代码如下：

typedef struct CUSlotTag {
    RelFileNodeOld m_rnode;
    int m_colId;
    int32 m_CUId;
    uint32 m_padding;
    CUPointer m_cuPtr;
} CUSlotTag;
/* slot id哈希表键值主要部分，各个成员的含义从命名中可以清晰看出 */
 
typedef struct DataSlotTag {
    DataSlotTagKey slotTag;
    CacheType slotType;
} DataSlotTag;
/* slot id哈希表键值结构体，成员包括CUSlotTag与slot类型（CU、OBS外表等） */
 
typedef struct CacheLookupEnt {
    CacheTag cache_tag;
    CacheSlotId_t slot_id;
} CacheLookupEnt;
/* slot id哈希表记录结构体，成员包括哈希表键值和对应的slot id  */
 
typedef struct CacheDesc {
    uint16 m_usage_count;
    uint16 m_ring_count;
    uint32 m_refcount;
    CacheTag m_cache_tag;
    CacheSlotId_t m_slot_id;
    CacheSlotId_t m_freeNext;
    LWLock *m_iobusy_lock;
    LWLock *m_compress_lock;
    /*The data size in the one slot.*/
    int m_datablock_size;
    bool m_refreshing;
    slock_t m_slot_hdr_lock;
    CacheFlags m_flag;
} CacheDesc;
/* CU共享缓冲区槽位状态结构体，其中m_usage_count、m_ring_count为LRU淘汰算法需要的使用计数，m_refcount为判断能否淘汰的被引用计数，m_freeNext指向下一次空闲的slot槽位（如果本槽位在free list中的话，否则m_freeNext恒等于-2），m_iobusy_lock为I/O并发控制锁，m_compress_lock为压缩并发控制锁，m_datablock_size为CU实际数据的大小，m_slot_hdr_lock保护整个CacheDesc的并发读写操作，m_flag表示槽位状态（包括全新、有效、freelist中、空闲、I/O中、错误等状态）*/

表6 日志类型

openGauss日志文件、页面和日志记录的格式如图13所示。

|图13 日志文件、页面和记录格式示意图|

日志文件在逻辑意义上是一个最大长度为64位无符号整数的连续文件。在物理分布上，该逻辑文件按XLOG_SEG_SIZE大小（默认为16MB）切断，每段日志文件的命名规则为“时间线+日志id号+该id内段号”。“时间线”用于表示该日志文件属于数据库的哪个“生命历程”，在时间点恢复功能中使用。“日志id号”从0开始，按每4G大小递增加1。“id内段号”表示该16MB大小的段文件在该4G“日志id号”内是第几段，范围为0至255。上面3个值在日志段文件名中都以16进制方式显示。

每个日志段文件都可以用XLOG_BLCKSZ（默认8KB）为单位，划分为多个页面。每个8KB页面中，起始位置为页面头，如果该页是整个段文件的第一个页面，那么页面头为一个长页头（XLogLongPageHeader），否则为一个正常页头（短页头）（XLogPageHeader）。在页头之后跟着一条或多条日志记录。每个日志记录对应一个数据库的某种操作。为了降低日志记录的大小（日志写入磁盘时延是影响事务时延的主要因素之一），每条日志内部都是紧密排列的。各条日志之间按8字节（64位系统）对齐。一条日志记录可以跨两个及以上的日志页面，其最大长度限制为1G。对于跨页的日志记录，其后续日志页面页头的标志位XLP_FIRST_IS_CONTRECORD会被置上。

长、短页头结构体的定义如下，其中存储了用于校验的magic信息、页面标志位信息、时间线信息、页面（在整个逻辑日志文件中的）偏移信息、有效长度信息、系统识别号信息、段尺寸信息、页尺寸信息等。

短页头结构体的代码如下：

typedef struct XLogPageHeaderData {
    uint16 xlp_magic;        /* 日志magic校验信息 */
    uint16 xlp_info;         /* 标志位 */
    TimeLineID xlp_tli;      /* 该页面第一条日志的时间线 */
    XLogRecPtr xlp_pageaddr; /* 该页面起始位置的LSN */
    uint32 xlp_rem_len; /* 如果是跨页记录，该记录在该页面内的剩余长度 */
} XLogPageHeaderData;

长页头结构体的代码如下：

typedef struct XLogLongPageHeaderData {
    XLogPageHeaderData std; /* 短页头 */
    uint64 xlp_sysid;       /* 系统标识符，和pg_control文件中相同 */
    uint32 xlp_seg_size;    /* 单个日志文件的大小 */
    uint32 xlp_xlog_blcksz; /* 单个日志页面的大小 */
} XLogLongPageHeaderData;

（1）日志记录头，对应XLogRecord结构体，存储了记录长度、主备任期号、事务号、上一条日志记录起始偏移、标志位、所属的资源管理器、crc校验值等信息。

（2）1 - 33个相关页面的元信息，对应XLogRecordBlockHeader结构体，存储了页面下标（0 - 32）、页面对应的物理文件的后缀、标志位、页面数据长度等信息；如果该日志没有对应的页面信息，则无该部分。

（3）日志数据主体的元信息，对应（长/短）XLogRecordDataHeader结构体，记录了特殊的页面下标，用于和第二部分区分，以及主体数据的长度。

（4）1 - 33个相关页面的数据；如果该日志没有对应的页面信息，则无该部分。

（5）日志数据主体。

这5部分对应的结构体代码如下。如上所述，在记录日志内容时，每个部分之间是紧密挨着的，无补空字符。如果一个日志记录没有对应的相关页面信息，那么第2和第4部分将被跳过。

typedef struct XLogRecord {
    uint32 xl_tot_len; /* 记录总长度 */
    uint32 xl_term;
    TransactionId xl_xid; /* 事务号 */
    XLogRecPtr xl_prev;   /* 前一条记录的起始位置LSN */
    uint8 xl_info;        /* 标志位 */
    RmgrId xl_rmid;       /* 资源管理器编号 */
    int2  xl_bucket_id;
    pg_crc32c xl_crc; /* 该记录的CRC校验值 */
 
    /* 后面紧接XLogRecordBlockHeaders或XLogRecordDataHeader结构体 */
} XLogRecord;
 
typedef struct XLogRecordBlockHeader {
    uint8 id;           /* 页面下标（即该记录中包含的第几个页面信息） */
    uint8 fork_flags;   /* 页面属于哪个后缀文件，以及标志位 */
    uint16 data_length; /* 实际页面相关的数据长度（紧接该头部结构体） */
    /* 如果BKPBLOCK_HAS_IMAGE标志位为1，后面紧跟XLogRecordBlockImageHeader结构体以及页面内连续数据 */
    /* 如果BKPBLOCK_SAME_REL标志位没有设置，后面紧跟RelFileNode结构体 */
    /* 后面紧跟页面号 */
} XLogRecordBlockHeader;
 
typedef struct XLogRecordDataHeaderShort {
    uint8 id;          /* 特殊的XLR_BLOCK_ID_DATA_SHORT页面下标 */
    uint8 data_length; /* 短记录数据长度 */
} XLogRecordDataHeaderShort;
 
typedef struct XLogRecordDataHeaderLong {
    uint8 id; /* 特殊的XLR_BLOCK_ID_DATA_LONG页面下标 */
               /* 后面紧跟长记录长度，无对齐 */
} XLogRecordDataHeaderLong;

单条日志记录的操作接口主要分为插入（写）和读接口。其中，一个完整的日志插入操作一般包含以下几步接口，如表7所示。

|图14 并发日志写入流程示意图|

如图14所示，在openGauss中对该共享缓冲区的操作采用Numa-aware的同步机制，具体步骤如下。

（1） 业务线程在本地内存中将日志记录组装成图13中所示的、5部分组成的字节流。

（2） 找到本线程所绑定的Numa Node对应的日志插入锁组，并在该锁组中随机找一个槽位对应的锁。

（3） 检查该锁的组头线程号。如果没有说明本线程是第一个请求该锁的，那么这个锁上所有的写日志请求将由本线程来执行，将锁的组头线程号设置为本线程号；否则说明已经存在这批写日志请求的组头线程，记录下当前组头线程的线程号，并将自己加入到这批的插入组队列中，等待组头线程完成日志插入。

（4） 对于组头线程，获取该日志插入锁的排他锁。

（5） 为该组所有的插入线程在逻辑日志文件中占位，即对当前该文件的插入偏移进行原子CAS（compare and swap，比较后交换）操作。

（6） 将该组所有后台线程本地内存中的日志依次拷贝到日志共享缓冲区的对应页面中。每当需要拷贝到下一个共享内存页面时，需要判断下一个页面对应的逻辑页面号是否和插入者的预期页面号一致（因为共享内存有限，因此同一个共享内存页面对应取模相同的逻辑页面）。首先，将自己预期的逻辑页面号，写入当前持有的日志插入锁的槽位中，然后进行上述判断。如果不一致，并且日志写入磁盘偏移比该共享内存页当前逻辑页面号还要小，那么需要将该页面写入磁盘以便复用。为了防止可能还有并发业务线程在拷贝日志数据到老逻辑页面号上，因此需要阻塞遍历每个日志插入锁，直到日志插入锁被释放，或者被持有的插入锁的逻辑页面号大于目标共享内存页面中现有的逻辑页面号。经过上述检查之后，就可以保证没有并发的业务还在对该共享内存页面进行拷贝写入操作，可以将其内容写入磁盘，并更新其对应的逻辑页面号到目标逻辑页面号。

（7） 重复上一步操作，直到把该组所有后台线程待插入的日志记录拷贝完。

（8） 释放日志插入锁。

（9） 唤醒本组所有后台线程。

由于内容较多，关于磁盘引擎方面的其他内容将在下篇图文中进行分享，敬请期待！

END

Gauss松鼠会

汇集数据库从业人员及爱好者

互助解决问题 共建数据库技术交流圈