一、LRU 缓存是什么LRULeast Recently Used最近最少使用是一种经典的缓存淘汰策略。它的核心假设是如果一个数据最近被访问过那么它在将来被访问的概率也更高。因此当缓存容量达到上限、需要腾出空间时LRU 会优先淘汰那些最久未被访问的数据。这个假设并非凭空而来它源于程序访问的时间局部性Temporal Locality——程序倾向于重复访问最近使用过的数据。这一规律在 CPU 缓存、数据库缓冲池、Web 页面缓存、操作系统页面置换等场景中都被反复验证。一个标准的 LRU 缓存需要支持两个核心操作get(key)如果 key 存在返回对应的值并将该 key 标记为最近使用put(key, value)插入或更新 key如果容量已满先淘汰最久未使用的 key。关键的工程要求是这两个操作都必须在 O(1) 时间内完成。典型应用场景场景说明操作系统页置换内存页淘汰CPU 缓存硬件级近似 LRURedisallkeys-lru/volatile-lruMySQL Buffer Pool改进版分区 LRUNginx / CDN边缘缓存淘汰浏览器缓存页面资源淘汰二、LRU 的核心设计哈希表 双向链表LRU 要求get和put都是O(1)这决定了它必须组合两种数据结构哈希表key → 链表节点指针 O(1) 查找 双向链表维护访问顺序 O(1) 插入/删除 - 头部最近使用MRU - 尾部最久未使用LRU为什么必须是双向链表删除任意节点需要 O(1) 拿到前驱单链表删除需要遍历找前驱无法 O(1)为什么哈希表存指针而不是值需要 O(1) 定位链表节点直接操作存值的话移动节点还要同步更新哈希表代价更大三、样本代码分析给出的代码是一个基于unordered_map 自定义双向链表的 LRU 实现。整体思路正确但存在若干问题。3.1 类结构template typename Key, typename Value class LRUCacher { typedef struct Link { Link *prev, *next; } Link; typedef struct CacheNode : public Link { Key key; Value value; } CacheNode; unordered_mapKey, std::unique_ptrCacheNode _cache; int _capacity, _size; std::unique_ptrCacheNode head, tail; // ... };CacheNode继承自Link这样链表操作只需要操作Link*不需要关心具体存储的Key/Value类型——这是一种简化版的多态手法。代价是需要static_cast向下转型且要求Link必须是CacheNode的第一个基类或使用static_cast时的安全前提。这是典型的侵入式设计效率高但耦合紧。3.2put函数的逻辑void put(string key, string value) { // 情况 1key 已存在更新值并移到头部 if (auto it _cache.find(key); it ! _cache.end()) { it-second-value std::move(value); removeNode(it-second.get()); addNode_head(it-second.get()); return; } // 情况 2容量已满淘汰尾部 if (_size _capacity) { CacheNode *delnode static_castCacheNode *(tail-prev); if (delnode head.get()) throw CacheError(cache is in inconsistent state); removeNode(delnode); // _size-- _cache.erase(delnode-key); // unique_ptr 析构自动 delete 节点 } // 情况 3插入新节点 auto node std::make_uniqueCacheNode(Key(key), std::move(value)); CacheNode *raw node.get(); // 保存裸指针 _cache.emplace(std::move(key), std::move(node)); // node 被移走 addNode_head(raw); // 用 raw不能用 node.get() }这里有几个关键设计点值得展开第一raw的保存时机。std::move(node)本身不置空但emplace内部会移动构造unique_ptr移动之后node变成空指针。如果此时再调用node.get()得到的是nullptr。因此必须在emplace之前保存裸指针。这是一个非常隐蔽、但极易犯的错误——编译器不会报错运行时的表现是节点没有挂进链表数据在 map 里但链表里看不到。第二淘汰时不能手动delete。_cache的值是unique_ptrCacheNode_cache.erase(key)会析构这个unique_ptrunique_ptr的析构函数会 delete 节点。如果外面再写一句delete delnode;就是双重释放double free属于未定义行为通常会破坏堆元数据导致后续内存操作返回错误地址、链表指针被写乱。第三_size的维护。addNode_head内部_sizeremoveNode内部_size--。因此put在插入路径上不能再次_size否则计数会翻倍。更新路径上removeNodeaddNode_head的净变化为零是正确的。3.3 get 的实现std::optionalstd::string get(string key) { auto it _cache.find(key); if (it _cache.end()) return std::nullopt; else { CacheNode *node it-second.get(); removeNode(node); addNode_head(node); return node-value; } }四、LRU 缓存的优缺点4.1 优点实现简单、常数开销小。相比 LFU最不经常使用、ARC自适应替换缓存等策略LRU 只需要维护一个链表顺序每次访问固定做几次指针操作常数因子很小。符合程序的时间局部性。对大多数真实负载热点数据反复访问、近期数据更可能被再次使用LRU 的命中率接近最优策略。实现成熟、工程验证充分。从 Linux 页框回收、MySQL Buffer Pool、Redis 的近似 LRU到 CPU 各级缓存的替换策略LRU 及其变体在工业界被广泛使用了几十年。4.2 缺点对扫描型负载不友好。如果程序做一次全表扫描把所有数据依次读一遍LRU 会认为每个数据都是最近使用把原本的热点数据全部挤出去。这就是所谓的缓存污染cache pollution。数据库系统通常用 LRU-K 或 2Q 来对抗这个问题。命中率依赖访问分布。对幂律分布少数 key 被极度频繁访问的负载LFU 表现更好对循环访问模式依次访问 A、B、C、A、B、C…如果容量小于循环长度LRU 命中率会降到 0。每次访问都要修改链表存在并发瓶颈。在多线程环境下get操作会修改链表结构无法做到无锁读。这意味着即使全是读操作也需要加锁。这是 LRU 在高并发场景下最大的工程难题。每次访问都要修改链表存在并发瓶颈。在多线程环境下get操作会修改链表结构无法做到无锁读。这意味着即使全是读操作也需要加锁。这是 LRU 在高并发场景下最大的工程难题。五、扩展方向5.1 并发安全给 LRU 加锁是最直接的做法但一把大锁会把所有操作串行化。常见的优化方向分段锁把 key 哈希到 N 个分片每个分片一个独立的 LRU 锁。代价是全局淘汰策略不精确可能出现某个分片满了而其他分片空闲。读写锁 惰性更新读操作只更新访问计数不做链表调整后台线程定期重构顺序。Redis 的近似 LRU 就是这个思路不给每个 key 维护精确的链表位置而是记录最后一次访问时间戳淘汰时随机采样若干 key淘汰其中最久未使用的。无锁数据结构用 CAS 实现无锁双向链表但正确性极难保证实际工程中很少采用。5.2 淘汰策略的组合LRU-K记录每个 key 最近 K 次访问的时间只有第 K 次访问时才认为它是热的。能有效抵抗扫描污染。2Q两个队列一个 FIFO 队列存新数据一个 LRU 队列存热数据。新数据先进入 FIFO被再次访问才升级到 LRU。ARC自适应地在 LRU 和 LFU 之间平衡根据访问模式动态调整两个队列的大小。W-TinyLFUCaffeine 缓存库采用的策略用频率草图Count-Min Sketch过滤掉低频访问再用 LRU 管理高频数据。是目前工业界命中率最高的方案之一。5.3 内存管理优化对象池 / 内存池预分配一批节点避免每次put都调用new。既提升性能又减少内存碎片。侵入式容器把prev/next指针直接嵌进业务对象避免额外的节点封装和一次内存分配。开放寻址哈希表用连续数组存储提升遍历和查找的缓存命中率。5.4 功能扩展TTL过期时间为每个节点增加过期时间戳get时检查是否过期。Redis 就是 LRU TTL 的组合。持久化 / 快照把缓存状态序列化到磁盘重启后恢复。统计与监控命中率、淘汰次数、平均访问延迟等指标用于调优容量和策略。多级缓存L1 用 LRUL2 用更大的容量或更慢的存储形成层级结构。六、面试常见考点LRU 是算法面试和系统设计面试的高频题考察点从数据结构到工程权衡都有。以下是最常见的几类问题。6.1 手写实现题目设计并实现一个 LRU 缓存支持get和put要求 O(1) 时间复杂度。考察点是否能想到哈希表 双向链表的组合是否能正确处理边界容量为 1、更新已存在的 key、淘汰时的链表和 map 同步是否使用哨兵节点简化代码内存管理是否正确C 中是否用智能指针、是否 double free、是否内存泄漏。常见坑忘记在get时把节点移到头部淘汰时只从链表删了忘了从 map 删unique_ptr被 move 之后再取裸指针得到nullptr更新已存在的 key 时重复递增_size。6.2 为什么是 O(1)答哈希表提供 O(1) 的 key 定位双向链表在持有节点指针的前提下提供 O(1) 的删除和插入。两个操作合起来get和put都是常数时间。6.3 为什么用双向链表答删除节点需要访问其前驱以修改next指针。单向链表要从头遍历才能拿到前驱无法 O(1)。双向链表通过prev直接访问前驱因此删除是 O(1)。6.4 哨兵节点的作用答消除边界判断。没有哨兵时插入/删除需要分别处理链表为空、操作头节点、操作尾节点等特殊情况。引入哨兵后所有操作都发生在哨兵之间代码统一、不易出错。6.5 LRU 的缺点与替代方案答LRU 对扫描型负载不友好会污染缓存。替代方案包括 LFU对频繁访问更敏感但对新数据不友好、LRU-K用历史 K 次访问过滤一次性访问、2QFIFO LRU 两级、ARC自适应平衡 LRU 和 LFU、W-TinyLFU频率草图 LRU。选择哪种取决于访问分布特征。6.6 并发场景下如何优化答大锁 → 分段锁 → 近似 LRU如 Redis 的时间戳 随机采样→ 读写分离 后台重构。每种方案都有取舍分段锁牺牲全局精确性近似 LRU 牺牲命中率无锁实现牺牲开发复杂度。6.7 与其他缓存淘汰策略的对比策略优点缺点适用场景FIFO实现最简单不考虑访问频率访问模式均匀LRU符合时间局部性常数小怕扫描并发难做通用场景LFU对热点数据友好新数据易被饿死需维护频率幂律分布LRU-K抗扫描实现复杂需要维护 K 次历史数据库缓冲池ARC自适应实现复杂参数多通用但要求高6.8 系统设计延伸面试官常从 LRU 出发延伸到系统设计问题设计一个分布式缓存如何分片、如何保证一致性、如何处理节点故障设计一个带 TTL 的缓存过期 key 如何清理惰性删除 vs 定期删除设计一个高并发缓存分段锁、读写分离、无锁数据结构如何评估缓存效果命中率、平均延迟、淘汰率、内存占用。推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接
LRU缓存设计与实现
一、LRU 缓存是什么LRULeast Recently Used最近最少使用是一种经典的缓存淘汰策略。它的核心假设是如果一个数据最近被访问过那么它在将来被访问的概率也更高。因此当缓存容量达到上限、需要腾出空间时LRU 会优先淘汰那些最久未被访问的数据。这个假设并非凭空而来它源于程序访问的时间局部性Temporal Locality——程序倾向于重复访问最近使用过的数据。这一规律在 CPU 缓存、数据库缓冲池、Web 页面缓存、操作系统页面置换等场景中都被反复验证。一个标准的 LRU 缓存需要支持两个核心操作get(key)如果 key 存在返回对应的值并将该 key 标记为最近使用put(key, value)插入或更新 key如果容量已满先淘汰最久未使用的 key。关键的工程要求是这两个操作都必须在 O(1) 时间内完成。典型应用场景场景说明操作系统页置换内存页淘汰CPU 缓存硬件级近似 LRURedisallkeys-lru/volatile-lruMySQL Buffer Pool改进版分区 LRUNginx / CDN边缘缓存淘汰浏览器缓存页面资源淘汰二、LRU 的核心设计哈希表 双向链表LRU 要求get和put都是O(1)这决定了它必须组合两种数据结构哈希表key → 链表节点指针 O(1) 查找 双向链表维护访问顺序 O(1) 插入/删除 - 头部最近使用MRU - 尾部最久未使用LRU为什么必须是双向链表删除任意节点需要 O(1) 拿到前驱单链表删除需要遍历找前驱无法 O(1)为什么哈希表存指针而不是值需要 O(1) 定位链表节点直接操作存值的话移动节点还要同步更新哈希表代价更大三、样本代码分析给出的代码是一个基于unordered_map 自定义双向链表的 LRU 实现。整体思路正确但存在若干问题。3.1 类结构template typename Key, typename Value class LRUCacher { typedef struct Link { Link *prev, *next; } Link; typedef struct CacheNode : public Link { Key key; Value value; } CacheNode; unordered_mapKey, std::unique_ptrCacheNode _cache; int _capacity, _size; std::unique_ptrCacheNode head, tail; // ... };CacheNode继承自Link这样链表操作只需要操作Link*不需要关心具体存储的Key/Value类型——这是一种简化版的多态手法。代价是需要static_cast向下转型且要求Link必须是CacheNode的第一个基类或使用static_cast时的安全前提。这是典型的侵入式设计效率高但耦合紧。3.2put函数的逻辑void put(string key, string value) { // 情况 1key 已存在更新值并移到头部 if (auto it _cache.find(key); it ! _cache.end()) { it-second-value std::move(value); removeNode(it-second.get()); addNode_head(it-second.get()); return; } // 情况 2容量已满淘汰尾部 if (_size _capacity) { CacheNode *delnode static_castCacheNode *(tail-prev); if (delnode head.get()) throw CacheError(cache is in inconsistent state); removeNode(delnode); // _size-- _cache.erase(delnode-key); // unique_ptr 析构自动 delete 节点 } // 情况 3插入新节点 auto node std::make_uniqueCacheNode(Key(key), std::move(value)); CacheNode *raw node.get(); // 保存裸指针 _cache.emplace(std::move(key), std::move(node)); // node 被移走 addNode_head(raw); // 用 raw不能用 node.get() }这里有几个关键设计点值得展开第一raw的保存时机。std::move(node)本身不置空但emplace内部会移动构造unique_ptr移动之后node变成空指针。如果此时再调用node.get()得到的是nullptr。因此必须在emplace之前保存裸指针。这是一个非常隐蔽、但极易犯的错误——编译器不会报错运行时的表现是节点没有挂进链表数据在 map 里但链表里看不到。第二淘汰时不能手动delete。_cache的值是unique_ptrCacheNode_cache.erase(key)会析构这个unique_ptrunique_ptr的析构函数会 delete 节点。如果外面再写一句delete delnode;就是双重释放double free属于未定义行为通常会破坏堆元数据导致后续内存操作返回错误地址、链表指针被写乱。第三_size的维护。addNode_head内部_sizeremoveNode内部_size--。因此put在插入路径上不能再次_size否则计数会翻倍。更新路径上removeNodeaddNode_head的净变化为零是正确的。3.3 get 的实现std::optionalstd::string get(string key) { auto it _cache.find(key); if (it _cache.end()) return std::nullopt; else { CacheNode *node it-second.get(); removeNode(node); addNode_head(node); return node-value; } }四、LRU 缓存的优缺点4.1 优点实现简单、常数开销小。相比 LFU最不经常使用、ARC自适应替换缓存等策略LRU 只需要维护一个链表顺序每次访问固定做几次指针操作常数因子很小。符合程序的时间局部性。对大多数真实负载热点数据反复访问、近期数据更可能被再次使用LRU 的命中率接近最优策略。实现成熟、工程验证充分。从 Linux 页框回收、MySQL Buffer Pool、Redis 的近似 LRU到 CPU 各级缓存的替换策略LRU 及其变体在工业界被广泛使用了几十年。4.2 缺点对扫描型负载不友好。如果程序做一次全表扫描把所有数据依次读一遍LRU 会认为每个数据都是最近使用把原本的热点数据全部挤出去。这就是所谓的缓存污染cache pollution。数据库系统通常用 LRU-K 或 2Q 来对抗这个问题。命中率依赖访问分布。对幂律分布少数 key 被极度频繁访问的负载LFU 表现更好对循环访问模式依次访问 A、B、C、A、B、C…如果容量小于循环长度LRU 命中率会降到 0。每次访问都要修改链表存在并发瓶颈。在多线程环境下get操作会修改链表结构无法做到无锁读。这意味着即使全是读操作也需要加锁。这是 LRU 在高并发场景下最大的工程难题。每次访问都要修改链表存在并发瓶颈。在多线程环境下get操作会修改链表结构无法做到无锁读。这意味着即使全是读操作也需要加锁。这是 LRU 在高并发场景下最大的工程难题。五、扩展方向5.1 并发安全给 LRU 加锁是最直接的做法但一把大锁会把所有操作串行化。常见的优化方向分段锁把 key 哈希到 N 个分片每个分片一个独立的 LRU 锁。代价是全局淘汰策略不精确可能出现某个分片满了而其他分片空闲。读写锁 惰性更新读操作只更新访问计数不做链表调整后台线程定期重构顺序。Redis 的近似 LRU 就是这个思路不给每个 key 维护精确的链表位置而是记录最后一次访问时间戳淘汰时随机采样若干 key淘汰其中最久未使用的。无锁数据结构用 CAS 实现无锁双向链表但正确性极难保证实际工程中很少采用。5.2 淘汰策略的组合LRU-K记录每个 key 最近 K 次访问的时间只有第 K 次访问时才认为它是热的。能有效抵抗扫描污染。2Q两个队列一个 FIFO 队列存新数据一个 LRU 队列存热数据。新数据先进入 FIFO被再次访问才升级到 LRU。ARC自适应地在 LRU 和 LFU 之间平衡根据访问模式动态调整两个队列的大小。W-TinyLFUCaffeine 缓存库采用的策略用频率草图Count-Min Sketch过滤掉低频访问再用 LRU 管理高频数据。是目前工业界命中率最高的方案之一。5.3 内存管理优化对象池 / 内存池预分配一批节点避免每次put都调用new。既提升性能又减少内存碎片。侵入式容器把prev/next指针直接嵌进业务对象避免额外的节点封装和一次内存分配。开放寻址哈希表用连续数组存储提升遍历和查找的缓存命中率。5.4 功能扩展TTL过期时间为每个节点增加过期时间戳get时检查是否过期。Redis 就是 LRU TTL 的组合。持久化 / 快照把缓存状态序列化到磁盘重启后恢复。统计与监控命中率、淘汰次数、平均访问延迟等指标用于调优容量和策略。多级缓存L1 用 LRUL2 用更大的容量或更慢的存储形成层级结构。六、面试常见考点LRU 是算法面试和系统设计面试的高频题考察点从数据结构到工程权衡都有。以下是最常见的几类问题。6.1 手写实现题目设计并实现一个 LRU 缓存支持get和put要求 O(1) 时间复杂度。考察点是否能想到哈希表 双向链表的组合是否能正确处理边界容量为 1、更新已存在的 key、淘汰时的链表和 map 同步是否使用哨兵节点简化代码内存管理是否正确C 中是否用智能指针、是否 double free、是否内存泄漏。常见坑忘记在get时把节点移到头部淘汰时只从链表删了忘了从 map 删unique_ptr被 move 之后再取裸指针得到nullptr更新已存在的 key 时重复递增_size。6.2 为什么是 O(1)答哈希表提供 O(1) 的 key 定位双向链表在持有节点指针的前提下提供 O(1) 的删除和插入。两个操作合起来get和put都是常数时间。6.3 为什么用双向链表答删除节点需要访问其前驱以修改next指针。单向链表要从头遍历才能拿到前驱无法 O(1)。双向链表通过prev直接访问前驱因此删除是 O(1)。6.4 哨兵节点的作用答消除边界判断。没有哨兵时插入/删除需要分别处理链表为空、操作头节点、操作尾节点等特殊情况。引入哨兵后所有操作都发生在哨兵之间代码统一、不易出错。6.5 LRU 的缺点与替代方案答LRU 对扫描型负载不友好会污染缓存。替代方案包括 LFU对频繁访问更敏感但对新数据不友好、LRU-K用历史 K 次访问过滤一次性访问、2QFIFO LRU 两级、ARC自适应平衡 LRU 和 LFU、W-TinyLFU频率草图 LRU。选择哪种取决于访问分布特征。6.6 并发场景下如何优化答大锁 → 分段锁 → 近似 LRU如 Redis 的时间戳 随机采样→ 读写分离 后台重构。每种方案都有取舍分段锁牺牲全局精确性近似 LRU 牺牲命中率无锁实现牺牲开发复杂度。6.7 与其他缓存淘汰策略的对比策略优点缺点适用场景FIFO实现最简单不考虑访问频率访问模式均匀LRU符合时间局部性常数小怕扫描并发难做通用场景LFU对热点数据友好新数据易被饿死需维护频率幂律分布LRU-K抗扫描实现复杂需要维护 K 次历史数据库缓冲池ARC自适应实现复杂参数多通用但要求高6.8 系统设计延伸面试官常从 LRU 出发延伸到系统设计问题设计一个分布式缓存如何分片、如何保证一致性、如何处理节点故障设计一个带 TTL 的缓存过期 key 如何清理惰性删除 vs 定期删除设计一个高并发缓存分段锁、读写分离、无锁数据结构如何评估缓存效果命中率、平均延迟、淘汰率、内存占用。推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接
