导读缓存系统有一个绕不开的灵魂问题容量满了淘汰谁LRULeast Recently Used最近最少使用的答案是——淘汰最久没被访问的那个。听起来简单但要在 O(1) 时间内完成访问即更新淘汰最旧两个操作需要精心设计数据结构。MiniKV 的 Store 类给出了教科书式的答案std::list记录访问顺序、std::unordered_map存键值、Entry 内嵌 list 迭代器三个结构协作实现 O(1) 的查询、插入与淘汰。本文逐行拆解这个经典组合并回答一个关键问题为什么必须是 list mapvector 不行吗一、LRU 要解决什么问题假设我们有一个容量为 2 的缓存依次执行SET cold 1 → 缓存: [cold] SET hot 2 → 缓存: [hot, cold] hot 最近cold 次近 GET cold → 缓存: [cold, hot] 访问 cold它变成最近 SET new 3 → 容量满了淘汰谁 → 淘汰 hot最久未用关键洞察GET cold让 cold 从次近变成了最近——每一次访问都必须更新访问顺序。如果这个更新是 O(n) 的那缓存越大越慢性能无从谈起。所以 LRU 的实现核心是两个 O(1) 操作访问时 O(1) 移到最前淘汰时 O(1) 找到并删掉最旧。二、数据结构为什么是 list map 组合MiniKV 的 Store 类用三个结构协作// store.hclassStore{conststd::size_t capacity_;std::liststd::stringlru_;// ① 访问顺序链表std::unordered_mapstd::string,Entryentries_;// ② 键值哈希表structEntry{std::string value;std::optionalClock::time_pointexpires_at;// TTL第 3 篇展开std::liststd::string::iterator lru_position;// ③ ⭐ 链表迭代器};};三个结构的职责分工结构存什么解决什么问题lru_std::list所有 key按访问顺序排列头部最近谁最久没被访问的答案entries_unordered_mapkey → Entry含 valueO(1) 按 key 查值lru_positionlist 迭代器该 key 在链表中的位置⭐ 通过 map 找到 Entry 后 O(1) 定位链表节点lru_position是整个设计的点睛之笔。它让通过 key 找到 Entry和通过 Entry 找到链表位置两个方向都变成 O(1)——不需要为了找链表位置而 O(n) 遍历链表。三、O(1) 访问更新splice 的妙用每次 get/set 命中都要把该 key 移到链表头部。MiniKV 的实现voidStore::touch_locked(Entryentry){lru_.splice(lru_.begin(),lru_,entry.lru_position);entry.lru_positionlru_.begin();}std::list::splice的语义是把节点从当前链表剪切到目标位置——不复制、不移动数据纯指针操作O(1)。为什么选splice而不是删掉再插入因为 splice 有两个关键性质O(1)直接操作节点指针不遍历迭代器不失效splice 保持元素的身份entry.lru_position在剪切后仍然有效指向同一个节点只是位置变了这两点恰好是 LRU 频繁移动节点的刚需。四、O(1) 淘汰evict_if_needed_locked容量超限时的淘汰逻辑voidStore::evict_if_needed_locked(){while(entries_.size()capacity_){conststd::string victimlru_.back();// 最久未用的 key链表尾部lru_.pop_back();entries_.erase(victim);stats_.evictions;}}lru_.back()链表尾部就是最久未用的 key——O(1) 拿到pop_back()entries_.erase(victim)链表和哈希表同步删除——都是 O(1)注意是while而不是if正常情况下每次 set 只多 1 个键if就够但极端情况如构造后容量被调小可能一次需要淘汰多个while保证彻底清到容量内五、set 与 get 的完整流程set三种情况voidStore::set(std::string key,std::string value){std::lock_guardstd::mutexlock(mutex_);// 线程安全第4篇展开remove_if_expired_locked(key);// TTL 惰性清理第3篇constautofoundentries_.find(key);if(found!entries_.end()){// ① 已存在更新found-second.valuestd::move(value);found-second.expires_at.reset();// 重置 TTLtouch_locked(found-second);// 移到链表头return;}lru_.push_front(key);// ② 新 key链表头插入entries_.emplace(std::move(key),Entry{std::move(value),std::nullopt,lru_.begin()});evict_if_needed_locked();// ③ 超容量淘汰最旧}注意entries_.emplace(..., lru_.begin())——新 Entry 的lru_position初始化为链表头迭代器因为 push_front 刚把它放到了头部。get命中即 touchstd::optionalstd::stringStore::get(conststd::stringkey){std::lock_guardstd::mutexlock(mutex_);if(remove_if_expired_locked(key)){stats_.misses;returnstd::nullopt;}constautofoundentries_.find(key);if(foundentries_.end()){stats_.misses;returnstd::nullopt;}stats_.hits;touch_locked(found-second);// ⭐ 访问即更新 LRU 位置returnfound-second.value;}touch_locked在 get 里是关键——读取本身就会改变访问顺序这正是 LRU 与 FIFO 的本质区别。六、为什么是 list不是 vector这是面试必考题也是理解 LRU 实现的关键特性std::liststd::vector任意位置插入/删除O(1)指针操作O(n)搬移元素迭代器稳定性插入/删除后其他迭代器仍有效插入/删除可能使所有迭代器失效splice 剪切节点✅ 支持O(1)❌ 无此操作LRU 的核心操作是把链表中间的节点移到头部——如果lru_position存的是 vector 的迭代器下标每次移动后 vector 里其他元素的迭代器可能全部失效lru_position就全错了。list 的迭代器稳定性 splice 的 O(1) 剪切是 LRU 选择 list 的根本原因。七、测试验证StoreEvictsLeastRecentlyUsedMiniKV 自带的单元测试验证了完整逻辑tests/store_test.cppTEST(StoreEvictsLeastRecentlyUsed){minikv::Storestore(2);// 容量 2store.set(cold,1);// lru: [cold]store.set(hot,2);// lru: [hot, cold]store.get(cold);// touch → lru: [cold, hot]cold 变最近store.set(new,3);// 超容量 → 淘汰 hot最久未用EXPECT_TRUE(store.exists(cold));// cold 存活刚被访问过✓EXPECT_FALSE(store.exists(hot));// hot 被淘汰 ✓EXPECT_TRUE(store.exists(new));// new 已加入 ✓EXPECT_EQ(store.stats().evictions,std::uint64_t{1});}这个测试完美演示了 LRU 的核心语义get(cold)改变了淘汰对象——如果淘汰规则是 FIFO淘汰的会是 cold但因为 LRU 记住了 cold 刚被访问淘汰的是 hot。小结LRU 的核心需求访问时 O(1) 更新顺序淘汰时 O(1) 找到最旧list map 组合list 记访问顺序头最近尾最旧map 按 key O(1) 查 Entrylru_position点睛Entry 内嵌 list 迭代器让key→链表位置双向 O(1)splice 妙用O(1) 剪切节点且迭代器不失效是移到头部的正确工具while 而非 if淘汰逻辑要考虑一次淘汰多个的极端情况list vs vector迭代器稳定性 splice是 LRU 选 list 的根本原因下一篇预告《TTL 过期机制惰性删除的取舍》——Entry 里那个expires_at时间戳是 TTL过期时间的核心。MiniKV 采用惰性删除策略不主动扫描过期键而是在每次操作时顺手检查。这篇讲清楚惰性删除的原理、六条命令如何统一调用remove_if_expired_locked、以及它和 LRU 淘汰如何协作。参考文献与引用cppreference - std::list::spliceen.cppreference.com/w/cpp/container/list/splice——splice 的 O(1) 剪切与迭代器不失效的权威说明cppreference - std::listen.cppreference.com/w/cpp/container/list——list 迭代器稳定性保证下载完整源码如需整个工程的源码请在下面的链接下载https://download.csdn.net/download/ganxin7932508/93241722觉得有用点个关注持续获取 C 与系统编程技术干货。