深刻解密来自将来的缓存 -Caffeine

1. 前言

读这篇文章之前心愿你能好好的浏览: 你应该晓得的缓存进化史 和 如何优雅的设计和应用缓存？。这两篇文章次要从一些实战下面去介绍如何去应用缓存。在这两篇文章中我都比拟举荐 Caffeine 这款本地缓存去代替你的 Guava Cache。本篇文章我将介绍 Caffeine 缓存的具体有哪些性能，以及外部的实现原理，让大家知其然，也要知其所以然。有人会问: 我不应用 Caffeine 这篇文章应该对我没啥用了，别着急，在 Caffeine 中的常识肯定会对你在其余代码设计方面有很大的帮忙。当然在介绍之前还是要贴一下他和其余缓存的一些比拟图:

能够看见 Caffeine 根本从各个维度都是相比于其余缓存都高，废话不多说，首先还是先看看如何应用吧。

1.1 如何应用

Caffeine 应用比较简单，API 和 Guava Cache 统一:

public static void main(String[] args) {Cache<String, String> cache = Caffeine.newBuilder()
                .expireAfterWrite(1, TimeUnit.SECONDS)
                .expireAfterAccess(1,TimeUnit.SECONDS)
                .maximumSize(10)
                .build();
        cache.put("hello","hello");
    }
复制代码

2.Caffeine 原理简介

2.1W-TinyLFU

传统的 LFU 受工夫周期的影响比拟大。所以各种 LFU 的变种呈现了，基于工夫周期进行衰减，或者在最近某个时间段内的频率。同样的 LFU 也会应用额定空间记录每一个数据拜访的频率，即便数据没有在缓存中也须要记录，所以须要保护的额定空间很大。

能够试想咱们对这个保护空间建设一个 hashMap，每个数据项都会存在这个 hashMap 中，当数据量特地大的时候，这个 hashMap 也会特地大。

再回到 LRU，咱们的 LRU 也不是那么一无是处，LRU 能够很好的应答突发流量的状况，因为他不须要累计数据频率。

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

2.1.1 频率记录

首先要说到的就是频率记录的问题，咱们要实现的指标是利用无限的空间能够记录随工夫变动的拜访频率。在 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 来举例。

1. 首先确定 50 这个 hash 是在哪个段外面，通过 hash & 3(3 的二进制是 11)必然能取得小于 4 的数字，假如 hash & 3=0，那就在 A 段。
2. 对 50 的 hash 再用其余 hash 算法再做一次 hash，失去 long 数组的地位，也就是在长度 128 数组中的地位。假如用 s1 算法失去 1，s2 算法失去 3，s3 算法失去 4，s4 算法失去 0。
3. 因为 S1 算法失去的是 1，所以在 long[1]的 A 段外面的 s1 地位进行 +1, 简称 1As1 加 1，而后在 3As2 加 1，在 4As3 加 1，在 0As4 加 1。

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

2.2 读写性能

在 guava cache 中咱们说过其读写操作中夹杂着过期工夫的解决，也就是你在一次 Put 操作中有可能还会做淘汰操作，所以其读写性能会受到肯定影响，能够看下面的图中，caffeine 确实在读写操作下面完爆 guava cache。次要是因为在 caffeine，对这些事件的操作是通过异步操作，他将事件提交至队列，这里的队列的数据结构是 RingBuffer, 不分明的能够看看这篇文章, 你应该晓得的高性能无锁队列 Disruptor。而后会通过默认的 ForkJoinPool.commonPool()，或者本人配置线程池，进行取队列操作，而后在进行后续的淘汰，过期操作。

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

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

2.3 数据淘汰策略

在 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。

这三个队列关系如下:

1. 所有的新数据都会进入 Eden。
2. Eden 满了，淘汰进入 Probation。
3. 如果在 Probation 中拜访了其中某个数据，则这个数据降级为 Protected。
4. 如果 Protected 满了又会持续降级为 Probation。

对于产生数据淘汰的时候，会从 Probation 中进行淘汰。会把这个队列中的数据队头称为受害者，这个队头必定是最早进入的，依照 LRU 队列的算法的话那他其实他就应该被淘汰，然而在这里只能叫他受害者，这个队列是缓刑队列，代表马上要给他行刑了。这里会取出队尾叫候选者，也叫攻击者。这里受害者会和攻击者皇城 PK 决出咱们应该被淘汰的。

通过咱们的 Count-Min Sketch 中的记录的频率数据有以下几个判断:

• 如果攻击者大于受害者，那么受害者就间接被淘汰。

• 如果攻击者 <=5，那么间接淘汰攻击者。这个逻辑在他的正文中有解释:

  他认为设置一个预热的门槛会让整体命中率更高。

• 其余状况，随机淘汰。

3.Caffeine 性能分析

在 Caffeine 中性能比拟多，上面来分析一下，这些 API 到底是如何失效的呢？

