作為一名服務(wù)端工程師，工作中你肯定和 Redis 打過(guò)交道。Redis 為什么快，這點(diǎn)想必你也知道，至少為了面試也做過(guò)準(zhǔn)備。很多人知道 Redis 快僅僅因?yàn)樗腔趦?nèi)存實(shí)現(xiàn)的，對(duì)于其他原因倒是模棱兩可。

[[349387]]

 圖片來(lái)自 Pexels

那么今天就和我一起看看：

 

思維導(dǎo)圖

基于內(nèi)存實(shí)現(xiàn)

這點(diǎn)在一開(kāi)始就提到過(guò)了，這里再簡(jiǎn)單說(shuō)說(shuō)。

Redis 是基于內(nèi)存的數(shù)據(jù)庫(kù)，那不可避免的就要與磁盤數(shù)據(jù)庫(kù)做對(duì)比。對(duì)于磁盤數(shù)據(jù)庫(kù)來(lái)說(shuō)，是需要將數(shù)據(jù)讀取到內(nèi)存里的，這個(gè)過(guò)程會(huì)受到磁盤 I/O 的限制。

而對(duì)于內(nèi)存數(shù)據(jù)庫(kù)來(lái)說(shuō)，本身數(shù)據(jù)就存在于內(nèi)存里，也就沒(méi)有了這方面的開(kāi)銷。

高效的數(shù)據(jù)結(jié)構(gòu)

Redis 中有多種數(shù)據(jù)類型，每種數(shù)據(jù)類型的底層都由一種或多種數(shù)據(jù)結(jié)構(gòu)來(lái)支持。

正是因?yàn)橛辛诉@些數(shù)據(jù)結(jié)構(gòu)，Redis 在存儲(chǔ)與讀取上的速度才不受阻礙。這些數(shù)據(jù)結(jié)構(gòu)有什么特別的地方，各位看官接著往下看：

 

簡(jiǎn)單動(dòng)態(tài)字符串

這個(gè)名詞可能你不熟悉，換成 SDS 肯定就知道了。這是用來(lái)處理字符串的。了解 C 語(yǔ)言的都知道，它是有處理字符串方法的。

而 Redis 就是 C 語(yǔ)言實(shí)現(xiàn)的，那為什么還要重復(fù)造輪子?我們從以下幾點(diǎn)來(lái)看：

①字符串長(zhǎng)度處理

 

這個(gè)圖是字符串在 C 語(yǔ)言中的存儲(chǔ)方式，想要獲取 Redis 的長(zhǎng)度，需要從頭開(kāi)始遍歷，直到遇到 '\0' 為止。

 

Redis 中怎么操作呢?用一個(gè) len 字段記錄當(dāng)前字符串的長(zhǎng)度。想要獲取長(zhǎng)度只需要獲取 len 字段即可。

你看，差距不言自明。前者遍歷的時(shí)間復(fù)雜度為 O(n)，Redis 中 O(1) 就能拿到，速度明顯提升。

②內(nèi)存重新分配

C 語(yǔ)言中涉及到修改字符串的時(shí)候會(huì)重新分配內(nèi)存。修改地越頻繁，內(nèi)存分配也就越頻繁。而內(nèi)存分配是會(huì)消耗性能的，那么性能下降在所難免。

而 Redis 中會(huì)涉及到字符串頻繁的修改操作，這種內(nèi)存分配方式顯然就不適合了。

于是 SDS 實(shí)現(xiàn)了兩種優(yōu)化策略：

空間預(yù)分配：對(duì) SDS 修改及空間擴(kuò)充時(shí)，除了分配所必須的空間外，還會(huì)額外分配未使用的空間。

具體分配規(guī)則是這樣的：SDS 修改后，len 長(zhǎng)度小于 1M，那么將會(huì)額外分配與 len 相同長(zhǎng)度的未使用空間。如果修改后長(zhǎng)度大于 1M，那么將分配 1M 的使用空間。

惰性空間釋放：當(dāng)然，有空間分配對(duì)應(yīng)的就有空間釋放。

SDS 縮短時(shí)，并不會(huì)回收多余的內(nèi)存空間，而是使用 free 字段將多出來(lái)的空間記錄下來(lái)。如果后續(xù)有變更操作，直接使用 free 中記錄的空間，減少了內(nèi)存的分配。

