科普|你应该知道的Java缓存进化史

背景

本文是上周去技术沙龙听了一下爱奇艺的 Java 缓存之路有感写出来的。先简单介绍一下爱奇艺的 Java 缓存道路的发展吧。

可以看见图中分为几个阶段：

• 第一阶段：数据同步加 Redis

通过消息队列进行数据同步至 Redis，然后 Java 应用直接去取缓存。这个阶段的优点是:由于是使用的分布式缓存，所以数据更新快。缺点也比较明显:依赖 Redis 的稳定性，一旦 Redis 挂了，整个缓存系统不可用，造成缓存雪崩，所有请求打到 DB。

• 第二，三阶段：JavaMap 到 Guava Cache

这个阶段使用进程内缓存作为一级缓存，Redis 作为二级。优点:不受外部系统影响，其他系统挂了，依然能使用。缺点:进程内缓存无法像分布式缓存那样做到实时更新。由于 Java 内存有限，必定缓存得设置大小，然后有些缓存会被淘汰，就会有命中率的问题。

• 第四阶段： Guava Cache 刷新

为了解决上面的问题，利用 Guava Cache 可以设置写后刷新时间，进行刷新。解决了一直不更新的问题，但是依然没有解决实时刷新。

• 第五阶段：外部缓存异步刷新

这个阶段扩展了 Guava Cache，利用 Redis 作为消息队列通知机制，通知其他 Java 应用程序进行刷新。

这里简单介绍一下爱奇艺缓存发展的五个阶段，当然还有一些其他的优化，比如 GC 调优，缓存穿透，缓存覆盖的一些优化等等。

原始社会 - 查库

上面说的是爱奇艺的一个进化线路，但是在大家的一般开发过程中，第一步一般都没有 Redis，而是直接查库。

在流量不大的时候，查数据库或者读取文件最为方便，也能完全满足我们的业务要求。

古代社会 - HashMap

当我们应用有一定流量之后或者查询数据库特别频繁，这个时候就可以祭出我们 Java 中自带的 HashMap 或者 ConcurrentHashMap。我们可以在代码中这么写：

1. public class CustomerService {
2. private HashMap<String,String> hashMap = new HashMap<>();
3. private CustomerMapper customerMapper;
4. public String getCustomer(String name){
5. String customer = hashMap.get(name);
6. if ( customer == null){
7. customer = customerMapper.get(name);
8. hashMap.put(name,customer);
9. }
10. return customer;
11. }
12. }

但是这样做就有个问题 HashMap 无法进行数据淘汰，内存会无限制的增长，所以 HashMap 很快也被淘汰了。

当然并不是说它完全就没用，就像我们古代社会也不是所有的东西都是过时的，比如我们中华名族的传统美德是永不过时的，就像这个 HashMap 一样的可以在某些场景下作为缓存，当不需要淘汰机制的时候，比如我们利用反射，如果我们每次都通过反射去搜索 Method,field，性能必定低效，这时我们用 HashMap 将其缓存起来，性能能提升很多。

近代社会 - LRUHashMap

在古代社会中难住我们的问题是无法进行数据淘汰，这样会导致我们内存无限膨胀，显然我们是不可以接受的。

有人就说我把一些数据给淘汰掉呗，这样不就对了，但是怎么淘汰呢？随机淘汰吗？当然不行，试想一下你刚把 A 装载进缓存，下一次要访问的时候就被淘汰了，那又会访问我们的数据库了，那我们要缓存干嘛呢？

所以聪明的人们就发明了几种淘汰算法，下面列举下常见的三种 FIFO,LRU,LFU（还有一些 ARC,MRU 感兴趣的可以自行搜索）:

• FIFO：先进先出，在这种淘汰算法中，先进入缓存的会先被淘汰。

这种可谓是最简单的了，但是会导致我们命中率很低。试想一下我们如果有个访问频率很高的数据是所有数据第一个访问的，而那些不是很高的是后面再访问的，那这样就会把我们的首个数据但是他的访问频率很高给挤出。

• LRU：最近最少使用算法。

在这种算法中避免了上面的问题，每次访问数据都会将其放在我们的队尾，如果需要淘汰数据，就只需要淘汰队首即可。

