页面置换算法：LRU 的谎言与 ARC 的真相

2003 年，IBM 的 Nimrod Megiddo 和 Dharmendra Modha 发表了一篇论文：ARC: A Self-Tuning, Low Overhead Replacement Cache。这篇论文优雅地解决了一个困扰系统设计者三十多年的问题：如何在不知道工作负载特征的情况下，自动在”最近性”和”频率”之间取得平衡？

为了理解 ARC 的精妙，我们需要先理解 LRU 的缺陷。而要理解 LRU 的缺陷，我们需要先理解”最优”是什么——Bélády 在 1966 年就告诉我们了。

这篇文章不是操作系统教科书的复述。我会用数学证明告诉你为什么 LRU 是”stack algorithm”，用真实的 trace 数据告诉你 LRU 在哪些场景下比 FIFO 还差，用竞争性分析推导 ARC 的理论保证，然后给出一个完整的 C 实现——包括四个链表和自适应参数 \(p\) 的全部细节。

一、为什么需要页面置换

虚拟内存与 page fault

现代操作系统通过虚拟内存为每个进程提供独立的地址空间。当进程访问的虚拟页面不在物理内存中时，CPU 触发一个 page fault 异常。操作系统的 page fault handler 负责：

1. 找到该页面在磁盘上的位置（swap 分区或文件映射）。
2. 如果物理内存已满，选择一个牺牲页面（victim page）淘汰——这就是页面置换算法的职责。
3. 将目标页面从磁盘读入物理内存，更新页表映射。
4. 重启引发 fault 的指令。

一次 page fault 的代价是巨大的。内存访问延迟约 100 ns，而磁盘 I/O（即使是 SSD）至少 10 μs——差了两个数量级。如果是传统 HDD，延迟高达 10 ms，差五个数量级。页面置换算法的好坏直接决定了系统在内存压力下的性能。

问题的精确定义

给定： - 物理内存容纳 \(k\) 个页面（页框数） - 一个页面引用序列 \(r_1, r_2, \ldots, r_n\)（来自虚拟地址的页面号） - 初始时物理内存为空

目标：设计一个在线算法（只能看到当前和过去的引用，不能看未来），在每次缺页时决定淘汰哪个页面，使总缺页次数最小。

这就是经典的 demand paging 模型。注意几个关键约束：

1. 在线性：算法不能偷看未来。这是与 Bélády 最优算法的根本区别。
2. 强制缺页（compulsory miss / cold miss）：第一次访问任何页面都必然缺页，任何算法都无法避免。
3. 容量缺页（capacity miss）：工作集大于物理内存时不可避免。
4. 冲突缺页（conflict miss）：算法选择不当导致的额外缺页——这是我们要最小化的。

Bélády 的 OPT 算法与不可实现性

1966 年，László Bélády 提出了最优页面置换算法（OPT，也叫 MIN 或 Clairvoyant）：

淘汰未来最久不会被引用的页面。

如果有页面将来永远不会被引用，淘汰它；否则淘汰下次引用距当前最远的那个。

定理：OPT 产生的缺页次数不多于任何其他算法。

证明（交换论证）：假设存在算法 A 在某序列上比 OPT 少缺页。取第一个 A 和 OPT 行为不同的时刻 \(t\)。此时 A 淘汰了页面 \(p\)，OPT 淘汰了页面 \(q\)（\(q\) 是未来最远引用的）。将 A 在 \(t\) 的决策替换为淘汰 \(q\)，不会增加总缺页次数——因为 \(q\) 被引用的时间最晚，替换它”延迟”了缺页发生的时间最长。逐步替换 A 的所有决策为 OPT 的决策，缺页不增。矛盾。\(\blacksquare\)

OPT 不可实现——它需要知道完整的未来引用序列。它的价值是提供理论下界。在评估缓存算法时，我通常会跑两组数据：一组 OPT（离线计算），一组待评估算法。两者的缺页率之差就是算法的”优化空间”。

为什么这个问题无处不在

你可能觉得”页面置换”只是操作系统课的考试题。错了。这个抽象模型出现在所有分层存储系统中：

• 数据库缓冲池：MySQL InnoDB、PostgreSQL 都有自己的页面置换策略。
• CPU 缓存：L1/L2/L3 缓存的 eviction 策略就是硬件实现的页面置换。
• CDN 缓存：Varnish、Nginx 的缓存淘汰。
• Redis 内存淘汰：当 maxmemory 达到上限时。

理解页面置换的本质，就是理解所有缓存系统的核心。

二、FIFO 与 Bélády 异常

FIFO 算法

最简单的在线算法：淘汰最早进入内存的页面。用一个环形队列即可实现。

typedef struct {
    int *pages;
    int capacity;
    int head;
    int count;
} FIFOCache;

int fifo_access(FIFOCache *cache, int page) {
    for (int i = 0; i < cache->count; i++) {
        if (cache->pages[(cache->head + i) % cache->capacity] == page)
            return 1;  // 命中
    }
    if (cache->count < cache->capacity) {
        cache->pages[(cache->head + cache->count) % cache->capacity] = page;
        cache->count++;
    } else {
        cache->pages[cache->head] = page;
        cache->head = (cache->head + 1) % cache->capacity;
    }
    return 0;  // 缺页
}

