791
汽車大全
現代化的緩存設計方案
緩存是提升性能的通用方法，現在大多數的緩存實現都使用了經典的技術。這篇文章中，我們會發掘 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。
最後更新：2017-05-18 20:37:17