大家都知道 Redis 是單執行緒的。比較懂的人會告訴你，其實 Redis 算是 *有點* 單執行緒，因為它還是會用一些執行緒來處理某些在磁碟上比較慢的操作。到目前為止，有用到執行緒的操作都高度集中在 I/O 上，以至於我們那個用來在不同執行緒上執行非同步任務的小函式庫，就直接叫做 bio.c：基本上就是 Background I/O（背景 I/O）。

不過，前一陣子我開了一個 issue，承諾要做一個很多人敲碗、我自己也很想要的 Redis 新功能，叫做「lazy free」（延遲釋放）。原始的 issue 在這裡：https://github.com/antirez/redis/issues/1748。

這個 issue 的重點在於，Redis 的 DEL 操作通常是會阻塞的，所以如果你對 Redis 送出「DEL mykey」，而你的 key 剛好有五千萬個物件，伺服器就會卡住好幾秒，這段時間什麼請求都無法處理。長久以來，這被視為 Redis 設計上的副作用而被大家接受，但在某些使用情境下，這確實是個限制。DEL 並不是唯一會阻塞的指令，但它比較特別，因為我們通常會說：只要你用的是 O(1) 和 O(log_N) 的指令，Redis 就非常快。你當然也可以用 O(N) 的指令，但要知道那不是我們最佳化的重點，得做好會出現延遲突波的心理準備。

這聽起來很合理，但同時，就算物件是用快速操作建立的，終究還是得刪除。而在這種情況下，Redis 就會卡住。

第一次嘗試

在單執行緒的伺服器裡，要讓操作變成非阻塞，最簡單的方法就是改成漸進式地處理，而不是讓整個世界停擺。所以如果要釋放一百萬個配置，與其用一個 for() 迴圈把所有事都卡住，我們可以例如每毫秒釋放 1000 個元素。使用的 CPU 時間是一樣的，甚至還多一點，因為多了一些邏輯，但從使用者的角度來看，延遲會好得多。搞不好那每毫秒用來釋放 1000 個元素的運算週期，原本根本就沒被用到。重點就在於避免一次卡住好幾秒。這也是 Redis 內部很多機制的運作方式：LRU 淘汰和 key 過期就是兩個最明顯的例子，但還有更多，像是雜湊表的漸進式 rehash。

所以這就是我第一次嘗試的做法：建立一個新的 timer 函式，然後在裡面執行回收。物件就只是被丟進一個鏈結串列裡排隊，等每次呼叫 timer 函式時再慢慢地、漸進式地回收。要讓這個方法運作得好，需要一些技巧。舉例來說，用雜湊表實作的物件，也會用跟 Redis SCAN 指令內部相同的機制來漸進式回收：在字典裡拿一個游標（cursor），然後一個接一個地迭代、釋放元素。這樣一來，在每次呼叫 timer 時，我們就不需要一次釋放整個雜湊表。游標會告訴我們上次停在哪裡，下次再進入 timer 函式時就可以接著做。

要做到自適應很難

你知道這個做法困難的地方在哪裡嗎？這一次，我們漸進式處理的是一項非常特殊的任務：我們在釋放記憶體。所以，如果我們一邊漸進式地釋放記憶體，伺服器的記憶體使用量卻快速飆升，為了顧及延遲，我們最後可能會消耗掉 *無上限* 的記憶體。這非常糟糕。舉個例子，想像一下：

WHILE 1
    SADD myset element1 element2 … many many many elements
    DEL myset
END

如果在背景刪除 myset 的速度，比我們每次 SADD 呼叫加入大量元素的速度還慢，我們的記憶體使用量就會永遠不斷成長。

不過，經過幾次實驗後，我找到了一個能讓它運作得非常好的方法。這個 timer 函式用了兩個想法，來讓它能因應記憶體壓力自動調整：

1. 檢查記憶體的趨勢：是在上升還是下降？藉此來調整釋放時要多積極。
2. 同時也根據「1」來調整 timer 本身的頻率，這樣當沒什麼需要釋放時，就不會因為不斷中斷事件循環而浪費 CPU 時間。同時，在真正需要時，timer 的頻率可以達到約 300 HZ。

以下是一小段程式碼，來自那個已經不存在、實作這些想法的函式：

/* Compute the memory trend, biased towards thinking memory is raising
 * for a few calls every time previous and current memory raise. */