为什么更多内存反而更多缺页

FIFO 有一个违反直觉的性质：增加页框数量反而可能增加缺页次数。这就是 Bélády 异常（Bélády’s Anomaly）。

经典反例——引用序列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5：

• 3 个页框：9 次缺页
• 4 个页框：10 次缺页

手动推演 3 个页框的情况：

请求: 1  2  3  4  1  2  5  1  2  3  4  5
页框: 1  1  1  4  4  4  5  5  5  3  3  3
      -  2  2  2  1  1  1  1  1  1  4  4
      -  -  3  3  3  2  2  2  2  2  2  5
缺页: *  *  *  *  *  *  *  -  -  *  *  *  → 9 次

4 个页框的情况：

请求: 1  2  3  4  1  2  5  1  2  3  4  5
页框: 1  1  1  1  1  1  5  5  5  5  4  4
      -  2  2  2  2  2  2  1  1  1  1  5
      -  -  3  3  3  3  3  3  2  2  2  2
      -  -  -  4  4  4  4  4  4  3  3  3
缺页: *  *  *  *  -  -  *  *  *  *  *  *  → 10 次

更多页框，更多缺页！FIFO 的”淘汰最老”策略在某些模式下是灾难性的——一个页面可能很老但正在被频繁使用。

Bélády 异常揭示了一个深刻的事实：“先来后到”不是缓存优先级的好依据。 页面进入内存的时间与它未来是否会被使用之间没有因果关系。

三、LRU 的理论：栈算法与 OPT 的最佳近似

算法描述

LRU（Least Recently Used）淘汰最近最久未被使用的页面。与 FIFO 的区别是：LRU 考虑最后一次使用的时间，而 FIFO 只考虑进入的时间。

LRU 的核心假设是时间局部性（temporal locality）：最近被访问的页面在近期内更可能被再次访问。这个假设在大多数工作负载下成立——但不是全部，后面会看到反例。

栈算法性质与包含性

LRU 属于一类叫做 stack algorithm 的算法。设 \(B_t(k)\) 为时刻 \(t\) 时、使用 \(k\) 个页框的内存内容，那么对所有 \(t\) 和 \(k\)：

\[ B_t(k) \subseteq B_t(k+1) \]

即：用 \(k\) 个页框时内存中的页面，一定也在用 \(k+1\) 个页框时的内存中。这就是包含性（inclusion property）。

推论：stack algorithm 不会出现 Bélády 异常。增加页框数只会减少（或不变）缺页次数。

证明：如果算法是 stack algorithm，那么用 \(k+1\) 个页框时，内存是用 \(k\) 个页框时内存的超集。\(k\) 个页框时的命中，在 \(k+1\) 个页框时也一定命中。但 \(k+1\) 个页框时可能还有额外的命中（位于第 \(k+1\) 个位置的页面）。所以缺页次数单调不增。\(\blacksquare\)

为什么 LRU 是 stack algorithm？因为 LRU 维护一个按最近使用时间排序的栈。用 \(k\) 个页框就是取栈顶 \(k\) 个元素；用 \(k+1\) 个页框就是取栈顶 \(k+1\) 个。前者显然是后者的子集。

为什么 LRU 是 OPT 的最佳”镜像”

OPT 看未来：淘汰未来最远引用的页面。LRU 看过去：淘汰过去最远引用的页面。LRU 本质上是 OPT 的时间反转——它假设”过去的访问模式是未来的最佳预测”。

在随机过程理论中，如果引用序列是时间可逆的（time-reversible），比如独立同分布（i.i.d.）或某些马尔科夫链模型，LRU 就是精确的 OPT 镜像。这解释了为什么在很多”自然”工作负载下 LRU 表现良好——因为时间局部性模式通常具有近似的时间可逆性。

Stack Distance 分析

LRU 的 stack algorithm 性质带来一个优美的分析工具：stack distance（栈距离）。

对每次页面引用，定义其 stack distance 为该页面在 LRU 栈中的位置（最近使用的在栈顶，位置为 1）。如果页面不在栈中，stack distance 为 \(\infty\)。

• stack distance \(\leq k\)（页框数）→ 命中
• stack distance \(> k\) → 缺页

一次模拟就可以得到所有 \(k\) 值下的缺页率曲线——这就是 stack algorithm 的威力。你不需要对每个 \(k\) 分别跑模拟。

四、LRU 的工程实现

双向链表加哈希表：O(1) 的经典方案

精确 LRU 需要在每次内存访问时更新页面在排序结构中的位置。经典实现是双向链表 + 哈希表：

#include <stdlib.h>
#include <string.h>

#define HT_SIZE 4096

typedef struct LRUNode {
    int key;
    int value;
    struct LRUNode *prev;
    struct LRUNode *next;
    struct LRUNode *ht_next;  // 哈希表链
} LRUNode;

typedef struct {
    int capacity;
    int size;
    LRUNode *head;   // MRU 端
    LRUNode *tail;   // LRU 端（淘汰候选）
    LRUNode *buckets[HT_SIZE];
} LRUCache;

