Caffeine Cache 高性能 Java 本地緩存組件

不點藍字關(guān)注，我們哪來故事？

一個指導(dǎo)程序員進入大公司/獨角獸?的精品社群，致力于分享職場達人的專業(yè)打法，包括「學(xué)習(xí)路線+簡歷模板+實習(xí)避坑+筆試面試+試用轉(zhuǎn)正+升職加薪+跳槽技巧」。
點這里去了解，劍指大廠吧！







來源：https://www.cnblogs.com/rickiyang/p/11074158.html
我們知道Guava Cache，他的優(yōu)點是封裝了get，put操作；提供線程安全的緩存操作；提供過期策略；提供回收策略；緩存監(jiān)控。當(dāng)緩存的數(shù)據(jù)超過最大值時，使用LRU算法替換。這一篇我們將要談到一個新的本地緩存框架：Caffeine Cache。它也是站在巨人的肩膀上-Guava Cache，借著他的思想優(yōu)化了算法發(fā)展而來。
本篇博文主要介紹Caffine Cache 的使用方式，以及Caffine Cache在SpringBoot中的使用。
|?Caffine Cache 在算法上的優(yōu)點-W-TinyLFU
說到優(yōu)化，Caffine Cache到底優(yōu)化了什么呢？我們剛提到過LRU，常見的緩存淘汰算法還有FIFO，LFU：
FIFO：先進先出，在這種淘汰算法中，先進入緩存的會先被淘汰，會導(dǎo)致命中率很低。
LRU：最近最少使用算法，每次訪問數(shù)據(jù)都會將其放在我們的隊尾，如果需要淘汰數(shù)據(jù)，就只需要淘汰隊首即可。仍然有個問題，如果有個數(shù)據(jù)在 1 分鐘訪問了 1000次，再后 1 分鐘沒有訪問這個數(shù)據(jù)，但是有其他的數(shù)據(jù)訪問，就導(dǎo)致了我們這個熱點數(shù)據(jù)被淘汰。
LFU：最近最少頻率使用，利用額外的空間記錄每個數(shù)據(jù)的使用頻率，然后選出頻率最低進行淘汰。這樣就避免了 LRU 不能處理時間段的問題。
上面三種策略各有利弊，實現(xiàn)的成本也是一個比一個高，同時命中率也是一個比一個好。Guava Cache雖然有這么多的功能，但是本質(zhì)上還是對LRU的封裝，如果有更優(yōu)良的算法，并且也能提供這么多功能，相比之下就相形見絀了。
LFU的局限性?：在 LFU 中只要數(shù)據(jù)訪問模式的概率分布隨時間保持不變時，其命中率就能變得非常高。比如有部新劇出來了，我們使用 LFU 給他緩存下來，這部新劇在這幾天大概訪問了幾億次，這個訪問頻率也在我們的 LFU 中記錄了幾億次。但是新劇總會過氣的，比如一個月之后這個新劇的前幾集其實已經(jīng)過氣了，但是他的訪問量的確是太高了，其他的電視劇根本無法淘汰這個新劇，所以在這種模式下是有局限性。
LRU的優(yōu)點和局限性?：LRU可以很好的應(yīng)對突發(fā)流量的情況，因為他不需要累計數(shù)據(jù)頻率。但LRU通過歷史數(shù)據(jù)來預(yù)測未來是局限的，它會認(rèn)為最后到來的數(shù)據(jù)是最可能被再次訪問的，從而給與它最高的優(yōu)先級。
在現(xiàn)有算法的局限性下，會導(dǎo)致緩存數(shù)據(jù)的命中率或多或少的受損，而命中略又是緩存的重要指標(biāo)。HighScalability網(wǎng)站刊登了一篇文章，由前Google工程師發(fā)明的W-TinyLFU——一種現(xiàn)代的緩存 。Caffine Cache就是基于此算法而研發(fā)。Caffeine 因使用?Window TinyLfu?回收策略，提供了一個近乎最佳的命中率?。
當(dāng)數(shù)據(jù)的訪問模式不隨時間變化的時候，LFU的策略能夠帶來最佳的緩存命中率。然而LFU有兩個缺點：
首先，它需要給每個記錄項維護頻率信息，每次訪問都需要更新，這是個巨大的開銷；
其次，如果數(shù)據(jù)訪問模式隨時間有變，LFU的頻率信息無法隨之變化，因此早先頻繁訪問的記錄可能會占據(jù)緩存，而后期訪問較多的記錄則無法被命中。
因此，大多數(shù)的緩存設(shè)計都是基于LRU或者其變種來進行的。相比之下，LRU并不需要維護昂貴的緩存記錄元信息，同時也能夠反應(yīng)隨時間變化的數(shù)據(jù)訪問模式。然而，在許多負(fù)載之下，LRU依然需要更多的空間才能做到跟LFU一致的緩存命中率。因此，一個“現(xiàn)代”的緩存，應(yīng)當(dāng)能夠綜合兩者的長處。
TinyLFU維護了近期訪問記錄的頻率信息，作為一個過濾器，當(dāng)新記錄來時，只有滿足TinyLFU要求的記錄才可以被插入緩存。如前所述，作為現(xiàn)代的緩存，它需要解決兩個挑戰(zhàn)：
一個是如何避免維護頻率信息的高開銷；
另一個是如何反應(yīng)隨時間變化的訪問模式。
首先來看前者，TinyLFU借助了數(shù)據(jù)流Sketching技術(shù)，Count-Min Sketch顯然是解決這個問題的有效手段，它可以用小得多的空間存放頻率信息，而保證很低的False Positive Rate。但考慮到第二個問題，就要復(fù)雜許多了，因為我們知道，任何Sketching數(shù)據(jù)結(jié)構(gòu)如果要反應(yīng)時間變化都是一件困難的事情，在Bloom Filter方面，我們可以有Timing Bloom Filter，但對于CMSketch來說，如何做到Timing CMSketch就不那么容易了。TinyLFU采用了一種基于滑動窗口的時間衰減設(shè)計機制，借助于一種簡易的reset操作：每次添加一條記錄到Sketch的時候，都會給一個計數(shù)器上加1，當(dāng)計數(shù)器達到一個尺寸W的時候，把所有記錄的Sketch數(shù)值都除以2，該reset操作可以起到衰減的作用 。
W-TinyLFU主要用來解決一些稀疏的突發(fā)訪問元素。在一些數(shù)目很少但突發(fā)訪問量很大的場景下，TinyLFU將無法保存這類元素，因為它們無法在給定時間內(nèi)積累到足夠高的頻率。因此W-TinyLFU就是結(jié)合LFU和LRU，前者用來應(yīng)對大多數(shù)場景，而LRU用來處理突發(fā)流量。
在處理頻率記錄的方案中，你可能會想到用hashMap去存儲，每一個key對應(yīng)一個頻率值。那如果數(shù)據(jù)量特別大的時候，是不是這個hashMap也會特別大呢。由此可以聯(lián)想到 Bloom Filter，對于每個key，用n個byte每個存儲一個標(biāo)志用來判斷key是否在集合中。原理就是使用k個hash函數(shù)來將key散列成一個整數(shù)。
在W-TinyLFU中使用Count-Min Sketch記錄我們的訪問頻率，而這個也是布隆過濾器的一種變種。如下圖所示:


