openGauss内核求索——时钟替换算法及其应用

1.前言

1.1 基本概念

缓冲管理器：主要是管理共享内存和持久存储之间的数据传输，并可能对 DBMS 的性能产生重大影响。缓冲区管理器、持久存储和后端进程之间的关系如下图所示：

1.2 缓冲区管理器结构

缓冲区标签

数据库为所有数据文件的每个页面分配一个唯一的标记，即缓冲区标签。缓冲区标签由关系文件节点、关系分支编号和页面块号

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

缓冲区表

缓冲表层是一个散列表，它存储着页面的 buffer_tag 与描述符的 buffer_id 之间的映射关系。

t_thrd.storage_cxt.SharedBufHash = ShmemInitHash("Shared Buffer Lookup Table", size, size, &info,
                                                HASH_ELEM | HASH_FUNCTION | HASH_PARTITION);
uint32 BufTableHashCode(BufferTag *tagPtr)      

缓冲区描述符

保存着页面的元数据，对应的页面则保存在缓冲池的槽位中。

#define BufferGetBufferDescriptor(buffer)                          
   (AssertMacro(BufferIsValid(buffer)), BufferIsLocal(buffer) ?  
       (BufferDesc *)&u_sess->storage_cxt.LocalBufferDescriptors[(buffer)-1].bufferdesc :
       &t_thrd.storage_cxt.BufferDescriptors[(buffer)-1].bufferdesc)

缓冲池

缓冲池存储数据文件的页，如表的页面。缓冲池是一个数组，每个插槽存储数据文件的一页。缓冲池数组的索引称为buffer_id。

/* Note: these two macros only work on shared buffers, not local ones! */
#define BufHdrGetBlock(bufHdr)                                                          
       (IsNvmBufferID((bufHdr)->buf_id) ? ((Block)(t_thrd.storage_cxt.NvmBufferBlocks + ((Size)(uint32)(bufHdr)->buf_id - NvmBufferStartID) * BLCKSZ))
                             : IsSegmentBufferID((bufHdr)->buf_id) ? ((Block)(t_thrd.storage_cxt.BufferBlocks + ((Size)(uint32)(bufHdr)->buf_id - NVM_BUFFER_NUM) * BLCKSZ))
                                                        : ((Block)(t_thrd.storage_cxt.BufferBlocks + ((Size)(uint32)(bufHdr)->buf_id) * BLCKSZ)))
#define BufferGetLSN(bufHdr) (PageGetLSN(BufHdrGetBlock(bufHdr)))

相关函数

BufferDesc *BufferAlloc

1.3 buffer候选队列

buffer候选队列：即candidate_buffer，内核中与normal_list、candidate_free_map联合一起管理空闲buffer的使用。

candidate_buffer（候选buffer队列，全部可用（或在用）缓冲区槽位数组）：数据类型：数组 key: 0~(N-1) value：buf_id，长度等同于buffer缓冲池的槽位数 normal_list（空闲buffer队列）：数据类型：CandidateList类型链表， size: shared_buffers_num pagewriter_thread_num, value：buf_id candidate_free_map（候选队列中buffer空闲状态标记表）：数据类型：数组 key: buf_id value：true/false，长度等同于buffer缓冲池的槽位数 candidate_buffer候选队列和缓冲区、缓冲区描述的关系如下：

pagewriter线程会定期从candidate_buffers中筛选出空闲buffer放到normal_list中。数据库在调用BufferAlloc获取Buffer时，如果没有在已有的缓冲区buffer中找到页面，需要挑选已有buffer换入换出时，会优先从normal_list中选取受害者，如果normal_list为空，基于时钟替换算法从candidate_bufffers中选一个受害者。

2. 时钟替换算法

PG的时钟替换算法

