優效學院，大數據，Java，人工智能，架構，在線教育

1. 背景

本文是上週去技術沙龍聽了一下愛奇藝的Java緩存之路有感寫出來的。先簡單介紹一下愛奇藝的java緩存道路的發展吧。

可以看見圖中分為幾個階段：

• 第一階段：數據同步加redis

通過消息隊列進行數據同步至redis，然後Java應用直接去取緩存 這個階段優點是:由於是使用的分佈式緩存，所以數據更新快。缺點也比較明顯:依賴Redis的穩定性，一旦redis掛了，整個緩存系統不可用，造成緩存雪崩，所有請求打到DB。

• 第二，三階段：JavaMap到Guava cache

這個階段使用進程內緩存作為一級緩存，redis作為二級。優點:不受外部系統影響，其他系統掛了，依然能使用。缺點:進程內緩存無法像分佈式緩存那樣做到實時更新。由於java內存有限，必定緩存得設置大小，然後有些緩存會被淘汰，就會有命中率的問題。

• 第四階段：Guava Cache刷新

為了解決上面的問題，利用Guava Cache可以設置寫後刷新時間，進行刷新。解決了一直不更新的問題，但是依然沒有解決實時刷新。

• 第五階段：外部緩存異步刷新

這個階段擴展了Guava Cache,利用redis作為消息隊列通知機制，通知其他java應用程序進行刷新。

這裡簡單介紹一下愛奇藝緩存發展的五個階段，當然還有一些其他的優化，比如GC調優，緩存穿透，緩存覆蓋的一些優化等等。有興趣的同學可以關注公眾號，聯繫我進行交流。

2. 原始社會 - 查庫

上面說的是愛奇藝的一個進化線路，但是在大家的一般開發過程中，第一步一般都沒有redis，而是直接查庫。

在流量不大的時候，查數據庫或者讀取文件是最為方便，也能完全滿足我們的業務要求。

3. 古代社會 - HashMap

當我們應用有一定流量之後或者查詢數據庫特別頻繁，這個時候就可以祭出我們的java中自帶的HashMap或者ConcurrentHashMap。我們可以在代碼中這麼寫：

但是這樣做就有個問題HashMap無法進行數據淘汰，內存會無限制的增長，所以hashMap很快也被淘汰了。當然並不是說他完全就沒用，就像我們古代社會也不是所有的東西都是過時的，比如我們中華名族的傳統美德是永不過時的，就像這個hashMap一樣的可以在某些場景下作為緩存，當不需要淘汰機制的時候，比如我們利用反射，如果我們每次都通過反射去搜索Method,field，性能必定低效，這時我們用HashMap將其緩存起來，性能能提升很多。

4. 近代社會 - LRUHashMap

在古代社會中難住我們的問題無法進行數據淘汰，這樣會導致我們內存無限膨脹,顯然我們是不可以接受的。有人就說我把一些數據給淘汰掉唄，這樣不就對了，但是怎麼淘汰呢？隨機淘汰嗎？當然不行，試想一下你剛把A裝載進緩存，下一次要訪問的時候就被淘汰了，那又會訪問我們的數據庫了，那我們要緩存幹嘛呢？

所以聰明的人們就發明了幾種淘汰算法，下面列舉下常見的三種FIFO,LRU,LFU（還有一些ARC,MRU感興趣的可以自行搜索）：

• FIFO：先進先出，在這種淘汰算法中，先進入緩存的會先被淘汰。這種可謂是最簡單的了，但是會導致我們命中率很低。試想一下我們如果有個訪問頻率很高的數據是所有數據第一個訪問的，而那些不是很高的是後面再訪問的，那這樣就會把我們的首個數據但是他的訪問頻率很高給擠出。

• LRU：最近最少使用算法。在這種算法中避免了上面的問題，每次訪問數據都會將其放在我們的隊尾，如果需要淘汰數據，就只需要淘汰隊首即可。但是這個依然有個問題，如果有個數據在1個小時的前59分鐘訪問了1萬次(可見這是個熱點數據),再後一分鐘沒有訪問這個數據，但是有其他的數據訪問，就導致了我們這個熱點數據被淘汰。

• LFU：最近最少頻率使用。在這種算法中又對上面進行了優化，利用額外的空間記錄每個數據的使用頻率，然後選出頻率最低進行淘汰。這樣就避免了LRU不能處理時間段的問題。

上面列舉了三種淘汰策略，對於這三種，實現成本是一個比一個高，同樣的命中率也是一個比一個好。而我們一般來說選擇的方案居中即可，即實現成本不是太高，而命中率也還行的LRU,如何實現一個LRUMap呢？我們可以通過繼承LinkedHashMap，重寫removeEldestEntry方法，即可完成一個簡單的LRUMap。

