還在用 Guava Cache？它才是 Java 本地緩存之王！

Guava Cache 的優點是封裝了get，put操作；提供線程安全的緩存操作；提供過期政策；提供回收政策；緩存監控。當緩存的資料超過最大值時，使用LRU算法替換。

這一篇我們将要談到一個新的本地緩存架構：Caffeine Cache。它也是站在巨人的肩膀上-Guava Cache，借着它的思想優化了算法發展而來。

本篇博文主要介紹Caffine Cache 的使用方式。另外，Java 緩存系列面試題和答案我都整理好了，關注下公衆号Java技術棧，在背景回複 "面試" 進行擷取。

1. Caffine Cache 在算法上的優點-W-TinyLFU

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

FIFO：先進先出，在這種淘汰算法中，先進入緩存的會先被淘汰，會導緻命中率很低。

LRU：最近最少使用算法，每次通路資料都會将其放在我們的隊尾，如果需要淘汰資料，就隻需要淘汰隊首即可。仍然有個問題，如果有個資料在 1 分鐘通路了 1000次，再後 1 分鐘沒有通路這個資料，但是有其他的資料通路，就導緻了我們這個熱點資料被淘汰。

LFU：最近最少頻率使用，利用額外的空間記錄每個資料的使用頻率，然後選出頻率最低進行淘汰。這樣就避免了 LRU 不能處理時間段的問題。

上面三種政策各有利弊，實作的成本也是一個比一個高，同時命中率也是一個比一個好。Guava Cache雖然有這麼多的功能，但是本質上還是對LRU的封裝，如果有更優良的算法，并且也能提供這麼多功能，相比之下就相形見绌了。

LFU的局限性：在 LFU 中隻要資料通路模式的機率分布随時間保持不變時，其命中率就能變得非常高。比如有部新劇出來了，我們使用 LFU 給他緩存下來，這部新劇在這幾天大概通路了幾億次，這個通路頻率也在我們的 LFU 中記錄了幾億次。但是新劇總會過氣的，比如一個月之後這個新劇的前幾集其實已經過氣了，但是他的通路量的确是太高了，其他的電視劇根本無法淘汰這個新劇，是以在這種模式下是有局限性。

LRU的優點和局限性：LRU可以很好的應對突發流量的情況，因為他不需要累計資料頻率。但LRU通過曆史資料來預測未來是局限的，它會認為最後到來的資料是最可能被再次通路的，進而給與它最高的優先級。

在現有算法的局限性下，會導緻緩存資料的命中率或多或少的受損，而命中略又是緩存的重要名額。HighScalability網站刊登了一篇文章，由前Google工程師發明的W-TinyLFU——一種現代的緩存。Caffine Cache就是基于此算法而研發。Caffeine 因使用 Window TinyLfu 回收政策，提供了一個近乎最佳的命中率。

當資料的通路模式不随時間變化的時候，LFU的政策能夠帶來最佳的緩存命中率。然而LFU有兩個缺點：

首先，它需要給每個記錄項維護頻率資訊，每次通路都需要更新，這是個巨大的開銷；

其次，如果資料通路模式随時間有變，LFU的頻率資訊無法随之變化，是以早先頻繁通路的記錄可能會占據緩存，而後期通路較多的記錄則無法被命中。

是以，大多數的緩存設計都是基于LRU或者其變種來進行的。相比之下，LRU并不需要維護昂貴的緩存記錄元資訊，同時也能夠反應随時間變化的資料通路模式。然而，在許多負載之下，LRU依然需要更多的空間才能做到跟LFU一緻的緩存命中率。是以，一個“現代”的緩存，應當能夠綜合兩者的長處。

TinyLFU維護了近期通路記錄的頻率資訊，作為一個過濾器，當新記錄來時，隻有滿足TinyLFU要求的記錄才可以被插入緩存。如前所述，作為現代的緩存，它需要解決兩個挑戰：

一個是如何避免維護頻率資訊的高開銷；

另一個是如何反應随時間變化的通路模式。

首先來看前者，TinyLFU借助了資料流Sketching技術，Count-Min Sketch顯然是解決這個問題的有效手段，它可以用小得多的空間存放頻率資訊，而保證很低的False Positive Rate。但考慮到第二個問題，就要複雜許多了，因為我們知道，任何Sketching資料結構如果要反應時間變化都是一件困難的事情，在Bloom Filter方面，我們可以有Timing Bloom Filter，但對于CMSketch來說，如何做到Timing CMSketch就不那麼容易了。TinyLFU采用了一種基于滑動視窗的時間衰減設計機制，借助于一種簡易的reset操作：每次添加一條記錄到Sketch的時候，都會給一個計數器上加1，當計數器達到一個尺寸W的時候，把所有記錄的Sketch數值都除以2，該reset操作可以起到衰減的作用。

