前言

项目地址：https://github.com/ben-manes/caffeine

目前的master的版本是2.8.4

如何用

基本使用（摘自官网）：

LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
    .maximumSize(10_000)
    .expireAfterWrite(5, TimeUnit.MINUTES)
    .refreshAfterWrite(1, TimeUnit.MINUTES)
    .build(key -> createExpensiveGraph(key));

缓存容量为1w个对象，写后5分钟失效、写后1分钟刷新，刷新从哪获取值？执行createExpensiveGraph获取新值

// 更新缓存
graphs.put(key, graph);
// 获取缓存
graphs.get(key);

存在哪

缓存的配置放哪？

就是我们构造的Caffeine对象

缓存中是如何存数据的呢？

用JUC库

final ConcurrentHashMap<Object, Node<K, V>> data = new ConcurrentHashMap<>(builder.getInitialCapacity());
// 为什么key类型是Object，因为支持weakKey，所以这时Object就是WeakReference
// Node对象除了键和值对象，还有可能维护一些时间戳的信息，用于过期的判断

所以，我们看到了类似Map接口的put、get的api。而caffeine也通过data对象的原子操作解决了，部分并发问题，比如

  @Nullable V put(K key, V value) {
  // 省略data.get为null，就把computed往里放
            prior = data.computeIfAbsent(node.getKeyReference(), k -> {
              writer.write(key, value);
              return computed;
            });
  }

对于设置了大小限制的入参，框架要如何淘汰，提高命中率呢？

划分为3块区域。比如代码示例中，`maximumSize(10_000)`

那么1%，做为window的最大大小，即100
剩下的80%，做为protected的最大大小，即7200
最后剩下的，作为probation的最大大小，即1800

所以，数据除了放data，也会放入对应区域的LRU队列，accessOrderWindowDeque、accessOrderProtectedDeque、accessOrderProbationDeque note：这些是LRU队列，队尾是最新操作的

以上就是window-tinyLFU论文中的区域划分，注意到LFU，可以看出这是根据频率的淘汰策略

论文提到的LFU的实现Count-Min Sketch，这是一个基于多hash统计的实现，caffeine也是。后续详解。现在只要知道，通过Sketch统计频率，有两种操作：

increment(key) 加频数
frequency(key) 获取当前频数

note：

数据更新或新增，不管数据处于哪个区域，increment(key)
频数的值，最大15，所以超过15就不加了
当increment操作达到采样数量sampleSize（一般是缓存的10倍），进行reset操作，Sketch里的所有统计，全部除2

区域之间的调度

数据新增进来，放入window
如果window满了，把window的队头，加到probation队尾，直到window不再超过1%，假如移了a个对象，那么probation多了a个对象
接下来，要在probation，清理掉a个对象（要是probation已经空了，那清probation，还是空的，那就清window）
- 首先，把probation的队头peek出来，作为victim，队尾peek出来，作为candidate（一般就是上一步从window移进来的）
- 然后，要把其中一个清理掉。
- 通过Sketch，如果candidate的频数更大，清理victim，否则应该考虑清理candidate
- 如何考虑candidate的清理呢？如果candidate的频数小于等于5，就直接清了，否则以1%的概率决定保留candidate（也就是1%的概率清victim）
1%是哪来的？

考虑一种漏洞攻击，通过hash碰撞设法把victim维持在高频率，所以我们引入随机，1%的的概率踢掉victim，正常使用其实没有影响
到现在，我们现在有window->probation，probation->移除，还有以下的情况

probation -> protected：条件是probation区的数据被新增或更新
protected -> probation：条件是protected满了

总结一下：

数据先到window，满了，移到probation，进行频数比较，进行清理。
剩下的probation和protected的转换，比较独立。

那个1%的window，为什么要加这层？

我们提到，那三块区域，其实都是LRU队列，数据进来就放window，其实说明，这个框架的前端，就是LRU（基于最近），后端才是LFU（基于频率）论文里指出：如果单纯用tinyLFU的问题：对于突发一组请求，也就是和当前的缓存，毫无关系。突发请求结束后，基于频率的策略比LRU恢复的更慢，所以加入window

那这个空间占比，为什么是1%？其实在不同的场景下，window的最大值的最佳值，也是不同的。 caffeine对此作了adaptive，自适应类似梯度下降算法：

如果第一次把window调大一定步长step
如果缓存命中率提高了，那么第二次，在第一次的基础上，调小一点，比如调成step*98%
如果命中率降低了，第二次就往相反的方向调。
这样step会不断收敛
如果命中率相比上一次变化太大（大于5%），那可能缓存的负载环境已经发生变化了，重新设置step

前言

如何用

存在哪