C++ 并发 LRU Cache 实现对比

发表于 分类于
调研对比主流 C++ 并发 LRU Cache 开源实现，分析各版本的设计特点、并发策略及适用场景。

简介

LRU Cache 是最常用的本地缓存淘汰策略。虽然经典的 std::list + std::unordered_map 实现只需 50 行代码，但在并发场景下，线程安全和性能优化会带来显著的复杂度。本文调研了当前 C++ 生态中几个有代表性的 LRU Cache 实现，从数据结构、并发策略、淘汰机制等维度进行对比。

经典实现：list + unordered_map

最基础的 LRU Cache 用双向链表维护访问顺序，哈希表提供 O(1) 查找。每次 get/put 时将被访问的条目移动到链表头部，容量满时淘汰链表尾部的条目。

template <typename K, typename V>
class SimpleLRUCache {
    using ListIter = typename std::list<std::pair<K, V>>::iterator;

    size_t capacity_;
    std::list<std::pair<K, V>> list_;
    std::unordered_map<K, ListIter> map_;
    mutable std::shared_mutex mtx_;

public:
    std::optional<V> get(const K& key) {
        std::unique_lock lock(mtx_);
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;
        // 移到链表头部
        list_.splice(list_.begin(), list_, it->second);
        return it->second->second;
    }

    void put(const K& key, const V& value) {
        std::unique_lock lock(mtx_);
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }
        if (list_.size() >= capacity_) {
            map_.erase(list_.back().first);
            list_.pop_back();
        }
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }
};

优点：

  • 代码少，易于理解和维护
  • std::list::splice 不分配新节点，移动操作 O(1)

缺点：

  • std::list 每次插入都分配堆内存（Node 分配），cache-unfriendly
  • std::shared_mutex 在极高并发下成为瓶颈
  • 链表中每个节点存储 pair<K,V>，存在额外的指针追踪开销

适合缓存量不大（几千以内）、并发度不高的场景。

folly::EvictingCacheMap — 侵入式链表

Facebook Folly 库中的 EvictingCacheMap 是单线程场景下最经典的 LRU Map 实现。它通过 Boost.Intrusive 将 LRU 链表指针直接嵌入到 value 对象内部，消除了独立的链表节点分配。

核心设计：一个对象同时属于两个容器

EvictingCacheMap 使用了 Boost.Intrusive 的多重继承机制，让每个缓存条目既是一个哈希表条目，又是一个 LRU 链表节点：

struct Node
    : public boost::intrusive::unordered_set_base_hook<safe_link>,  // 哈希桶链指针
      public boost::intrusive::list_base_hook<safe_link>           // LRU 链表指针
{
    std::pair<const K, V> pr;
};
  • unordered_set_base_hook 在 Node 内部嵌入了哈希桶碰撞链的 prev/next 指针
  • list_base_hook 在 Node 内部嵌入了 LRU 双向链表的 prev/next 指针
  • Node 本身是一个 pair<K,V>，不需要额外的包装

这意味着：一次 new 分配，Node 同时出现在哈希表中和 LRU 链表中。相比于 list<pair<K,V>> 的方式，省去了为每个条目分配独立 list::node 的开销，内存布局更加紧凑，缓存友好性更好。

关键操作

查找并提升到 MRU 位置：

iterator find(const K& key) {
    auto it = index_.find(key);             // 哈希查找
    if (it == index_.end()) return end();
    lru_.erase(lru_.iterator_to(*it));      // 从 LRU 当前位移除
    lru_.push_front(*it);                   // 推到 MRU
    return iterator(lru_.iterator_to(*it));
}

淘汰：

void prune(size_t count) {
    for (size_t i = 0; i < count && !lru_.empty(); ++i) {
        auto* node = &lru_.back();          // LRU 尾是最久未用的
        lru_.pop_back();
        index_.erase(index_.iterator_to(*node));
        delete node;                        // 释放内存
    }
}

关键限制

  1. 非线程安全：EvictingCacheMap 不提供内部同步，需要外部加锁
  2. 哈希表容量不会自动缩小：setMaxSize() 修改淘汰阈值不会调整哈希桶数
  3. 哈希表初始桶数 = max(capacity/2, 100)，之后不会 resize

如何变成并发版本

在实际项目中，围绕 EvictingCacheMap 构建并发缓存通常采用分片锁模式：创建 N 个 EvictingCacheMap 实例，根据 key 的哈希值路由到不同的实例，每个实例独立加锁。这种设计思路是工业界最常用的策略。

vpetrigo/caches — 策略可插拔

vpetrigo/caches 是一个轻量级 header-only 库，定位类似 Python 的 cachetools，支持多种淘汰策略。

特性

  • 淘汰策略可插拔：LRU、LFU、FIFO 三种策略，通过模板参数切换
  • 支持自定义哈希表：可将 std::unordered_map 替换为 phmap::node_hash_map 等高性能容器
  • 线程安全：所有公开方法内部用 std::mutex + RAII 保护
  • C++11 兼容：不依赖高版本 C++ 特性
#include "caches/cache.hpp"
#include "caches/lru_cache_policy.hpp"

// 定义 LRU Cache 类型
template <typename K, typename V>
using lru_cache_t = typename caches::fixed_sized_cache<K, V, caches::LRUCachePolicy>;

lru_cache_t<std::string, int> cache(256);
cache.Put("hello", 1);
auto val = cache.Get("hello");  // 抛出 std::range_error 如果不存在
auto [val, ok] = cache.TryGet("hello");  // 安全版本，不抛异常

淘汰策略对比

策略 Touch(key) 操作 淘汰规则
LRU 将 key 移到链表头部 淘汰链表尾部（最久未访问）
LFU 递增 key 的访问计数 淘汰计数最小的 key
FIFO 无操作 淘汰最早插入的 key

局限性

  • 无 TTL / 时间过期：纯粹基于容量淘汰，不支持时间维度的过期
  • 全局锁：单个 std::mutex 保护所有操作，高并发下扩展性有限
  • Get 返回引用：锁释放后引用可能悬空（需要调用方立即消费）

适用场景：快速集成、淘汰策略需要灵活切换、并发度不高的项目。

oneTBB concurrent_lru_cache — 工业级并发

Intel oneTBB 提供了 concurrent_lru_cache，是目前 C++ 生态中并发级别最高的 LRU Cache 实现之一。它基于 handle 机制和引用计数保证线程安全。

设计思想

  • Handle 访问：operator[] 返回 handle 对象而非裸引用。handle 持有 value 的引用计数，只要 handle 存在，value 就不会被淘汰
  • 工厂函数：miss 时调用用户提供的工厂函数构造 value，工厂函数需要线程安全
  • 引用计数淘汰：只有引用计数归零的条目才参与 LRU 淘汰
  • 预览特性：需要定义 TBB_PREVIEW_CONCURRENT_LRU_CACHE=1
#define TBB_PREVIEW_CONCURRENT_LRU_CACHE 1
#include <oneapi/tbb/concurrent_lru_cache.h>

std::string load_from_db(int key) {
    return "value_" + std::to_string(key);
}

oneapi::tbb::concurrent_lru_cache<int, std::string> cache(load_from_db, 100);

// handle 持有 value 的引用，保证使用期间不被淘汰
auto handle = cache[42];
if (handle) {
    std::cout << handle.value() << std::endl;
} // handle 析构，引用计数减 1

特点总结

维度 描述
并发度 高 —— handle 机制允许真正的并发读
淘汰时机 延迟 —— 只有引用计数归零且容量超限时才淘汰
接口风格 类似工厂模式，miss 时自动构造
TTL 支持 无

优点：

  • 真正的并发安全，无需外部加锁
  • handle 解决了「使用中条目被淘汰」的问题
  • TBB 质量背书，适合生产环境

缺点：

  • 预览特性，API 可能变化
  • 依赖 TBB 整个库，引入较重
  • 淘汰策略只有 LRU，不可切换
  • 无 TTL

mohaps/lrucache11 — 轻量并发 + TTL

lrucache11 是一个 header-only 的 LRU Cache，在经典实现基础上增加了同步控制和 TTL 支持。

特性

  • 读写锁：使用 std::shared_mutex，读操作共享锁，写操作独占锁
  • TTL 支持：条目可设置过期时间，过期后自动失效
  • Loading 模式：miss 时自动调用 loader 函数填充
  • 支持自定义 Map 类型：可以将底层 unordered_map 替换为其他容器
#include "LRUCache11.hpp"

lru11::Cache<std::string, std::string> cache(1000, 0);  // 容量 1000，无 TTL

// TTL 模式
cache.insert("key", "value", std::chrono::seconds(60));

// Loading 模式
auto val = cache.get("key", [](const std::string& k) {
    return load_from_db(k);
});

优点：

  • 接口类似 Guava LoadingCache，Java 开发者容易上手
  • TTL 支持是大多数其他库缺少的功能
  • header-only，零编译依赖

缺点：

  • 读写锁在极高并发下仍有瓶颈
  • 性能优化不如 folly 或 TBB 深入

分片锁模式（Sharded LRU）

这是工业界实际上最常用的并发 LRU 方案——不是设计一个线程安全的 LRU，而是用 N 个独立的 EvictingCacheMap 实例，通过分片分散锁竞争：

template <typename K, typename V, size_t NumShards = 64>
class ShardedLRUCache {
    struct Shard {
        folly::EvictingCacheMap<K, V> map_;
        std::mutex mtx_;
    };
    std::array<Shard, NumShards> shards_;

    Shard& getShard(const K& key) {
        size_t h = std::hash<K>{}(key);
        return shards_[h % NumShards];
    }

public:
    std::optional<V> get(const K& key) {
        auto& shard = getShard(key);
        std::lock_guard lock(shard.mtx_);
        auto it = shard.map_.find(key);
        return it != shard.map_.end() ? std::optional(it->second) : std::nullopt;
    }
};

这也是 Folly 自身推荐的做法——EvictingCacheMap 不提供内部锁，交由上层灵活组合。分片锁的优点：

  • 锁粒度可控：分片数可以根据并发度自由调整
  • 实现简单：不需要复杂的无锁数据结构
  • 热点分散：不同的 key 落在不同的 shard，锁竞争概率降低到 1/NumShards
  • 可组合：与 EvictingCacheMap、flat_hash_map 等任意容器配合

缺点：不能跨分片做全局 LRU——淘汰只在单个 shard 内进行。在分布均匀的场景下，这通常不成问题。

进阶：W-TinyLFU（Caffeine 风格）

Java 的 Caffeine 缓存库以 W-TinyLFU 策略闻名，在命中率上显著优于纯 LRU。C++ 生态目前没有直接的等价库，但理解其设计模式有助于在需要极致命中率时自研。

W-TinyLFU 的核心思想

纯 LRU 的问题：一次突发流量扫过大量新 key，会把真正的热点数据全部踢出。W-TinyLFU 通过以下机制解决：

  1. 三层队列：

    • Window LRU (1%)：新条目先进入这里，处理突发访问
    • Probation LRU (20%)：考察区，候选淘汰对象
    • Protected LRU (80%)：热门区，长期热数据

  2. Count-Min Sketch：用极小的内存记录每条 key 的历史访问频率（4 行 × 16K 列 = ~256KB），淘汰时比较候选者的频率，而非简单的 LRU 位序

  3. 时间衰减：定期将所有频率计数减半，让「曾经热门、现已冷却」的数据自然降级

C++ 中的 Count-Min Sketch 示意

class CountMinSketch {
    static constexpr int kDepth = 4;
    static constexpr int kWidth = 1 << 14;     // 16K
    std::vector<std::vector<uint32_t>> table_; // 4 × 16K = ~256KB
    uint32_t counter_ = 0;

public:
    void increment(uint64_t hash) {
        for (int i = 0; i < kDepth; ++i) {
            size_t idx = (hash + i * 0x9e3779b9) & (kWidth - 1);
            table_[i][idx]++;
        }
        // 时间衰减：每 16K 次访问所有计数减半
        if (++counter_ >= kWidth) {
            for (auto& row : table_)
                for (auto& cell : row) cell >>= 1;
            counter_ = 0;
        }
    }

    uint32_t estimate(uint64_t hash) const {
        uint32_t min = UINT32_MAX;
        for (int i = 0; i < kDepth; ++i) {
            size_t idx = (hash + i * 0x9e3779b9) & (kWidth - 1);
            min = std::min(min, table_[i][idx]);
        }
        return min;  // 取最小值消除哈希冲突导致的过高估计
    }
};

W-TinyLFU 适合缓存命中率敏感的长期运行服务（如 CDN、广告、推荐系统），但实现复杂度高（~500+ 行核心代码），一般只有在纯 LRU 命中率确实无法满足需求时才值得投入。

方案对比总结

方案 并发策略 淘汰策略 TTL 依赖 适用场景
经典 list+map + shared_mutex 读写锁 LRU 需自建 无 小型缓存，快速原型
folly::EvictingCacheMap + 分片锁 外部 mutex / 分片锁 LRU 无 Boost.Intrusive 中大型项目，已在用 Folly
vpetrigo/caches 全局 mutex LRU/LFU/FIFO 无 无（header-only） 快速集成，需灵活策略
oneTBB concurrent_lru_cache Handle + 引用计数 LRU 无 Intel TBB 工业级并发，已有 TBB 依赖
mohaps/lrucache11 读写锁 LRU 支持 无（header-only） 需要 TTL 的 Loading Cache
分片锁 + 自选容器 分片锁 LRU（shard 内） 需自建 取决于容器 高并发，需要灵活定制
自研 W-TinyLFU 需自建 W-TinyLFU 需自建 Count-Min Sketch 命中率敏感，大规模长期运行

关键要点

1. 大部分场景用分片锁模式最实际

不是每个项目都有 TBB 或 Folly 依赖。用一个简单的 shared_mutex + 经典 list+map 实现，加上分片扩展，就能覆盖绝大多数需求。分片数选 16-64，锁粒度可控，实现简单。

2. 注意「全局 LRU」vs「分片 LRU」的区别

分片锁模式下，淘汰只在单个 shard 内进行——如果某些 shard 的 key 特别多或特别冷，可能导致整体缓存利用率不均衡。对于 key 分布均匀的场景（大多数场景），影响可忽略。如果对全局 LRU 有硬性要求，需要用 folly 或 TBB 的方案。

3. TTL 比淘汰策略更重要

在实践中，TTL（时间过期）对于缓存正确性的重要性往往超过淘汰策略。数据过期后的刷新比踢掉谁更关键。选择库时优先看 TTL 支持，大多数轻量 C++ LRU 库都不提供 TTL，需要自行封装。

4. 缓存库选择 = 依赖成本 vs 性能收益

  • 项目已有 Folly → 直接用 EvictingCacheMap + 分片锁
  • 项目已有 TBB → 用 concurrent_lru_cache
  • 零依赖快速集成 → vpetrigo/caches 或 lrucache11
  • 需要极致性能且可接受复杂度 → 基于 W-TinyLFU 自研

5. C++ 缺少一个「Caffeine 级别」的本地缓存库

Java 有 Guava Cache 和 Caffeine，Go 有 groupcache / ristretto，而 C++ 生态目前没有一个集 LRU/LFU/W-TinyLFU 多策略、TTL、权重、统计、异步刷新于一体的成熟本地缓存库。这既是痛点也是机会。

参考

  • folly::EvictingCacheMap 源码
  • vpetrigo/caches
  • oneTBB concurrent_lru_cache
  • mohaps/lrucache11
  • Caffeine: W-TinyLFU