摘要：在靜態(tài)的頻率分布下，性能也落后于因?yàn)槠洳辉贋椴辉诰彺嬷械臄?shù)據(jù)維護(hù)任何頻率數(shù)據(jù)。可以詳見的準(zhǔn)入淘汰策略是新增一個(gè)新的元素時(shí)，判斷使用該元素替換一個(gè)舊元素，是否可以提升緩存命中率。

LFU的局限：

LFU實(shí)現(xiàn)需要維護(hù)大而復(fù)雜的元數(shù)據(jù)（頻次統(tǒng)計(jì)數(shù)據(jù)等）

大多數(shù)實(shí)際工作負(fù)載中，訪問頻率隨著時(shí)間的推移而發(fā)生根本變化（這是外賣業(yè)務(wù)不適合樸素LFU的根本原因）

針對(duì)LFU的問題，已經(jīng)存在了一些LFU的替代或優(yōu)化方案，例如WLFU（Window LFU）：

老化機(jī)制

限制采樣為：最后W次訪問的有限大小窗口

在絕大多數(shù)情況下，新訪問的數(shù)據(jù)總是被直接插入到緩存中，緩存方案僅設(shè)計(jì)驅(qū)逐策略，即，決定應(yīng)該驅(qū)逐哪個(gè)數(shù)據(jù)。這是因?yàn)榫S護(hù)當(dāng)前不在緩存中的對(duì)象的元數(shù)據(jù)被認(rèn)為是不切實(shí)際的。

由于維護(hù)所有訪問的頻率數(shù)據(jù)消耗過大，很多LFU的實(shí)現(xiàn)只維護(hù)了緩存中數(shù)據(jù)的頻率數(shù)據(jù)。對(duì)于前者，我們稱為Perfect LFU（PLFU），后者則稱為In-Memory LFU。由于WLFU（Window-LFU）優(yōu)于In-Memery LFU（以更大的元數(shù)據(jù)為代價(jià)），所以論文在第一節(jié)只討論了WLFU和PLFU。

LRU是一個(gè)很常見的用來替代LFU的算法，LRU的淘汰最近最少使用的元素。相較于LFU，LRU可能會(huì)有更加高效的實(shí)現(xiàn)，可以并自動(dòng)適應(yīng)突發(fā)的訪問請(qǐng)求；然而基于LRU的緩存，在較大的負(fù)載下，需要更多的空間來保持和LFU一樣的緩存命中率。

本文的貢獻(xiàn)：

闡明了一種近似LFU準(zhǔn)入策略的緩存結(jié)構(gòu)/算法的有效性

提出了一種緩存結(jié)構(gòu)，只有在準(zhǔn)入策略認(rèn)為將其替換進(jìn)入緩存會(huì)提高緩存命中率的情況下，才會(huì)被插入

提出了一種空間利用率很高的新的數(shù)據(jù)結(jié)構(gòu)——TinyLFU，可以在較大訪問量的場景下近似的替代LFU的數(shù)據(jù)統(tǒng)計(jì)部分（meta-data）。

通過形式化的證明和模擬，證明了TinyLFU獲得的Freq排序與真實(shí)的訪問頻率排序是幾乎近似的

以優(yōu)化的形式將TinyLFU實(shí)現(xiàn)在了Caffeine項(xiàng)目中：W-TinyLFU

與其他幾種緩存管理策略進(jìn)行了比較，包括ARC、LIRC

對(duì)于較為靜態(tài)的訪問分布，各種的緩存管理策略的差異是微不足道的，而對(duì)于偏倚較大的負(fù)載場景，TinyLFU體現(xiàn)出了較大的優(yōu)勢。即便是使用了TinyLFU準(zhǔn)入策略進(jìn)行優(yōu)化的LRU也獲得了較大的提升（LRU原生沒有準(zhǔn)入策略）。

PLFU更加適合相對(duì)靜態(tài)的訪問分布，但不能很好的適應(yīng)動(dòng)態(tài)的訪問頻率分布。
In-Memory LFU僅維護(hù)已存在于緩存中的數(shù)據(jù)項(xiàng)的訪問頻率，并始終將最近訪問的項(xiàng)插入緩存中，如果需要，逐出緩存中最不頻繁訪問的項(xiàng)。通常In-Memory LFU使用堆來管理緩存，并且由Anirban優(yōu)化到了O(1)。然而即便有了這樣的改進(jìn)，但I(xiàn)n-Memory LFU仍然對(duì)頻率分布的變化顯得反應(yīng)遲緩。在靜態(tài)的頻率分布下，性能也落后于PLFU（因?yàn)槠洳辉贋椤静辉诰彺嬷械臄?shù)據(jù)】維護(hù)任何頻率數(shù)據(jù)）。

Aging

是對(duì)In-Memory LFU的優(yōu)化，提高了其對(duì)變化的響應(yīng)能力。

增加了一個(gè)【最大平均引用計(jì)數(shù)】，當(dāng)緩存中的數(shù)據(jù)引用計(jì)數(shù)平均值超過了該值，則將所有的數(shù)據(jù)的頻率技術(shù)都進(jìn)行減少。但是如何減少（一般是存在一個(gè)衰減因子）是一個(gè)棘手且tricky的問題。

WLFU

只保存一個(gè)時(shí)間窗口內(nèi)的訪問數(shù)據(jù)來統(tǒng)計(jì)頻次，這個(gè)機(jī)制要求按照時(shí)序?qū)υL問進(jìn)行持續(xù)的采樣。對(duì)變化的調(diào)整是優(yōu)于PLFU的。