static unsigned hash_key(int key) {
    return (unsigned)key % HT_SIZE;
}

static LRUNode *ht_lookup(LRUCache *c, int key) {
    for (LRUNode *n = c->buckets[hash_key(key)]; n; n = n->ht_next)
        if (n->key == key) return n;
    return NULL;
}

static void ht_insert(LRUCache *c, LRUNode *node) {
    unsigned h = hash_key(node->key);
    node->ht_next = c->buckets[h];
    c->buckets[h] = node;
}

static void ht_remove(LRUCache *c, LRUNode *node) {
    unsigned h = hash_key(node->key);
    LRUNode **pp = &c->buckets[h];
    while (*pp != node) pp = &(*pp)->ht_next;
    *pp = node->ht_next;
}

static void detach(LRUCache *c, LRUNode *node) {
    if (node->prev) node->prev->next = node->next;
    else c->head = node->next;
    if (node->next) node->next->prev = node->prev;
    else c->tail = node->prev;
}

static void push_front(LRUCache *c, LRUNode *node) {
    node->prev = NULL;
    node->next = c->head;
    if (c->head) c->head->prev = node;
    c->head = node;
    if (!c->tail) c->tail = node;
}

int lru_get(LRUCache *c, int key) {
    LRUNode *node = ht_lookup(c, key);
    if (!node) return -1;
    detach(c, node);     // O(1)
    push_front(c, node); // O(1) 移到 MRU 端
    return node->value;
}

void lru_put(LRUCache *c, int key, int value) {
    LRUNode *node = ht_lookup(c, key);
    if (node) {
        node->value = value;
        detach(c, node);
        push_front(c, node);
        return;
    }
    if (c->size == c->capacity) {
        LRUNode *victim = c->tail;  // LRU 端淘汰
        detach(c, victim);
        ht_remove(c, victim);
        free(victim);
        c->size--;
    }
    node = calloc(1, sizeof(LRUNode));
    node->key = key;
    node->value = value;
    ht_insert(c, node);
    push_front(c, node);
    c->size++;
}

每次 get 和 put 都是 O(1)。空间开销是每页面一个链表节点加一个哈希条目。

为什么操作系统不用精确 LRU

在软件缓存（Redis、memcached、数据库缓冲池）中，每次操作顺便更新链表可以接受。但在操作系统页面置换中，每次内存访问都更新链表是不可能的：

1. 频率太高：CPU 每秒执行数十亿次内存访问，每次都做链表操作不可行。
2. 用户态/内核态切换：内存访问在用户态完成，如果每次都陷入内核更新链表，开销灾难性。
3. 多核竞争：链表是共享数据结构，多核同时更新需要加锁，导致严重的 cache line bouncing。

因此没有任何主流操作系统实现精确 LRU。所有系统都用近似 LRU——利用硬件提供的引用位（reference bit）来低成本地跟踪页面访问。

LRU 在实际工作负载中的三大问题

理论上优美的 LRU，在实际中有三个致命问题：

顺序扫描污染（Sequential Flooding）：数据库缓冲池 1000 页，热数据命中率 95%。一次全表扫描扫了 10000 页——每个新页面成为”最近使用”，放到 LRU 栈顶，热数据全被冲走。扫描结束后命中率从 95% 跌到 0%。

循环访问模式（Loop Pattern）：引用序列 1, 2, ..., k+1, 1, 2, ...，\(k\) 个页框。LRU 缺页率 100%——每次访问恰好是栈底页面。而 FIFO 或随机替换的缺页率约为 \(1/(k+1)\)，远好于 LRU。

近似带来的额外损失：操作系统用 CLOCK 近似 LRU，但只有 1 bit 的”最近使用”信息，高压力下退化为近似 FIFO。

这三个问题叠加，使得 LRU 的实际表现远不如教科书暗示的那么好。

五、CLOCK（二次机会）：环形缓冲与 reference bit

硬件基础

x86 CPU 的 PTE（Page Table Entry）有一个 Accessed bit (A bit)。每当 CPU 访问一个页面，硬件自动将 A bit 设为 1。操作系统可以清除 A bit，过一段时间再检查——如果被重新设为 1，说明这段时间内页面被访问过。

CLOCK 算法利用这个硬件支持实现近似 LRU，无需在每次内存访问时做任何软件操作。

算法与实现

把所有页面排成一个环形链表，一个时钟指针（clock hand）指向当前扫描位置：

typedef struct {
    int *pages;
    int *ref_bits;
    int capacity;
    int hand;
    int count;
} ClockCache;

int clock_evict(ClockCache *cache) {
    while (1) {
        if (cache->ref_bits[cache->hand] == 0) {
            int victim = cache->hand;
            cache->hand = (cache->hand + 1) % cache->capacity;
            return victim;
        }
        // 给"第二次机会"：清除引用位，跳过
        cache->ref_bits[cache->hand] = 0;
        cache->hand = (cache->hand + 1) % cache->capacity;
    }
}

