缓存满了淘汰谁:LRU 的 O(1) 是用两套结构换来的
LRU 缓存是在容量满时淘汰“最久没有被访问”的那条数据,用最近性近似预测下一次还会不会被用到。它能在 O(1) 内完成查找与淘汰,靠的不是某个巧妙算法,而是哈希表与双向链表的分工:前者负责定位,后者负责顺序。最常见的错误是只在写入时调整顺序、忘了命中也要把节点移到队首,以及在更新已有键时误触发淘汰;另一个被忽略的事实是,严格的全局 LRU 在分布式缓存里几乎不存在,Redis 用的是采样近似,InnoDB 则用中点插入来抵抗全表扫描。读完你能手写一版正确的 LRU,讲清它为何会被顺序扫描打穿,并知道什么时候该换成 LRU-K、2Q 或 LFU。
是什么
LRU(Least Recently Used,最近最少使用)是一种缓存淘汰策略:容量满了以后,优先丢掉最久没有被访问的那一条。它背后的假设很朴素——刚被用过的东西,接下来被用到的概率更高;很久没人碰的东西,大概率也不会突然变热。这就是时间局部性,也是几乎所有缓存能成立的前提。
一句话直觉:书架只有一格空位,最近翻过的书放在最顺手的位置,要腾地方就从最里侧抽那本积灰的。
它出现的场景比想象中多:操作系统的页缓存、CPU 的 TLB、InnoDB 的 buffer pool、Redis 的 allkeys-lru、浏览器与 CDN 的 HTTP 缓存、服务里的本地对象缓存,以及面试里那道要求 get 和 put 都 O(1) 的题。需要先分清两个维度:LRU 管的是容量,满了才触发;TTL 管的是时间,到期就该失效。两者可以叠加,但不能互相替代。
核心原理
LRU 要同时满足两件事:按 key 找到数据,以及知道谁最旧、谁最新。任何单一结构都会在其中一半上退化成线性:
- 只用哈希表,查找是 O(1),但哈希表不维护顺序,要找最久未使用的键只能全表扫描。
- 只用链表,把节点移到队首是 O(1),但按 key 定位要先遍历,还是 O(n)。
- 用「时间戳 + 最小堆」,每次命中都要更新堆,代价是 O(log n);若改成惰性删除,堆里会堆积大量失效条目,内存反而失控。
所以标准答案是两套结构各管一半:哈希表存 key → 节点指针,负责 O(1) 定位;双向链表按访问时间排序,头部是最新、尾部是最旧,负责 O(1) 插入与摘除。哈希表回答“在哪”,链表回答“谁该走”。
具体操作只有两个:
get(key):哈希表命中后,把该节点从链表中间摘下来,挂到头部;未命中返回空。命中也要动链表,这是 LRU 与 FIFO 的分水岭。put(key, value):键已存在就更新值并移到头部;键不存在就新建节点挂到头部、写入哈希表,然后检查容量,超了就摘掉尾节点并从哈希表删除对应 key。
链表头尾各放一个哨兵节点,可以让“在头部插入”“摘掉尾节点”“删除中间节点”三种情况共用同一套指针操作,不必到处判空。下面用 Python 的 OrderedDict 演示同一套语义——它内部正是哈希表加双向链表,面试时则要求你手写这两个结构:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.od = OrderedDict()
def get(self, key: int) -> int:
if key not in self.od:
return -1
self.od.move_to_end(key) # 命中同样改变新旧顺序
return self.od[key]
def put(self, key: int, value: int) -> None:
if key in self.od:
self.od.move_to_end(key) # 更新不算新增,不能触发淘汰
self.od[key] = value
if len(self.od) > self.cap:
self.od.popitem(last=False) # 弹出最旧的那一端
复杂度是 O(1),但常数并不小:每次命中都要改六个指针,节点在内存里分散,指针追逐对 CPU 缓存不友好。这也是为什么高并发场景里,严格 LRU 往往第一个被牺牲。
如果连采样都觉得重,还有更省的一档:CLOCK(二次机会)算法。它把节点排成一个环,每个节点只留一个引用位,命中就置 1;需要淘汰时指针顺时针扫,遇到 1 就清零并放过,遇到 0 就选中。它用一位标记替代了完整的时间顺序,指针只走一圈就能找到近似最旧的节点,元数据开销和修改成本都比严格 LRU 低得多,操作系统页缓存里常见它的变体。
真实系统几乎都不做全局严格 LRU。Redis 在每个对象里存一个 24 位、精度约 1 秒的访问时钟,需要淘汰时随机采样若干 key(maxmemory-samples 默认 5),把空闲时间最长的挑出来,再放进候选池比较;采样越多越接近严格 LRU,CPU 也越贵。InnoDB 则把 buffer pool 分成 young 与 old 两段,新页一律从中间插入,只有在 old 区停留超过 innodb_old_blocks_time(默认 1000 毫秒)后被再次访问,才有资格进入 young 区。这两处设计的共同目的不是“更准”,而是更便宜、且不被一次性扫描冲垮。
常见考点与误区
- 误区一:只在
put时调整顺序。 面试官常追问“get里为什么要移动节点”。如果get不刷新最近性,链表顺序就退化成写入顺序,LRU 变成 FIFO,热点数据会被先写进来的冷数据挤掉。 - 误区二:更新已有键时也走淘汰逻辑。 典型翻车是容量为 1 时
put同一个 key,先判容量再覆盖,结果把自己淘汰掉。正确顺序是“存在则更新并前移,不存在才新建并检查容量”。 - 考点三:LRU 是不是最优淘汰策略。 不是。理论最优是 Belady 的 OPT,它需要预知未来,无法实现;LRU 只是用过去近似未来。它有一个著名的最坏情况:缓存能放 n 条,程序循环访问 n+1 条数据,每一轮都把下一轮要用的那条挤出去,命中率直接归零。这就是顺序扫描打穿缓存。
- 考点四:哈希表让复杂度严格为 O(1)。 平均是 O(1),最坏情况所有键碰撞到同一个桶,查找退化为 O(n)。工程上还要考虑扩容时的 rehash 停顿。
- 考点五:把 LRU 当成过期策略。 Redis 里被淘汰和已过期是两回事:过期键在被动删除或主动清扫之前仍然占内存;
volatile-lru只在设置了过期时间的键里挑,allkeys-lru才看全部键。用错策略会出现“明明有大量过期键,却在淘汰有用数据”。 - 考点六:以为分布式缓存也是 LRU。 每个节点各自维护自己的顺序,全局并不构成一个 LRU;再叠加一致性哈希和热点倾斜,“最久未使用”可能落在某个并不缺内存的节点上。客户端本地缓存与远端缓存两层叠加时,整体命中率也不能简单相加。
实践建议
- 按工作集定容量,而不是按数据总量。 先画命中率随容量变化的曲线,找拐点,再留 10%–20% 余量吸收突发。容量拍脑袋定大,既浪费内存,也让单次淘汰的回收收益变低。
- 给扫描流量留隔离通道。 离线导出、批量对账、全表遍历这类一次性的顺序访问,最容易把热数据冲走。可以让它们走独立缓存、限制并发,或者采用中点插入、2Q、LRU-K 这类带扫描抵抗的结构。
- 高并发下分片,别抢一把锁。
get会修改链表,所以读也是写,全局锁会成为瓶颈。按 key 哈希成多个独立 LRU 分片,各自加锁,能把竞争降到 1/N;代价是全局顺序不再严格,需要接受这一点。 - 监控不能只看命中率。 同时看淘汰速率、被淘汰对象的“最后一次访问距今多久”、以及回源 QPS。如果被淘汰的多数是刚写入的冷数据,说明策略或容量出了问题;如果淘汰的都是很久没用的,才说明 LRU 在正常工作。
- 缓存永远只是加速层。 任何 LRU 实现都可能在你需要的那一刻把数据丢掉,miss 必须有回源路径,并用请求合并(singleflight)挡住同一热点 key 的并发回源,避免击穿。TTL 上加随机抖动,可以防止大批键同时到期引发雪崩。
一句话总结:LRU 用哈希表买定位、用双向链表买顺序,O(1) 的代价是每次命中都要改写顺序。