但是这个依然有个问题，如果有个数据在 1 个小时的前 59 分钟访问了 1 万次(可见这是个热点数据)，再后 1 分钟没有访问这个数据，但是有其他的数据访问，就导致了我们这个热点数据被淘汰。

• LFU：最近最少频率使用。

在这种算法中又对上面进行了优化，利用额外的空间记录每个数据的使用频率，然后选出频率最低进行淘汰。这样就避免了 LRU 不能处理时间段的问题。

上面列举了三种淘汰策略，对于这三种，实现成本是一个比一个高，同样的命中率也是一个比一个好。

而我们一般来说选择的方案居中即可，即实现成本不是太高，而命中率也还行的 LRU，如何实现一个 LRUMap 呢？我们可以通过继承 LinkedHashMap，重写 removeEldestEntry 方法，即可完成一个简单的 LRUMap。

1. ?class LRUMap extends LinkedHashMap {
2. private final int max;
3. private Object lock;
4. public LRUMap(int max, Object lock) {
5. //无需扩容
6. super((int) (max * 1.4f), 0.75f, true);
7. this.max = max;
8. this.lock = lock;
9. }
10. /**
11. * 重写LinkedHashMap的removeEldestEntry方法即可
12. * 在Put的时候判断，如果为true，就会删除最老的
13. * @param eldest
14. * @return
15. */
16. @Override
17. protected boolean removeEldestEntry(Map.Entry eldest) {
18. return size() > max;
19. }
20. public Object getValue(Object key) {
21. synchronized (lock) {
22. return get(key);
23. }
24. }
25. public void putValue(Object key, Object value) {
26. synchronized (lock) {
27. put(key, value);
28. }
29. }
30. public boolean removeValue(Object key) {
31. synchronized (lock) {
32. return remove(key) != null;
33. }
34. }
35. public boolean removeAll(){
36. clear();
37. return true;
38. }
39. }

在 LinkedHashMap 中维护了一个 entry(用来放 key 和 value 的对象)链表。在每一次 get 或者 put 的时候都会把插入的新 entry，或查询到的老 entry 放在我们链表末尾。

可以注意到我们在构造方法中，设置的大小特意设置到 max*1.4，在下面的 removeEldestEntry 方法中只需要 size>max 就淘汰，这样我们这个 map 永远也走不到扩容的逻辑了，通过重写 LinkedHashMap，几个简单的方法我们实现了我们的 LruMap。

现代社会 - Guava Cache

在近代社会中已经发明出来了 LRUMap，用来进行缓存数据的淘汰，但是有几个问题：

• 锁竞争严重，可以看见我的代码中，Lock 是全局锁，在方法级别上面的，当调用量较大时，性能必然会比较低。
• 不支持过期时间
• 不支持自动刷新

所以谷歌的大佬们对于这些问题，按捺不住了，发明了 Guava Cache，在 Guava Cache 中你可以如下面的代码一样，轻松使用：

1. ?public static void main(String[] args) throws ExecutionException {
2. LoadingCache<String, String> cache = CacheBuilder.newBuilder()
3. .maximumSize(100)
4. //写之后30ms过期
5. .expireAfterWrite(30L, TimeUnit.MILLISECONDS)
6. //访问之后30ms过期
7. .expireAfterAccess(30L, TimeUnit.MILLISECONDS)
8. //20ms之后刷新
9. .refreshAfterWrite(20L, TimeUnit.MILLISECONDS)
10. //开启weakKey key 当启动垃圾回收时，该缓存也被回收
11. .weakKeys()
12. .build(createCacheLoader());
13. System.out.println(cache.get("hello"));
14. cache.put("hello1", "我是hello1");
15. System.out.println(cache.get("hello1"));
16. cache.put("hello1", "我是hello2");
17. System.out.println(cache.get("hello1"));
18. }
19. public static com.google.common.cache.CacheLoader<String, String> createCacheLoader() {
20. return new com.google.common.cache.CacheLoader<String, String>() {
21. @Override
22. public String load(String key) throws Exception {
23. return key;
24. }
25. };
26. }

我将会从 Guava Cache 原理中，解释 Guava Cache 是如何解决 LRUMap 的几个问题的。

锁竞争