int clock_access(ClockCache *cache, int page) {
    for (int i = 0; i < cache->count; i++) {
        if (cache->pages[i] == page) {
            cache->ref_bits[i] = 1;
            return 1;  // 命中
        }
    }
    int victim;
    if (cache->count < cache->capacity) {
        victim = cache->count++;
    } else {
        victim = clock_evict(cache);
    }
    cache->pages[victim] = page;
    cache->ref_bits[victim] = 1;
    return 0;  // 缺页
}

与 LRU 的近似关系

CLOCK 的近似程度取决于时钟指针的扫描速度：

• 低内存压力：指针转得慢，页面有足够时间被再次访问并重置 R bit。效果接近 LRU——最近被使用的页面有 R=1，不会被淘汰。
• 高内存压力：指针转得快，几乎所有页面在被再次访问之前就被扫到了。效果退化为 FIFO——按进入环的顺序淘汰。

直觉上，CLOCK 把 LRU 的连续时间排序”量化”为了 1-bit 的二值分类：最近被用过（R=1）和没被用过（R=0）。这在大多数情况下足够，但丢失了”谁比谁更近”的精确信息。

增强型 CLOCK（Enhanced CLOCK / NRU）加入脏页位 M，组合 (R, M) 形成四个优先级：淘汰时优先选 (0,0) 即未引用且干净的页面，其次 (0,1)，再次 (1,0)，最后 (1,1)。这减少了不必要的磁盘写回。

六、CLOCK-Pro：三种状态与自适应

为什么 CLOCK 不够

经典 CLOCK 的致命缺陷与 LRU 相同：无法区分频率和最近性。一个被顺序扫描访问一次的页面获得 R=1，和一个被反复访问的热页面获得同样的保护。

2005 年，Song Jiang、Feng Chen 和 Xiaodong Zhang 提出了 CLOCK-Pro，将 ARC 的自适应思想融入 CLOCK 的硬件友好框架中。

三种页面状态

CLOCK-Pro 为每个页面维护三种状态：

• hot：高频访问页面，类似 ARC 的 T2。受保护，不参与淘汰。
• cold（resident）：在缓存中但只被访问少量次数，类似 ARC 的 T1。淘汰候选。
• cold（test / non-resident）：已被淘汰但保留元数据的影子条目，类似 ARC 的 B1/B2。

三个时钟指针

CLOCK-Pro 在同一个环形缓冲上运行三个指针：

                    ┌───────────────────────────────────┐
                    │  环形缓冲（混合 hot / cold 页面）  │
                    │                                   │
    hand_cold ────► │  扫描 cold 页面，执行淘汰          │
                    │                                   │
    hand_hot  ────► │  扫描 hot 页面，降级为 cold         │
                    │                                   │
    hand_test ────► │  清理过期的 test (shadow) 条目     │
                    └───────────────────────────────────┘

• hand_cold：扫描 cold（resident）页面。如果 R=0，淘汰它，创建 test 条目。如果 R=1，提升为 hot。
• hand_hot：扫描 hot 页面。如果 R=0，降级为 cold。如果 R=1，清除 R，保留 hot 状态。
• hand_test：清理过期的 test 条目，限制影子列表大小。

自适应机制

CLOCK-Pro 的自适应通过 test 条目实现。当一个 cold 页面被淘汰后，变成 test 条目。如果在 test 期间内该页面再次被请求（refault），说明缓存中的 cold 空间太小了——系统自适应地增大 cold 的配额，减少 hot 的配额。

这与 ARC 中 B1 命中后增大 \(p\) 的逻辑完全对应，但 CLOCK-Pro 只需要引用位和 hot/cold 标记位（可以塞进 PTE 的空闲位），不需要链表操作。

为什么比 CLOCK 强得多

在 Scan-Heavy 工作负载下，普通 CLOCK 和 LRU 一样被顺序扫描冲垮。CLOCK-Pro 则不同：

1. 扫描页面初始状态为 cold，只被访问一次后就被 hand_cold 淘汰。
2. 这些页面的 test 条目不会产生后续命中（因为扫描页面不会再被访问）。
3. 因此 cold 的配额不会被自适应地增大——hot 页面的空间得到保护。

在作者的实验中，CLOCK-Pro 在 SPC1（存储性能委员会标准 trace）上的命中率比 CLOCK 高 10-15 个百分点，与 ARC 和 LIRS 持平。

七、2Q：三个队列的冷热分离

核心设计

2Q 算法（Theodore Johnson 和 Dennis Shasha，1994 年）是另一种抗扫描污染的方案。它维护三个队列：

• A1in（FIFO 队列）：新页面首先进入这里。容量通常为缓存的 25%。
• A1out（影子 FIFO 队列）：从 A1in 淘汰的页面在此保留页面号（不缓存数据）。容量通常为缓存的 50%。
• Am（LRU 队列）：从 A1in 或 A1out “毕业”的热页面。容量为缓存的 75%。

页面流转

新页面请求
 │
 ├── 在 Am 中命中 → 移到 Am 的 MRU 端（热数据保护）
 │
 ├── 在 A1in 中命中 → 什么都不做（避免在 FIFO 队列中乱序）
 │
 ├── 在 A1out 中命中 → 从磁盘加载，插入 Am 的 MRU 端
 │                     （二次访问证明了"热度"，提升到 LRU 区）
 │
 └── 完全未命中 → 插入 A1in 的尾部
                  如果 A1in 满 → 淘汰 A1in 头部，页面号进入 A1out
                  如果 A1out 满 → 淘汰 A1out 头部（丢弃影子）

