LRU（最近最少使用）驱逐策略的概念起源可以追溯到 1960 年代的计算机架构研究，特别是作为一种页面替换算法，旨在通过保留频繁访问的内存页面来最小化昂贵的磁盘 I/O。在 Python 中，随着函数式编程范式的流行，标准化的高性能记忆化机制的需求变得尤为迫切，这促成了 PEP 3181 的接受和 functools.lru_cache 在 Python 3.2 中的引入。在此之前，开发者使用原始字典手动实现缓存，这虽然提供了快速查找但缺乏高效的驱逐能力，或者依赖于引入不必要的依赖的外部库。
在记忆化昂贵的函数调用时，缓存实现必须支持三个关键操作，且时间复杂度最优：插入新计算值、检索现有结果和在达到容量限制时驱逐过期条目。尽管 Python 内置的 dict 提供了 O(1) 的平均插入和查找时间，但没有机制来跟踪访问的最近性，迫使 O(n) 的扫描以识别最近最少使用的项进行驱逐。此外，标准字典无法在访问时有效地更新项目位置为“最近”，而不通过删除和重新插入，导致迭代器稳定性破坏并产生不必要的开销。
CPython 的 lru_cache 通过实现一个混合结构来解决这个问题，该结构结合了哈希表和循环双向链表，这两者均在 C 级别维护以提高性能。哈希表将计算的缓存键（参数的元组）映射到节点指针，从而实现 O(1) 的随机访问，而链表则严格维护从最新（头部）到最旧（尾部）的访问顺序。在缓存命中时，节点从其当前位置原子性地切断并移动到头部；在全缓存插入时，通过更新邻居指针以 O(1) 时间驱逐尾部节点，确保结构永远不会超过 maxsize。
from functools import lru_cache import time @lru_cache(maxsize=128) def compute_expensive(x, y): time.sleep(0.1) # 模拟 I/O return x ** y # 第一次调用：计算并填充缓存 start = time.time() result1 = compute_expensive(2, 20) print(f"未命中: {time.time() - start:.3f}s") # 第二次调用：从缓存中 O(1) 检索 start = time.time() result2 = compute_expensive(2, 20) print(f"命中: {time.time() - start:.6f}s") print(compute_expensive.cache_info())
一家高频交易分析平台需要实时将加密货币符号转换为标准的 ISO 代码，使用的外部微服务施加了每分钟 100 个请求和每个调用 300 毫秒延迟的严格速率限制。该系统每小时处理超过 10,000 个市场事件，其中 80% 的事件引用相同的 50 个流行交易对，创造了巨大的记忆化机会，但在没有边界缓存的情况下会存在内存耗尽的风险。开发团队需要一个能够最小化外部 API 调用的缓存策略，同时保证缓存数据的亚毫秒延迟和严格的内存占用限制。
团队首先考虑将 API 响应存储在一个简单的全局 dict 中，手动跟踪时间戳，并通过后台线程进行定期清理。这种方法实现复杂度最低且没有外部依赖，但在高交易量窗口期间会遭遇无限制的内存增长，并且需要 O(n) 的迭代来清除旧条目，导致每 60 秒的延迟峰值。此外，后台线程还引入了竞争条件，过期数据可能会在清理间隔与访问模式不良对齐时返回。
他们评估了部署一个专用的 Redis 实例，并利用 LRU 驱逐策略在多个分析工作者之间提供分布式缓存。尽管 Redis 提供了持久性、跨进程共享以及复杂的过期策略，但它引入了每次查找 2-5 毫秒的网络延迟和需要故障转移管理的操作复杂性，此外还增加了额外的基础设施成本。对于单节点微服务而言，过程隔离是可以接受的，因此网络延迟和维护负担超过了分布式缓存的好处。
最后，他们在 API 客户端方法上直接实现了 functools.lru_cache(maxsize=128, typed=True)，利用 CPython 的优化 C 实现来通过 GIL 处理并发。这个解决方案为热键提供了真正的 O(1) 访问，自动 LRU 驱逐而无需手动记账，并确保内部数据结构的线程安全，尽管它将缓存限制在了进程边界内。typed=True 参数确保 get_rate("BTC") 和 get_rate(123) 维护独立的缓存条目，防止类型强制错误。
团队选择 lru_cache 方法，因为这种进程边界性质与微服务架构相符合，而 128 条目的限制将内存使用保持在 20MB 以下，同时根据流量分析捕获了 96% 的重复查找。部署后，外部 API 调用减少了 94%，平均响应延迟从 280 毫秒减少到 0.8 毫秒（对于缓存条目），并且服务在 48 小时高负载测试期间保持了稳定的内存消耗。
lru_cache 如何处理不可哈希的参数类型，比如列表或字典，并且有哪些策略可以绕过这个限制？
当 lru_cache 遇到不可哈希的类型作为参数时，它会立即引发 TypeError，因为底层缓存键是通过对位置参数和关键字参数的元组进行哈希构建的，这要求所有组件都是不可变的。为了缓存处理可变数据的函数，候选人必须在包装函数中或在调用之前手动将参数转换为可哈希的表示——例如，将列表转换为元组或使用 json.dumps() 处理字典。或者，对于 self 可能不可哈希的方式缓存，必须确保实例实现了 __hash__ 方法，或者在类级别缓存函数，根据不可变标识符进行显式键提取。
当 maxsize 设置为 None 时，lru_cache 会发生什么架构变化，为什么这会禁用 LRU 跟踪机制？
将 maxsize=None 设置为 CPython 使用一个简单的 PyDictObject 而没有双向链表的开销，从而有效地禁用 LRU 跟踪并将缓存转换为一个无限增长的无界哈希映射。这种优化去除了与将节点移动到最近列表头部相关的指针操作成本，使在输入域严格有限的情况下的插入和查找稍微快一些。然而，候选人常常忽略的是，这种模式完全消除了自动驱逐的功能，如果应用于具有大或无限输入范围的函数，可能会导致内存耗尽，并且 cache_info() 会报告 maxsize=None，而 currsize 则无限增长。
为什么 lru_cache 的线程安全性不能保证在多线程环境中被包装函数执行的原子性？
虽然 CPython 的 lru_cache 实现持有 GIL 以防止内部哈希表和链表变更期间的结构损坏（例如，破裂的读取或丢失的更新），但在缓存未命中时实际执行包装函数时，GIL 是被释放的。这意味着如果两个线程同时调用一个带相同参数的缓存函数并未命中缓存，它们将会并发执行这个函数，从而可能导致竞态条件的发生，尤其当该函数修改共享状态或执行非幂等操作时。候选人经常错误地将数据结构的线程安全性与原子记忆化语义混淆，忘记了缓存只保证结果的存储是安全的，而不是结果计算是序列化的。