在LinkedHashMap中維護了一個entry(用來放key和value的對象)鏈表。在每一次get或者put的時候都會把插入的新entry，或查詢到的老entry放在我們鏈表末尾。 可以注意到我們在構造方法中，設置的大小特意設置到max*1.4，在下面的removeEldestEntry方法中只需要size>max就淘汰，這樣我們這個map永遠也走不到擴容的邏輯了，通過重寫LinkedHashMap，幾個簡單的方法我們實現了我們的LruMap。

5. 現代社會 - Guava cache

在近代社會中已經發明出來了LRUMap,用來進行緩存數據的淘汰，但是有幾個問題：

• 鎖競爭嚴重，可以看見我的代碼中，Lock是全局鎖，在方法級別上面的，當調用量較大時，性能必然會比較低。
• 不支持過期時間
• 不支持自動刷新

所以谷歌的大佬們對於這些問題，按捺不住了，發明了Guava cache，在Guava cache中你可以如下面的代碼一樣，輕鬆使用：

我將會從guava cache原理中，解釋guava cache是如何解決LRUMap的幾個問題的。

5.1 鎖競爭

guava cache採用了類似ConcurrentHashMap的思想，分段加鎖，在每個段裡面各自負責自己的淘汰的事情。在Guava根據一定的算法進行分段，這裡要說明的是，如果段太少那競爭依然很嚴重，如果段太多會容易出現隨機淘汰，比如大小為100的，給他分100個段，那也就是讓每個數據都獨佔一個段，而每個段會自己處理淘汰的過程，所以會出現隨機淘汰。在guava cache中通過如下代碼，計算出應該如何分段。

上面segmentCount就是我們最後的分段數，其保證了每個段至少10個Entry。如果沒有設置concurrencyLevel這個參數，那麼默認就會是4，最後分段數也最多為4，例如我們size為100，會分為4段，每段最大的size是25。 在guava cache中對於寫操作直接加鎖，對於讀操作，如果讀取的數據沒有過期，且已經加載就緒，不需要進行加鎖，如果沒有讀到會再次加鎖進行二次讀，如果還沒有需要進行緩存加載，也就是通過我們配置的CacheLoader，我這裡配置的是直接返回Key，在業務中通常配置從數據庫中查詢。 如下圖所示：

5.2 過期時間

相比於LRUMap多了兩種過期時間，一個是寫後多久過期expireAfterWrite，一個是讀後多久過期expireAfterAccess。很有意思的事情是，在guava cache中對於過期的Entry並沒有馬上過期(也就是並沒有後臺線程一直在掃)，而是通過進行讀寫操作的時候進行過期處理，這樣做的好處是避免後臺線程掃描的時候進行全局加鎖。看下面的代碼：

從這個結果中我們知道，在put的時候才進行的過期處理。特別注意的是我上面concurrencyLevel(1)我這裡將分段最大設置為1，不然不會出現這個實驗效果的，在上面一節中已經說過，我們是以段位單位進行過期處理。在每個Segment中維護了兩個隊列：

writeQueue維護了寫隊列，隊頭代表著寫得早的數據，隊尾代表寫得晚的數據。 accessQueue維護了訪問隊列,和LRU一樣，用來我們進行訪問時間的淘汰，如果當這個Segment超過最大容量，比如我們上面所說的25，超過之後，就會把accessQueue這個隊列的第一個元素進行淘汰。

上面就是guava cache處理過期Entries的過程，會對兩個隊列一次進行peek操作，如果過期就進行刪除。一般處理過期Entries可以在我們的put操作的前後，或者讀取數據時發現過期了，然後進行整個Segment的過期處理，又或者進行二次讀lockedGetOrLoad操作的時候調用。

上面是我們驅逐Entry的時候的代碼，可以看見訪問的是accessQueue對其隊頭進行驅逐。而驅逐策略一般是在對segment中的元素髮生變化時進行調用，比如插入操作，更新操作，加載數據操作。

5.3 自動刷新

自動刷新操作，在guava cache中實現相對比較簡單，直接通過查詢，判斷其是否滿足刷新條件，進行刷新。

5.4 其他特性

在Guava cache中還有一些其他特性：

虛引用

在Guava cache中，key和value都能進行虛引用的設定，在Segment中的有兩個引用隊列：

這兩個隊列用來記錄被回收的引用，其中每個隊列記錄了每個被回收的Entry的hash，這樣回收了之後通過這個隊列中的hash值就能把以前的Entry進行刪除。

刪除監聽器

在guava cache中，當有數據被淘汰時，但是你不知道他到底是過期，還是被驅逐，還是因為虛引用的對象被回收？這個時候你可以調用這個方法removalListener(RemovalListener listener)添加監聽器進行數據淘汰的監聽，可以打日誌或者一些其他處理，可以用來進行數據淘汰分析。

