標籤：

redis之父的博客翻譯-Redis中的LRU演算法改進

04-04

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版本和不同的配置下的表現：

觀察這個圖記得我們討論的這個實現是redis 2.8的實現。下一節討論的是redis 3.0中的實現。

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

藉助最新的可視化工具，我可以在嘗試新的方法觀察和測試幾分鐘。使用redis最明顯有效的提高演算法就是，積累對立的垃圾信息在一個淘汰池中。

基本上，當N keys演算法被採用時，通常會分配一個很大的線程pool（默認為16key），這個池按照空閑時間排序，所以只有當有一個大於池中的一個或者池為空的時候，最新的key只會進入到這個池中。

有一個小提高這個演算法的改動點是，正如你在上圖圖片中看到的，這個實現沒有很複雜。一對memmove()在這裡有一點點的提高，但是我不記得這個地方的主要bug了。

同時，一個新的redis-cli模式去測量LRU演算法也增加了(看這個-lru-test選項)。

我還有另外一個方式去檢驗LRU演算法的好壞，通過一個冪等訪問模式。這個工具通常校驗用一個不同的測試，新演算法工作工作效果好於真實世界負載。它也同樣使用流水線和每秒列印訪問日誌，因此可以被使用不用為了基準不同的思想，至少可以校驗和觀察明顯的速度回歸。

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

我寫這篇博客的原因是因為幾天前，我重新實現部分邏輯，不同程度的提高redis的緩存淘汰代碼。

一切源於一個開放性問題：但你有多個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演算法。

(arxiv.org/pdf/1512.0072)

這篇文章包含一個非常厲害的觀點：相比於記錄當前對象的訪問頻率，讓我們（概率性地）記錄全部對象的訪問頻率，看到了，這種方式我們甚至可以拒絕新key，同樣，我們相信這些key很可能得到很少的訪問，所以一點也不需要淘汰，如果淘汰一個key意味著降低命中/未命中率。

我的感覺這種技術雖然很感興趣GET/SET LFU緩存，但不適用與redis性質的數據伺服器：用戶期望keys被創建後至少存在幾毫秒。拒絕key的創建似乎在redis上就是一種錯誤。

然而，redis保留了LFU信息，當一個key被覆蓋時，舉個例子：

SET oldkey some_new_value

24位的LFU計數器會從老的key複製到新對象中。

新的redis淘汰演算法不穩定版本還有以下幾個好消息：

1、跨DB策略。在過去的redis只是基於本地的選舉，現在修復為所有策略，不僅僅是LRU。

2、易變ttl策略。基於key預期淘汰存活時間，如今就像其他策略中的使用緩存池。

3、在緩存池中重用了sds對象，性能更好。

這篇博客比我預期要長，但是我希望它反映出一個見解：在創新和對於已經存在的事物實現上，一種解決方案去解決一個特定問題，一個基礎工具。由開發人員以正確的方式使用它。許多redis的用戶把redis作為一個緩存的解決方案，因此提高淘汰策略這一塊經常一次又一次被拿出來探討。

原文：

antirez.com/news/109

推薦閱讀：

※求指教學習redis源碼的方法？
※scrapy-redis 和 scrapy 有什麼區別？
※圖解redis之數據結構篇

TAG:Redis |