转载

jvm内部缓存选型？一篇文章为你解答疑惑

jvm内部缓存有哪些

原生Java

简单的在HashMap的链式法增加新的引用形成一个链表，即是一个HashMap又是一个链表，这样输出即有序，也可以根据访问来动态调整顺序，达到FIFO或者LRU的特点。

使用ConcurrentHashMap作为缓存，没有淘汰功能或者手动淘汰。但是寻找效率较高，而且线程安全

可以明显看出这个存在的问题，线程不安全，需要额外加锁，功能结构单一，没有过期时间容易存在内存泄露

Guava

因为LinkedHashMap存在的问题，所以大神们在此基础上造出了Guava

既然HashMap线程不安全，那么就使用CurrentHashMap(类似不完全是)，为了实现过期那么就给数据加上时间戳标志，为了实现写后过期，读后过期，这两种配置，就使用了多条队列分别代表读和写

EHCHCHED

Ehcache支持持久化到本地磁盘，Guava不可以;

Ehcache有现成的集群解决方案，Guava没有。不过个人感觉比较鸡肋，对JVM级别的缓存来讲太重了

Ehcache jar包庞大，Guava Cache只是Guava jar包中的工具之一，而且后者远远小于Ehcache;

两种缓存当缓存过期或者没有命中的时候都可以通过load接口重载数据，调用方式略有不同。两者的主要区别是Ehcache的缓存load的时候，允许用户返回null，而Guava Cache则不允许返回为null，因为Guava Cache是根据value的值是否为null来判断是否需要load，所以不允许返回为null，但是使用的时候可以使用空对象替换。不允许返回null是一个很好的考虑;

Ehcache有内存占用大小统计，Guava Cache没有，需要自己开发;

Ehcache在put缓存的时候，对K、V都做了包装，对GC有一定影响。

Caffeine

Caffeine是Spring 5默认支持的Cache，可见Spring对它的看重，那么Spring为什么喜新厌旧的抛弃Guava而追求Caffeine呢?

缓存的淘汰策略是为了预测哪些数据在短期内最可能被再次用到，从而提升缓存的命中率。LRU由于实现简单、高效的运行时表现以及在常规的使用场景下有不错的命中率，或许是目前最佳的实现途径。但 LRU 通过历史数据来预测未来是局限的，它会认为最后到来的数据是最可能被再次访问的，从而给与它最高的优先级。这样就意味着淘汰真正热点数据，为了解决这个问题业界运用一些数据结构上的改进巧妙的解决这个问题。

下面的内容是转载的一篇译文，如果需要查看译文原文，请点击这里,英语好的同学也可以直接查看英文原作。

缓存是提升性能的通用方法，现在大多数的缓存实现都使用了经典的技术。这篇文章中，我们会发掘Caffeine中的现代的实现方法。Caffeine是一个开源的Java缓存库，它能提供高命中率和出色的并发能力。期望读者们能被这些想法激发，进而将它们应用到任何你喜欢的编程语言中。

驱逐策略

缓存的驱逐策略是为了预测哪些数据在短期内最可能被再次用到，从而提升缓存的命中率。由于简洁的实现、高效的运行时表现以及在常规的使用场景下有不错的命中率，LRU(Least Recently Used)策略或许是最流行的驱逐策略。但LRU通过历史数据来预测未来是局限的，它会认为最后到来的数据是最可能被再次访问的，从而给与它最高的优先级。

现代缓存扩展了对历史数据的使用，结合就近程度(recency)和访问频次(frequency)来更好的预测数据。其中一种保留历史信息的方式是使用popularity sketch(一种压缩、概率性的数据结构)来从一大堆访问事件中定位频繁的访问者。可以参考CountMin Sketch算法，它由计数矩阵和多个哈希方法实现。发生一次读取时，矩阵中每行对应的计数器增加计数，估算频率时，取数据对应是所有行中计数的最小值。这个方法让我们从空间、效率、以及适配矩阵的长宽引起的哈希碰撞的错误率上做权衡。

