常見的緩存數據淘汰算法

一個緩存組件是否好用，其中一個重要的指標就是他的緩存命中率，而命中率又和緩存組件自己的緩存數據淘汰算法息息相關。

FIFO

FIFO（First in First out）先進先出。能夠理解為是一種相似隊列的算法實現。

算法：最早進來的數據，被認為在將來被訪問的幾率也是最低的，所以，當規定空間用盡且需要放入新數據的時候，會優先淘汰最先進來的數據。
優勢：最簡單、最公平的一種數據淘汰算法，邏輯簡單清晰，易于實現。
缺點：這種算法邏輯設計所實現的緩存的命中率是比較低的，由于沒有任何額外邏輯可以盡量的保證經常使用數據不被淘汰掉。

LRU

LRU（The Least Recently Used）最近最久未使用算法。相比于FIFO算法智能些。

算法：若是一個數據最近不多被訪問到，那么被認為在將來被訪問的幾率也是最低的，當規定空間用盡且需要放入新數據的時候，會優先淘汰最久未被訪問的數據。
優勢：LRU能夠有效的對訪問比較頻繁的數據進行保護，也就是針對熱點數據的命中率提升有明顯的效果。

缺點：對于周期性、偶發性的訪問數據，有大幾率可能形成緩存污染，也就是置換出去了熱點數據，把這些偶發性數據留下了，從而致使LRU的數據命中率急劇降低。

下圖展現了LRU簡單的工做過程，訪問時對數據的提早操做，以及數據滿且添加新數據的時候淘汰的過程的展現以下：

此處介紹的LRU是有明顯的缺點，如上所述，對于偶發性、周期性的數據沒有良好的抵抗力，很容易就形成緩存的污染，影響命中率，所以衍生出了不少的LRU算法的變種，用以處理這種偶發冷數據突增的場景，好比：LRU-K、Two Queues等，目的就是當判別數據為偶發或周期的冷數據時，不會存入空間內，從而下降熱數據的淘汰率。

下圖展現了LRU-K的簡單工做過程，簡單理解，LRU中的K是指數據被訪問K次，傳統LRU與此對比則能夠認為傳統LRU是LRU-1。能夠看到LRU-K有兩個隊列，新來的元素先進入到歷史訪問隊列中，該隊列用于記錄元素的訪問次數，采用的淘汰策略是LRU或者FIFO，當歷史隊列中的元素訪問次數達到K的時候，才會進入緩存隊列。

下圖展現了Two Queues的工做過程，與LRU-K相比，他也一樣是兩個隊列，不一樣之處在于，他的隊列一個是緩存隊列，一個是FIFO隊列，當新元素進來的時候，首先進入FIFO隊列，當該隊列中的元素被訪問的時候，會進入LRU隊列，過程以下：

LFU

LFU（The Least Frequently Used）最近不多使用算法，與LRU的區別在于LRU是以時間衡量，LFU是以時間段內的次數

算法：若是一個數據在必定時間內被訪問的次數很低，那么被認為在將來被訪問的幾率也是最低的，當規定空間用盡且需要放入新數據的時候，會優先淘汰時間段內訪問次數最低的數據。
優勢：LFU也能夠有效的保護緩存，相對場景來說，比LRU有更好的緩存命中率。由于是以次數為基準，因此更加準確，天然能有效的保證和提升命中率。
缺點：由于LFU須要記錄數據的訪問頻率，所以需要額外的空間；當訪問模式改變的時候，算法命中率會急劇降低，這也是他最大弊端。。

下面描述了LFU的簡單工做過程，首先是訪問元素增長元素的訪問次數，從而提升元素在隊列中的位置，下降淘汰優先級，后面是插入新元素的時候，由于隊列已經滿了，因此優先淘汰在必定時間間隔內訪問頻率最低的元素。

W-TinyLFU

W-TinyLFU（Window Tiny Least Frequently Used）是對LFU的的優化和增強。

算法：當一個數據進來的時候，會進行篩選比較，進入W-LRU窗口隊列，以此應對流量突增，通過淘汰后進入過濾器，通過訪問頻率判決是否進入緩存。若是一個數據最近被訪問的次數很低，那么被認為在將來被訪問的幾率也是最低的，當規定空間用盡的時候，會優先淘汰最近訪問次數很低的數據；
優勢：使用Count-Min Sketch算法存儲訪問頻率，極大的節省空間；按期衰減操做，應對訪問模式變化；而且使用window-lru機制可以盡量避免緩存污染的發生，在過濾器內部會進行篩選處理，避免低頻數據置換高頻數據。
缺點：是由谷歌工程師發明的一種算法，目前已知應用于Caffeine Cache組件里。

關于Count-Min Sketch算法，能夠看做是布隆過濾器的同源的算法，假如咱們用一個hashmap來存儲每一個元素的訪問次數，那這個量級是比較大的，而且hash沖突的時候須要作必定處理，不然數據會產生很大的偏差，Count-Min Sketch算法將一個hash操做，擴增為多個hash，這樣原來hash沖突的幾率就下降了幾個等級，且當多個hash取得數據的時候，取最低值，也就是Count Min的含義所在。

下圖展現了Count-Min Sketch算法簡單的工做原理：