你與解決“緩存污染”只差這篇文章的距離-創(chuàng)新互聯(lián)

什么是緩存污染？

由于緩存的讀取速度比非緩存要快上很多，所以在高性能場景下，系統(tǒng)在讀取數(shù)據(jù)時，是首先從緩存中查找需要的數(shù)據(jù)，如果找到了則直接讀取結(jié)果，如果找不到的話，則從內(nèi)存或者硬盤中查找，再將查找到的結(jié)果存入緩存，以備下次使用。

創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站設(shè)計、網(wǎng)站制作與策劃設(shè)計,零陵網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:零陵等地區(qū)。零陵做網(wǎng)站價格咨詢:13518219792

實際上，對于一個系統(tǒng)來說，緩存的空間是有限且寶貴的，我們不可能將所有的數(shù)據(jù)都放入緩存中進行操作，即便可以數(shù)據(jù)安全性也得不到保證，而且，如果緩存的數(shù)據(jù)量過大大，其速度也會變得越來越慢。 這個時候就需要考慮緩存的淘汰機制，但是淘汰哪些數(shù)據(jù)，又保留哪些數(shù)據(jù)，這是一個問題。如果處理不得當(dāng)，就會造成“緩存污染”問題。

而緩存污染，是指系統(tǒng)將不常用的數(shù)據(jù)從內(nèi)存移到緩存，造成常用數(shù)據(jù)的擠出，降低了緩存效率的現(xiàn)象。

解決緩存污染的算法

LFU算法

LFU，英文名Least Frequently Used，字面意思就是最不經(jīng)常使用的淘汰掉算法，是通過數(shù)據(jù)被訪問的頻率來判斷一個數(shù)據(jù)的熱點情況。其核心理念是“歷史上這個數(shù)據(jù)被訪問次數(shù)越多，那么將來其被訪問的次數(shù)也多”。

LFU中每個數(shù)據(jù)塊都有一個引用計數(shù)器，所有數(shù)據(jù)塊按照引用數(shù)從大到小的排序。

步驟：

1. 新數(shù)據(jù)插入到尾部，并將計數(shù)設(shè)置為1；

2. 當(dāng)隊列中的數(shù)據(jù)被訪問后，引用計數(shù)+1，然后重新排序，保持引用次數(shù)從大到小排序；

3. 當(dāng)空間不足，需要淘汰數(shù)據(jù)時，將尾部引用計數(shù)最小的數(shù)據(jù)塊刪除。

分析：由于是根據(jù)頻數(shù)進行熱點判斷和淘汰，所以先天具備避免偶發(fā)性、周期性批量操作導(dǎo)致臨時非熱點數(shù)據(jù)大量涌入緩存，擠出熱點數(shù)據(jù)的問題。 雖然具備這種先天優(yōu)勢，但依舊存在另一種緩存污染問題，即歷史熱點數(shù)據(jù)污染當(dāng)前熱點數(shù)據(jù)，如果系統(tǒng)訪問模式發(fā)生了改變，新的熱點數(shù)據(jù)需要計數(shù)累加超過舊熱點數(shù)據(jù)，才能將舊熱點數(shù)據(jù)進行淘汰，造成熱點效應(yīng)滯后的問題。

復(fù)雜度與代價：每次操作都需要進行計數(shù)和排序，并且需要維護每個數(shù)據(jù)塊計數(shù)情況，會占用較高的內(nèi)存與cpu。

一個小思考，根據(jù)LFU算法，如何以O(shè)(1)時間復(fù)雜度實現(xiàn)get和put操作緩存？

---

LFU-Aging算法

LFU-Aging是基于LFU的改進算法，目的是解決歷史熱點數(shù)據(jù)對當(dāng)前熱點數(shù)據(jù)的污染問題。有些數(shù)據(jù)在開始時使用次數(shù)很多，但以后就不再使用，這類數(shù)據(jù)將會長時間留在緩存中，所以“除了訪問次數(shù)外，還要考慮訪問時間”，這也是LFU-Aging的核心理念。

