caffeine[1]是一個高性能，高命中率，低記憶體占用，near optimal 的本地緩存，簡單來說它是 guava cache 的優化加強版，有些文章把 caffeine 稱為“新一代的緩存”、“現代緩存之王”。
本文将重點講解 caffeine 的高性能設計，以及對應部分的源碼分析。
如果你對 guava cache 還不了解的話，可以點選這裡[2]來看一下我之前寫過關于 guava cache 的文章。
大家都知道，spring5 即将放棄掉 guava cache 作為緩存機制，而改用 caffeine 作為新的本地 cache 的元件，這對于 caffeine 來說是一個很大的肯定。為什麼 spring 會這樣做呢？其實在 caffeine 的benchmarks[3]裡給出了好靓仔的資料，對讀和寫的場景，還有跟其他幾個緩存工具進行了比較，caffeine 的性能都表現很突出。
caffeine 為了友善大家使用以及從 guava cache 切換過來（很有針對性啊～），借鑒了 guava cache 大部分的概念（諸如核心概念<code>cache</code>、<code>loadingcache</code>、<code>cacheloader</code>、<code>cachebuilder</code>等等），對于 caffeine 的了解隻要把它當作 guava cache 就可以了。
使用上，大家隻要把 caffeine 的包引進來，然後換一下 cache 的實作類，基本應該就沒問題了。這對與已經使用過 guava cache 的同學來說沒有任何難度，甚至還有一點熟悉的味道，如果你之前沒有使用過 guava cache，可以檢視 caffeine 的官方 api 說明文檔[4]，其中<code>population</code>，<code>eviction</code>，<code>removal</code>，<code>refresh</code>，<code>statistics</code>，<code>cleanup</code>，<code>policy</code>等等這些特性都是跟 guava cache 基本一樣的。
下面給出一個例子說明怎樣建立一個 cache：
更多從 guava cache 遷移過來的使用說明，請看這裡[5]
判斷一個緩存的好壞最核心的名額就是命中率，影響緩存命中率有很多因素，包括業務場景、淘汰政策、清理政策、緩存容量等等。如果作為本地緩存， 它的性能的情況，資源的占用也都是一個很重要的名額。下面
我們來看看 caffeine 在這幾個方面是怎麼着手的，如何做優化的。
（注：本文不會分析 caffeine 全部源碼，隻會對核心設計的實作進行分析，但我建議讀者把 caffeine 的源碼都涉獵一下，有個 overview 才能更好了解本文。如果你看過 guava cache 的源碼也行，代碼的資料結構和處理邏輯很類似的。
源碼基于：caffeine-2.8.0.jar）
上面說到淘汰政策是影響緩存命中率的因素之一，一般比較簡單的緩存就會直接用到 lfu(least frequently used，即最不經常使用) 或者lru(least recently used，即最近最少使用) ，而 caffeine 就是使用了 w-tinylfu 算法。
w-tinylfu 看名字就能大概猜出來，它是 lfu 的變種，也是一種緩存淘汰算法。那為什麼要使用 w-tinylfu 呢？
lru 實作簡單，在一般情況下能夠表現出很好的命中率，是一個“成本效益”很高的算法，平時也很常用。雖然 lru 對突發性的稀疏流量（sparse bursts）表現很好，但同時也會産生緩存污染，舉例來說，如果偶然性的要對全量資料進行周遊，那麼“曆史通路記錄”就會被刷走，造成污染。
如果資料的分布在一段時間内是固定的話，那麼 lfu 可以達到最高的命中率。但是 lfu 有兩個缺點，第一，它需要給每個記錄項維護頻率資訊，每次通路都需要更新，這是個巨大的開銷；第二，對突發性的稀疏流量無力，因為前期經常通路的記錄已經占用了緩存，偶然的流量不太可能會被保留下來，而且過去的一些大量被通路的記錄在将來也不一定會使用上，這樣就一直把“坑”占着了。
無論 lru 還是 lfu 都有其各自的缺點，不過，現在已經有很多針對其缺點而改良、優化出來的變種算法。
tinylfu 就是其中一個優化算法，它是專門為了解決 lfu 上述提到的兩個問題而被設計出來的。
解決第一個問題是采用了 count–min sketch 算法。
解決第二個問題是讓記錄盡量保持相對的“新鮮”（freshness mechanism），并且當有新的記錄插入時，可以讓它跟老的記錄進行“pk”，輸者就會被淘汰，這樣一些老的、不再需要的記錄就會被剔除。
下圖是 tinylfu 設計圖（來自官方）
如何對一個 key 進行統計，但又可以節省空間呢？（不是簡單的使用<code>hashmap</code>，這太消耗記憶體了），注意哦，不需要精确的統計，隻需要一個近似值就可以了，怎麼樣，這樣場景是不是很熟悉，如果你是老司機，或許已經聯想到布隆過濾器（bloom filter）的應用了。
沒錯，将要介紹的 count–min sketch 的原理跟 bloom filter 一樣，隻不過 bloom filter 隻有 0 和 1 的值，那麼你可以把 count–min sketch 看作是“數值”版的 bloom filter。
更多關于 count–min sketch 的介紹請自行搜尋。
在 tinylfu 中，近似頻率的統計如下圖所示：
對一個 key 進行多次 hash 函數後，index 到多個數組位置後進行累加，查詢時取多個值中的最小值即可。
caffeine 對這個算法的實作在<code>frequencysketch</code>類。但 caffeine 對此有進一步的優化，例如 count–min sketch 使用了二維數組，caffeine 隻是用了一個一維的數組；再者，如果是數值類型的話，這個數需要用 int 或 long 來存儲，但是 caffeine 認為緩存的通路頻率不需要用到那麼大，隻需要 15 就足夠，一般認為達到 15 次的頻率算是很高的了，而且 caffeine 還有另外一個機制來使得這個頻率進行衰退減半（下面就會講到）。如果最大是 15 的話，那麼隻需要 4 個 bit 就可以滿足了，一個 long 有 64bit，可以存儲 16 個這樣的統計數，caffeine 就是這樣的設計，使得存儲效率提高了 16 倍。
caffeine 對緩存的讀寫（<code>afterread</code>和<code>afterwrite</code>方法）都會調用<code>onaccess</code>s 方法，而<code>onaccess</code>方法裡有一句：
這句就是追加記錄的頻率，下面我們看看具體實作
知道了追加方法，那麼讀取方法<code>frequency</code>就很容易了解了。
通過代碼和注釋或者讀者可能難以了解，下圖是我畫出來幫助大家了解的結構圖。
注意紫色虛線框，其中藍色小格就是需要計算的位置：
為了讓緩存保持“新鮮”，剔除掉過往頻率很高但之後不經常的緩存，caffeine 有一個 freshness mechanism。做法很簡答，就是當整體的統計計數（目前所有記錄的頻率統計之和，這個數值内部維護）達到某一個值時，那麼所有記錄的頻率統計除以 2。
從上面的代碼
看到<code>reset</code>方法就是做這個事情
關于這個 reset 方法，為什麼是除以 2，而不是其他，及其正确性，在最下面的參考資料的 tinylfu 論文中 3.3 章節給出了數學證明，大家有興趣可以看看。
caffeine 通過測試發現 tinylfu 在面對突發性的稀疏流量（sparse bursts）時表現很差，因為新的記錄（new items）還沒來得及建立足夠的頻率就被剔除出去了，這就使得命中率下降。
于是 caffeine 設計出一種新的 policy，即 window tiny lfu（w-tinylfu），并通過實驗和實踐發現 w-tinylfu 比 tinylfu 表現的更好。
w-tinylfu 的設計如下所示（兩圖等價）：
它主要包括兩個緩存子產品，主緩存是 slru（segmented lru，即分段 lru），slru 包括一個名為 protected 和一個名為 probation 的緩存區。通過增加一個緩存區（即 window cache），當有新的記錄插入時，會先在 window 區呆一下，就可以避免上述說的 sparse bursts 問題。
當 window 區滿了，就會根據 lru 把 candidate（即淘汰出來的元素）放到 probation 區，如果 probation 區也滿了，就把 candidate 和 probation 将要淘汰的元素 victim，兩個進行“pk”，勝者留在 probation，輸者就要被淘汰了。
而且經過實驗發現當 window 區配置為總容量的 1%，剩餘的 99%當中的 80%分給 protected 區，20%分給 probation 區時，這時整體性能和命中率表現得最好，是以 caffeine 預設的比例設定就是這個。
不過這個比例 caffeine 會在運作時根據統計資料（statistics）去動态調整，如果你的應用程式的緩存随着時間變化比較快的話，那麼增加 window 區的比例可以提高命中率，相反緩存都是比較固定不變的話，增加 main cache 區（protected 區 +probation 區）的比例會有較好的效果。
下面我們看看上面說到的淘汰政策是怎麼實作的：
一般緩存對讀寫操作後都有後續的一系列“維護”操作，caffeine 也不例外，這些操作都在<code>maintenance</code>方法，我們将要說到的淘汰政策也在裡面。
這方法比較重要，下面也會提到，是以這裡隻先說跟“淘汰政策”有關的<code>evictentries</code>和<code>climb</code>。
先說一下 caffeine 對上面說到的 w-tinylfu 政策的實作用到的資料結構：
以及預設比例設定（意思看注釋）
重點來了，<code>evictentries</code>和<code>climb</code>方法：
<code>evictfrommain</code>方法：
<code>climb</code>方法主要是用來調整 window size 的，使得 caffeine 可以适應你的應用類型（如 olap 或 oltp）表現出最佳的命中率。
下圖是官方測試的資料：
我們看看 window size 的調整是怎麼實作的。
調整時用到的預設比例資料：
下面分别展開每個方法來解釋：
以上，是 caffeine 的 w-tinylfu 政策的設計原理及代碼實作解析。
一般的緩存每次對資料處理完之後（讀的話，已經存在則直接傳回，不存在則 load 資料，儲存，再傳回；寫的話，則直接插入或更新），但是因為要維護一些淘汰政策，則需要一些額外的操作，諸如：
計算和比較資料的是否過期
統計頻率（像 lfu 或其變種）
維護 read queue 和 write queue
淘汰符合條件的資料
等等。。。
這種資料的讀寫伴随着緩存狀态的變更，guava cache 的做法是把這些操作和讀寫操作放在一起，在一個同步加鎖的操作中完成，雖然 guava cache 巧妙地利用了 jdk 的 concurrenthashmap（分段鎖或者無鎖 cas）來降低鎖的密度，達到提高并發度的目的。但是，對于一些熱點資料，這種做法還是避免不了頻繁的鎖競争。caffeine 借鑒了資料庫系統的 wal（write-ahead logging）思想，即先寫日志再執行操作，這種思想同樣适合緩存的，執行讀寫操作時，先把操作記錄在緩沖區，然後在合适的時機異步、批量地執行緩沖區中的内容。但在執行緩沖區的内容時，也是需要在緩沖區加上同步鎖的，不然存在并發問題，隻不過這樣就可以把對鎖的競争從緩存資料轉移到對緩沖區上。
在 caffeine 的内部實作中，為了很好的支援不同的 features（如 eviction，removal，refresh，statistics，cleanup，policy 等等），擴充了很多子類，它們共同的父類是<code>boundedlocalcache</code>，而<code>readbuffer</code>就是作為它們共有的屬性，即都是用一樣的 readbuffer，看定義：
上面提到 caffeine 對每次緩存的讀操作都會觸發<code>afterread</code>
重點看<code>boundedbuffer</code>
它是一個 striped、非阻塞、有界限的 buffer，繼承于<code>stripedbuffer</code>類。下面看看<code>stripedbuffer</code>的實作：
這個<code>stripedbuffer</code>設計的思想是跟<code>striped64</code>類似的，通過擴充結構把競争熱點分離。
具體實作是這樣的，<code>stripedbuffer</code>維護一個<code>buffer[]</code>數組，每個元素就是一個<code>ringbuffer</code>，每個線程用自己<code>threadlocalrandomprobe</code>屬性作為 hash 值，這樣就相當于每個線程都有自己“專屬”的<code>ringbuffer</code>，就不會産生競争啦，而不是用 key 的<code>hashcode</code>作為 hash 值，因為會産生熱點資料問題。
看看<code>stripedbuffer</code>的屬性
<code>offer</code>方法，當沒初始化或存在競争時，則擴容為 2 倍。
實際是調用<code>ringbuffer</code>的 offer 方法，把資料追加到<code>ringbuffer</code>後面。
最後看看<code>ringbuffer</code>，注意<code>ringbuffer</code>是<code>boundedbuffer</code>的内部類。
注意，ring buffer 的 size（固定是 16 個）是不變的，變的是 head 和 tail 而已。
總的來說<code>readbuffer</code>有如下特點：
使用 <code>striped-ringbuffer</code>來提升對 buffer 的讀寫
用 thread 的 hash 來避開熱點 key 的競争
允許寫入的丢失
<code>writebuffer</code>跟<code>readbuffer</code>不一樣，主要展現在使用場景的不一樣。本來緩存的一般場景是讀多寫少的，讀的并發會更高，且 afterread 顯得沒那麼重要，允許延遲甚至丢失。寫不一樣，寫<code>afterwrite</code>不允許丢失，且要求盡量馬上執行。caffeine 使用mpsc（multiple producer / single consumer）作為 buffer 數組，實作在<code>mpscgrowablearrayqueue</code>類，它是仿照<code>jctools</code>的<code>mpscgrowablearrayqueue</code>來寫的。
mpsc 允許無鎖的高并發寫入，但隻允許一個消費者，同時也犧牲了部分操作。
mpsc 我打算另外分析，這裡不展開了。
除了支援<code>expireafteraccess</code>和<code>expireafterwrite</code>之外（guava cache 也支援這兩個特性），caffeine 還支援<code>expireafter</code>。因為<code>expireafteraccess</code>和<code>expireafterwrite</code>都隻能是固定的過期時間，這可能滿足不了某些場景，譬如記錄的過期時間是需要根據某些條件而不一樣的，這就需要使用者自定義過期時間。
先看看<code>expireafter</code>的用法
通過自定義過期時間，使得不同的 key 可以動态的得到不同的過期時間。
注意，我把<code>expireafteraccess</code>和<code>expireafterwrite</code>注釋了，因為這兩個特性不能跟<code>expireafter</code>一起使用。
而當使用了<code>expireafter</code>特性後，caffeine 會啟用一種叫“時間輪”的算法來實作這個功能。更多關于時間輪的介紹，可以看我的文章hashedwheeltimer 時間輪原理分析[6]。
好，重點來了，為什麼要用時間輪？
對<code>expireafteraccess</code>和<code>expireafterwrite</code>的實作是用一個<code>accessorderdeque</code>雙端隊列，它是 fifo 的，因為它們的過期時間是固定的，是以在隊列頭的資料肯定是最早過期的，要處理過期資料時，隻需要首先看看頭部是否過期，然後再挨個檢查就可以了。但是，如果過期時間不一樣的話，這需要對<code>accessorderqueue</code>進行排序&插入，這個代價太大了。于是，caffeine 用了一種更加高效、優雅的算法-時間輪。
時間輪的結構：
因為在我的對時間輪分析的文章裡已經說了時間輪的原理和機制了，是以我就不展開 caffeine 對時間輪的實作了。
caffeine 對時間輪的實作在<code>timerwheel</code>，它是一種多層時間輪（hierarchical timing wheels ）。
看看元素加入到時間輪的<code>schedule</code>方法：
caffeine 還有其他的優化性能的手段，如使用軟引用和弱引用、消除僞共享、<code>completablefuture</code>異步等等。
caffeien 是一個優秀的本地緩存，通過使用 w-tinylfu 算法， 高性能的 readbuffer 和 writebuffer，時間輪算法等，使得它擁有高性能，高命中率（near optimal），低記憶體占用等特點。
tinylfu 論文[7]
design of a modern cache[8]
design of a modern cache—part deux[9]
caffeine 的 github[10]
[1]
caffeine: https://github.com/ben-manes/caffeine
[2]
這裡: https://albenw.github.io/posts/df42dc84/
[3]
benchmarks: https://github.com/ben-manes/caffeine/wiki/benchmarks
[4]
官方api說明文檔: https://github.com/ben-manes/caffeine/wiki
[5]
這裡: https://github.com/ben-manes/caffeine/wiki/guava
[6]
hashedwheeltimer時間輪原理分析: https://albenw.github.io/posts/ec8df8c/
[7]
tinylfu論文: https://arxiv.org/abs/1512.00727
[8]
design of a modern cache: http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html
[9]
design of a modern cache—part deux: http://highscalability.com/blog/2019/2/25/design-of-a-modern-cachepart-deux.html
[10]
caffeine的github: https://github.com/ben-manes/caffeine
https://mp.weixin.qq.com/s/cjkpezazpg55u6zilfttsg