来源：https://albenw.github.io/posts/a4ae1aa2/ 概要 Caffeine是一个高性能，高命中率，低内存占用，near optimal 的本地缓存，简单来说它是Guava Cache的优化加强版，有些文章把Caffeine称为“新一代的缓存”、“现代缓存之王”。本文将重点讲解Caffeine的高性能设计，以及对应部分的源码分析。 与Guava Cache比较 大家都知道，Spring5即将放弃掉Guava Cache作为缓存机制，而改用Caffeine作为新的本地Cache的组件，这对于Caffeine来说是一个很大的肯定。为什么Spring会这样做呢？其实在Caffeine的Benchmarks里给出了好靓仔的数据，对读和写的场景，还有跟其他几个缓存工具进行了比较，Caffeine的性能都表现很突出。 使用Caffeine Caffeine为了方便大家使用以及从Guava Cache切换过来（很有针对性啊～），借鉴了Guava Cache大部分的概念（诸如核心概念Cache、LoadingCache、CacheLoader、CacheBuilder等等），对于Caffeine的理解只要把它当作Guava Cache就可以了。 使用上，大家只要把Caffeine的包引进来，然后换一下cache的实现类，基本应该就没问题了。这对与已经使用过Guava Cache的同学来说没有任何难度，甚至还有一点熟悉的味道，如果你之前没有使用过Guava Cache，可以查看Caffeine的官方API说明文档，其中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; } }); 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;} 知道了追加方法，那么读取方法frequency就很容易理解了。 /** * Returns the estimated number of occurrences of an element, up to the maximum (15). * * @param e the element to count occurrences of * @return the estimated number of occurrences of the element; possibly zero but never negative */@NonNegativepublic int frequency(@NonNull E e) { if (isNotInitialized()) { return 0; } //得到hash值，跟上面一样 int hash = spread(e.hashCode()); //得到等分的下标，跟上面一样 int start = (hash & 3) << 2; int frequency = Integer.MAX_VALUE; //循环四次，分别获取在table数组中不同的下标位置 for (int i = 0; i < 4; i++) { int index = indexOf(hash, i); //这个操作就不多说了，其实跟上面incrementAt是一样的，定位到table[index] + 等分的位置，再根据mask取出计数值 int count = (int) ((table[index] >>> ((start + i) << 2)) & 0xfL); //取四个中的较小值 frequency = Math.min(frequency, count); } return frequency;} 通过代码和注释或者读者可能难以理解，下图是我画出来帮助大家理解的结构图。 注意紫色虚线框，其中蓝色小格就是需要计算的位置： 保新机制 为了让缓存保持“新鲜”，剔除掉过往频率很高但之后不经常的缓存，Caffeine有一个Freshness Mechanism。做法很简答，就是当整体的统计计数（当前所有记录的频率统计之和，这个数值内部维护）达到某一个值时，那么所有记录的频率统计除以2。 从上面的代码 //size变量就是所有记录的频率统计之，即每个记录加1，这个size都会加1//sampleSize一个阈值，从FrequencySketch初始化可以看到它的值为maximumSize的10倍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表现的更好。 W-TinyLFU的设计如下所示（两图等价）： 它主要包括两个缓存模块，主缓存是SLRU（Segmented LRU，即分段LRU），SLRU包括一个名为protected和一个名为probation的缓存区。通过增加一个缓存区（即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区）的比例会有较好的效果。 下面我们看看上面说到的淘汰策略是怎么实现的： 一般缓存对读写操作后都有后续的一系列“维护”操作，Caffeine也不例外，这些操作都在maintenance方法，我们将要说到的淘汰策略也在里面。 这方法比较重要，下面也会提到，所以这里只先说跟“淘汰策略”有关的evictEntries和climb。 /** * Performs the pending maintenance work and sets the state flags during processing to avoid * excess scheduling attempts. The read buffer, write buffer, and reference queues are * drained, followed by expiration, and size-based eviction. * * @param task an additional pending task to run, or {@code null} if not present */ @GuardedBy("evictionLock") void maintenance(@Nullable Runnable task) { lazySetDrainStatus(PROCESSING_TO_IDLE); try { drainReadBuffer(); drainWriteBuffer(); if (task != null) { task.run(); } drainKeyReferences(); drainValueReferences(); expireEntries(); //把符合条件的记录淘汰掉 evictEntries(); //动态调整window区和protected区的大小 climb(); } finally { if ((drainStatus() != PROCESSING_TO_IDLE) || !casDrainStatus(PROCESSING_TO_IDLE, IDLE)) { lazySetDrainStatus(REQUIRED); } } } ``` 先说一下Caffeine对上面说到的W-TinyLFU策略的实现用到的数据结构： ``` //最大的个数限制long maximum;//当前的个数long weightedSize;//window区的最大限制long windowMaximum;//window区当前的个数long windowWeightedSize;//protected区的最大限制long mainProtectedMaximum;//protected区当前的个数long mainProtectedWeightedSize;//下一次需要调整的大小（还需要进一步计算）double stepSize;//window区需要调整的大小long adjustment;//命中计数int hitsInSample;//不命中的计数int missesInSample;//上一次的缓存命中率double previousSampleHitRate;final FrequencySketch sketch; //window区的LRU queue（FIFO） final AccessOrderDeque > accessOrderWindowDeque; //probation区的LRU queue（FIFO） final AccessOrderDeque > accessOrderProbationDeque; //protected区的LRU queue（FIFO） final AccessOrderDeque > accessOrderProtectedDeque; 以及默认比例设置（意思看注释） /** The initial percent of the maximum weighted capacity dedicated to the main space. */static final double PERCENT_MAIN = 0.99d;/** The percent of the maximum weighted capacity dedicated to the main's protected space. */static final double PERCENT_MAIN_PROTECTED = 0.80d;/** The difference in hit rates that restarts the climber. */static final double HILL_CLIMBER_RESTART_THRESHOLD = 0.05d;/** The percent of the total size to adapt the window by. */static final double HILL_CLIMBER_STEP_PERCENT = 0.0625d;/** The rate to decrease the step size to adapt by. */static final double HILL_CLIMBER_STEP_DECAY_RATE = 0.98d;/** The maximum number of entries that can be transfered between queues. */ 重点来了，evictEntries和climb方法： /** Evicts entries if the cache exceeds the maximum. */@GuardedBy("evictionLock")void evictEntries() { if (!evicts()) { return; } //淘汰window区的记录 int candidates = evictFromWindow(); //淘汰Main区的记录 evictFromMain(candidates);}/** * Evicts entries from the window space into the main space while the window size exceeds a * maximum. * * @return the number of candidate entries evicted from the window space *///根据W-TinyLFU，新的数据都会无条件的加到admission window//但是window是有大小限制，所以要“定期”做一下“维护”@GuardedBy("evictionLock")int evictFromWindow() { int candidates = 0; //查看window queue的头部节点 Node node = accessOrderWindowDeque().peek(); //如果window区超过了最大的限制，那么就要把“多出来”的记录做处理 …
