39、设计原则在缓存系统中的应用：LRU/LFU缓存设计，装饰器模式实现缓存统计

缓存系统，说白了就是拿空间换时间。你想想看，一个高频访问的数据，每次都要去数据库或者远程服务拉一遍，那延迟和压力都受不了。我早年做游戏后端时，一个排行榜接口每秒被调用上千次，每次都要从MySQL里算一遍排名——结果可想而知，数据库直接被打挂了。

后来我引入了缓存层，问题才解决。但缓存也不是随便写个map就完事的，你得考虑淘汰策略、统计监控、扩展性。今天我们就聊聊，怎么用设计原则来指导缓存系统的设计。

缓存淘汰策略：LRU与LFU

先说说两种最常见的淘汰策略。

LRU（Least Recently Used）：淘汰最久没被访问的数据。它的核心假设是——如果一个数据最近被访问过，那么未来被访问的概率也高。

LFU（Least Frequently Used）：淘汰访问频率最低的数据。它的核心假设是——访问次数多的数据，未来更可能被访问。

我在项目中遇到过一个问题：用LRU缓存一个新闻列表，结果热点新闻一过，那些旧新闻还占着缓存位置，因为它们在刚发布时被访问过，后来就没人看了。换成LFU之后，低频旧数据很快就被淘汰了。

核心区别：LRU关注“时间局部性”，LFU关注“频率局部性”。没有绝对的好坏，取决于业务场景。

LRU缓存的设计

LRU的经典实现是“哈希表+双向链表”。哈希表保证O(1)查找，双向链表保证O(1)移动和删除。

class LRUCache {
private:
    struct Node {
        int key, value;
        Node *prev, *next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    Node *head, *tail;  // 虚拟头尾节点
    unordered_map<int, Node*> cache;

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }

    Node* removeTail() {
        Node* node = tail->prev;
        removeNode(node);
        return node;
    }

public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!cache.count(key)) return -1;
        Node* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        } else {
            if (cache.size() >= capacity) {
                Node* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
            }
            Node* node = new Node(key, value);
            cache[key] = node;
            addToHead(node);
        }
    }
};

个人习惯：我写LRU时喜欢用虚拟头尾节点，这样能省去大量判空逻辑。你试试看，代码会清爽很多。

LFU缓存的设计

LFU比LRU复杂一些。你需要维护每个数据的访问频率，并且当缓存满时，淘汰频率最低的那个。如果多个数据频率相同，还得淘汰最久没用的那个——说白了就是LRU的变种。

我常用的实现是“频率到桶的映射”，每个桶里放一个双向链表，链表里放相同频率的节点。

class LFUCache {
private:
    struct Node {
        int key, value, freq;
        Node *prev, *next;
        Node(int k, int v) : key(k), value(v), freq(1), prev(nullptr), next(nullptr) {}
    };

    struct FreqList {
        Node *head, *tail;
        FreqList() {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head->next = tail;
            tail->prev = head;
        }
        void remove(Node* node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        void addToHead(Node* node) {
            node->next = head->next;
            node->prev = head;
            head->next->prev = node;
            head->next = node;
        }
        bool empty() { return head->next == tail; }
        Node* removeTail() {
            Node* node = tail->prev;
            remove(node);
            return node;
        }
    };

    int capacity, minFreq;
    unordered_map<int, Node*> cache;
    unordered_map<int, FreqList*> freqMap;

    void increaseFreq(Node* node) {
        int oldFreq = node->freq;
        freqMap[oldFreq]->remove(node);
        if (freqMap[oldFreq]->empty() && oldFreq == minFreq) {
            minFreq++;
        }
        node->freq++;
        if (!freqMap.count(node->freq)) {
            freqMap[node->freq] = new FreqList();
        }
        freqMap[node->freq]->addToHead(node);
    }

public:
    LFUCache(int cap) : capacity(cap), minFreq(0) {}

    int get(int key) {
        if (!cache.count(key)) return -1;
        Node* node = cache[key];
        increaseFreq(node);
        return node->value;
    }

