caffeine[1]是一个高性能，高命中率，低内存占用，near optimal 的本地缓存，简单来说它是 guava cache 的优化加强版，有些文章把 caffeine 称为“新一代的缓存”、“现代缓存之王”。
本文将重点讲解 caffeine 的高性能设计，以及对应部分的源码分析。
如果你对 guava cache 还不理解的话，可以点击这里[2]来看一下我之前写过关于 guava cache 的文章。
大家都知道，spring5 即将放弃掉 guava cache 作为缓存机制，而改用 caffeine 作为新的本地 cache 的组件，这对于 caffeine 来说是一个很大的肯定。为什么 spring 会这样做呢？其实在 caffeine 的benchmarks[3]里给出了好靓仔的数据，对读和写的场景，还有跟其他几个缓存工具进行了比较，caffeine 的性能都表现很突出。
caffeine 为了方便大家使用以及从 guava cache 切换过来（很有针对性啊～），借鉴了 guava cache 大部分的概念（诸如核心概念<code>cache</code>、<code>loadingcache</code>、<code>cacheloader</code>、<code>cachebuilder</code>等等），对于 caffeine 的理解只要把它当作 guava cache 就可以了。
使用上，大家只要把 caffeine 的包引进来，然后换一下 cache 的实现类，基本应该就没问题了。这对与已经使用过 guava cache 的同学来说没有任何难度，甚至还有一点熟悉的味道，如果你之前没有使用过 guava cache，可以查看 caffeine 的官方 api 说明文档[4]，其中<code>population</code>，<code>eviction</code>，<code>removal</code>，<code>refresh</code>，<code>statistics</code>，<code>cleanup</code>，<code>policy</code>等等这些特性都是跟 guava cache 基本一样的。
下面给出一个例子说明怎样创建一个 cache：
更多从 guava cache 迁移过来的使用说明，请看这里[5]
判断一个缓存的好坏最核心的指标就是命中率，影响缓存命中率有很多因素，包括业务场景、淘汰策略、清理策略、缓存容量等等。如果作为本地缓存， 它的性能的情况，资源的占用也都是一个很重要的指标。下面
我们来看看 caffeine 在这几个方面是怎么着手的，如何做优化的。
（注：本文不会分析 caffeine 全部源码，只会对核心设计的实现进行分析，但我建议读者把 caffeine 的源码都涉猎一下，有个 overview 才能更好理解本文。如果你看过 guava cache 的源码也行，代码的数据结构和处理逻辑很类似的。
源码基于：caffeine-2.8.0.jar）
上面说到淘汰策略是影响缓存命中率的因素之一，一般比较简单的缓存就会直接用到 lfu(least frequently used，即最不经常使用) 或者lru(least recently used，即最近最少使用) ，而 caffeine 就是使用了 w-tinylfu 算法。
w-tinylfu 看名字就能大概猜出来，它是 lfu 的变种，也是一种缓存淘汰算法。那为什么要使用 w-tinylfu 呢？
lru 实现简单，在一般情况下能够表现出很好的命中率，是一个“性价比”很高的算法，平时也很常用。虽然 lru 对突发性的稀疏流量（sparse bursts）表现很好，但同时也会产生缓存污染，举例来说，如果偶然性的要对全量数据进行遍历，那么“历史访问记录”就会被刷走，造成污染。
如果数据的分布在一段时间内是固定的话，那么 lfu 可以达到最高的命中率。但是 lfu 有两个缺点，第一，它需要给每个记录项维护频率信息，每次访问都需要更新，这是个巨大的开销；第二，对突发性的稀疏流量无力，因为前期经常访问的记录已经占用了缓存，偶然的流量不太可能会被保留下来，而且过去的一些大量被访问的记录在将来也不一定会使用上，这样就一直把“坑”占着了。
无论 lru 还是 lfu 都有其各自的缺点，不过，现在已经有很多针对其缺点而改良、优化出来的变种算法。
tinylfu 就是其中一个优化算法，它是专门为了解决 lfu 上述提到的两个问题而被设计出来的。
解决第一个问题是采用了 count–min sketch 算法。
解决第二个问题是让记录尽量保持相对的“新鲜”（freshness mechanism），并且当有新的记录插入时，可以让它跟老的记录进行“pk”，输者就会被淘汰，这样一些老的、不再需要的记录就会被剔除。
下图是 tinylfu 设计图（来自官方）
如何对一个 key 进行统计，但又可以节省空间呢？（不是简单的使用<code>hashmap</code>，这太消耗内存了），注意哦，不需要精确的统计，只需要一个近似值就可以了，怎么样，这样场景是不是很熟悉，如果你是老司机，或许已经联想到布隆过滤器（bloom filter）的应用了。
没错，将要介绍的 count–min sketch 的原理跟 bloom filter 一样，只不过 bloom filter 只有 0 和 1 的值，那么你可以把 count–min sketch 看作是“数值”版的 bloom filter。
更多关于 count–min sketch 的介绍请自行搜索。
在 tinylfu 中，近似频率的统计如下图所示：
对一个 key 进行多次 hash 函数后，index 到多个数组位置后进行累加，查询时取多个值中的最小值即可。
caffeine 对这个算法的实现在<code>frequencysketch</code>类。但 caffeine 对此有进一步的优化，例如 count–min sketch 使用了二维数组，caffeine 只是用了一个一维的数组；再者，如果是数值类型的话，这个数需要用 int 或 long 来存储，但是 caffeine 认为缓存的访问频率不需要用到那么大，只需要 15 就足够，一般认为达到 15 次的频率算是很高的了，而且 caffeine 还有另外一个机制来使得这个频率进行衰退减半（下面就会讲到）。如果最大是 15 的话，那么只需要 4 个 bit 就可以满足了，一个 long 有 64bit，可以存储 16 个这样的统计数，caffeine 就是这样的设计，使得存储效率提高了 16 倍。
caffeine 对缓存的读写（<code>afterread</code>和<code>afterwrite</code>方法）都会调用<code>onaccess</code>s 方法，而<code>onaccess</code>方法里有一句：
这句就是追加记录的频率，下面我们看看具体实现
知道了追加方法，那么读取方法<code>frequency</code>就很容易理解了。
通过代码和注释或者读者可能难以理解，下图是我画出来帮助大家理解的结构图。
注意紫色虚线框，其中蓝色小格就是需要计算的位置：
为了让缓存保持“新鲜”，剔除掉过往频率很高但之后不经常的缓存，caffeine 有一个 freshness mechanism。做法很简答，就是当整体的统计计数（当前所有记录的频率统计之和，这个数值内部维护）达到某一个值时，那么所有记录的频率统计除以 2。
从上面的代码
看到<code>reset</code>方法就是做这个事情
关于这个 reset 方法，为什么是除以 2，而不是其他，及其正确性，在最下面的参考资料的 tinylfu 论文中 3.3 章节给出了数学证明，大家有兴趣可以看看。
caffeine 通过测试发现 tinylfu 在面对突发性的稀疏流量（sparse bursts）时表现很差，因为新的记录（new items）还没来得及建立足够的频率就被剔除出去了，这就使得命中率下降。
于是 caffeine 设计出一种新的 policy，即 window tiny lfu（w-tinylfu），并通过实验和实践发现 w-tinylfu 比 tinylfu 表现的更好。
w-tinylfu 的设计如下所示（两图等价）：
它主要包括两个缓存模块，主缓存是 slru（segmented lru，即分段 lru），slru 包括一个名为 protected 和一个名为 probation 的缓存区。通过增加一个缓存区（即 window cache），当有新的记录插入时，会先在 window 区呆一下，就可以避免上述说的 sparse bursts 问题。
当 window 区满了，就会根据 lru 把 candidate（即淘汰出来的元素）放到 probation 区，如果 probation 区也满了，就把 candidate 和 probation 将要淘汰的元素 victim，两个进行“pk”，胜者留在 probation，输者就要被淘汰了。
而且经过实验发现当 window 区配置为总容量的 1%，剩余的 99%当中的 80%分给 protected 区，20%分给 probation 区时，这时整体性能和命中率表现得最好，所以 caffeine 默认的比例设置就是这个。
不过这个比例 caffeine 会在运行时根据统计数据（statistics）去动态调整，如果你的应用程序的缓存随着时间变化比较快的话，那么增加 window 区的比例可以提高命中率，相反缓存都是比较固定不变的话，增加 main cache 区（protected 区 +probation 区）的比例会有较好的效果。
下面我们看看上面说到的淘汰策略是怎么实现的：
一般缓存对读写操作后都有后续的一系列“维护”操作，caffeine 也不例外，这些操作都在<code>maintenance</code>方法，我们将要说到的淘汰策略也在里面。
这方法比较重要，下面也会提到，所以这里只先说跟“淘汰策略”有关的<code>evictentries</code>和<code>climb</code>。
先说一下 caffeine 对上面说到的 w-tinylfu 策略的实现用到的数据结构：
以及默认比例设置（意思看注释）
重点来了，<code>evictentries</code>和<code>climb</code>方法：
<code>evictfrommain</code>方法：
<code>climb</code>方法主要是用来调整 window size 的，使得 caffeine 可以适应你的应用类型（如 olap 或 oltp）表现出最佳的命中率。
下图是官方测试的数据：
我们看看 window size 的调整是怎么实现的。
调整时用到的默认比例数据：
下面分别展开每个方法来解释：
以上，是 caffeine 的 w-tinylfu 策略的设计原理及代码实现解析。
一般的缓存每次对数据处理完之后（读的话，已经存在则直接返回，不存在则 load 数据，保存，再返回；写的话，则直接插入或更新），但是因为要维护一些淘汰策略，则需要一些额外的操作，诸如：
计算和比较数据的是否过期
统计频率（像 lfu 或其变种）
维护 read queue 和 write queue
淘汰符合条件的数据
等等。。。
这种数据的读写伴随着缓存状态的变更，guava cache 的做法是把这些操作和读写操作放在一起，在一个同步加锁的操作中完成，虽然 guava cache 巧妙地利用了 jdk 的 concurrenthashmap（分段锁或者无锁 cas）来降低锁的密度，达到提高并发度的目的。但是，对于一些热点数据，这种做法还是避免不了频繁的锁竞争。caffeine 借鉴了数据库系统的 wal（write-ahead logging）思想，即先写日志再执行操作，这种思想同样适合缓存的，执行读写操作时，先把操作记录在缓冲区，然后在合适的时机异步、批量地执行缓冲区中的内容。但在执行缓冲区的内容时，也是需要在缓冲区加上同步锁的，不然存在并发问题，只不过这样就可以把对锁的竞争从缓存数据转移到对缓冲区上。
在 caffeine 的内部实现中，为了很好的支持不同的 features（如 eviction，removal，refresh，statistics，cleanup，policy 等等），扩展了很多子类，它们共同的父类是<code>boundedlocalcache</code>，而<code>readbuffer</code>就是作为它们共有的属性，即都是用一样的 readbuffer，看定义：
上面提到 caffeine 对每次缓存的读操作都会触发<code>afterread</code>
重点看<code>boundedbuffer</code>
它是一个 striped、非阻塞、有界限的 buffer，继承于<code>stripedbuffer</code>类。下面看看<code>stripedbuffer</code>的实现：
这个<code>stripedbuffer</code>设计的思想是跟<code>striped64</code>类似的，通过扩展结构把竞争热点分离。
具体实现是这样的，<code>stripedbuffer</code>维护一个<code>buffer[]</code>数组，每个元素就是一个<code>ringbuffer</code>，每个线程用自己<code>threadlocalrandomprobe</code>属性作为 hash 值，这样就相当于每个线程都有自己“专属”的<code>ringbuffer</code>，就不会产生竞争啦，而不是用 key 的<code>hashcode</code>作为 hash 值，因为会产生热点数据问题。
看看<code>stripedbuffer</code>的属性
<code>offer</code>方法，当没初始化或存在竞争时，则扩容为 2 倍。
实际是调用<code>ringbuffer</code>的 offer 方法，把数据追加到<code>ringbuffer</code>后面。
最后看看<code>ringbuffer</code>，注意<code>ringbuffer</code>是<code>boundedbuffer</code>的内部类。
注意，ring buffer 的 size（固定是 16 个）是不变的，变的是 head 和 tail 而已。
总的来说<code>readbuffer</code>有如下特点：
使用 <code>striped-ringbuffer</code>来提升对 buffer 的读写
用 thread 的 hash 来避开热点 key 的竞争
允许写入的丢失
<code>writebuffer</code>跟<code>readbuffer</code>不一样，主要体现在使用场景的不一样。本来缓存的一般场景是读多写少的，读的并发会更高，且 afterread 显得没那么重要，允许延迟甚至丢失。写不一样，写<code>afterwrite</code>不允许丢失，且要求尽量马上执行。caffeine 使用mpsc（multiple producer / single consumer）作为 buffer 数组，实现在<code>mpscgrowablearrayqueue</code>类，它是仿照<code>jctools</code>的<code>mpscgrowablearrayqueue</code>来写的。
mpsc 允许无锁的高并发写入，但只允许一个消费者，同时也牺牲了部分操作。
mpsc 我打算另外分析，这里不展开了。
除了支持<code>expireafteraccess</code>和<code>expireafterwrite</code>之外（guava cache 也支持这两个特性），caffeine 还支持<code>expireafter</code>。因为<code>expireafteraccess</code>和<code>expireafterwrite</code>都只能是固定的过期时间，这可能满足不了某些场景，譬如记录的过期时间是需要根据某些条件而不一样的，这就需要用户自定义过期时间。
先看看<code>expireafter</code>的用法
通过自定义过期时间，使得不同的 key 可以动态的得到不同的过期时间。
注意，我把<code>expireafteraccess</code>和<code>expireafterwrite</code>注释了，因为这两个特性不能跟<code>expireafter</code>一起使用。
而当使用了<code>expireafter</code>特性后，caffeine 会启用一种叫“时间轮”的算法来实现这个功能。更多关于时间轮的介绍，可以看我的文章hashedwheeltimer 时间轮原理分析[6]。
好，重点来了，为什么要用时间轮？
对<code>expireafteraccess</code>和<code>expireafterwrite</code>的实现是用一个<code>accessorderdeque</code>双端队列，它是 fifo 的，因为它们的过期时间是固定的，所以在队列头的数据肯定是最早过期的，要处理过期数据时，只需要首先看看头部是否过期，然后再挨个检查就可以了。但是，如果过期时间不一样的话，这需要对<code>accessorderqueue</code>进行排序&插入，这个代价太大了。于是，caffeine 用了一种更加高效、优雅的算法-时间轮。
时间轮的结构：
因为在我的对时间轮分析的文章里已经说了时间轮的原理和机制了，所以我就不展开 caffeine 对时间轮的实现了。
caffeine 对时间轮的实现在<code>timerwheel</code>，它是一种多层时间轮（hierarchical timing wheels ）。
看看元素加入到时间轮的<code>schedule</code>方法：
caffeine 还有其他的优化性能的手段，如使用软引用和弱引用、消除伪共享、<code>completablefuture</code>异步等等。
caffeien 是一个优秀的本地缓存，通过使用 w-tinylfu 算法， 高性能的 readbuffer 和 writebuffer，时间轮算法等，使得它拥有高性能，高命中率（near optimal），低内存占用等特点。
tinylfu 论文[7]
design of a modern cache[8]
design of a modern cache—part deux[9]
caffeine 的 github[10]
[1]
caffeine: https://github.com/ben-manes/caffeine
[2]
这里: https://albenw.github.io/posts/df42dc84/
[3]
benchmarks: https://github.com/ben-manes/caffeine/wiki/benchmarks
[4]
官方api说明文档: https://github.com/ben-manes/caffeine/wiki
[5]
这里: https://github.com/ben-manes/caffeine/wiki/guava
[6]
hashedwheeltimer时间轮原理分析: https://albenw.github.io/posts/ec8df8c/
[7]
tinylfu论文: https://arxiv.org/abs/1512.00727
[8]
design of a modern cache: http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html
[9]
design of a modern cache—part deux: http://highscalability.com/blog/2019/2/25/design-of-a-modern-cachepart-deux.html
[10]
caffeine的github: https://github.com/ben-manes/caffeine
https://mp.weixin.qq.com/s/cjkpezazpg55u6zilfttsg