Window TinyLFU(W-TinyLFU)算法将sketch作为过滤器，当新来的数据比要驱逐的数据高频时，这个数据才会被缓存接纳。这个许可窗口给予每个数据项积累热度的机会，而不是立即过滤掉。这避免了持续的未命中，特别是在突然流量暴涨的的场景中，一些短暂的重复流量就不会被长期保留。为了刷新历史数据，一个时间衰减进程被周期性或增量的执行，给所有计数器减半。

对于长期保留的数据，W-TinyLFU使用了分段LRU(Segmented LRU，缩写SLRU)策略。起初，一个数据项存储被存储在试用段(probationary segment)中，在后续被访问到时，它会被提升到保护段(protected segment)中(保护段占总容量的80%)。保护段满后，有的数据会被淘汰回试用段，这也可能级联的触发试用段的淘汰。这套机制确保了访问间隔小的热数据被保存下来，而被重复访问少的冷数据则被回收。

如图中数据库和搜索场景的结果展示，通过考虑就近程度和频率能大大提升LRU的表现。一些高级的策略，像ARC，LIRS和W-TinyLFU都提供了接近最理想的命中率。想看更多的场景测试，请查看相应的论文，也可以在使用simulator来测试自己的场景。

过期策略

过期的实现里，往往每个数据项拥有不同的过期时间。因为容量的限制，过期后数据需要被懒淘汰，否则这些已过期的脏数据会污染到整个缓存。一般缓存中会启用专有的清扫线程周期性的遍历清理缓存。这个策略相比在每次读写操作时按照过期时间排序的优先队列来清理过期缓存要好，因为后台线程隐藏了的过期数据清除的时间开销。

鉴于大多数场景里不同数据项使用的都是固定的过期时长，Caffien采用了统一过期时间的方式。这个限制让用O(1)的有序队列组织数据成为可能。针对数据的写后过期，维护了一个写入顺序队列，针对读后过期，维护了一个读取顺序队列。缓存能复用驱逐策略下的队列以及下面将要介绍的并发机制，让过期的数据项在缓存的维护阶段被抛弃掉。

并发

由于在大多数的缓存策略中，数据的读取都会伴随对缓存状态的写操作，并发的缓存读取被视为一个难点问题。传统的解决方式是用同步锁。这可以通过将缓存的数据划成多个分区来进行锁拆分优化。不幸的是热点数据所持有的锁会比其他数据更常的被占有，在这种场景下锁拆分的性能提升也就没那么好了。当单个锁的竞争成为瓶颈后，接下来的经典的优化方式是只更新单个数据的元数据信息，以及使用随机采样、基于FIFO的驱逐策略来减少数据操作。这些策略会带来高性能的读和低性能的写，同时在选择驱逐对象时也比较困难。

另一种可行方案来自于数据库理论，通过提交日志的方式来扩展写的性能。写入操作先记入日志中，随后异步的批量执行，而不是立即写入到数据结构中。这种思想可以应用到缓存中，执行哈希表的操作，将操作记录到缓冲区，然后在合适的时机执行缓冲区中的内容。这个策略依然需要同步锁或者tryLock，不同的是把对锁的竞争转移到对缓冲区的追加写上。

在Caffeine中，有一组缓冲区被用来记录读写。一次访问首先会被因线程而异的哈希到stripped ring buffer上，当检测到竞争时，缓冲区会自动扩容。一个ring buffer容量满载后，会触发异步的执行操作，而后续的对该ring buffer的写入会被丢弃，直到这个ring buffer可被使用。虽然因为ring buffer容量满而无法被记录该访问，但缓存值依然会返回给调用方。这种策略信息的丢失不会带来大的影响，因为W-TinyLFU能识别出我们希望保存的热点数据。通过使用因线程而异的哈希算法替代在数据项的键上做哈希，缓存避免了瞬时的热点key的竞争问题。