W-TinyLFU主要用來解決一些稀疏的突發通路元素。在一些數目很少但突發通路量很大的場景下，TinyLFU将無法儲存這類元素，因為它們無法在給定時間内積累到足夠高的頻率。是以W-TinyLFU就是結合LFU和LRU，前者用來應對大多數場景，而LRU用來處理突發流量。

在處理頻率記錄的方案中，你可能會想到用hashMap去存儲，每一個key對應一個頻率值。那如果資料量特别大的時候，是不是這個hashMap也會特别大呢。由此可以聯想到 Bloom Filter，對于每個key，用n個byte每個存儲一個标志用來判斷key是否在集合中。原理就是使用k個hash函數來将key散列成一個整數。

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

如果需要記錄一個值，那我們需要通過多種Hash算法對其進行處理hash，然後在對應的hash算法的記錄中+1，為什麼需要多種hash算法呢？由于這是一個壓縮算法必定會出現沖突，比如我們建立一個byte的數組，通過計算出每個資料的hash的位置。比如張三和李四，他們兩有可能hash值都是相同，比如都是1那byte[1]這個位置就會增加相應的頻率，張三通路1萬次，李四通路1次那byte[1]這個位置就是1萬零1，如果取李四的通路評率的時候就會取出是1萬零1，但是李四命名隻通路了1次啊，為了解決這個問題，是以用了多個hash算法可以了解為long[][]二維數組的一個概念，比如在第一個算法張三和李四沖突了，但是在第二個，第三個中很大的機率不沖突，比如一個算法大概有1%的機率沖突，那四個算法一起沖突的機率是1%的四次方。通過這個模式我們取李四的通路率的時候取所有算法中，李四通路最低頻率的次數。是以他的名字叫Count-Min Sketch。

2. 使用

Caffeine Cache 的github位址：

https://github.com/ben-manes/caffeine

目前的最新版本是：

<groupId>com.github.ben-manes.caffeine</groupId>

<artifactId>caffeine</artifactId>

</dependency>

2.1 緩存填充政策

Caffeine Cache提供了三種緩存填充政策：手動、同步加載和異步加載。

1.手動加載

在每次get key的時候指定一個同步的函數，如果key不存在就調用這個函數生成一個值。

/**
* 手動加載
* @param key
* @return
*/
public Object manulOperator(String key) {
    Cache<String, Object> cache = Caffeine.newBuilder()
        .expireAfterWrite(1, TimeUnit.SECONDS)
        .expireAfterAccess(1, TimeUnit.SECONDS)
        .maximumSize(10)
        .build();
    //如果一個key不存在，那麼會進入指定的函數生成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<String, Object> setValue(String key){
    return t -> key + "value";
}

2. 同步加載

構造Cache時候，build方法傳入一個CacheLoader實作類。實作load方法，通過key加載value。

/**
* 同步加載
* @param key
* @return
*/
public Object syncOperator(String key){
    LoadingCache<String, Object> cache = Caffeine.newBuilder()
        .maximumSize(100)
        .expireAfterWrite(1, TimeUnit.MINUTES)
        .build(k -> setValue(key).apply(key));
    return cache.get(key);
}

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

3. 異步加載

AsyncLoadingCache是繼承自LoadingCache類的，異步加載使用Executor去調用方法并傳回一個CompletableFuture。異步加載緩存使用了響應式程式設計模型。

如果要以同步方式調用時，應提供CacheLoader。要以異步表示時，應該提供一個AsyncCacheLoader，并傳回一個CompletableFuture。

/**
* 異步加載
*
* @param key
* @return
*/
public Object asyncOperator(String key){
    AsyncLoadingCache<String, Object> cache = Caffeine.newBuilder()
        .maximumSize(100)
        .expireAfterWrite(1, TimeUnit.MINUTES)
        .buildAsync(k -> setAsyncValue(key).get());

    return cache.get(key);
}

public CompletableFuture<Object> setAsyncValue(String key){
    return CompletableFuture.supplyAsync(() -> {
        return key + "value";
    });
}

2.2 回收政策

Caffeine提供了3種回收政策：基于大小回收，基于時間回收，基于引用回收。

1. 基于大小的過期方式

