第1章 LRU缓存基础与容量泄漏定义

LRU（Least Recently Used，最近最少使用）是应用最广泛的缓存淘汰策略之一。理解其核心原理、容量边界以及泄漏形成机制，是构建可靠缓存系统的第一道防线。本章从三个维度拆解基础概念：淘汰算法如何工作、容量上限为何必须强制设定、以及泄漏的三种典型成因。

1.1 LRU淘汰算法原理

LRU 的核心假设是：如果一条数据最近被访问过，那么它在未来被再次访问的概率也更高。因此当缓存空间不足时，优先淘汰那些最长时间未被访问的数据项。

实现 LRU 的标准数据结构是 双向链表 + 哈希表 的组合，通常称为 LinkedHashMap 模式：

组件作用操作方式
双向链表维护所有 key 的访问先后顺序头部 = 最近使用，尾部 = 最久未使用
哈希表提供 O(1) 的键到链表节点的映射key → Node 指针
get(key)读取数据并刷新访问顺序命中 → 移动到链表头部；未命中 → 返回 -1
put(key, value)写入或更新数据已存在 → 更新值并移到头部；不存在 → 插入头部，超容量则淘汰尾部

每次 get 或 put 操作都会将被访问的节点提升至链表头部。经过连续访问后，链表尾部的节点即为最久未被使用的候选淘汰对象。

LRU 的「使用」既包括读操作（get），也包括写操作（put）。只要发生了访问，对应节点的生命周期就会被刷新。
LRU 淘汰算法完整流程 访问数据项 是否在缓存中？ 命中：移到链表头部 未命中 缓存是否已满？ 淘汰链表尾部数据 插入数据到链表头部 是 否 是 否 LRU 核心思想 当缓存达到容量上限时，淘汰最久未访问的数据项。 每次访问（读 / 写）都会将对应数据项提升到链表头部，表示最近被使用过。

1.2 缓存容量上限概念

缓存容量上限是指缓存实例允许存储的最大数据条目数或最大内存阈值。没有容量上限的缓存等同于内存泄漏——它会无节制地吞噬堆内存，直到触发 OOM。

容量上限通常通过以下两种方式定义：

  • 条目数上限（maxEntries）：LRU 缓存中最常见的限制方式，精确控制存储条目的数量。
  • 内存阈值（maxMemoryBytes）：以字节为单位限制缓存占用的总内存，适用于 value 大小不均的场景。

一个标准的 LRU 缓存初始化接口通常如下：

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity          # 硬性容量上限
        self.cache = {}                   # 哈希表：key → Node
        self.head = ListNode()            # 链表哑头
        self.tail = ListNode()            # 链表哑尾
        self.head.next = self.tail
        self.tail.prev = self.head
容量上限是 LRU 缓存的安全锁。任何不设上限的 LRU 实现，本质上都是一棵「成长的毒草」—— 表面上能缓存所有数据，实际上会在流量尖峰时拖垮整个进程。

1.3 泄漏的根本原因

缓存泄漏是指缓存占用的内存无法被正常回收，或者缓存中存储了大量不会再被访问的无效数据，导致有效容量持续下降。LRU 缓存中泄漏的根源可归纳为以下三类：

泄漏类型根本原因典型表现危害等级
无效引用缓存持有已从业务层删除的对象的强引用，GC 无法回收缓存条目数未超限，但内存占用持续上升高
容量膨胀容量上限设置过大、未设上限，或淘汰策略未正确触发缓存大小无限增长，最终 OOM严重
过期未回收TTL 过期数据未被及时清除，仍占用链表和哈希表位置缓存命中率下降，大量陈旧数据占据容量中

以下是一段存在 容量膨胀 问题的错误实现：

class LeakyLRUCache:
    def __init__(self):
        self.cache = {}    # ❌ 没有容量上限
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def put(self, key, value):
        # 每次 put 都直接插入，从不检查容量
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_head(node)      # 链表无限增长 → 内存泄漏
诊断缓存泄漏的快速方法：在测试环境中固定写入 N 条数据后，观察进程的 RES（常驻内存）是否稳定。如果内存持续增长且不收敛，几乎可以断定存在容量膨胀或无效引用问题。

三种泄漏类型的关联性：实际系统中，三类泄漏往往同时存在。过期未回收会加剧容量膨胀，而容量膨胀又会导致更多的无效引用滞留。因此，防泄漏设计必须从「上限控制、引用管理、过期清理」三个维度同时入手，后续章节将逐一展开。

本章小结：LRU 缓存的核心是「双向链表 + 哈希表」的有序淘汰机制；容量上限是防止泄漏的第一道闸门；泄漏的三大成因（无效引用、容量膨胀、过期未回收）必须从架构层面系统性地防御，而非靠零散的补丁修复。
← 上一章 📖 返回目录 下一章 →