前面剛說到Guava Cache，他的優(yōu)點(diǎn)是封裝了get，put操作；提供線程安全的緩存操作；提供過期策略；提供回收策略；緩存監(jiān)控。當(dāng)緩存的數(shù)據(jù)超過最大值時(shí)，使用LRU算法替換。這一篇我們將要談到一個(gè)新的本地緩存框架：Caffeine Cache。它也是站在巨人的肩膀上-Guava Cache，借著他的思想優(yōu)化了算法發(fā)展而來。

本篇博文主要介紹Caffine Cache 的使用方式，以及Caffine Cache在SpringBoot中的使用。

|?Caffine Cache 在算法上的優(yōu)點(diǎn)-W-TinyLFU

說到優(yōu)化，Caffine Cache到底優(yōu)化了什么呢？我們剛提到過LRU，常見的緩存淘汰算法還有FIFO，LFU：

1. FIFO：先進(jìn)先出，在這種淘汰算法中，先進(jìn)入緩存的會(huì)先被淘汰，會(huì)導(dǎo)致命中率很低。
2. LRU：最近最少使用算法，每次訪問數(shù)據(jù)都會(huì)將其放在我們的隊(duì)首，如果需要淘汰數(shù)據(jù)，就只需要淘汰隊(duì)尾即可。仍然有個(gè)問題，如果有個(gè)數(shù)據(jù)在 1 分鐘訪問了 1000次，再后 1 分鐘沒有訪問這個(gè)數(shù)據(jù)，但是有其他的數(shù)據(jù)訪問，就導(dǎo)致了我們這個(gè)熱點(diǎn)數(shù)據(jù)被淘汰。
3. LFU：最近最少頻率使用，利用額外的空間記錄每個(gè)數(shù)據(jù)的使用頻率，然后選出頻率最低進(jìn)行淘汰。這樣就避免了 LRU 不能處理時(shí)間段的問題。

上面三種策略各有利弊，實(shí)現(xiàn)的成本也是一個(gè)比一個(gè)高，同時(shí)命中率也是一個(gè)比一個(gè)好。Guava Cache雖然有這么多的功能，但是本質(zhì)上還是對(duì)LRU的封裝，如果有更優(yōu)良的算法，并且也能提供這么多功能，相比之下就相形見絀了。

LFU的局限性?：在 LFU 中只要數(shù)據(jù)訪問模式的概率分布隨時(shí)間保持不變時(shí)，其命中率就能變得非常高。比如有部新劇出來了，我們使用 LFU 給他緩存下來，這部新劇在這幾天大概訪問了幾億次，這個(gè)訪問頻率也在我們的 LFU 中記錄了幾億次。但是新劇總會(huì)過氣的，比如一個(gè)月之后這個(gè)新劇的前幾集其實(shí)已經(jīng)過氣了，但是他的訪問量的確是太高了，其他的電視劇根本無法淘汰這個(gè)新劇，所以在這種模式下是有局限性。

LRU的優(yōu)點(diǎn)和局限性?：LRU可以很好的應(yīng)對(duì)突發(fā)流量的情況，因?yàn)樗恍枰塾?jì)數(shù)據(jù)頻率。但LRU通過歷史數(shù)據(jù)來預(yù)測(cè)未來是局限的，它會(huì)認(rèn)為最后到來的數(shù)據(jù)是最可能被再次訪問的，從而給與它最高的優(yōu)先級(jí)。

在現(xiàn)有算法的局限性下，會(huì)導(dǎo)致緩存數(shù)據(jù)的命中率或多或少的受損，而命中略又是緩存的重要指標(biāo)。HighScalability網(wǎng)站刊登了一篇文章，由前Google工程師發(fā)明的W-TinyLFU——一種現(xiàn)代的緩存 。Caffine Cache就是基于此算法而研發(fā)。Caffeine 因使用?Window TinyLfu?回收策略，提供了一個(gè)近乎最佳的命中率?。

當(dāng)數(shù)據(jù)的訪問模式不隨時(shí)間變化的時(shí)候，LFU的策略能夠帶來最佳的緩存命中率。然而LFU有兩個(gè)缺點(diǎn)：

首先，它需要給每個(gè)記錄項(xiàng)維護(hù)頻率信息，每次訪問都需要更新，這是個(gè)巨大的開銷；

其次，如果數(shù)據(jù)訪問模式隨時(shí)間有變，LFU的頻率信息無法隨之變化，因此早先頻繁訪問的記錄可能會(huì)占據(jù)緩存，而后期訪問較多的記錄則無法被命中。

因此，大多數(shù)的緩存設(shè)計(jì)都是基于LRU或者其變種來進(jìn)行的。相比之下，LRU并不需要維護(hù)昂貴的緩存記錄元信息，同時(shí)也能夠反應(yīng)隨時(shí)間變化的數(shù)據(jù)訪問模式。然而，在許多負(fù)載之下，LRU依然需要更多的空間才能做到跟LFU一致的緩存命中率。因此，一個(gè)“現(xiàn)代”的緩存，應(yīng)當(dāng)能夠綜合兩者的長(zhǎng)處。

TinyLFU維護(hù)了近期訪問記錄的頻率信息，作為一個(gè)過濾器，當(dāng)新記錄來時(shí)，只有滿足TinyLFU要求的記錄才可以被插入緩存。如前所述，作為現(xiàn)代的緩存，它需要解決兩個(gè)挑戰(zhàn)：