雖然算法將時間納入了考量范圍，但LFU-Aging并不是直接記錄數(shù)據(jù)的訪問時間，而是增加了一個大平均引用計數(shù)的閾值，然后通過當(dāng)前平均引用計數(shù)來標(biāo)識時間，換句話說，就是將當(dāng)前緩存中的平均引用計數(shù)值當(dāng)作當(dāng)前的生命年代，當(dāng)這個生命年代超過了預(yù)設(shè)的閾值，就會將當(dāng)前所有計數(shù)值減半，形成指數(shù)衰變的生命年代。

分析：優(yōu)點是當(dāng)訪問模式發(fā)生改變的時候，生命年代的指數(shù)衰變會使LFU-Aging能夠更快的適用新的數(shù)據(jù)訪問模式，淘汰舊的熱點數(shù)據(jù)。

復(fù)雜度與代價：在LFU的基礎(chǔ)上又增加平均引用次數(shù)判斷和統(tǒng)計處理，對cpu的消耗更高，并且當(dāng)平均引用次數(shù)超過指定閾值（Aging）后，還需要遍歷每一個數(shù)據(jù)塊的引用計數(shù)，進行指數(shù)衰變。

Window-LFU算法

Window-LFU顧名思義叫做窗口期LFU，區(qū)別于原義LFU中記錄所有數(shù)據(jù)的訪問歷史，Window-LFU只記錄過去一段時間內(nèi)（窗口期）的訪問歷史，相當(dāng)于給緩存設(shè)置了有效期限，過期數(shù)據(jù)不再緩存。當(dāng)需要淘汰時，將這個窗口期內(nèi)的數(shù)據(jù)按照LFU算法進行淘汰。

分析：由于是維護一段窗口期的記錄，數(shù)據(jù)量會比較少，所以內(nèi)存占用和cpu消耗都比LFU要低。并且這段窗口期相當(dāng)于給緩存設(shè)置了有效期，能夠更快的適應(yīng)新的訪問模式的變化，緩存污染問題基本不嚴重。

復(fù)雜度與代價：維護一段時期內(nèi)的數(shù)據(jù)訪問記錄，并對其排序。

---

LRU算法

LRU算法，英文名Least Recently Used，意思是最近最少使用的淘汰算法，根據(jù)數(shù)據(jù)的歷史訪問記錄來進行淘汰數(shù)據(jù)，核心思想是“如果數(shù)據(jù)最近被訪問過1次，那么將來被訪問的概率會更高”，類似于就近優(yōu)先原則。

步驟：

1. 新數(shù)據(jù)插入到鏈表頭部；

2. 每當(dāng)命中緩存，便將命中的緩存數(shù)據(jù)移到鏈表頭部；

3. 當(dāng)鏈表滿的時候，將鏈表尾部的數(shù)據(jù)丟棄。

分析：偶發(fā)性的、周期性的批量操作會使臨時數(shù)據(jù)涌入緩存，擠出熱點數(shù)據(jù)，導(dǎo)致LRU熱點命中率急劇下降，緩存污染情況比較嚴重。

復(fù)雜度與代價：數(shù)據(jù)結(jié)構(gòu)復(fù)雜度較低；每次需要遍歷鏈表，找到命中的數(shù)據(jù)塊，然后將數(shù)據(jù)移到頭部。

LRU-K算法

LRU-K是基于LRU算法的優(yōu)化版，其中K代表最近訪問的次數(shù)，從某種意義上，LRU可以看作是LRU-1算法，引入K的意義是為了解決上面所提到的緩存污染問題。其核心理念是從“數(shù)據(jù)最近被訪問過1次”蛻變成“數(shù)據(jù)最近被訪問過K次，那么將來被訪問的概率會更高”。

LRU-K與LRU區(qū)別是，LRU-K多了一個數(shù)據(jù)訪問歷史記錄隊列（需要注意的是，訪問歷史記錄隊列并不是緩存隊列，所以是不保存數(shù)據(jù)本身的，只是保存對數(shù)據(jù)的訪問記錄，數(shù)據(jù)此時依舊在原始存儲中），隊列中維護著數(shù)據(jù)被訪問的次數(shù)以及時間戳，只有當(dāng)這個數(shù)據(jù)被訪問的次數(shù)大于等于K值時，才會從歷史記錄隊列中刪除，然后把數(shù)據(jù)加入到緩存隊列中去。

