Guava Cache实现原理——LRU回收实现
系列文章：
Guava Cache实现原理——开篇&基本实现
Guava Cache实现原理——LRU回收实现
Guava Cache实现原理——引用类型回收
Guava Cache实现原理——高效回收技巧
目录
一、前言
无论我们做什么缓存策略，当我们考虑到如何对缓存项进行淘汰的时候，我们都会接触到LRU算法，即最近最少使用（访问）。比如在Redis中，当内存占用快达到阈值的时候，就有一个对应的allkeys-lru: 对所有的键都采取LRU淘；volatile-lru: 仅对设置了过期时间的键采取LRU淘汰。当然我们的主角的Guava Cache也会通过LRU算法来对缓存项进行淘汰，从而确保缓存不超过设置的阈值。
接下来我们就来看看什么是LRU算法？LRU怎么实现？Guava Cache的LRU怎么实现？
二、LRU的实现
1、什么是LRU
开始前，我们简单回顾下什么是LRU。LRU即Least Recently Used。即最近最少使用。也就是当需要清楚缓存项的时候，我们从最近使用（读写）最少缓存项开始清除。
2、LRU的实现-数组+时间戳
这是一种比较普通的实现，即将所有的元素存在数组中，然后每个元素还携带一个时间戳(最近访问时间)。这样就可以根据时间戳来找到最近访问最少的元素。其大概结构如下图。
该方案实现起来也比较简单，但是访问数据和查找最少使用元素的时间复杂度比较高，为O(n)。
3、LRU的实现-链表
这种实现也比较简单，只是需要对链表进行操作。所以相对上一种来说还是要复杂点。具体方案为：通过双向链表存储元素，然后每次访问某个元素就将元素移动到链表头部。这样链表头部的尾部的元素就是最近最少使用的元素。其大概结构如下图：
这种方式相对前一种来说，其获取最少访问元素的时候时间复杂度不再是O(n)，而是O(1)。但是其对元素的操作却和上一种方法一样都是O(n)。所以看起来这种方案也不是很好。
4、LRU的实现-链表+HashMap
这种方案看起来就比较复杂。但是说起来就比较简单了，哈哈哈。元素通过HashMap存储，同时元素之间又彼此构建成一条双向链表。其充分利用二者的优势高效的实现了LRU算法。是不是听起来很简单。为了偷懒，笔者就不画图了，感兴趣的同学可以自行网上搜索，嘿嘿。
该实现通过HashMap来存储元素，从而解决了读写元素的时间复杂度的问题。我们都知道HashMap的时间复杂度为O(1)。其通过双向链表又解决了查找最少使用元素的问题，其时间复杂度仍然为O(1)。
通过分析我们发现这种算法应该是LRU中最牛逼的算法了。也因为如此Java中的LinkedHashMap中的LRU也是通过这种方式实现的（不知道LinkedHashMap中使用的LRU的同学可以去面壁了）。本文的主角Guava Cache也是通过这种方式实现的LRU算法，但是在此基础上有一定的优化从而实现高性能。接来下我们将一起探讨Guava Cache的LRU如何实现的高效。
三、Guava Cache中LRU的高效实现
1、LRU的实现思想
到此我们已经知道了Guava Cache中是通过HashMap+双向链表的思想来实现的LRU了。通过前一篇文章的基本原理介绍我们又知道Guava Cache是通过ConcurrentHashMap的思想来实现高并发下读写。因此我们可以总结为Guava Cache中的LRU算法是通过ConcurrentHashMap+双向链表实现的。
2、LRU的具体实现
在Guava Cache的LRU实现中，它的双向链表并不是全局的(即这个那个Guava Cache只有一个)。而是每个Segment(ConcurrentHashMap中的概念)中都有。其中一共涉及到三个Queue其中包括：AccessQueue和WriteQueue，以及RecentQueue。其中AccessQueue和WriteQueue就是双向链表；而RecentQueue才是真正的Queue，它就是CocurrentLinkedQueue。接下来我们将分析Guava Cache是如何通过这三个Queue来实现的LRU。
A、AccessQueue和WriteQueue
这两个Queue（双向链表）是Guava Cache自己实现的一个比较简单的双向链表，为了性能，其设计成了非线程安全的。因此对这个两个Queue的操作就需要在获得了Segment的lock的场景下才能使用。
其中AccessQueue负责存储对元素的读取行为记录。而WriteAccess则负责对元素的写入行为进行记录。具体记录和我们上面探讨的链表实现LRU一样：访问（访问）的时候将最近访问移动到链表前面。
这里有个问题为什么要存在WriteQueue，上面我们不是说了Hash+链表的实现思想只需要一个链表就OK了，为什么这里还要一个WriteAccess呢？因为在Guava Cache中可以设置元素在写入后多久就被删除（即视为失效）。因此需要由WriteAccess来让元素根据写入时间排序（链表中每个节点页记录了元素的write时间）。
B、RecencyQueue
既然已经有了AccessQueue我们就能够知道元素的访问顺序了，从而很容易实现LRU算法了。为什么还需要RecentQueue这个CocurrentLinkedQueue呢？
因为上面我们已经提到到过，AccessQueue被设计成了线程不安全，因此必须要在获取到Segment中的Lock的时候才能访问。设想一下当我们访问元素的时候需要怎么操作才能够确保被访问的元素在AccessQueue中能够被移动到前面去？很明显为了实现着功能，我们必须在每次访问元素的时候都需要获取Segment中的Lock，然后才能够安全地将元素移动AccessQueue的前面去。这样功能我们是实现了，但是每次访问元素的时候我们都需要获取锁。这样就破坏了ConcurrentHashMap的分段锁的思想（ConcurrentHashMap分段锁思想中get是不需要获取锁的，这样才能够提供高效的读取性能），导致元素的读取变得很慢，性能很低。
因此为了确保Guava Cache的性能，它引入了RecencyQueue这个同步队列。在读取元素的时候，将所有被访问元素添加到RecencyQueue中。因为其是同步队列所以支持并发插入。这样就确保了高性能的读取能力。当在某些场景下获取到锁的时候，就再将RecencyQueue中的元素移动到AccessQueue中。
那么什么场景下能够获取到锁？主要有如下两种情况：
1、对缓存的修改（写入，新增，修改、删除）是必须要获取锁的
2、每次get元素的时候都会尝试获取一下锁(tryLock)，没有竞争的情况下就能够获取成功
如下图：每次get完元素之后都会执行一下如下代码（调用链：segment.get->postReadCleanup->cleanUp->runLockedCleanup）:
所以Guava Cache通过RecentQueue和AccessQueue的结合就实现了在确保get的高性能的场景下还能记录对元素的访问，从而实现LRU算法。
遗留问题：为什么WriteQueue没有一个对应的CocurrentLinkedQueue呢？
四、惯例
如果你对本文有任何疑问或者高见，欢迎添加公众号共同交流探讨（添加公众号可以获得”Java高级架构“上10G的视频和图文资料哦）。