深入源码分析，缓存之王 Caffeine 为何这么猛?

vlambda
2020-12-26

深入源码分析，缓存之王 Caffeine 为何这么猛?

老家浙江东海边，靠海吃海，目前经营一个小品牌，让普通人吃到最新鲜的海鲜。有兴趣可以点击了解：《》🐟🐟🐟

Caffeine^[1]是一个高性能，高命中率，低内存占用，near optimal 的本地缓存，简单来说它是 Guava Cache 的优化加强版，有些文章把 Caffeine 称为“新一代的缓存”、“现代缓存之王”。

本文将重点讲解 Caffeine 的高性能设计，以及对应部分的源码分析。

与 Guava Cache 比较

如果你对 Guava Cache 还不理解的话，可以点击这里^[2]来看一下我之前写过关于 Guava Cache 的文章。

大家都知道，Spring5 即将放弃掉 Guava Cache 作为缓存机制，而改用 Caffeine 作为新的本地 Cache 的组件，这对于 Caffeine 来说是一个很大的肯定。为什么 Spring 会这样做呢？其实在 Caffeine 的Benchmarks^[3]里给出了好靓仔的数据，对读和写的场景，还有跟其他几个缓存工具进行了比较，Caffeine 的性能都表现很突出。

使用 Caffeine

Caffeine 为了方便大家使用以及从 Guava Cache 切换过来（很有针对性啊～），借鉴了 Guava Cache 大部分的概念（诸如核心概念Cache、LoadingCache、CacheLoader、CacheBuilder等等），对于 Caffeine 的理解只要把它当作 Guava Cache 就可以了。

使用上，大家只要把 Caffeine 的包引进来，然后换一下 cache 的实现类，基本应该就没问题了。这对与已经使用过 Guava Cache 的同学来说没有任何难度，甚至还有一点熟悉的味道，如果你之前没有使用过 Guava Cache，可以查看 Caffeine 的官方 API 说明文档^[4]，其中Population，Eviction，Removal，Refresh，Statistics，Cleanup，Policy等等这些特性都是跟 Guava Cache 基本一样的。

下面给出一个例子说明怎样创建一个 Cache：

private static LoadingCache<String, String> cache = Caffeine.newBuilder()
            //最大个数限制
            .maximumSize(256L)
            //初始化容量
            .initialCapacity(1)
            //访问后过期（包括读和写）
            .expireAfterAccess(2, TimeUnit.DAYS)
            //写后过期
            .expireAfterWrite(2, TimeUnit.HOURS)
            //写后自动异步刷新
            .refreshAfterWrite(1, TimeUnit.HOURS)
            //记录下缓存的一些统计数据，例如命中率等
            .recordStats()
            //cache对缓存写的通知回调
            .writer(new CacheWriter<Object, Object>() {
                @Override
                public void write(@NonNull Object key, @NonNull Object value) {
                    log.info("key={}, CacheWriter write", key);
                }

                @Override
                public void delete(@NonNull Object key, @Nullable Object value, @NonNull RemovalCause cause) {
                    log.info("key={}, cause={}, CacheWriter delete", key, cause);
                }
            })
            //使用CacheLoader创建一个LoadingCache
            .build(new CacheLoader<String, String>() {
                //同步加载数据
                @Nullable
                @Override
                public String load(@NonNull String key) throws Exception {
                    return "value_" + key;
                }

                //异步加载数据
                @Nullable
                @Override
                public String reload(@NonNull String key, @NonNull String oldValue) throws Exception {
                    return "value_" + key;
                }
            });

更多从 Guava Cache 迁移过来的使用说明，请看这里^[5]

Caffeine 的高性能设计

判断一个缓存的好坏最核心的指标就是命中率，影响缓存命中率有很多因素，包括业务场景、淘汰策略、清理策略、缓存容量等等。如果作为本地缓存，它的性能的情况，资源的占用也都是一个很重要的指标。下面

我们来看看 Caffeine 在这几个方面是怎么着手的，如何做优化的。

（注：本文不会分析 Caffeine 全部源码，只会对核心设计的实现进行分析，但我建议读者把 Caffeine 的源码都涉猎一下，有个 overview 才能更好理解本文。如果你看过 Guava Cache 的源码也行，代码的数据结构和处理逻辑很类似的。

源码基于：caffeine-2.8.0.jar）

W-TinyLFU 整体设计

上面说到淘汰策略是影响缓存命中率的因素之一，一般比较简单的缓存就会直接用到 LFU(Least Frequently Used，即最不经常使用) 或者LRU(Least Recently Used，即最近最少使用) ，而 Caffeine 就是使用了 W-TinyLFU 算法。

W-TinyLFU 看名字就能大概猜出来，它是 LFU 的变种，也是一种缓存淘汰算法。那为什么要使用 W-TinyLFU 呢？

LRU 和 LFU 的缺点

