如何实现一个支持过期时间的 LRU 缓存（Go 实现）？

如何实现一个支持过期时间的 LRU 缓存（Go 实现）？

先说一个核心结论：Go 标准库的 container/list 本身并不具备过期能力，你必须自己动手，组合定时清理或惰性检查机制。直接套用 sync.Map 加上独立的定时器，这条路走不通，很容易导致数据漏删或者重复触发，可靠性堪忧。

为什么不能只靠 container/list + map？

LRU 的核心机制，大家都很熟悉：双向链表负责 O(1) 的节点移动，哈希表负责 O(1) 的快速查找。但一旦引入过期时间，事情就复杂了——这等于在空间和访问顺序之外，硬生生加上了第三个维度：时间。问题恰恰出在这里：标准库的 container/list 节点没有预留时间戳字段，更不支持按时间维度进行批量淘汰。

那么，如果只在 Get 操作时才检查过期，会怎样？结果是，那些已经过期但从未被再次访问的数据，会像“幽灵”一样一直残留在内存里，形成脏数据。反过来，如果为了清理而全量扫描整个链表，LRU 引以为傲的 O(1) 时间复杂度就被彻底破坏了。这显然是个两难境地。

所以，实操层面必须把握好几个要点：

• 每个缓存项必须自带“死亡时间”，也就是 expireAt 字段，用 time.Time 或者 int64 类型的 Unix 毫秒时间戳都可以。
• 淘汰逻辑需要设计成两层：第一层是访问时的惰性清理（在 Get 或 Put 时，检查链表头部是否过期并弹出），第二层是后台 goroutine 的定期扫描（防止那些长期不被访问的数据成为“漏网之鱼”，导致内存泄漏）。
• 务必警惕一个常见的性能陷阱：为每个 key 单独启动一个 time.AfterFunc 定时器。想象一下，10万个 key 就是 10 万个 goroutine，系统资源瞬间就会被压垮，OOM 几乎是必然结局。

Get 和 Put 中如何做惰性过期检查？

关键在于，每次访问缓存之前，都先“瞄一眼”链表最头部的节点。这个节点是最久未被使用的，也最有可能已经过期。如果它真的超时了，就果断地从链表和 map 中一并移除，然后继续检查下一个头部节点，直到遇到一个有效的节点，或者链表被清空为止。

来看一段示例逻辑片段（注意，这不是完整代码）：

// 惰性清理头部过期项
for e := c.list.Front(); e != nil; {
    item := e.Value.(*cacheItem)
    if time.Now().After(item.expireAt) {
        c.list.Remove(e)
        delete(c.items, item.key)
        e = c.list.Front()
    } else {
        break // 头部已有效，停止清理
    }
}

这里有三个细节需要特别注意：

• 比较时间时，用 time.Now().After(item.expireAt) 比 item.expireAt.Before(time.Now()) 更符合直觉，虽然两者语义等价。
• 在清理循环内部，移除节点后必须重新获取链表头部（e = c.list.Front()），否则迭代器会失效，导致逻辑错误。
• 这个清理逻辑在 Put 操作时也必须调用。否则，新数据写入时，旧的过期项可能还卡在头部，影响缓存的有效性。

后台 goroutine 清理该用什么策略？

相比为每个 key 设置独立定时器这种“重型”方案，周期性的轮询扫描成本更低、也更可控，尤其适合高并发缓存场景。推荐的做法是：设定一个固定间隔（比如30秒），启动一个后台 goroutine，每次扫描时，从链表尾部（最近使用的）开始，向前最多检查 N 个节点（例如100个），避免单次扫描耗时过长，阻塞正常操作。

具体实施时，有几个建议：

• 使用 time.NewTicker 来驱动周期任务，而不是在循环里用 time.Sleep。前者精度更高，也更容易实现优雅关闭。
• 将扫描范围限制在链表末尾的一小部分节点。原因很简单：越靠近尾部的节点，越是近期被写入或访问的，它们过期的概率相对更高。链表头部的节点，则已经在惰性清理的覆盖范围内了。
• 后台扫描时，加上读锁（RWMutex.RLock）即可。因为扫描过程是只读的，不会修改数据结构，这样就不会影响正常的 Get 和 Put 操作的性能。
• 别忘了，在缓存的 Close() 方法里显式地调用 ticker.Stop()，这是防止 goroutine 泄漏的标准操作。

要不要用 sync.Map 替代手写 map + mutex？

答案是：不要。虽然 sync.Map 在读多写少的无锁场景下速度很快，但它有一个致命缺陷——不支持遍历。而无论是后台清理还是惰性清理，都需要遍历链表，并同步更新哈希映射中的对应条目。一旦使用了 sync.Map，你就很难安全地将链表节点和 map 中的条目进行原子性的关联操作。

正确的做法其实更经典：

• 使用普通的 map[interface{}]*list.Element。
• 所有对这个 map 的读写操作，都规规矩矩地用 sync.RWMutex 保护起来。
• 具体来说，Get 操作用读锁（RLock），Put 和 Delete 操作用写锁（Lock），后台清理也用读锁（RLock）。
• 注意，这里 map 存储的是 *list.Element（指针），而不是值的拷贝，所以从链表节点能直接定位到值，这是安全的。

最后，还有一个生产环境中极易被忽略的“暗坑”：时间精度与系统时钟跳变。容器迁移、NTP 时间同步校正都可能导致 time.Now() 获取的系统时间发生回跳。这样一来，原本尚未过期的缓存项，就可能被误判为过期而遭删除。应对策略有两种：一是使用基于单调时钟的 time.Since()（计算自程序启动后的偏移）；二是在存储 expireAt 时，不存绝对的时刻，而是存储一个相对的毫秒数。这才是保证缓存行为在复杂环境下依然确定性的关键所在。