本节简单介绍了PostgreSQL缓存管理(Buffer Manager)中的Clock Sweep算法,其主要逻辑在StrategyGetBuffer函数中实现。 ### 一、数据结构 **BufferDesc** 共享缓冲区的共享描述符(状态)数据 ``` /* * Flags for buffer descriptors * buffer描述器标记 * * Note: TAG_VALID essentially means that there is a buffer hashtable * entry associated with the buffer's tag. * 注意:TAG_VALID本质上意味着有一个与缓冲区的标记相关联的缓冲区散列表条目。 */ //buffer header锁定 #define BM_LOCKED (1U << 22) /* buffer header is locked */ //数据需要写入(标记为DIRTY) #define BM_DIRTY (1U << 23) /* data needs writing */ //数据是有效的 #define BM_VALID (1U << 24) /* data is valid */ //已分配buffer tag #define BM_TAG_VALID (1U << 25) /* tag is assigned */ //正在R/W #define BM_IO_IN_PROGRESS (1U << 26) /* read or write in progress */ //上一个I/O出现错误 #define BM_IO_ERROR (1U << 27) /* previous I/O failed */ //开始写则变DIRTY #define BM_JUST_DIRTIED (1U << 28) /* dirtied since write started */ //存在等待sole pin的其他进程 #define BM_PIN_COUNT_WAITER (1U << 29) /* have waiter for sole pin */ //checkpoint发生,必须刷到磁盘上 #define BM_CHECKPOINT_NEEDED (1U << 30) /* must write for checkpoint */ //持久化buffer(不是unlogged或者初始化fork) #define BM_PERMANENT (1U << 31) /* permanent buffer (not unlogged, * or init fork) */ /* * BufferDesc -- shared descriptor/state data for a single shared buffer. * BufferDesc -- 共享缓冲区的共享描述符(状态)数据 * * Note: Buffer header lock (BM_LOCKED flag) must be held to examine or change * the tag, state or wait_backend_pid fields. In general, buffer header lock * is a spinlock which is combined with flags, refcount and usagecount into * single atomic variable. This layout allow us to do some operations in a * single atomic operation, without actually acquiring and releasing spinlock; * for instance, increase or decrease refcount. buf_id field never changes * after initialization, so does not need locking. freeNext is protected by * the buffer_strategy_lock not buffer header lock. The LWLock can take care * of itself. The buffer header lock is *not* used to control access to the * data in the buffer! * 注意:必须持有Buffer header锁(BM_LOCKED标记)才能检查或修改tag/state/wait_backend_pid字段. * 通常来说,buffer header lock是spinlock,它与标记位/参考计数/使用计数组合到单个原子变量中. * 这个布局设计允许我们执行原子操作,而不需要实际获得或者释放spinlock(比如,增加或者减少参考计数). * buf_id字段在初始化后不会出现变化,因此不需要锁定. * freeNext通过buffer_strategy_lock锁而不是buffer header lock保护. * LWLock可以很好的处理自己的状态. * 务请注意的是:buffer header lock不用于控制buffer中的数据访问! * * It's assumed that nobody changes the state field while buffer header lock * is held. Thus buffer header lock holder can do complex updates of the * state variable in single write, simultaneously with lock release (cleaning * BM_LOCKED flag). On the other hand, updating of state without holding * buffer header lock is restricted to CAS, which insure that BM_LOCKED flag * is not set. Atomic increment/decrement, OR/AND etc. are not allowed. * 假定在持有buffer header lock的情况下,没有人改变状态字段. * 持有buffer header lock的进程可以执行在单个写操作中执行复杂的状态变量更新, * 同步的释放锁(清除BM_LOCKED标记). * 换句话说,如果没有持有buffer header lock的状态更新,会受限于CAS, * 这种情况下确保BM_LOCKED没有被设置. * 比如原子的增加/减少(AND/OR)等操作是不允许的. * * An exception is that if we have the buffer pinned, its tag can't change * underneath us, so we can examine the tag without locking the buffer header. * Also, in places we do one-time reads of the flags without bothering to * lock the buffer header; this is generally for situations where we don't * expect the flag bit being tested to be changing. * 一种例外情况是如果我们已有buffer pinned,该buffer的tag不能改变(在本进程之下), * 因此不需要锁定buffer header就可以检查tag了. * 同时,在执行一次性的flags读取时不需要锁定buffer header. * 这种情况通常用于我们不希望正在测试的flag bit将被改变. * * We can't physically remove items from a disk page if another backend has * the buffer pinned. Hence, a backend may need to wait for all other pins * to go away. This is signaled by storing its own PID into * wait_backend_pid and setting flag bit BM_PIN_COUNT_WAITER. At present, * there can be only one such waiter per buffer. * 如果其他进程有buffer pinned,那么进程不能物理的从磁盘页面中删除items. * 因此,后台进程需要等待其他pins清除.这可以通过存储它自己的PID到wait_backend_pid中, * 并设置标记位BM_PIN_COUNT_WAITER. * 目前,每个缓冲区只能由一个等待进程. * * We use this same struct for local buffer headers, but the locks are not * used and not all of the flag bits are useful either. To avoid unnecessary * overhead, manipulations of the state field should be done without actual * atomic operations (i.e. only pg_atomic_read_u32() and * pg_atomic_unlocked_write_u32()). * 本地缓冲头部使用同样的结构,但并不需要使用locks,而且并不是所有的标记位都使用. * 为了避免不必要的负载,状态域的维护不需要实际的原子操作 * (比如只有pg_atomic_read_u32() and pg_atomic_unlocked_write_u32()) * * Be careful to avoid increasing the size of the struct when adding or * reordering members. Keeping it below 64 bytes (the most common CPU * cache line size) is fairly important for performance. * 在增加或者记录成员变量时,小心避免增加结构体的大小. * 保持结构体大小在64字节内(通常的CPU缓存线大小)对于性能是非常重要的. */ typedef struct BufferDesc { //buffer tag BufferTag tag; /* ID of page contained in buffer */ //buffer索引编号(0开始),指向相应的buffer pool slot int buf_id; /* buffer's index number (from 0) */ /* state of the tag, containing flags, refcount and usagecount */ //tag状态,包括flags/refcount和usagecount pg_atomic_uint32 state; //pin-count等待进程ID int wait_backend_pid; /* backend PID of pin-count waiter */ //空闲链表链中下一个空闲的buffer int freeNext; /* link in freelist chain */ //缓冲区内容锁 LWLock content_lock; /* to lock access to buffer contents */ } BufferDesc; ``` **BufferTag** Buffer tag标记了buffer存储的是磁盘中哪个block ``` /* * Buffer tag identifies which disk block the buffer contains. * Buffer tag标记了buffer存储的是磁盘中哪个block * * Note: the BufferTag data must be sufficient to determine where to write the * block, without reference to pg_class or pg_tablespace entries. It's * possible that the backend flushing the buffer doesn't even believe the * relation is visible yet (its xact may have started before the xact that * created the rel). The storage manager must be able to cope anyway. * 注意:BufferTag必须足以确定如何写block而不需要参照pg_class或者pg_tablespace数据字典信息. * 有可能后台进程在刷新缓冲区的时候深圳不相信关系是可见的(事务可能在创建rel的事务之前). * 存储管理器必须可以处理这些事情. * * Note: if there's any pad bytes in the struct, INIT_BUFFERTAG will have * to be fixed to zero them, since this struct is used as a hash key. * 注意:如果在结构体中有填充的字节,INIT_BUFFERTAG必须将它们固定为零，因为这个结构体用作散列键. */ typedef struct buftag { //物理relation标识符 RelFileNode rnode; /* physical relation identifier */ ForkNumber forkNum; //相对于relation起始的块号 BlockNumber blockNum; /* blknum relative to begin of reln */ } BufferTag; ``` ### 二、源码解读 算法思想,在[Buffer Manager](http://www.interdb.jp/pg/pgsql08.html)中已有详细介绍,摘录如下: ``` 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 /* the corresponding slot of this descriptor is victim slot. */ 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中的代码片段: ``` ... /* Nothing on the freelist, so run the "clock sweep" algorithm */ //空闲链表中找不到或者满足不了条件,则执行"clock sweep"算法 //int NBuffers = 1000; trycounter = NBuffers;//尝试次数 for (;;) { //------- 循环 //获取buffer描述符 buf = GetBufferDescriptor(ClockSweepTick()); /* * If the buffer is pinned or has a nonzero usage_count, we cannot use * it; decrement the usage_count (unless pinned) and keep scanning. * 如果buffer已pinned,或者有一个非零值的usage_count,不能使用这个buffer. * 减少usage_count(除非已pinned)继续扫描. */ 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 /* Found a usable buffer */ //发现一个可用的buffer if (strategy != NULL) //添加到该策略的环形缓冲区中 AddBufferToRing(strategy, buf); //输出参数赋值 *buf_state = local_buf_state; //返回buf return buf; } } else if (--trycounter == 0) { //----- refcount <> 0 && --trycounter == 0 /* * We've scanned all the buffers without making any state changes, * so all the buffers are pinned (or were when we looked at them). * We could hope that someone will free one eventually, but it's * probably better to fail than to risk getting stuck in an * infinite loop. * 在没有改变任何状态的情况,我们已经完成了所有buffers的遍历, * 因此所有的buffers已pinned(或者在搜索的时候pinned). * 我们希望某些进程会周期性的释放buffer,但如果实在拿不到,那报错总比傻傻的死循环要好. */ UnlockBufHdr(buf, local_buf_state); elog(ERROR, "no unpinned buffers available"); } //解锁buffer header UnlockBufHdr(buf, local_buf_state); } ``` ClockSweepTick()函数是StrategyGetBuffer()的辅助过程,移动时针(当前位置往前一格),返回时针指向的buffer. 其实现逻辑如下: ``` /* * ClockSweepTick - Helper routine for StrategyGetBuffer() * ClockSweepTick - StrategyGetBuffer()的辅助过程 * * Move the clock hand one buffer ahead of its current position and return the * id of the buffer now under the hand. * 移动时针(当前位置往前一格),返回时针指向的buffer. */ static inline uint32 ClockSweepTick(void) { uint32 victim; /* * Atomically move hand ahead one buffer - if there's several processes * doing this, this can lead to buffers being returned slightly out of * apparent order. * 原子移动时针一格 * - 如果有多个进程执行这个操作,这可能会导致缓冲返回的顺序稍微有些混乱. * */ victim = pg_atomic_fetch_add_u32(&StrategyControl->nextVictimBuffer, 1); if (victim >= NBuffers) { //-------- 候选buffer大于NBuffers //记录元素的victim uint32 originalVictim = victim; /* always wrap what we look up in BufferDescriptors */ //回卷BufferDescriptors中查找的内容 victim = victim % NBuffers; /* * If we're the one that just caused a wraparound, force * completePasses to be incremented while holding the spinlock. We * need the spinlock so StrategySyncStart() can return a consistent * value consisting of nextVictimBuffer and completePasses. * 如果我们正好导致了wraparound,在持有自旋锁的情况下强制completePasses增加. * 之所以需要自旋锁是因为StrategySyncStart()才能返回nextVictimBuffer和completePasses的一致性值. */ if (victim == 0) { //出现回卷 uint32 expected;//期望值(不考虑回卷) uint32 wrapped;//回卷后的值 bool success = false;//成功标记 //期望值 expected = originalVictim + 1; while (!success) { /* * Acquire the spinlock while increasing completePasses. That * allows other readers to read nextVictimBuffer and * completePasses in a consistent manner which is required for * StrategySyncStart(). In theory delaying the increment * could lead to an overflow of nextVictimBuffers, but that's * highly unlikely and wouldn't be particularly harmful. * 在增加completePasses时请求获取自旋锁. * 这样可以让其他读取进程以一致性的方式读取nextVictimBuffer和completePasses, * 这种一致性的方式在StrategySyncStart()中是需要的. * 理论上来说,延迟增加可能会导致nextVictimBuffers溢出, * 但但这是非常不可能的，也不会特别有害。 */ 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; } /* * pg_atomic_compare_exchange_u32 - CAS operation *pg_atomic_compare_exchange_u32 - CAS操作 * * Atomically compare the current value of ptr with *expected and store newval * iff ptr and *expected have the same value. The current value of *ptr will * always be stored in *expected. * 原子比较ptr当前值与*expected,如果ptr和*expected值一致,则存储newval到ptr中. * *ptr的当前值通常会存储在*expected中. * * Return true if values have been exchanged, false otherwise. * 如值已交换,则返回T,否则返回F. * * Full barrier semantics. * 完整的屏障语义. */ 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; /* * Do atomic op under a spinlock. It might look like we could just skip * the cmpxchg if the lock isn't available, but that'd just emulate a * 'weak' compare and swap. I.e. one that allows spurious failures. Since * several algorithms rely on a strong variant and that is efficiently * implementable on most major architectures let's emulate it here as * well. * 在自旋锁保护下执行原子操作. * 这看起来如果锁不可能的话,我们可以跳过cmpxchg,但这只是模拟了一个"浅"比较和交换. * 比如,这会引起spurious failures. * 由于有几种算法依赖于一种强大的变体，而且这种变体可以在大多数主要架构上有效地实现， * 因此我们在这里也对其进行模拟。 */ SpinLockAcquire((slock_t *) &ptr->sema); /* perform compare/exchange logic */ //执行比较/交换逻辑 ret = ptr->value == *expected;//ptr与*expected是否一致? *expected = ptr->value;//*expected赋值为ptr if (ret) ptr->value = newval;//值一致,则ptr设置为新值 /* and release lock */ //释放自旋锁 SpinLockRelease((slock_t *) &ptr->sema); //返回结果 return ret; } ``` ### 三、跟踪分析 N/A ### 四、参考资料 [PG Source Code](https://doxygen.postgresql.org) [Buffer Manager](http://www.interdb.jp/pg/pgsql08.html)