英文原文：Lazy Redis is better Redis

前言

大家都知道 Redis 是單線程的。真正的內(nèi)行會(huì)告訴你，實(shí)際上 Redis 并不是完全單線程，因?yàn)樵趫?zhí)行磁盤上的特定慢操作時(shí)會(huì)有多線程。目前為止多線程操作絕大部分集中在 I/O 上以至于在不同線程執(zhí)行異步任務(wù)的小型庫被稱為 bio.c: 也就是 Background I/O。

然而前陣子我提交了一個(gè)問題，在問題里我承諾提供一個(gè)很多人（包括我自己）都想要的功能，叫做“免費(fèi)懶加載”。原始的問題在這

問題的根本在于，Redis 的 DEL 操作通常是阻塞的。因此如果你發(fā)送 Redis “DEL mykey” 命令，碰巧你的 key 有 5000萬個(gè)對(duì)象，那么服務(wù)器將會(huì)阻塞幾秒鐘，在此期間服務(wù)器不會(huì)處理其他請(qǐng)求。歷史上這被當(dāng)做 Redis 設(shè)計(jì)的副作用而被接受，但是在特定的用例下這是一個(gè)局限。DEL 不是唯一的阻塞式命令，卻是特殊的一個(gè)命令，因?yàn)槲覀冋J(rèn)為：Redis 非?？?，只要你用復(fù)雜度為 O(1) 和 O(log_N) 的命令。你可以自由使用 O(N) 的命令，但是要知道這不是我們優(yōu)化的用例，你需要做好延遲的準(zhǔn)備。

這聽起來很合理，但是同時(shí)即便用快速操作創(chuàng)建的對(duì)象也需要被刪除。在這種情況下，Redis 會(huì)阻塞。

第一次嘗試
—

對(duì)于單線程服務(wù)器，為了讓操作不阻塞，最簡(jiǎn)單的方式就是用增量的方式一點(diǎn)點(diǎn)來，而不是一下子把整個(gè)世界都搞定。例如，如果要釋放一個(gè)百萬級(jí)的對(duì)象，可以每一個(gè)毫秒釋放1000個(gè)元素，而不是在一個(gè) for() 循環(huán)里一次性全做完。CPU 的耗時(shí)是差不多的，也許會(huì)稍微多一些，因?yàn)檫壿嫺嘁恍?，但是從用戶來看延時(shí)更少一些。當(dāng)然也許實(shí)際上并沒有每毫秒刪除1000個(gè)元素，這只是個(gè)例子。重點(diǎn)是如何避免秒級(jí)的阻塞。在 Redis 內(nèi)部做了很多事情：最顯然易見的是 LRU 淘汰機(jī)制和 key 的過期，還有其他方面的，例如增量式的對(duì) hash 表進(jìn)行重排。

剛開始我們是這樣嘗試的：創(chuàng)建一個(gè)新的定時(shí)器函數(shù)，在里面實(shí)現(xiàn)淘汰機(jī)制。對(duì)象只是被添加到一個(gè)鏈表里，每次定時(shí)器調(diào)用的時(shí)候，會(huì)逐步的、增量式的去釋放。這需要一些小技巧，例如，那些用哈希表實(shí)現(xiàn)的對(duì)象，會(huì)使用 Redis 的 SCAN 命令里相同的機(jī)制去增量式的釋放：在字典里設(shè)置一個(gè)游標(biāo)來遍歷和釋放元素。通過這種方式，在每次定時(shí)器調(diào)用的時(shí)候我們不需要釋放整個(gè)哈希表。在重新進(jìn)入定時(shí)器函數(shù)時(shí)，游標(biāo)可以告訴我們上次釋放到哪里了。

適配是困難的
—

你知道這里最困難的部分是哪里嗎？這次我們是在增量式的做一件很特別的事情：釋放內(nèi)存。如果內(nèi)存的釋放是增量式的，服務(wù)器的內(nèi)容增長將會(huì)非?？?，最后為了得到更少的延時(shí)，會(huì)消耗調(diào)無限的內(nèi)存。這很糟，想象一下，有下面的操作：

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

