TL;DR

PostgreSQL 使用 Clock-sweep（时钟扫描）算法管理 shared_buffers 中的页面替换，而非经典的 LRU。这篇文章带你逐行走读 src/backend/storage/buffer/bufmgr.c 中的核心实现。

为什么不用 LRU？

LRU 需要维护一个全局有序链表，在并发环境下锁争用严重。PostgreSQL 采用 Clock-sweep：一个环形缓冲区 + 一个时钟指针，每次扫描时递减 usage_count，找到第一个 usage_count == 0 的页面即被替换。

核心数据结构

// src/include/storage/buf_internals.h

typedef struct BufferDesc {
    BufferTag   tag;           // 页面标识
    pg_atomic_uint32 state;    // 状态位
    int         buf_id;        // 缓冲区索引
    int         freeNext;      // 空闲列表指针
    LWLock      content_lock;  // 内容锁
} BufferDesc;

usage_count 被编码在 state 原子变量中，每个页面最大引用计数为 5（BM_MAX_USAGE_COUNT）。

Clock-sweep 执行流程

// src/backend/storage/buffer/bufmgr.c

static BufferDesc *
StrategyGetBuffer(BufferAccessStrategy strategy, uint32 *buf_state) {
    for (;;) {
        // 1. 推进时钟指针
        StrategyControl->nextVictimBuffer++;
        if (StrategyControl->nextVictimBuffer >= NBuffers)
            StrategyControl->nextVictimBuffer = 0;

        buf = GetBufferDescriptor(StrategyControl->nextVictimBuffer);

        // 2. 递减 usage_count
        local_buf_state = LockBufHdr(buf);
        usage_count = BUF_STATE_GET_USAGECOUNT(local_buf_state);

        if (usage_count > 0) {
            local_buf_state -= BUF_USAGECOUNT_ONE;  // usage_count--
            // 继续扫描
        } else {
            // usage_count == 0 → 选定为 victim
            *buf_state = local_buf_state;
            return buf;
        }
    }
}

算法关键点

  1. 时钟指针绕圈：每圈扫描都会递减 usage_count，经过 BM_MAX_USAGE_COUNT 圈后 usage_count 必然归零
  2. NUMA 友好：没有全局有序结构，锁粒度在单个 buffer 级别
  3. pin 计数独立：被 pin 住的页面不会被替换，usage_count 递增在 pin 时发生

访问模式下的行为

场景：顺序扫描
         ↓（每页只访问一次）
usage_count: 1 → clock 经过 → 0 → 下一圈被淘汰 ✓

场景：热点页面（索引根节点）
         ↓（频繁访问）
usage_count: 1 → clock 经过 → 0 → 再被 pin → 1
         → 一直保持在缓存中 ✓

这与 LRU-K 的思想类似：只访问一次的数据很快被淘汰，频繁访问的数据持续保留。

总结

PostgreSQL 的 Clock-sweep 是 LRU 在并发环境下的工程优化，核心思想是“用环形扫描代替排序，用多圈递减代替精确排序”。此算法也广泛用于操作系统的页面替换中。

参考