資訊專欄INFORMATION COLUMN
摘要：在靜態的頻率分布下，性能也落后于因為其不再為不在緩存中的數據維護任何頻率數據。可以詳見的準入淘汰策略是新增一個新的元素時，判斷使用該元素替換一個舊元素，是否可以提升緩存命中率。
1. Introduction
LFU的局限：
LFU實現需要維護大而復雜的元數據（頻次統計數據等）
大多數實際工作負載中，訪問頻率隨著時間的推移而發生根本變化（這是外賣業務不適合樸素LFU的根本原因）
針對LFU的問題，已經存在了一些LFU的替代或優化方案，例如WLFU（Window LFU）：
老化機制
限制采樣為：最后W次訪問的有限大小窗口
在絕大多數情況下，新訪問的數據總是被直接插入到緩存中，緩存方案僅設計驅逐策略，即，決定應該驅逐哪個數據。這是因為維護當前不在緩存中的對象的元數據被認為是不切實際的。
由于維護所有訪問的頻率數據消耗過大，很多LFU的實現只維護了緩存中數據的頻率數據。對于前者，我們稱為Perfect LFU（PLFU），后者則稱為In-Memory LFU。由于WLFU（Window-LFU）優于In-Memery LFU（以更大的元數據為代價），所以論文在第一節只討論了WLFU和PLFU。
LRU是一個很常見的用來替代LFU的算法，LRU的淘汰最近最少使用的元素。相較于LFU，LRU可能會有更加高效的實現，可以并自動適應突發的訪問請求；然而基于LRU的緩存，在較大的負載下，需要更多的空間來保持和LFU一樣的緩存命中率。
本文的貢獻：
闡明了一種近似LFU準入策略的緩存結構/算法的有效性
提出了一種緩存結構，只有在準入策略認為將其替換進入緩存會提高緩存命中率的情況下，才會被插入
提出了一種空間利用率很高的新的數據結構——TinyLFU，可以在較大訪問量的場景下近似的替代LFU的數據統計部分（meta-data）。
通過形式化的證明和模擬，證明了TinyLFU獲得的Freq排序與真實的訪問頻率排序是幾乎近似的
以優化的形式將TinyLFU實現在了Caffeine項目中：W-TinyLFU
與其他幾種緩存管理策略進行了比較，包括ARC、LIRC
對于較為靜態的訪問分布，各種的緩存管理策略的差異是微不足道的，而對于偏倚較大的負載場景，TinyLFU體現出了較大的優勢。即便是使用了TinyLFU準入策略進行優化的LRU也獲得了較大的提升（LRU原生沒有準入策略）。
2. Related Work 2.1 Cache ReplacementPLFU更加適合相對靜態的訪問分布，但不能很好的適應動態的訪問頻率分布。
In-Memory LFU僅維護已存在于緩存中的數據項的訪問頻率，并始終將最近訪問的項插入緩存中，如果需要，逐出緩存中最不頻繁訪問的項。通常In-Memory LFU使用堆來管理緩存，并且由Anirban優化到了O(1)。然而即便有了這樣的改進，但In-Memory LFU仍然對頻率分布的變化顯得反應遲緩。在靜態的頻率分布下，性能也落后于PLFU（因為其不再為【不在緩存中的數據】維護任何頻率數據）。
Aging
是對In-Memory LFU的優化，提高了其對變化的響應能力。
增加了一個【最大平均引用計數】，當緩存中的數據引用計數平均值超過了該值，則將所有的數據的頻率技術都進行減少。但是如何減少（一般是存在一個衰減因子）是一個棘手且tricky的問題。
WLFU
只保存一個時間窗口內的訪問數據來統計頻次，這個機制要求按照時序對訪問進行持續的采樣。對變化的調整是優于PLFU的。
ARC
LIRS
SLRU
2Q
LRU-K
GDSF
2.2 近似統計結構（Approximate Counting Architectures）簡單說就是對全流量采樣，TinyLFU需要一種近似的流量統計結構來替代全量Hash，減少內存的占用，并且要盡可能高效，且盡量保持精度。可以詳見3.2
3. TinyLFU Architecture 3.1 TinyLFU OverviewTinyLFU的準入&淘汰策略是：新增一個新的元素時，判斷使用該元素替換一個舊元素，是否可以提升緩存命中率。
上圖為TinyLFU的主要結構，但是在闡述前需要強調我們面臨的兩個主要的挑戰：
維護一個新鮮度機制（freshness mechanism），來保持歷史最近訪問且可以移除舊事件（keep the history recent and remove the history old events）
如何減少內存的消耗
3.2 Approximate Counting Overview
Minimal Increment Counting Bloom Filter Counting Bloom Filter參考鏈接
Minimal Increment CBF 和CBF 使用一個合適大小的計數器來代替了Bloom Filter中的bit
Minimal Increment CBF支持以下兩個方法（下面的闡述，假設我們的場景是來為key計算k=3個hash value，來定位）
Estimate
例如，獲取到3個hash位置上的計數值：{2, 2, 5}，取所有值中的最小值返回
Add
在元素到達后，獲取到已有的3個計數值{2, 2, 5}，Add操作僅增加兩個較小的計數值，來避免針對最大值的不必要的增加
3.3 Freshness MechanismTinyLFU使用reset機制來保證sketch中的數據盡可能最新。每增加一個新的元素到approximation sketches，會增加一個計數值，一旦計數值達到了一個預設的采樣尺寸（W），就會將頻率采樣（CBF）維護的所有計數值除以2（可以使用高效的寄存器位移來實現）；論文也花了較大的篇幅來證明了這種Reset機制的正確性，且評估了其存在的截斷錯誤（3會被reset為1，而非1.5），并且得出了以下結論：
reset在固定的頻率分布下完全正確，且可以應對流量頻率的變化（數學歸納法證明，感興趣的可以參考原文3.3.1）
采樣數W越大，截斷錯誤的帶來的影響越小
3.4 Space Reduction
在兩個維度減少了空間的占用：
減小了sketch中計數值的尺寸
對于我們的采樣大小W，我們的計數值需要占用log(W) bit
減少了sketch分的計數器的數量
Doorkeeper
引入了Doorkeeper機制，來避免為長尾流量分配計數器
由一個常規的Bloom Filter攔截在CBF之前
如果一個元素，在Doorkeeper中，則直接插入TinyLFU的主結構，否則先插入Doorkeeper；對于數據查詢，會將Doorkeeper中的那一個計數值也加到計數值上去
reset操作會清空Doorkeeper
這樣對于每個W周期內，都會過濾僅有一次的訪問的數據
盡管Doorkeeper需要一些額外的空間，但是相對于在主要結構中節約的空間來說，顯得微不足道。
3.5 TingLFU vs a Strwman略
3.6 Connecting TinyLFU to Caches對于LRU和隨機緩存而言，緩存存儲本質上是個黑盒。而TinyLFU不同，由于reset機制的存在，需要在reset時，同步更新緩存中的item；
4. Winwod TinyLFU（W-TinyLFU）主要是優化了“sparse bursts（突發的稀疏流量）”，新的突發流量可能會因為無法構建足夠的頻率數據來保證自己駐留在緩存中。
前端是一個小的LRU（window cache）；window cache淘汰后，會送到DoorKeeper過濾；過濾通過后，元素存儲到一個大的Segmented LRU緩存里。Window LRU，它的容量只占據1%的總空間，它的目的就是用來存放短期突發訪問記錄。存放主要元素的Segmented LRU(SLRU)是一種LRU的改進，主要把在一個時間窗口內命中至少2次的記錄和命中1次的多帶帶存放，這樣就可以把短期內較頻繁的緩存元素區分開來。具體做法上，SLRU包含2個固定尺寸的LRU，一個叫Probation段A1，一個叫Protection段A2。新記錄總是插入到A1中，當A1的記錄被再次訪問，就把它移到A2，當A2滿了需要驅逐記錄時，會把驅逐記錄插入到A1中。W-TinyLFU中，SLRU有80%空間被分配給A2段。
5. 實驗略
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/62009.html
摘要：在靜態的頻率分布下，性能也落后于因為其不再為不在緩存中的數據維護任何頻率數據。可以詳見的準入淘汰策略是新增一個新的元素時，判斷使用該元素替換一個舊元素，是否可以提升緩存命中率。 1. Introduction LFU的局限： LFU實現需要維護大而復雜的元數據（頻次統計數據等） 大多數實際工作負載中，訪問頻率隨著時間的推移而發生根本變化（這是外賣業務不適合樸素LFU的根本原因） 針...
摘要：鑒于大多數場景里不同數據項使用的都是固定的過期時長，采用了統一過期時間的方式。緩存能復用驅逐策略下的隊列以及下面將要介紹的并發機制，讓過期的數據項在緩存的維護階段被拋棄掉。的設計實現來自于大量的洞見和許多貢獻者的共同努力。 本文來自阿里集團客戶體驗事業群 簡直同學的投稿，簡直基于工作場景對于緩存做了一些研究，并翻譯了一篇文章供同道中人學習。 原文：http://highscalabi...
摘要：近幾年，深度學習高速發展，出現了大量的新模型與架構，以至于我們無法理清網絡類型之間的關系。是由深度學習先驅等人提出的新一代神經網絡形式，旨在修正反向傳播機制。當多個預測一致時本論文使用動態路由使預測一致，更高級別的將變得活躍。 近幾年，深度學習高速發展，出現了大量的新模型與架構，以至于我們無法理清網絡類型之間的關系。在這篇文章中，香港科技大學（HKUST）助理教授金成勳總結了深度網絡類型之間...
閱讀 2862·2021-07-30 15:30
閱讀 559·2019-08-30 15:55
閱讀 1625·2019-08-26 17:04
閱讀 637·2019-08-26 11:36
閱讀 2074·2019-08-26 10:58
閱讀 3553·2019-08-23 14:34
閱讀 1561·2019-08-22 18:48
閱讀 2529·2019-08-21 17:51