步驟：

1. 數(shù)據(jù)第一次被訪問時，加入到歷史訪問記錄隊列中，訪問次數(shù)為1，初始化訪問時間戳；

2. 如果數(shù)據(jù)訪問次數(shù)沒有達到K次，則訪問次數(shù)+1，更新時間戳。當(dāng)隊列滿了時，按照某種規(guī)則（LRU或者FIFO）將歷史記錄淘汰。為了避免歷史數(shù)據(jù)污染未來數(shù)據(jù)的問題，還需要加上一個有效期限，對超過有效期的訪問記錄，進行重新計數(shù)。（可以使用懶處理，即每次對訪問記錄做處理時，先將記錄中的訪問時間與當(dāng)前時間進行對比，如果時間間隔超過預(yù)設(shè)的值，則訪問次數(shù)重置為1并更新時間戳，表示重新開始計數(shù)）

3. 當(dāng)數(shù)據(jù)訪問計數(shù)大于等于K次后，將數(shù)據(jù)從歷史訪問隊列中刪除，更新數(shù)據(jù)時間戳，保存到緩存隊列頭部中（緩存隊列時間戳遞減排序，越到尾部距離當(dāng)前時間越長）；

4. 緩存隊列中數(shù)據(jù)被再次訪問后，將其移到頭部，并更新時間戳；

5. 緩存隊列需要淘汰數(shù)據(jù)時，淘汰緩存隊列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問離現(xiàn)在最久”的數(shù)據(jù)。

分析：LRU-K降低了“緩存污染”帶來的問題，命中率比LRU要高。實際應(yīng)用中LRU-2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會高，但適應(yīng)性差，一旦訪問模式發(fā)生變化，需要大量的新數(shù)據(jù)訪問才能將歷史熱點訪問記錄清除掉。

復(fù)雜度與代價：LRU-K隊列是一個優(yōu)先級隊列。由于LRU-K需要記錄那些被訪問過，但還沒有放入緩存的對象，導(dǎo)致內(nèi)存消耗會很多。

URL-Two queues算法

URL-Two queues算法類似于LRU-2，不同點在于URL-Two queues將LRU-2算法中的訪問歷史隊列（注意這不是緩存數(shù)據(jù)的）改為一個FIFO緩存隊列，即：URL-Two queues算法有兩個緩存隊列，一個是FIFO隊列（First in First out，先進先出），一個是LRU隊列。

當(dāng)數(shù)據(jù)第一次訪問時，URL-Two queues算法將數(shù)據(jù)緩存在FIFO隊列里面，當(dāng)數(shù)據(jù)第二次被訪問時，則將數(shù)據(jù)從FIFO隊列移到LRU隊列里面，兩個隊列各自按照自己的方法淘汰數(shù)據(jù)。

步驟：

1. 新訪問的數(shù)據(jù)先插入到FIFO隊列中；

2. 如果數(shù)據(jù)在FIFO隊列中一直沒有被再次訪問，則最終按照FIFO規(guī)則淘汰；

3. 如果數(shù)據(jù)在FIFO隊列中被再次訪問，則將數(shù)據(jù)從FIFO刪除，加入到LRU隊列頭部；

4. 如果數(shù)據(jù)在LRU隊列再次被訪問，則將數(shù)據(jù)移到LRU隊列頭部；

5. LRU隊列淘汰末尾的數(shù)據(jù)。

分析：URL-Two queues算法和LRU-2算法命中率類似，但是URL-Two queues會減少一次從原始存儲讀取或計算數(shù)據(jù)的操作。命中率要高于LRU。

復(fù)雜度與代價：需要維護兩個隊列，代價是FIFO和LRU代價之和。

五三LRU算法

emmmm...