如果慢慢的在后臺(tái)去刪除myset，同時(shí)SADD調(diào)用又在不斷的添加大量的元素，內(nèi)存使用量將會(huì)一直增長。

好在經(jīng)過一段嘗試之后，我找到一種可以工作的很好的方式。定時(shí)器函數(shù)里使用了兩個(gè)想法來適應(yīng)內(nèi)存的壓力：

1.檢測(cè)內(nèi)存趨勢(shì)：增加還是減少？以決定釋放的力度。

2.同時(shí)適配定時(shí)器的頻率，避免在只有很少需要釋放的時(shí)候去浪費(fèi)CPU，不用頻繁的去中斷事件循環(huán)。當(dāng)確實(shí)需要的時(shí)候，定時(shí)器也可以達(dá)到大約300HZ的頻率。
這里有一小段代碼，不過這個(gè)想法現(xiàn)在已經(jīng)不再實(shí)現(xiàn)了：

/計(jì)算內(nèi)存趨勢(shì)，只要是上次和這次內(nèi)存都在增加，就傾向于認(rèn)為內(nèi)存趨勢(shì)
 是增加的 */

if (prev_mem lt; mem) mem_trend = 1;
   
mem_trend *= 0.9; /* 逐漸衰減 */
   
int mem_is_raising = mem_trend gt; .1;

   
/* 釋放一些元素 */
   
size_t workdone = lazyfreeStep(LAZYFREE_STEP_SLOW);

   
/* 根據(jù)現(xiàn)有狀態(tài)調(diào)整定時(shí)器頻率 */
   
if (workdone) {
       
    if (timer_period == 1000) timer_period = 20;

    if (mem_is_raising timer_period gt; 3)
           
        timer_period--; /* Raise call frequency. */
       
    else if (!mem_is_raising timer_period lt; 20)

        timer_period++; /* Lower call frequency. */
   
} else {
       
  timer_period = 1000;    /* 1 HZ */
   
}

這是一個(gè)小技巧，工作的也很好。不過郁悶的是我們還是不得不在單線程里執(zhí)行。要做好需要有很多的邏輯，而且當(dāng)延遲釋放（lazy free）周期很繁忙的時(shí)候，每秒能完成的操作會(huì)降到平時(shí)的65%左右。
如果是在另一個(gè)線程去釋放對(duì)象，那就簡(jiǎn)單多了：如果有一個(gè)線程只做釋放操作的話，釋放總是要比在數(shù)據(jù)集里添加數(shù)據(jù)來的要快。

當(dāng)然，主線程和延遲釋放線程直接對(duì)內(nèi)存分配器的使用肯定會(huì)有競(jìng)爭(zhēng)，不過 Redis 在內(nèi)存分配上只用到一小部分時(shí)間，更多的時(shí)間用在I/O、命令分發(fā)、緩存失敗等等。
不過，要實(shí)現(xiàn)線程化的延遲釋放有一個(gè)大問題，那就是 Redis 自身。內(nèi)部實(shí)現(xiàn)完全是追求對(duì)象的共享，最終都是些引用計(jì)數(shù)。干嘛不盡可能的共享呢？這樣可以節(jié)省內(nèi)存和時(shí)間。例如：SUNIONSTORE 命令最后得到的是目標(biāo)集合的共享對(duì)象。類似的，客戶端的輸出緩存包含了作為返回結(jié)果發(fā)送給socket的對(duì)象的列表，于是在類似 SMEMBERS 這樣的命令調(diào)用之后，集合的所有成員都有可能最終在輸出緩存里被共享。看上去對(duì)象共享是那么有效、漂亮、精彩，還特別酷。