Guava Cache 采用了类似 ConcurrentHashMap 的思想，分段加锁，在每个段里面各自负责自己的淘汰的事情。

在 Guava 根据一定的算法进行分段，这里要说明的是，如果段太少那竞争依然很严重，如果段太多容易出现随机淘汰，比如大小为 100 的，给他分 100 个段，那也就是让每个数据都独占一个段，而每个段会自己处理淘汰的过程，所以会出现随机淘汰。在 Guava Cache 中通过如下代码，计算出应该如何分段。

1. int segmentShift = 0;
2. int segmentCount = 1;
3. while (segmentCount < concurrencyLevel && (!evictsBySize() || segmentCount * 20 <= maxWeight)) {
4. ++segmentShift;
5. segmentCount <<= 1;
6. }

上面 segmentCount 就是我们最后的分段数，其保证了每个段至少 10 个 entry。如果没有设置 concurrencyLevel 这个参数，那么默认就会是 4，最后分段数也最多为 4，例如我们 size 为 100，会分为 4 段，每段最大的 size 是 25。

在 Guava Cache 中对于写操作直接加锁，对于读操作，如果读取的数据没有过期，且已经加载就绪，不需要进行加锁，如果没有读到会再次加锁进行二次读，如果还没有需要进行缓存加载，也就是通过我们配置的 CacheLoader，我这里配置的是直接返回 Key，在业务中通常配置从数据库中查询。 如下图所示：

过期时间

相比于 LRUMap 多了两种过期时间，一个是写后多久过期 expireAfterWrite，一个是读后多久过期 expireAfterAccess。

很有意思的事情是，在 Guava Cache 中对于过期的 entry 并没有马上过期(也就是并没有后台线程一直在扫)，而是通过进行读写操作的时候进行过期处理，这样做的好处是避免后台线程扫描的时候进行全局加锁。看下面的代码：

1. public static void main(String[] args) throws ExecutionException, InterruptedException {
2. Cache<String, String> cache = CacheBuilder.newBuilder()
3. .maximumSize(100)
4. //写之后5s过期
5. .expireAfterWrite(5, TimeUnit.MILLISECONDS)
6. .concurrencyLevel(1)
7. .build();
8. cache.put("hello1", "我是hello1");
9. cache.put("hello2", "我是hello2");
10. cache.put("hello3", "我是hello3");
11. cache.put("hello4", "我是hello4");
12. //至少睡眠5ms
13. Thread.sleep(5);
14. System.out.println(cache.size());
15. cache.put("hello5", "我是hello5");
16. System.out.println(cache.size());
17. }
18. 输出:
19. 4
20. 1

从这个结果中我们知道，在 put 的时候才进行的过期处理。特别注意的是我上面 concurrencyLevel(1)这里将分段最大设置为 1，不然不会出现这个实验效果的，在上面一节中已经说过，我们是以段位单位进行过期处理。在每个 Segment 中维护了两个队列：

1. final Queue<ReferenceEntry<K, V>> writeQueue;
2. final Queue<ReferenceEntry<K, V>> accessQueue;

writeQueue 维护了写队列，队头代表着写得早的数据，队尾代表写得晚的数据。accessQueue 维护了访问队列，和 LRU 一样，用来进行访问时间的淘汰。如果当这个 Segment 超过最大容量，比如我们上面所说的 25，超过之后，就会把 accessQueue 这个队列的第一个元素进行淘汰。

1. void expireEntries(long now) {
2. drainRecencyQueue();
3. ReferenceEntry<K, V> e;
4. while ((e = writeQueue.peek()) != null && map.isExpired(e, now)) {
5. if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
6. throw new AssertionError();
7. }
8. }
9. while ((e = accessQueue.peek()) != null && map.isExpired(e, now)) {
10. if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
11. throw new AssertionError();
12. }
13. }
14. }

上面就是 Guava Cache 处理过期 entries 的过程，会对两个队列一次进行 peek 操作，如果过期就进行删除。

一般处理过期 entries 可以在我们的 put 操作的前后，或者读取数据时发现过期了，然后进行整个 segment 的过期处理，又或者进行二次读 lockedGetOrLoad 操作的时候调用。

