来源: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区超过了最大的限制,那么就要把“多出来”的记录做处理 …