LRU 缓存淘汰策略1、基本介绍LRU全称 Least Recently Used即最近最少使用它是一种经典的缓存淘汰策略当缓存空间满了需要腾出位置放新数据时LRU 会优先淘汰那个最久没有被访问过的数据LRU 通常需要支持如下两种操作且要求高效一般是 O(1) 时间复杂度访问数据get 如果数据在缓存中把它标记为最近使用并移到最前面 如果不在返回空插入数据put 如果数据已存在更新值并移到最前面 如果不存在插入到最前面 如果插入后超出容量删除最后面最久未使用的那个数据为了在 O(1) 时间内完成查找、插入和删除LRU 通常结合如下两种数据结构哈希表实现 O(1) 的快速查找判断某个 key 是否在缓存中 双向链表维护访问顺序。链表头部是最近使用的尾部是最久未使用的。因为需要频繁移动节点所以用双向链表而不是单链表2、举例说明假设缓存容量为 3访问 A → 缓存[A]访问 B → 缓存[B, A]访问 C → 缓存[C, B, A]访问 A → A 被移到最前 → 缓存[A, C, B]插入 D → 容量满了淘汰最久未使用的 B → 缓存[D, A, C]3、应用场景CPU 缓存利用局部性原理保留最近使用的内存块数据库缓冲池例如MySQL 的 InnoDB 缓冲池用 LRU 的变体来管理内存页操作系统页面置换决定哪些内存页可以被换出Redis作为缓存淘汰策略之一浏览器 / HTTP 缓存决定哪些资源保留在本地4、优缺点1优点实现相对简单命中率在多数场景下表现不错符合最近使用过的东西更可能被再次使用的直觉2缺点对偶发性的批量操作不友好。例如一次性扫描大量数据会把原本的热点数据全部挤出去导致缓存命中率骤降。这被称为缓存污染实际系统中常用改进版例如LRU-K、2Q、LFU 等