③二進(jìn)制安全

你已經(jīng)知道了 Redis 可以存儲(chǔ)各種數(shù)據(jù)類型，那么二進(jìn)制數(shù)據(jù)肯定也不例外。但二進(jìn)制數(shù)據(jù)并不是規(guī)則的字符串格式，可能會(huì)包含一些特殊的字符，比如 '\0' 等。

前面我們提到過(guò)，C 中字符串遇到 '\0' 會(huì)結(jié)束，那 '\0' 之后的數(shù)據(jù)就讀取不上了。但在 SDS 中，是根據(jù) len 長(zhǎng)度來(lái)判斷字符串結(jié)束的。

看，二進(jìn)制安全的問(wèn)題就解決了。

雙端鏈表

列表 List 更多是被當(dāng)作隊(duì)列或棧來(lái)使用的。隊(duì)列和棧的特性一個(gè)先進(jìn)先出，一個(gè)先進(jìn)后出。雙端鏈表很好的支持了這些特性。

 

雙端鏈表

①前后節(jié)點(diǎn)

 

鏈表里每個(gè)節(jié)點(diǎn)都帶有兩個(gè)指針，prev 指向前節(jié)點(diǎn)，next 指向后節(jié)點(diǎn)。這樣在時(shí)間復(fù)雜度為 O(1) 內(nèi)就能獲取到前后節(jié)點(diǎn)。 

②頭尾節(jié)點(diǎn)

 

你可能注意到了，頭節(jié)點(diǎn)里有 head 和 tail 兩個(gè)參數(shù)，分別指向頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。

這樣的設(shè)計(jì)能夠?qū)﹄p端節(jié)點(diǎn)的處理時(shí)間復(fù)雜度降至 O(1) ，對(duì)于隊(duì)列和棧來(lái)說(shuō)再適合不過(guò)。同時(shí)鏈表迭代時(shí)從兩端都可以進(jìn)行。

③鏈表長(zhǎng)度

頭節(jié)點(diǎn)里同時(shí)還有一個(gè)參數(shù) len，和上邊提到的 SDS 里類似，這里是用來(lái)記錄鏈表長(zhǎng)度的。

因此獲取鏈表長(zhǎng)度時(shí)不用再遍歷整個(gè)鏈表，直接拿到 len 值就可以了，這個(gè)時(shí)間復(fù)雜度是 O(1)。

你看，這些特性都降低了 List 使用時(shí)的時(shí)間開(kāi)銷。

壓縮列表

雙端鏈表我們已經(jīng)熟悉了。不知道你有沒(méi)有注意到一個(gè)問(wèn)題：如果在一個(gè)鏈表節(jié)點(diǎn)中存儲(chǔ)一個(gè)小數(shù)據(jù)，比如一個(gè)字節(jié)。那么對(duì)應(yīng)的就要保存頭節(jié)點(diǎn)，前后指針等額外的數(shù)據(jù)。

這樣就浪費(fèi)了空間，同時(shí)由于反復(fù)申請(qǐng)與釋放也容易導(dǎo)致內(nèi)存碎片化。這樣內(nèi)存的使用效率就太低了。

于是，壓縮列表上場(chǎng)了!

它是經(jīng)過(guò)特殊編碼，專門為了提升內(nèi)存使用效率設(shè)計(jì)的。所有的操作都是通過(guò)指針與解碼出來(lái)的偏移量進(jìn)行的。 

并且壓縮列表的內(nèi)存是連續(xù)分配的，遍歷的速度很快。

字典

Redis 作為 K-V 型數(shù)據(jù)庫(kù)，所有的鍵值都是用字典來(lái)存儲(chǔ)的。

日常學(xué)習(xí)中使用的字典你應(yīng)該不會(huì)陌生，想查找某個(gè)詞通過(guò)某個(gè)字就可以直接定位到，速度非?？?。

這里所說(shuō)的字典原理上是一樣的，通過(guò)某個(gè) key 可以直接獲取到對(duì)應(yīng)的 value。