关键洞察

2Q 的核心洞察是：只被访问一次的页面不应该进入 LRU 区。A1in 是一个”试用期”——只有在试用期结束后（被淘汰到 A1out）又被再次请求的页面，才证明了自己的热度，才有资格进入 Am。

这天然抗顺序扫描：全表扫描的页面只被访问一次，在 A1in 中按 FIFO 淘汰，永远不会污染 Am 中的热数据。

2Q 的局限

2Q 的 A1in 和 Am 的大小比例是静态配置的。如果工作负载改变（比如从 scan-heavy 变为 lookup-heavy），静态比例可能不再合适。这正是 ARC 解决的问题——用 ghost list 的命中反馈动态调整比例。

// 2Q 的核心淘汰逻辑（简化）
void twoq_access(TwoQ *tq, int page) {
    if (lru_contains(tq->Am, page)) {
        lru_move_to_mru(tq->Am, page);
        return;  // Am 命中
    }
    if (fifo_contains(tq->A1in, page)) {
        return;  // A1in 命中，不移动
    }
    if (fifo_contains(tq->A1out, page)) {
        fifo_remove(tq->A1out, page);
        if (lru_full(tq->Am))
            evict_from_Am(tq);
        lru_insert_mru(tq->Am, page);
        return;  // A1out 命中 → 提升到 Am
    }
    // 完全未命中
    if (fifo_full(tq->A1in)) {
        int victim = fifo_evict(tq->A1in);
        if (fifo_full(tq->A1out))
            fifo_evict(tq->A1out);  // 丢弃最老的影子
        fifo_insert(tq->A1out, victim);
    }
    fifo_insert(tq->A1in, page);
}

八、ARC：自适应替换缓存

核心洞察

ARC 的核心洞察可以用一句话概括：

用淘汰历史（ghost entries）来预测未来的工作负载特征，并据此动态调整策略。

LRU 只考虑最近性（recency）。LFU 只考虑频率（frequency），且对新页面不友好。ARC 同时维护两个 LRU 链表——T1 偏向 recency，T2 偏向 frequency——然后根据实际命中情况动态调整两者的大小。

T1/T2/B1/B2 四个列表

ARC 维护四个链表，总共管理最多 \(2c\) 个条目（\(c\) 是缓存容量）：

• T1：最近只被引用一次的页面（recency LRU），目标大小 \(p\)
• T2：最近被引用两次以上的页面（frequency LRU），目标大小 \(c - p\)
• B1：T1 的影子条目——最近从 T1 淘汰的页面号（不缓存数据）
• B2：T2 的影子条目——最近从 T2 淘汰的页面号

约束：\(|T1| + |T2| \leq c\)，\(|T1| + |B1| \leq c\)，\(|T2| + |B2| \leq c\)，\(|T1| + |T2| + |B1| + |B2| \leq 2c\)。

                    ┌────────────────────────────────────┐
  direction of      │                                    │
  recency ────►     │    B1      │     T1    ║    T2     │     B2      │
                    │  (ghost)   │  (cache)  ║  (cache)  │   (ghost)   │
                    │            │           ║           │             │
                    └────────────────────────────────────┘
                                 ←────── c ──────►
                                         ↑
                              自适应参数 p 控制 T1/T2 的分割点

自适应参数 p 与数学证明

ARC 维护参数 \(p\)（\(0 \leq p \leq c\)），表示 T1 的目标大小。\(p\) 的调整策略：

B1 命中时（刚从 T1 淘汰的页面又被请求）——recency 信号，增大 \(p\)：

\[ p \leftarrow \min\left(p + \delta_1, c\right), \quad \delta_1 = \max\left(\frac{|B2|}{|B1|}, 1\right) \]

B2 命中时（刚从 T2 淘汰的页面又被请求）——frequency 信号，减小 \(p\)：

\[ p \leftarrow \max\left(p - \delta_2, 0\right), \quad \delta_2 = \max\left(\frac{|B1|}{|B2|}, 1\right) \]

\(\delta\) 的设计精妙之处在于比例感知：如果 B1 比 B2 小，B1 中的每次命中信号更”珍贵”（因为 T1 淘汰得少），\(\delta_1\) 就更大，\(p\) 增长更快。反之亦然。

scan-resistant 的数学论证：考虑一个 scan 序列（\(n \gg c\) 个不同页面的单次顺序访问）混合少量热点页面的工作负载。scan 页面进入 T1，从 T1 的 LRU 端淘汰后进入 B1。但这些 scan 页面不会再被访问，所以 B1 不会有命中。没有 B1 命中就意味着 \(p\) 不会增大——T1 不会抢占 T2 的空间。热点页面安全地留在 T2 中。与此同时，如果热点页面从 T2 淘汰进入 B2 后又被请求，B2 命中使 \(p\) 减小，T2 获得更多空间。系统自动收敛到对热点友好的状态。

九、ARC 的竞争性分析

竞争比的定义