3.1 百花齐放 -Cache 工厂

在 Caffeine 中有个 LocalCacheFactory 类，他会依据你的配置进行具体 Cache 的创立。

能够看见他会依据你是否配置了过期工夫,remove 监听器等参数，来进行字符串的拼装，最初会依据字符串来生成具体的 Cache，这里的 Cache 太多了，作者的源码并没有间接写这部分代码，而是通过 Java Poet 进行代码的生成:

3.2 转瞬即逝 - 过期策略

在 Caffeine 中分为两种缓存，一个是有界缓存，一个是无界缓存，无界缓存不须要过期并且没有界线。在有界缓存中提供了三个过期 API:

• expireAfterWrite：代表着写了之后多久过期。
• expireAfterAccess: 代表着最初一次拜访了之后多久过期。
• expireAfter: 在 expireAfter 中须要本人实现 Expiry 接口，这个接口反对 create,update, 以及 access 了之后多久过期。留神这个 API 和后面两个 API 是互斥的。这里和后面两个 API 不同的是，须要你通知缓存框架，他应该在具体的某个工夫过期，也就是通过后面的重写 create,update, 以及 access 的办法，获取具体的过期工夫。

在 Caffeine 中有个 scheduleDrainBuffers 办法, 用来进行咱们的过期工作的调度，在咱们读写之后都会对其进行调用:

首先他会进行加锁，如果锁失败阐明有人曾经在执行调度了。他会应用默认的线程池 ForkJoinPool 或者自定义线程池, 这里的 drainBuffersTask 其实是 Caffeine 中 PerformCleanupTask。

在 performCleanUp 办法中再次进行加锁，避免其余线程进行清理操作。而后咱们进入到 maintenance 办法中:

能够看见外面有挺多办法的，其余办法稍后再探讨，这里咱们重点关注 expireEntries(), 也就是用来过期的办法:

• 首先获取以后工夫。
• 第二步, 进行 expireAfterAccess 的过期:

这里依据咱们的配置 evicts()办法为 true，所以会从三个队列都进行过期淘汰，下面曾经说过了这三个队列都是 LRU 队列，所以咱们的 expireAfterAccessEntries 办法，只须要把各个队列的头结点进行判断是否拜访过期而后进行剔除即可。

• 第三步, 是 expireAfterWrite:

能够看见这里依赖了一个队列 writeQrderDeque, 这个队列的数据是什么时候填充的呢？当然也是应用异步，具体方法在咱们下面的 draninWriteBuffer 中，他会将咱们之前放进 RingBuffer 的 Task 拿进去执行，其中也包含增加 writeQrderDeque。过期的策略很简略，间接循环弹出第一个判断其是否过期即可。

• 第四步，进行 expireVariableEntries 过期:

在下面的办法中咱们能够看见，是利用工夫轮，来进行过期解决的，工夫轮是什么呢？想必相熟一些定时工作系统对其并不生疏，他是一个高效的解决定时工作的构造，能够简略的将其看做是一个多维数组。在 Caffeine 中是一个二层工夫轮，也就是二维数组，其一维的数据表示较大的工夫维度比方，秒，分，时，天等，其二维的数据表示该工夫维度较小的工夫维度，比方秒内的某个区间段。当定位到一个 TimeWhilei 之后，其数据结构其实是一个链表，记录着咱们的 Node。在 Caffeine 利用工夫轮记录咱们在某个工夫过期的数据，而后去解决。

在 Caffeine 中的工夫轮如下面所示。在咱们插入数据的时候，依据咱们重写的办法计算出他应该过期的工夫，比方他应该在 1536046571142 工夫过期，上一次解决过期工夫是 1536046571100，对其相减则失去 42ms，而后将其放入工夫轮，因为其小于 1.07s，所以间接放入 1.07s 的地位，以及第二层的某个地位(须要通过肯定的算法算出)，应用尾插法插入链表。

解决过期工夫的时候会算出上一次解决的工夫和以后解决的工夫的差值，须要将其这个工夫范畴之内的所有工夫轮的工夫都进行解决，如果某个 Node 其实没有过期，那么就须要将其从新插入进工夫轮。

3.3. 除旧布新 - 更新策略

Caffeine 提供了 refreshAfterWrite()办法来让咱们进行写后多久更新策略:

下面的代码咱们须要建设一个 CacheLodaer 来进行刷新, 这里是同步进行的，能够通过 buildAsync 办法进行异步构建。在理论业务中这里能够把咱们代码中的 mapper 传入进去，进行数据源的刷新。

留神这里的刷新并不是到期就刷新，而是对这个数据再次拜访之后，才会刷新。举个例子: 有个 key:’ 咖啡 ’,value:’ 拿铁 ’ 的数据，咱们设置 1s 刷新，咱们在增加数据之后，期待 1 分钟，按理说下次访问时他会刷新，获取新的值，惋惜并没有，拜访的时候还是返回 ’ 拿铁 ’。然而持续拜访的话就会发现，他曾经进行了刷新了。