字典又稱為哈希表，這點(diǎn)沒(méi)什么可說(shuō)的。哈希表的特性大家都很清楚，能夠在 O(1) 時(shí)間復(fù)雜度內(nèi)取出和插入關(guān)聯(lián)的值。

跳躍表

作為 Redis 中特有的數(shù)據(jù)結(jié)構(gòu)-跳躍表，其在鏈表的基礎(chǔ)上增加了多級(jí)索引來(lái)提升查找效率。

 

這是跳躍表的簡(jiǎn)單原理圖，每一層都有一條有序的鏈表，最底層的鏈表包含了所有的元素。這樣跳躍表就可以支持在 O(logN) 的時(shí)間復(fù)雜度里查找到對(duì)應(yīng)的節(jié)點(diǎn)。

下面這張是跳表真實(shí)的存儲(chǔ)結(jié)構(gòu)，和其它數(shù)據(jù)結(jié)構(gòu)一樣，都在頭節(jié)點(diǎn)里記錄了相應(yīng)的信息，減少了一些不必要的系統(tǒng)開(kāi)銷。

 

合理的數(shù)據(jù)編碼

對(duì)于每一種數(shù)據(jù)類型來(lái)說(shuō)，底層的支持可能是多種數(shù)據(jù)結(jié)構(gòu)，什么時(shí)候使用哪種數(shù)據(jù)結(jié)構(gòu)，這就涉及到了編碼轉(zhuǎn)化的問(wèn)題。

那我們就來(lái)看看，不同的數(shù)據(jù)類型是如何進(jìn)行編碼轉(zhuǎn)化的：

• String：存儲(chǔ)數(shù)字的話，采用 int 類型的編碼，如果是非數(shù)字的話，采用 raw 編碼。
• List：字符串長(zhǎng)度及元素個(gè)數(shù)小于一定范圍使用 ziplist 編碼，任意條件不滿足，則轉(zhuǎn)化為 linkedlist 編碼。
• Hash：hash 對(duì)象保存的鍵值對(duì)內(nèi)的鍵和值字符串長(zhǎng)度小于一定值及鍵值對(duì)。
• Set：保存元素為整數(shù)及元素個(gè)數(shù)小于一定范圍使用 intset 編碼，任意條件不滿足，則使用 hashtable 編碼。
• Zset：zset 對(duì)象中保存的元素個(gè)數(shù)小于及成員長(zhǎng)度小于一定值使用 ziplist 編碼，任意條件不滿足，則使用 skiplist 編碼。

合適的線程模型

Redis 快的原因還有一個(gè)是因?yàn)槭褂昧撕线m的線程模型：

 

I/O 多路復(fù)用模型

I/O ：網(wǎng)絡(luò) I/O;多路：多個(gè) TCP 連接;復(fù)用：共用一個(gè)線程或進(jìn)程。

生產(chǎn)環(huán)境中的使用，通常是多個(gè)客戶端連接 Redis，然后各自發(fā)送命令至 Redis 服務(wù)器，最后服務(wù)端處理這些請(qǐng)求返回結(jié)果。

應(yīng)對(duì)大量的請(qǐng)求，Redis 中使用 I/O 多路復(fù)用程序同時(shí)監(jiān)聽(tīng)多個(gè)套接字，并將這些事件推送到一個(gè)隊(duì)列里，然后逐個(gè)被執(zhí)行。最終將結(jié)果返回給客戶端。 

避免上下文切換

你一定聽(tīng)說(shuō)過(guò)，Redis 是單線程的。那么單線程的 Redis 為什么會(huì)快呢?

因?yàn)槎嗑€程在執(zhí)行過(guò)程中需要進(jìn)行 CPU 的上下文切換，這個(gè)操作比較耗時(shí)。

Redis 又是基于內(nèi)存實(shí)現(xiàn)的，對(duì)于內(nèi)存來(lái)說(shuō)，沒(méi)有上下文切換效率就是最高的。多次讀寫都在一個(gè)CPU 上，對(duì)于內(nèi)存來(lái)說(shuō)就是最佳方案。

單線程模型

順便提一下，為什么 Redis 是單線程的。

Redis 中使用了 Reactor 單線程模型，你可能對(duì)它并不熟悉。沒(méi)關(guān)系，只需要大概了解一下即可。

 

