新一代快取-Caffeine
簡介
Caffeine,是一種建立在java8基礎上的高效能快取框架。它是一種本地快取,功能類似Guava cache,可以理解為其是Guava cache的一個加強版本。 下圖是其官網給出的效能比較:
本文主要介紹了Caffeine的基本用法並對其實現原理進行一些探討。
功能介紹
Caffeine的Api幾乎和Guava cache一樣,如果對Guava cache比較熟悉的話,那麼熟悉Caffeine的api將會很容易,下面簡單的展示一下Caffeine的用法。
快取載入方式
Caffeine提供了三種使用方式:手動載入、同步載入、非同步載入方式,如下所示:
/**
* 手動載入
*/
@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一樣,也提供了三種快取淘汰策略,分別是基於大小、時間、引用方式。
LoadingCache<String,String> cache = Caffeine.newBuilder()
//基於數量的配置
.maximumSize(1000)
//基於權重
.maximumWeight(1000)
//指定計算權重的方式
.weigher(this::caculateWeight)
//指定快取在寫入多久後失效。
.expireAfterWrite(1000,TimeUnit.SECONDS)
//指定快取在訪問多久後失效。
.expireAfterAccess(1000,TimeUnit.SECONDS)
//多種時間過期策略組合使用。
.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一樣,也提供了非同步重新整理的功能,通過refreshAfterWrite方法指定重新整理的時間,例項如下所示:
LoadingCache<String,String> cache = Caffeine.newBuilder()
.expireAfterWrite(10,TimeUnit.SECONDS)
.refreshAfterWrite(2,TimeUnit.SECONDS)
.executor(Executors.newFixedThreadPool(1))
.build(this::load);
Caffeine的重新整理是非同步執行的,預設的重新整理執行緒池是ForkJoinPool.commonPool(),也可以通過executor方法指定為其它執行緒池。重新整理操作的觸發時機是在資料讀取之後,通過判斷當前時間減去資料的建立時間是否大於refreshAfterWrite指定的時間,如果大於則進行重新整理操作。一般refreshAfterWrite常和expireAfterWrite結合使用,需要注意的是:refreshAfterWrite設定的時間要小於expireAfterWrite,因為在讀取資料的時候首先通過expireAfterWrite來判斷資料有沒有失效,資料失效後會同步更新資料,如果refreshAfterWrite時間大於expireAfterWrite,那麼refresh操作永遠不會執行到,設定了refreshAfterWrite也沒有任何意義。
快取的清除策略
Caffeine的快取清除是惰性的,可能發生在讀請求後或者寫請求後,比如說有一條資料過期後,不會立即刪除,可能在下一次讀/寫操作後觸發刪除。如果讀請求和寫請求比較少,但想要儘快的刪掉cache中過期的資料的話,可以通過增加定時器的方法,定時執行cache.cleanUp()方法,觸發快取清除操作。
其它功能
Caffeine還提供了其它的功能,如:快取監控、事件監聽等功能,感興趣的同學可以去其wiki檢視。
原理
高效的快取淘汰演算法
快取淘汰演算法的作用是在有限的資源內,儘可能識別出哪些資料在短時間會被重複利用,從而提高快取的命中率。常用的快取淘汰演算法有LRU、LFU、FIFO等。
LRU(Least Recently Used)演算法認為最近訪問過的資料將來被訪問的機率也更高。LRU通常使用連結串列來實現,如果資料新增或者被訪問到則把資料移動到連結串列的頭部,連結串列的頭部為熱資料,連結串列的尾部如冷資料,當資料滿時,淘汰尾部的資料。其實現比較簡單,但是存在一些問題,如:當存在資料遍歷時,會導致LRU命中率急劇下降,快取汙染情況比較嚴重。LRU演算法也並非一無是處,其在突發流量下表現良好。
LFU(Least Frequently Used)演算法根據資料的歷史訪問頻率來淘汰資料,其核心思想是“如果資料過去被訪問多次,那麼將來被訪問的頻率也更高”。根據LFU的思想,如果想要實現這個演算法,需要額外的一套儲存用來存每個元素的訪問次數,會造成記憶體資源的浪費。
Caffeine採用了一種結合LRU、LFU優點的演算法:W-TinyLFU,其特點:高命中率、低記憶體佔用。在搞懂W-TinyLFU演算法之前,首先了解一下TinyLFU演算法:TinyLFU是一種為了解決傳統LFU演算法空間儲存比較大的問題LFU演算法,它可以在較大訪問量的場景下近似的替代LFU的資料統計部分,它的原理有些類似BloomFilter。首先回顧一下BloomFilter原理:在BloomFilter中,使用一個大的bit陣列用於儲存所有key,每一個key通過多次不同的hash計算來對映陣列的不同bit位,如果key存在將對應的bit位設定為1,這樣就可以通過少量的儲存空間進行大量的資料過濾。在TinyLFU中,把多個bit位看做一個整體,用於統計一個key的使用頻率,TinyFLU中的key也是通過多次不同的hash計算來對映多個不同的bit組。在讀取時,取對映的所有值中的最小的值作為key的使用頻率,TinyLFU演算法如下圖所示:
在Caffeine中,維護了一個4-bit CountMinSketch用來記錄key的使用頻率。4-bit也就意味著,統計的key最大使用頻率為15,具體的實現邏輯可以參考原始碼中的FrequencySketch類。
TinyLFU有一個缺點,在應對突發流量的時候,可能由於沒有及時構建足夠的頻率資料來保證自己駐留在快取中,從而導致快取的命中率下降,為了解決這個問題,產生了W-TinyLFU演算法。W-TinyLFU由兩部分組成,主快取使用SLRU回收策略和TinyLFU回收策略,而視窗快取使用沒有任何回收策略的LRU回收策略,增加的視窗快取用於應對突發流量的問題,如下圖所示:
視窗快取佔用總大小的1%左右,主快取佔用99%。Caffeine可以根據工作負載特性動態調整視窗和主空間的大小,如果新增資料頻率比較高,大視窗更受歡迎;如果新增資料頻率偏小,小視窗更受歡迎。主快取內部包含兩個部分,一部分為Protected,用於存比較熱的資料,它佔用主快取80%空間;另一部分是Probation,用於存相對比較冷的資料,佔用主快取20%空間,資料可以在這兩部分空間裡面互相轉移。
快取淘汰的過程:新新增的資料首先放入視窗快取中,如果視窗快取滿了,則把視窗快取淘汰的資料轉移到主快取Probation區域中。如果這時主快取也滿了,則從主快取的Probation區域淘汰資料,把這條資料稱為受害者,從視窗快取淘汰的資料稱為候選人。接下來候選人和受害者進行一次pk,來決定去留。pk的方式是通過TinyFLU記錄的訪問頻率來進行判斷,具體過程如下:
1. 首先獲取候選人和受害者的頻率 2. 如果候選人大於受害者,則淘汰受害者 3. 如果候選人頻率小於等於5,則淘汰候選人 4. 其餘情況隨機處理。
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) {
return false;
}
int random = ThreadLocalRandom.current().nextInt();
return ((random & 127) == 0);
}
讀寫優化
Caffeine的底層資料儲存採用ConcurrentHashMap。因為Caffeine面向JDK8,在jdk8中ConcurrentHashMap增加了紅黑樹,在hash衝突嚴重時也能有良好的讀效能。
Caffeine的快取清除動作是觸發式的,它可能發生在讀、寫請求後。這個動作在Caffeine中是非同步執行的,預設執行的執行緒池是ForkJoinPool.commonPool()。相比較Guava cache的同步執行清除操作,Caffeine的非同步執行能夠提高讀寫請求的效率。針對讀寫請求後的非同步操作(清除快取、調整LRU佇列順序等操作),Caffeine分別使用了ReadBuffer和WriterBuffer。使用Buffer一方面能夠合併操作,另一方面可以避免鎖爭用的問題。
在時間的過期策略中,Caffeine針對不同的過期策略採用不同的實現:針對寫後過期,維護了一個寫入順序佇列;針對讀後過期,維護了一個讀取順序佇列;針對expireAfter指定的多種時間組合過期策略中,採用了二維時間輪來實現。Caffeine使用上述這些策略,來提高其在快取過期清除時的效率。
總結
本文對Caffeine的使用和原理進行了簡單的介紹,其在細節設計上有很多優化,如果想要更加深入的瞭解內部設計細節,可以參考下方給出的參考資料。Caffeine是一個非常不錯的快取框架,無論是在效能方面,還是在API方面,都要比Guava cache要優秀一些。如果在新的專案中要使用local cache的話,可以優先考慮使用Caffeine。對於老的專案,如果使用了Guava cache,想要升級為Caffeine的話,可以使用Caffeine提供的Guava cache介面卡,方便的進行切換。
參考
• https://github.com/ben-manes/caffeine/wiki • https://arxiv.org/pdf/1512.00727.pdf • https://github.com/google/guava/wiki/CachesExplained