LRU算法的Java实现

LRU算法的Java实现

27 2019-04-29 20:39:21

## LRU算法介绍
LRU算法全称Least Recently Used，也就是检查最近最少使用的数据的算法。这个算法通常使用在内存淘汰策略中，用于将不常用的数据转移出内存，将空间腾给最近更常用的“热点数据”。
初识这个算法忘了是在操作系统课还是计算机组成原理课上，其在Redis、Guava等工具中也有非常广泛的应用，甚至是最核心的思想之一。如果今后需要自己设计系统，即使不自己实现这个算法，LRU的思想也仍然是很重要的。

算法很简单，只需要将所有数据按使用时间排序，在需要筛选出LRU数据时，取排名靠后的即可。

## 算法实现
### Redis中的LRU
Redis中的数据量通常很庞大，如果每次对全量数据进行排序，势必将对服务吞吐量造成影响。因此，Redis在LRU淘汰部分key时，使用的是采样并计算近似LRU的，因此淘汰的是局部LRU数据。
**Redis内存淘汰策略**
`maxmemory-policy`配置可选参数：
- `noeviction`：不淘汰，内存超限后写命令会返回错误(如OOM, del命令除外)	
- `allkeys-lru`：所有key的LRU机制	在所有key中按照最近最少使用LRU原则剔除key，释放空间	
- `volatile-lru`：易失key的LRU	仅以设置过期时间key范围内的LRU(如均为设置过期时间，则不会淘汰)	
- `allkeys-random`：所有key随机淘汰	一视同仁，随机	
- `volatile-random`：易失Key的随机	仅设置过期时间key范围内的随机	
- `volatile-ttl`：易失key的TTL淘汰	按最小TTL的key优先淘汰

**Redis LRU的效果**
![](/img/pic/2019042920220188301_png_854_449_432300)
> 左上-理论LRU效果；右上-Redis3.0中的近似LRU(采样值10)；左下-Redis2.8中的近似LRU(采样值5)；右下-Redis3.0中的近似LRU(采样值5)
> 浅灰色-被淘汰；灰色-未被淘汰；绿色-新写入

补充说明：
- 达到设定的内存占用阈值时才会进行内存淘汰
- `maxmemory-samples`配置表示采样值，每次删除时采集的样本数——采样值10，表示从设置中定义的key中取10个key进行LRU计算并删除LRU的那个key
- Redis3.0中的算法建立了一个“候选池”，使得算法的效率和准确率都比2.8有提高，因为范围缩小了

结论：
- Redis3.0通过增加候选池提高了LRU准确性，效果比2.8好
- 采样值越高越结果越接近理论LRU（但是采样值越高效率低）
- 差不多采样率5就已经足够准确了，当然使用10已经基本接近理论LRU结果，但是损失效率

### Java中的LRU实现思路
根据LRU算法，在Java中实现需要这些条件：
- 底层数据使用双向链表，方便在链表的任意位置进行删除，在链表尾进行添加
这一点用单链表比较费劲，当然用数组等结构也都很费劲
当然双向链表在查找时也麻烦，但下述可以结合HashMap使用
- 需要将链表按照访问（使用）顺序排序
- 数据量超过一定阈值后，需要删除Least Recently Used数据

### Java中一个简单的LRUCache实现
对于上述的实现思路，`java.util.LinkedHashMap`已经实现了其中的99%，因此直接基于LinkedHashMap实现LRUCache非常简单。

**LinkedHashMap为LRUCache铺垫了什么**
- 构造方法提供了`accessOrder`选项，开启后会get方法会有额外操作保证链表顺序按访问顺序逆序排列
- 底层结构使用双向链表，查找可以使用HashMap的特点
- 覆盖了父类HashMap的`newNode`方法和`newTreeNode`方法，这两个方法在HashMap中只是创建Node用的，而在LinkedHashMap中不但创建Node，还将Node放在链表末尾
- 父类HashMap提供了3个void的Hook方法，方法没做任何事：
	- `afterNodeRemoval` 父类在remove一个集合中存在的元素后调用
	- `afterNodeInsertion` 父类在put、compute、merge后调用
	- `afterNodeAccess` 父类在replace、compute、merge等替换值后会调用，LinkedHashMap在get中开启accessOrder时调用，**究其根本是在对数据有操作时会调用**
- LinkedHashMap本质上还是复用HashMap的绝大部分功能，包括底层的Node<K, V>[]，因此能支持原本HashMap的功能
- 但是LinkedHashMap实现了父类HashMap的3个Hook方法：
	- `afterNodeRemoval` 实现链表的删除操作
	- `afterNodeInsertion` **并没有实现链表的插入操作**，但新添加了一个Hook方法`boolean removeEldestEntry`，当这个Hook方法返回true时，删除链表头的节点
	- `afterNodeAccess` 如前所述，开启accessOrder后会将被操作的节点放在链表末尾，保证链表顺序按访问顺序逆序排列
- 上一条3个方法是用来构建双向链表的，LinkedHashMap还覆盖了父类的3个方法：
	- `newNode` 在创建一个Node的同时，将Node添加到链表末尾
	- `newTreeNode` 创建TreeNode的同时，将Node添加到链表末尾
	- `get` 完成get功能的同时，如果accessOrder开启，会调用afterNodeAccess将Node移动到链表末尾
覆盖`newNode`和`newTreeNode`方法后，在put方法中调用的`newNode`和`newTreeNode`方法也就连带实现了链表的插入操作

**综上，我们可以了解到LinkedHashMap为什么能够轻松实现LRUCache**
1. 继承父类HashMap，拥有HashMap的功能，因此在查找一个节点时时间复杂度为O(1)，再加上链表是双向，做链表任意节点的删除工作就非常简单
2. 通过HashMap提供的3个Hook方法并覆盖了2个创建Node的方法，实现了自身链表的添加、删除工作，保证在不影响原本Array功能的前提下，正确完成自身的链表构建；这个过程实际上均是通过Hook方式增强原有功能的，因为原本的HashMap中创建节点其实也是使用的Hook方法
3. 提供属性`accessOrder`并实现了`afterNodeAccess`方法，因此能够根据访问或操作顺序将最近使用或最近插入的数据放在链表尾，越久没被使用的数据就越靠近链表头，实现了整个链表按照LRU的要求排序
4. **提供了一个Hook方法`boolean removeEldestEntry`，这个方法返回true时将会删除表头节点，即LRU中应当淘汰的节点，但是这个方法在LinkedHashMap中的实现永远返回false**

到这为止，实现一个LRUCache就很简单了：实现这个`removeEldestEntry`Hook方法，给LinkedHashMap设置一个阈值，那么超过这个阈值时就会进行LRU淘汰。

**网上随处可见的Java代码实现**
```java
	// 继承LinkedHashMap
	public class LRUCache<K, V> extends LinkedHashMap<K, V> {
		private final int MAX_CACHE_SIZE;

public LRUCache(int cacheSize) {
			// 使用构造方法 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
			// initialCapacity、loadFactor都不重要
			// accessOrder要设置为true，按访问排序
			super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
			MAX_CACHE_SIZE = cacheSize;
		}

@Override
		protected boolean removeEldestEntry(Map.Entry eldest) {
			// 超过阈值时返回true，进行LRU淘汰
			return size() > MAX_CACHE_SIZE;
		}

}
```

看似几行代码解决的事儿，其实只是冰山一角而已。

## 参考资料
[Using Redis as an LRU cache – Redis](https://redis.io/topics/lru-cache)