Random notes on improving the Redis LRU algorithm

2016-07-29

關於改進 Redis LRU 演算法的隨筆

Redis 經常用作快取，通常會設定一個固定的最大可用記憶體。當有新資料進來時，就必須移除舊資料來騰出空間。Redis 作為快取的效率，取決於它在決定淘汰哪些資料時做得多好：刪除很快就會再次被需要的資料是很差的策略，而刪除不太可能再次被請求的資料則是好的策略。

換句話說，每個快取都有命中／未命中比率，以質性的角度來說，就是快取能夠回應的讀取請求所佔的百分比。在大多數工作負載中，對快取鍵的存取並不會平均分布在整個資料集上。往往只有少數比例的鍵，卻佔了所有存取中極大的比例。此外，存取模式通常會隨著時間而改變，也就是說，隨著時間推移，某些原本被頻繁請求的鍵可能不再常被存取，反之，原本不受歡迎的鍵也可能變成最常被存取的鍵。

因此，一般來說，快取應該盡量保留未來最有可能被存取的鍵。從淘汰策略（用來騰出空間讓新資料進入的策略）的角度來看，這句話反過來說就是：應該從資料集中移除未來最不可能被存取的鍵。問題只有一個：Redis 與其他快取都無法預測未來。

LRU(最近最少使用)演算法

雖然快取無法預測未來，但可以這樣推論：很可能會再次被請求的鍵，就是近期被頻繁請求的鍵。由於存取模式通常不會突然劇變，這是個有效的策略。然而，「近期被頻繁請求」這個概念，比乍看之下更為弔詭（我們稍後會再談到這點）。因此，這個概念被簡化為一種稱為 LRU 的演算法，它只追蹤鍵 *上次* 被請求的時間。相較於很少被存取的鍵，被存取頻率較高的鍵，其閒置（未被存取）時間較短的機率也較高。

例如，以下是四個不同鍵隨時間存取情況的示意。每個「~」字元代表一秒，而末端的「|」線則代表當下時刻。

~~~~~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 每 5 秒被存取一次，鍵 B 每 2 秒一次，而鍵 C 與 D 則都是每 10 秒被存取一次。

由於鍵 B 的存取頻率很高，它的閒置時間屬於最短之列，也就是說它的上次存取時間在四個鍵中是第二新的。

同樣地，A 與 C 分別為 2 秒與 6 秒的閒置時間，很好地反映了這兩個鍵的存取頻率。然而如你所見，這個技巧並非總是有效：鍵 D 每 10 秒才被存取一次，卻擁有所有鍵中最新的存取時間。

不過，從長期來看，這個演算法的表現已經相當不錯。通常存取頻率越高的鍵，閒置時間就越短。LRU 演算法會淘汰最近最少使用的鍵，也就是閒置時間最長的那個。它實作起來很簡單，因為我們只需要追蹤每個鍵上次被存取的時間，有時甚至連這都不需要：我們只要把所有想淘汰的物件用一個鏈結串列串起來即可。當某個物件被存取時，就把它移到串列的頂端；當需要淘汰物件時，就從串列的尾端淘汰。成了！搞定。

Redis 中的 LRU：起源

最初 Redis 並不支援 LRU 淘汰。這個功能是後來才加入的，當時記憶體使用效率是個重大考量。透過稍微修改 Redis Object 結構，我設法擠出了 24 位元的空間。根本沒有空間用來把物件串進鏈結串列（指標太肥了！），而且實作必須夠有效率，因為挑選要淘汰的鍵不應該讓伺服器效能大幅下降。

物件中的 24 位元足以儲存目前 Unix 時間（以秒為單位）的最低有效位元。在 Redis 原始碼中，這種表示法被稱為「LRU clock」，需要 194 天才會溢位。鍵的中繼資料更新得相當頻繁，所以這樣的設計已經足夠。

然而還有另一個更複雜的問題要解決：要如何選出閒置時間最長的鍵來淘汰？Redis 的鍵空間是以扁平的雜湊表來表示。要再加入另一種資料結構來存放這些中繼資料並不可行，不過既然 LRU 本身就已經是我們想達成目標的一種近似，那何不進一步近似 LRU 本身呢？

