缓冲池管理算法：LRU-K → 2Q → CLOCK-Pro

/* 朴素 LRU 核心操作 */
void lru_access(LRUCache *cache, page_id_t pid) {
    Node *node = hashtable_lookup(cache->ht, pid);
    if (node) {
        /* 命中：移到链表头部 */
        list_remove(node);
        list_push_front(&cache->list, node);
    } else {
        /* 未命中：可能需要淘汰 */
        if (cache->size >= cache->capacity) {
            Node *victim = list_pop_back(&cache->list);
            if (victim->dirty) flush_page(victim);
            hashtable_remove(cache->ht, victim->pid);
            free_node(victim);
            cache->size--;
        }
        node = alloc_node(pid);
        load_page_from_disk(node, pid);
        list_push_front(&cache->list, node);
        hashtable_insert(cache->ht, pid, node);
        cache->size++;
    }
}

SELECT COUNT(*) FROM orders;  -- 1000 万行，约 120 万页

/* lru_k.c -- LRU-K (K=2) buffer pool replacement */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>

#define HASH_SIZE      4096
#define HIST_HASH_SIZE 8192
#define CRP_WINDOW     5       /* correlated reference period */

typedef unsigned int page_id_t;
typedef unsigned long long timestamp_t;

/* --- history record for pages (including evicted) --- */
typedef struct HistEntry {
    page_id_t           pid;
    timestamp_t         last[2];   /* last[0]=most recent, last[1]=2nd recent */
    int                 count;     /* total independent accesses */
    struct HistEntry   *hash_next;
} HistEntry;

/* --- buffer pool page --- */
typedef struct BufPage {
    page_id_t           pid;
    bool                valid;
    bool                dirty;
    HistEntry          *hist;
    struct BufPage     *hash_next;
} BufPage;

/* --- LRU-K buffer pool manager --- */
typedef struct LRUKPool {
    int          capacity;
    int          used;
    timestamp_t  clock;

    BufPage     *pages;                   /* page array */
    BufPage     *page_ht[HASH_SIZE];      /* page hash table */

    HistEntry   *hist_ht[HIST_HASH_SIZE]; /* history hash table */
    int          hist_count;
    int          hist_max;                /* max retained history entries */
} LRUKPool;

/* --- hash helpers --- */
static unsigned int page_hash(page_id_t pid, int sz) {
    return (pid * 2654435761u) % (unsigned int)sz;
}

static HistEntry *hist_lookup(LRUKPool *pool, page_id_t pid) {
    unsigned int h = page_hash(pid, HIST_HASH_SIZE);
    for (HistEntry *e = pool->hist_ht[h]; e; e = e->hash_next)
        if (e->pid == pid) return e;
    return NULL;
}

static HistEntry *hist_get_or_create(LRUKPool *pool, page_id_t pid) {
    HistEntry *e = hist_lookup(pool, pid);
    if (e) return e;
    e = (HistEntry *)calloc(1, sizeof(HistEntry));
    e->pid = pid;
    unsigned int h = page_hash(pid, HIST_HASH_SIZE);
    e->hash_next = pool->hist_ht[h];
    pool->hist_ht[h] = e;
    pool->hist_count++;
    return e;
}

static void hist_record_access(HistEntry *e, timestamp_t now) {
    /* enforce correlated reference period */
    if (e->count > 0 && (now - e->last[0]) <= CRP_WINDOW)
        return;   /* within CRP, do not count as independent access */
    e->last[1] = e->last[0];
    e->last[0] = now;
    e->count++;
}

/* backward 2-distance: larger = colder */
static timestamp_t backward_k_dist(HistEntry *e, timestamp_t now) {
    if (!e || e->count < 2)
        return ULLONG_MAX;   /* fewer than K accesses */
    return now - e->last[1];
}

/* --- page hash table helpers --- */
static BufPage *page_lookup(LRUKPool *pool, page_id_t pid) {
    unsigned int h = page_hash(pid, HASH_SIZE);
    for (BufPage *p = pool->page_ht[h]; p; p = p->hash_next)
        if (p->valid && p->pid == pid) return p;
    return NULL;
}