该算法是NFU（Not Frequently Used）算法的变体，开销较少，能高效地选出较少使用的页面。我们将缓冲区描述符想象为一个循环列表，如下图所示，缓冲区描述符为黑色或灰色的方框，框中的数字显示每个描述符的 usage_count(该buffer的访问次数)。而 nextVictimBuffer是一个 32位的无符号整型变量，即时钟手，它总是指向某个缓冲区描述符并按顺时针顺序旋转。

当数据页调用StrategyGetBuffer方法尝试获取一个用于置换的页面时，如果候选队列normal list中找不到可以用来置换的空闲buffer，则会通过时钟替换算法选出一个受害者用于替换。

每次要通过时钟替换算法选出受害者时，时钟手会在不停在所有缓冲区描述符中轮转，如果一个选中描述符的usage_count = 0，则选中该buffer为受害者，否则usage_count--。

WHILE true
 (1)      获取nextVictimBuffer指向的缓冲区描述符
 (2)      IF 缓冲区描述符没有被钉住 THEN
 (3)           IF 候选缓冲区描述符的 usage_count == 0 THEN
                 BREAK WHILE LOOP  /* 该描述符对应的槽就是受害者槽 */
               ELSE
                   将候选描述符的 usage_count - 1
               END IF
           END IF
 (4)      迭代 nextVictimBuffer，指向下一个缓冲区描述符
END WHILE
 (5) RETURN 受害者页面的 buffer_id

openGauss的时钟替换算法

openGauss的时钟与上述流程相近，但是没有使用usage_count作为筛选受害者的标准。而是选择 refcount = 0 && 非元数据 && （非脏页 ||开启double write ）的页面作为受害者，BufferAlloc会尝试将该页面换出用于新页面换入。

StrateyGetBuffer
 get_buf_from_candidate_list 从空闲队列中获取buffer


 if 候选队列中没有空闲buffer
retry:
   try_counter = NORMAL_SHARED_BUFFER_NUM
   while try_counter--
     buf = ClockSweepTick // 时钟手移动一次
     if  refcount = 0 && 非元数据 && （非脏页 ||开启double write)
       return buf // 返回受害者
     else
       continue
     end
   end
   if (shared_buffers_fraction < 1.0 || 开启双写 || 正在进行btree分裂)
     goto retry
   else
     return NULL // 找不到可用受害者
 end

相关流程 ReadBuffer_Common->BufferAlloc->StrategyGetBuffer->ClockSweepTick

相关变量：

（1）nextVictimBuffer，unint32，受害者buffer的id，取值范围0~max_nbuffer_can_use。

t_thrd.storage_cxt.StrategyControl->nextVictimBuffer

（2）备节点生效，备节点不会直接使用所有的shared buffer，而是先使用一部分，如果不够用再慢慢扩张，取值范围0~1.0

u_sess->attr.attr_storage.shared_buffers_fraction

3. 时钟替换算法的应用

时钟替换算法的应用——BufferAlloc时将页面从存储加载到受害者的缓冲池槽位

这种情况下，假设所有缓冲池槽位都被页面占用，且未存储所需的页面。下面两个图是将页面从存储加载到受害者缓冲池槽的示意图。

缓冲区管理器将执行以下步骤：

（1）创建所需页面的 buffer_tag 并查找缓冲表。在本例中假设 buffer_tag 是 ‘Tag_M’ （且相应的页面在缓冲区中找不到）。

（2）使用时钟扫描算法选择一个受害者缓冲池槽位（StrategyGetBuffer—>ClockSweepTick）。从缓冲表中获取包含着受害者槽位 buffer_id 的旧表项，并在缓冲区描述符层将受害者槽位的缓冲区描述符钉住。本例中受害者槽的 buffer_id=5，旧表项为 Tag_F, id = 5。

（3）如果受害者页面是脏页，则将其刷盘（write & fsync），否则进入步骤（4）。

在使用新数据覆盖脏页之前，必须将脏页写入存储中。脏页的刷盘步骤如下：

