Golang 实现高性能的 LRU-K 缓存淘汰算法-Golang-PHP中文网

LRU-K不能直接套用container/list，因其需双链表隔离主缓存与访问历史队列，并维护独立计数器，混用会导致晋升逻辑失效、历史队列膨胀及并发竞态。

为什么不用标准库 container/list 直接套 LRU-K？

container/list.list 本身不记录访问次数，也没有历史队列（history queue）支持；lru-k 的核心是“某 key 必须被访问 k 次才进主缓存”，这要求你维护两套独立结构：一个主 lru 链表（ll），一个 fifo 历史队列（historycache.ll），外加一个计数器 cnt map[string]int。直接复用 list.list 但只用一个链表，会把历史访问和主缓存混在一起，导致淘汰逻辑错乱——比如刚访问第 1 次就进了主链表头，后续根本无法判断是否达 k 次。

常见错误现象：

Put 后 Get 一次就命中，实际应至少访问 K 次才进主缓存
History 队列满时未淘汰最老 entry，导致计数器膨胀、内存泄漏
cnt 和 historyCache.mp 不同步：key 在 history 队列里，但 cnt 已被删或未增

怎么组织 LRU-K 的双层结构？

必须拆成两个物理隔离的链表 + 两套 map：

主缓存：ll *list.List + mp map[string]*list.Element，行为同标准 LRU：Get 命中则 MoveToFront，Put 满则 RemoveOldest
历史队列：historyCache.ll *list.List + historyCache.mp map[string]*list.Element + historyCache.cnt map[string]int，仅用于计数，不存 value；每次 Get 未命中主缓存时，往 history 队列尾部 Push，并更新 cnt[key]++
晋升逻辑放在 Get：若 cnt[key] >= k，则从 history 队列中 Remove 该节点，再调 Put(key, value) 进主缓存（注意：value 需业务层提供或提前缓存）

关键点：historyCache.ll 是 FIFO，不是 LRU；它只管“谁先进来”，不管“谁最近用”。所以淘汰用 Front() 而非 Back()。

Golang Naming

Go（Golang）命名规范 — 包括包、构造函数、结构体、接口、常量、枚举、错误、布尔值、接收器、getter/setter、函数等。

下载

并发安全下，锁怎么分层才不卡 Get？

LRU-K 比纯 LRU 多一层 history 访问，锁粒度更敏感。不能所有操作都用一把 sync.Mutex ——否则 Get 未命中时要查主缓存 → 查 history → 更新 cnt → 判晋升 → 可能 Put，全程阻塞其他请求。

主缓存读（Get 命中路径）：用 sync.RWMutex.RLock()，只保护 mp 查找和 ll.MoveToFront()
主缓存写（Put / RemoveOldest）：升级为 Lock()，但临界区只做链表指针重连 + mp 增删，绝不含 value 序列化、日志、回调
history 部分：单独一把 sync.RWMutex（比如叫 historyMu），因为它的读写频率和主缓存不一致；Get 未命中时先 historyMu.RLock() 查 cnt，再 Lock() 更新计数或移出队列
切忌：在 Get 中先 Unlock() 主锁，再去处理 history —— 这会导致竞态：A goroutine 判定未命中、解锁，B goroutine 此刻 Put 进了该 key，A 回来再晋升就重复写

怎么避免 history 队列无限增长？

historyCache 没有容量限制的话，cnt 和 historyCache.mp 会持续膨胀，尤其当大量冷 key 被试探性访问时。不能靠定时 goroutine 扫描清理 —— sync.Map 不支持安全遍历，而自己遍历 map 加锁又影响性能。

实操建议：给 historyCache.ll 设硬上限（比如 maxHistory = 1000），每次 PushBack 前检查 historyCache.ll.Len() >= maxHistory，超限则 Remove(historyCache.ll.Front()) 并同步删 historyCache.mp[key] 和 historyCache.cnt[key]
别用 len(historyCache.cnt) 做判断依据：map 长度 ≠ 队列长度，且 cnt 可能残留已出队 key
晋升后务必清空 history 状态：从 historyCache.ll 移除节点后，立刻 delete(historyCache.mp, key) 和 delete(historyCache.cnt, key)，否则下次同 key 访问会误用旧计数