static void page_ht_insert(LRUKPool *pool, BufPage *pg) {
    unsigned int h = page_hash(pg->pid, HASH_SIZE);
    pg->hash_next = pool->page_ht[h];
    pool->page_ht[h] = pg;
}

static void page_ht_remove(LRUKPool *pool, BufPage *pg) {
    unsigned int h = page_hash(pg->pid, HASH_SIZE);
    BufPage **pp = &pool->page_ht[h];
    while (*pp) {
        if (*pp == pg) { *pp = pg->hash_next; return; }
        pp = &(*pp)->hash_next;
    }
}

/* --- find victim using LRU-K policy --- */
static int find_victim(LRUKPool *pool) {
    int victim = -1;
    timestamp_t max_dist = 0;
    timestamp_t max_first = 0;

    for (int i = 0; i < pool->capacity; i++) {
        if (!pool->pages[i].valid) continue;
        HistEntry *e = pool->pages[i].hist;
        timestamp_t d = backward_k_dist(e, pool->clock);

        if (d == ULLONG_MAX) {
            /* fewer than K accesses: prefer the earliest first-access */
            timestamp_t first = e ? e->last[0] : 0;
            if (victim == -1 || max_dist != ULLONG_MAX ||
                first < max_first) {
                victim = i;
                max_dist = ULLONG_MAX;
                max_first = first;
            }
        } else if (max_dist != ULLONG_MAX && d > max_dist) {
            victim = i;
            max_dist = d;
        }
    }
    return victim;
}

/* --- public API --- */
LRUKPool *lruk_create(int capacity) {
    LRUKPool *pool = (LRUKPool *)calloc(1, sizeof(LRUKPool));
    pool->capacity = capacity;
    pool->pages = (BufPage *)calloc(capacity, sizeof(BufPage));
    pool->hist_max = capacity * 4;
    return pool;
}

/* returns true on hit, false on miss */
bool lruk_access(LRUKPool *pool, page_id_t pid) {
    pool->clock++;
    HistEntry *hist = hist_get_or_create(pool, pid);

    BufPage *pg = page_lookup(pool, pid);
    if (pg) {
        /* hit */
        hist_record_access(hist, pool->clock);
        return true;
    }

    /* miss: need a free slot or evict */
    int slot = -1;
    if (pool->used < pool->capacity) {
        for (int i = 0; i < pool->capacity; i++) {
            if (!pool->pages[i].valid) { slot = i; break; }
        }
    } else {
        slot = find_victim(pool);
        if (slot >= 0) {
            page_ht_remove(pool, &pool->pages[slot]);
            pool->pages[slot].valid = false;
            pool->used--;
        }
    }

    if (slot < 0) return false; /* should not happen */

    pool->pages[slot].pid   = pid;
    pool->pages[slot].valid = true;
    pool->pages[slot].dirty = false;
    pool->pages[slot].hist  = hist;
    page_ht_insert(pool, &pool->pages[slot]);
    pool->used++;

    hist_record_access(hist, pool->clock);
    return false;
}

void lruk_destroy(LRUKPool *pool) {
    for (int i = 0; i < HIST_HASH_SIZE; i++) {
        HistEntry *e = pool->hist_ht[i];
        while (e) { HistEntry *next = e->hash_next; free(e); e = next; }
    }
    free(pool->pages);
    free(pool);
}

/* clock_pro.c -- CLOCK-Pro page replacement */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define HASH_SIZE 4096

typedef unsigned int page_id_t;

typedef enum { PG_HOT, PG_COLD, PG_TEST } PageStatus;

typedef struct ClockEntry {
    page_id_t        pid;
    PageStatus       status;
    bool             ref;        /* reference bit */
    bool             in_cache;   /* has actual data (not test-only) */
    struct ClockEntry *next;     /* circular list */
    struct ClockEntry *prev;
    struct ClockEntry *hash_next;
} ClockEntry;

typedef struct ClockProPool {
    int           capacity;     /* max resident (data-bearing) pages */
    int           resident;     /* current resident count */
    int           cold_target;  /* target number of cold pages */
    int           cold_count;
    int           hot_count;
    int           test_count;
    int           test_limit;

    ClockEntry    sentinel;     /* dummy head of circular list */
    ClockEntry   *hand_hot;
    ClockEntry   *hand_cold;
    ClockEntry   *hand_test;

    ClockEntry   *ht[HASH_SIZE];
} ClockProPool;

