redis——Redis中的LRU算法改進

redis通常使用緩存，是使用一種固定最大內存的使用。當數據達到可使用的最大固定內存時，我們需要通過移除老數據來獲取空間。redis作為緩存是否有效的重要標志是如何尋找一種好的策略：刪除即將需要使用的數據是一種糟糕的策略，而刪除那些很少再次請求的數據則是一種好的策略。
在其他的緩存組件還有個命中率，僅僅表示讀請求的比例。訪問一個緩存中的keys通常不是分布式的。然而訪問經常變化，這意味著不經常訪問，相反，有些keys一旦不流行可能會轉向最經常訪問的keys。因此，通常一個緩存系統應該盡可能保留那些未來最有可能被訪問的keys。針對keys淘汰的策略是：那些未來極少可能被訪問的數據應該被移除。
但有一個問題：redis和其他緩存系統不能夠預測未來。

LRU算法

緩存系統不能預測未來，原因是：那些很少再次被訪問的key也很有可能最近訪問相當頻繁。如果經常被訪問的模式不會突然改變，那么這是一種很有效的策略。然而，“最近經常被訪問”似乎更隱晦地標明一種理念。這種算法被稱為LRU算法。最近訪問頻繁的key相比訪問少的key有更高的可能性。
舉個例子，這里有4個不同訪問周期的key，每一個“~”字符代表一秒，結尾的“|”表示當前時刻。

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|

A key每5秒請求一次，B周期是2秒，C、D都是10秒。
訪問頻率最高的是B，因為它的空閑時間最短，這意味著B是4個key中未來最有可能被訪問的key。
同樣的A和C目前的空閑時間是2s和6s也能很好地反映它們本身的周期。然而你可以看到不夠嚴謹：D的訪問周期是10秒，但它卻是4個key中最近被訪問的。
當然，在一個很長的運行周期中，LRU算法能工作得很好。通常有一個更高訪問頻率的key當然有一個更低的空閑周期。LRU算法淘汰最少被訪問key，那些有最大空閑周期的key。實現上也相當容易，只需要額外跟蹤最近被訪問的key即可，有時甚至都需要：把所有我們想要淘汰的對象放到一個鏈表中，當一個對象訪問就移除鏈表頭部元素，當我們要淘汰元素是就直接淘汰鏈表尾部開始。

redis中的LRU:起因

最初，redis不支持LRU算法。當內存有效性成為一個必須被解決的問題時，后來才加上了。通過修改redis對象結構，在每個key對象增加24bit的空間。沒有額外的空間使用鏈表把所有對象放到一個鏈表中（大指針），因此需要實現得更加有效，不能因為key淘汰算法而讓整個服務改動太大。
24bits的對象已經足夠去存儲當前的unxi時間戳。這個表現，被稱為“LRU 時鐘”，key元數據經常被更新，所以它是一個有效的算法。
然后，有另一個更加復雜的問題需要解決：如何選擇訪問間隔最長的key，然后淘汰它。
redis內部采用一個龐大的hash table來保存，添加另外一個數據結構存儲時間間隔顯然不是一個好的選擇。然而我們希望能達到一個LRU本身是一個近似的，通過LRU算法本身來實現。

redis原始的淘汰算法簡單實現：**當需要淘汰一個key時，隨機選擇3個key，淘汰其中間隔時間最長的key。**基本上，我們隨機選擇key，淘汰key效果很好。后來隨機3個key改成一個配置項"N隨機key"。但把默認值提高改成5個后效果大大提高。考慮到它的效果，你根本不用修改他。

然而，你可能會想這個算法如何有效執行，你可以看到我們如何搗毀了很多有趣的數據。也許簡單的N key，我們會遇到很多好的決策，但是當我們淘汰最好的，下一個周期又開始抓。

驗證規則第一條：用肉眼觀察你的算法

其中有一個觀點已經應用到Redis 3.0正式版中了。在redis2.8中一個LRU緩存經常被使用在多個環境，用戶關于淘汰的沒有抱怨太多，但是很明顯我可以提高它，通過不僅僅是增加額外的空間，還有額外的CPU時間。
然而為了提高某項功能，你必須觀察它。有多個不同的方式去觀察LRU算法。你可以通過寫工具觀察，例如模擬不同的工作負載、校驗命中率和失誤率。
程序非常簡單：增加一些指定的keys，然后頻繁地訪問這些keys以至于每一個key都有一個下降的空閑時間。最終超過50%的keys被增加，一半的老key需要被淘汰。
一個完美理想的LRU實現，應該是沒有最新加的key被淘汰，而是淘汰最初的50%的老key。

規則二：不要丟棄重要信息

借助最新的可視化工具，我可以在嘗試新的方法觀察和測試幾分鐘。使用redis最明顯有效的提高算法就是，積累對立的垃圾信息在一個淘汰池中。
基本上，當N keys算法被采用時，通常會分配一個很大的線程pool（默認為16key），這個池按照空閑時間排序，所以只有當有一個大于池中的一個或者池為空的時候，最新的key只會進入到這個池中。
同時，一個新的redis-cli模式去測量LRU算法也增加了(看這個-lru-test選項)。
還有另外一個方式去檢驗LRU算法的好壞，通過一個冪等訪問模式。這個工具通常校驗用一個不同的測試，新算法工作工作效果好于真實世界負載。它也同樣使用流水線和每秒打印訪問日志，因此可以被使用不用為了基準不同的思想，至少可以校驗和觀察明顯的速度回歸。

規則三、最少使用原則（LFU算法）

