大家都知道 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 剛好包含了 5,000 萬個物件，伺服器就會阻塞數秒鐘，在此期間完全無法處理任何其他請求。一直以來，這大多被視為 Redis 設計上的副作用而被接受，但在某些使用情境下，這卻是一個限制。DEL 並不是唯一會阻塞的指令，但它比較特別，因為我們通常會說：只要你使用 O(1) 和 O(log_N) 的指令，Redis 就非常快。你當然可以自由使用 O(N) 的指令，但要知道那並不是我們最佳化的重點，要有出現延遲突波的心理準備。

這聽起來很合理，但同時，即使是用快速操作建立出來的物件，最終還是需要被刪除。而在這種情況下，Redis 就會阻塞。

第一次嘗試

在單執行緒的伺服器中，要讓操作變成非阻塞，最簡單的方法就是改為漸進式地處理，而不是讓整個世界停擺。所以如果需要釋放 100 萬個記憶體配置，與其在一個 for() 迴圈中阻塞所有事情，我們可以例如每毫秒釋放 1,000 個元素。所耗費的 CPU 時間是一樣的，或甚至多一點，因為多了一些邏輯，但從使用者的角度來看，延遲表現卻好得多。也許那每毫秒釋放 1,000 個元素所用的週期本來就是閒置的。關鍵在於避免長達數秒的阻塞。這就是 Redis 內部許多機制的運作方式：LRU 淘汰和鍵的過期就是兩個明顯的例子，但還有更多，例如雜湊表的 incremental rehashing(漸進式重新雜湊)。

所以這就是我首先嘗試的做法：建立一個新的計時器函式，並在其中執行回收作業。物件只是被排進一個鏈結串列中，等待每次呼叫計時器函式時，再慢慢地、漸進式地被回收。要讓這個機制運作良好，需要一些技巧。例如，以雜湊表實作的物件也會使用與 Redis SCAN 指令內部相同的機制來漸進式地回收：利用字典中的游標來迭代，一個接一個地釋放元素。這樣，在每次計時器呼叫中，我們就不必一次釋放整個雜湊表。游標會告訴我們下次重新進入計時器函式時，該從哪裡繼續。

要做到自適應很難

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

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

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

然而，經過幾次實驗後，我找到了一個效果非常好的方法。計時器函式運用了兩個想法，以便能根據記憶體壓力自動調整：

1. 檢查記憶體的趨勢：是在上升還是下降？以此來調整釋放的積極程度。
2. 同時也根據第 1 點來調整計時器本身的頻率，這樣當沒什麼需要釋放時，就不會因為不斷中斷事件迴圈而浪費 CPU 時間。同時，在真正需要時，計時器的頻率可以達到約 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 */
}

這是個不錯的技巧，而且運作得非常好。但即便如此，用單一執行緒來做這件事還是讓人有點遺憾。這需要大量的邏輯才能處理得好，而且無論如何，當惰性釋放週期非常忙碌時，每秒操作數會降至正常情況下的約 65%。

在不同的執行緒中釋放物件會簡單得多：只要有一個專門負責釋放操作的執行緒，釋放幾乎總是比在資料集中新增值來得快。當然，主執行緒呼叫記憶體配置器與惰性釋放執行緒同時操作之間會存在一些競爭，但 Redis 花在記憶體配置上的時間只佔一小部分，更多時間是花在 I/O、指令分派、快取未命中等等。

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

但是，嘿，這裡還有一些問題。如果我在 SUNIONSTORE 之後重新載入資料庫，物件就會變成非共享狀態，所以記憶體可能會突然暴增到比原來更多。這不太好。此外，當我們向客戶端發送回覆時，實際上會在物件較小時將它們「黏合」成純粹的緩衝區，因為否則執行大量的 write() 呼叫是沒有效率的！（免費提示，writev() 也幫不上忙）。所以我們大多數時候本來就在複製了。而在程式設計中，當某個東西沒什麼用卻又存在時，它很可能就是個問題。