1. void evictEntries(ReferenceEntry<K, V> newest) {
2. ///... 省略无用代码
3. while (totalWeight > maxSegmentWeight) {
4. ReferenceEntry<K, V> e = getNextEvictable();
5. if (!removeEntry(e, e.getHash(), RemovalCause.SIZE)) {
6. throw new AssertionError();
7. }
8. }
9. }
10. /**
11. **返回accessQueue的entry
12. **/
13. ReferenceEntry<K, V> getNextEvictable() {
14. for (ReferenceEntry<K, V> e : accessQueue) {
15. int weight = e.getValueReference().getWeight();
16. if (weight > 0) {
17. return e;
18. }
19. }
20. throw new AssertionError();
21. }

上面是我们驱逐 entry 的时候的代码，可以看见访问的是 accessQueue 对其队头进行驱逐。而驱逐策略一般是在对 segment 中的元素发生变化时进行调用，比如插入操作，更新操作，加载数据操作。

自动刷新

自动刷新操作，在 Guava Cache 中实现相对比较简单，直接通过查询，判断其是否满足刷新条件，进行刷新。

其他特性

在 Guava Cache 中还有一些其他特性：

虚引用

在 Guava Cache 中，key 和 value 都能进行虚引用的设定，在 segment 中有两个引用队列：

1. final @Nullable ReferenceQueue<K> keyReferenceQueue;
2. final @Nullable ReferenceQueue<V> valueReferenceQueue;

这两个队列用来记录被回收的引用，其中每个队列记录了每个被回收的 entry 的 hash，这样回收了之后通过这个队列中的 hash 值就能把以前的 entry 进行删除。

删除监听器

在 Guava Cache 中，当有数据被淘汰时，但是你不知道他到底是过期，还是被驱逐，还是因为虚引用的对象被回收？

这个时候你可以调用这个方法 removalListener(RemovalListener listener)添加监听器进行数据淘汰的监听，可以打日志或者一些其他处理，可以用来进行数据淘汰分析。

在 RemovalCause 记录了所有被淘汰的原因:被用户删除，被用户替代，过期，驱逐收集，由于大小淘汰。

Guava Cache 的总结

细细品读 Guava Cache 的源码总结下来，其实就是一个性能不错的，api 丰富的 LRU Map。爱奇艺的缓存的发展也是基于此之上，通过对 Guava Cache 的二次开发，让其可以进行 Java 应用服务之间的缓存更新。

走向未来-caffeine

Guava Cache 的功能的确是很强大，满足了绝大多数人的需求，但是其本质上还是 LRU 的一层封装，所以在众多其他较为优良的淘汰算法中就相形见绌了。而 Caffeine Cache 实现了 W-TinyLFU(LFU+LRU 算法的变种)。下面是不同算法的命中率的比较：

其中 Optimal 是最理想的命中率，LRU 和其他算法相比的确是个弟弟。而我们的 W-TinyLFU 是最接近理想命中率的。当然不仅仅是命中率 Caffeine 优于了 Guava Cache，在读写吞吐量上面也是完爆 Guava Cache。

这个时候你肯定会好奇为啥 Caffeine 这么牛逼呢？别着急下面慢慢给你道来。

W-TinyLFU

上面已经说过了传统的 LFU 是怎么一回事。在 LFU 中只要数据访问模式的概率分布随时间保持不变时，其命中率就能变得非常高。

这里我还是拿爱奇艺举例，比如有部新剧出来了，我们使用 LFU 给他缓存下来，这部新剧在这几天大概访问了几亿次，这个访问频率也在我们的 LFU 中记录了几亿次。

但是新剧总会过气的，比如一个月之后这个新剧的前几集其实已经过气了，但是他的访问量的确是太高了，其他的电视剧根本无法淘汰这个新剧，所以在这种模式下是有局限性。

所以各种 LFU 的变种出现了，基于时间周期进行衰减，或者在最近某个时间段内的频率。同样的 LFU 也会使用额外空间记录每一个数据访问的频率，即使数据没有在缓存中也需要记录，所以需要维护的额外空间很大。

可以试想我们对这个维护空间建立一个 HashMap，每个数据项都会存在这个 HashMap 中，当数据量特别大的时候，这个 HashMap 也会特别大。