一切源于一個開放性問題：但你有多個redis 3.2數據庫時，而淘汰算法只能在本機選擇。因此，假如你全部空閑小的key都是DB0號機器，空閑時間長的key都是1號機器，redis每臺機器都會淘汰各自的key。一個更好的選擇當然是先淘汰DB1，最后再淘汰DB0。
當redis被當作緩存使用時很少有情況被分成不同的db上，這不是一個好的處理方式。然而這也是我為什么我再一次修改淘汰代碼的原因。最終，我能夠修改緩存池包括數據庫id，使用單緩存池為多個db，代替多緩存池。這種實現很麻煩，但是通過優化和修改代碼，最終它比普通實現要快到20%。
然而這時候，我對這個redis緩存淘汰算法的好奇心又被點燃。我想要提升它。我花費了幾天想要提高LRU算法實現：或許可以使用更大的緩存池？通過歷史時間選擇最合適被淘汰的key？
經過一段時間，通過優化我的工具，我理解到：LRU算法受限于數據庫中的數據樣本，有時可能相反的場景效果非常好，因此要想提高非常非常難。實際上，能通過展示不同算法的圖片上看這有點非常明顯：每個周期10個keys幾乎和理論的LRU算法表現一致。
當原始算法很難提高時，我開始測試新的算法。如果我們倒回到博客開始，我們說過LRU實際上有點嚴格。哪些key需要我們真正想要保留：將來有最大可能被訪問，最頻繁被訪問，而不是最近被訪問的key。
淘汰最少被訪問的key算法成為：LFU（Least Frequently Used），將來要被淘汰騰出新空間給新key。
理論上LFU的思想相當簡單，只需要給每個key加一個訪問計數器。每次訪問就自增1，所以也就很容易知道哪些key被訪問更頻繁。
當然，LFU也會帶起其他問題，不單單是針對redis，對于LFU實現：
1、不能使用“移除頂部元素”的方式，keys必須要根據訪問計數器進行排序。每訪問一次就得遍歷所有key找出訪問次數最少的key。
2、LFU不能僅僅是只增加每一訪問的計數器。正如我們所講的，訪問模式改變隨時變化，因此一個有高訪問次數的key，后面很可能沒有人繼續訪問它，因此我們的算法必須要適應超時的情況。
在redis中，第一個問題很好解決：我們可以在LRU的方式一樣：隨機在緩存池中選舉，淘汰其中某項。第二個問題redis還是存在，因此一般對于LFU的思想必須使用一些方式進行減少，或者定期把訪問計數器減半。

24位的LFU實現

LFU有它本身的實現，在redis中我們使用自己的24bit來記錄LRU。
為了實現LFU僅僅需要在每個對象額外新增24bit：
1、一部分用于保存訪問計數器；
2、足夠用于決定什么時候將計數器減半的信息；

我的解決方法是把24bit分成兩列：

16bits8bitslast decr timeLOG_C

16位記錄最后一次減半時間，那樣redis知道上一次減半時間，另外8bit作為訪問計數器。
你可能會想8位的計數器很快就會溢出，是的，相對于簡單計數器，我采用邏輯計數器。邏輯計數器的實現：

uint8_t LFULogIncr(uint8_t counter) {if (counter == 255) return 255;double r = (double)rand()/RAND_MAX;double baseval = counter - LFU_INIT_VAL;if (baseval < 0) baseval = 0;double p = 1.0/(baseval*server.lfu_log_factor+1);if (r < p) counter++;return counter;}

基本上計數器的較大者，更小的可能計數器會增加：上面的代碼計算p位于0~1之間，但計數器增長時會越來越小，位于0-1的隨機數r，只會但滿足r<p時計數器才會加一。
你可以配置計數器增長的速率，如果使用默認配置，會發生：

100次訪問后，計數器=10；
1000次訪問是是18；
10萬次訪問是142；
100萬次訪問后達到255，并不在繼續增長；

下面，讓我們看看計數器如果進行衰減。16位的被儲存為unix時間戳保留到分鐘級別，redis會隨機掃描key填充到緩存池中，如果最后一個下降的時間大于N分鐘前（可配置化），如果計數器的值很大就減半，或者對于值小的就直接簡單減半。
這里又衍生出另外一個問題，就是新進來的key是需要有機會被保留的。由于LFU新增是得分都是0，非常容易被選舉替換掉。在redis中，開始默認值為5。這個初始值是根據增長數據和減半算法來估算的。模擬顯示得分小于5的key是首選。

代碼和性能

上面描述的算法已經提交到一個非穩定版的redis分支上。我最初的測試顯示：它在冪等模式下優于LRU算法，測試情況是每個key使用用相同數量的內存，然而真實世界的訪問可能會有很大不同。時間和空間都可能改變得很不同，所以我會很開心去學習觀察現實世界中LFU的性能如何，兩種方式在redis實現中對性能的改變。
因此，新增了一個OBJECT FREQ子命令，用于報告給定key的訪問計數器，不僅僅能有效提觀察一個計數器，而且還能調試LFU實現中的bug。
注意運行中切換LRU和LFU，剛開始會隨機淘汰一些key，隨著24bit不能匹配上，然而慢慢會適應。還有幾種改進實現的可能。Ben Manes發給我這篇感興趣的文章，描述了一種叫TinyLRU算法。鏈接

這篇文章包含一個非常厲害的觀點：相比于記錄當前對象的訪問頻率，讓我們（概率性地）記錄全部對象的訪問頻率，看到了，這種方式我們甚至可以拒絕新key，同樣，我們相信這些key很可能得到很少的訪問，所以一點也不需要淘汰，如果淘汰一個key意味著降低命中/未命中率。
我的感覺這種技術雖然很感興趣GET/SET LFU緩存，但不適用與redis性質的數據服務器：用戶期望keys被創建后至少存在幾毫秒。拒絕key的創建似乎在redis上就是一種錯誤。
然而，redis保留了LFU信息，當一個key被覆蓋時，舉個例子：