if (prev_mem < mem) mem_trend = 1;
mem_trend *= 0.9; /* Make it slowly forget. */
int mem_is_raising = mem_trend > .1;

/* Free a few items. */
size_t workdone = lazyfreeStep(LAZYFREE_STEP_SLOW);

/* Adjust this timer call frequency according to the current state. */
if (workdone) {
    if (timer_period == 1000) timer_period = 20;
    if (mem_is_raising && timer_period > 3)
        timer_period--; /* Raise call frequency. */
    else if (!mem_is_raising && timer_period < 20)
        timer_period++; /* Lower call frequency. */
} else {
    timer_period = 1000;    /* 1 HZ */
}

這是個不錯的技巧，而且運作得非常好。但還是有點可惜，我們得在單一執行緒裡做這件事。要把它處理好需要很多邏輯，而且無論如何，當 lazy free 的週期非常忙碌時，每秒操作數還是會降到正常水準的約 65%。

如果在不同的執行緒裡釋放物件，會簡單得多：只要有一個執行緒專門忙著做釋放操作，釋放的速度幾乎總是比在資料集中加入新值的速度還快。當然，主執行緒呼叫分配器（allocator）和 lazy free 執行緒做同樣的事情之間，肯定會有一些競爭，但 Redis 花在分配上的時間只佔一小部分，更多時間是花在 I/O、指令分派、快取未命中等等上面。

然而，要實作多執行緒的 lazy free，有個很大的問題：就是 Redis 本身。它的內部設計完全偏向到處共享物件。畢竟它們都是有參照計數（reference counted）的，對吧？那何不盡可能地共享呢？這樣可以節省記憶體和時間。舉幾個例子：如果你執行 SUNIONSTORE，最終目標集合裡會是共享的物件。同樣地，客戶端的輸出緩衝區（output buffers）會有一串要透過 socket 作為回應送出的物件，所以在像 SMEMBERS 這樣的呼叫期間，集合的所有成員最終都可能會在輸出緩衝區的串列中被共享。所以，共享物件聽起來是那麼實用、可愛、美好、超級酷。

但是，嘿，這裡還有更多問題。如果我在執行 SUNIONSTORE 之後重新載入資料庫，物件就會變成非共享狀態，所以記憶體可能會突然暴增到比原來還多。這可不太妙。此外，當我們把回應送給客戶端時會發生什麼事？當物件很小時，我們其實會把它們 *黏合* 成單純的緩衝區，因為否則執行大量的 write() 呼叫是沒有效率的！（免費提示：writev() 也幫不上忙）。所以其實我們大部分時候已經在做複製了。而在程式設計的世界裡，當某個東西沒什麼用卻還存在時，它很可能就是個問題。

而且，的確，每次你要存取一個值，在一個包含聚合資料型別的 key 裡面，你都得遍歷以下這一串：

key -> value_obj -> hash table -> robj -> sds_string

那如果乾脆完全拋棄「robj」結構，把聚合型別的值改成只由 SDS 字串的雜湊表（或跳躍表 skiplists）組成，會怎麼樣？（SDS 是我們在 Redis 內部用來處理字串的函式庫）。這麼做有個問題。想像一下像 SADD myset myvalue 這樣的指令。我們不能直接拿 client->argv[2]，然後就在實作集合的雜湊表裡參照它。我們有時得 *複製* 值，無法重複使用在解析指令時就已在客戶端參數向量（client argument vector）中建立好的那些值。不過，Redis 的效能主要是被快取未命中所主導，所以或許我們可以用少一層間接存取來彌補這個損失？

於是我開始在這個新的 lazyfree 分支上動工，還在 Twitter 上毫無來由地發文講這件事，搞得大家都以為我是不是絕望了還是在發瘋（最後有幾個人跑來問說這該死的 lazyfree 到底是什麼東西）。那我做了什麼呢？

1. 把客戶端輸出緩衝區改成只使用動態字串，而不是 robj 結構。每次要產生回應時，值永遠都會被複製。
2. 把所有 Redis 資料型別都改成使用 SDS 字串，而不是共享的 robj 結構。聽起來很簡單？花了好幾個星期，改了約 800 行對錯誤極度敏感的程式碼。但現在所有測試都通過了。
3. 把 lazyfree 重寫成多執行緒的版本。

