算法

缓存淘汰算法

LRU / LFU / Clock — 操作系统页表、数据库缓冲池与进程内缓存的核心替换策略

LRU（最近最少使用）

淘汰最久未被访问的条目。实现：双向链表（头部 = 最近使用，尾部 = 最久未用）+ HashMap(key→node)，get/put 均为 O(1)。

算法步骤

  1. get(key)：若存在，将节点移到链表头（MRU 端），返回 value；否则返回 -1
  2. put(key, val)：若存在，更新 value 并移到头部；否则在头部插入新节点
  3. 若插入后超出容量，删除尾部节点（LRU 条目）并从 HashMap 中移除
struct Node { int key, val; Node *prev, *next; };

class LRUCache {
    int cap;
    unordered_map<int, Node*> mp;
    Node *head, *tail; // sentinels

    void remove(Node* n) {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    void insertFront(Node* n) {
        n->next = head->next; n->prev = head;
        head->next->prev = n; head->next = n;
    }
public:
    LRUCache(int c) : cap(c) {
        head = new Node{0,0,nullptr,nullptr};
        tail = new Node{0,0,nullptr,nullptr};
        head->next = tail; tail->prev = head;
    }
    int get(int key) {
        if (!mp.count(key)) return -1;
        remove(mp[key]); insertFront(mp[key]);
        return mp[key]->val;
    }
    void put(int key, int val) {
        if (mp.count(key)) { remove(mp[key]); delete mp[key]; mp.erase(key); }
        else if ((int)mp.size() == cap) {
            Node* lru = tail->prev;
            remove(lru); mp.erase(lru->key); delete lru;
        }
        Node* n = new Node{key, val, nullptr, nullptr};
        insertFront(n); mp[key] = n;
    }
};

应用场景

  • Redis maxmemory-policy allkeys-lru / volatile-lru
  • OS 页面置换——通过引用位（NRU）近似 LRU
  • InnoDB Buffer Pool——含 young/old 段的 LRU 子列表
  • CPU LLC——硬件伪 LRU 树

注意：真实硬件采用 Clock 算法（引用位近似），因为记录精确访问顺序需要对每次内存访问加锁，开销极高。

练习：缓存 — LRU Cache — 代码练习
测试用例（2 个）
用例 1
输入：2 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4
期望：1 -1 -1 3 4
用例 2
输入：1 put 1 1 put 2 2 get 1 get 2
期望：-1 2

LFU（最不频繁使用）

淘汰访问频率最低的条目，频率相同时按 LRU 顺序淘汰。O(1) 实现：key→(val,freq) 映射 + freq→LinkedHashSet of keys 映射 + minFreq 指针。

算法步骤

  1. get(key)：若存在，freq+1，将 key 从当前 freq 桶移入 freq+1 桶，必要时更新 minFreq
  2. put(key, val)：若存在，更新 value 后执行 get 逻辑；否则以 freq=1 插入，重置 minFreq=1
  3. 若超出容量，淘汰 minFreq 桶中最早插入的 key
class LFUCache {
    int cap, minFreq;
    unordered_map<int,pair<int,int>> key_val_freq; // key->{val,freq}
    unordered_map<int,list<int>> freq_keys;        // freq->list of keys (LRU order)
    unordered_map<int,list<int>::iterator> key_it; // key->iterator in freq list

    void touch(int key) {
        int f = key_val_freq[key].second++;
        freq_keys[f].erase(key_it[key]);
        if (freq_keys[f].empty()) {
            freq_keys.erase(f);
            if (minFreq == f) minFreq++;
        }
        freq_keys[f+1].push_front(key);
        key_it[key] = freq_keys[f+1].begin();
    }
public:
    LFUCache(int c) : cap(c), minFreq(0) {}
    int get(int key) {
        if (!key_val_freq.count(key)) return -1;
        touch(key); return key_val_freq[key].first;
    }
    void put(int key, int val) {
        if (cap <= 0) return;
        if (key_val_freq.count(key)) { key_val_freq[key].first = val; touch(key); return; }
        if ((int)key_val_freq.size() == cap) {
            int evict = freq_keys[minFreq].back();
            freq_keys[minFreq].pop_back();
            if (freq_keys[minFreq].empty()) freq_keys.erase(minFreq);
            key_val_freq.erase(evict); key_it.erase(evict);
        }
        key_val_freq[key] = {val, 1};
        freq_keys[1].push_front(key);
        key_it[key] = freq_keys[1].begin();
        minFreq = 1;
    }
};

应用场景

  • Redis maxmemory-policy allkeys-lfu（Redis 4.0+，带频率衰减）
  • CDN 边缘节点缓存——热门内容更持久
  • ZFS / Solaris 的 ARC（自适应替换缓存）——融合 LRU + LFU

对比 LRU：LFU 能抵抗「历史热点污染」问题，但新插入条目的初始频率为 1，在高写压力下容易被立即淘汰。

练习：缓存 — LFU Cache — 代码练习
测试用例（2 个）
用例 1
输入：2 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3
期望：1 -1 3
用例 2
输入：2 put 1 1 put 2 2 get 1 get 1 put 3 3 get 2 get 1
期望：1 1 -1 1

时钟算法（Second-Chance）

用循环缓冲区+引用位近似 LRU，O(1) 均摊。时钟指针扫描：引用位=1 则清零并继续；引用位=0 则淘汰该槽位。

算法步骤

  1. 命中时：将该槽位的引用位置 1
  2. 缺页（缓存已满）：推进指针；若 ref_bit=1，清零并继续推进；直到 ref_bit=0
  3. 淘汰当前指针位置，装入新页，设 ref_bit=1，指针推进 1
// Clock algorithm: returns total page faults for access sequence
int clockSimulation(int capacity, vector<int>& pages) {
    vector<int> frame(capacity, -1);
    vector<bool> ref(capacity, false);
    int hand = 0, faults = 0;

    for (int page : pages) {
        // Check if already in cache
        bool hit = false;
        for (int i = 0; i < capacity; i++) {
            if (frame[i] == page) { ref[i] = true; hit = true; break; }
        }
        if (hit) continue;
        faults++;
        // Scan for a slot to evict
        while (ref[hand]) { ref[hand] = false; hand = (hand + 1) % capacity; }
        frame[hand] = page;
        ref[hand] = true;
        hand = (hand + 1) % capacity;
    }
    return faults;
}

应用场景

  • Linux 内核 PFRA——active/inactive 双链表变体，使用引用位
  • PostgreSQL 共享缓冲区管理器——clock-sweep 置换
  • 嵌入式 RTOS——每帧仅需 1 bit，内存开销极小

优势：时钟算法只需翻转一个引用位，无需移动链表节点，在硬件规模下缓存友好度远高于真实 LRU。最坏扫描 O(n)，缓存热时期望 O(1)。

练习：缓存 — Clock Algorithm — 代码练习
测试用例（3 个）
用例 1
输入：3 1 2 3 4 1 2 5 1 2 3 4 5
期望：7
用例 2
输入：2 1 2 1 3 1 2 3
期望：5
用例 3
输入：4 1 2 3 4 5 1 2 3 4 5
期望：6