对于在线算法 A 和离线最优算法 OPT，A 的竞争比（competitive ratio）定义为：

\[ \exists \alpha, \beta \geq 0, \forall \sigma: \text{cost}_A(\sigma) \leq \alpha \cdot \text{cost}_{OPT}(\sigma) + \beta \]

其中 \(\sigma\) 是任意请求序列。\(\alpha\) 越小，算法越接近最优。

LRU 的竞争比

Sleator 和 Tarjan（1985 年）证明了一个经典结果：

定理：对于容量为 \(k\) 的缓存，LRU 的竞争比为 \(k\)。即对任意序列 \(\sigma\)：

\[ \text{cost}_{LRU}(\sigma) \leq k \cdot \text{cost}_{OPT}(\sigma) + k \]

这是紧的——存在使 LRU 达到 \(k\) 倍 OPT 缺页次数的最坏序列。就是前面提到的循环模式 1, 2, ..., k+1, 1, 2, ...：LRU 每次都缺页，OPT 只缺 \(1/(k+1)\) 的次数。

更惊人的是，Sleator 和 Tarjan 还证明了没有确定性在线算法能做到比 \(k\) 更好的竞争比。LRU 在最坏情况下已经是最优的确定性算法。

ARC 的竞争性优势

ARC 的理论保证比单纯的竞争比更精细。Megiddo 和 Modha 证明了：

定理（ARC 的包含性）：设 \(\text{LRU}(p^*, c)\) 表示在 T1 大小固定为 \(p^*\)、T2 大小固定为 \(c - p^*\) 的静态分割下运行 LRU 的缺页次数。则对任意请求序列 \(\sigma\) 和任意 \(p^* \in [0, c]\)：

\[ \text{cost}_{ARC}(\sigma) \leq \text{cost}_{LRU(p^*, c)}(\sigma) + O(c) \]

即 ARC 的缺页次数不超过已知最优 T1/T2 比例的静态 LRU 分割，再加上一个与序列长度无关的常数项。ARC 不需要事先知道 \(p^*\) 是什么——它通过 ghost list 的反馈自动逼近。

p 的移动策略的直觉

想象 \(p\) 在 \([0, c]\) 上做一维随机游走：

• B1 命中 → \(p\) 向右走（给 T1 更多空间）
• B2 命中 → \(p\) 向左走（给 T2 更多空间）

\(p\) 的平衡点就是当前工作负载下 T1/T2 的最优分割。如果工作负载是 recency-heavy，B1 命中多于 B2 命中，\(p\) 稳定在较大值；反之稳定在较小值。如果工作负载切换，\(p\) 在几轮淘汰内就能迁移到新的平衡点。

这种”用错误来学习”的机制——通过观察哪些淘汰决策是”错误的”（ghost list 命中 = 不该淘汰的页面被淘汰了）来调整策略——是 ARC 最深刻的设计思想。

十、完整 C 实现：ARC 算法

以下是一个完整的、可编译的 ARC 实现，包含四个链表和自适应 \(p\) 调节的全部逻辑。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ====== 双向链表节点 ====== */
typedef struct DNode {
    int key;
    struct DNode *prev;
    struct DNode *next;
} DNode;

typedef struct {
    DNode head;   // 哨兵头（MRU 端）
    DNode tail;   // 哨兵尾（LRU 端）
    int size;
} DList;

static void dlist_init(DList *l) {
    l->head.prev = NULL;
    l->head.next = &l->tail;
    l->tail.prev = &l->head;
    l->tail.next = NULL;
    l->size = 0;
}

static void dlist_remove(DList *l, DNode *n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
    l->size--;
}

static void dlist_push_mru(DList *l, DNode *n) {
    n->next = l->head.next;
    n->prev = &l->head;
    l->head.next->prev = n;
    l->head.next = n;
    l->size++;
}

static DNode *dlist_pop_lru(DList *l) {
    if (l->size == 0) return NULL;
    DNode *n = l->tail.prev;
    dlist_remove(l, n);
    return n;
}

/* ====== 简易哈希表 ====== */
#define ARC_HT_BITS 12
#define ARC_HT_SIZE (1 << ARC_HT_BITS)

typedef struct HTEntry {
    int key;
    int list_id;           // 0=T1, 1=T2, 2=B1, 3=B2
    DNode *node;
    struct HTEntry *next;
} HTEntry;

typedef struct {
    HTEntry *buckets[ARC_HT_SIZE];
} HashTable;

static unsigned arc_hash(int key) {
    return ((unsigned)key * 2654435761u) >> (32 - ARC_HT_BITS);
}

static HTEntry *ht_find(HashTable *ht, int key) {
    for (HTEntry *e = ht->buckets[arc_hash(key)]; e; e = e->next)
        if (e->key == key) return e;
    return NULL;
}

static void ht_put(HashTable *ht, int key, int list_id, DNode *node) {
    HTEntry *e = malloc(sizeof(HTEntry));
    e->key = key;
    e->list_id = list_id;
    e->node = node;
    unsigned h = arc_hash(key);
    e->next = ht->buckets[h];
    ht->buckets[h] = e;
}

