W-TinyLFU

我们有三种常见的缓存驱逐策略：

  • FIFO:先进先出，在这种淘汰算法中，先进入缓存的会先被淘汰。这种可谓是最简单的了，但是会导致我们命中率很低。试想一下我们如果有个访问频率很高的数据是所有数据第一个访问的，而那些不是很高的是后面再访问的，那这样就会把我们的首个数据但是他的访问频率很高给挤出。
  • LRU:最近最少使用算法。在这种算法中避免了上面的问题，每次访问数据都会将其放在我们的队尾，如果需要淘汰数据，就只需要淘汰队首即可。但是这个依然有个问题，如果有个数据在1个小时的前59分钟访问了1万次(可见这是个热点数据),再后一分钟没有访问这个数据，但是有其他的数据访问，就导致了我们这个热点数据被淘汰。
  • LFU:最近最少频率使用。在这种算法中又对上面进行了优化，利用额外的空间记录每个数据的使用频率，然后选出频率最低进行淘汰。这样就避免了LRU不能处理时间段的问题。

LRU 的问题在于，如果在某个数据在前9分钟访问了1万次，最近1分钟没有访问，那么依然会认为该 key 并不热门而有可能被驱逐。

LFU 的问题在于，经常会有一些数据在某时刻非常极其热门，但之后一直没人访问，例如因为某些原因被隐藏的用户动态这类场景。另外，LFU 的频率信息在缓存失效后依旧会存在内存中。

值得注意的一点是，缓存系统的驱逐往往是由于写入而引起的，换句话说，是为了在缓存中，给更加重要的 key 腾出空间，才驱逐出那些没它重要的 key。那么问题来了，无论是 LRU 还是 LFU 的写入过程中，都有一个假设是新来的 key 一定是更重要的，以至于我必须牺牲掉某个已有的 key。但这个假设很可能是不成立的。而且这种方式很容易导致一些冷门数据在短时间过热导致缓存系统迅速驱逐出了原先的那些热门数据。为了解决上述问题，于是就有了 TinyLFU。

TinyLFU 增加写入过滤器，只有当新来的 key 的频率大于需要被驱逐的 key 时，此时才会执行写入，否则只进行频率信息的累加。也就是说所有新的 key 都会有一个被预热的过程才能够「够格」被写入缓存中。

但此时会存在的一个问题是，当有突发性的稀疏流量（sparse bursts）进来时，他们会由于一直无法建立足够的频率使得自己被缓存系统而接纳，从而导致击穿了缓存。为了解决这个问题，于是又有了 W-TinyLFU。

W-TinyLFU 算法吸收了上述算法的优点，在 TinyLFU 前面放了一个基于 LRU 的 Window Cache，从而可以使得前面提到的突发性稀疏流量会缓存在 Window Cache 里，只有在 Window Cache 里被淘汰的缓存才会过继给后面的 TinyLFU。

TinyLFU && W-TinyLFU 算法是由 Gil Einziger、Roy Friedman 和 Ben Manes 三人在 15 年共同写的论文：TinyLFU: A Highly Efficient Cache Admission Policy 所提出来的，后来 Ben Manes 还依照这个算法写了一个 Java 领域备受欢迎的缓存系统 Caffeine。

Caffeine的整体结构:

窗口缓存占用总大小的1%左右，主缓存占用99%。Caffeine可以根据工作负载特性动态调整窗口和主空间的大小，如果新增数据频率比较高，大窗口更受欢迎;如果新增数据频率偏小，小窗口更受欢迎。主缓存内部包含两个部分，一部分为Protected，用于存比较热的数据，它占用主缓存80%空间；另一部分是Probation，用于存相对比较冷的数据，占用主缓存20%空间，数据可以在这两部分空间里面互相转移。

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

频率记录

首先要说到的就是频率记录的问题，我们要实现的目标是利用有限的空间可以记录随时间变化的访问频率。在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来举例。

  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,简称1As1加1，然后在3As2加1，在4As3加1，在0As4加1。

这个时候有人会质疑频率最大为15的这个是否太小？

为了避免一些短时间热度的 key 一直残留在缓存中，每隔一个时间间隔，还需要将所有网格计数器衰减一半。

在这个算法中，比如size等于100，如果他全局提升了1000次就会全局除以2衰减，衰减之后也可以继续增加，这个算法在W-TinyLFU的论文中证明了其可以较好的适应时间段的访问频率。

读写性能

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

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

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

读写有不同的队列，在caffeine中认为缓存读比写多很多，所以对于写操作是所有线程共享一个Ringbuffer。

对于读操作比写操作更加频繁，进一步减少竞争，其为每个线程配备了一个RingBuffer：

数据淘汰策略

在caffeine所有的数据都在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。

对于发生数据淘汰的时候，会从Probation中进行淘汰，会把Probation队列中的数据队头称为受害者，这个队头肯定是最早进入的，按照LRU队列的算法的话那他其实他就应该被淘汰，但是在这里只能叫他受害者，这个队列是缓刑队列，代表马上要给他行刑了。这里会取出Probation队列中的队尾叫候选者，也叫攻击者。这里受害者会和攻击者做PK，通过我们的Count-Min Sketch中的记录的频率数据有以下几个判断:

  • 如果攻击者大于受害者，那么受害者就直接被淘汰。
  • 如果攻击者<=5，那么直接淘汰攻击者。这个逻辑在他的注释中有解释: 他认为设置一个预热的门槛会让整体命中率更高。
  • 其他情况，随机淘汰。

过期策略

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

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

参考: go cache 实现综述 Go 中的缓存现状 设计实现高性能本地内存缓存 你应该知道的缓存进化史