ARC

LIRS

SLRU

2Q

LRU-K

GDSF

簡單說就是對(duì)全流量采樣，TinyLFU需要一種近似的流量統(tǒng)計(jì)結(jié)構(gòu)來替代全量Hash，減少內(nèi)存的占用，并且要盡可能高效，且盡量保持精度。可以詳見3.2

TinyLFU的準(zhǔn)入&淘汰策略是：新增一個(gè)新的元素時(shí)，判斷使用該元素替換一個(gè)舊元素，是否可以提升緩存命中率。

上圖為TinyLFU的主要結(jié)構(gòu)，但是在闡述前需要強(qiáng)調(diào)我們面臨的兩個(gè)主要的挑戰(zhàn)：

維護(hù)一個(gè)新鮮度機(jī)制（freshness mechanism），來保持歷史最近訪問且可以移除舊事件（keep the history recent and remove the history old events）

如何減少內(nèi)存的消耗

Minimal Increment Counting Bloom Filter Counting Bloom Filter參考鏈接

Minimal Increment CBF 和CBF 使用一個(gè)合適大小的計(jì)數(shù)器來代替了Bloom Filter中的bit

Minimal Increment CBF支持以下兩個(gè)方法（下面的闡述，假設(shè)我們的場景是來為key計(jì)算k=3個(gè)hash value，來定位）

Estimate

例如，獲取到3個(gè)hash位置上的計(jì)數(shù)值：{2, 2, 5}，取所有值中的最小值返回

Add

在元素到達(dá)后，獲取到已有的3個(gè)計(jì)數(shù)值{2, 2, 5}，Add操作僅增加兩個(gè)較小的計(jì)數(shù)值，來避免針對(duì)最大值的不必要的增加

TinyLFU使用reset機(jī)制來保證sketch中的數(shù)據(jù)盡可能最新。每增加一個(gè)新的元素到approximation sketches，會(huì)增加一個(gè)計(jì)數(shù)值，一旦計(jì)數(shù)值達(dá)到了一個(gè)預(yù)設(shè)的采樣尺寸（W），就會(huì)將頻率采樣（CBF）維護(hù)的所有計(jì)數(shù)值除以2（可以使用高效的寄存器位移來實(shí)現(xiàn)）；論文也花了較大的篇幅來證明了這種Reset機(jī)制的正確性，且評(píng)估了其存在的截?cái)噱e(cuò)誤（3會(huì)被reset為1，而非1.5），并且得出了以下結(jié)論：

reset在固定的頻率分布下完全正確，且可以應(yīng)對(duì)流量頻率的變化（數(shù)學(xué)歸納法證明，感興趣的可以參考原文3.3.1）

采樣數(shù)W越大，截?cái)噱e(cuò)誤的帶來的影響越小

在兩個(gè)維度減少了空間的占用：

減小了sketch中計(jì)數(shù)值的尺寸

對(duì)于我們的采樣大小W，我們的計(jì)數(shù)值需要占用log(W) bit

減少了sketch分的計(jì)數(shù)器的數(shù)量

Doorkeeper

引入了Doorkeeper機(jī)制，來避免為長尾流量分配計(jì)數(shù)器

由一個(gè)常規(guī)的Bloom Filter攔截在CBF之前

如果一個(gè)元素，在Doorkeeper中，則直接插入TinyLFU的主結(jié)構(gòu)，否則先插入Doorkeeper；對(duì)于數(shù)據(jù)查詢，會(huì)將Doorkeeper中的那一個(gè)計(jì)數(shù)值也加到計(jì)數(shù)值上去

reset操作會(huì)清空Doorkeeper

這樣對(duì)于每個(gè)W周期內(nèi)，都會(huì)過濾僅有一次的訪問的數(shù)據(jù)

盡管Doorkeeper需要一些額外的空間，但是相對(duì)于在主要結(jié)構(gòu)中節(jié)約的空間來說，顯得微不足道。

略

對(duì)于LRU和隨機(jī)緩存而言，緩存存儲(chǔ)本質(zhì)上是個(gè)黑盒。而TinyLFU不同，由于reset機(jī)制的存在，需要在reset時(shí)，同步更新緩存中的item；

主要是優(yōu)化了“sparse bursts（突發(fā)的稀疏流量）”，新的突發(fā)流量可能會(huì)因?yàn)闊o法構(gòu)建足夠的頻率數(shù)據(jù)來保證自己駐留在緩存中。

前端是一個(gè)小的LRU（window cache）；window cache淘汰后，會(huì)送到DoorKeeper過濾；過濾通過后，元素存儲(chǔ)到一個(gè)大的Segmented LRU緩存里。Window LRU，它的容量只占據(jù)1%的總空間，它的目的就是用來存放短期突發(fā)訪問記錄。存放主要元素的Segmented LRU(SLRU)是一種LRU的改進(jìn)，主要把在一個(gè)時(shí)間窗口內(nèi)命中至少2次的記錄和命中1次的多帶帶存放，這樣就可以把短期內(nèi)較頻繁的緩存元素區(qū)分開來。具體做法上，SLRU包含2個(gè)固定尺寸的LRU，一個(gè)叫Probation段A1，一個(gè)叫Protection段A2。新記錄總是插入到A1中，當(dāng)A1的記錄被再次訪問，就把它移到A2，當(dāng)A2滿了需要驅(qū)逐記錄時(shí)，會(huì)把驅(qū)逐記錄插入到A1中。W-TinyLFU中，SLRU有80%空間被分配給A2段。

略