Caffeine本地缓存

简单说，Caffine 是一款高性能的本地缓存组件
由下面三幅图可见：不管在并发读、并发写还是并发读写的场景下，Caffeine 的性能都大幅领先于其他本地开源缓存组件

它是优先淘汰掉最先缓存的数据、是最简单的淘汰算法。缺点是如果先缓存的数据使用频率比较高的话，那么该数据就不停地进进出出，因此它的缓存命中率比较低

它是优先淘汰掉最久未访问到的数据。缺点是不能很好地应对偶然的突发流量。比如一个数据在一分钟内的前 59 秒访问很多次，而在最后 1 秒没有访问，但是有一批冷门数据在最后一秒进入缓存，那么热点数据就会被冲刷掉

最近最少频率使用。它是优先淘汰掉最不经常使用的数据，需要维护一个表示使用频率的字段，缺点主要有两个：

• 需要给每个记录项维护频率信息，每次访问都需要更新，这是个巨大的开销
• 对突发性的稀疏流量响应迟钝，因为历史的数据已经积累了很多次计数，新来的数据肯定是排在后续的

比如某个歌手的老歌播放历史较多，新出的歌如果和老歌一起排序的话，就永无出头之日

问题：如果老板让你统计一个实时的数据流中元素出现的频率，并且准备随时回答某个元素出现的频率，不需要的精确的计数，那该怎么办？

直觉告诉我们可能需要一个巨大的 HashMap 来统计各个元素的出现频率，但由于不同的元素的个数可能非常大，以至于是个天文数字，要求的内存可能会非常大，从而不切实际。同时，又要求我们实时计算，实时回答，当 HashMap 的冲突很高时，最坏的情况的时间复杂度可能无法满足实时的要求

Count-min Sketch算法是一个可以用来计数的算法，在数据大小非常大时，一种高效的计数算法，通过牺牲准确性提高的效率

基本的思路：

创建一个长度为 x 的数组，用来计数，初始化每个元素的计数值为 0；对于一个新来的元素，哈希到 0 到 x 之间的一个数，比如哈希值为 i，作为数组的位置索引；这时，数组对应的位置索引 i 的计数值加 1；那么，这时要查询某个元素出现的频率，只要简单的返回这个元素哈希望后对应的数组的位置索引的计数值即可；考虑到使用哈希，会有冲突，即不同的元素哈希到同一个数组的位置索引，这样，频率的统计都会偏大

如何优化

使用多个数组，和多个哈希函数，来计算一个元素对应的数组的位置索引；那么，要查询某个元素的频率时，返回这个元素在不同数组中的计数值中的最小值即可；

Count–Min Sketch 算法类似布隆过滤器 (Bloom Filter）思想，对于频率统计我们其实不需要一个精确值。存储数据时，对 key 进行多次 hash 函数运算后，二维数组不同位置存储频率（Caffeine 实际实现的时候是用一维 long 型数组，每个 long 型数字切分成 16 份，每份 4 bit，默认 15 次为最高访问频率，每个 key 实际 hash 了四次，落在不同 long 型数字的 16 份中某个位置）。读取某个 key 的访问次数时，会比较所有位置上的频率值，取最小值返回。为了解决数据访问模式随时间变化的问题，也为了避免计数无限增长，对于所有 key 的访问频率之和有个最大值，当达到最大值时，会进行 reset 即对各个缓存 key 的频率除以 2

对同一对象的 “稀疏突发” 的场景下，TinyLFU 会出现问题。在这种情况下，新突发的 key 无法建立足够的频率以保留在缓存中，从而导致不断的 cache miss。通过设计称为 Window Tiny LFU（W-TinyLFU）的策略（包含两个缓存区域），Caffeine 解决了这个问题

缓存访问频率存储主要分为两大部分，即 LRU 和 Segmented LRU 。新访问的数据会进入第一个 LRU，在 Caffeine 里叫 WindowDeque。当 WindowDeque 满时，会进入 Segmented LRU 中的 ProbationDeque，在后续被访问到时，它会被提升到 ProtectedDeque。当 ProtectedDeque 满时，会有数据降级到 ProbationDeque 。数据需要淘汰的时候，对 ProbationDeque 中的数据进行淘汰。具体淘汰机制：取 ProbationDeque 中的队首和队尾进行 PK，队首数据是最先进入队列的，称为受害者，队尾的数据称为攻击者，比较两者频率大小，大胜小汰；

下次看下这个视频：哔哩哔哩搜 Window-TinyLFU