LRU算法全称Least Recently Used,也就是检查最近最少使用的数据的算法。这个算法通常使用在内存淘汰策略中,用于将不常用的数据转移出内存,将空间腾给最近更常用的“热点数据”。
初识这个算法忘了是在操作系统课还是计算机组成原理课上,其在Redis、Guava等工具中也有非常广泛的应用,甚至是最核心的思想之一。如果今后需要自己设计系统,即使不自己实现这个算法,LRU的思想也仍然是很重要的。
算法很简单,只需要将所有数据按使用时间排序,在需要筛选出LRU数据时,取排名靠后的即可。
Redis中的数据量通常很庞大,如果每次对全量数据进行排序,势必将对服务吞吐量造成影响。因此,Redis在LRU淘汰部分key时,使用的是采样并计算近似LRU的,因此淘汰的是局部LRU数据。
maxmemory-policy
配置可选参数:
noeviction allkeys-lru volatile-lru allkeys-random volatile-random volatile-ttl
左上-理论LRU效果;右上-Redis3.0中的近似LRU(采样值10);左下-Redis2.8中的近似LRU(采样值5);右下-Redis3.0中的近似LRU(采样值5)
浅灰色-被淘汰;灰色-未被淘汰;绿色-新写入
补充说明:
maxmemory-samples
结论:
根据LRU算法,在Java中实现需要这些条件:
对于上述的实现思路, java.util.LinkedHashMap
已经实现了其中的99%,因此直接基于LinkedHashMap实现LRUCache非常简单。
accessOrder
选项,开启后会get方法会有额外操作保证链表顺序按访问顺序逆序排列 newNode
方法和 newTreeNode
方法,这两个方法在HashMap中只是创建Node用的,而在LinkedHashMap中不但创建Node,还将Node放在链表末尾 afterNodeRemoval
父类在remove一个集合中存在的元素后调用 afterNodeInsertion
父类在put、compute、merge后调用 afterNodeAccess
父类在replace、compute、merge等替换值后会调用,LinkedHashMap在get中开启accessOrder时调用, 究其根本是在对数据有操作时会调用 afterNodeRemoval
实现链表的删除操作 afterNodeInsertion
并没有实现链表的插入操作 ,但新添加了一个Hook方法 boolean removeEldestEntry
,当这个Hook方法返回true时,删除链表头的节点 afterNodeAccess
如前所述,开启accessOrder后会将被操作的节点放在链表末尾,保证链表顺序按访问顺序逆序排列 newNode
在创建一个Node的同时,将Node添加到链表末尾 newTreeNode
创建TreeNode的同时,将Node添加到链表末尾 get
完成get功能的同时,如果accessOrder开启,会调用afterNodeAccess将Node移动到链表末尾 覆盖 newNode
和 newTreeNode
方法后,在put方法中调用的 newNode
和 newTreeNode
方法也就连带实现了链表的插入操作 accessOrder
并实现了 afterNodeAccess
方法,因此能够根据访问或操作顺序将最近使用或最近插入的数据放在链表尾,越久没被使用的数据就越靠近链表头,实现了整个链表按照LRU的要求排序 boolean removeEldestEntry
,这个方法返回true时将会删除表头节点,即LRU中应当淘汰的节点,但是这个方法在LinkedHashMap中的实现永远返回false 到这为止,实现一个LRUCache就很简单了:实现这个 removeEldestEntry
Hook方法,给LinkedHashMap设置一个阈值,那么超过这个阈值时就会进行LRU淘汰。
// 继承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; } } 复制代码
看似几行代码解决的事儿,其实只是冰山一角而已。