LRU 实现简单，在一般情况下能够表现出很好的命中率，是一个“性价比”很高的算法，平时也很常用。虽然 LRU 对突发性的稀疏流量（sparse bursts）表现很好，但同时也会产生缓存污染，举例来说，如果偶然性的要对全量数据进行遍历，那么“历史访问记录”就会被刷走，造成污染。
如果数据的分布在一段时间内是固定的话，那么 LFU 可以达到最高的命中率。但是 LFU 有两个缺点，第一，它需要给每个记录项维护频率信息，每次访问都需要更新，这是个巨大的开销；第二，对突发性的稀疏流量无力，因为前期经常访问的记录已经占用了缓存，偶然的流量不太可能会被保留下来，而且过去的一些大量被访问的记录在将来也不一定会使用上，这样就一直把“坑”占着了。

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

TinyLFU

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

解决第一个问题是采用了 Count–Min Sketch 算法。

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

下图是 TinyLFU 设计图（来自官方）

统计频率 Count–Min Sketch 算法

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

没错，将要介绍的 Count–Min Sketch 的原理跟 Bloom Filter 一样，只不过 Bloom Filter 只有 0 和 1 的值，那么你可以把 Count–Min Sketch 看作是“数值”版的 Bloom Filter。

更多关于 Count–Min Sketch 的介绍请自行搜索。

在 TinyLFU 中，近似频率的统计如下图所示：

对一个 key 进行多次 hash 函数后，index 到多个数组位置后进行累加，查询时取多个值中的最小值即可。

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方法里有一句：

frequencySketch().increment(key);

这句就是追加记录的频率，下面我们看看具体实现

//FrequencySketch的一些属性

//种子数
static final long[] SEED = { // A mixture of seeds from FNV-1a, CityHash, and Murmur3
    0xc3a5c85c97cb3127L, 0xb492b66fbe98f273L, 0x9ae16a3b2f90404fL, 0xcbf29ce484222325L};
static final long RESET_MASK = 0x7777777777777777L;
static final long ONE_MASK = 0x1111111111111111L;

int sampleSize;
//为了快速根据hash值得到table的index值的掩码
//table的长度size一般为2的n次方，而tableMask为size-1，这样就可以通过&操作来模拟取余操作，速度快很多，老司机都知道
int tableMask;
//存储数据的一维long数组
long[] table;
int size;

/**
 * Increments the popularity of the element if it does not exceed the maximum (15). The popularity
 * of all elements will be periodically down sampled when the observed events exceeds a threshold.
 * This process provides a frequency aging to allow expired long term entries to fade away.
 *
 * @param e the element to add
 */
public void increment(@NonNull E e) {
  if (isNotInitialized()) {
    return;
  }

  //根据key的hashCode通过一个哈希函数得到一个hash值
  //本来就是hashCode了，为什么还要再做一次hash？怕原来的hashCode不够均匀分散，再打散一下。
  int hash = spread(e.hashCode());
  //这句光看有点难理解
  //就如我刚才说的，Caffeine把一个long的64bit划分成16个等分，每一等分4个bit。
  //这个start就是用来定位到是哪一个等分的，用hash值低两位作为随机数，再左移2位，得到一个小于16的值
  int start = (hash & 3) << 2;

  //indexOf方法的意思就是，根据hash值和不同种子得到table的下标index
  //这里通过四个不同的种子，得到四个不同的下标index
  int index0 = indexOf(hash, 0);
  int index1 = indexOf(hash, 1);
  int index2 = indexOf(hash, 2);
  int index3 = indexOf(hash, 3);

  //根据index和start(+1, +2, +3)的值，把table[index]对应的等分追加1
  //这个incrementAt方法有点难理解，看我下面的解释
  boolean added = incrementAt(index0, start);
  added |= incrementAt(index1, start + 1);
  added |= incrementAt(index2, start + 2);
  added |= incrementAt(index3, start + 3);

  //这个reset等下说
  if (added && (++size == sampleSize)) {
    reset();
  }
}

/**
 * Increments the specified counter by 1 if it is not already at the maximum value (15).
 *
 * @param i the table index (16 counters)
 * @param j the counter to increment
 * @return if incremented
 */
boolean incrementAt(int i, int j) {
  //这个j表示16个等分的下标，那么offset就是相当于在64位中的下标（这个自己想想）
  int offset = j << 2;
  //上面提到Caffeine把频率统计最大定为15，即0xfL
  //mask就是在64位中的掩码，即1111后面跟很多个0
  long mask = (0xfL << offset);
  //如果&的结果不等于15，那么就追加1。等于15就不会再加了
  if ((table[i] & mask) != mask) {
    table[i] += (1L << offset);
    return true;
  }
  return false;
}

/**
 * Returns the table index for the counter at the specified depth.
 *
 * @param item the element's hash
 * @param i the counter depth
 * @return the table index
 */
int indexOf(int item, int i) {
  long hash = SEED[i] * item;
  hash += hash >>> 32;
  return ((int) hash) & tableMask;
}

/**
 * Applies a supplemental hash function to a given hashCode, which defends against poor quality
 * hash functions.
 */
int spread(int x) {
  x = ((x >>> 16) ^ x) * 0x45d9f3b;
  x = ((x >>> 16) ^ x) * 0x45d9f3b;
  return (x >>> 16) ^ x;
}