最初的 Redis 演算法就是這麼簡單：當需要淘汰一個鍵時，就隨機選出 3 個鍵，然後淘汰其中閒置時間最長的那個。基本上就是在鍵空間上做隨機取樣，然後淘汰剛好比較好的那個。後來這個「隨機 3 個鍵」變成了可設定的「隨機 N 個鍵」，而且演算法的速度也獲得了改進，因此在不損失效能的情況下，預設的取樣數被提高到 5 個。儘管這個方法看起來很天真，實際運作效果卻很好，甚至非常好。仔細想想，用這個演算法你永遠做不出最佳決策，但也幾乎不可能做出非常糟的決策。如果資料集中有一群被非常頻繁存取的鍵，在抽樣 5 個鍵的情況下，要倒楣到只抽到閒置時間都很短的鍵，其實是很困難的。

然而，如果你從這個演算法 *多次執行* 的角度來思考，就會發現我們丟棄了大量有用的資訊。或許在取樣 N 個鍵時，我們會遇到許多不錯的淘汰候選者，但我們卻只淘汰其中最好的那個，然後在下一個週期又從頭開始。

鬥陣俱樂部的第一條規則是：用肉眼觀察你的演算法

有段時間，我正忙於即將推出的 Redis 3.0 版本。當時 Redis 2.8 已在多個環境中被積極地用作 LRU 快取，大家對於 Redis 淘汰精準度的抱怨並不多，但很明顯，即使不增加明顯的 CPU 時間，也不增加任何額外的空間，仍有改進的空間。

然而要改進某個東西，就得先仔細觀察它。觀察 LRU 演算法有不同的方法。例如，你可以撰寫工具來模擬不同的工作負載，並在最後檢查命中／未命中比率。這就是我所做的，不過命中／未命中比率很大程度上取決於存取模式，因此除了這些資訊之外，我還寫了一個工具，能以視覺化的方式呈現演算法的品質。

這個程式非常簡單：它先加入一定數量的鍵，然後依序存取這些鍵，讓每個鍵的閒置時間遞減。最後再加入多 50% 的鍵（圖片中的綠色部分），因此舊鍵中有一半需要被淘汰。

在完美的 LRU 實作中，不會有任何新加入的鍵被淘汰，而舊資料集中最舊的 50% 會被淘汰。

以下是該程式針對不同 Redis 版本與不同設定所產生的示意圖：

http://redis.io/images/redisdoc/lru_comparison.png

在查看圖表時請記得，我們至今討論的實作是 Redis 2.8 的版本。而你在 Redis 3.0 中看到的改進，將在下一節說明。

LRU V2：別把重要資訊丟掉

有了這個新的視覺化工具，我得以在幾分鐘內嘗試新方法並進行測試。改進 Redis 所使用的原始演算法最顯而易見的方法，就是把原本會被丟棄的資訊累積到一個由優秀淘汰候選者組成的「pool」中。

基本上，當執行 N 個鍵的取樣時，會用這些樣本來填入一個更大的鍵 pool（預設只有 16 個鍵）。這個 pool 會依閒置時間對鍵進行排序，因此只有當新鍵的閒置時間大於 pool 中某個鍵，或是 pool 中還有空位時，新鍵才會進入 pool。

如你在上方連結的圖片中所見，這個小小的改變大幅提升了演算法的效能，而且實作並不複雜。只需在幾個地方加上 memmove()，再做一些效能剖析，就完成了，我也不記得這個部分曾出現過重大的錯誤。

同時，也新增了一個用來測試 LRU 精準度的 redis-cli 模式（請參閱 —lru-test 選項），因此我有了另一種方法，可以用冪次法則的存取模式來檢查 LRU 程式碼的效能。這個工具被用來以不同的測試驗證新演算法在更貼近真實世界的負載下表現更好。它還使用了管線化（pipelining），並會顯示每秒存取次數，因此也能用來對不同實作進行基準測試，至少可以檢查是否有明顯的速度衰退。

Least Frequently Used(最不常使用)

我現在會寫這篇部落格文章，是因為幾天前我針對 Redis 快取淘汰程式碼進行了部分重寫與多項改進。