再回到 LRU，我们的 LRU 也不是那么一无是处，LRU 可以很好的应对突发流量的情况，因为他不需要累计数据频率。

所以 W-TinyLFU 结合了 LRU 和 LFU，以及其他的算法的一些特点。

频率记录

首先要说到的就是频率记录的问题，我们要实现的目标是利用有限的空间可以记录随时间变化的访问频率。在 W-TinyLFU 中使用 Count-Min Sketch 记录我们的访问频率，而这个也是布隆过滤器的一种变种。如下图所示:：

如果需要记录一个值，那我们需要通过多种 hash 算法对其进行处理hash，然后在对应的 hash 算法的记录中+1，为什么需要多种 hash 算法呢？

由于这是一个压缩算法必定会出现冲突，比如我们建立一个 Long 的数组，通过计算出每个数据的 hash 的位置。比如张三和李四，他们俩有可能 hash 值都是相同，比如都是 1 那 Long[1] 这个位置就会增加相应的频率，张三访问 1 万次，李四访问 1 次那 Long[1] 这个位置就是 1 万零 1。

如果取李四的访问评率的时候就会取出是 1 万零 1，但是李四命名只访问了 1 次啊，为了解决这个问题，所以用了多个 hash 算法可以理解为 Long[][] 二维数组的一个概念，比如在第一个算法张三和李四冲突了，但是在第二个，第三个中很大的概率不冲突，比如一个算法大概有 1% 的概率冲突，那四个算法一起冲突的概率是 1% 的四次方。

通过这个模式，我们取李四的访问率的时候取所有算法中，李四访问最低频率的次数。所以他的名字叫 Count-Min Sketch。

这里和以前的做个对比，简单的举个例子：如果一个 HashMap 来记录这个频率，如果我有 100 个数据，那这个 HashMap 就得存储 100 个这个数据的访问频率。

哪怕我这个缓存的容量是 1，因为 LFU 的规则我必须全部记录这 100 个数据的访问频率。如果有更多的数据我就有记录更多的。

在 Count-Min Sketch 中，我这里直接说 Caffeine 中的实现吧(在 FrequencySketch 这个类中)，如果你的缓存大小是 100，他会生成一个 Long 数组大小是和 100 最接近的 2 的幂的数，也就是 128。

而这个数组将会记录我们的访问频率。在 Caffeine 中它规则频率最大为 15，15 的二进制位 1111，总共是 4 位，而 Long 型是 64 位。所以每个 Long 型可以放 16 种算法，但是 Caffeine 并没有这么做，只用了四种 hash 算法，每个 Long 型被分为四段，每段里面保存的是四个算法的频率。

这样做的好处是可以进一步减少 hash 冲突，原先 128 大小的 hash，就变成了 128X4。

一个Long的结构如下：

我们的 4 个段分为 A,B,C,D，在后面我也会这么叫它们。而每个段里面的四个算法我叫他 s1,s2,s3,s4。下面举个例子，如果要添加一个访问 50 的数字频率应该怎么做？我们这里用 size=100 来举例。

• 首先确定 50 这个 hash 是在哪个段里面，通过 hash & 3 必定能获得小于 4 的数字，假设 hash & 3=0，那就在 A 段。
• 对 50 的 hash 再用其他 hash 算法再做一次 hash，得到 Long 数组的位置。假设用 s1 算法得到 1，s2 算法得到 3，s3 算法得到 4，s4 算法得到 0。
• 然后在 Long[1] 的 A 段里面的 s1 位置进行+1，简称 1As1 加 1，然后在 3As2 加 1，在 4As3 加 1，在 0As4 加 1。

这个时候有人会质疑频率最大为 15 的这个是否太小？没关系在这个算法中，比如 size 等于 100，如果他全局提升了 1000 次就会全局除以 2 衰减，衰减之后也可以继续增加，这个算法再 W-TinyLFU 的论文中证明了其可以较好的适应时间段的访问频率。

读写性能

在 Guava Cache 中我们说过其读写操作中夹杂着过期时间的处理，也就是你在一次 put 操作中有可能还会做淘汰操作，所以其读写性能会受到一定影响。

可以看上面的图中，Caffeine 的确在读写操作上面完爆 Guava Cache。主要是因为在 Caffeine，对这些事件的操作是通过异步操作，它将事件提交至队列，这里的队列的数据结构是 RingBuffer。