這張圖里，接收到用戶的請(qǐng)求后，全部推送到一個(gè)隊(duì)列里，然后交給文件事件分派器，而它是單線程的工作方式。Redis 又是基于它工作的，所以說(shuō) Redis 是單線程的。

Redis 單線程與多線程

Redis是單線程的，這話擱以前，是橫著走的，誰(shuí)都知道的真理?，F(xiàn)在不一樣，Redis 變了。再說(shuō)這句話，多少得有質(zhì)疑的語(yǔ)氣來(lái)跟你辯駁一番。意志不堅(jiān)定的，可能就繳械投降，順著別人走了。

到底是什么樣的，各位看官請(qǐng)跟小萊一起往下看：

 

Reactor 模式

反應(yīng)器模式，你可能不太認(rèn)識(shí)，如果看完上文的話應(yīng)該會(huì)有點(diǎn)印象。涉及到 Redis 線程它是一個(gè)繞不過(guò)去的話題。

①傳統(tǒng)阻塞 IO 模型

在講反應(yīng)器模式前，這里有必要提一下傳統(tǒng)阻塞 IO 模型的處理方式。

在傳統(tǒng)阻塞 IO 模型中，由一個(gè)獨(dú)立的 Acceptor 線程來(lái)監(jiān)聽(tīng)客戶端的連接，每當(dāng)有客戶端請(qǐng)求過(guò)來(lái)時(shí)，它就會(huì)為客戶端分配一個(gè)新的線程來(lái)進(jìn)行處理。

當(dāng)同時(shí)有多個(gè)請(qǐng)求過(guò)來(lái)，服務(wù)端對(duì)應(yīng)的就會(huì)分配相應(yīng)數(shù)量的線程。這就會(huì)導(dǎo)致 CPU 頻繁切換，浪費(fèi)資源。

有的連接請(qǐng)求過(guò)來(lái)不做任何事情，但服務(wù)端還會(huì)分配對(duì)應(yīng)的線程，這樣就會(huì)造成不必要的線程開(kāi)銷。

這就好比你去餐廳吃飯，你拿著菜單看了半天發(fā)現(xiàn)真他娘的貴，然后你就走人了。

這段時(shí)間等你點(diǎn)菜的服務(wù)員就相當(dāng)于一個(gè)對(duì)應(yīng)的線程，你要點(diǎn)菜可以看作一個(gè)連接請(qǐng)求。

 

同時(shí)，每次建立連接后，當(dāng)線程調(diào)用讀寫方法時(shí)，線程會(huì)被阻塞，直到有數(shù)據(jù)可讀可寫，在此期間線程不能做其它事情。

還是上邊餐廳吃飯的例子，你出去轉(zhuǎn)了一圈發(fā)現(xiàn)還是這家性價(jià)比最高?；氐竭@家餐廳又拿著菜單看了半天，服務(wù)員也在旁邊等你點(diǎn)完菜為止。

這個(gè)過(guò)程中服務(wù)員什么也不能做，只能這么干等著，這個(gè)過(guò)程相當(dāng)于阻塞。

 

你看這樣的方式，每來(lái)一個(gè)請(qǐng)求就要分配一個(gè)線程，并且還得阻塞地等線程處理完。

有的請(qǐng)求還只是過(guò)來(lái)連接下，什么操作也不干，還得為它分配一個(gè)線程，對(duì)服務(wù)器資源要求那得多高啊。

遇到高并發(fā)場(chǎng)景，不敢想象。對(duì)于連接數(shù)目比較小的的固定架構(gòu)倒是可以考慮。

②偽異步 IO 模型

你可能了解過(guò)一種通過(guò)線程池優(yōu)化的解決方案，采用線程池和任務(wù)隊(duì)列的方式。這種被稱作偽異步 IO 模型。

當(dāng)有客戶端接入時(shí)，將客戶端的請(qǐng)求封裝成一個(gè) task 投遞到后端線程池中來(lái)處理。線程池維護(hù)一個(gè)消息隊(duì)列和多個(gè)活躍線程，對(duì)消息隊(duì)列中的任務(wù)進(jìn)行處理。

 

這種解決方案，避免了為每個(gè)請(qǐng)求創(chuàng)建一個(gè)線程導(dǎo)致的線程資源耗盡問(wèn)題。但是底層仍然是同步阻塞模型。

