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

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

FIFO

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

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

LRU

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

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

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

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

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

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

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

LFU

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

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

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

W-TinyLFU

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

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

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

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

假設(shè)有四個(gè)hash函數(shù)，每當(dāng)元素被訪問時(shí)，將進(jìn)行次數(shù)加1；
此時(shí)會按照約定好的四個(gè)hash函數(shù)進(jìn)行hash計(jì)算找到對應(yīng)的位置，相應(yīng)的位置進(jìn)行+1操做；
當(dāng)獲取元素的頻率時(shí)，一樣根據(jù)hash計(jì)算找到4個(gè)索引位置；
取得四個(gè)位置的頻率信息，而后根據(jù)Count Min取得最低值做為本次元素的頻率值返回，即Min(Count)；