写数据时，采用更传统的并发队列，每次变更会引起一次立即的执行。虽然数据的损失是不可接受的，但我们仍然有很多方法可以来优化写缓冲区。所有类型的缓冲区都被多个的线程写入，但却通过单个线程来执行。这种多生产者/单个消费者的模式允许了更简单、高效的算法来实现。

缓冲区和细粒度的写带来了单个数据项的操作乱序的竞态条件。插入、读取、更新、删除都可能被各种顺序的重放，如果这个策略控制的不合适，则可能引起悬垂索引。解决方案是通过状态机来定义单个数据项的生命周期。

在基准测试中，缓冲区随着哈希表的增长而增长，它的的使用相对更节省资源。读的性能随着CPU的核数线性增长，是哈希表吞吐量的33%。写入有10%的性能损耗，这是因为更新哈希表时的竞争是最主要的开销。

Caffeine

举个例子

Mysql的缓存池，内部实现是一个LRU，但是其内部有个中间点,指向倒数3/8，一半是old区，另一半是young区，新数据插入是直接插入young区，这样就保护了真正的老数据不会被冲刷掉。

多级队列的形式

LFU结合频率这一属性给予更好的预测缓存数据是否在未来被使用。

但是传统LFU有其局限性：

LFU实现需要维护大而复杂的元数据(频次统计数据等)

大多数实际工作负载中，访问频率随着时间的推移而发生根本变化，而传统LFU无法周期衰减频率

传统LFU的实现通过外接一个HashMap统计频率，但是HashMap存在Hash冲突，这会导致频率统计的不准确。

为了解决这些问题，Caffeine提出一种新的算法W-TinyLFU，它可以解决频率统计不准确以及访问频率衰减问题。这个方法让我们从空间、效率、以及适配矩阵的长宽引起的哈希碰撞的错误率上做权衡。

传统Hash存在Hash冲突的问题，使用LFU算法时候记录频率的话一旦发生hash冲突可能造成频率的统计错误。

W-TinyLFU算法使用一种Count-Min Sketch解决维护空间大的问题，类似布隆过滤器，降低冲突可能性，原理是多次hash分散开来，取最小值作为频率，一次Hash冲突的几率是1%的话，4次Hash的几率就是1%的4次方，大大降低的冲突可能性。

在Caffeine中为了实现Count-Min Sketch它在其中村政府，存放四个算法

其中randomSeed是一个随机数，sampleSize=开始设置的缓存最大树*10;table= 最大缓存数最接近的2的次方数(100的话是128，50是64);tableMask = table.length-1;size=0

在向缓存put数据的时候会调用

这个AddTask是一个Runnable，其中run方法会调用increment方法。

Caffeine比guava好在哪

W-TinyLFU

传统的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(3的二进制是11)必定能获得小于4的数字，假设hash & 3=0，那就在A段。

对50的hash再用其他hash算法再做一次hash，得到long数组的位置，也就是在长度128数组中的位置。假设用s1算法得到1，s2算法得到3，s3算法得到4，s4算法得到0。

因为S1算法得到的是1，所以在long[1]的A段里面的s1位置进行+1,简称1As1加1，然后在3As2加1，在4As3加1，在0As4加1。

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

读写性能

在guava cache中我们说过其读写操作中夹杂着过期时间的处理，也就是你在一次Put操作中有可能还会做淘汰操作，所以其读写性能会受到一定影响，可以看上面的图中，caffeine的确在读写操作上面完爆guava cache。主要是因为在caffeine，对这些事件的操作是通过异步操作，他将事件提交至队列，这里的队列的数据结构是RingBuffer,不清楚的可以看看这篇文章,你应该知道的高性能无锁队列Disruptor。然后会通过默认的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，那么直接淘汰攻击者。这个逻辑在他的注释中有解释: