怎么理解PostgreSQL中Clock Sweep算法

本篇内容介绍了“怎么理解postgresql中Clock Sweep算法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一、数据结构

BufferDesc
共享缓冲区的共享描述符(状态)数据

//buffer header锁定
#define BM_LOCKED               (1U << 22)  
//数据需要写入(标记为DIRTY)
#define BM_DIRTY                (1U << 23)  
//数据是有效的
#define BM_VALID                (1U << 24)  
//已分配buffer tag
#define BM_TAG_VALID            (1U << 25)  
//正在R/W
#define BM_io_IN_PROGRESS       (1U << 26)  
//上一个I/O出现错误
#define BM_IO_ERROR             (1U << 27)  
//开始写则变DIRTY
#define BM_JUST_DIRTIED         (1U << 28)  
//存在等待sole pin的其他进程
#define BM_PIN_COUNT_WaiTER     (1U << 29)  
//checkpoint发生,必须刷到磁盘上
#define BM_CHECKPOINT_NEEDED    (1U << 30)  
//持久化buffer(不是unlogged或者初始化fork)
#define BM_PERMANENT            (1U << 31)  

typedef struct BufferDesc
{
    //buffer tag
    BufferTag   tag;            
    //buffer索引编号(0开始),指向相应的buffer pool slot
    int         buf_id;         
    
    //tag状态,包括flags/refcount和usagecount
    pg_atomic_uint32 state;
    //pin-count等待进程ID
    int         wait_backend_pid;   
    //空闲链表链中下一个空闲的buffer
    int         freeNext;       
    //缓冲区内容锁
    LWLock      content_lock;   
} BufferDesc;

BufferTag
Buffer tag标记了buffer存储的是磁盘中哪个block

typedef struct buftag
{
    //物理relation标识符
    RelFilenode rnode;          
    ForkNumber  forkNum;
    //相对于relation起始的块号
    BlockNumber blockNum;       
} BufferTag;

二、源码解读

算法思想,在 Buffer Manager 中已有详细介绍,摘录如下:

WHILE true
(1)     Obtain the candidate buffer descriptor pointed by the nextVictimBuffer
(2)     IF the candidate descriptor is unpinned THEN
(3)        IF the candidate descriptor's usage_count == 0 THEN
                BREAK WHILE LOOP  
           ELSE
            Decrease the candidate descriptpor's usage_count by 1
               END IF
         END IF
(4)     Advance nextVictimBuffer to the next one
      END WHILE 
(5) RETURN buffer_id of the victim

算法思想朴素且简单,比起高大上的LRU算法要简单多了.
nextVictimBuffer可视为时钟的时针,把缓冲区视为环形缓冲区,时针循环周而往复的循环,如缓冲区满足unpinned(ref_count == 0) && usage_count == 0的条件,则选中该缓冲,否则,usage_count减一,继续循环,直至找到满足条件的buffer为止.选中的buffer一定是buffers中较少使用的那个.

StrategyGetBuffer中的代码片段:

...
    
    //空闲链表中找不到或者满足不了条件,则执行"clock sweep"算法
    //int NBuffers = 1000;
    trycounter = NBuffers;//尝试次数
    for (;;)
    {
        //------- 循环
        //获取buffer描述符
        buf = GetBufferDescriptor(ClockSweepTick());
        
        local_buf_state = LockBufHdr(buf);
        if (BUF_STATE_GET_REFCOUNT(local_buf_state) == 0)
        {
            //----- refcount == 0
            if (BUF_STATE_GET_USAGECOUNT(local_buf_state) != 0)
            {
                //usage_count <> 0
                //usage_count - 1
                local_buf_state -= BUF_USAGECOUNT_ONE;
                //重置尝试次数
                trycounter = NBuffers;
            }
            else
            {
                //usage_count = 0
                
                //发现一个可用的buffer
                if (strategy != NULL)
                    //添加到该策略的环形缓冲区中
                    AddBufferToRing(strategy, buf);
                //输出参数赋值
                *buf_state = local_buf_state;
                //返回buf
                return buf;
            }
        }
        else if (--trycounter == 0)
        {
            //----- refcount <> 0 && --trycounter == 0
            
            UnlockBufHdr(buf, local_buf_state);
            elog(ERROR, "no unpinned buffers available");
        }
        //解锁buffer header
        UnlockBufHdr(buf, local_buf_state);
    }

ClockSweepTick()函数是StrategyGetBuffer()的辅助过程,移动时针(当前位置往前一格),返回时针指向的buffer.
其实现逻辑如下:

static inline uint32
ClockSweepTick(void)
{
    uint32      victim;
    
    victim =
        pg_atomic_fetch_add_u32(&StrategyControl->nextVictimBuffer, 1);
    if (victim >= NBuffers)
    {
        //-------- 候选buffer大于NBuffers
        //记录元素的victim
        uint32      originalVictim = victim;
        
        //回卷BufferDescriptors中查找的内容
        victim = victim % NBuffers;
        
        if (victim == 0)
        {
            //出现回卷
            uint32      expected;//期望值(不考虑回卷)
            uint32      wrapped;//回卷后的值
            bool        success = false;//成功标记
            //期望值
            expected = originalVictim + 1;
            while (!success)
            {
                
                SpinLockAcquire(&StrategyControl->buffer_strategy_lock);
                //获取回卷数
                wrapped = expected % NBuffers;
                //原子比较并交换数字
                success = pg_atomic_compare_exchange_u32(&StrategyControl->nextVictimBuffer,
                                                         &expected, wrapped);
                if (success)
                    //如成功,则增加计数
                    StrategyControl->completePasses++;
                //释放自旋锁
                SpinLockRelease(&StrategyControl->buffer_strategy_lock);
            }
        }
    }
    //返回victim
    return victim;
}

static inline bool
pg_atomic_compare_exchange_u32(volatile pg_atomic_uint32 *ptr,
                               uint32 *expected, uint32 newval)
{
    AssertPointerAlignment(ptr, 4);
    AssertPointerAlignment(expected, 4);
    return pg_atomic_compare_exchange_u32_impl(ptr, expected, newval);
}
bool
pg_atomic_compare_exchange_u32_impl(volatile pg_atomic_uint32 *ptr,
                                    uint32 *expected, uint32 newval)
{
    bool        ret;
    
    SpinLockAcquire((slock_t *) &ptr->sema);
    
    //执行比较/交换逻辑
    ret = ptr->value == *expected;//ptr与*expected是否一致?
    *expected = ptr->value;/
    //释放自旋锁
    SpinLockRelease((slock_t *) &ptr->sema);
    //返回结果
    return ret;
}

“怎么理解Postgresql中Clock Sweep算法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！