閑話緩存：算法

從前面的文章中，我們已經了解到了緩存設計的目标，緩存設計應該考慮的因素。今天我們來看看一系列緩存算法以及它們如何去解決問題的。同時，我們也會涉及到各種緩存算法的優缺點。

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

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

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

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

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

                                                  i.      它的實作複雜度于緩存大小成對數關系（logarithmic）;

                                                ii.      對最近的緩存單元的通路情況基本沒考慮；

                                              iii.      對通路模式的改變基本上沒有應變的政策。

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

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

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

                                                  i.      它需要維護一個優先級隊列。也就是說它具有對數的實作複雜度；

                                                ii.      它需要一個可調參數：CIP（correlated information period）。

c.       在現實中，對數的實作複雜度是一個非常嚴重的overhead（負擔）。是以另外一個政策2Q被提了出來。

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

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

b.      但是在2Q中，LRU-2的第二個不足還是存在，并且更嚴重了。因為它需要兩個可調參數：Kin和Kout。

c.       為什麼可調參數一個很嚴重的限制？這是我們在實施一個系統時，必須确定這些參數，而且不可更改。一旦确定了一組參數，這個緩存系統往往隻能對某一類workload表現很好。也就是這種緩存系統缺少了自适應性。

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

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

b.      第一個不足在于需要兩個可調參數Llirs 和Lhirs ；

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

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

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

                                                  i.      需要可調參數：緩存中三塊的大小，Cmax 和Amax：大小調整的時間周期。

                                                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.      一種自适應，低成本的淘汰算法

b.      它集合了LRU和LFU的優點，并且沒有額外的使用和實作成本。

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

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