static void ht_del(HashTable *ht, int key) {
    unsigned h = arc_hash(key);
    HTEntry **pp = &ht->buckets[h];
    while (*pp) {
        if ((*pp)->key == key) {
            HTEntry *tmp = *pp;
            *pp = tmp->next;
            free(tmp);
            return;
        }
        pp = &(*pp)->next;
    }
}

/* ====== ARC 主体 ====== */
typedef struct {
    int c;                 // 缓存容量
    int p;                 // T1 的目标大小
    DList T1, T2, B1, B2;
    HashTable ht;
    long hits;
    long misses;
} ARC;

static void arc_init(ARC *arc, int capacity) {
    arc->c = capacity;
    arc->p = 0;
    dlist_init(&arc->T1);
    dlist_init(&arc->T2);
    dlist_init(&arc->B1);
    dlist_init(&arc->B2);
    memset(&arc->ht, 0, sizeof(arc->ht));
    arc->hits = 0;
    arc->misses = 0;
}

static DNode *make_node(int key) {
    DNode *n = malloc(sizeof(DNode));
    n->key = key;
    return n;
}

static void arc_replace(ARC *arc, int in_b2) {
    if (arc->T1.size > 0 &&
        (arc->T1.size > arc->p ||
         (in_b2 && arc->T1.size == arc->p))) {
        /* 从 T1 淘汰到 B1 */
        DNode *victim = dlist_pop_lru(&arc->T1);
        HTEntry *e = ht_find(&arc->ht, victim->key);
        e->list_id = 2;  // 标记为 B1
        dlist_push_mru(&arc->B1, victim);
    } else if (arc->T2.size > 0) {
        /* 从 T2 淘汰到 B2 */
        DNode *victim = dlist_pop_lru(&arc->T2);
        HTEntry *e = ht_find(&arc->ht, victim->key);
        e->list_id = 3;  // 标记为 B2
        dlist_push_mru(&arc->B2, victim);
    }
}

static int imax(int a, int b) { return a > b ? a : b; }
static int imin(int a, int b) { return a < b ? a : b; }

void arc_access(ARC *arc, int key) {
    HTEntry *e = ht_find(&arc->ht, key);

    if (e && (e->list_id == 0 || e->list_id == 1)) {
        /* Case 1: 在 T1 或 T2 中命中 → 移到 T2 的 MRU 端 */
        arc->hits++;
        DList *from = (e->list_id == 0) ? &arc->T1 : &arc->T2;
        dlist_remove(from, e->node);
        dlist_push_mru(&arc->T2, e->node);
        e->list_id = 1;
        return;
    }

    if (e && e->list_id == 2) {
        /* Case 2: B1 命中 — recency 信号，增大 p */
        arc->misses++;
        int d1 = imax(arc->B2.size / imax(arc->B1.size, 1), 1);
        arc->p = imin(arc->p + d1, arc->c);

        arc_replace(arc, 0);

        dlist_remove(&arc->B1, e->node);
        dlist_push_mru(&arc->T2, e->node);
        e->list_id = 1;
        return;
    }

    if (e && e->list_id == 3) {
        /* Case 3: B2 命中 — frequency 信号，减小 p */
        arc->misses++;
        int d2 = imax(arc->B1.size / imax(arc->B2.size, 1), 1);
        arc->p = imax(arc->p - d2, 0);

        arc_replace(arc, 1);

        dlist_remove(&arc->B2, e->node);
        dlist_push_mru(&arc->T2, e->node);
        e->list_id = 1;
        return;
    }

    /* Case 4: 完全未命中 */
    arc->misses++;

    int t1b1 = arc->T1.size + arc->B1.size;
    int t2b2 = arc->T2.size + arc->B2.size;

    if (t1b1 == arc->c) {
        if (arc->T1.size < arc->c) {
            DNode *ghost = dlist_pop_lru(&arc->B1);
            ht_del(&arc->ht, ghost->key);
            free(ghost);
            arc_replace(arc, 0);
        } else {
            DNode *victim = dlist_pop_lru(&arc->T1);
            ht_del(&arc->ht, victim->key);
            free(victim);
        }
    } else if (t1b1 < arc->c && t1b1 + t2b2 >= arc->c) {
        if (t1b1 + t2b2 >= 2 * arc->c) {
            DNode *ghost = dlist_pop_lru(&arc->B2);
            ht_del(&arc->ht, ghost->key);
            free(ghost);
        }
        arc_replace(arc, 0);
    } else {
        arc_replace(arc, 0);
    }

    DNode *n = make_node(key);
    dlist_push_mru(&arc->T1, n);
    ht_put(&arc->ht, key, 0, n);
}

/* 测试驱动 */
int main(void) {
    ARC arc;
    arc_init(&arc, 4);

    int trace[] = {1,2,3,4,1,2,5,1,2,3,4,5};
    int n = sizeof(trace) / sizeof(trace[0]);

    for (int i = 0; i < n; i++)
        arc_access(&arc, trace[i]);

    printf("ARC(c=4): hits=%ld, misses=%ld, hit_rate=%.1f%%\n",
           arc.hits, arc.misses,
           100.0 * arc.hits / (arc.hits + arc.misses));
    return 0;
}

