常用的缓存机制

墨蓝 2022-10-29 15:28 216阅读 0赞

### 文章目录 ###

*   *  1. LRU （Least Recently Used）最近最少使用
     *  2. LFU （Least Frequently Used）最近最不常用使用页面置换
     *  3.比较LRU 和 LFU 的缺点
     *  TinyLFU
     *   *  统计频率Count–Min Sketch 算法
         *  保新机制
         *  Window特性
         *  淘汰策略（eviction policy）
         *  异步的高性能读写
     *  总结

## 1. LRU （Least Recently Used）最近最少使用 ##

核心思想：如果数据最近被访问过，那么将来被访问的可能性也更高。

实现：

1） 新数据插入链表头部；

2） 每当缓存命中，则将命中数据移到链表头部；

3） 当链表满时，将链表尾部数据丢弃。

## 2. LFU （Least Frequently Used）最近最不常用使用页面置换 ##

核心思想：如果数据过去被访问次数最多，那么将来被访问的可能性也更高。

实现：（LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序）

1） 新加入的数据插入队列尾部；

2） 队列中的数据被访问后，引用计数加1，对列重新排序；

3） 当需要淘汰数据时，将队列最后的数据块删除。

## 3.比较LRU 和 LFU 的缺点 ##

LRU 实现简单，在一般情况下能够表现出很好的命中率，是一个“性价比”很高的算法，平时也很常用。虽然 LRU 对突发性的稀疏流量（sparse bursts）表现很好，但同时也会产生缓存污染，举例来说，如果偶然性的要对全量数据进行遍历，那么“历史访问记录”就会被刷走，造成污染。

如果数据的分布在一段时间内是固定的话，那么 LFU 可以达到最高的命中率。但是 LFU 有两个缺点  
第一，它需要给每个记录项维护频率信息，每次访问都需要更新，这是个巨大的开销；  
第二，对突发性的稀疏流量无力，因为前期经常访问的记录已经占用了缓存，偶然的流量不太可能会被保留下来，而且过去的一些大量被访问的记录在将来也不一定会使用上，这样就一直把“坑”占着了。

无论 LRU 还是 LFU 都有其各自的缺点，不过，现在已经有很多针对其缺点而改良、优化出来的变种算法

## TinyLFU ##

TinyLFU 就是其中一个优化算法，它是专门为了解决 LFU 上述提到的两个问题而被设计出来的。

解决第一个问题,即是采用了 Count–Min Sketch 统计频率算法解决记录维护开销大的问题。

解决第二个问题是让记录尽量保持相对的“新鲜”（Freshness Mechanism），并且当有新的记录插入时，可以让它跟老的记录进行“PK”，输者就会被淘汰，这样一些老的、不再需要的记录就会被剔除。

### 统计频率Count–Min Sketch 算法 ###

如何对一个 key 进行统计，但又可以节省空间呢？（不是简单的使用HashMap，这太消耗内存了），注意哦，不需要精确的统计，只需要一个近似值就可以了，怎么样，这样场景是不是很熟悉，如果你是老司机，或许已经联想到布隆过滤器（Bloom Filter）的应用了。

没错，将要介绍的 Count–Min Sketch 的原理跟 Bloom Filter 一样，只不过 Bloom Filter 只有 0 和 1 的值，那么你可以把 Count–Min Sketch 看作是“数值”版的 Bloom Filter,就是布尔型1变更成了数值型频率,这样访问的次数越多它就会自加大于1，越大访问的频率越高

Caffeine 对这个算法的实现在FrequencySketch类。但 Caffeine 对此有进一步的优化，例如 Count–Min Sketch 使用了二维数组，Caffeine 只是用了一个一维的数组；再者，如果是数值类型的话，这个数需要用 int 或 long 来存储，但是 Caffeine 认为缓存的访问频率不需要用到那么大，只需要 15 就足够，一般认为达到 15 次的频率算是很高的了，而且 Caffeine 还有另外一个机制来使得这个频率进行衰退减半（下面就会讲到）。如果最大是 15 的话，那么只需要 4 个 bit 就可以满足了，一个 long 有 64bit，可以存储 16 个这样的统计数，Caffeine 就是这样的设计，使得存储效率提高了 16 倍。

