前言
LRU 是 Least Recently Used
的简写,字面意思则是最近最少使用
。
通常用于缓存的淘汰策略实现,由于缓存的内存非常宝贵,所以需要根据某种规则来剔除数据保证内存不被撑满。
如常用的 Redis 就有以下几种策略:
策略 | 描述 |
---|---|
volatile-lru | 从已设置过期时间的数据集中挑选最近最少使用的数据淘汰 |
volatile-ttl | 从已设置过期时间的数据集中挑选将要过期的数据淘汰 |
volatile-random | 从已设置过期时间的数据集中任意选择数据淘汰 |
allkeys-lru | 从所有数据集中挑选最近最少使用的数据淘汰 |
allkeys-random | 从所有数据集中任意选择数据进行淘汰 |
no-envicition | 禁止驱逐数据 |
实现一
之前也有接触过一道面试题,大概需求是:
- 实现一个 LRU 缓存,当缓存数据达到 N 之后需要淘汰掉最近最少使用的数据。
- N 小时之内没有被访问的数据也需要淘汰掉。
以下是我的实现:
|
|
感兴趣的朋友可以直接从:
下载代码本地运行。
代码看着比较多,其实实现的思路还是比较简单:
- 采用了与 HashMap 一样的保存数据方式,只是自己手动实现了一个简易版。
- 内部采用了一个队列来保存每次写入的数据。
- 写入的时候判断缓存是否大于了阈值 N,如果满足则根据队列的 FIFO 特性将队列头的数据删除。因为队列头的数据肯定是最先放进去的。
- 再开启了一个守护线程用于判断最先放进去的数据是否超期(因为就算超期也是最先放进去的数据最有可能满足超期条件。)
- 设置为守护线程可以更好的表明其目的(最坏的情况下,如果是一个用户线程最终有可能导致程序不能正常退出,因为该线程一直在运行,守护线程则不会有这个情况。)
以上代码大体功能满足了,但是有一个致命问题。
就是最近最少使用没有满足,删除的数据都是最先放入的数据。
不过其中的
put get
流程算是一个简易的 HashMap 实现,可以对 HashMap 加深一些理解。
实现二
因此如何来实现一个完整的 LRU 缓存呢,这次不考虑过期时间的问题。
其实从上一个实现也能想到一些思路:
- 要记录最近最少使用,那至少需要一个有序的集合来保证写入的顺序。
- 在使用了数据之后能够更新它的顺序。
基于以上两点很容易想到一个常用的数据结构:链表。
- 每次写入数据时将数据放入链表头结点。
- 使用数据时候将数据移动到头结点。
- 缓存数量超过阈值时移除链表尾部数据。
因此有了以下实现:
|
|
实际效果,写入时:
|
|
使用时:
|
|
实现思路和上文提到的一致,说下重点:
- 数据是直接利用 HashMap 来存放的。
- 内部使用了一个双向链表来存放数据,所以有一个头结点 header,以及尾结点 tailer。
- 每次写入头结点,删除尾结点时都是依赖于 header tailer,如果看着比较懵建议自己实现一个链表熟悉下,或结合下文的对象关系图一起理解。
- 使用数据移动到链表头时,第一步是需要在双向链表中找到该节点。这里就体现出链表的问题了。查找效率很低,最差需要
O(N)
。之后依赖于当前节点进行移动。 - 在写入头结点时有判断链表大小等于 2 时需要删除初始化的头尾结点。这是因为初始化时候生成了两个双向节点,没有数据只是为了形成一个数据结构。当真实数据进来之后需要删除以方便后续的操作(这点可以继续优化)。
- 以上的所有操作都是线程不安全的,需要使用者自行控制。
下面是对象关系图:
初始化时
写入数据时
|
|
|
|
|
|
|
|
获取数据时
数据和上文一样:
|
|
通过以上几张图应该是很好理解数据是如何存放的了。
实现三
其实如果对 Java 的集合比较熟悉的话,会发现上文的结构和 LinkedHashMap 非常类似。
对此不太熟悉的朋友可以先了解下 LinkedHashMap 底层分析 。
所以我们完全可以借助于它来实现:
|
|
这次就比较简洁了,也就几行代码(具体的逻辑 LinkedHashMap 已经帮我们实现好了)
实际效果:
|
|
使用时:
|
|
LinkedHashMap 内部也有维护一个双向队列,在初始化时也会给定一个缓存大小的阈值。初始化时自定义是否需要删除最近不常使用的数据,如果是则会按照实现二中的方式管理数据。
其实主要代码就是重写了 LinkedHashMap 的 removeEldestEntry 方法:
|
|
它默认是返回 false,也就是不会管有没有超过阈值。
所以我们自定义大于了阈值时返回 true,这样 LinkedHashMap 就会帮我们删除最近最少使用的数据。
总结
以上就是对 LRU 缓存的实现,了解了这些至少在平时使用时可以知其所以然。
当然业界使用较多的还有 guava 的实现,并且它还支持多种过期策略。
号外
最近在总结一些 Java 相关的知识点,感兴趣的朋友可以一起维护。