但是，嘿，還需要再多說一句的是，如果在 SUNIONSTORE 命令之后重新加載了數(shù)據(jù)庫，對(duì)象都取消了共享，內(nèi)存也會(huì)突然回復(fù)到最初的狀態(tài)。這可不太妙。接下來我們發(fā)送應(yīng)答請(qǐng)求給客戶端，會(huì)怎么樣？當(dāng)對(duì)象比較小時(shí)，我們實(shí)際上是把它們拼接成線性的緩存，要不然進(jìn)行多次 write() 調(diào)用效率是不高的！（友情提示，writev() 并沒有幫助）。于是我們大部分情況下是已經(jīng)復(fù)制了數(shù)據(jù)。對(duì)于編程來說，沒有用的東西卻存在，通常意味著是有問題的。
事實(shí)上，訪問一個(gè)包含聚合類型數(shù)據(jù)的key，需要經(jīng)過下面這些遍歷過程：

key -gt; value_obj -gt; hash table -gt; robj -gt; sds_string

如果去掉整個(gè) tobj 結(jié)構(gòu)體，把聚合類型轉(zhuǎn)換成 SDS 字符串類型的哈希表（或者跳表）會(huì)怎么樣？（SDS是Redis內(nèi)部使用的字符串類型）。

這樣做有個(gè)問題，假設(shè)有個(gè)命令：SADD myset myvalue，舉個(gè)例子來說，我們做不到通過client->argv[2] 來引用用來實(shí)現(xiàn)集合的哈希表的某個(gè)元素。我們不得不很多次的把值復(fù)制出來，即使數(shù)據(jù)已經(jīng)在客戶端命令解析后創(chuàng)建的參數(shù) vector 里，也沒辦法去復(fù)用。Redis的性能受控于緩存失效，我們也許可以用稍微間接一些的辦法來彌補(bǔ)一下。
于是我在這個(gè) lazyfree 的分支上開始了一項(xiàng)工作，并且在 Twitter 上聊了一下，但是沒有公布上下文的細(xì)節(jié)，結(jié)果所有的人都覺得我像是絕望或者瘋狂了（甚至有人喊道 lazyfree 到底是什么玩意）。那么，我到底做了什么呢？

把客戶端的輸出緩存由 robj 結(jié)構(gòu)體改成動(dòng)態(tài)字符串。在創(chuàng)建 reply 的時(shí)候總是復(fù)制值的內(nèi)容。
把所有的 Redis 數(shù)據(jù)類型轉(zhuǎn)換成 SDS 字符串，而不是使用共享對(duì)象結(jié)構(gòu)。聽上去很簡(jiǎn)單？實(shí)際上這花費(fèi)了數(shù)周的時(shí)間，涉及到大約800行高風(fēng)險(xiǎn)的代碼修改。不過現(xiàn)在全都測(cè)試通過了。
把 lazyfree 重寫成線程化的。
結(jié)果是 Redis 現(xiàn)在在內(nèi)存使用上更加高效，因?yàn)樵跀?shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)上不再使用 robj 結(jié)構(gòu)體（不過由于某些代碼還涉及到大量的共享，所以 robj 依然存在，例如在命令分發(fā)和復(fù)制部分）。線程化的延遲釋放工作的很好，比增量的方式更能減少內(nèi)存的使用，雖然增量方式在實(shí)現(xiàn)上與線程化的方式相似，并且也沒那么糟糕?，F(xiàn)在，你可以刪除一個(gè)巨大的 key，性能損失可以忽略不計(jì)，這非常有用。不過，最有趣的事情是，在我測(cè)過的一些操作上，Redis 現(xiàn)在都要更快一些。消除間接引用（Less indirection）最后勝出，即使在不相關(guān)的一些測(cè)試上也更快一些，還是因?yàn)榭蛻舳说妮敵鼍彺娆F(xiàn)在更加簡(jiǎn)單和高效。

最后我把增量式的延遲釋放實(shí)現(xiàn)從分支里刪除，只保留了線程化的實(shí)現(xiàn)。

關(guān)于 API 的一點(diǎn)備注

不過 API 又怎么樣了呢？DEL 命令仍然是阻塞的，默認(rèn)還跟以前一樣，因?yàn)樵?Redis 中 DEL 命令就意味著釋放內(nèi)存，我并不打算改變這一點(diǎn)。所以現(xiàn)在你可以用新的命令 UNLINK，這個(gè)命令更清晰的表明了數(shù)據(jù)的狀態(tài)。

