当前位置：首页 > news >正文

LRU（1）

news 2025/5/31 14:05:45

LRU是"Least Recently Used"(最近最少使用)的缩写，它是一种常用的页面置换算法和缓存淘汰策略。当计算机系统的内存或缓存资源有限时，LRU算法根据的历史访问记录来决定哪些数据应该被保留在内存或缓存中，哪些被淘汰。其核心思想是“如果一个数据项在最近一段时间内没有被访问过，那再未来的一段时间内它被访问的可能型也比较小”。因此，当需要腾出空间给新的数据项时，LRU会选择哪些最长时间未被使用的数据项目进行淘汰。

页面访问序列	2	3	2	1	5	2	4	5	3
第1块	2/1	2/1	2/2	2/2	2/0	2/2	2/0	2/0	3/1
第2块		3/1	3/1	3/1	5/1	5/1	5/0	5/1	5/0
第3块				1/1	1/0	1/0	4/1	4/1	4/0
缺页否（*）	*	*		*	*		*		*
换出页面					3，1		1		2
					随机
换进页面	2	3		1	5		4		3

LRU工作原理

LRU可以通过多种方式来跟踪数据项的使用情况：

基于栈的方式：可以利用一个特殊的栈来保存当前正在使用的各个页面的页面号。每当进程访问某页面时，便将该页面号压入栈顶，其他的页面号往栈底移。这样，栈顶始终时最新被访问的页面编号，而栈底则时最近最久未访问的页面编号。
双向链表与哈希表结合：为了确保get和put方法的时间复杂度为O(1)，通常采用双向链表加哈希表的数据结构。哈希表用于快速查找是否再缓存中，而双向链表则用来维护元素的顺序，保证新插入或最近访问过的袁术位于链表头部，而最久未使用的袁术位于链表尾部。
数据访问记录：LRU 算法会为每个缓存的数据块维护一个访问时间戳或者访问顺序记录。每当一个数据块被访问（读或写操作）时，它的时间戳就会更新，或者它在访问顺序记录中的位置就会调整到最新（例如，移到队列的头部）。
缓存空间已满时的处理：
1. 当缓存空间已满，需要放入新的数据块时，LRU 算法会查找访问时间最早或者最久未被访问的数据块。
2. 例如，假设有一个缓存大小为 3 的数据缓存，里面已经存放了数据块 A、B、C。此时，如果要访问数据块 D，由于缓存已满，LRU 算法会检查 A、B、C 这三个数据块的访问顺序。假设 A 是最早被访问的（也就是最近最少使用的），那么 A 就会被从缓存中移除，D 则会被放入缓存，并且 D 会被标记为最新访问的数据块。
使用数据结构实现：
1. 一种常见的实现方式是使用链表和哈希表结合。链表用于维护数据块的访问顺序，新访问的数据块会被移到链表头部。哈希表用于快速查找数据块在链表中的位置，这样可以在 O (1) 时间复杂度内完成数据的访问和更新操作。
2. 比如，在一个简单的 LRU 缓存实现中，每次访问一个数据块，通过哈希表可以快速定位到链表中的节点，然后将该节点从原来的位置移除并插入到链表头部，以此来更新访问顺序。如果缓存已满，需要淘汰数据块时，直接删除链表尾部的数据块即可，因为链表尾部的数据块就是最近最少使用的数据块。

LRU 的应用场景

LRU 在计算机系统的缓存管理中应用广泛，如 CPU 缓存、数据库缓存等。在 Web 服务器的内容缓存中也经常使用，它可以帮助服务器快速响应客户端的请求。例如，当用户频繁访问某些网页时，这些网页的数据就会被保留在缓存中，而那些长时间无人访问的网页数据可能会被淘汰，从而提高缓存的命中率和系统的整体性能。

LRU优势：

LRU 算法能够很好地适应访问模式的变化。如果数据的访问频率发生改变，它会自动调整缓存中的数据，使得经常被访问的数据能够留在缓存中。并且它的实现相对简单，与其他一些复杂的缓存淘汰策略相比，它的时间复杂度和空间复杂度在很多情况下都比较容易控制，能够在性能和资源利用之间取得较好的平衡。

缓存系统

数据库查询缓存：

在企业级应用中，数据库查询操作通常是比较耗时的。例如，在一个电商系统中，商品信息的查询很频繁。通过使用 LRU 缓存，可以将最近查询的商品信息存储在内存中。当有新的查询请求时，首先在缓存中查找。如果缓存命中，就直接返回结果，避免了重复的数据库查询。
假设缓存大小为 100 条商品信息记录。当查询商品 A 时，LRU 算法会将商品 A 的信息缓存起来。如果缓存已满，并且又要缓存新的商品信息，它会根据 LRU 策略，淘汰最久未被查询的商品信息。这样可以大大提高系统的响应速度，减少数据库的负载。

Web 服务器内容缓存：

在 Web 服务器中，对于经常访问的网页内容，如 HTML 文件、图片、脚本等可以进行缓存。以一个新闻网站为例，热门新闻页面会被大量用户访问。服务器可以使用 LRU 缓存来存储这些热门页面的内容。
比如，一个 Web 服务器的缓存可以存储 1000 个网页内容。当用户请求一个网页时，服务器先检查 LRU 缓存。如果页面在缓存中，就直接返回缓存中的内容，提高了网页的加载速度。当缓存满了，LRU 算法会淘汰那些访问次数最少的网页内容，保证缓存中总是存储最有可能被访问的内容。

内存管理

Java 虚拟机（JVM）中的对象缓存：

在 JVM 内部，对于一些频繁创建和销毁的对象，可以使用 LRU 缓存来管理。例如，在一个图形处理应用中，会频繁创建和使用一些图形对象，像形状、颜色等对象。
假设 JVM 中有一个小型的对象缓存，大小为 50 个对象。这些图形对象可以被缓存起来。当需要再次使用某个图形对象时，首先在缓存中查找。如果缓存中有，就直接使用，避免了重新创建对象的开销。LRU 算法会确保缓存中的对象是最近最有可能被使用的，当缓存满时，会淘汰最久未被使用的对象。

分布式系统中的缓存

分布式缓存集群（如 Redis）：

在分布式系统中，多个节点可能会共享一个缓存集群。LRU 策略可以用于管理这些缓存节点中的数据。例如，在一个电商系统的分布式缓存中，不同的服务器节点可能会访问和缓存用户的购物车信息。
假设分布式缓存集群中有 10 个节点，每个节点都有自己的 LRU 缓存。当某个节点需要存储新的购物车信息，但缓存已满时，LRU 算法会在该节点的缓存中淘汰最久未被访问的购物车信息，从而保证缓存的高效利用，提高整个分布式系统的性能。这种应用场景可以有效避免缓存数据的不一致性和过期问题，使得分布式缓存能够更好地服务于多个节点的应用需求。

LRU局限性

Java中使用链表实现的LRU（Least Recently Used）缓存虽然在很多情况下能够有效地提高系统性能，但也存在一些局限性。这些局限性主要体现在内存占用、并发处理能力以及面对特定访问模式时的表现上。

内存占用

首先，基于链表和哈希表的数据结构实现LRU缓存需要额外的空间来存储指针信息。对于每个缓存项而言，不仅需要保存实际的数据内容，还需要维护前驱和后继节点的引用。当缓存容量较大时，这种额外的开销可能会变得显著，导致整体内存消耗增加。此外，频繁地进行插入和删除操作会导致内存分配和释放活动增多，进而可能引起内存碎片化问题。

并发性能

其次，在高并发场景下，链表操作可能会成为性能瓶颈。由于双向链表不是线程安全的，默认情况下多个线程同时访问或修改同一个LRU缓存实例时，必须采取适当的同步措施以确保数据一致性。然而，全局加锁的方式虽然简单直接，但在多线程环境下容易造成争用热点，影响吞吐量。因此，如果应用对并发度要求较高，则需要考虑更复杂的同步策略或者采用其他更适合并发环境的数据结构。

对特定访问模式的支持

最后，传统的LRU算法仅考虑了最近最少使用的特性，而忽略了某些数据可能被频繁访问的事实。这意味着一旦出现周期性的批量读取请求或者其他非典型的访问模式，LRU缓存有可能会因为“缓存污染”而导致命中率下降。例如，当发生偶发性的大量历史数据查询时，原本应该保留下来的热门数据可能会被新进来的冷门数据所替代，从而降低了缓存的有效性。

为了解决上述问题，业界提出了多种改进方案：

LRU-K：通过记录每个缓存项最近K次访问的时间戳，选择淘汰第K次访问时间最久远的那个元素。这种方法可以在一定程度上缓解短期突发流量对缓存的影响。
2Q (Two Queues)：该算法将缓存分为两个队列，分别存放短期访问频率较低与长期访问频率较高的项目。当某个项目从一个队列迁移到另一个队列时，表明它可能是经常使用的对象，有助于提升缓存命中率。
ARC (Adaptive Replacement Cache)：这是一种自适应替换策略，通过动态调整两个LRU列表（T1 和 T2）及相应的历史列表（B1 和 B2），使得算法能够在不同类型的访问模式下都表现出色。