Redis 8 已发布——并且是开源的
了解更多
最近最少使用 (LRU) 缓存基于最近访问的数据很可能在不久的将来再次被访问的原则运行。 通过首先驱逐最近最少访问的项目，LRU 缓存确保最相关的数据保留在缓存中。
LRU 缓存比其他缓存算法具有多个优势。 它在性能和内存使用之间提供了良好的平衡，使其适用于各种应用程序。 与其他可能基于频率或其他指标对数据进行优先级排序的算法不同，LRU 仅关注访问的及时性，使其 驱逐 决策具有可预测性和一致性。
由于其有效性，从数据库到 Web 浏览器，许多系统都采用 LRU 缓存。 例如，操作系统使用 LRU 算法来管理内存页面，确保最近访问的页面随时可用，而较少访问的页面则被换出。
LRU 缓存维护一个数据项列表，最近访问的项位于列表的前面，最近最少访问的项位于列表的后面。 当访问或添加数据项时，它会被移动到列表的前面。 如果缓存达到其容量并且需要驱逐一个项目以腾出空间，则位于后面的项目（即最近最少使用的项目）将被删除。
底层数据结构
实现 LRU 缓存通常涉及使用 数据结构 的组合。 一种常见的方法是使用双向链表来维护基于访问及时性的项目顺序，并使用哈希映射来实现对缓存中任何项目的恒定时间访问。 这种组合有效地创建了一种支持 LRU 缓存所需操作的数据结构。
驱逐过程
当缓存已满并且需要添加新项目时，将触发驱逐过程。 列表末尾的项目（表示最近最少使用的数据）将从列表和哈希映射中删除。 然后，新项目被添加到列表的前面，并且其引用（称为缓存键）与其相应的缓存值一起存储在哈希映射中。
优化和变体
虽然基本的 LRU 缓存算法很简单，但存在一些变体和优化来满足特定需求。 例如，一些实现可能使用“计数器”或“时间戳”方法来跟踪及时性，而另一些实现可能引入额外的层或段，以便更精细地控制驱逐决策。 同样重要的是要处理诸如缓存未命中之类的场景，即在缓存中找不到所请求的元素。
选择正确的数据结构
LRU 缓存实现的效率很大程度上取决于底层数据结构的选择。 通常使用双向链表和哈希映射的组合。 双向链表允许恒定时间的添加和删除，尤其是在处理列表的头部或尾部时。 哈希映射确保对缓存中任何元素的恒定时间访问。
Python 实现
在 Python 中，可以使用 `collections` 模块中的 `OrderedDict` 来实现 LRU 缓存。 `OrderedDict` 基于项目的插入或访问来维护项目的顺序，使其适用于 LRU 机制。 通过将其与容量检查配对，可以轻松地在缓存已满时驱逐最近最少使用的项目。
Java 实现
在 Java 中，可以使用 `LinkedHashMap` 的组合并通过覆盖其 `removeEldestEntry` 方法来实现 LRU 缓存。 在 `put` 和 `putAll` 方法之后调用此方法，并允许开发人员控制删除映射中最旧的条目。
JavaScript 实现
对于 JavaScript，可以使用内置的 `Map` 对象，该对象维护键的插入顺序。 通过跟踪映射的大小并使用 `Map.prototype.delete` 方法，开发人员可以管理最近最少使用的项目的驱逐。
可伸缩性的考虑因素
虽然 LRU 缓存的基本实现适用于许多应用程序，但在分布式系统或高流量场景中可能会出现可伸缩性考虑因素。 在这种情况下，开发人员可能会研究分布式缓存解决方案或探索 LRU 算法的变体，这些变体可以满足大规模环境的需求。
Web 浏览器
诸如 Chrome 和 Firefox 之类的 Web 浏览器采用 LRU 缓存来存储经常访问的网页。 这允许用户快速重新访问页面，而无需从服务器获取整个内容，从而增强了浏览体验并减少了延迟。
操作系统
操作系统使用 LRU 缓存进行内存管理，特别是在页面替换算法中。 当程序需要的内存页面多于物理内存中可用的内存页面时，操作系统会根据 LRU 原则决定要驱逐哪些页面，从而确保最近访问的页面保留在内存中。
内容分发网络 (CDN)
CDN 将 Web 内容分发到更靠近最终用户的服务器，它们利用 LRU 缓存来存储热门内容。 通过缓存经常访问的数据，CDN 可以更快地向用户提供内容，从而减少源服务器上的负载并提高网站性能。
数据库
数据库，尤其是那些处理大量数据的数据库，使用 LRU 缓存来存储频繁的查询结果。 这减少了访问底层存储系统以进行重复查询的需要，从而缩短了查询响应时间并优化了数据库性能。
移动应用程序
移动应用程序，尤其是那些需要离线访问或快速数据检索的应用程序，实现 LRU 缓存来存储经常访问的数据。 这确保用户可以访问应用程序的关键功能而不会延迟，即使在连接性较差的情况下也是如此。
过度依赖缓存
虽然缓存可以显着提高性能，但过度依赖缓存会导致向用户提供过时的数据。 在缓存数据和确保用户收到最新信息之间取得平衡至关重要。
未设置缓存驱逐策略
未能设置驱逐策略可能导致缓存已满，无法存储新数据。 这可能导致频繁的缓存未命中，从而抵消了缓存的好处。 实施驱逐策略（例如 LRU）可确保缓存保持有效。
忽略缓存大小限制
设置过大的缓存大小可能会消耗过多的系统资源，而设置过小的缓存大小可能会导致频繁的驱逐。 监控缓存性能并根据应用程序的需求调整大小至关重要。
不考虑线程安全
在多线程环境中，多个线程可能会同时访问缓存。 如果没有适当的同步机制，这可能会导致数据不一致。 实施线程安全的缓存机制可确保数据完整性。
最佳实践
为了最大限度地提高 LRU 缓存的优势，开发人员应定期监控缓存命中率和未命中率，根据系统资源和应用程序需求调整缓存大小，实施适当的驱逐策略并确保线程安全。 此外，为缓存数据设置适当的生存时间 (TTL) 值有助于提供相关且更新的数据。
缓存算法确定在需要空间来存储新数据时要从缓存中驱逐哪些项目。 虽然 LRU 缓存会驱逐最近最少使用的项目，但 其他算法 使用不同的驱逐标准。
先进先出 (FIFO)
FIFO 是一种简单的缓存算法，它驱逐缓存中最旧的项目。 它基于添加到缓存的第一个项目将是第一个被删除的项目的原则运行。 虽然简单，但 FIFO 并不总是考虑数据访问的相关性或频率。
最不常用 (LFU)
LFU 缓存驱逐最不经常访问的项目。 它维护一个项目被访问频率的计数，并在需要驱逐时删除计数最低的项目。 当访问模式一致时，此方法可能有效，但如果过去多次访问不常用的数据，则可能会保留这些数据。
随机替换 (RR)
顾名思义，RR 缓存在需要空间时从缓存中驱逐一个随机项目。 此算法很简单，不需要跟踪访问模式，但其驱逐选择可能无法预测。
对比分析
虽然 LRU 缓存因其关注最近的数据访问而在许多场景中有效，但根据具体的用例，其他算法可能更适合。例如，当某些数据项偶尔被访问，但仍然必须保留在缓存中时，LFU 可能会有所帮助。 另一方面，FIFO 可能适用于数据访问模式是顺序的场景。 选择正确的缓存算法需要了解应用程序的数据访问模式以及每种算法的权衡。
2Q 算法
2Q 算法是 LRU 缓存算法的增强版。它引入了两个队列：一个用于仅访问一次的页面 (Am)，另一个用于访问多次的页面 (A1)。 这种区分允许该算法通过优先考虑频繁访问的页面，同时考虑最近的访问模式，来更好地管理缓存逐出。
低 Inter-reference Recency Set (LIRS)
LIRS 是一种缓存算法，旨在在访问模式具有大型循环的场景中优于 LRU。 LIRS 区分了 recency 和 inter-reference recency，使其能够做出更明智的逐出决策。 这样，即使在具有挑战性的访问模式下，LIRS 也能保持较高的缓存命中率。
分段 LRU (SLRU)
SLRU 将缓存分为两个段：一个试用段和一个受保护段。 新条目进入试用段，如果再次被访问，它们将移动到受保护段。 这种方法允许 SLRU 在保持 LRU 优势的同时，也考虑访问频率。
自适应替换缓存 (ARC)
ARC 是一种自调整缓存算法，它根据观察到的访问模式动态调整其 LRU 和 LFU 组件的大小。 这种适应性使 ARC 能够在各种场景中表现良好，从而平衡了 recency 和访问频率。
高级缓存的注意事项
虽然基本的 LRU 缓存算法对于许多应用程序来说是有效的，但高级变体可以在特定场景中提供改进的性能。 但是，实现这些高级算法需要更深入地了解其机制以及它们所解决的特定挑战。 开发人员应评估其应用程序的访问模式，并选择最符合其需求的缓存算法。
