Go语言实现简单的LRU-K算法：语言学习中的高性能缓存设计-Golang-PHP中文网

go标准库container/list+map无法实现lru-k，因其仅维护单次访问时间戳，而lru-k需为每个key保存最近k次访问时间戳并按第k次访问时间排序淘汰，须用双层结构（主缓存+历史队列）配合最小堆与懒删除机制。

go语言实现简单的lru-k算法：语言学习中的高性能缓存设计

Go 标准库的 container/list + map 无法直接拼出可用的 LRU-K，因为 LRU-K 要求每个 key 必须维护最近 K 次访问时间戳（不是单次），且淘汰逻辑依赖「第 K 次访问时间」排序——这和纯 LRU 的单链表移动完全不是一回事。

常见错误是：给每个 key 加一个 accessCount int，每次 Get 就 count++，等 count >= K 就进主缓存。这看起来像 LRU-K，但实际漏掉了核心机制：

LRU-K 不是“升级版 LRU”，而是双层结构：一层管热数据（主 LRU 链表），一层管候选数据（FIFO 历史队列）。二者完全独立，靠晋升逻辑连接：

Go语言（Golang）1.26.0

Go语言（Golang）1.26.0版本官方下载，版本号 1.26.0，适合旧项目维护、兼容性测试和指定版本开发环境搭建。

下载

主缓存：*list.List + map[K]*list.Element，行为同标准 LRU：命中则 MoveToFront，满则删 Back()
历史队列：*list.List + map[K]*list.Element + map[K]int（计数器），只存 key，不存 value；Get 未命中主缓存时，往队尾 PushBack(key) 并 cnt[key]++
晋升触发点在 Get：若 cnt[key] >= K，则从历史队列中 Remove 对应节点，再调用 Put(key, value) 进主缓存（value 需业务层提供或提前缓存）
历史队列满时淘汰头部（Front()），不是尾部——它是 FIFO，先进先出，保证老的候选尽早释放

每次淘汰都扫一遍所有 key 的 history[0]（即第 K 次访问时间）是 O(N)，高并发下不可行。正确做法是维护一个最小堆：

堆元素为 {key string, kthTime time.Time}，按 kthTime 升序排列
每次 key 的历史时间戳更新（如新增一次访问并截断到 K 个），就把新 kthTime 推入堆
淘汰时循环 Pop 堆顶，检查其 kthTime 是否仍等于当前 key 的 history[0]；不一致说明已过期，丢弃并继续 Pop——这就是懒删除
Go 标准库 container/heap 要求实现 heap.Interface，重点写好 Less(i, j int) bool 和 Swap，其他可复用

LRU-K 比纯 LRU 多一层历史操作，锁乱套就会卡死或竞态。分层锁是底线：

主缓存读路径（Get 命中）：只用 mu.RLock()，保护 cache[key] 查找和 ll.MoveToFront()
主缓存写路径（Put / RemoveOldest）：用 mu.Lock()，但临界区只做链表重连 + map 增删，绝不含日志、HTTP、序列化等阻塞操作
历史队列：单独一把 historyMu sync.RWMutex，Get 未命中时先 Rlock 查 cnt，再 Lock 更新计数或移出队列
绝对避免：在 Get 中先 Unlock() 主锁，再去处理历史队列——中间窗口可能被另一个 goroutine 修改状态，导致晋升错乱或 double-remove