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 物件的結構，我擠出了 24 位元的空間。已經沒有空間把物件用鏈結串列串起來了（指標太肥了！），而且實作還必須夠有效率，因為不能讓挑選要淘汰的鍵這件事拖慢伺服器的效能太多。

物件中的 24 位元足以儲存目前 Unix 時間（以秒為單位）的最低有效位元。這種表示法在 Redis 原始碼中被稱為「LRU 時鐘」，要 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 原本使用的陽春演算法，最顯而易見的方法就是把那些原本會被丟棄的資訊，累積到一個由適合淘汰的候選鍵所組成的「池」裡。

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

如你在上面連結的圖片中所見，這個小小的改動就讓演算法的效能大幅提升，而且實作並不複雜。這裡那裡加幾個 memmove()，再做一些效能分析，就完成了，我也不記得這個部分曾有過什麼重大錯誤。

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

最少使用頻率（LFU）

我之所以現在寫這篇部落格文章，是因為幾天前我針對 Redis 快取淘汰的程式碼做了部分重寫與各種改進。

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

這通常不是什麼大問題，當 Redis 被當作快取使用時，很少會同時使用多個 DB，不過這就是我再次投入淘汰程式碼的原因。最終我成功修改了池，讓它包含資料庫 ID，並對所有 DB 使用單一的池，而不是使用多個池。一開始它比較慢，但經過效能分析與調校後，最終反而比原本的實作快了約 20%。

不過到那時，我對 Redis 這個子系統的好奇心又被激起了，我想進一步改進它。我花了幾天時間試圖改進 LRU 的實作：也許用更大的池？把挑選最佳鍵時經過的時間也考慮進去？

過了一陣子，在改良了我的工具之後，我意識到 LRU 演算法的限制在於從資料庫中取樣的資料量，除此之外它已經非常好、很難再改進了。這點其實從顯示不同演算法的那張圖片就可以看出來：每個週期取樣 10 個鍵時，演算法的準確度就已經幾乎跟理論上的 LRU 一樣了。

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

會淘汰存取次數最少的鍵的演算法叫做 LFU，也就是 Least Frequently Used（最少使用頻率），這正是它試圖淘汰以騰出空間給新鍵的鍵的特性。

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

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

1. 在 LFU 中，你無法使用 LRU 那種「移到頭部」的鏈結串列技巧來簡單地取得已排序、可供淘汰的元素，因為在「完美的 LFU」中，鍵必須依存取次數來排序。把被存取的鍵移到正確的位置可能會很麻煩，因為可能有很多鍵具有相同的分數，所以即使鍵的頻率計數器只改變了一點點，最糟情況下操作也可能是 O(N)。而且如我們在第 2 點中會看到的，存取計數器並不總是只改變一點點，有時也會有突然的大幅變動。
2. LFU 也不能真的就只是每次存取時把存取計數器遞增這麼單純。如我們所說，存取模式會隨時間改變，所以一個分數很高的鍵，如果沒有人持續存取它，其分數就需要隨著時間降低。我們的演算法必須能夠隨著時間來適應。

在 Redis 中，第一個問題不是問題：我們只要沿用 LRU 的技巧就行——用候選池做隨機取樣。第二個問題則仍然存在。所以一般來說，LFU 的實作都會有某種機制，不時地遞減或減半存取計數器。

在 24 位元空間中實作 LFU

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

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

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

我的解法是把 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」，隨著計數器增加，p 會越來越小。然後它會取出一個介於 0 和 1 之間的隨機數「r」，只有當「r < p」為真時，才會遞增計數器。

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

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

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

還有另一個問題，新鍵終究需要有存活的機會。在最單純的 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 中新的淘汰程式碼還包含了其他好消息：

1. 策略現在是「跨 DB」的。過去如這篇部落格文章開頭所解釋的，Redis 會做出區域性的選擇。現在這個問題已針對所有策略修正，不只是 LRU。
2. volatile-ttl 淘汰策略，也就是根據已設定過期時間的鍵的剩餘存活時間來淘汰的策略，現在也像其他策略一樣使用池。
3. 透過在鍵池中重複使用 SDS 物件，效能變得更好。

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

Hacker News 討論： https://news.ycombinator.com/item?id=12185534