一切始於一個未解決的問題：當你在 Redis 3.2 中使用多個資料庫時，演算法會做出區域性的淘汰決策。舉例來說，如果你所有的閒置時間很短的鍵都在 0 號資料庫，而所有閒置時間很長的鍵都在 1 號資料庫，Redis 卻會從每個資料庫各淘汰一個鍵。當然，更合理的做法是先從 1 號資料庫開始淘汰，之後才淘汰其他鍵。

這通常不是什麼大問題，當 Redis 被用作快取時，很少會同時使用多個資料庫，不過這正是我再次著手處理淘汰程式碼的起點。最終，我成功修改了 pool，使其包含資料庫 ID，並改為對所有資料庫使用單一的 pool，而非多個 pool。一開始速度反而變慢，但經過剖析與調校後，最終比原本的實作快了約 20%。

然而到了這個時候，我對 Redis 這個子系統的好奇心又被激發了，我想要進一步改進它。我花了幾天時間嘗試改進 LRU 的實作：或許用更大的 pool？或者把挑選最佳鍵時經過的時間也納入考量？

過了一段時間，並在改良了我的工具之後，我了解到 LRU 演算法受限於在資料庫中取樣的資料量，除此之外，它已經非常優秀且很難再改進。事實上，這從顯示不同演算法的圖片中就可見一斑：每個週期取樣 10 個鍵時，演算法的精準度幾乎就和理論上的 LRU 一樣了。

既然原本的演算法很難再改進，我便開始測試新的演算法。如果我們回顧一下這篇部落格文章開頭所說的，LRU 其實有點像是一種技巧。我們真正想要保留的，是未來最有可能被存取的鍵，也就是 *最常被存取* 的鍵，而不只是最新被存取的鍵。

會淘汰存取次數最少的鍵的演算法稱為 LFU。它代表 Least Frequently Used，也就是它試圖為了騰出空間給新鍵而淘汰的鍵所具備的特性。

理論上，LFU 就像為每個鍵關聯一個計數器一樣簡單。每次存取時計數器就會遞增，這樣我們就能知道某個鍵比另一個鍵更常被存取。

不過，至少還有幾個問題，並非 Redis 特有，而是 LFU 實作上普遍會遇到的問題：

使用 LFU 時，你無法像 LRU 那樣使用「移到開頭」的鏈結串列技巧來簡單地取得已排序好的待淘汰元素，因為在「完美的 LFU」中，鍵必須依存取次數來排序。將被存取的鍵移到正確的位置可能會很棘手，因為可能有許多鍵具有相同的分數，所以即使鍵的頻率計數器只改變了一點點，最糟情況下這個操作的時間複雜度也可能是 O(N)。此外，如同我們在第 2 點會看到的，存取計數器並非總是只改變一點點，有時也會有突然的大幅變動。
LFU 也不能真的像每次存取就只是把存取計數器加一那麼簡單。如我們所說，存取模式會隨時間改變，因此如果沒有人持續存取某個高分的鍵，它的分数就必須隨時間降低。我們的演算法必須能夠隨時間自我調整。

在 Redis 中，第一個問題不算是問題：我們只要沿用 LRU 用的技巧即可：透過候選 pool 進行隨機取樣。第二個問題則依然存在。因此，一般的 LFU 實作都會有某種方式，不時將存取計數器遞減或減半。

在 24 位元空間中實作 LFU

LFU 本身在實作上就有其特殊之處，然而在 Redis 中，我們能用來建模 LFU 的只有那 24 位元的 LRU 欄位。要在每個物件僅用 24 位元來實作 LFU，確實有點棘手。

我們需要在 24 位元內做到的是：

某種存取頻率計數器。
足夠用來決定何時將計數器減半的資訊。

我的解決方案是將 24 位元拆成兩個欄位：

           16 bits      8 bits
      +----------------+--------+
      + Last decr time | LOG_C  |
      +----------------+--------+

16 位元的欄位是上次遞減的時間，讓 Redis 知道計數器上次被遞減是什麼時候，而 8 位元的欄位則是實際的存取計數器。

你可能會想，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;
}

基本上，計數器的值越大，計數器真正會被遞增的機率就越小：上面的程式碼會計算出一個介於 0 與 1 之間的數字「p」，隨著計數器增加，這個數字會越來越小。接著它會取出一個介於 0 與 1 之間的隨機數「r」，只有在「r < p」為真時，才會遞增計數器。

你可以透過 redis.conf 的參數來設定計數器遞增的積極程度，但舉例來說，使用預設設定時，情況會是這樣：

