常見的緩存數(shù)據(jù)淘汰算法

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

FIFO

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

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

LRU

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

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

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

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

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

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

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

LFU

LFU（The Least Frequently Used）最近不多使用算法，與LRU的區(qū)別在于LRU是以時間衡量，LFU是以時間段內(nèi)的次數(shù)

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

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

W-TinyLFU

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

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

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

下圖展現(xiàn)了Count-Min Sketch算法簡單的工做原理：