来自未来的缓存解密-Caffeine1。前言希望大家仔细阅读这篇文章：你应该知道的缓存演化史，如何优雅地设计和使用缓存？.这两篇文章主要从一些实战中介绍缓存的使用方法。在这两篇文章中，我推荐使用本地缓存Caffeine来替换您的GuavaCache。在这篇文章中，我将介绍Caffeine缓存的具体作用，以及内部实现原理，让大家知其然，知其所以然。有人会问：我不使用Caffeine，这篇文章对我来说应该没什么用，别担心，Caffeine中的知识一定会对你其他代码设计有很大帮助。当然，在介绍之前，我还是想贴几张他和其他缓存的对比图：可以看到Caffeine在各个维度上基本都高于其他缓存。废话不多说，先来看看怎么用吧。1.1Caffeine的使用比较简单，API和GuavaCache一致：publicstaticvoidmain(String[]args){Cachecache=Caffeine.newBuilder().expireAfterWrite(1,TimeUnit.SECONDS).expireAfterAccess(1,TimeUnit.SECONDS).maximumSize(10).build();cache.put("你好","你好");}复制代码2.Caffeine原理介绍2.1W-TinyLFU传统的LFU受时间周期影响比较大。于是就出现了LFU的各种变体，根据时间段衰减，或者最近某个时间段内的频率衰减。同样的LFU也会使用额外的空间来记录每次数据访问的频率，即使数据不在缓存中也需要记录，所以需要维护的额外空间很大。你可以想象，我们为这个维护空间创建了一个hashMap，每一个数据项都会存储在这个hashMap中。当数据量特别大的时候，这个hashMap也会特别大。回到LRU，我们的LRU并没有那么无用。LRU可以很好地处理突发流量，因为它不需要积累数据频率。所以W-TinyLFU结合了LRU和LFU以及其他算法的一些特点。2.1.1录频首先要说的是录频的问题。我们要达到的目标是利用有限的空间来记录随时间变化的访问频率。使用W-TinyLFU中的Count-MinSketch来记录我们的访问频率，这也是Bloomfilter的变种。如下图所示：如果需要记录一个值，那么我们需要通过多种哈希算法对其进行哈希处理，然后将对应哈希算法的记录加1。为什么我们需要多种哈希算法？既然是压缩算法，肯定有冲突。比如我们创建一个Long的数组，计算每条数据的hash位置。比如张三和李四，他们两个的hash值可能是一样的。比如都为1，Long[1]的位置会增加相应的频率。如果张三访问10000次，李四访问一次，那么Long[1]这个位置就是10001。如果拿李斯的访问评价率来说，就是10001。然而，李斯只去过一次。为了解决这个问题，多重哈希算法可以理解为一个long[][]二维数组的概念。比如第一个算法，张三和李四冲突，但是第二个和第三个，大概率是不冲突的。例如，一个算法大约有1%的概率发生冲突，四个算法一起冲突的概率是1%的4次方。通过这种模式，我们在取李四的访问率时，取所有算法中李四访问频率最低的个数。所以他的名字叫Count-MinSketch。这里和前面的比较一下，一个简单的例子：如果用一个hashMap来记录这个频率，如果我有100条数据，那么这个HashMap要存储100个这个数据的访问频率。即使我缓存的容量是1，因为Lfu的规则，我必须记录这100条数据的所有访问频率。如果有更多数据，我会记录更多。在Count-MinSketch中，我直接说说caffeine中的实现（在FrequencySketch类中）。如果你的缓存大小是100，它会生成一个long数组，其大小是最接近100的2次方，也就是128。而这个数组会记录我们的访问频率。在caffeine中，最大频率为15，15个二进制位1111，共4位，Long类型为64位。因此，每个Long类型可以容纳16个算法，但caffeine不会这样做。它仅使用四种哈希算法。每个Long类型分为四个段，每个段存储四种算法的频率。这样做的好处是可以进一步减少Hash冲突，原来的128个hash大小变成了128X4。一个Long的结构是这样的：我们的4段分为A,B,C,D，后面我会这样称呼它们。而每个段中的四种算法我称他为s1、s2、s3、s4。这是一个例子。想添加接入50的数字频率怎么办？这里我们以size=100为例。首先判断50的hash在哪个段，通过hash&3（3的二进制值为11），必须得到一个小于4的数。假设hash&3=0，在A段，对于50的hash，用其他hash算法再做一次hash，得到long数组的位置，即数组中长度为的位置128.假设用s1算法得到1，s2算法得到3，s3算法得到4，s4算法得到0。因为S1算法得到1，所以在s1的位置加1long[1]的一段，简称1As1加1，然后3As2加1，4As3加1，0As4加1。这时候有人会质疑最大频率15是不是太小了？没关系。在这个算法中，比如size等于100，如果他全局增加size*10，也就是1000倍，就除以2，全局衰减。衰减后还可以继续增加。该算法在W-TinyLFU论文中得到证明。更能适应时间段的访问频率。2.2读写性能在guavacache中，我们说过它的读写操作是混合了过期时间处理的，也就是你可能还会在一个Put操作中进行淘汰操作，所以它的读写性能会受到一定的影响一定程度上，你可以看上图，caffeine确实在读写操作时爆了guavacache。主要原因是在caffeine中，这些事件的操作是通过异步操作的。他将事件提交到队列。这里队列的数据结构是RingBuffer。如果不清楚，可以看这篇文章。你应该知道高性能无锁QueueDisruptor。然后通过默认的ForkJoinPool.commonPool()，或者自己配置线程池，进行取队列操作，然后进行后续的淘汰和过期操作。当然，读和写有不同的队列。Caffeine认为缓存的读比写多很多，所以对于写操作，所有线程共享一个Ringbuffer。对于比写操作更频繁的读操作，进一步减少竞争，它为每个线程配备了一个RingBuffer：2.3数据淘汰策略caffeine中的所有数据都在ConcurrentHashMap中，这一点不同于guava缓存。Guava缓存实现了一个类似ConcurrentHashMap的A结构。caffeine中记录引用的LRU队列有3种：Eden队列：caffeine中规定只能是缓存容量的%1。如果size=100，则这个队列的有效大小等于1。新到达的数据记录在这个队列中，防止突发流量因为之前没有访问频率而被淘汰。比如新剧上线，一开始其实是没有访问频率的，防止上线后被其他缓存淘汰，加入这个区域。伊甸园区，最舒适最舒适的区域，在这里很难被其他数据淘汰。试用队列：称为试用队列。在这个队列中意味着你的数据比较冷，很快就会被淘汰。有效大小是大小减去伊甸园减去保护。Protected队列：在这个队列中，你可以放心，你暂时不会被淘汰，但是不用担心，如果Protation队列没有数据或者Protected数据满了，你也会面临被淘汰的尴尬情况被淘汰。当然，如果你想成为这个队列，你需要访问一次Probation，然后它就会升级为受保护的队列。有效大小为（size减去eden）X80%如果size=100，则为79。这三个队列之间的关系如下：所有新数据都会进入Eden。伊甸园已满，被淘汰进入试用期。如果其中一个数据在Probation中被访问，则该数据将升级为Protected。如果Protected已满，它将继续降级为Probation。当发生数据淘汰时，它将被淘汰出试用期。这个队列中数据队列的头部将被称为牺牲者。这个队列的头部必须是第一个进入的。按照LRU队列的算法，他其实应该被淘汰，但在这里他只能被称为受害者。这个队列是缓刑队列，也就是说他要处决他了。这将取出团队尾部呼叫候选人，也称为攻击者。在这里，受害者将在皇城与攻击者PK，决定我们应该消灭谁。根据我们Count-MinSketch中记录的频率数据，有如下几种判断：如果攻击者比受害者大，则直接淘汰受害者。如果攻击者<=5，则直接消灭攻击者。他的笔记中解释了这个逻辑：他认为设置预热阈值会导致更高的整体命中率。其他情况随机淘汰。3.Caffeine功能分析Caffeine的功能有很多。让我们分析一下这些API是如何工作的。3.1百花齐放——CacheFactoryCaffeine中有一个LocalCacheFactory类，它会根据你的配置创建特定的Cache。可以看到，他会根据你是否配置过期时间来组装字符串，去掉listener等参数，最后根据字符串生成具体的缓存。这里缓存太多，作者的源码就不直接写了。这部分代码由Java诗人生成：3.2Ephemeral-Caffeine中过期策略分为两种缓存，一种是有界缓存，一种是无界缓存。无界缓存不需要过期，没有边界。有界缓存中提供了三个过期API：expireAfterWrite：表示写入后过期时间。expireAfterAccess：表示上次访问过期后多久。expireAfter：在expireAfter中，需要自己实现Expiry接口。此接口支持创建、更新以及访问过期后的时间。请注意，此API与前两个API互斥。这个和前面两个API的区别在于，你需要告诉缓存框架它应该在特定的时间过期，即通过重写上面的create、update和access方法来获取具体的过期时间。Caffeine中有一个scheduleDrainBuffers方法，用来调度我们的逾期任务。我们读写后会调用它：首先，它会加锁。如果锁定失败，则意味着已经有人在执行调度。他会使用默认的线程池ForkJoinPool或者自定义的线程池。这里的drainBuffersTask其实就是Caffeine中的PerformCleanupTask。在performCleanUp方法中再次加锁，防止其他线程清理。然后我们进入维护方法：可以看到里面有很多方法，其他的方法后面再说。这里重点关注expireEntries()，也就是用来过期的方法：先获取当前时间。第二步是expireafterAccess：这里根据我们的配置，evicts()方法为true，所以三个队列都会过期淘汰。上面说了，这三个队列都是LRU队列，所以我们的expireAfterAccessEntries方法，只需要判断每个队列的头节点是否过期，然后移除即可。第三步expireAfterWrite：可以看到这里依赖了一个队列writeQrderDeque。这个队列中的数据什么时候填满？当然也用到了异步。具体方法在我们上面的draninWriteBuffer中，会把我们之前放入RingBuffer中的Task取出来执行，其中还包括添加writeQrderDeque。过期策略很简单，循环弹出第一个判断是否过期即可。第四步expireVariableEntries：在上面的方法中，我们可以看到时间轮是用来进行过期处理的。什么是时间轮？对一些定时任务系统你肯定不陌生，对它也不陌生。是一种处理定时任务的高效结构，可以简单的看成是一个多维数组。在Caffeine中，它是一个双层时间轮，也就是一个二维数组。它的一维数据代表一个更大的时间维度，比如秒、分、小时、天等，它的二维数据代表一个更小的时间维度。时间维度，比如秒级内的某个时间间隔。定位到一个TimeWhilei之后，它的数据结构其实就是一个链表，记录了我们的Node.在Caffeine中，我们使用时间轮来记录某个时间过期的数据，然后进行处理。Caffeine中的时间轮如上所示。当我们插入数据时，我们根据我们的重写方法计算它应该过期的时间。比如应该在1536046571142过期，最后处理过期时间是15♂46571100。减去就是得到42ms，然后放入时间轮。由于小于1.07s，直接放到1.07s的位置，和第二层的某个位置（需要通过一定的算法计算），用尾部插值的方式插入到链表中。在处理过期时间时，会计算上次处理时间与当前处理时间的差值。需要处理这个时间范围内的所有时间轮次。如果一个节点还没有过期，那么它需要将它重新插入到时间轮中。3.3.去旧更新——更新策略Caffeine提供了refreshAfterWrite()方法让我们可以在写入后更新策略：我们需要创建一个CacheLodaer来刷新上面的代码，同步执行，可以通过buildAsync异步构建方法。在实际业务中，可以传入我们代码中的mapper来刷新数据源。注意这里的刷新不是过期刷新，而是再次访问数据后刷新。比如：有key:'coffee',value:'latte'数据，我们设置1s刷新，我们添加数据后等待1分钟，按理说下次访问时会刷新，得到新的值，不幸的是，没有，当我访问时，我仍然返回'Latte'。但是如果你继续访问，你会发现他已经神清气爽了。我们来看看他是怎么做自动刷新的？自动刷新只存在于读操作之后，也就是我们的afterRead()方法。有一个方法叫refreshIfNeeded，会根据你是同步还是异步来刷新。3.4虚构与现实——软引用和弱引用Java中有四种引用：强引用（StrongReference）、软引用（SoftReference）、弱引用（WeakReference）、虚引用（PhantomReference）。强引用：在我们的代码中直接声明一个对象就是强引用。软引用：如果一个对象只有软引用，如果有足够的内存空间，垃圾回收器不会回收它；如果内存空间不足，就会回收这些对象的内存。只要垃圾收集器不收集它，该对象就可以被程序使用。软引用可以与引用队列（ReferenceQueue）结合使用。如果软引用引用的对象被垃圾回收器回收，Java虚拟机会将软引用添加到与其关联的引用队列中。弱引用：垃圾回收线程在扫描其管辖的内存区域过程中，一旦发现只有弱引用的对象，无论当前内存空间是否充足，都会回收其内存。弱引用可以与引用队列（ReferenceQueue）结合使用。如果弱引用引用的对象被垃圾回收，Java虚拟机会将弱引用添加到与其关联的引用队列中。幻影引用：如果一个对象只有幻影引用，就好像它没有任何引用，随时可能被垃圾收集器回收。幻象引用必须与引用队列（ReferenceQueue）结合使用。当垃圾回收器要回收一个对象时，如果发现它还有一个虚引用，就会把这个虚引用添加到与之关联的引用队列中，然后再回收该对象的内存。3.4.1弱引用淘汰策略Caffeine支持弱引用淘汰策略。有两个API：weakKeys()和weakValues()，用于设置key是弱引用还是value是弱引用。具体原理是把key和value用virtualreferences包裹起来，在put的时候绑定到referencequeue：。在回收的时候，在我们前面介绍的维护方法中，有两个方法//drainKeyReferences()处理键引用；//处理drainValueReferences()处理值引用；copycode具体的处理代码是：因为我们的key已经被回收了，然后会进入引用队列，通过这个引用队列，弹出，直到为空。我们可以根据这个队列中的申请获取Node，然后驱逐。注意：很多同学认为缓存中的内部存储是以Key-Value的形式存储的，但实际上是以KeyReference-Node（Node包含Value）的形式存储的。3.4.2软引用的淘汰策略Caffeine也支持软引用的淘汰策略。它的api是softValues()。软引用只支持Value，不支持Key。我们可以看到，在Value的回收策略中：类似于key的引用回收，但是需要注意的是这里的引用队列可能是软引用队列，也可能是弱引用队列。3.5知己知彼-RBI监控Caffeine提供了一些RBI监控策略，这些策略通过recordStats()API启用。默认自带Caffeine，也可以自己实现。在StatsCounter接口中，需要检查的方法定义如下：recordHits：记录缓存命中recordMisses：记录缓存未命中recordLoadSuccess：记录加载成功（指CacheLoader加载成功）recordLoadFailure：记录加载失败recordEviction：记录淘汰数据通过通过以上监控，我们可以实时监控缓存的当前状态，评估缓存的健康度和缓存命中率等，方便后续调整参数。3.6首末淘汰监控很多时候我们需要知道Caffeine中的缓存为什么要淘汰，从而做一些优化？这时候我们需要一个监听器，代码如下：Cachecache=Caffeine.newBuilder().removalListener(((key,value,cause)->{System.out.println(cause);}））。建造（）;Caffeine中复制代码被淘汰的原因有很多：EXPLICIT：这个原因是用户造成的，调用remove方法删除。REPLACED：更新时，其实相当于删除旧值。COLLECTED：对于我们的垃圾收集器，也就是我们上面减少的软引用和弱引用。EXPIRED：过期淘汰。SIZE：尺寸淘汰，超过最大值则淘汰。当我们淘汰时，我们会回调，我们可以打印出日志，实时监控数据淘汰情况。