在 100 次命中後，計數器的值為 10；在 1000 次後為 18；在 10 萬次後為 142；在 100 萬次命中後則會達到 255 的上限，不再遞增

現在來看看這個計數器是如何遞減的。16 位元被用來儲存轉換為分鐘後的 UNIX 時間的最低有效位元。當 Redis 執行隨機取樣、掃描鍵空間以尋找鍵來填入 pool 時，所有遇到的鍵都會被檢查是否需要遞減。如果上次遞減是在 N 分鐘以前執行的（N 可設定），那麼計數器的值若較高就會被減半，若較低則只會遞減一（希望在計數器解析度很小的情況下，我們能更好地區分存取次數很少的鍵）。

還有另一個問題，新鍵終究需要有存活的機會。在原始的 LFU 中，剛加入的鍵其存取分數為 0，因此會是非常好的淘汰候選者。在 Redis 中，新鍵一開始的 LFU 值為 5。這個初始值在遞增與減半的演算法中都會被納入考量。模擬顯示，有了這個改變，鍵就有一些時間可以累積存取次數：分數小於 5 的鍵會被優先淘汰（長時間未活躍的鍵）。

程式碼與效能

上述的實作可以在 Redis 的「unstable」分支中找到。我最初的測試顯示，它在冪次法則的存取模式下表現優於 LRU，同時每個鍵使用相同的記憶體用量，不過真實世界的存取模式可能會有所不同：存取在時間與空間上的局部性可能會以非常不同的方式變化，因此我很樂意從真實世界的使用案例中了解 LFU 的表現，以及在 Redis LFU 實作中可調整的兩個參數如何影響不同工作負載的效能。

此外還新增了 OBJECT FREQ 子指令，用來回報指定鍵的頻率計數器，這對於觀察應用程式的存取模式以及除錯 LFU 實作都很有用。

請注意，在執行期間於 LRU 與 LFU 策略之間切換，會導致一開始幾乎是隨機淘汰，因為在 24 位元計數器中累積的中繼資料並不符合新選定策略的含義。不過隨著時間推移，它又會重新適應。

可能還有許多可以改進的地方。

Ben Manes（班·曼恩斯）向我介紹了這篇有趣的論文，其中描述了一種名為 TinyLRU 的演算法（http://arxiv.org/pdf/1512.00727.pdf）。

這篇論文包含了一個非常巧妙的想法：與其記住目前物件的存取頻率，不如（以機率的方式）記住迄今為止所有見過物件的存取頻率，這樣我們甚至可以在認為新鍵從名稱來看很可能只會得到少量存取時，就直接拒絕寫入新鍵，如此一來，如果淘汰某個鍵會降低命中／未命中比率，那就完全不需要進行淘汰。

我的感覺是，這項技術雖然對於單純的 GET/SET LFU 快取非常有趣，但並不適用於 Redis 作為資料結構伺服器的本質：使用者會期待鍵在建立後至少能存在幾毫秒。完全拒絕建立鍵，在語意上對 Redis 而言似乎是錯誤的。

不過，當鍵被覆寫時，Redis 會保留 LFU 資訊，因此例如在執行以下指令之後：

SET oldkey some_new_value

24 位元的 LFU 計數器會被複製到與舊鍵關聯的新物件上。

Redis unstable 中新的淘汰程式碼還包含了其他好消息：

策略現在是「跨資料庫」的。過去如本篇部落格文章開頭所解釋，Redis 會做出區域性的選擇。現在這個問題已針對所有策略修正，而不僅僅是 LRU。
volatile-ttl 淘汰策略，也就是根據設有過期時間的鍵其剩餘存活時間來進行淘汰的策略，現在也像其他策略一樣使用 pool。
透過在鍵的 pool 中重複使用 SDS 物件，效能也獲得了提升。

這篇文章比我預期的長了很多，但我希望它能對新功能以及對我們既有功能的改進提供一些見解。Redis 與其說是用來解決特定問題的「解決方案」，不如說是一個通用工具。如何以正確的方式運用它，取決於明智的開發者。許多人將 Redis 用作快取解決方案，因此這個領域的改進總是會不時被加以研究。

Hacker News 留言：https://news.ycombinator.com/item?id=12185534