caffeine cache

转载自：https://blog.csdn.net/rlnLo2pNEfx9c/article/details/85241639

  guava cache的功能的确是很强大，满足了绝大多数的人的需求，但是其本质上还是LRU的一层封装,所以在众多其他较为优良的淘汰算法中就相形见绌了。而caffeine cache实现了W-TinyLFU(LFU+LRU算法的变种)。W-TinyLFU是命中率最接近理想的。当然不仅仅是命中率caffeine优于了guava cache，在读写吞吐量上面也是完爆guava cache。

W-TinyLFU
  在LFU中只要数据访问模式的概率分布随时间保持不变时，其命中率就能变得非常高。在这种模式下也是有局限性，比如有部新剧出来了，使用LFU缓存下来，这部新剧在这几天大概访问了几亿次，这个访问频率也在LFU中记录了几亿次，一个月之后这个新剧的前几集其实已经过气了，但是它的访问量的确是太高了，其他的电视剧根本无法淘汰这个新剧。所以各种LFU的变种出现了，基于时间周期进行衰减，或者在最近某个时间段内的频率。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中的实现,如果缓存大小是100，它会生成一个long数组大小是和100最接近的2的幂的数，也就是128。而这个数组将会记录访问频率。在caffeine中频率最大为15，15的二进制位1111，总共是4位，而Long型是64位。所以每个Long型可以放16种算法，但是caffeine并没有这么做，只用了四种hash算法，每个Long型被分为四段，每段里面保存的是四个算法的频率。这样做的好处是可以进一步减少Hash冲突，原先128大小的hash，就变成了128X4。

  一个Long有64位，分四段，每段16位，假设4个段分为A、B、C、D，每个段对应的四个hash算法分别是s1,s2,s3,s4。下面举个例子如果要添加一个访问50的数字频率应该怎么做？这里用size=100来举例。

1. 首先确定50这个hash是在哪个段里面，通过hash & 3必定能获得小于4的数字，假设hash & 3=0，那就在A段。
2. 对50的hash值再用其他hash算法再做一次hash，得到long数组的位置。假设用s1算法得到1，s2算法得到3，s3算法得到4，s4算法得到0。
3. 然后在long[1]的A段里面的s1位置进行+1，然后在long[3]的A段里面的s2位置进行+1，long[4]的A段里面的s3位置进行+1，long[0]的A段里面的s4位置进行+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。

  这三个队列关系如下:

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

  
  caffeine的api借鉴了Guava的api，其使用基本一模一样。越来越多的开源框架都放弃了Guava cache，比如Spring5。