1. 从一道经典题到工程实战LRU Cache 到底在解决什么问题先聊点实际的。LRULeast Recently Used最近最少使用这个名字凡是搞过一点点服务端开发、中间件设计或者刷过面试题的人都不可能陌生。但坦白讲很多人对它的理解停留在“用一个哈希表加一个双向链表get 和 put 都是 O(1)”这个层面上真让他从零手写一个能扛住高并发、能处理容量淘汰、能优雅应对缓存穿透的 LRU Cache往往就会卡壳。我最初接触 LRU Cache 也是在准备一场算法面试后来在几个真实项目里反复用到它才慢慢意识到这玩意儿表面上是一道“C 数据结构题”本质上是一套缓存淘汰策略的工程化实现。你设计的每一个节点、每一次指针移动、每一处锁的粒度都在真金白银地影响线上服务的延迟和命中率。先说它解决了什么问题。假设你有一个访问频率极高的热点数据源比如数据库里的用户信息、推荐系统的特征向量、或者某个计算成本很高的中间结果。如果每次请求都去源头取延迟和压力都受不了。于是你引入一层缓存把最近用过的数据放在内存里。但内存不是无限的缓存空间有限总得有个规则决定“新数据来了旧数据谁滚蛋”。LRU 的规则很朴素如果一块数据最近被访问过那么它很可能在接下来一段时间还会被访问反过来如果一块数据很久没被访问那它大概率已经凉了优先淘汰它。这个直觉在大量真实负载下是成立的比起随机淘汰、FIFO 先进先出LRU 的命中率通常更高实现成本又比 LFULeast Frequently Used最不经常使用低很多。LFU 需要维护访问频率计数还要处理频率衰减复杂度蹭蹭往上涨。所以 LRU 成为了从 CPU 缓存、操作系统内存管理到 Redis 的近似 LRU 策略、MySQL 的 buffer pool 里最常见的淘汰算法之一。也正是因为它太常用了C 面试官特别喜欢让你手写一个。但面试归面试工程上的 LRU Cache 远不止“写出来能跑”这么简单。这篇文章我会从一个完整的 C 实现出发把设计思路、代码细节、工程优化、常见坑点全部拆开讲。你可以把它当作一份可复现的手写 LRU 指南也可以把它当作理解缓存设计的一把钥匙。2. 哈希表 双向链表为什么是这两个结构换别的行不行设计一个 LRU Cache最核心的需求其实是三个访问某个 key 要足够快最好是 O(1)知道每个 key 的“最近使用时间”的相对顺序并且能在 O(1) 时间内把这个顺序调整好插入新数据、淘汰最久未使用的数据也要 O(1)单纯用一个数组插入和淘汰倒是简单但查找是 O(n)。单纯用一个哈希表unordered_map查找是 O(1)可是你无法知道哪个 key 是最久没用的除非额外给每个 key 盖时间戳然后每次淘汰去扫一遍找最小值那又是 O(n)。单纯用一个链表维护访问顺序很容易把刚访问的节点移到头部但查找一个 key 你得从头遍历到尾。哈希表负责“找得快”链表负责“记得住顺序”两者一拼所有操作都是 O(1)。这个组合不是谁拍脑袋想出来的而是这两种数据结构在能力上天然互补哈希表提供 O(1) 的 key 到节点的映射。注意这里存的是“指向链表节点的迭代器或指针”不是简单的 value 拷贝否则你更新顺序的时候还得再查一次链表。双向链表提供 O(1) 的节点删除和插入。为什么必须双向因为单向链表删除一个节点时你得知道它的前驱节点除非你每次都从头遍历那就不是 O(1) 了。双向链表每个节点都持有 prev 和 next 指针删除当前节点只需要改前后两个节点的指针干净利落。#include list #include unordered_map #include utility class LRUCache { private: using K int; using V int; using List std::liststd::pairK, V; using Iter typename List::iterator; List list_; // 双向链表头部是最近使用的尾部是最久未使用的 std::unordered_mapK, Iter map_; // key - 链表节点迭代器 int capacity_; public: explicit LRUCache(int capacity) : capacity_(capacity) {} int get(int key) { auto it map_.find(key); if (it map_.end()) { return -1; } // 命中把节点搬到链表头部 list_.splice(list_.begin(), list_, it-second); return it-second-second; } void put(int key, int value) { auto it map_.find(key); if (it ! map_.end()) { // 已存在更新值并搬到头部 it-second-second value; list_.splice(list_.begin(), list_, it-second); return; } if (map_.size() capacity_) { // 容量满淘汰链表尾部节点 auto old list_.back(); map_.erase(old.first); list_.pop_back(); } list_.emplace_front(key, value); map_[key] list_.begin(); } };这段代码你能直接跑逻辑也是对的。但注意我用的是std::list加splice这是工程里比较省心的做法因为迭代器不会因为链表插入删除而失效。面试时很多面试官会要求你手写链表节点和哈希表的指针操作那下面我再说说自实现的版本因为自己管理内存才能真正理解背后的代价。3. 从零手写节点与指针把链表操作拆到骨头里std::list固然方便但有些场景下你不能用标准库比如嵌入式环境没有 STL、或者你需要对内存分配做极致控制。更重要的是手写一遍能帮你把“为什么双向链表”“为什么哈希表存的是迭代器而不是 value”这些底层逻辑吃透。面试官也喜欢看到你能在白板上把prev和next指针撸出来。一个经典的裸实现是这样的struct Node { int key; int value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; class LRUCache { private: int capacity_; int size_; Node* head_; // 哨兵头节点不存数据next 指向真正的头部 Node* tail_; // 哨兵尾节点不存数据prev 指向真正的尾部 std::unordered_mapint, Node* map_; 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: explicit LRUCache(int capacity) : capacity_(capacity), size_(0) { head_ new Node(0, 0); tail_ new Node(0, 0); head_-next tail_; tail_-prev head_; } ~LRUCache() { Node* cur head_; while (cur) { Node* next cur-next; delete cur; cur next; } } int get(int key) { auto it map_.find(key); if (it map_.end()) { return -1; } Node* node it-second; moveToHead(node); return node-value; } void put(int key, int value) { auto it map_.find(key); if (it ! map_.end()) { Node* node it-second; node-value value; moveToHead(node); return; } if (size_ capacity_) { Node* removed removeTail(); map_.erase(removed-key); delete removed; --size_; } Node* node new Node(key, value); addToHead(node); map_[key] node; size_; } };这里有几个细节值得掰扯一下为什么用哨兵节点 head_ 和 tail_如果你不用哨兵那么链表为空、只有一个节点、插入头部、删除尾部这些边界情况都要一遍遍判空代码容易写得像一坨浆糊。哨兵节点让“空表”也有一个固定的虚拟头尾操作逻辑完全统一。head_ 的下一个永远是真正的最近使用节点tail_ 的上一个永远是最久未使用节点不管是空表还是满表代码都不用分叉。为什么 remove 之后还要 delete自实现版本里节点是用 new 分配的不用 delete 会内存泄漏。这个点很多开始手写算法的同学容易忽略因为用 STL 的时候容器析构会自动释放内存但裸指针不会。为什么哈希表存的是 Node*如果你只存 key 和 value那么 get 命中后你还需要重新在链表里查找 key 才能移动节点无法做到 O(1)。存 Node* 之后哈希表直接告诉你在哪个节点改指针即可。手写的版本还有一个好处你可以自己控制内存池比如预先分配一个足够大的节点数组用的时候从空闲链表里取释放的时候放回去避免频繁new/delete带来的性能抖动。高并发低延迟场景下这是很常见的优化手法。4. 参数选型与边界场景capacity 怎么定、key 用什么类型、value 要多大很多人写 LRU 时不太关心容量到底怎么设反正构造的时候给个数就行。但实际工程里 capacity 的设定直接决定了命中率和内存开销的平衡点。4.1 capacity 不是越大越好缓存空间越大能装的数据越多理论上命中率会上升。但内存有限而且当缓存数据量超过某个阈值后命中率增长会进入平台期。比如一个业务每天活跃用户 100 万每个用户的数据 1KB全放进来要 1GB 内存你可能只愿意分给缓存 256MB那 capacity 就得按 256MB 算。更务实的做法是先分析业务访问分布看热点数据集中在多大范围内把 capacity 设为“能装下绝大多数热点”的大小而不是一味求大。4.2 淘汰边界size_ capacity_还是size_ capacity_上面代码里我用if (size_ capacity_)是因为先判断容量是否已满满了先淘汰再插入一个新的。如果你写成if (size_ capacity_)那么插入前 size_ 必须已经比 capacity_ 大才会淘汰这意味着 capacity_ 为 0 时你插入第一个节点就得淘汰它自己逻辑也要相应调整。个人建议保持“先看是否已满满则先淘汰再插入”的顺序语义清晰也不容易出现 capacity_ 0 时的特殊问题。4.3 如果 key 不是 int 呢实际业务里 key 往往是字符串、用户 ID、URL 等。C 的unordered_map支持这些类型作为 key但哈希函数的选择会影响性能。比如字符串 key 直接用std::hashstd::string就够了但如果你的 key 是有结构的比如复合 ID最好自定义一个高性能哈希函数避免碰撞太多导致哈希表退化成链表。value 同理实际操作里很少直接存一个 int更多是存对象指针、共享指针或序列化后的字节流。如果 value 是昂贵对象比如一个大的图片解码结果你还要考虑 LRU 淘汰时析构成本必要时把对象放到独立的对象池里延迟释放。5. 并发访问下的 LRU单线程好写多线程才是真考验前面所有的代码默认都是单线程的。但线上服务几乎不可能单线程跑一个缓存你可能会遇到多线程读多线程写这时候就需要考虑线程安全。这里又有一堆选择题。5.1 最简单粗暴全域互斥锁直接给 get 和 put 包一个std::mutex或者std::shared_mutex读多写少时可提升性能。优点是正确性容易保证代码改动最小缺点是并发高时锁竞争严重缓存反而可能成为性能瓶颈。class ThreadSafeLRU { private: mutable std::shared_mutex mtx_; LRUCache lru_; public: int get(int key) { std::shared_lock lock(mtx_); return lru_.get(key); } void put(int key, int value) { std::unique_lock lock(mtx_); lru_.put(key, value); } };但注意即使是 get你也要修改链表顺序移动节点到头部所以它本质上不是“只读操作”。用shared_lock在并发读多的时候确实能减少读读互斥但写锁还是会串行化所有写操作。实测下来当 QPS 很高、且缓存命中率也很高时锁竞争依然明显。5.2 分段锁分片缓存把竞争摊开另一种思路是把整个缓存空间分成多个 shard每个 shard 是一棵独立的 LRU有自己的锁。通过 key 的哈希值决定它进入哪个 shard。比如 16 个 shard每个 shard 锁的竞争压力就降到原来的 1/16 左右。代价是每个 shard 的 capacity 要单独分配且整体容量控制变得复杂。这个方案适合缓存数据量大、并发又很高的场景很多分布式缓存的本地客户端就是这么做的。5.3 无锁化与 read-copy-update更深入一点可以用无锁数据结构比如boost::intrusive::list配合原子操作或者使用类似std::atomic的引用计数配合 RCU 思路。这种做法的实现复杂度很高而且对于“移动节点到头部”这种链式操作无锁化非常困难。我见过不少团队尝试过最后还是回到分片锁或者读写锁方案。作为经验之谈绝大多数业务场景下分片锁 合理的 capacity 设置已经足够无需为了追求无锁而牺牲可维护性。6. 缓存时间与过期LRU 和 TTL 怎么配合纯 LRU 只淘汰“最久未使用”不关心数据是否“已经过期”。但真实业务里缓存数据是有生命周期的比如验证码 5 分钟有效、排行榜 10 秒刷新一次。如果只靠 LRU一个很久没人访问但实际已过期的 key 会一直占着内存空间直到它被挤出 capacity。这不一定是问题但会浪费空间。所以工程上通常会给每个缓存项加上过期时间戳get 时检查是否过期过期则删除并返回 missput 时如果 key 已存在同时更新时间戳。有些方案还提供惰性删除访问时判断和定期删除后台线程扫表两种策略的结合。加 TTL 的 LRU 在链表节点里需要多存储一个expireTime字段。过期节点在链表里仍然是“旧数据”淘汰时优先淘汰链表尾部最久未使用如果尾部节点没过期但过期节点在中间惰性过期时遇到就删否则等它被访问时删除或者后台线程扫描。这是一个经典的“空间换准确性”的取舍如果你能容忍偶尔的过期延迟清理性能会更好。7. 从 LRU 到近似 LRURedis 的启发如果你用过 Redis会发现它的maxmemory-policy里有allkeys-lru和volatile-lru策略。但 Redis 并不是严格 LRU而是“近似 LRU”。原因很简单严格 LRU 需要在每次访问时都修改链表的相对顺序Redis 作为单线程事件循环如果每条命令都要做一次链表移动开销非常大。所以 Redis 的默认 LRU 实现是采样的在需要淘汰时随机采样若干个 key默认 5 个从中挑一个最久没访问的淘汰。它的实际效果在抽样数较多时已经很接近严格 LRU但开销小得多。这个思路对我们也有启发。如果你自己实现的缓存访问路径非常敏感完全可以用“采样 近似淘汰”替代“严格顺序维护”。例如把std::unordered_map里的数据按某种粗略的时间戳桶分组淘汰时只在随机选的桶里淘汰。牺牲一点命中率换回更好的 CPU 缓存友好性在高并发系统里其实是划算的买卖。8. 完整生产级实现参考自带统计、TTL 和线程安全下面我整合一个相对完整、可直接裁剪使用的 C LRU Cache 类。它包含线程安全、过期时间、命中/未命中统计、容量控制适合嵌入到服务端进程内使用。数据结构和上面的手工链表类似但这里我用 STL 方便展示真正的生产代码中你可以把 list 换成侵入式链表或者内存池改造。#include list #include unordered_map #include shared_mutex #include chrono #include cstdint template typename K, typename V class LRUCache { public: struct Entry { V value; std::chrono::steady_clock::time_point expire_at; int64_t access_count 0; // 可选的访问计数用于热数据分析 }; private: using Clock std::chrono::steady_clock; struct Node { K key; Entry data; }; using List std::listNode; using Iter typename List::iterator; List list_; std::unordered_mapK, Iter map_; mutable std::shared_mutex mtx_; const size_t capacity_; const std::chrono::milliseconds default_ttl_; int64_t hits_ 0; int64_t misses_ 0; bool isExpired(const Entry e) const { return e.expire_at Clock::now(); } void evictLocked() { while (list_.size() capacity_ !list_.empty()) { auto back list_.back(); map_.erase(back.key); list_.pop_back(); } } public: explicit LRUCache(size_t capacity, std::chrono::milliseconds ttl std::chrono::milliseconds(0)) : capacity_(capacity), default_ttl_(ttl) {} void put(const K key, const V value, std::chrono::milliseconds ttl {}) { std::unique_lock lock(mtx_); auto it map_.find(key); auto now Clock::now(); auto expire_at now (ttl.count() 0 ? ttl : default_ttl_); if (it ! map_.end()) { it-second-data.value value; it-second-data.expire_at expire_at; it-second-data.access_count; list_.splice(list_.begin(), list_, it-second); return; } evictLocked(); list_.emplace_front(Node{key, {value, expire_at, 1}}); map_[key] list_.begin(); } bool get(const K key, V out) { std::unique_lock lock(mtx_); // 因为要移动链表节点所以必须独占 auto it map_.find(key); if (it map_.end()) { misses_; return false; } if (isExpired(it-second-data)) { map_.erase(key); list_.erase(it-second); misses_; return false; } it-second-data.access_count; list_.splice(list_.begin(), list_, it-second); out it-second-data.value; hits_; return true; } void stats(double hit_rate, size_t size) const { std::shared_lock lock(mtx_); auto total hits_ misses_; hit_rate total ? (double)hits_ / total : 0.0; size list_.size(); } };这个类有几个点值得说TTL 为 0 表示永不过期判别逻辑是ttl.count() 0 ? ttl : default_ttl_这样调用方可以显式传 -1 来使用默认 TTL。过期清理策略这里是惰性过期get 时才删除。工程上如果缓存项很多且写入频繁可以再起一个后台线程定期淘汰过期项避免过期项堆积。统计信息访问次数可以用来辅助决策 capacity 是否需要调整或者定位热点数据。锁类型get 虽然看起来是读操作但因为要 splice 链表实际上要写顺序。这里用unique_lock牺牲读并发换取实现简单。如果你确实有很多读可以用“只读 get”和“write-back 迁移”分开设计或者采用近似 LRU 方案避免每次读都移动节点。9. 常见问题速查与避坑清单实践过程中无论你是面试手写还是项目落地总有一批反复出现的坑。我这里按经验整理一份速查表每一条都是我或者同事真实踩过的。问题现象根本原因解决方案内存持续增长但命中率却不高capacity 设得太大或过期数据没有被及时淘汰调小 capacity增加后台到期清理配合监控观察命中率曲线并发环境下 put 后数据丢失多个线程同时操作哈希表竞争破坏内部状态加锁或使用分片缓存降低锁粒度get 命中后顺序没更新导致热点数据被淘汰忘记把节点 moveToHead在 get、命中 put 分支里都要 move不能用 const 引用绕过手写版本节点内存泄漏删除节点后没有 delete析构函数遍历链表释放所有节点淘汰时释放移除节点使用 unordered_map 存 key-value 而不是节点迭代器更新顺序时需要再次查找复杂度退化哈希表直接存链表节点迭代器或指针删除迭代器后再使用该迭代器取数据迭代器失效先取数据再删除或使用 std::list 时注意 splice 不会失效erase 后必须重新查找TTL 过期但缓存仍返还旧数据只检查 LRU 顺序忘了检查过期时间get 里增加过期判断过期按 miss 处理大量 put 新 key 导致缓存抖动周期性热点迁移LRU 天然不擅长抗扫描考虑加“保护段”Segmented LRU或者使用 W-TinyLFU 等高级策略capacity0 时崩溃删尾节点时 list 为空且未判断 capacityput 时先判断 capacity0 直接返回或抛异常另外几个容易被忽视的工程细节不要用time(nullptr)作为间隔计时跨平台时精度不够且秒级粒度对短 TTL 不友好。用std::chrono::steady_clock或者monotonic clock避免用户改系统时间导致缓存全部抖动过期。不要在锁内做昂贵析构如果 value 是复杂对象析构可能触发 IO 或递归释放最好把要淘汰的节点从链表摘下来解锁后再析构。这个优化在延迟敏感场景立竿见影。哈希表的reserve不要省如果容量是 100000直接unordered_map.reserve(capacity * 2)避免频繁 rehash 带来抖动。考虑使用std::list::splice而不是“先擦除再插入”splice 只需要改指针不涉及节点构造析构成本更低。10. 压测与调参让数据帮你做决定很多新手实现完 LRU 后就直接上线这不太靠谱。我建议至少做一个简单的压测观察几个关键指标命中率预期中 80% 是底线90% 以上算健康。如果命中率过低加容量或者查一下访问分布是不是太分散。延迟毛刺看 p99 和 max。如果一个完整的 put 经常超过几毫秒说明锁竞争太剧烈或者淘汰时析构太慢。内存占用淘汰速度是否跟上写入速度如果内存持续上涨说明 TTL 清理或者容量淘汰没有生效。简单的测试方法用一个循环随机生成 key执行put/get记录耗时分布。也可以从录制一段真实业务访问日志回放压测缓存这样测出来的命中率最贴近线上。如果你测出命中率分布极度不均匀——比如前 1% 的 key 占据了 90% 的访问次数——那么纯 LRU 可能不是最优解可以考虑热点数据单独缓存或者用 LFU 的变体。LRU 适合“时间局部性”强的场景LFU 适合“频率局部性”强的场景。我自己见过一个推荐系统特征缓存用 LRU 命中率只有 70%换成 W-TinyLFU 后飙到 95% 以上内存容量反而减小了。所以 LRU 虽经典但不该是唯一选择。11. 扩展方向LRU 的变体和后续玩法写到这里如果你觉得 LRU 已经吃透了可以再往这几个方向探索LRU-K记录每个 key 最近 K 次访问时间当访问次数达到 K 次才进入热度队列避免单次偶发访问把数据误判为热点。Two Queue2Q把数据分为“新鲜队列”和“正式队列”。新数据先进入新鲜队列被再次访问才升级到正式队列防止扫描型数据冲垮缓存。W-TinyLFUCaffeine 缓存的核心策略用布隆过滤器近似统计频率结合 LRU 的局部性优势是目前本地缓存里综合表现非常亮眼的方案。基于 LRU 的分级淘汰把内存划分为冷热区热区用严格 LRU冷区用近似 LRU后台定期把冷区数据降级或淘汰。这种结构在搜索引擎、广告引擎里很常见。这些变体本质上都是在“热点识别”和“抗干扰”之间做权衡。理解了 LRU 的朴素思路再去上手这些变体会容易得多。最后分享一个小技巧。如果你需要在现有代码里快速加一层 LRU又不想手写链表可以使用boost::bimap或者boost::multi_index_container。后者可以用一个容器同时实现 key 索引和“最后访问时间”索引淘汰时按时间索引取尾部代码写起来非常简洁。代价是依赖 Boost且底层还是红黑树/哈希表混用性能未必比手写 listmap 强。所以简单场景手写复杂场景封装才是务实的选择。