Caffeine 对缓存的读写（afterRead和afterWrite方法）都会调用onAccesss 方法，而onAccess方法里有一句Caffeine 对缓存的读写（afterRead和afterWrite方法）都会调用onAccesss 方法，而onAccess方法里有一句frequencySketch().increment(key);  
这句就是追加记录的频率

### 保新机制 ###

为了让缓存保持“新鲜”，剔除掉过往频率很高但之后不经常的缓存，Caffeine 有一个 Freshness Mechanism。做法很简答，就是当整体的统计计数（当前所有记录的频率统计之和，这个数值内部维护）达到某一个值时，那么所有记录的频率统计除以 2。

if (added && (++size == sampleSize)) {
          reset();
    }

看到reset方法就是做这个事情

/** Reduces every counter by half of its original value. */
    void reset() {
      int count = 0;
      for (int i = 0; i < table.length; i++) {
        count += Long.bitCount(table[i] & ONE_MASK);
        table[i] = (table[i] >>> 1) & RESET_MASK;
      }
      size = (size >>> 1) - (count >>> 2);
    }

关于这个 reset 方法，为什么是除以 2，而不是其他，及其正确性，在最下面的参考资料的 TinyLFU 论文中 3.3 章节给出了数学证明，大家有兴趣可以看看。

### Window特性 ###

Caffeine 通过测试发现 TinyLFU 在面对突发性的稀疏流量（sparse bursts）时表现很差，因为新的记录（new items）还没来得及建立足够的频率就被剔除出去了，这就使得命中率下降。

于是 Caffeine 设计出一种新的 policy，即 Window Tiny LFU（W-TinyLFU），并通过实验和实践发现 W-TinyLFU 比 TinyLFU 表现的更好。

它主要包括两个缓存模块，主缓存是 SLRU（Segmented LRU，即分段 LRU），SLRU 包括一个名为 protected 和一个名为 probation 的缓存区（类似于JVM的分代机制）。通过增加一个缓存区（即 Window Cache），当有新的记录插入时，会先在 window 区呆一下，就可以避免上述说的 sparse bursts 问题。

### 淘汰策略（eviction policy） ###

当 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 区）的比例会有较好的效果。

### 异步的高性能读写 ###

一般的缓存每次对数据处理完之后（读的话，已经存在则直接返回，不存在则 load 数据，保存，再返回；写的话，则直接插入或更新），但是因为要维护一些淘汰策略，则需要一些额外的操作，诸如：

计算和比较数据的是否过期  
统计频率（像 LFU 或其变种）  
维护 read queue 和 write queue  
淘汰符合条件的数据  
等等

这种数据的读写都伴随着缓存状态的变更，Guava Cache 的做法是把这些操作和读写操作放在一起，在一个同步加锁的操作中完成，虽然 Guava Cache 巧妙地利用了 JDK 的 ConcurrentHashMap（分段锁或者无锁 CAS）来降低锁的密度，达到提高并发度的目的。但是，对于一些热点数据，这种做法还是避免不了频繁的锁竞争。Caffeine 借鉴了数据库系统的 WAL（Write-Ahead Logging）思想，即先写日志再执行操作，这种思想同样适合缓存的，执行读写操作时，先把操作记录在缓冲区，然后在合适的时机异步、批量地执行缓冲区中的内容。但在执行缓冲区的内容时，也是需要在缓冲区加上同步锁的，不然存在并发问题，只不过这样就可以把对锁的竞争从缓存数据转移到对缓冲区上。

## 总结 ##

Caffeien 是一个优秀的本地缓存，通过使用 W-TinyLFU 算法， 高性能的 readBuffer 和 WriteBuffer，时间轮算法等，使得它拥有高性能，高命中率（near optimal），低内存占用等特点。