/* --- circular list operations --- */
static void clist_init(ClockEntry *s) {
    s->next = s->prev = s;
}

static void clist_insert_before(ClockEntry *pos, ClockEntry *entry) {
    entry->prev = pos->prev;
    entry->next = pos;
    pos->prev->next = entry;
    pos->prev = entry;
}

static void clist_remove(ClockEntry *entry) {
    entry->prev->next = entry->next;
    entry->next->prev = entry->prev;
}

static bool clist_empty(ClockEntry *s) {
    return s->next == s;
}

/* --- hash table --- */
static unsigned int pg_hash(page_id_t pid) {
    return (pid * 2654435761u) % HASH_SIZE;
}

static ClockEntry *ht_lookup(ClockProPool *pool, page_id_t pid) {
    unsigned int h = pg_hash(pid);
    for (ClockEntry *e = pool->ht[h]; e; e = e->hash_next)
        if (e->pid == pid) return e;
    return NULL;
}

static void ht_insert(ClockProPool *pool, ClockEntry *e) {
    unsigned int h = pg_hash(e->pid);
    e->hash_next = pool->ht[h];
    pool->ht[h] = e;
}

static void ht_remove(ClockProPool *pool, ClockEntry *e) {
    unsigned int h = pg_hash(e->pid);
    ClockEntry **pp = &pool->ht[h];
    while (*pp) {
        if (*pp == e) { *pp = e->hash_next; return; }
        pp = &(*pp)->hash_next;
    }
}

/* --- advance hand, skip sentinel --- */
static ClockEntry *advance(ClockProPool *pool, ClockEntry *hand) {
    hand = hand->next;
    if (hand == &pool->sentinel) hand = hand->next;
    return hand;
}

/* --- run HAND-test: reclaim expired test entries --- */
static void run_hand_test(ClockProPool *pool) {
    while (pool->test_count > pool->test_limit) {
        if (clist_empty(&pool->sentinel)) return;
        ClockEntry *e = pool->hand_test;
        if (e == &pool->sentinel) {
            pool->hand_test = advance(pool, pool->hand_test);
            continue;
        }
        pool->hand_test = advance(pool, pool->hand_test);
        if (e->status == PG_TEST) {
            clist_remove(e);
            ht_remove(pool, e);
            pool->test_count--;
            free(e);
        }
    }
}

/* --- run HAND-hot: demote cold hot pages --- */
static void run_hand_hot(ClockProPool *pool) {
    int steps = 0;
    while (steps < pool->capacity * 2) {
        ClockEntry *e = pool->hand_hot;
        if (e == &pool->sentinel) {
            pool->hand_hot = advance(pool, pool->hand_hot);
            steps++;
            continue;
        }
        if (e->status != PG_HOT) {
            pool->hand_hot = advance(pool, pool->hand_hot);
            steps++;
            continue;
        }
        if (e->ref) {
            e->ref = false;
            pool->hand_hot = advance(pool, pool->hand_hot);
            steps++;
            continue;
        }
        /* demote to cold */
        e->status = PG_COLD;
        pool->hot_count--;
        pool->cold_count++;
        pool->hand_hot = advance(pool, pool->hand_hot);
        return;
    }
}

/* --- run HAND-cold: evict cold pages --- */
static void evict_one(ClockProPool *pool) {
    int steps = 0;
    while (steps < pool->capacity * 2) {
        ClockEntry *e = pool->hand_cold;
        if (e == &pool->sentinel) {
            pool->hand_cold = advance(pool, pool->hand_cold);
            steps++;
            continue;
        }
        if (e->status == PG_COLD && e->in_cache) {
            if (!e->ref) {
                /* evict: turn into test entry */
                pool->hand_cold = advance(pool, pool->hand_cold);
                e->in_cache = false;
                e->status = PG_TEST;
                pool->cold_count--;
                pool->test_count++;
                pool->resident--;
                run_hand_test(pool);
                return;
            }
            /* ref=1: promote to hot */
            e->ref = false;
            e->status = PG_HOT;
            pool->cold_count--;
            pool->hot_count++;
            /* maintain hot/cold balance */
            if (pool->hot_count > pool->capacity - pool->cold_target)
                run_hand_hot(pool);
        }
        pool->hand_cold = advance(pool, pool->hand_cold);
        steps++;
    }
}

