緩存（5）：常見緩存數據淘汰算法/緩存清空策略

主要的三種緩存數據淘汰算法

FIFO(first in first out)：先進先出策略，最先進入緩存的數據在緩存空間不夠的情況下（超出最大元素限制）會被優先被清除掉，以騰出新的空間接受新的數據。策略算法主要比較緩存元素的創建時間。在數據實效性要求場景下可選擇該類策略，優先保障最新數據可用。

LFU(less frequently used)：最少使用策略，無論是否過期，根據元素的被使用次數判斷，清除使用次數較少的元素釋放空間。策略算法主要比較元素的hitCount（命中次數）。在保證高頻數據有效性場景下，可選擇這類策略。

LRU(least recently used)：最近最少使用策略，無論是否過期，根據元素最后一次被使用的時間戳，清除最遠使用時間戳的元素釋放空間。策略算法主要比較元素最近一次被get使用時間。在熱點數據場景下較適用，優先保證熱點數據的有效性。

其他的一些簡單策略比如：

根據過期時間判斷，清理過期時間最長的元素；
根據過期時間判斷，清理最近要過期的元素；
隨機清理；
根據關鍵字（或元素內容）長短清理等。

FIFO

算法：最先進來的數據，被認為在未來被訪問的概率也是最低的，因此，當規定空間用盡且需要放入新數據的時候，會優先淘汰最早進來的數據

優點：最簡單、最公平的一種數據淘汰算法，邏輯簡單清晰，易于實現

缺點：這種算法邏輯設計所實現的緩存的命中率是比較低的，因為沒有任何額外邏輯能夠盡可能的保證常用數據不被淘汰掉

LRU-時間（適用局部突發流量場景）

算法：如果一個數據最近很少被訪問到，那么被認為在未來被訪問的概率也是最低的，當規定空間用盡且需要放入新數據的時候，會優先淘汰最久未被訪問的數據

優點：

LRU 實現簡單，在一般情況下能夠表現出很好的命中率，是一個“性價比”很高的算法。
LRU可以有效的對訪問比較頻繁的數據進行保護，也就是針對熱點數據的命中率提高有明顯的效果。
LRU局部突發流量場景，對突發性的稀疏流量（sparse bursts）表現很好。

缺點：

在存在周期性的局部熱點數據場景，有大概率可能造成緩存污染。
最近訪問的數據，并不一定是周期性數據，比如把全量的數據做一次迭代，那么LRU 會產生較大的緩存污染，因為周期性的局部熱點數據，可能會被淘汰。

LRU-K

算法：LRU中的K是指數據被訪問K次，傳統LRU與此對比則可以認為傳統LRU是LRU-1

LRU-K有兩個隊列，新來的元素先進入到歷史訪問隊列中，該隊列用于記錄元素的訪問次數，采用的淘汰策略是LRU或者FIFO，
當歷史隊列中的元素訪問次數達到K的時候，才會進入緩存隊列

Two Queues

Two Queues與LRU-K相比，他也同樣是兩個隊列，不同之處在于，他的隊列一個是緩存隊列，一個是FIFO隊列，
當新元素進來的時候，首先進入FIFO隊列，當該隊列中的元素被訪問的時候，會進入LRU隊列

LFU-頻率（適用局部周期性流量場景）

算法：如果一個數據在一定時間內被訪問的次數很低，那么被認為在未來被訪問的概率也是最低的，當規定空間用盡且需要放入新數據的時候，會優先淘汰時間段內訪問次數最低的數據

優點：

LFU適用于局部周期性流量場景，在這個場景下，比LRU有更好的緩存命中率。
在局部周期性流量場景下， LFU是以次數為基準，所以更加準確，自然能有效的保證和提高命中率

缺點：

因為LFU需要記錄數據的訪問頻率，因此需要額外的空間；
它需要給每個記錄項維護頻率信息，每次訪問都需要更新，這是個巨大的開銷；
在**存在局部突發流量場景下，有大概率可能造成緩存污染，算法命中率會急劇下降，這也是他最大弊端。** 所以，LFU 對突發性的稀疏流量（sparse bursts）是無效的。

LFU 按照訪問次數或者訪問頻率取勝，這個次數有一個累計的長周期，導致前期經常訪問的數據，訪問次數很大，或者說權重很高

新來的緩存數據，哪怕他是突發熱點，但是，新數據的訪問次數累計的時間太短
老的記錄已經占用了緩存，過去的一些大量被訪問的記錄，在將來不一定會繼續是熱點數據，但是就一直把“坑”占著了，而那些偶然的突破熱點數據，不太可能會被保留下來，而是被淘汰
所以，存在突發性的稀疏流量下，LFU中的偶然的、稀疏的突發流量在訪問頻率上，不占優勢，很容易被淘汰，造成緩存污染和未來緩存命中率下降

TinyLFU

概述

TinyLFU 就是其中一個優化算法，專門為了解決 LFU 上的三個問題而被設計出來的。

LFU 上的三個問題如下

如何減少訪問頻率的保存，所帶來的空間開銷
如何減少訪問記錄的更新，所帶來的時間開銷
如果提升對局部熱點數據的算法命中率

解決第1個問題/第2個問題是采用了 Count–Min Sketch 算法

