資訊專欄INFORMATION COLUMN
摘要：鑒于大多數場景里不同數據項使用的都是固定的過期時長，采用了統一過期時間的方式。緩存能復用驅逐策略下的隊列以及下面將要介紹的并發機制，讓過期的數據項在緩存的維護階段被拋棄掉。的設計實現來自于大量的洞見和許多貢獻者的共同努力。
本文來自阿里集團客戶體驗事業群 簡直同學的投稿，簡直基于工作場景對于緩存做了一些研究，并翻譯了一篇文章供同道中人學習。
原文：http://highscalability.com/bl...
緩存是提升性能的通用方法，現在大多數的緩存實現都使用了經典的技術。這篇文章中，我們會發掘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.
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/61833.html
摘要：并且這種格式沒有事先對時間序列的數量做任何限制。使用格式來存儲時間序列數據的兩種可能的。其中存放了時間列序列列和數值列三列。隨著數據規模的繼續增長，基于的應用程序越來越不適合處理這樣規模的時間序列數據了。 就像我們在前一章提到的，一個時間序列是一系列數值，每個數值都伴隨著一個時間值，代表數據被記錄時的時間。時間序列數據存入后就很少再需要修改了，查詢時經常是查詢一個連續時間段的數據，也可...
摘要：微服務架構的風險微服務架構將應用程序邏輯移動到服務，并使用網絡層在它們之間進行通信。在微服務架構中，服務依賴于彼此。您始終只能部署其中一個，并且在驗證新版本是否符合預期之后才，將負載均衡器指向新的。 [譯] 設計一個容錯的微服務架構 摘要：本文屬于原創，歡迎轉載，轉載請保留出處：https://github.com/jasonGeng88/blog 原文地址 https://blog....
摘要：簡言之，我們認為好的用戶體驗從快速的內容傳輸開始，也就意味著性能美觀。每一步我們都在探討如何在獲得好的用戶體驗和保證設計美感的同時，最小化對性能的影響。字型子集設定到目前為止，子集設定是改善網頁字體性能最快的方式。 作者 Declan 原文鏈接 最近更新了我們的網站，它是經過了設計上的全面驗收的。但實際上，作為軟件開發者，我們會注重很多技術相關的零碎的東西。我們的目標是控制性能，注重性...
摘要：簡言之，我們認為好的用戶體驗從快速的內容傳輸開始，也就意味著性能美觀。每一步我們都在探討如何在獲得好的用戶體驗和保證設計美感的同時，最小化對性能的影響。字型子集設定到目前為止，子集設定是改善網頁字體性能最快的方式。 作者 Declan 原文鏈接 最近更新了我們的網站，它是經過了設計上的全面驗收的。但實際上，作為軟件開發者，我們會注重很多技術相關的零碎的東西。我們的目標是控制性能，注重性...
閱讀 3219·2021-11-12 10:36
閱讀 1280·2019-08-30 15:56
閱讀 2449·2019-08-30 11:26
閱讀 558·2019-08-29 13:00
閱讀 3614·2019-08-28 18:08
閱讀 2753·2019-08-26 17:18
閱讀 1907·2019-08-26 13:26
閱讀 2438·2019-08-26 11:39