    void put(int key, int value) {
        if (capacity == 0) return;
        if (cache.count(key)) {
            Node* node = cache[key];
            node->value = value;
            increaseFreq(node);
        } else {
            if (cache.size() >= capacity) {
                Node* removed = freqMap[minFreq]->removeTail();
                cache.erase(removed->key);
                delete removed;
            }
            Node* node = new Node(key, value);
            cache[key] = node;
            minFreq = 1;
            if (!freqMap.count(1)) {
                freqMap[1] = new FreqList();
            }
            freqMap[1]->addToHead(node);
        }
    }
};

我曾经踩过的坑：LFU里minFreq的维护很容易出错。当你删除一个节点后，如果那个频率的链表空了，而minFreq正好等于那个频率，你得更新minFreq。我一开始忘了这个，结果缓存满了之后永远淘汰不了数据，内存直接爆了。

装饰器模式：给缓存加统计

现在缓存的核心功能有了。但产品经理说：“能不能加个统计？我想看缓存命中率、访问次数、淘汰次数。”

你当然可以直接在LRUCache和LFUCache里加统计代码。但这样违反了开闭原则——对扩展开放，对修改关闭。每次加新功能都要改核心类，代码会越来越臃肿。

这时候装饰器模式就派上用场了。它允许你动态地给对象添加职责，而不修改原有代码。

// 缓存接口
class Cache {
public:
    virtual ~Cache() = default;
    virtual int get(int key) = 0;
    virtual void put(int key, int value) = 0;
};

// 统计装饰器
class CacheStatsDecorator : public Cache {
private:
    Cache* wrapped;
    int hitCount;
    int missCount;
    int evictCount;

public:
    CacheStatsDecorator(Cache* cache) 
        : wrapped(cache), hitCount(0), missCount(0), evictCount(0) {}

    int get(int key) override {
        int result = wrapped->get(key);
        if (result != -1) {
            hitCount++;
        } else {
            missCount++;
        }
        return result;
    }

    void put(int key, int value) override {
        int oldSize = getSize(); // 假设有这个方法
        wrapped->put(key, value);
        if (getSize() <= oldSize) {
            evictCount++;
        }
    }

    double getHitRate() {
        int total = hitCount + missCount;
        return total == 0 ? 0.0 : (double)hitCount / total;
    }

    void printStats() {
        std::cout << "命中次数: " << hitCount << "\n"
                  << "未命中次数: " << missCount << "\n"
                  << "淘汰次数: " << evictCount << "\n"
                  << "命中率: " << getHitRate() << "\n";
    }
};

使用起来也很简单：

Cache* lru = new LRUCache(100);
Cache* statsLru = new CacheStatsDecorator(lru);

statsLru->put(1, 10);
statsLru->get(1);  // 命中
statsLru->get(2);  // 未命中

// 输出统计
dynamic_cast<CacheStatsDecorator*>(statsLru)->printStats();

我建议：装饰器模式特别适合这种场景——你想给现有类加功能，但又不想改它的代码。而且你可以叠加多个装饰器，比如再加一个“日志装饰器”、“延迟监控装饰器”，每个装饰器只关注一件事，符合单一职责原则。

知识体系结构图

缓存系统设计知识体系 缓存核心 LRU策略（时间局部性） LFU策略（频率局部性） 装饰器模式（统计） 装饰器模式（日志/监控） 设计原则：开闭原则 / 单一职责 / 依赖倒置

总结

今天的内容其实就三个要点：

  • LRU和LFU是两种经典的缓存淘汰策略，各有适用场景。LRU实现简单，适合时间局部性强的场景；LFU更精准，但实现复杂一些。
  • 装饰器模式让我们在不修改核心类的前提下，给缓存加上统计、日志等额外功能。这符合开闭原则。
  • 设计原则不是纸上谈兵。你看，单一职责让每个类只做一件事，开闭原则让系统易于扩展——这些原则在缓存系统里体现得淋漓尽致。

嗯，缓存系统看起来简单，但真要设计好，里面门道不少。下次你再写缓存的时候，不妨想想今天聊的这些原则，说不定能帮你少踩几个坑。

专注资料整理
← 上一章 📖 返回目录 下一章 →