從前面的文章中，我們已經(jīng)了解到了緩存設(shè)計的目標，緩存設(shè)計應(yīng)該考慮的因素。今天我們來看看一系列緩存算法以及它們?nèi)绾稳ソ鉀Q問題的。同時，我們也會涉及到各種緩存算法的優(yōu)缺點。

這里我并不想討論與預(yù)取（pre-fetch）相關(guān)的算法，主要是考慮各種淘汰算法。因為相比于預(yù)取算法，淘汰算法具有更大的通用性，對緩存好壞影響更大。

1.????? 時間（完全從最近使用的時間角度考慮）

a.????? LRU（least recently used）：這種策略就是永遠替換掉最近最少使用的緩存單元。它是最古老，應(yīng)用最廣泛的的一種淘汰算法。它的致命的缺陷就是沒有考慮緩存單元的使用頻率，在某些I/O 模式中，會把一些有價值的緩存單元替換出去。比如，假設(shè)我們有10個緩存單元，客戶端應(yīng)用來了一次順序讀寫，這樣可能把這10個現(xiàn)有的緩存單元替換出去，而把這次順序讀寫的數(shù)據(jù)緩存起來。但是，這種順序讀寫的數(shù)據(jù)在以后都不會被再次用到。反而，那些因為順序讀而被替換出去的緩存單元卻是更有價值的。為此，有了各種各樣的基于LRU的優(yōu)化策略被提出來。

2.????? 頻率（完全從使用頻率的角度考慮）

a.????? LFU（least frequently used）: IRM(獨立的引用模型)提供了一種用來獲取頻率的負載特性。它趨向于淘汰最近使用頻率最少的緩存單元。這種策略的弊端是：

????????????????????????????????????????????????? i.????? 它的實現(xiàn)復雜度于緩存大小成對數(shù)關(guān)系（logarithmic）;

??????????????????????????????????????????????? ii.????? 對最近的緩存單元的訪問情況基本沒考慮；

????????????????????????????????????????????? iii.????? 對訪問模式的改變基本上沒有應(yīng)變的策略。

3.????? LRU-2（LRU-K）：一種對LRU的改進型策略 （頻率）

a.????? LRU-2于LFU很相似，如果我們不考慮它對緩存單元引用頻率進化分布的自適應(yīng)性。它的基本思想是對每一個緩存單元，記住最近兩次訪問的時間。總是淘汰最近兩次時間間隔最長的緩存單元。在IRM的假設(shè)下，對于任何知道最多兩次最近引用緩存單元的在線算法，我們可以得出LRU-2具有最高的命中率。

b.????? 但是LRU-2也有一些實際的限制：

????????????????????????????????????????????????? i.????? 它需要維護一個優(yōu)先級隊列。也就是說它具有對數(shù)的實現(xiàn)復雜度；

??????????????????????????????????????????????? ii.????? 它需要一個可調(diào)參數(shù)：CIP（correlated information period）。

c.?????? 在現(xiàn)實中，對數(shù)的實現(xiàn)復雜度是一個非常嚴重的overhead（負擔）。所以另外一個策略2Q被提了出來。

4.????? 2Q：對LRU-2的改進策略 （頻率）

a.????? 相對于LRU-2，2Q的主要改進是用一個簡單的LRU list取代了LRU-2中的優(yōu)先級隊列。其它的2Q和LRU-2基本相同。

b.????? 但是在2Q中，LRU-2的第二個不足還是存在，并且更嚴重了。因為它需要兩個可調(diào)參數(shù)：K_in和K_out。

c.?????? 為什么可調(diào)參數(shù)一個很嚴重的限制？這是我們在實施一個系統(tǒng)時，必須確定這些參數(shù)，而且不可更改。一旦確定了一組參數(shù)，這個緩存系統(tǒng)往往只能對某一類workload表現(xiàn)很好。也就是這種緩存系統(tǒng)缺少了自適應(yīng)性。

5.????? LIRS（Low Inter-reference Recency Set）（頻率）

a.????? 詳細描述參考：“LIRS： An efficient low inter-reference recency set replacement policy to improve buffer cache performance”

b.????? 第一個不足在于需要兩個可調(diào)參數(shù)L_lirs?和L_hirs?；

c.?????? 它的第二個缺點在于，在最壞的情況下，它需要一個“棧修剪”。這個操作需要遍歷數(shù)量龐大的緩存單元。

6.????? 時間和頻率（同時考慮時間和頻率的算法：LRU和LFU）

a.????? FBR（Frequency-based replacement）:詳細描述請參考“Data cache management using frequency-based replacement”。這個算法的不足之處在于：

????????????????????????????????????????????????? i.????? 需要可調(diào)參數(shù)：緩存中三塊的大小，C_max?和A_max：大小調(diào)整的時間周期。

??????????????????????????????????????????????? ii.????? Cache pollution（解決cache污染的機制）

b.????? LRFU（Least Recently/Frequently Used）: 參考“LRFU： A spectrum of policies that subsumes the least recently used and least frequently used policies”

c.?????? ALRFU(adaptive LRFU): 參考“On the existence of a spectrum of policies that subsumes the least recently used and least frequently used policies”

7.????? 臨時距離分布（Temporal distance distribution）

a.????? MQ(multi-queue replacement policy MQ ): 參考“The multi-queue replacement algorithm for second level buffer caches”

8.????? ARC: adaptive replacement cache(IBM), adjusted replacement cache(ZFS)

a.????? 一種自適應(yīng)，低成本的淘汰算法

b.????? 它集合了LRU和LFU的優(yōu)點，并且沒有額外的使用和實現(xiàn)成本。

c.?????? 它可以更具workload的改變而自動的改變淘汰策略。

ARC是目前應(yīng)用非常廣泛的一種淘汰算法。我們應(yīng)該詳細的研究它，并實現(xiàn)它。在ZFS源碼中就是它的完整實現(xiàn)。當然，ZFS中的實現(xiàn)和IBM當初提出的內(nèi)容有點改變。這個我們留在下篇文章中講述。

總結(jié)

以上是生活随笔為你收集整理的闲话缓存：算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。