咱们来看看主动刷新他是怎么做的呢？主动刷新只存在读操作之后，也就是咱们 afterRead()这个办法，其中有个办法叫 refreshIfNeeded，他会依据你是同步还是异步而后进行刷新解决。

3.4 虚虚实实 - 软援用和弱援用

在 Java 中有四种援用类型: 强援用（StrongReference）、软援用（SoftReference）、弱援用（WeakReference）、虚援用（PhantomReference）。

• 强援用: 在咱们代码中间接申明一个对象就是强援用。
• 软援用: 如果一个对象只具备软援用，如果内存空间足够，垃圾回收器就不会回收它；如果内存空间有余了，就会回收这些对象的内存。只有垃圾回收器没有回收它，该对象就能够被程序应用。软援用能够和一个援用队列（ReferenceQueue）联结应用，如果软援用所援用的对象被垃圾回收器回收，Java 虚拟机就会把这个软援用退出到与之关联的援用队列中。
• 弱援用: 在垃圾回收器线程扫描它所管辖的内存区域的过程中，一旦发现了只具备弱援用的对象，不论以后内存空间足够与否，都会回收它的内存。弱援用能够和一个援用队列（ReferenceQueue）联结应用，如果弱援用所援用的对象被垃圾回收，Java 虚拟机就会把这个弱援用退出到与之关联的援用队列中。
• 虚援用: 如果一个对象仅持有虚援用，那么它就和没有任何援用一样，在任何时候都可能被垃圾回收器回收。虚援用必须和援用队列（ReferenceQueue）联结应用。当垃圾回收器筹备回收一个对象时，如果发现它还有虚援用，就会在回收对象的内存之前，把这个虚援用退出到与之 关联的援用队列中。

3.4.1 弱援用的淘汰策略

在 Caffeine 中反对弱援用的淘汰策略，其中有两个 api: weakKeys()和 weakValues(), 用来设置 key 是弱援用还是 value 是弱援用。具体原理是在 put 的时候将 key 和 value 用虚援用进行包装并绑定至援用队列:

。

具体回收的时候，在咱们后面介绍的 maintenance 办法中，有两个办法:

// 解决 key 援用的
drainKeyReferences();
// 解决 value 援用
drainValueReferences();
复制代码

具体的解决的代码有:

因为咱们的 key 曾经被回收了，而后他会进入援用队列，通过这个援用队列，始终弹出到他为空为止。咱们能依据这个队列中的使用获取到 Node, 而后对其进行驱赶。

留神: 很多同学认为在缓存中外部是存储的 Key-Value 的模式，其实存储的是 KeyReference – Node(Node 中蕴含 Value)的模式。

3.4.2 软援用的淘汰策略

在 Caffeine 中还反对软援用的淘汰策略, 其 api 是 softValues(), 软援用只反对 Value 不反对 Key。咱们能够看见在 Value 的回收策略中有：

和 key 援用回收类似，然而要阐明的是这里的援用队列，有可能是软援用队列，也有可能是弱援用队列。

3.5 知己知彼 - 打点监控

在 Caffeine 中提供了一些的打点监控策略，通过 recordStats()Api 进行开启，默认是应用 Caffeine 自带的，也能够本人进行实现。在 StatsCounter 接口中，定义了须要打点的办法目前来说有如下几个:

• recordHits：记录缓存命中
• recordMisses：记录缓存未命中
• recordLoadSuccess：记录加载胜利(指的是 CacheLoader 加载胜利)
• recordLoadFailure：记录加载失败
• recordEviction：记录淘汰数据

通过下面的监听，咱们能够实时监控缓存以后的状态，以评估缓存的衰弱水平以及缓存命中率等，不便后续调整参数。

3.6 善始善终 - 淘汰监听

有很多时候咱们须要晓得 Caffeine 中的缓存为什么被淘汰了呢，从而进行一些优化？这个时候咱们就须要一个监听器, 代码如下所示:

Cache<String, String> cache = Caffeine.newBuilder()
                .removalListener(((key, value, cause) -> {System.out.println(cause);
                }))
                .build();
复制代码

在 Caffeine 中被淘汰的起因有很多种:

• EXPLICIT: 这个起因是，用户造成的，通过调用 remove 办法从而进行删除。
• REPLACED: 更新的时候，其实相当于把老的 value 给删了。
• COLLECTED: 用于咱们的垃圾收集器，也就是咱们下面缩小的软援用，弱援用。
• EXPIRED：过期淘汰。
• SIZE: 大小淘汰，当超过最大的时候就会进行淘汰。

当咱们进行淘汰的时候就会进行回调，咱们能够打印出日志，对数据淘汰进行实时监控。