深刻解密来自将来的缓存-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: 大小淘汰，当超过最大的时候就会进行淘汰。

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