614
緩存淘汰算法係列之2——LFU類
1. LFU類
1.1. LFU
1.1.1. 原理
LFU（Least Frequently Used）算法根據數據的曆史訪問頻率來淘汰數據，其核心思想是“如果數據過去被訪問多次，那麼將來被訪問的頻率也更高”。
1.1.2. 實現
LFU的每個數據塊都有一個引用計數，所有數據塊按照引用計數排序，具有相同引用計數的數據塊則按照時間排序。
具體實現如下：
1. 新加入數據插入到隊列尾部（因為引用計數為1）；
2. 隊列中的數據被訪問後，引用計數增加，隊列重新排序；
3. 當需要淘汰數據時，將已經排序的列表最後的數據塊刪除。
1.1.3. 分析
l 命中率
一般情況下，LFU效率要優於LRU，且能夠避免周期性或者偶發性的操作導致緩存命中率下降的問題。但LFU需要記錄數據的曆史訪問記錄，一旦數據訪問模式改變，LFU需要更長時間來適用新的訪問模式，即：LFU存在曆史數據影響將來數據的“緩存汙染”效用。
l 複雜度
需要維護一個隊列記錄所有數據的訪問記錄，每個數據都需要維護引用計數。
l 代價
需要記錄所有數據的訪問記錄，內存消耗較高；需要基於引用計數排序，性能消耗較高。
1.2. LFU*
1.2.1. 原理
基於LFU的改進算法，其核心思想是“隻淘汰訪問過一次的數據”。
1.2.2. 實現
LFU*數據緩存實現和LFU一樣，不同的地方在於淘汰數據時，LFU*隻淘汰引用計數為1的數據，且如果所有引用計數為1的數據大小之和都沒有新加入的數據那麼大，則不淘汰數據，新的數據也不緩存。
1.2.3. 分析
l 命中率
和LFU類似，但由於其不淘汰引用計數大於1的數據，則一旦訪問模式改變，LFU*無法緩存新的數據，因此這個算法的應用場景比較有限。
l 複雜度
需要維護一個隊列，記錄引用計數為1的數據。
l 代價
相比LFU要低很多，不需要維護所有數據的曆史訪問記錄，隻需要維護引用次數為1的數據，也不需要排序。
1.3. LFU-Aging
1.3.1. 原理
基於LFU的改進算法，其核心思想是“除了訪問次數外，還要考慮訪問時間”。這樣做的主要原因是解決LFU緩存汙染的問題。
1.3.2. 實現
雖然LFU-Aging考慮時間因素，但其算法並不直接記錄數據的訪問時間，而是通過平均引用計數來標識時間。
LFU-Aging在LFU的基礎上，增加了一個最大平均引用計數。當當前緩存中的數據“引用計數平均值”達到或者超過“最大平均引用計數”時，則將所有數據的引用計數都減少。減少的方法有多種，可以直接減為原來的一半，也可以減去固定的值等。
1.3.3. 分析
l 命中率
LFU-Aging的效率和LFU類似，當訪問模式改變時，LFU-Aging能夠更快的適用新的數據訪問模式，效率要高。
l 複雜度
在LFU的基礎上增加平均引用次數判斷和處理。
l 代價
和LFU類似，當平均引用次數超過指定閾值（Aging）後，需要遍曆訪問列表。
1.4. LFU*-Aging
1.4.1. 原理
LFU*和LFU-Aging的合成體。
1.4.2. 實現
略。
1.4.3. 分析
l 命中率
和LFU-Aging類似。
l 複雜度
比LFU-Aging簡單一些，不需要基於引用計數排序。
l 代價
比LFU-Aging少一些，不需要基於引用計數排序。
1.5. Window-LFU
1.5.1. 原理
Windows-LFU是LFU的一個改進版，差別在於Window-LFU並不記錄所有數據的訪問曆史，而隻是記錄過去一段時間內的訪問曆史，這就是Window的由來，基於這個原因，傳統的LFU又被稱為“Perfect-LFU”。
1.5.2. 實現
與LFU的實現基本相同，差別在於不需要記錄所有數據的曆史訪問數據，而隻記錄過去一段時間內的訪問曆史。具體實現如下：
1）記錄了過去W個訪問記錄；
2）需要淘汰時，將W個訪問記錄按照LFU規則排序淘汰
舉例如下：
假設曆史訪問記錄長度設為9，緩存大小為3，圖中不同顏色代表針對不同數據塊的訪問，同一顏色代表針對同一數據的多次訪問。
樣例1：黃色訪問3次，藍色和橘色都是兩次，橘色更新，因此緩存黃色、橘色、藍色三個數據塊
樣例2：綠色訪問3次，藍色兩次，暗紅兩次，藍色更新，因此緩存綠色、藍色、暗紅三個數據塊
1.5.3. 分析
l 命中率
Window-LFU的命中率和LFU類似，但Window-LFU會根據數據的訪問模式而變化，能夠更快的適應新的數據訪問模式，”緩存汙染“問題不嚴重。
l 複雜度
需要維護一個隊列，記錄數據的訪問流曆史；需要排序。
l 代價
Window-LFU隻記錄一部分的訪問曆史記錄，不需要記錄所有的數據訪問曆史，因此內存消耗和排序消耗都比LFU要低。
1.6. LFU類算法對比
由於不同的訪問模型導致命中率變化較大，此處對比僅基於理論定性分析，不做定量分析。
|
對比點 |
對比 |
|
命中率 |
Window-LFU/LFU-Aging > LFU*-Aging > LFU > LFU* |
|
複雜度 |
LFU-Aging > LFU> LFU*-Aging >Window-LFU > LFU* |
|
代價 |
LFU-Aging > LFU > Window-LFU > LFU*-Aging > LFU* |
最後更新：2017-04-02 16:47:37