如果需要記錄一個值，那我們需要通過多種Hash算法對其進行處理hash，然后在對應(yīng)的hash算法的記錄中+1，為什么需要多種hash算法呢？由于這是一個壓縮算法必定會出現(xiàn)沖突，比如我們建立一個byte的數(shù)組，通過計算出每個數(shù)據(jù)的hash的位置。比如張三和李四，他們兩有可能hash值都是相同，比如都是1那byte[1]這個位置就會增加相應(yīng)的頻率，張三訪問1萬次，李四訪問1次那byte[1]這個位置就是1萬零1，如果取李四的訪問評率的時候就會取出是1萬零1，但是李四命名只訪問了1次啊，為了解決這個問題，所以用了多個hash算法可以理解為long[][]二維數(shù)組的一個概念，比如在第一個算法張三和李四沖突了，但是在第二個，第三個中很大的概率不沖突，比如一個算法大概有1%的概率沖突，那四個算法一起沖突的概率是1%的四次方。通過這個模式我們?nèi)±钏牡脑L問率的時候取所有算法中，李四訪問最低頻率的次數(shù)。所以他的名字叫Count-Min Sketch。
|?使用
Caffeine Cache 的github地址：
https://github.com/ben-manes/caffeine
目前的最新版本是：
<dependency>
????<groupId>com.github.ben-manes.caffeinegroupId>
????<artifactId>caffeineartifactId>
????<version>2.6.2version>
dependency>
緩存填充策略
Caffeine Cache提供了三種緩存填充策略：手動、同步加載和異步加載。
手動加載
在每次get key的時候指定一個同步的函數(shù)，如果key不存在就調(diào)用這個函數(shù)生成一個值。
/**
?????*?手動加載
?????*?@param?key
?????*?@return
?????*/
public?Object?manulOperator(String?key)?{
????Cache?cache?=?Caffeine.newBuilder()
????????.expireAfterWrite(1,?TimeUnit.SECONDS)
????????.expireAfterAccess(1,?TimeUnit.SECONDS)
????????.maximumSize(10)
????????.build();
????//如果一個key不存在，那么會進入指定的函數(shù)生成value
????Object?value?=?cache.get(key,?t?->?setValue(key).apply(key));
????cache.put("hello",value);

????//判斷是否存在如果不存返回null
????Object?ifPresent?=?cache.getIfPresent(key);
????//移除一個key
????cache.invalidate(key);
????return?value;
}

public?Function?setValue(String?key){
????return?t?->?key?+?"value";
}
同步加載
構(gòu)造Cache時候，build方法傳入一個CacheLoader實現(xiàn)類。實現(xiàn)load方法，通過key加載value。
/**
?????*?同步加載
?????*?@param?key
?????*?@return
?????*/
public?Object?syncOperator(String?key){
????LoadingCache?cache?=?Caffeine.newBuilder()
????????.maximumSize(100)
????????.expireAfterWrite(1,?TimeUnit.MINUTES)
????????.build(k?->?setValue(key).apply(key));
????return?cache.get(key);
}

public?Function?setValue(String?key){
????return?t?->?key?+?"value";
}
異步加載
AsyncLoadingCache是繼承自LoadingCache類的，異步加載使用Executor去調(diào)用方法并返回一個CompletableFuture。異步加載緩存使用了響應(yīng)式編程模型。
如果要以同步方式調(diào)用時，應(yīng)提供CacheLoader。要以異步表示時，應(yīng)該提供一個AsyncCacheLoader，并返回一個CompletableFuture。
?/**
?????*?異步加載
?????*
?????*?@param?key
?????*?@return
?????*/
public?Object?asyncOperator(String?key){
????AsyncLoadingCache?cache?=?Caffeine.newBuilder()
????????.maximumSize(100)
????????.expireAfterWrite(1,?TimeUnit.MINUTES)
????????.buildAsync(k?->?setAsyncValue(key).get());

????return?cache.get(key);
}

public?CompletableFuture