如果線程池內(nèi)的所有線程都阻塞了，那么對(duì)于更多請(qǐng)求就無(wú)法響應(yīng)了。因此這種模式會(huì)限制最大連接數(shù)，并不能從根本上解決問(wèn)題。

我們繼續(xù)用上邊的餐廳來(lái)舉例，餐廳老板在經(jīng)營(yíng)了一段時(shí)間后，顧客多了起來(lái)，原本店里的 5 個(gè)服務(wù)員一對(duì)一服務(wù)的話根本對(duì)付不過(guò)來(lái)。

于是老板采用 5 個(gè)人線程池的方式。服務(wù)員服務(wù)完一個(gè)客人后立刻去服務(wù)另一個(gè)。

這時(shí)問(wèn)題出現(xiàn)了，有的客人點(diǎn)菜特別慢，服務(wù)員就得等待很長(zhǎng)時(shí)間，直到客人點(diǎn)完為止。

如果 5 個(gè)客人都點(diǎn)的特別慢的話，這 5 個(gè)服務(wù)員就得一直等下去，就會(huì)導(dǎo)致其余的顧客沒(méi)有人服務(wù)的狀態(tài)。這就是我們上邊所說(shuō)的線程池所有線程都被阻塞的情況。

那么這種問(wèn)題該如何解決呢?別急， Reactor 模式就要出場(chǎng)了。

③Reactor 設(shè)計(jì)模式

Reactor 模式的基本設(shè)計(jì)思想是基于 I/O 復(fù)用模型來(lái)實(shí)現(xiàn)的。

這里說(shuō)下 I/O 復(fù)用模型。和傳統(tǒng) IO 多線程阻塞不同，I/O 復(fù)用模型中多個(gè)連接共用一個(gè)阻塞對(duì)象，應(yīng)用程序只需要在一個(gè)阻塞對(duì)象等待。

當(dāng)某個(gè)連接有新的數(shù)據(jù)可以處理時(shí)，操作系統(tǒng)通知應(yīng)用程序，線程從阻塞狀態(tài)返回，開(kāi)始進(jìn)行業(yè)務(wù)處理。

什么意思呢?餐廳老板也發(fā)現(xiàn)了顧客點(diǎn)餐慢的問(wèn)題，于是他采用了一種大膽的方式，只留了一個(gè)服務(wù)員。

當(dāng)客人點(diǎn)餐的時(shí)候，這個(gè)服務(wù)員就去招待別的客人，客人點(diǎn)好餐后直接喊服務(wù)員來(lái)進(jìn)行服務(wù)。

這里的顧客和服務(wù)員可以分別看作多個(gè)連接和一個(gè)線程。服務(wù)員阻塞在一個(gè)顧客那里，當(dāng)有別的顧客點(diǎn)好餐后，她就立刻去服務(wù)其他的顧客。

了解了 Reactor 的設(shè)計(jì)思想后，我們?cè)賮?lái)看下今天的主角單 Reactor 單線程的實(shí)現(xiàn)方案：

 

Reactor 通過(guò) I/O 復(fù)用程序監(jiān)控客戶端請(qǐng)求事件，收到事件后通過(guò)任務(wù)分派器進(jìn)行分發(fā)。

針對(duì)建立連接請(qǐng)求事件，通過(guò) Acceptor 處理，并建立對(duì)應(yīng)的 handler 負(fù)責(zé)后續(xù)業(yè)務(wù)處理。

針對(duì)非連接事件，Reactor 會(huì)調(diào)用對(duì)應(yīng)的 handler 完成 read→業(yè)務(wù)處理→write 處理流程，并將結(jié)果返回給客戶端。

整個(gè)過(guò)程都在一個(gè)線程里完成：

 

單線程時(shí)代

了解了 Reactor 模式后，你可能會(huì)有一個(gè)疑問(wèn)，這個(gè)和我們今天的主題有什么關(guān)系呢?？赡苣悴恢赖氖?，Redis 是基于 Reactor 單線程模式來(lái)實(shí)現(xiàn)的。

IO多路復(fù)用程序接收到用戶的請(qǐng)求后，全部推送到一個(gè)隊(duì)列里，交給文件分派器。