然后会通过默认的 ForkJoinPool.commonPool()，或者自己配置线程池，进行取队列操作，然后在进行后续的淘汰，过期操作。

当然读写也是有不同的队列，在 Caffeine 中认为缓存读比写多很多，所以对于写操作是所有线程共享一个 Ringbuffer。

对于读操作比写操作更加频繁，进一步减少竞争，其为每个线程配备了一个 RingBuffer：

数据淘汰策略

在 Caffeine 所有的数据都在 ConcurrentHashMap 中，这个和 Guava Cache 不同，Guava Cache 是自己实现了个类似 ConcurrentHashMap 的结构。在 Caffeine 中有三个记录引用的 LRU 队列：

• Eden 队列：在 Caffeine 中规定只能为缓存容量的 %1，如果 size=100，那这个队列的有效大小就等于 1。这个队列中记录的是新到的数据，防止突发流量由于之前没有访问频率，而导致被淘汰。

比如有一部新剧上线，在最开始其实是没有访问频率的，防止上线之后被其他缓存淘汰出去，而加入这个区域。伊甸区，最舒服最安逸的区域，在这里很难被其他数据淘汰。

• Probation 队列：叫做缓刑队列，在这个队列就代表你的数据相对比较冷，马上就要被淘汰了。这个有效大小为 size 减去 eden 减去 protected。
• Protected 队列：在这个队列中，可以稍微放心一下了，你暂时不会被淘汰，但是别急，如果 Probation 队列没有数据了或者 Protected 数据满了，你也将会面临淘汰的尴尬局面。

当然想要变成这个队列，需要把 Probation 访问一次之后，就会提升为 Protected 队列。这个有效大小为(size 减去 eden) X 80% 如果 size =100，就会是 79。

这三个队列关系如下：

• 所有的新数据都会进入 Eden。
• Eden 满了，淘汰进入 Probation。
• 如果在 Probation 中访问了其中某个数据，则这个数据升级为 Protected。
• 如果 Protected 满了又会继续降级为 Probation。

对于发生数据淘汰的时候，会从 Probation 中进行淘汰，会把这个队列中的数据队头称为受害者，这个队头肯定是最早进入的，按照 LRU 队列的算法的话那它就应该被淘汰，但是在这里只能叫它受害者，这个队列是缓刑队列，代表马上要给它行刑了。

这里会取出队尾叫候选者，也叫攻击者。这里受害者会和攻击者做 PK，通过我们的 Count-Min Sketch 中的记录的频率数据有以下几个判断：

• 如果攻击者大于受害者，那么受害者就直接被淘汰。
• 如果攻击者<=5，那么直接淘汰攻击者。这个逻辑在他的注释中有解释: 他认为设置一个预热的门槛会让整体命中率更高。

• 其他情况，随机淘汰。

如何使用

对于熟悉 Guava 的玩家来说，如果担心有切换成本，那么你就多虑了， Caffeine 的 api 借鉴了 Guava 的 api，可以发现其基本一模一样。

1. public static void main(String[] args) {
2. Cache<String, String> cache = Caffeine.newBuilder()
3. .expireAfterWrite(1, TimeUnit.SECONDS)
4. .expireAfterAccess(1,TimeUnit.SECONDS)
5. .maximumSize(10)
6. .build();
7. cache.put("hello","hello");
8. }

顺便一提的是，越来越多的开源框架都放弃了 Guava Cache，比如 Spring5。在业务上我也曾经比较过 Guava Cache 和 Caffeine，最终选择了 Caffeine，在线上也有不错的效果。所以不用担心 Caffeine 不成熟，没人使用。

最后

本文主要讲述爱奇艺的缓存之路和本地缓存的一个发展历史(从古至今到未来），以及每一种缓存的实现基本原理。

当然要使用好缓存光是这些远远不够，比如本地缓存如何在其他地方更改了之后同步更新，分布式缓存，多级缓存等等。后面也会专门写一节介绍这个如何用好缓存。

对于 Guava Cache 和 Caffeine 的原理后面也会专门抽出时间写这两个的源码分析，如果感兴趣的朋友可以关注公众号第一时间查阅更新文章。