原文位址 譯者：簡直
緩存是提升性能的通用方法，現在大多數的緩存實作都使用了經典的技術。這篇文章中，我們會發掘 Caffeine 中的現代化的實作方法。Caffeine 是一個開源的 Java 緩存庫，它能提供高命中率和出色的并發能力。期望讀者們能被這些想法激發，進而将它們應用到任何你喜歡的程式設計語言中。
驅逐政策
緩存的驅逐政策是為了預測哪些資料在短期内最可能被再次用到，進而提升緩存的命中率。由于簡潔的實作、高效的運作時表現，以及在正常的使用場景下有不錯的命中率，LRU（Least Recently Used）政策或許是最流行的驅逐政策。但 LRU 通過曆史資料來預測未來是局限的，它會認為最後到來的資料是最可能被再次通路的，進而給與它最高的優先級。
現代緩存擴充了對曆史資料的使用，結合就近程度（recency）和通路頻次（frequency）來更好的預測資料。其中一種保留曆史資訊的方式是使用 popularity sketch（一種壓縮、機率性的資料結構）來從一大堆通路事件中定位頻繁的通路者。可以參考 CountMin Sketch 算法，它由計數矩陣和多個哈希方法實作。發生一次讀取時，矩陣中每行對應的計數器增加計數，估算頻率時，取資料對應是所有行中計數的最小值。這個方法讓我們從空間、效率、以及适配矩陣的長寬引起的哈希碰撞的錯誤率上做權衡。
Window TinyLFU（W-TinyLFU）算法将 sketch 作為過濾器，當新來的資料比要驅逐的資料高頻時，這個資料才會被緩存接納。這個許可視窗給予每個資料項積累熱度的機會，而不是立即過濾掉。這避免了持續的未命中，特别是在突然流量暴漲的的場景中，一些短暫的重複流量就不會被長期保留。為了重新整理曆史資料，一個時間衰減程序被周期性或增量的執行，給所有計數器減半。
對于長期保留的資料，W-TinyLFU 使用了分段 LRU（Segmented LRU，縮寫 SLRU）政策。起初，一個資料項存儲被存儲在試用段（probationary segment）中，在後續被通路到時，它會被提升到保護段（protected segment）中（保護段占總容量的 80%）。保護段滿後，有的資料會被淘汰回試用段，這也可能級聯的觸發試用段的淘汰。這套機制確定了通路間隔小的熱資料被儲存下來，而被重複通路少的冷資料則被回收。
如圖中資料庫和搜尋場景的結果展示，通過考慮就近程度和頻率能大大提升 LRU 的表現。一些進階的政策，像 ARC，LIRS 和 W-TinyLFU 都提供了接近最理想的命中率。想看更多的場景測試，請檢視相應的論文，也可以在使用 simulator 來測試自己的場景。
過期政策
過期的實作裡，往往每個資料項擁有不同的過期時間。因為容量的限制，過期後資料需要被懶淘汰，否則這些已過期的髒資料會污染到整個緩存。一般緩存中會啟用專有的清掃線程周期性的周遊清理緩存。這個政策相比在每次讀寫操作時按照過期時間排序的優先隊列來清理過期緩存要好，因為背景線程隐藏了的過期資料清除的時間開銷。
鑒于大多數場景裡不同資料項使用的都是固定的過期時長，Caffien 采用了統一過期時間的方式。這個限制讓用 O（1）的有序隊列組織資料成為可能。針對資料的寫後過期，維護了一個寫入順序隊列，針對讀後過期，維護了一個讀取順序隊列。緩存能複用驅逐政策下的隊列以及下面将要介紹的并發機制，讓過期的資料項在緩存的維護階段被抛棄掉。
并發
由于在大多數的緩存政策中，資料的讀取都會伴随對緩存狀态的寫操作，并發的緩存讀取被視為一個難點問題。傳統的解決方式是用同步鎖。這可以通過将緩存的資料劃成多個分區來進行鎖拆分優化。不幸的是熱點資料所持有的鎖會比其他資料更常的被占有，在這種場景下鎖拆分的性能提升也就沒那麼好了。當單個鎖的競争成為瓶頸後，接下來的經典的優化方式是隻更新單個資料的中繼資料資訊，以及使用随機采樣、基于 FIFO 的驅逐政策來減少資料操作。這些政策會帶來高性能的讀和低性能的寫，同時在選擇驅逐對象時也比較困難。
另一種可行方案來自于資料庫理論，通過送出日志的方式來擴充寫的性能。寫入操作先記入日志中，随後異步的批量執行，而不是立即寫入到資料結構中。這種思想可以應用到緩存中，執行哈希表的操作，将操作記錄到緩沖區，然後在合适的時機執行緩沖區中的内容。這個政策依然需要同步鎖或者 tryLock，不同的是把對鎖的競争轉移到對緩沖區的追加寫上。
在 Caffeine 中，有一組緩沖區被用來記錄讀寫。一次通路首先會被因線程而異的哈希到 stripped ring buffer 上，當檢測到競争時，緩沖區會自動擴容。一個 ring buffer 容量滿載後，會觸發異步的執行操作，而後續的對該 ring buffer 的寫入會被丢棄，直到這個 ring buffer 可被使用。雖然因為 ring buffer 容量滿而無法被記錄該通路，但緩存值依然會傳回給調用方。這種政策資訊的丢失不會帶來大的影響，因為 W-TinyLFU 能識别出我們希望儲存的熱點資料。通過使用因線程而異的雜湊演算法替代在資料項的鍵上做哈希，緩存避免了瞬時的熱點 key 的競争問題。
寫資料時，采用更傳統的并發隊列，每次變更會引起一次立即的執行。雖然資料的損失是不可接受的，但我們仍然有很多方法可以來優化寫緩沖區。所有類型的緩沖區都被多個的線程寫入，但卻通過單個線程來執行。這種多生産者/單個消費者的模式允許了更簡單、高效的算法來實作。
緩沖區和細粒度的寫帶來了單個資料項的操作亂序的競态條件。插入、讀取、更新、删除都可能被各種順序的重放，如果這個政策控制的不合适，則可能引起懸垂索引。解決方案是通過狀态機來定義單個資料項的生命周期。
在基準測試中，緩沖區随着哈希表的增長而增長，它的的使用相對更節省資源。讀的性能随着 CPU 的核數線性增長，是哈希表吞吐量的 33%。寫入有 10%的性能損耗，這是因為更新哈希表時的競争是最主要的開銷。
結論
還有許多實用的話題沒有被覆寫到。包括最小化記憶體的技巧，當複雜度上升時保證品質的測試技術以及确定優化是否值得的性能分析方法。這些都是緩存的實踐者需要關注的點，因為一旦這些被忽視，就很難重拾掌控緩存帶來的複雜度的信心。
Caffeine 的設計實作來自于大量的洞見和許多貢獻者的共同努力。它這些年的演化離不開一些人的幫助：Charles Fry, Adam Zell, Gil Einziger, Roy Friedman, Kevin Bourrillion, Bob Lee, Doug Lea, Josh Bloch, Bob Lane, Nitsan Wakart, Thomas Müeller, Dominic Tootell, Louis Wasserman, and Vladimir Blagojevic. Thanks to Nitsan Wakart, Adam Zell, Roy Friedman, and Will Chu for their feedback on drafts of this article。
另外一篇：
Caffeine Cache-高性能Java本地緩存元件
https://www.cnblogs.com/rickiyang/p/11074158.html