1. 获取 buffer_id=5 描述符上的共享 content_lock 和独占 io_in_progress_lock。
2. 更改相应描述符的状态：相应 IO_IN_PROCESS 位设置为"1"，JUST_DIRTIED 位设置为"0"。
3. 根据具体情况，调用 XLogFlush() 函数将WAL缓冲区上的WAL数据写入当前WAL段文件（WAL和XLogFlush函数将在第9章中介绍）。
4. 将受害者页面的数据刷盘至存储中。
5. 更改相应描述符的状态；将 IO_IN_PROCESS 位设置为"0"，将 VALID 位设置为"1"。
6. 释放 io_in_progress_lock和 content_lock。

（4）以排他模式获取缓冲区表中旧表项所在分区上的 BufMappingLock。

（5）获取新表项和旧表项（如果就表项的buftag还有效）所在分区上的 BufMappingLock，并将新表项插入缓冲表：

• 创建新表项：由 buffer_tag='Tag_M’与受害者的 buffer_id组成的新表项。

• 以独占模式获取新表项所在分区上的 BufMappingLock。

• 将新表项插入缓冲区表中。

（6）从缓冲表中删除旧表项，并释放旧表项所在分区的 BufMappingLock。

（7）将目标页面数据从存储加载至受害者槽位，然后用 buffer_id=5 更新描述符的标识字段，将脏位设置为0，并按流程初始化其他标记位。

（8）释放新表项所在分区上的 BufMappingLock。

（9）访问 buffer_id=5 对应的缓冲区槽位。

相关的锁

buffer_strategy_lock：BufferStrategyControl->buffer_strategy_lock字段

自旋锁， buffer_strategy_lock 为访问缓存区空闲列表或选择缓存区进行替换的操作提供互斥。为了提高效率，这里使用自旋锁而不是轻量级锁；在保留 buffer_strategy_lock 时，不应获取其他任何类型的锁。这对于允许在多个后端以合理的并发度进行缓存区替换至关重要。

保护范围：

BufferDesc结构体中的freeNext字段；

BufferStrategyControl结构体中的nextVictimBuffer、firstFreeBuffer、lastFreeBuffer。

操作方式：参考StrategyGetBuffer函数。

相关参数

standby_shared_buffers_fraction

参数说明：备实例所在服务器使用shared_buffers内存缓冲区大小的比例。

该参数属于SIGHUP类型参数，请参考表1中对应设置方法进行设置。

取值范围：双精度浮点型，0.1~1.0

默认值：0.3

4.相关函数