在RemovalCause記錄了所有被淘汰的原因:被用戶刪除，被用戶替代，過期，驅逐收集，由於大小淘汰。

guava cache的總結

細細品讀guava cache的源碼總結下來，其實就是一個性能不錯的，api豐富的LRU Map。愛奇藝的緩存的發展也是基於此之上，通過對guava cache的二次開發，讓其可以進行java應用服務之間的緩存更新。

6. 走向未來-caffeine

guava cache的功能的確是很強大，滿足了絕大多數的人的需求，但是其本質上還是LRU的一層封裝,所以在眾多其他較為優良的淘汰算法中就相形見絀了。而caffeine cache實現了W-TinyLFU(LFU+LRU算法的變種)。下面是不同算法的命中率的比較：

其中Optimal是最理想的命中率，LRU和其他算法相比的確是個弟弟。而我們的W-TinyLFU 是最接近理想命中率的。當然不僅僅是命中率caffeine優於了guava cache，在讀寫吞吐量上面也是完爆guava cache。

這個時候你肯定會好奇為啥這麼caffeine這麼牛逼呢？彆著急下面慢慢給你道來。

6.1 W-TinyLFU

上面已經說過了傳統的LFU是怎麼一回事。在LFU中只要數據訪問模式的概率分佈隨時間保持不變時，其命中率就能變得非常高。這裡我還是拿愛奇藝舉例，比如有部新劇出來了，我們使用LFU給他緩存下來，這部新劇在這幾天大概訪問了幾億次，這個訪問頻率也在我們的LFU中記錄了幾億次。但是新劇總會過氣的，比如一個月之後這個新劇的前幾集其實已經過氣了，但是他的訪問量的確是太高了，其他的電視劇根本無法淘汰這個新劇，所以在這種模式下是有侷限性。所以各種LFU的變種出現了，基於時間週期進行衰減，或者在最近某個時間段內的頻率。同樣的LFU也會使用額外空間記錄每一個數據訪問的頻率，即使數據沒有在緩存中也需要記錄，所以需要維護的額外空間很大。

可以試想我們對這個維護空間建立一個hashMap，每個數據項都會存在這個hashMap中，當數據量特別大的時候，這個hashMap也會特別大。

再回到LRU，我們的LRU也不是那麼一無是處，LRU可以很好的應對突發流量的情況，因為他不需要累計數據頻率。

所以W-TinyLFU結合了LRU和LFU，以及其他的算法的一些特點。

6.2 頻率記錄

首先要說到的就是頻率記錄的問題，我們要實現的目標是利用有限的空間可以記錄隨時間變化的訪問頻率。在W-TinyLFU中使用Count-Min Sketch記錄我們的訪問頻率，而這個也是布隆過濾器的一種變種。如下圖所示：

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

這裡和以前的做個對比，簡單的舉個例子:如果一個hashMap來記錄這個頻率，如果我有100個數據，那這個HashMap就得存儲100個這個數據的訪問頻率。哪怕我這個緩存的容量是1，因為Lfu的規則我必須全部記錄這個100個數據的訪問頻率。如果有更多的數據我就有記錄更多的。

在Count-Min Sketch中，我這裡直接說caffeine中的實現吧(在FrequencySketch這個類中),如果你的緩存大小是100，他會生成一個long數組大小是和100最接近的2的冪的數，也就是128。而這個數組將會記錄我們的訪問頻率。在caffeine中他規則頻率最大為15，15的二進制位1111，總共是4位，而Long型是64位。所以每個Long型可以放16種算法，但是caffeine並沒有這麼做，只用了四種hash算法，每個Long型被分為四段，每段裡面保存的是四個算法的頻率。這樣做的好處是可以進一步減少Hash衝突，原先128大小的hash，就變成了128X4。

一個Long的結構如下：

我們的4個段分為A,B,C,D，在後面我也會這麼叫它們。而每個段裡面的四個算法我叫他s1,s2,s3,s4。下面舉個例子如果要添加一個訪問50的數字頻率應該怎麼做？我們這裡用size=100來舉例。

① 首先確定50這個hash是在哪個段裡面，通過hash & 3必定能獲得小於4的數字，假設hash & 3=0，那就在A段。

② 對50的hash再用其他hash算法再做一次hash，得到long數組的位置。假設用s1算法得到1，s2算法得到3，s3算法得到4，s4算法得到0。

③ 然後在long[1]的A段裡面的s1位置進行+1,簡稱1As1加1，然後在3As2加1，在4As3加1，在0As4加1。

