走向未來-caffeine

整理自：

https://juejin.im/post/5b7593496fb9a009b62904fa#heading-12

https://www.cnblogs.com/liujinhua306/p/9808500.html

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

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

Caffeine原理簡介

W-TinyLFU

傳統的LFU受時間周期的影響比較大。是以各種LFU的變種出現了，基于時間周期進行衰減，或者在最近某個時間段内的頻率。同樣的LFU也會使用額外空間記錄每一個資料通路的頻率，即使資料沒有在緩存中也需要記錄，是以需要維護的額外空間很大。

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

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

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

頻率記錄

首先要說到的就是頻率記錄的問題，我們要實作的目标是利用有限的空間可以記錄随時間變化的通路頻率。在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來舉例。

1. 首先确定50這個hash是在哪個段裡面，通過hash & 3(3的二進制是11)必定能獲得小于4的數字，假設hash & 3=0，那就在A段。
2. 對50的hash再用其他hash算法再做一次hash，得到long數組的位置，也就是在長度128數組中的位置。假設用s1算法得到1，s2算法得到3，s3算法得到4，s4算法得到0。
3. 因為S1算法得到的是1，是以在long[1]的A段裡面的s1位置進行+1,簡稱1As1加1，然後在3As2加1，在4As3加1，在0As4加1。

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

讀寫性能

在guava cache中我們說過其讀寫操作中夾雜着過期時間的處理，也就是你在一次Put操作中有可能還會做淘汰操作，是以其讀寫性能會受到一定影響，可以看上面的圖中，caffeine的确在讀寫操作上面完爆guava cache。主要是因為在caffeine，對這些事件的操作是通過異步操作，他将事件送出至隊列，這裡的隊列的資料結構是RingBuffer,不清楚的可以看看這篇文章,你應該知道的高性能無鎖隊列Disruptor。然後通過會通過預設的ForkJoinPool.commonPool()，或者自己配置線程池，進行取隊列操作，然後在進行後續的淘汰，過期操作。

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

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

資料淘汰政策

在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。

這三個隊列關系如下:

1. 所有的新資料都會進入Eden。
2. Eden滿了，淘汰進入Probation。
3. 如果在Probation中通路了其中某個資料，則這個資料更新為Protected。
4. 如果Protected滿了又會繼續降級為Probation。

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

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

  

• 其他情況，随機淘汰。