基于大小的回收政策有兩種方式：一種是基于緩存大小，一種是基于權重。

// 根據緩存的計數進行驅逐
// 根據緩存的計數進行驅逐
LoadingCache<String, Object> cache = Caffeine.newBuilder()
    .maximumSize(10000)
    .build(key -> function(key));


// 根據緩存的權重來進行驅逐（權重隻是用于确定緩存大小，不會用于決定該緩存是否被驅逐）
LoadingCache<String, Object> cache1 = Caffeine.newBuilder()
    .maximumWeight(10000)
    .weigher(key -> function1(key))
    .build(key -> function(key));

// 根據緩存的計數進行驅逐

LoadingCache<String, Object> cache = Caffeine.newBuilder()

.maximumSize(10000)

.build(key -> function(key));

// 根據緩存的權重來進行驅逐（權重隻是用于确定緩存大小，不會用于決定該緩存是否被驅逐）

LoadingCache<String, Object> cache1 = Caffeine.newBuilder()

.maximumWeight(10000)

.weigher(key -> function1(key))

// 基于固定的到期政策進行退出
LoadingCache<String, Object> cache = Caffeine.newBuilder()
    .expireAfterAccess(5, TimeUnit.MINUTES)
    .build(key -> function(key));
LoadingCache<String, Object> cache1 = Caffeine.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build(key -> function(key));

// 基于不同的到期政策進行退出
LoadingCache<String, Object> cache2 = Caffeine.newBuilder()
    .expireAfter(new Expiry<String, Object>() {
        @Override
        public long expireAfterCreate(String key, Object value, long currentTime) {
            return TimeUnit.SECONDS.toNanos(seconds);
        }

        @Override
        public long expireAfterUpdate(@Nonnull String s, @Nonnull Object o, long l, long l1) {
            return 0;
        }

        @Override
        public long expireAfterRead(@Nonnull String s, @Nonnull Object o, long l, long l1) {
            return 0;
        }
    }).build(key -> function(key));

Caffeine提供了三種定時驅逐政策：

expireAfterAccess(long, TimeUnit):在最後一次通路或者寫入後開始計時，在指定的時間後過期。假如一直有請求通路該key，那麼這個緩存将一直不會過期。

expireAfterWrite(long, TimeUnit): 在最後一次寫入緩存後開始計時，在指定的時間後過期。

expireAfter(Expiry): 自定義政策，過期時間由Expiry實作獨自計算。

緩存的删除政策使用的是惰性删除和定時删除。這兩個删除政策的時間複雜度都是O(1)。

3. 基于引用的過期方式

Java中四種引用類型

引用類型被垃圾回收時間用途生存時間

強引用 Strong Reference 從來不會對象的一般狀态 JVM停止運作時終止

軟引用 Soft Reference 在記憶體不足時對象緩存記憶體不足時終止

弱引用 Weak Reference 在垃圾回收時對象緩存 gc運作後終止

虛引用 Phantom Reference 從來不會可以用虛引用來跟蹤對象被垃圾回收器回收的活動，當一個虛引用關聯的對象被垃圾收集器回收之前會收到一條系統通知 JVM停止運作時終止

注意：AsyncLoadingCache不支援弱引用和軟引用。

Caffeine.weakKeys()：使用弱引用存儲key。如果沒有其他地方對該key有強引用，那麼該緩存就會被垃圾回收器回收。由于垃圾回收器隻依賴于身份(identity)相等，是以這會導緻整個緩存使用身份 (==) 相等來比較 key，而不是使用 equals()。

Caffeine.weakValues() ：使用弱引用存儲value。如果沒有其他地方對該value有強引用，那麼該緩存就會被垃圾回收器回收。由于垃圾回收器隻依賴于身份(identity)相等，是以這會導緻整個緩存使用身份 (==) 相等來比較 key，而不是使用 equals()。

Caffeine.softValues() ：使用軟引用存儲value。當記憶體滿了過後，軟引用的對象以将使用最近最少使用(least-recently-used ) 的方式進行垃圾回收。由于使用軟引用是需要等到記憶體滿了才進行回收，是以我們通常建議給緩存配置一個使用記憶體的最大值。 softValues() 将使用身份相等(identity) (==) 而不是equals() 來比較值。

Caffeine.weakValues()和Caffeine.softValues()不可以一起使用。

3. 移除事件監聽

還在用 Guava Cache？它才是 Java 本地緩存之王！

2. 同步加載

2.2 回收政策

1. 基于大小的過期方式

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希