簡(jiǎn)介
Caffeine，是一種建立在java8基礎(chǔ)上的高性能緩存框架订雾。它是一種本地緩存晶默，功能類似Guava cache，可以理解為其是Guava cache的一個(gè)加強(qiáng)版本为流。 下圖是其官網(wǎng)給出的性能比較：
本文主要介紹了Caffeine的基本用法并對(duì)其實(shí)現(xiàn)原理進(jìn)行一些探討呕屎。
功能介紹
Caffeine的Api幾乎和Guava cache一樣，如果對(duì)Guava cache比較熟悉的話敬察，那么熟悉Caffeine的api將會(huì)很容易秀睛，下面簡(jiǎn)單的展示一下Caffeine的用法。
緩存加載方式
Caffeine提供了三種使用方式：手動(dòng)加載莲祸、同步加載蹂安、異步加載方式椭迎，如下所示：
/**
* 手動(dòng)加載
*/
@Test
public void testManual() {
Cache<String, String> cache = Caffeine.newBuilder()
.expireAfterWrite(10, TimeUnit.MINUTES)
.maximumSize(10_000)
.build();
cache.get("key", k -> createExpensiveGraph("key"));
}
/**
* 同步加載
*/
@Test
public void testLoading() {
LoadingCache<String, String> cache = Caffeine.newBuilder()
.maximumSize(10_000)
.expireAfterWrite(10, TimeUnit.MINUTES)
.build(this::createExpensiveGraph);
System.out.println(cache.get("key"));
}
/**
* 異步加載
*/
@Test
public void testAsyn() throws ExecutionException, InterruptedException {
AsyncCache<String,String> cache = Caffeine.newBuilder()
.expireAfterWrite(10, TimeUnit.MINUTES)
.maximumSize(10_000)
.buildAsync();
CompletableFuture<String> graph = cache.get("test", k -> createExpensiveGraph("test"));
System.out.println(graph.get());
}
緩存淘汰策略
與Guava cache一樣，也提供了三種緩存淘汰策略田盈，分別是基于大小畜号、時(shí)間、引用方式允瞧。
LoadingCache<String,String> cache = Caffeine.newBuilder()
//基于數(shù)量的配置
.maximumSize(1000)
//基于權(quán)重
.maximumWeight(1000)
//指定計(jì)算權(quán)重的方式
.weigher(this::caculateWeight)
//指定緩存在寫入多久后失效简软。
.expireAfterWrite(1000,TimeUnit.SECONDS)
//指定緩存在訪問(wèn)多久后失效。
.expireAfterAccess(1000,TimeUnit.SECONDS)
//多種時(shí)間過(guò)期策略組合使用述暂。
.expireAfter(new Expiry<String, String>() {
public long expireAfterCreate(Key key, Graph graph, long currentTime) {
long seconds = graph.creationDate().plusHours(5)
.minus(System.currentTimeMillis(), ChronoUnit.MILLIS).getSeconds();
return TimeUnit.SECONDS.toNanos(seconds);
}
public long expireAfterUpdate(Key key, Graph graph,long currentTime, long currentDuration) {
return currentDuration;
}
public long expireAfterRead(Key key, Graph graph,long currentTime, long currentDuration) {
return currentDuration;
}
})
.build(this::load);
異步刷新
Caffeine和Guava cache一樣痹升，也提供了異步刷新的功能，通過(guò)refreshAfterWrite方法指定刷新的時(shí)間畦韭，實(shí)例如下所示：
LoadingCache<String,String> cache = Caffeine.newBuilder()
.expireAfterWrite(10,TimeUnit.SECONDS)
.refreshAfterWrite(2,TimeUnit.SECONDS)
.executor(Executors.newFixedThreadPool(1))
.build(this::load);
Caffeine的刷新是異步執(zhí)行的疼蛾，默認(rèn)的刷新線程池是ForkJoinPool.commonPool()，也可以通過(guò)executor方法指定為其它線程池艺配。刷新操作的觸發(fā)時(shí)機(jī)是在數(shù)據(jù)讀取之后察郁，通過(guò)判斷當(dāng)前時(shí)間減去數(shù)據(jù)的創(chuàng)建時(shí)間是否大于refreshAfterWrite指定的時(shí)間，如果大于則進(jìn)行刷新操作转唉。一般refreshAfterWrite常和expireAfterWrite結(jié)合使用绳锅，需要注意的是：refreshAfterWrite設(shè)置的時(shí)間要小于expireAfterWrite，因?yàn)樵谧x取數(shù)據(jù)的時(shí)候首先通過(guò)expireAfterWrite來(lái)判斷數(shù)據(jù)有沒有失效酝掩，數(shù)據(jù)失效后會(huì)同步更新數(shù)據(jù)，如果refreshAfterWrite時(shí)間大于expireAfterWrite眷柔，那么refresh操作永遠(yuǎn)不會(huì)執(zhí)行到期虾，設(shè)置了refreshAfterWrite也沒有任何意義。
緩存的清除策略
Caffeine的緩存清除是惰性的驯嘱，可能發(fā)生在讀請(qǐng)求后或者寫請(qǐng)求后谁榜，比如說(shuō)有一條數(shù)據(jù)過(guò)期后侈沪，不會(huì)立即刪除，可能在下一次讀/寫操作后觸發(fā)刪除。如果讀請(qǐng)求和寫請(qǐng)求比較少即舌，但想要盡快的刪掉cache中過(guò)期的數(shù)據(jù)的話，可以通過(guò)增加定時(shí)器的方法恰响，定時(shí)執(zhí)行cache.cleanUp()方法税肪，觸發(fā)緩存清除操作。
其它功能
Caffeine還提供了其它的功能负乡，如：緩存監(jiān)控牍白、事件監(jiān)聽等功能，感興趣的同學(xué)可以去其wiki查看抖棘。
原理
高效的緩存淘汰算法
緩存淘汰算法的作用是在有限的資源內(nèi)茂腥，盡可能識(shí)別出哪些數(shù)據(jù)在短時(shí)間會(huì)被重復(fù)利用狸涌，從而提高緩存的命中率。常用的緩存淘汰算法有LRU最岗、LFU帕胆、FIFO等。
LRU（Least Recently Used）算法認(rèn)為最近訪問(wèn)過(guò)的數(shù)據(jù)將來(lái)被訪問(wèn)的幾率也更高般渡。LRU通常使用鏈表來(lái)實(shí)現(xiàn)懒豹，如果數(shù)據(jù)添加或者被訪問(wèn)到則把數(shù)據(jù)移動(dòng)到鏈表的頭部，鏈表的頭部為熱數(shù)據(jù)诊杆，鏈表的尾部如冷數(shù)據(jù)歼捐，當(dāng)數(shù)據(jù)滿時(shí)，淘汰尾部的數(shù)據(jù)晨汹。其實(shí)現(xiàn)比較簡(jiǎn)單豹储，但是存在一些問(wèn)題，如：當(dāng)存在數(shù)據(jù)遍歷時(shí)淘这，會(huì)導(dǎo)致LRU命中率急劇下降剥扣，緩存污染情況比較嚴(yán)重。LRU算法也并非一無(wú)是處铝穷，其在突發(fā)流量下表現(xiàn)良好钠怯。
LFU（Least Frequently Used）算法根據(jù)數(shù)據(jù)的歷史訪問(wèn)頻率來(lái)淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)過(guò)去被訪問(wèn)多次曙聂，那么將來(lái)被訪問(wèn)的頻率也更高”晦炊。根據(jù)LFU的思想，如果想要實(shí)現(xiàn)這個(gè)算法宁脊，需要額外的一套存儲(chǔ)用來(lái)存每個(gè)元素的訪問(wèn)次數(shù)断国，會(huì)造成內(nèi)存資源的浪費(fèi)。
Caffeine采用了一種結(jié)合LRU榆苞、LFU優(yōu)點(diǎn)的算法：W-TinyLFU稳衬，其特點(diǎn)：高命中率、低內(nèi)存占用坐漏。在搞懂W-TinyLFU算法之前薄疚，首先了解一下TinyLFU算法：TinyLFU是一種為了解決傳統(tǒng)LFU算法空間存儲(chǔ)比較大的問(wèn)題LFU算法，它可以在較大訪問(wèn)量的場(chǎng)景下近似的替代LFU的數(shù)據(jù)統(tǒng)計(jì)部分赊琳，它的原理有些類似BloomFilter街夭。首先回顧一下BloomFilter原理：在BloomFilter中，使用一個(gè)大的bit數(shù)組用于存儲(chǔ)所有key慨畸，每一個(gè)key通過(guò)多次不同的hash計(jì)算來(lái)映射數(shù)組的不同bit位莱坎，如果key存在將對(duì)應(yīng)的bit位設(shè)置為1，這樣就可以通過(guò)少量的存儲(chǔ)空間進(jìn)行大量的數(shù)據(jù)過(guò)濾寸士。在TinyLFU中檐什，把多個(gè)bit位看做一個(gè)整體碴卧，用于統(tǒng)計(jì)一個(gè)key的使用頻率，TinyFLU中的key也是通過(guò)多次不同的hash計(jì)算來(lái)映射多個(gè)不同的bit組乃正。在讀取時(shí)住册，取映射的所有值中的最小的值作為key的使用頻率，TinyLFU算法如下圖所示：
在Caffeine中瓮具，維護(hù)了一個(gè)4-bit CountMinSketch用來(lái)記錄key的使用頻率荧飞。4-bit也就意味著，統(tǒng)計(jì)的key最大使用頻率為15名党，具體的實(shí)現(xiàn)邏輯可以參考源代碼中的FrequencySketch類叹阔。
TinyLFU有一個(gè)缺點(diǎn)，在應(yīng)對(duì)突發(fā)流量的時(shí)候传睹，可能由于沒有及時(shí)構(gòu)建足夠的頻率數(shù)據(jù)來(lái)保證自己駐留在緩存中耳幢，從而導(dǎo)致緩存的命中率下降，為了解決這個(gè)問(wèn)題欧啤，產(chǎn)生了W-TinyLFU算法睛藻。W-TinyLFU由兩部分組成，主緩存使用SLRU回收策略和TinyLFU回收策略邢隧，而窗口緩存使用沒有任何回收策略的LRU回收策略店印，增加的窗口緩存用于應(yīng)對(duì)突發(fā)流量的問(wèn)題，如下圖所示：
窗口緩存占用總大小的1%左右倒慧，主緩存占用99%按摘。Caffeine可以根據(jù)工作負(fù)載特性動(dòng)態(tài)調(diào)整窗口和主空間的大小，如果新增數(shù)據(jù)頻率比較高纫谅，大窗口更受歡迎;如果新增數(shù)據(jù)頻率偏小院峡，小窗口更受歡迎。主緩存內(nèi)部包含兩個(gè)部分系宜，一部分為Protected，用于存比較熱的數(shù)據(jù)发魄，它占用主緩存80%空間盹牧；另一部分是Probation，用于存相對(duì)比較冷的數(shù)據(jù)励幼，占用主緩存20%空間汰寓，數(shù)據(jù)可以在這兩部分空間里面互相轉(zhuǎn)移。
緩存淘汰的過(guò)程：新添加的數(shù)據(jù)首先放入窗口緩存中苹粟，如果窗口緩存滿了有滑，則把窗口緩存淘汰的數(shù)據(jù)轉(zhuǎn)移到主緩存Probation區(qū)域中。如果這時(shí)主緩存也滿了嵌削，則從主緩存的Probation區(qū)域淘汰數(shù)據(jù)毛好，把這條數(shù)據(jù)稱為受害者望艺，從窗口緩存淘汰的數(shù)據(jù)稱為候選人。接下來(lái)候選人和受害者進(jìn)行一次pk肌访，來(lái)決定去留找默。pk的方式是通過(guò)TinyFLU記錄的訪問(wèn)頻率來(lái)進(jìn)行判斷，具體過(guò)程如下：
- 首先獲取候選人和受害者的頻率
- 如果候選人大于受害者吼驶，則淘汰受害者
- 如果候選人頻率小于等于5惩激，則淘汰候選人
- 其余情況隨機(jī)處理。
Caffeine中的pk代碼：
boolean admit(K candidateKey, K victimKey) {
int victimFreq = frequencySketch().frequency(victimKey);
int candidateFreq = frequencySketch().frequency(candidateKey);
if (candidateFreq > victimFreq) {
return true;
} else if (candidateFreq <= 5) {
// The maximum frequency is 15 and halved to 7 after a reset to age the history. An attack
// exploits that a hot candidate is rejected in favor of a hot victim. The threshold of a warm
// candidate reduces the number of random acceptances to minimize the impact on the hit rate.
return false;
}
int random = ThreadLocalRandom.current().nextInt();
return ((random & 127) == 0);
}
讀寫優(yōu)化
Caffeine的底層數(shù)據(jù)存儲(chǔ)采用ConcurrentHashMap蟹演。因?yàn)镃affeine面向JDK8风钻，在jdk8中ConcurrentHashMap增加了紅黑樹，在hash沖突嚴(yán)重時(shí)也能有良好的讀性能酒请。
Caffeine的緩存清除動(dòng)作是觸發(fā)式的骡技，它可能發(fā)生在讀、寫請(qǐng)求后蚌父。這個(gè)動(dòng)作在Caffeine中是異步執(zhí)行的哮兰，默認(rèn)執(zhí)行的線程池是ForkJoinPool.commonPool()。相比較Guava cache的同步執(zhí)行清除操作苟弛，Caffeine的異步執(zhí)行能夠提高讀寫請(qǐng)求的效率喝滞。針對(duì)讀寫請(qǐng)求后的異步操作（清除緩存、調(diào)整LRU隊(duì)列順序等操作）膏秫，Caffeine分別使用了ReadBuffer和WriterBuffer右遭。使用Buffer一方面能夠合并操作，另一方面可以避免鎖爭(zhēng)用的問(wèn)題缤削。
在時(shí)間的過(guò)期策略中窘哈，Caffeine針對(duì)不同的過(guò)期策略采用不同的實(shí)現(xiàn)：針對(duì)寫后過(guò)期，維護(hù)了一個(gè)寫入順序隊(duì)列亭敢；針對(duì)讀后過(guò)期滚婉，維護(hù)了一個(gè)讀取順序隊(duì)列；針對(duì)expireAfter指定的多種時(shí)間組合過(guò)期策略中帅刀，采用了二維時(shí)間輪來(lái)實(shí)現(xiàn)让腹。Caffeine使用上述這些策略，來(lái)提高其在緩存過(guò)期清除時(shí)的效率扣溺。
總結(jié)
本文對(duì)Caffeine的使用和原理進(jìn)行了簡(jiǎn)單的介紹骇窍，其在細(xì)節(jié)設(shè)計(jì)上有很多優(yōu)化，如果想要更加深入的了解內(nèi)部設(shè)計(jì)細(xì)節(jié)锥余，可以參考下方給出的參考資料腹纳。Caffeine是一個(gè)非常不錯(cuò)的緩存框架，無(wú)論是在性能方面，還是在API方面嘲恍，都要比Guava cache要優(yōu)秀一些足画。如果在新的項(xiàng)目中要使用local cache的話，可以優(yōu)先考慮使用Caffeine蛔钙。對(duì)于老的項(xiàng)目锌云，如果使用了Guava cache，想要升級(jí)為Caffeine的話吁脱，可以使用Caffeine提供的Guava cache適配器桑涎，方便的進(jìn)行切換。
