LRU 缓存

相关源文件

• README.md
• solutions/object_oriented_design/lru_cache/__init__.py
• solutions/object_oriented_design/lru_cache/lru_cache.ipynb
• solutions/object_oriented_design/lru_cache/lru_cache.py

最近最少使用 (LRU) 缓存是一种数据结构，它在内存中维护有限数量的项，并在缓存达到其容量限制时丢弃最近最少使用的项。本文档介绍了 System Design Primer 中 LRU 缓存的实现，重点关注其面向对象设计和关键算法。有关通用缓存策略的信息，请参阅系统设计主题中的“缓存”部分。

目的和用例

LRU 缓存广泛应用于系统设计中，用于：

• 通过将频繁访问的数据保存在内存中来提高响应时间
• 减少后端系统（如数据库）的负载
• 平衡内存限制与性能要求

在本仓库中，LRU 缓存被实现为一个面向对象设计的实践示例，用于演示关键数据结构概念。

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb13-29

设计概览

LRU 缓存的实现结合了两种数据结构：

1. 一个哈希表（字典），用于按键进行 O(1) 查找
2. 一个双向链表，用于维护使用顺序（最近使用到最少使用）

这种组合允许进行高效操作，在检索和插入方面均达到 O(1) 时间复杂度。

架构图

此图显示了 LRU 缓存实现中三个主要类之间的关系。Cache 类协调整体功能，使用LinkedList 来维护顺序，并使用字典（lookup）来提供对缓存项的快速访问。

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb54-66 solutions/object_oriented_design/lru_cache/lru_cache.py1-30

数据结构组件

节点

Node 类表示缓存中的单个条目

• results：存储缓存数据
• prev：指向链表中前一个节点的引用
• next：指向链表中下一个节点的引用

这是一个标准的双向链表节点，增加了存储任意结果的功能。

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb55-60 solutions/object_oriented_design/lru_cache/lru_cache.py1-5

链表

LinkedList 类管理缓存项的顺序

• head：指向最近使用的项
• tail：指向最近最少使用的项

它提供了三个关键操作：

• move_to_front(node)：将现有节点移动到列表头部
• append_to_front(node)：将新节点添加到列表头部
• remove_from_tail()：从尾部移除最近最少使用的节点

这些操作共同维护了 LRU 顺序。

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb63-71 solutions/object_oriented_design/lru_cache/lru_cache.py8-21

缓存

Cache 类整合了哈希表和链表

• MAX_SIZE：缓存可以容纳的最大项数
• size：缓存中当前项数
• lookup：将查询键映射到节点的字典
• linked_list：跟踪使用顺序的 LinkedList

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb74-80 solutions/object_oriented_design/lru_cache/lru_cache.py24-30

操作

LRU 缓存提供两个主要操作：

获取操作

get(query) 方法从缓存中检索值

1. 在哈希表中查找查询（O(1)）
2. 如果未找到，返回 None
3. 如果找到，将节点移动到链表头部（表示最近使用过）
4. 返回缓存结果

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb82-91 solutions/object_oriented_design/lru_cache/lru_cache.py32-41

设置操作

set(results, query) 方法添加或更新缓存条目

1. 检查查询是否已存在于缓存中
2. 如果存在：
   • 更新缓存结果
   • 将节点移动到链表头部
3. 如果不存在：
   • 如果缓存已满，移除最近最少使用的项（从尾部）
   • 创建一个包含结果的新节点
   • 将节点添加到链表头部
   • 将查询-节点对添加到查找字典

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb93-116 solutions/object_oriented_design/lru_cache/lru_cache.py43-66

复杂度分析

LRU 缓存实现在其操作中实现了最优时间复杂度：

操作	时间复杂度	空间复杂度
get(query)	O(1)	O(1)
set(results, query)	O(1)	O(1)

总空间复杂度为 O(n)，其中 n 是缓存的最大大小。

实现细节

缓存淘汰处理

当缓存达到容量时，必须淘汰最近最少使用的项，以便为新条目腾出空间。这在set 方法中实现。

该实现首先从查找字典中移除条目，然后从链表尾部移除对应的节点。

来源：solutions/object_oriented_design/lru_cache/lru_cache.ipynb107-110 solutions/object_oriented_design/lru_cache/lru_cache.py57-60

使用示例

此实现中的 LRU 缓存旨在缓存网页查询结果。典型的使用模式可能如下：

实际考量

在实际系统中实现 LRU 缓存时，请考虑：

1. 线程安全：当前实现不是线程安全的。在多线程环境中，需要同步机制。
2. 淘汰策略变体：纯 LRU 可能并非总是最优的。LRU-K、2Q 或 SLRU 等变体可能更适合特定工作负载。
3. 监控和指标：在生产环境中，跟踪缓存命中率和淘汰模式有助于优化缓存大小和策略。
4. TTL（存活时间）：考虑为可能过期的缓存项添加过期策略。

总结

LRU 缓存实现结合了哈希表和双向链表，为检索和插入提供了高效的 O(1) 操作。当达到容量时，它通过淘汰最近最少使用的项来自动管理内存使用，这使其非常适合具有内存限制且访问模式表现出时间局部性的应用程序。