而且的確，每當你需要存取某個包含聚合資料型別的鍵中的值時，你都必須經過以下路徑：

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

那麼，如果完全去掉「robj」結構，並將聚合型別的值改為僅由 SDS 字串的雜湊表（或跳躍表）組成，會怎麼樣呢？（SDS 是我們在 Redis 內部用來處理字串的函式庫）。這樣做有個問題。想像一個像 SADD myset myvalue 這樣的指令。我們不能直接拿 client->argv[2] 來，例如，直接在實作集合的雜湊表中引用它。我們有時必須「複製」值，而無法重複使用在解析指令時已在客戶端參數向量中建立好的值。然而，Redis 的效能主要受快取未命中所主導，所以也許我們可以用少一層間接存取來彌補這一點？

所以我開始著手這個新的 lazyfree 分支，並在 Twitter 上毫無上下文地發文談論它，以至於大家都以為我快絕望或瘋了（最後有幾個人問說這個 lazyfree 到底是什麼鬼）。那我做了什麼呢？

1. 將客戶端輸出緩衝區改為只使用動態字串，而不是 robj 結構。在需要建立回覆時，值永遠會被複製。
2. 將所有 Redis 資料型別改為使用 SDS 字串，而不是共享的 robj 結構。聽起來很簡單？在長達數週的過程中改了約 800 行對錯誤極為敏感的程式碼。但現在所有測試都通過了。
3. 將 lazyfree 重寫為執行緒化的版本。

結果是，Redis 現在的記憶體效率更高了，因為在資料結構的實作中不再到處存在 robj 結構（但在有大量共享的程式碼路徑中，例如指令分派和複寫期間，仍會使用它們）。執行緒化的惰性釋放運作得非常好，而且比漸進式版本更快地回收記憶體，即使漸進式版本的實作是我非常喜歡的，而且相較於執行緒化版本也沒有糟到哪去。但現在，你可以刪除一個巨大的鍵，而效能下降卻微乎其微，這非常有用。不過，最有趣的是，到目前為止，我測試過的所有操作中，Redis 現在都變得更快了。減少一層間接存取真的是個大贏家。即使在不相關的基準測試中也更快，僅僅是因為客戶端輸出緩衝區現在更簡單、更快了。最後，我從分支中刪除了漸進式惰性釋放的實作，只保留了執行緒化的版本。

關於 API 的說明

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

UNLINK 是一個聰明的指令：它會計算物件的回收成本，如果成本非常小，它就會像 DEL 應該做的那樣，盡快釋放物件。否則，物件就會被送到背景佇列中處理。除此之外，就鍵空間的語意而言，這兩個指令是完全相同的。

另外也實作了 FLUSHALL / FLUSHDB 的非阻塞變體，但目前還未在 API 層面開放，它們只會接受一個 LAZY 選項，如果提供了該選項，就會改變其行為。

不只是惰性釋放

現在聚合資料型別的值已經完全不共享，而且客戶端輸出緩衝區也不再包含共享物件，有很多事情可以加以利用。例如，終於可以在 Redis 中實作 threaded I/O(執行緒化 I/O) 了，讓不同的客戶端由不同的執行緒來服務。這意味著我們只有在存取資料庫時才需要全域鎖定，但客戶端的讀寫系統呼叫，甚至客戶端所傳送指令的解析，都可以在不同的執行緒中發生。這是一種類似於 memcached 的設計，也是我期待去實作與測試的設計。

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

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

預計時程

我動到了大量的內部結構，這不是明天就能上線的東西。所以我的計畫是，將目前 unstable 分支中的內容稱為 3.2 版，並著手將其推進到 Release Candidate 狀態，然後再將這個分支合併到 unstable 中，目標是 3.4 版。

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

如果你想試試看，請在 Github 上查看「lazyfree」分支。對了，請注意我目前正在非常積極地開發它，所以某些東西在某些時刻可能會完全壞掉。