一、簡介

Caffeine 是基于Java 8 開發(fā)的、提供了近乎最佳命中率的高性能本地緩存組件，Spring5 開始不再支持 Guava Cache，改為使用 Caffeine。

下面是 Caffeine 官方測試報告。

由上面三幅圖可見：不管在并發(fā)讀、并發(fā)寫還是并發(fā)讀寫的場景下，Caffeine 的性能都大幅領(lǐng)先于其他本地開源緩存組件。

本文先介紹 Caffeine 實現(xiàn)原理，再講解如何在項目中使用 Caffeine 。

?二、Caffeine 原理

2.1 淘汰算法

2.1.1 常見算法

對于 Java 進程內(nèi)緩存我們可以通過 HashMap 來實現(xiàn)。不過，Java 進程內(nèi)存是有限的，不可能無限地往里面放緩存對象。這就需要有合適的算法輔助我們淘汰掉使用價值相對不高的對象，為新進的對象留有空間。常見的緩存淘汰算法有 FIFO、LRU、LFU。

FIFO(First In First Out)：先進先出。它是優(yōu)先淘汰掉最先緩存的數(shù)據(jù)、是最簡單的淘汰算法。缺點是如果先緩存的數(shù)據(jù)使用頻率比較高的話，那么該數(shù)據(jù)就不停地進進出出，因此它的緩存命中率比較低。

LRU(Least Recently Used)：最近最久未使用。它是優(yōu)先淘汰掉最久未訪問到的數(shù)據(jù)。缺點是不能很好地應(yīng)對偶然的突發(fā)流量。比如一個數(shù)據(jù)在一分鐘內(nèi)的前59秒訪問很多次，而在最后1秒沒有訪問，但是有一批冷門數(shù)據(jù)在最后一秒進入緩存，那么熱點數(shù)據(jù)就會被沖刷掉。

LFU(Least Frequently Used)：最近最少頻率使用。它是優(yōu)先淘汰掉最不經(jīng)常使用的數(shù)據(jù)，需要維護一個表示使用頻率的字段。

主要有兩個缺點：

一、如果訪問頻率比較高的話，頻率字段會占據(jù)一定的空間；

二、無法合理更新新上的熱點數(shù)據(jù)，比如某個歌手的老歌播放歷史較多，新出的歌如果和老歌一起排序的話，就永無出頭之日。

2.1.2 W-TinyLFU 算法

Caffeine 使用了 W-TinyLFU 算法，解決了 LRU 和LFU上述的缺點。W-TinyLFU 算法由論文《TinyLFU: A Highly Efficient Cache Admission Policy》提出。

它主要干了兩件事：

一、采用 Count–Min Sketch 算法降低頻率信息帶來的內(nèi)存消耗；

二、維護一個PK機制保障新上的熱點數(shù)據(jù)能夠緩存。

如下圖所示，Count–Min Sketch 算法類似布隆過濾器 (Bloom filter)思想，對于頻率統(tǒng)計我們其實不需要一個精確值。存儲數(shù)據(jù)時，對key進行多次 hash 函數(shù)運算后，二維數(shù)組不同位置存儲頻率（Caffeine 實際實現(xiàn)的時候是用一維 long 型數(shù)組，每個 long 型數(shù)字切分成16份，每份4bit，默認(rèn)15次為最高訪問頻率，每個key實際 hash 了四次，落在不同 long 型數(shù)字的16份中某個位置）。讀取某個key的訪問次數(shù)時，會比較所有位置上的頻率值，取最小值返回。對于所有key的訪問頻率之和有個最大值，當(dāng)達到最大值時，會進行reset即對各個緩存key的頻率除以2。

如下圖緩存訪問頻率存儲主要分為兩大部分，即 LRU 和 Segmented LRU 。新訪問的數(shù)據(jù)會進入第一個 LRU，在 Caffeine 里叫 WindowDeque。當(dāng) WindowDeque 滿時，會進入 Segmented LRU 中的 ProbationDeque，在后續(xù)被訪問到時，它會被提升到 ProtectedDeque。當(dāng) ProtectedDeque 滿時，會有數(shù)據(jù)降級到 ProbationDeque 。數(shù)據(jù)需要淘汰的時候，對 ProbationDeque 中的數(shù)據(jù)進行淘汰。具體淘汰機制：取ProbationDeque 中的隊首和隊尾進行 PK，隊首數(shù)據(jù)是最先進入隊列的，稱為受害者，隊尾的數(shù)據(jù)稱為攻擊者，比較兩者 頻率大小，大勝小汰。

總的來說，通過 reset 衰減，避免歷史熱點數(shù)據(jù)由于頻率值比較高一直淘汰不掉，并且通過對訪問隊列分成三段，這樣避免了新加入的熱點數(shù)據(jù)早早地被淘汰掉。

2.2 高性能讀寫

Caffeine 認(rèn)為讀操作是頻繁的，寫操作是偶爾的，讀寫都是異步線程更新頻率信息。

2.2.1 讀緩沖

傳統(tǒng)的緩存實現(xiàn)將會為每個操作加鎖，以便能夠安全的對每個訪問隊列的元素進行排序。一種優(yōu)化方案是將每個操作按序加入到緩沖區(qū)中進行批處理操作。讀完把數(shù)據(jù)放到環(huán)形隊列 RingBuffer 中，為了減少讀并發(fā)，采用多個 RingBuffer，每個線程都有對應(yīng)的 RingBuffer。環(huán)形隊列是一個定長數(shù)組，提供高性能的能力并最大程度上減少了 GC所帶來的性能開銷。數(shù)據(jù)丟到隊列之后就返回讀取結(jié)果，類似于數(shù)據(jù)庫的WAL機制，和ConcurrentHashMap 讀取數(shù)據(jù)相比，僅僅多了把數(shù)據(jù)放到隊列這一步。異步線程并發(fā)讀取 RingBuffer 數(shù)組，更新訪問信息，這邊的線程池使用的是下文實戰(zhàn)小節(jié)講的 Caffeine 配置參數(shù)中的 executor。

2.2.2 寫緩沖

與讀緩沖類似，寫緩沖是為了儲存寫事件。讀緩沖中的事件主要是為了優(yōu)化驅(qū)逐策略的命中率，因此讀緩沖中的事件完整程度允許一定程度的有損。但是寫緩沖并不允許數(shù)據(jù)的丟失，因此其必須實現(xiàn)為一個安全的隊列。Caffeine 寫是把數(shù)據(jù)放入MpscGrowableArrayQueue 阻塞隊列中，它參考了JCTools里的MpscGrowableArrayQueue ，是針對 MPSC- 多生產(chǎn)者單消費者（Multi-Producer