Golang 实现基于内存的缓存淘汰算法 LRU-K-Golang-PHP中文网

LRU-K需双链表+双map+独立计数器+懒删除最小堆+系统内存压力感知，缺一不可；因其本质是历史暂存层（FIFO）与服务层（LRU）的物理隔离，非简单LRU加计数。

golang 实现基于内存的缓存淘汰算法 lru-k

不能只靠 container/list + map 实现可用的 LRU-K，它需要两套隔离链表、独立计数器、带懒删除的最小堆，还要接入系统内存压力信号——缺一不可。

为什么标准 LRU 结构体直接改 K 值会失效

常见错误是把 LRU 的 MoveToFront 逻辑原样搬过来，再加个计数器就叫 LRU-K。这会导致：
• Get 一次就进主缓存，完全跳过晋升门槛
• 历史队列（history queue）用 list.Back() 淘汰，实际该用 Front()（它是 FIFO，不是 LRU）
• cnt 和 historyCache.mp 不同步：key 已从 history 链表中被 Remove，但计数器没删，后续再 Get 会误判晋升条件
根本原因是 LRU-K 不是“LRU + 计数”，而是两个逻辑层：未达标的历史暂存层（FIFO）、已达标的服务层（LRU），必须物理隔离。

如何组织双链表 + 双 map + 计数器

必须拆成两组互不干扰的结构：

主缓存层：ll *list.List + mp map[string]*list.Element，行为和标准 LRU 一致；Get 命中后调 ll.MoveToFront()
历史层：historyCache.ll *list.List + historyCache.mp map[string]*list.Element + historyCache.cnt map[string]int；Get 未命中时，先 PushBack 到 history 链表尾，再 cnt[key]++
晋升触发点只在 Get：若 cnt[key] >= k，则从 historyCache.ll 中 Remove 对应节点，再走一次 Put(key, value) 进主缓存
注意：historyCache.ll 的淘汰必须用 Front() —— 它保留最老访问记录，不是最近；而主缓存淘汰用 Back()

怎么高效选出「第 K 次访问最久」的 key

不能每次淘汰都遍历所有 key 并取 history[0]（O(N) 太重）。正确路径是：

Golang Uber Dig

使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等

下载

为每个 key 维护一个长度 ≤ K 的升序 accessHistory []time.Time，插入时 append(history, now)，超长则 history = history[1:]；这样 history[0] 就是「第 K 次访问时间」
用 container/heap 构建最小堆，元素为 {key string, kthTime time.Time}，按 kthTime 排序
每次 key 的 accessHistory 更新后，把新 kthTime 推入堆 —— 允许重复 key 入堆
淘汰时循环 Pop() 堆顶，检查其 kthTime 是否等于当前 key 的 history[0]；不等就丢弃（懒删除），直到拿到有效项

如何让 LRU-K 感知系统内存压力而非只看容量

runtime.ReadMemStats 只反映 Go 堆，对 OOM 几乎无预警能力。真实内存水位得看 OS 层：

Linux 下读 /proc/meminfo 中的 MemAvailable 字段（非 MemFree），用 os.ReadFile + 正则提取，避免依赖 cgo
macOS 下调 host_statistics syscall 获取 vm_statistics_data_t 中的 free_count
在 Put 开头加判断：if memCheckFn() （强制淘汰 30% 最久未用项）
启动后台 goroutine，每 2 秒采样一次 MemAvailable，动态调整 memThreshold（例如低于 512MB 时收紧阈值）
别在 Put 内实时计算 value 占用字节数——unsafe.Sizeof 不准，且拖慢热点路径