LRU 淘汰Least recently used

优先淘汰最近最久未被使用的可淘汰对象。

核心约束: 访问操作更新最近使用顺序。
适用问题: 容量有限且存在时间局部性的缓存。
边界与取舍: 扫描负载可能污染缓存；引用保护与变体规则需要明确。

哈希表先定位 C，再将其从双向链表中摘除并移至表头。缓存满时淘汰表尾 D；已知节点时更新链接为常数时间。

常见操作#

n 为缓存容量；精确 LRU 用哈希表定位并用双向链表记录访问顺序。

操作	时间复杂度	条件与说明
命中并提升到最近使用端	期望 $O(1)$	哈希查找期望常数，已知链表节点移动为常数；并发同步另计。
插入 / 淘汰最久未使用项	期望摊还 $O(1)$	尾部摘除、哈希删除和头部插入；扩容或冲突可增加单次成本。

时间与空间#

时间复杂度: 查找 / 顺序更新通常期望 $O(1)$
辅助空间: $O(n)$ ，保存键索引和顺序链接

准确 LRU 每次命中也写共享顺序元数据。分片、采样 LRU 与 CLOCK 可降低维护成本，但淘汰语义不同。

工程中的应用#

2 个案例 · 附源码

vLLM·V1 / KV 块池v0.8.5 · V1

用内嵌双向链表管理空闲 KV 块

缓存块命中后可能需要从队列中间移除，双向链表让这一步保持常数时间。

链表 LRU 淘汰

附源码片段 · 内存管理

SGLang·RadixAttention70528762bf0800793dab10d1b51d40f21a0608ba · 2024-01-17

RadixAttention：共享请求前缀

用压缩前缀树组织 token 序列，让多轮对话和分支生成共享已有 KV。

Trie / Radix Tree LRU 淘汰

附源码片段 · 缓存与复用

基础原理参考资料

Java 21 · LinkedHashMapaccess-order 模式、LRU 缓存用途与基本性能前提。