编译运行：gcc -O2 -o arc arc.c && ./arc

十一、Linux 的实际方案

Active/Inactive 双链表

Linux 内核没有使用经典 CLOCK 或 ARC，而是用了双链表方案。内核为每个内存 zone 维护五条 LRU 链表（匿名页 active/inactive，文件页 active/inactive，不可回收页），核心是 active/inactive 的两级过滤：

• Active LRU list：存放”最近被多次访问”的热页面。
• Inactive LRU list：存放”可能不再需要”的冷页面。

页面的生命周期：

首次访问 → Inactive list 尾部（一次引用不算"热"）
   ↓
在 Inactive 中再次被访问 → 提升到 Active list
   ↓
Active list 满了 → 头部的页面降级到 Inactive list 尾部
   ↓
Inactive list 回收 → 从头部开始淘汰

这个设计天然抗单次扫描：全表扫描页面只引用一次，留在 Inactive list 中，不会污染 Active list。

kswapd 守护进程

Linux 的页面回收不是在 page fault 时同步执行的，而是由 kswapd 内核线程异步完成。kswapd 在后台监控每个 zone 的空闲页面数量：

• 当空闲页面低于 low watermark 时，kswapd 被唤醒，开始扫描 inactive list 回收页面。
• 当空闲页面升到 high watermark 以上时，kswapd 停止。
• 如果 kswapd 来不及回收，空闲页面跌到 min watermark 以下时，分配路径上的进程会被迫执行 direct reclaim——同步回收，这是性能杀手。

kswapd 的扫描逻辑：

1. 从 inactive list 的 LRU 端开始扫描
2. 对每个页面：
   a. 如果 PTE 的 Accessed bit = 1 → 清除，移到 active list（提升）
   b. 如果 Accessed bit = 0 且是干净页面 → 直接回收
   c. 如果 Accessed bit = 0 且是脏页面 → 发起回写 I/O，稍后回收
3. active list 太大时 → 从 active 的 LRU 端降级页面到 inactive

Workingset Detection

Linux 3.15+（Johannes Weiner, 2014）引入了 workingset detection，借鉴了 CLOCK-Pro 和 ARC 的影子条目思想。

当一个文件页面被淘汰时，它在 radix tree（后来改为 xarray）的 slot 中留下一个影子条目（shadow entry），记录淘汰时的 “eviction sequence counter”。当同一页面再次被请求（refault）时：

1. 找到它的影子条目，读取淘汰时的序列号。
2. 计算 refault distance = 当前序列号 - 淘汰时序列号。
3. 如果 refault distance ≤ inactive list 的长度，说明这个页面”本不应该被淘汰”（如果缓存再大一点就能命中）。直接将它激活到 Active list，跳过 Inactive list 的”试用期”。

这一机制让 Linux 的页面回收具有了类似 ARC 的自适应能力——通过 refault 历史判断淘汰是否过激，动态调整 active/inactive 的平衡。

Linux 5.9 进一步引入了多代 LRU（MGLRU，Yu Zhao），用多个年龄代（generation）替换传统的两级 active/inactive，提供更精细的年龄追踪，显著降低了高内存压力下的性能抖动。

十二、工程陷阱与个人观点

工程陷阱表

算法选型速查

个人观点

一、LRU 是教学工具，不是工程方案。 每次我看到生产系统的缓存设计文档里写”我们使用 LRU 淘汰策略”，我的第一反应是追问：“你的工作负载有没有扫描模式？”如果回答”有”或”不确定”，那 LRU 就是错误的选择。

二、ARC 的真正伟大之处不在于它的性能数字，而在于它的设计哲学。 用”错误的淘汰记录”来自动调整策略——这个想法可以推广到任何在线决策系统。机器学习中的 bandit 算法、TCP 拥塞控制中的 AIMD、负载均衡中的 power-of-two-choices，都有类似的”用反馈学习”的精神。

三、不要低估”近似”的力量。 Linux 的 CLOCK 变体 + workingset detection + MGLRU，在理论纯粹度上远不如 ARC，但它在工程约束下（硬件引用位、多核扩展性、中断上下文）做到了惊人的好。完美的理论算法如果无法在给定约束下实现，不如一个”粗糙但可行”的近似。

四、缓存算法的选择取决于工作负载，不是算法本身的”好坏”。 没有在所有工作负载下都最优的在线算法——Sleator-Tarjan 下界告诉我们，确定性在线算法的最坏情况竞争比不可能低于 \(k\)。所以关键是理解你的工作负载特征：是 recency 主导、frequency 主导、还是混合型？有没有 scan 模式？工作负载会不会动态切换？如果你不确定，ARC 是最安全的默认选择。

五、IBM 的 ARC 专利已经过期了（2023 年）。 曾经因为专利问题而不得不用 2Q 或 CLOCK-Pro 替代 ARC 的项目，现在可以自由地使用 ARC 了。如果你正在设计新的缓存系统，没有理由不考虑 ARC。

系列导航： - 上一篇：内存分配器对决 - 下一篇：进程调度：从 CFS 到 EEVDF

相关阅读： - 缓冲池管理算法 - 缓存无关算法