local_candidate_stat(）

显示本实例的bgwriter线程刷页信息，候选buffer链中页面个数，buffer淘汰信息。

• candidate_slots: 获取当前各候选队列（normal list）中总共有多少个buffer。

• get_buffer_from_list：通过候选队列 （normal list）获取了多少个buffer

• get_buf_clock_sweep: 通过时钟替换算法获取了多少个buffer

const incre_ckpt_view_col g_pagewirter_view_two_col[CANDIDATE_VIEW_COL_NUM] = {
   {"node_name", TEXTOID, ckpt_view_get_node_name},
   {"candidate_slots", INT4OID, ckpt_view_get_candidate_nums},
   {"get_buf_from_list", INT8OID, ckpt_view_get_num_candidate_list},
   {"get_buf_clock_sweep", INT8OID, ckpt_view_get_num_clock_sweep},
   {"seg_candidate_slots", INT4OID, ckpt_view_get_seg_candidate_nums},
   {"seg_get_buf_from_list", INT8OID, ckpt_view_seg_get_num_candidate_list},
   {"seg_get_buf_clock_sweep", INT8OID, ckpt_view_seg_get_num_clock_sweep}
};

local_bgwriter_stat(）

显示本实例的候选buffer链中页面个数，buffer淘汰信息等

• bgwr_actual_flush_total_num: bgwriter线程刷页数量，实际写死为0。

• bgwr_last_flush_num: 同写死为0。

• candidate_slots: 获取当前各候选队列（normal list + nvm list + seg list）中总共有多少个buffer。

• get_buffer_from_list：通过候选队列 （normal list）获取了多少个buffer。

• get_buf_clock_sweep: 通过时钟替换算法获取了多少个buffer。

const incre_ckpt_view_col g_bgwriter_view_col[INCRE_CKPT_BGWRITER_VIEW_COL_NUM] = {
   {"node_name", TEXTOID, bgwriter_view_get_node_name},
   {"bgwr_actual_flush_total_num", INT8OID, bgwriter_view_get_actual_flush_num},
   {"bgwr_last_flush_num", INT4OID, bgwriter_view_get_last_flush_num},
   {"candidate_slots", INT4OID, bgwriter_view_get_candidate_nums},
   {"get_buffer_from_list", INT8OID, bgwriter_view_get_num_candidate_list},
   {"get_buf_clock_sweep", INT8OID, bgwriter_view_get_num_clock_sweep}};

5.引申内容

BufferAccessStrategyData

功能：这段代码定义了一个缓冲区访问策略的数据结构，用于管理一个环形的共享缓冲区，以便重复使用。

目的：该数据结构的目的是提供一种策略，用于管理和重用一组共享缓冲区，以优化内存使用和提高性能。

使用场景：这种数据结构通常在需要频繁读写缓冲区的应用中使用，例如网络通信、数据处理等场景。

主要逻辑：

1. 定义了一个名为BufferAccessStrategyData的结构体，包含了缓冲区访问策略的相关信息。

2. btype字段表示整体的策略类型。

3. ring_size字段表示buffers数组的元素数量，即环形缓冲区的大小。

4. current字段表示环形缓冲区中最近被返回的"当前"槽的索引。

5. flush_rate字段表示在current后面需要刷新的元素数量。

6. current_was_in_ring字段表示最后一次由StrategyGetBuffer返回的缓冲区是否已经在环形缓冲区中。

7. buffers数组是一个动态大小的数组，用于存储缓冲区的编号。InvalidBuffer（即零）表示此环形插槽尚未选择缓冲区。为了简化分配，此数组与结构的固定字段一起palloc。

/* Possible arguments for GetAccessStrategy() */
typedef enum BufferAccessStrategyType {
   BAS_NORMAL,    /* Normal random access */
   BAS_BULKREAD,  /* Large read-only scan (hint bit updates are
                   * ok) */
   BAS_BULKWRITE, /* Large multi-block write (e.g. COPY IN) */
   BAS_VACUUM,     /* VACUUM */
   BAS_REPAIR      /* repair file */
} BufferAccessStrategyType;

/*
* Private (non-shared) state for managing a ring of shared buffers to re-use.
* This is currently the only kind of BufferAccessStrategy object, but someday
* we might have more kinds.
*/
typedef struct BufferAccessStrategyData {
   /* Overall strategy type */
   BufferAccessStrategyType btype;
   /* Number of elements in buffers[] array */
   int ring_size;


   /*
    * Index of the "current" slot in the ring, ie, the one most recently
    * returned by GetBufferFromRing.
    */
   int current;


   /* Number of elements to flush behind current */
   int flush_rate;


   /*
    * True if the buffer just returned by StrategyGetBuffer had been in the
    * ring already.
    */
   bool current_was_in_ring;


   /*
    * Array of buffer numbers.  InvalidBuffer (that is, zero) indicates we
    * have not yet selected a buffer for this ring slot.  For allocation
    * simplicity this is palloc'd together with the fixed fields of the
    * struct.
    */
   Buffer buffers[FLEXIBLE_ARRAY_MEMBER]; /* VARIABLE SIZE ARRAY */
} BufferAccessStrategyData;

参考文献

https://bbs.huaweicloud.com/blogs/308902

https://blog.csdn.net/cpongo1/article/details/89533991

◆ 相关阅读◆

openGauss内核求索——缓冲区管理器