對(duì)于后續(xù)的操作，和在 Reactor 單線程實(shí)現(xiàn)方案里看到的一樣，整個(gè)過(guò)程都在一個(gè)線程里完成，因此 Redis 被稱為是單線程的操作。 

 

對(duì)于單線程的 Redis 來(lái)說(shuō)，基于內(nèi)存，且命令操作時(shí)間復(fù)雜度低，因此讀寫速率是非?？斓?。

多線程時(shí)代

Redis6 版本中引入了多線程。上邊已經(jīng)提到過(guò) Redis 單線程處理有著很快的速度，那為什么還要引入多線程呢?單線程的瓶頸在什么地方?

我們先來(lái)看第二個(gè)問(wèn)題，在 Redis 中，單線程的性能瓶頸主要在網(wǎng)絡(luò)IO操作上。

也就是在讀寫網(wǎng)絡(luò) read/write 系統(tǒng)調(diào)用執(zhí)行期間會(huì)占用大部分 CPU 時(shí)間。如果你要對(duì)一些大的鍵值對(duì)進(jìn)行刪除操作的話，在短時(shí)間內(nèi)是刪不完的，那么對(duì)于單線程來(lái)說(shuō)就會(huì)阻塞后邊的操作。

回想下上邊講得 Reactor 模式中單線程的處理方式。針對(duì)非連接事件，Reactor 會(huì)調(diào)用對(duì)應(yīng)的 handler 完成 read→業(yè)務(wù)處理→write 處理流程，也就是說(shuō)這一步會(huì)造成性能上的瓶頸。

Redis 在設(shè)計(jì)上采用將網(wǎng)絡(luò)數(shù)據(jù)讀寫和協(xié)議解析通過(guò)多線程的方式來(lái)處理，對(duì)于命令執(zhí)行來(lái)說(shuō)，仍然使用單線程操作。

總結(jié)

基于內(nèi)存實(shí)現(xiàn)：

• 數(shù)據(jù)都存儲(chǔ)在內(nèi)存里，減少了一些不必要的 I/O 操作，操作速率很快。

高效的數(shù)據(jù)結(jié)構(gòu)：

• 底層多種數(shù)據(jù)結(jié)構(gòu)支持不同的數(shù)據(jù)類型，支持 Redis 存儲(chǔ)不同的數(shù)據(jù)。
• 不同數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，使得數(shù)據(jù)存儲(chǔ)時(shí)間復(fù)雜度降到最低。

合理的數(shù)據(jù)編碼：

• 根據(jù)字符串的長(zhǎng)度及元素的個(gè)數(shù)適配不同的編碼格式。

合適的線程模型：

• I/O 多路復(fù)用模型同時(shí)監(jiān)聽(tīng)客戶端連接;
• 單線程在執(zhí)行過(guò)程中不需要進(jìn)行上下文切換，減少了耗時(shí)。

Reactor 模式：

• 傳統(tǒng)阻塞 IO 模型客戶端與服務(wù)端線程 1:1 分配，不利于進(jìn)行擴(kuò)展。
• 偽異步 IO 模型采用線程池方式，但是底層仍然使用同步阻塞方式，限制了最大連接數(shù)。
• Reactor 通過(guò) I/O 復(fù)用程序監(jiān)控客戶端請(qǐng)求事件，通過(guò)任務(wù)分派器進(jìn)行分發(fā)。

單線程時(shí)代：

• 基于 Reactor 單線程模式實(shí)現(xiàn)，通過(guò) IO 多路復(fù)用程序接收到用戶的請(qǐng)求后，全部推送到一個(gè)隊(duì)列里，交給文件分派器進(jìn)行處理。

多線程時(shí)代：

• 單線程性能瓶頸主要在網(wǎng)絡(luò) IO 上。
• 將網(wǎng)絡(luò)數(shù)據(jù)讀寫和協(xié)議解析通過(guò)多線程的方式來(lái)處理 ，對(duì)于命令執(zhí)行來(lái)說(shuō)，仍然使用單線程操作。

作者：小萊，一枚后端工程師

編輯：陶家龍

出處：轉(zhuǎn)載自公眾號(hào)IT界農(nóng)民工(ID：kejishuqian)