Count-Min Sketch算法將一個hash操作，擴增為多個hash，這樣原來hash沖突的概率就降低了幾個等級，且當多個hash取得數據的時候，取最低值，也就是Count Min的含義所在。

Count–Min Sketch 的原理跟 Bloom Filter 一樣，只不過Bloom Filter 只有 0 和 1的值，可以把 Count–Min Sketch 看作是“數值”版的 Bloom Filter。

解決第三個問題是讓老的訪問記錄，盡量降低“新鮮度”

Count–Min Sketch 算法

工作原理

ount-Min Sketch算法簡單的工作原理：

假設有四個hash函數，每當元素被訪問時，將進行次數加1；
此時會按照約定好的四個hash函數進行hash計算找到對應的位置，相應的位置進行+1操作；
當獲取元素的頻率時，同樣根據hash計算找到4個索引位置；
取得四個位置的頻率信息，然后根據Count Min取得最低值作為本次元素的頻率值返回，即Min(Count);

空間開銷

Count-Min Sketch訪問次數的空間開銷？

用4個hash函數會存訪問次數，那空間就是4倍
解決：
- 訪問次數超過15次其實是很熱的數據了，沒必要存太大的數字。所以我們用4位就可以存到15
- 一個訪問次數占4個位，一個long有64位，可以存 16個訪問次數，4個訪問一次一組的話，一個long 可以分為4組
- 一個 key 對應到 4個hash 值，也就是 4個訪問次數，一個long 可以分為存儲 4個Key的訪問次數
- 最終：一個long對應的數組大小其實是容量的4倍（本來一個long是一個key的，但是現在可以存4個key）

降鮮機制

提升對局部熱點數據的算法命中率

讓緩存降低“新鮮度”，剔除掉過往頻率很高，但之后不經常的緩存

Caffeine 有一個 Freshness Mechanism。

做法：當整體的統計計數（當前所有記錄的頻率統計之和，這個數值內部維護）達到某一個值時，那么所有記錄的頻率統計除以 2。

TinyLFU 的算法流程

當緩存空間不夠的時候，TinyLFU 找到要淘汰的元素（the cache victim），也就是使用頻率最小的元素 ，
然后 TinyLFU 決定將新元素放入緩存，替代將要淘汰的元素 （the cache victim）

W-TinyLFU

演進

TinyLFU 在面對突發性的稀疏流量（sparse bursts）時表現很差

新的記錄（new items）還沒來得及建立足夠的頻率就被剔除出去了，這就使得命中率下降

W-TinyLFU是 LFU 的變種，也是TinyLFU的變種

W-TinyLFU是如何演進：W-TinyLFU = LRU + LFU

LRU能很好的處理局部突發流量
LFU能很好的處理局部周期流量

W-TinyLFU（Window Tiny Least Frequently Used）是對TinyLFU的的優化和加強，加入 LRU 以應對局部突發流量，從而實現緩存命中率的最優。

W-TinyLFU 在空間效率和訪問命中率之間達到了顯著平衡，成為現代緩存庫（如 Caffeine）的核心算法。

數據結構

W-TinyLFU增加了一個 W-LRU窗口隊列的組件

當一個數據進來的時候，會進行篩選比較，進入W-LRU窗口隊列
經過淘汰后進入Count-Min Sketch算法過濾器，通過訪問訪問頻率判決, 是否進入緩存

作用：如果一個數據最近被訪問的次數很低，那么被認為在未來被訪問的概率也是最低的，當規定空間用盡的時候，會優先淘汰最近訪問次數很低的數據

W-LRU窗口隊列用于應對局部突發流量
TinyLFU 用于應對局部周期流量

存儲空間結構

W-TinyLFU將緩存存儲空間分為兩個大的區域：Window Cache和Main Cache

Window Cache：是一個標準的LRU Cache
Main Cache：是一個SLRU（Segmemted LRU）cache，劃分為Protected Cache（保護區）和Probation Cache（考察區）兩個區域，這兩個區域都是基于LRU的Cache。
- 精細化淘汰：使用 TinyLFU 算法（基于概率型頻率統計）結合 SLRU（Segmented LRU，分段LRU）策略，區分高頻和低頻條目。
- 長期頻率管理：存儲經過 Window Cache 篩選的高頻訪問條目，基于訪問頻率決定保留優先級。
- Protected 是一個受保護的區域，該區域中的緩存項不會被淘汰
  - 存儲長期高頻訪問的條目（“熱數據”）。
  - 占比約 80%，使用 LRU 淘汰策略。
- Probation Region（觀察區）
  - 存儲候選條目，與 Window Cache 淘汰的條目競爭。
  - 占比約 20%，使用 TinyLFU 比較頻率決定去留。

空間最優選：當 window 區配置為總容量的 1%，剩余的 99%當中的 80%分給 protected 區，20%分給 probation 區時，這時整體性能和命中率表現得最好，所以 Caffeine 默認的比例設置就是這個。

這個比例 Caffeine 會在運行時根據統計數據（statistics）去動態調整，如果你的應用程序的緩存隨著時間變化比較快的話，或者說具備的突發特點數據多，那么增加 window 區的比例可以提高命中率
如果周期性熱地數據多，緩存都是比較固定不變的話，增加 Main Cache 區（protected 區 +probation 區）的比例會有較好的效果。