結果就是，Redis 現在的記憶體效率更高了，因為在資料結構的實作中已經沒有 robj 結構到處跑了（不過在那些大量共享發生的程式路徑中還是會用到，例如指令分派和複寫時）。多執行緒的 lazy free 運作得非常好，而且在回收記憶體方面比漸進式的那個更快，即使漸進式那個版本的實作我自己非常喜歡，跟多執行緒版比起來也沒有糟到哪去。但現在，你可以刪除一個巨大的 key，而效能下降幾乎可以忽略不計，這非常實用。不過，最有趣的是，到目前為止我測試過的所有操作，Redis 現在都變快了。減少一層間接存取在這裡真的是大獲全勝。甚至在不相關的基準測試中也變快了，僅僅是因為客戶端輸出緩衝區現在更簡單、更快。最後，我把分支中漸進式 lazy freeing 的實作刪掉了，只保留多執行緒的版本。

關於 API 的說明

不過，API 該怎麼辦呢？我們還是保留會阻塞的 DEL，預設行為不變，因為在 Redis 裡 DEL 的意思就是：立刻回收記憶體。我不喜歡改變這一點的想法。所以現在你有了一個叫做 UNLINK 的新指令，它更清楚地說明了值發生了什麼事。

UNLINK 是個聰明的指令：它會計算物件的釋放成本，如果成本非常小，它就會跟 DEL 該做的一樣，馬上釋放物件。否則，物件就會被送到背景佇列中處理。除此之外，從鍵空間（key space）語意來看，這兩個指令是完全相同的。

FLUSHALL / FLUSHDB 的非阻塞版本也已經實作了，但還沒到 API 層級，它們之後只要加上 LAZY 選項，就會改變行為。

不只是延遲釋放

現在聚合資料型別的值已經完全不共享，而且客戶端輸出緩衝區也不再包含共享物件，有很多可以發揮的空間。舉例來說，終於可以在 Redis 裡實作多執行緒 I/O 了，讓不同的客戶端由不同的執行緒來服務。這意味著我們只有在存取資料庫時才需要全域鎖，但客戶端的 read/write 系統呼叫，甚至客戶端送來指令的解析，都可以在不同的執行緒中進行。這是一種類似 memcached 的設計，也是我期待去實作和測試的。

此外，現在也可能在另一個執行緒中實作某些針對聚合資料型別的慢速操作，讓只有少數幾個 key 會被「阻塞」，而所有其他客戶端都能繼續運作。這可以用跟我們目前處理阻塞操作非常類似的方式來達成（參見 blocking.c），再加上一個雜湊表來記錄哪些 key 目前正忙碌、以及是被哪個客戶端占用。所以，如果有客戶端請求像是 SMEMBERS 這樣的操作，就有可能只鎖住那個 key，在背景處理請求並產生輸出緩衝區，之後再釋放該 key。只有當某個 key 被鎖住時，嘗試存取同一個 key 的客戶端才會被阻塞。

這一切都需要更大幅度的內部改動，但重點在於，我們少了一個禁忌。我們可以用更少的快取未命中和更小的聚合資料型別記憶體佔用，來彌補物件複製所花的時間，所以我們現在可以自由地以 share-nothing（無共享）設計來思考多執行緒的 Redis，而這是唯一能輕易超越我們單執行緒版本的設計。過去，如果把多執行緒的 Redis 想成是在資料結構和物件上加一堆 mutex 來實現並行存取，那總是被視為一個壞主意，但幸好還有其他方法可以兼顧兩者的優點。而且如果我們願意，仍然可以選擇像過去一樣，讓所有快速操作都由主執行緒來處理。從效能的角度來看，應該只有好處，代價則是一些可控的複雜度。

預計時程

我動到了很多內部核心，這不是明天就會上線的東西。所以我的計畫是，把我們在 unstable 分支中已有的東西稱為 3.2，進行到 Release Candidate（候選發布版）階段，然後再把這個分支合併到 unstable，目標是 3.4 版。

不過在合併之前，應該要非常仔細地檢查是否有速度上的退化。肯定還有更多工作要做。

如果你想試試看，可以到 GitHub 上看看「lazyfree」分支。順帶一提，請注意我目前還在非常積極地開發它，所以某些東西在某些時刻可能會完全壞掉。