LFU算法族相關文章目錄彙總：
LFU算法
LFU-Aging算法
window-LFU算法（本文）
1、LFU算法的不足
LFU（Least Frequently Used）是一種緩存淘汰算法。LFU算法是根據緩存的通路頻率，去淘汰通路次數最低的緩存。這樣就給LFU帶來了兩個問題：
- 不可避免的問題：對于每個緩存項，LFU都需要記錄其通路次數，這導緻了LFU需要一筆不小的額外記憶體開銷；
- 可一定程度避免的問題：對于記錄的通路次數，LFU要對其進行排序，用于淘汰通路次數最低的算法。而對大量資料的排序，則會帶來一定的處理器開銷。當然，這個開銷可以通過在每次操作時調整排序順序，來避免在記憶體淘汰時一次發生。
同時，由于LFU記錄的是緩存生成以來通路頻率，如果一條緩存曾經通路了很多次，但是如果服務的邏輯發生了改變，這條緩存已經很少甚至不再會被通路，這條緩存由于其曆史通路次數很高，依然不會被淘汰。這就導緻了緩存污染的問題：
- 緩存污染：系統将不常用的資料存入到緩存，造成常用資料的擠出，降低了緩存效率的現象。
總結來說，LFU算法有兩個不可避免的問題：
- 對于每個緩存項，LFU都需要記錄其通路次數，需要不小的額外記憶體開銷；
- 近期不再通路的曆史資料無法清理，導緻緩存污染。
2、window-LFU算法描述
Window-LFU被用來一定程度上解決LFU上述兩步不可避免的問題。
Window是用來描述算法儲存的曆史請求數量的視窗大小的。Window-LFU并不記錄所有資料的通路曆史，而隻是記錄過去一段時間内的通路曆史。即當請求次數達到或超過window的大小後，每次有一條新的請求到來，都會清理掉最舊的一條請求，以保證算法記錄的請求次數不超過window的大小。
2.1 緩存通路記錄的維護
在實作時，Window-LFU一般會維護一個定長隊列，或者用數組實作環形緩存區來存儲通路曆史。
例如：一個緩存場景，window = 9，現在有9條緩存通路記錄，按時間順序從先到後分别是：A,B,C,D,A,B,C,D,A，即緩存隊列
此時又來了一條新的緩存請求B，這是Window-LFU算法就會把第一條緩存通路記錄A删掉，并将B加到隊尾：
2.2 緩存淘汰
Window-LFU的緩存淘汰方式和LFU是一緻的。
Window-LFU首先會計算window條記錄中各條緩存項的通路次數，然後根據通路次數排序，淘汰次數最少的緩存項。當然，計算緩存想通路次數的操作，也可以放到每次緩存通路記錄更新的同時，這樣就避免了每次緩存操作的耗時長的問題。
一般來說，Window-LFU會使用哈希結構來存儲“緩存項 <---> 通路次數”的映射，因為哈希的時間複雜度低，為o(1)。
3、Window-LFU的優缺點
3.1 優點
由于Window-LFU不存儲全部曆史資料，是以其額外記憶體開銷要明顯低于LFU算法，同時由于資料量明顯減少，Window-LFU排序的處理器成本也要低于LFU。
另外，由于早于前window次的緩存通路記錄會被清理掉，是以Window-LFU也可以避免緩存污染的問題，因為過早時間通路的緩存已經被清理掉了。
在緩存命中率方面，Window-LFU一般會由于LFU，因為Window-LFU一定程度上解決了緩存污染的問題，緩存的有效性更高了。緩存污染問題越嚴重的場景，Window-LFU的命中率就比LFU高的越多。
另外，和LFU-Aging相比，Window-LFU對緩存污染問題的解決更徹底一些，是以在緩存使用場景産生改變時，命中率會優于LFU-Aging。
3.2 缺點
但是Window-LFU需要維護一個隊列去記錄曆史的通路流，複雜度略高于LFU。