這個時候有人會質疑頻率最大為15的這個是否太小？沒關係在這個算法中，比如size等於100，如果他全局提升了1000次就會全局除以2衰減，衰減之後也可以繼續增加，這個算法再W-TinyLFU的論文中證明了其可以較好的適應時間段的訪問頻率。

6.2 讀寫性能

在guava cache中我們說過其讀寫操作中夾雜著過期時間的處理，也就是你在一次Put操作中有可能還會做淘汰操作，所以其讀寫性能會受到一定影響，可以看上面的圖中，caffeine的確在讀寫操作上面完爆guava cache。主要是因為在caffeine，對這些事件的操作是通過異步操作，他將事件提交至隊列，這裡的隊列的數據結構是RingBuffer，不清楚的可以看看這篇文章，還在用BlockingQueue？讀這篇文章，瞭解下Disruptor吧（https://mp.weixin.qq.com/s/VLJ7fS4WjDFvj3ucWVe6bg）。然後通過會通過默認的ForkJoinPool.commonPool()，或者自己配置線程池，進行取隊列操作，然後在進行後續的淘汰，過期操作。

當然讀寫也是有不同的隊列，在caffeine中認為緩存讀比寫多很多，所以對於寫操作是所有線程共享一個Ringbuffer。

對於讀操作比寫操作更加頻繁，進一步減少競爭，其為每個線程配備了一個RingBuffer：

6.3 數據淘汰策略

在caffeine所有的數據都在ConcurrentHashMap中，這個和guava cache不同，guava cache是自己實現了個類似ConcurrentHashMap的結構。在caffeine中有三個記錄引用的LRU隊列：

• Eden隊列：在caffeine中規定只能為緩存容量的%1,如果size=100,那這個隊列的有效大小就等於1。這個隊列中記錄的是新到的數據，防止突發流量由於之前沒有訪問頻率，而導致被淘汰。比如有一部新劇上線，在最開始其實是沒有訪問頻率的，防止上線之後被其他緩存淘汰出去，而加入這個區域。伊甸區，最舒服最安逸的區域，在這裡很難被其他數據淘汰。

• Probation隊列：叫做緩刑隊列，在這個隊列就代表你的數據相對比較冷，馬上就要被淘汰了。這個有效大小為size減去eden減去protected。

• Protected隊列：在這個隊列中，可以稍微放心一下了，你暫時不會被淘汰，但是別急，如果Probation隊列沒有數據了或者Protected數據滿了，你也將會被面臨淘汰的尷尬局面。當然想要變成這個隊列，需要把Probation訪問一次之後，就會提升為Protected隊列。這個有效大小為(size減去eden) X 80% 如果size =100，就會是79。

這三個隊列關係如下：

① 所有的新數據都會進入Eden。

② Eden滿了，淘汰進入Probation。

③ 如果在Probation中訪問了其中某個數據，則這個數據升級為Protected。

④ 如果Protected滿了又會繼續降級為Probation。

對於發生數據淘汰的時候，會從Probation中進行淘汰，會把這個隊列中的數據隊頭稱為受害者，這個隊頭肯定是最早進入的，按照LRU隊列的算法的話那他其實他就應該被淘汰，但是在這裡只能叫他受害者，這個隊列是緩刑隊列，代表馬上要給他行刑了。這裡會取出隊尾叫候選者，也叫攻擊者。這裡受害者會和攻擊者做PK，通過我們的Count-Min Sketch中的記錄的頻率數據有以下幾個判斷：

• 如果攻擊者大於受害者，那麼受害者就直接被淘汰。
• 如果攻擊者<=5，那麼直接淘汰攻擊者。這個邏輯在他的註釋中有解釋，他認為設置一個預熱的門檻會讓整體命中率更高。

• 其他情況，隨機淘汰。

6.4 如何使用

對於熟悉Guava的玩家來說如果擔心有切換成本，那麼你完全就多慮了，caffeine的api借鑑了Guava的api，可以發現其基本一模一樣。

順便一提的是，越來越多的開源框架都放棄了Guava cache，比如Spring5。在業務上我也自己曾經比較過Guava cache和caffeine最終選擇了caffeine，在線上也有不錯的效果。所以不用擔心caffeine不成熟，沒人使用。

7. 最後

本文主要講了愛奇藝的緩存之路和本地緩存的一個發展歷史(從古至今到未來），以及每一種緩存的實現基本原理。當然要使用好緩存光是這些僅僅不夠，比如本地緩存如何在其他地方更改了之後同步更新，分佈式緩存，多級緩存等等。後面也會專門寫一節介紹這個如何用好緩存。對於Guava cache和caffeine的原理後面也會專門抽出時間寫這兩個的源碼分析，如果感興趣的朋友可以關注公眾號第一時間查閱更新文章。