一個(gè)是如何避免維護(hù)頻率信息的高開銷；

另一個(gè)是如何反應(yīng)隨時(shí)間變化的訪問模式。

首先來看前者，TinyLFU借助了數(shù)據(jù)流Sketching技術(shù)，Count-Min Sketch顯然是解決這個(gè)問題的有效手段，它可以用小得多的空間存放頻率信息，而保證很低的False Positive Rate。但考慮到第二個(gè)問題，就要復(fù)雜許多了，因?yàn)槲覀冎?，任何Sketching數(shù)據(jù)結(jié)構(gòu)如果要反應(yīng)時(shí)間變化都是一件困難的事情，在Bloom Filter方面，我們可以有Timing Bloom Filter，但對(duì)于CMSketch來說，如何做到Timing CMSketch就不那么容易了。TinyLFU采用了一種基于滑動(dòng)窗口的時(shí)間衰減設(shè)計(jì)機(jī)制，借助于一種簡(jiǎn)易的reset操作：每次添加一條記錄到Sketch的時(shí)候，都會(huì)給一個(gè)計(jì)數(shù)器上加1，當(dāng)計(jì)數(shù)器達(dá)到一個(gè)尺寸W的時(shí)候，把所有記錄的Sketch數(shù)值都除以2，該reset操作可以起到衰減的作用 。

W-TinyLFU主要用來解決一些稀疏的突發(fā)訪問元素。在一些數(shù)目很少但突發(fā)訪問量很大的場(chǎng)景下，TinyLFU將無法保存這類元素，因?yàn)樗鼈儫o法在給定時(shí)間內(nèi)積累到足夠高的頻率。因此W-TinyLFU就是結(jié)合LFU和LRU，前者用來應(yīng)對(duì)大多數(shù)場(chǎng)景，而LRU用來處理突發(fā)流量。

在處理頻率記錄的方案中，你可能會(huì)想到用hashMap去存儲(chǔ)，每一個(gè)key對(duì)應(yīng)一個(gè)頻率值。那如果數(shù)據(jù)量特別大的時(shí)候，是不是這個(gè)hashMap也會(huì)特別大呢。由此可以聯(lián)想到 Bloom Filter，對(duì)于每個(gè)key，用n個(gè)byte每個(gè)存儲(chǔ)一個(gè)標(biāo)志用來判斷key是否在集合中。原理就是使用k個(gè)hash函數(shù)來將key散列成一個(gè)整數(shù)。

在W-TinyLFU中使用Count-Min Sketch記錄我們的訪問頻率，而這個(gè)也是布隆過濾器的一種變種。如下圖所示:

如果需要記錄一個(gè)值，那我們需要通過多種Hash算法對(duì)其進(jìn)行處理hash，然后在對(duì)應(yīng)的hash算法的記錄中+1，為什么需要多種hash算法呢？由于這是一個(gè)壓縮算法必定會(huì)出現(xiàn)沖突，比如我們建立一個(gè)byte的數(shù)組，通過計(jì)算出每個(gè)數(shù)據(jù)的hash的位置。比如張三和李四，他們兩有可能hash值都是相同，比如都是1那byte[1]這個(gè)位置就會(huì)增加相應(yīng)的頻率，張三訪問1萬(wàn)次，李四訪問1次那byte[1]這個(gè)位置就是1萬(wàn)零1，如果取李四的訪問評(píng)率的時(shí)候就會(huì)取出是1萬(wàn)零1，但是李四命名只訪問了1次啊，為了解決這個(gè)問題，所以用了多個(gè)hash算法可以理解為long[][]二維數(shù)組的一個(gè)概念，比如在第一個(gè)算法張三和李四沖突了，但是在第二個(gè)，第三個(gè)中很大的概率不沖突，比如一個(gè)算法大概有1%的概率沖突，那四個(gè)算法一起沖突的概率是1%的四次方。通過這個(gè)模式我們?nèi)±钏牡脑L問率的時(shí)候取所有算法中，李四訪問最低頻率的次數(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提供了三種緩存填充策略：手動(dòng)、同步加載和異步加載。

手動(dòng)加載

在每次get key的時(shí)候指定一個(gè)同步的函數(shù)，如果key不存在就調(diào)用這個(gè)函數(shù)生成一個(gè)值。

/**
?????*?手動(dòng)加載
?????*?@param?key
?????*?@return
?????*/
public?Object?manulOperator(String?key)?{
????Cache?cache?=?Caffeine.newBuilder()
????????.expireAfterWrite(1,?TimeUnit.SECONDS)
????????.expireAfterAccess(1,?TimeUnit.SECONDS)
????????.maximumSize(10)
????????.build();
????//如果一個(gè)key不存在，那么會(huì)進(jìn)入指定的函數(shù)生成value
????Object?value?=?cache.get(key,?t?->?setValue(key).apply(key));
????cache.put("hello",value);

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

public?Function?setValue(String?key){
????return?t?->?key?+?"value";
}

同步加載

構(gòu)造Cache時(shí)候，build方法傳入一個(gè)CacheLoader實(shí)現(xiàn)類。實(shí)現(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)用方法并返回一個(gè)CompletableFuture。異步加載緩存使用了響應(yīng)式編程模型。

如果要以同步方式調(diào)用時(shí)，應(yīng)提供CacheLoader。要以異步表示時(shí)，應(yīng)該提供一個(gè)AsyncCacheLoader，并返回一個(gè)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