/* --- public API --- */
ClockProPool *clockpro_create(int capacity) {
    ClockProPool *pool = (ClockProPool *)calloc(1, sizeof(ClockProPool));
    pool->capacity    = capacity;
    pool->cold_target = capacity / 4;
    pool->test_limit  = capacity;
    clist_init(&pool->sentinel);
    pool->hand_hot  = &pool->sentinel;
    pool->hand_cold = &pool->sentinel;
    pool->hand_test = &pool->sentinel;
    return pool;
}

bool clockpro_access(ClockProPool *pool, page_id_t pid) {
    ClockEntry *e = ht_lookup(pool, pid);

    if (e && e->in_cache) {
        /* hit */
        e->ref = true;
        return true;
    }

    if (e && e->status == PG_TEST) {
        /* test hit: page was recently evicted, promote to hot */
        if (pool->cold_target > 1)
            pool->cold_target--;

        /* need room */
        while (pool->resident >= pool->capacity)
            evict_one(pool);

        clist_remove(e);
        pool->test_count--;
        e->status   = PG_HOT;
        e->in_cache = true;
        e->ref      = false;
        clist_insert_before(pool->hand_hot, e);
        pool->hot_count++;
        pool->resident++;
        return false;
    }

    /* cold miss: brand new page */
    while (pool->resident >= pool->capacity)
        evict_one(pool);

    e = (ClockEntry *)calloc(1, sizeof(ClockEntry));
    e->pid      = pid;
    e->status   = PG_COLD;
    e->ref      = false;
    e->in_cache = true;
    ht_insert(pool, e);
    clist_insert_before(pool->hand_cold, e);
    pool->cold_count++;
    pool->resident++;

    if (pool->cold_target < pool->capacity - 1)
        pool->cold_target++;

    return false;
}

void clockpro_destroy(ClockProPool *pool) {
    ClockEntry *e = pool->sentinel.next;
    while (e != &pool->sentinel) {
        ClockEntry *next = e->next;
        free(e);
        e = next;
    }
    free(pool);
}

/*
 * 页面只有处于 young 区域后 1/4 之后的位置时，
 * 再次访问才会被移到链表头部。
 * 位于前 1/4 的页面即使被访问也不移动。
 * 这大幅减少了链表 mutex 的争用。
 */
if (page_is_in_young_region(page) &&
    page->LRU_position < young_length / 4) {
    /* do NOT move to head, already hot enough */
    return;
}
buf_LRU_make_block_young(page);

/*
 * PostgreSQL buffer replacement (simplified)
 *
 * Each buffer has a usage_count (0..5), not just a single bit.
 * Clock hand sweeps the shared buffer array.
 * On access: usage_count = min(usage_count + 1, 5)
 * On sweep: if usage_count > 0, decrement; else evict.
 */
static BufferDesc *clock_sweep_victim(void) {
    for (;;) {
        BufferDesc *buf = &BufferDescriptors[next_victim];
        next_victim = (next_victim + 1) % NBuffers;

        uint32 state = pg_atomic_read_u32(&buf->state);
        int usage = BUF_STATE_GET_USAGECOUNT(state);

        if (usage == 0) {
            /* found victim */
            return buf;
        }
        /* decrement usage count */
        pg_atomic_fetch_sub_u32(&buf->state, BUF_USAGECOUNT_ONE);
    }
}

typedef struct BufferTag {
    RelFileLocator  rlocator;   /* tablespace + database + relation */
    ForkNumber      forkNum;    /* main / fsm / vm */
    BlockNumber     blockNum;
} BufferTag;

-- InnoDB: 命中率
SHOW GLOBAL STATUS LIKE 'Innodb_buffer_pool%';

-- 计算命中率
-- hit_rate = 1 - (reads / read_requests)
-- 健康值: > 99% (OLTP), > 95% (混合负载)

-- PostgreSQL: 命中率
SELECT
    datname,
    blks_hit::float / (blks_hit + blks_read) AS hit_rate
FROM pg_stat_database
WHERE blks_hit + blks_read > 0;