這個名字其實是我取的，大概是這種算法還沒有被命名？當(dāng)然，這是一個玩笑話。

我是在mysql底層實現(xiàn)里發(fā)現(xiàn)這個算法的，mysql在處理緩存淘汰時是用的這個方法，有點像URL-Two queues的變體，只是我們只需要維護一個隊列，然后將隊列按照5:3的比例進行分割，5的那部分叫做young區(qū)，3的那部分叫做old區(qū)。具體是怎么樣的請先看我把圖畫出來：

步驟：

1. 第一次訪問的數(shù)據(jù)從隊列的3/8處位置插入；

2. 如果數(shù)據(jù)再次被訪問，則移動到隊列頭部；

3. 如果數(shù)據(jù)沒有被再訪問，會逐步被熱點數(shù)據(jù)驅(qū)逐向下移；

4. 淘汰尾部數(shù)據(jù)。

分析：五三LRU算法算作是URL-Two queues算法的變種，原理其實是一樣的，只是把兩個隊列合二為一個隊列進行數(shù)據(jù)的處理，所以命中率和URL-Two queues算法一樣。

復(fù)雜度與代價：維護一個隊列，代價較低，但是內(nèi)存占用率和URL-Two queues一樣。

Multi Queue算法

Multi Queue算法根據(jù)訪問頻率將數(shù)據(jù)劃分為多個隊列，不同的隊列具有不同的訪問優(yōu)先級，其核心思想是“優(yōu)先緩存訪問次數(shù)多的數(shù)據(jù)”。

Multi Queue算法將緩存劃分為多個LRU隊列，每個隊列對應(yīng)不同的訪問優(yōu)先級。訪問優(yōu)先級是根據(jù)訪問次數(shù)計算出來的，例如： Q0，Q1....Qn代表不同的優(yōu)先級隊列，Q-history代表從緩存中淘汰數(shù)據(jù)，但記錄了數(shù)據(jù)的索引和引用次數(shù)。

步驟：

1. 新插入的數(shù)據(jù)放入Q0；

2. 每個隊列按照LRU管理數(shù)據(jù)，再次訪問的數(shù)據(jù)移動到頭部；

3. 當(dāng)數(shù)據(jù)的訪問次數(shù)達到一定次數(shù)，需要提升優(yōu)先級時，將數(shù)據(jù)從當(dāng)前隊列刪除，加入到高一級隊列的頭部；

4. 為了防止高優(yōu)先級數(shù)據(jù)永遠不被淘汰，當(dāng)數(shù)據(jù)在指定的時間里訪問沒有被訪問時，需要降低優(yōu)先級，將數(shù)據(jù)從當(dāng)前隊列刪除，加入到低一級的隊列頭部；

5. 需要淘汰數(shù)據(jù)時，從最低一級隊列開始按照LRU淘汰；每個隊列淘汰數(shù)據(jù)時，將數(shù)據(jù)從緩存中刪除，將數(shù)據(jù)索引加入Q-history頭部；

6. 如果數(shù)據(jù)在Q-history中被重新訪問，則重新計算其優(yōu)先級，移到目標(biāo)隊列的頭部；

7. Q-history按照LRU淘汰數(shù)據(jù)的索引。

分析：Multi Queue降低了“緩存污染”帶來的問題，命中率比LRU要高。

復(fù)雜度與代價：Multi Queue需要維護多個隊列，且需要維護每個數(shù)據(jù)的訪問時間，復(fù)雜度比LRU高。Multi Queue需要記錄每個數(shù)據(jù)的訪問時間，需要定時掃描所有隊列，代價比LRU要高。雖然Multi Queue的隊列看起來數(shù)量比較多，但由于所有隊列之和受限于緩存容量的大小，因此這里多個隊列長度之和和一個LRU隊列是一樣的，因此隊列掃描性能也相近。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章題目：你與解決“緩存污染”只差這篇文章的距離-創(chuàng)新互聯(lián)
瀏覽地址：http://muchs.cn/article32/dhjosc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、軟件開發(fā)、外貿(mào)建站、Google、品牌網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)