UNLINK 是一個(gè)聰明的命令：它會(huì)計(jì)算釋放對(duì)象的開銷，如果開銷很小，就會(huì)直接按 DEL 做的那樣立即釋放對(duì)象，否則對(duì)象會(huì)被放到后臺(tái)隊(duì)列里進(jìn)行處理。除此之外，這兩個(gè)命令在語義上是相同的。

我們也實(shí)現(xiàn)了 FLUSHALL/FLUSHDB 的非阻塞版本，不過沒有新增的 API，而是增加了一個(gè) LAZY 選項(xiàng)，說明是否更改命令的行為。

不只是延遲釋放

—

現(xiàn)在聚合數(shù)據(jù)類型的值都不再共享了，客戶端的輸出緩存也不再包含共享對(duì)象了，這一點(diǎn)有很多文章可做。例如，現(xiàn)在終于可以在 Redis 里實(shí)現(xiàn)線程化的 I/O，從而不同的客戶端可以由不同的線程去服務(wù)。也就是說，只有訪問數(shù)據(jù)庫才需要全局的鎖，客戶端的讀寫系統(tǒng)調(diào)用，甚至是客戶端發(fā)送的命令的解析，都可以在線程中去處理。這跟 memcached 的設(shè)計(jì)理念類似，我比較期待能夠被實(shí)現(xiàn)和測(cè)試。

還有，現(xiàn)在也可以在其他線程實(shí)現(xiàn)針對(duì)聚合數(shù)據(jù)類型的特定的慢操作，可以讓某些 key 被“阻塞”，但是所有其他的客戶端不會(huì)被阻塞。這個(gè)可以用很類似現(xiàn)在的阻塞操作的方式去完成（參考blocking.c），只是增加一個(gè)哈希表保存那些正在處理的 key 和對(duì)應(yīng)的客戶端。于是一個(gè)客戶端請(qǐng)求類似 SMEMBERS 這樣的命令，可能只是僅僅阻塞住這一個(gè) key，然后會(huì)創(chuàng)建輸出緩存處理數(shù)據(jù)，之后在釋放這個(gè) key。只有那些嘗試訪問相同的 key 的客戶端，才會(huì)在這個(gè) key 被阻塞的時(shí)候被阻塞住。
所有這些需求起了更激烈的內(nèi)部變化，但這里的底線我們已很少顧忌。我們可以補(bǔ)償對(duì)象復(fù)制時(shí)間來減少高速緩存的缺失，以更小的內(nèi)存占用聚合數(shù)據(jù)類型，所以我們現(xiàn)在可依照線程化的 Redis 來進(jìn)行無共享化設(shè)計(jì)，這一設(shè)計(jì)，可以很容易超越我們的單線程。在過去，一個(gè)線程化的 Redis 看起來總像是一個(gè)壞主意，因?yàn)闉榱藢?shí)現(xiàn)并發(fā)訪問數(shù)據(jù)結(jié)構(gòu)和對(duì)象其必定是一組互斥鎖，但幸運(yùn)的是還有別的選擇獲得這兩個(gè)環(huán)境的優(yōu)勢(shì)。如果我們想要，我們依然可以選擇快速操作服務(wù)，就像我們過去在主線程所做的那樣。這包含在復(fù)雜的代價(jià)之上，獲取執(zhí)行智能（performance-wise）。

計(jì)劃表
—

我在內(nèi)部增加了很多東西，明天就上線看上去是不現(xiàn)實(shí)的。我的計(jì)劃是先讓3.2版（已經(jīng)是unstable狀態(tài)）成為候選版本（RC）狀態(tài)，然后把我們的分支合并到進(jìn)入unstable的3.4版本。

不過在合并之前，需要對(duì)速度做細(xì)致的回歸測(cè)試，這有不少工作要做。

如果你現(xiàn)在就想嘗試的話，可以從Github上下載lazyfree分支。不過要注意的是，當(dāng)前我并不是很頻繁的更新這個(gè)分支，所以有些地方可能會(huì)不能工作。