作者|萊烏

作爲(wéi / wèi)一(yī / yì ／yí)名服務端工程師，工作中你肯定和(hé / huò) Redis 打過交道(dào)。Redis 爲(wéi / wèi)什麽快，這(zhè)點想必你也(yě)知道(dào)，至少爲(wéi / wèi)了(le／liǎo)面試也(yě)做過準備。很多人(rén)知道(dào) Redis 快僅僅因爲(wéi / wèi)它是(shì)基于(yú)内存實現的(de)，對于(yú)其它原因倒是(shì)模棱兩可。

那麽今天就(jiù)和(hé / huò)小萊一(yī / yì ／yí)起看看：

 - 思維導圖 -

基于(yú)内存實現

這(zhè)點在(zài)一(yī / yì ／yí)開始就(jiù)提到(dào)過了(le／liǎo)，這(zhè)裏再簡單說(shuō)說(shuō)。

Redis 是(shì)基于(yú)内存的(de)數據庫，那不(bù)可避免的(de)就(jiù)要(yào / yāo)與磁盤數據庫做對比。對于(yú)磁盤數據庫來(lái)說(shuō)，是(shì)需要(yào / yāo)将數據讀取到(dào)内存裏的(de)，這(zhè)個(gè)過程會受到(dào)磁盤 I/O 的(de)限制。

而(ér)對于(yú)内存數據庫來(lái)說(shuō)，本身數據就(jiù)存在(zài)于(yú)内存裏，也(yě)就(jiù)沒有了(le／liǎo)這(zhè)方面的(de)開銷。

高效的(de)數據結構

Redis 中有多種數據類型，每種數據類型的(de)底層都由一(yī / yì ／yí)種或多種數據結構來(lái)支持。正是(shì)因爲(wéi / wèi)有了(le／liǎo)這(zhè)些數據結構，Redis 在(zài)存儲與讀取上(shàng)的(de)速度才不(bù)受阻礙。這(zhè)些數據結構有什麽特别的(de)地(dì / de)方，各位看官接着往下看：

1、簡單動态字符串

這(zhè)個(gè)名詞可能你不(bù)熟悉，換成 SDS 肯定就(jiù)知道(dào)了(le／liǎo)。這(zhè)是(shì)用來(lái)處理字符串的(de)。了(le／liǎo)解 C 語言的(de)都知道(dào)，它是(shì)有處理字符串方法的(de)。而(ér) Redis 就(jiù)是(shì) C 語言實現的(de)，那爲(wéi / wèi)什麽還要(yào / yāo)重複造輪子(zǐ)？我們從以(yǐ)下幾點來(lái)看：

（1）字符串長度處理

 這(zhè)個(gè)圖是(shì)字符串在(zài) C 語言中的(de)存儲方式，想要(yào / yāo)獲取 「Redis」的(de)長度，需要(yào / yāo)從頭開始遍曆，直到(dào)遇到(dào) '\0' 爲(wéi / wèi)止。

  Redis 中怎麽操作呢？用一(yī / yì ／yí)個(gè) len 字段記錄當前字符串的(de)長度。想要(yào / yāo)獲取長度隻需要(yào / yāo)獲取 len 字段即可。你看，差距不(bù)言自明。前者遍曆的(de)時(shí)間複雜度爲(wéi / wèi) O(n)，Redis 中 O(1) 就(jiù)能拿到(dào)，速度明顯提升。

（2）内存重新分配

C 語言中涉及到(dào)修改字符串的(de)時(shí)候會重新分配内存。修改地(dì / de)越頻繁，内存分配也(yě)就(jiù)越頻繁。而(ér)内存分配是(shì)會消耗性能的(de)，那麽性能下降在(zài)所難免。

而(ér) Redis 中會涉及到(dào)字符串頻繁的(de)修改操作，這(zhè)種内存分配方式顯然就(jiù)不(bù)适合了(le／liǎo)。于(yú)是(shì) SDS 實現了(le／liǎo)兩種優化策略：

• 空間預分配

對 SDS 修改及空間擴充時(shí)，除了(le／liǎo)分配所必須的(de)空間外，還會額外分配未使用的(de)空間。

具體分配規則是(shì)這(zhè)樣的(de)：SDS 修改後，len 長度小于(yú) 1M，那麽将會額外分配與 len 相同長度的(de)未使用空間。如果修改後長度大(dà)于(yú) 1M，那麽将分配1M的(de)使用空間。

• 惰性空間釋放

當然，有空間分配對應的(de)就(jiù)有空間釋放。

SDS 縮短時(shí)，并不(bù)會回收多餘的(de)内存空間，而(ér)是(shì)使用 free 字段将多出(chū)來(lái)的(de)空間記錄下來(lái)。如果後續有變更操作，直接使用 free 中記錄的(de)空間，減少了(le／liǎo)内存的(de)分配。

（3）二進制安全

你已經知道(dào)了(le／liǎo) Redis 可以(yǐ)存儲各種數據類型，那麽二進制數據肯定也(yě)不(bù)例外。但二進制數據并不(bù)是(shì)規則的(de)字符串格式，可能會包含一(yī / yì ／yí)些特殊的(de)字符，比如 '\0' 等。

前面我們提到(dào)過，C 中字符串遇到(dào) '\0' 會結束，那 '\0' 之(zhī)後的(de)數據就(jiù)讀取不(bù)上(shàng)了(le／liǎo)。但在(zài) SDS 中，是(shì)根據 len 長度來(lái)判斷字符串結束的(de)。

看，二進制安全的(de)問題就(jiù)解決了(le／liǎo)。

2、雙端鏈表

列表 List 更多是(shì)被當作隊列或棧來(lái)使用的(de)。隊列和(hé / huò)棧的(de)特性一(yī / yì ／yí)個(gè)先進先出(chū)，一(yī / yì ／yí)個(gè)先進後出(chū)。雙端鏈表很好的(de)支持了(le／liǎo)這(zhè)些特性。

 - 雙端鏈表 -

（1）前後節點

 鏈表裏每個(gè)節點都帶有兩個(gè)指針，prev 指向前節點，next 指向後節點。這(zhè)樣在(zài)時(shí)間複雜度爲(wéi / wèi) O(1) 内就(jiù)能獲取到(dào)前後節點。

（2）頭尾節點

 你可能注意到(dào)了(le／liǎo)，頭節點裏有 head 和(hé / huò) tail 兩個(gè)參數，分别指向頭節點和(hé / huò)尾節點。這(zhè)樣的(de)設計能夠對雙端節點的(de)處理時(shí)間複雜度降至 O(1) ，對于(yú)隊列和(hé / huò)棧來(lái)說(shuō)再适合不(bù)過。同時(shí)鏈表叠代時(shí)從兩端都可以(yǐ)進行。

（3）鏈表長度

頭節點裏同時(shí)還有一(yī / yì ／yí)個(gè)參數 len，和(hé / huò)上(shàng)邊提到(dào)的(de) SDS 裏類似，這(zhè)裏是(shì)用來(lái)記錄鏈表長度的(de)。因此獲取鏈表長度時(shí)不(bù)用再遍曆整個(gè)鏈表，直接拿到(dào) len 值就(jiù)可以(yǐ)了(le／liǎo)，這(zhè)個(gè)時(shí)間複雜度是(shì) O(1)。

你看，這(zhè)些特性都降低了(le／liǎo) List 使用時(shí)的(de)時(shí)間開銷。

3、壓縮列表

雙端鏈表我們已經熟悉了(le／liǎo)。不(bù)知道(dào)你有沒有注意到(dào)一(yī / yì ／yí)個(gè)問題：如果在(zài)一(yī / yì ／yí)個(gè)鏈表節點中存儲一(yī / yì ／yí)個(gè)小數據，比如一(yī / yì ／yí)個(gè)字節。那麽對應的(de)就(jiù)要(yào / yāo)保存頭節點，前後指針等額外的(de)數據。

這(zhè)樣就(jiù)浪費了(le／liǎo)空間，同時(shí)由于(yú)反複申請與釋放也(yě)容易導緻内存碎片化。這(zhè)樣内存的(de)使用效率就(jiù)太低了(le／liǎo)。

于(yú)是(shì)，壓縮列表上(shàng)場了(le／liǎo)！

它是(shì)經過特殊編碼，專門爲(wéi / wèi)了(le／liǎo)提升内存使用效率設計的(de)。所有的(de)操作都是(shì)通過指針與解碼出(chū)來(lái)的(de)偏移量進行的(de)。

并且壓縮列表的(de)内存是(shì)連續分配的(de)，遍曆的(de)速度很快。

4、字典

Redis 作爲(wéi / wèi) K-V 型數據庫，所有的(de)鍵值都是(shì)用字典來(lái)存儲的(de)。

日常學習中使用的(de)字典你應該不(bù)會陌生，想查找某個(gè)詞通過某個(gè)字就(jiù)可以(yǐ)直接定位到(dào)，速度非常快。這(zhè)裏所說(shuō)的(de)字典原理上(shàng)是(shì)一(yī / yì ／yí)樣的(de)，通過某個(gè) key 可以(yǐ)直接獲取到(dào)對應的(de)value。

字典又稱爲(wéi / wèi)哈希表，這(zhè)點沒什麽可說(shuō)的(de)。哈希表的(de)特性大(dà)家都很清楚，能夠在(zài) O(1) 時(shí)間複雜度内取出(chū)和(hé / huò)插入關聯的(de)值。

5、跳躍表

作爲(wéi / wèi) Redis 中特有的(de)數據結構-跳躍表，其在(zài)鏈表的(de)基礎上(shàng)增加了(le／liǎo)多級索引來(lái)提升查找效率。

 這(zhè)是(shì)跳躍表的(de)簡單原理圖，每一(yī / yì ／yí)層都有一(yī / yì ／yí)條有序的(de)鏈表，最底層的(de)鏈表包含了(le／liǎo)所有的(de)元素。這(zhè)樣跳躍表就(jiù)可以(yǐ)支持在(zài) O(logN) 的(de)時(shí)間複雜度裏查找到(dào)對應的(de)節點。

下面這(zhè)張是(shì)跳表真實的(de)存儲結構，和(hé / huò)其它數據結構一(yī / yì ／yí)樣，都在(zài)頭節點裏記錄了(le／liǎo)相應的(de)信息，減少了(le／liǎo)一(yī / yì ／yí)些不(bù)必要(yào / yāo)的(de)系統開銷。

 合理的(de)數據編碼

對于(yú)每一(yī / yì ／yí)種數據類型來(lái)說(shuō)，底層的(de)支持可能是(shì)多種數據結構，什麽時(shí)候使用哪種數據結構，這(zhè)就(jiù)涉及到(dào)了(le／liǎo)編碼轉化的(de)問題。

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

String：存儲數字的(de)話，采用int類型的(de)編碼，如果是(shì)非數字的(de)話，采用 raw 編碼；

List：字符串長度及元素個(gè)數小于(yú)一(yī / yì ／yí)定範圍使用 ziplist 編碼，任意條件不(bù)滿足，則轉化爲(wéi / wèi) linkedlist 編碼；

Hash：hash 對象保存的(de)鍵值對内的(de)鍵和(hé / huò)值字符串長度小于(yú)一(yī / yì ／yí)定值及鍵值對；

Set：保存元素爲(wéi / wèi)整數及元素個(gè)數小于(yú)一(yī / yì ／yí)定範圍使用 intset 編碼，任意條件不(bù)滿足，則使用 hashtable 編碼；

Zset：zset 對象中保存的(de)元素個(gè)數小于(yú)及成員長度小于(yú)一(yī / yì ／yí)定值使用 ziplist 編碼，任意條件不(bù)滿足，則使用 skiplist 編碼。

合适的(de)線程模型

Redis 快的(de)原因還有一(yī / yì ／yí)個(gè)是(shì)因爲(wéi / wèi)使用了(le／liǎo)合适的(de)線程模型：

1、I/O多路複用模型

• I/O ：網絡 I/O

• 多路：多個(gè) TCP 連接

• 複用：共用一(yī / yì ／yí)個(gè)線程或進程

生産環境中的(de)使用，通常是(shì)多個(gè)客戶端連接 Redis，然後各自發送命令至 Redis 服務器，最後服務端處理這(zhè)些請求返回結果。

 應對大(dà)量的(de)請求，Redis 中使用 I/O 多路複用程序同時(shí)監聽多個(gè)套接字，并将這(zhè)些事件推送到(dào)一(yī / yì ／yí)個(gè)隊列裏，然後逐個(gè)被執行。最終将結果返回給客戶端。

2、避免上(shàng)下文切換

你一(yī / yì ／yí)定聽說(shuō)過，Redis 是(shì)單線程的(de)。那麽單線程的(de) Redis 爲(wéi / wèi)什麽會快呢？

因爲(wéi / wèi)多線程在(zài)執行過程中需要(yào / yāo)進行 CPU 的(de)上(shàng)下文切換，這(zhè)個(gè)操作比較耗時(shí)。Redis 又是(shì)基于(yú)内存實現的(de)，對于(yú)内存來(lái)說(shuō)，沒有上(shàng)下文切換效率就(jiù)是(shì)最高的(de)。多次讀寫都在(zài)一(yī / yì ／yí)個(gè)CPU 上(shàng)，對于(yú)内存來(lái)說(shuō)就(jiù)是(shì)最佳方案。

3、單線程模型

順便提一(yī / yì ／yí)下，爲(wéi / wèi)什麽 Redis 是(shì)單線程的(de)。

Redis 中使用了(le／liǎo) Reactor 單線程模型，你可能對它并不(bù)熟悉。沒關系，隻需要(yào / yāo)大(dà)概了(le／liǎo)解一(yī / yì ／yí)下即可。

這(zhè)張圖裏，接收到(dào)用戶的(de)請求後，全部推送到(dào)一(yī / yì ／yí)個(gè)隊列裏，然後交給文件事件分派器，而(ér)它是(shì)單線程的(de)工作方式。Redis 又是(shì)基于(yú)它工作的(de)，所以(yǐ)說(shuō) Redis 是(shì)單線程的(de)。

 
總結

基于(yú)内存實現

• 數據都存儲在(zài)内存裏，減少了(le／liǎo)一(yī / yì ／yí)些不(bù)必要(yào / yāo)的(de) I/O 操作，操作速率很快。

高效的(de)數據結構

• 底層多種數據結構支持不(bù)同的(de)數據類型，支持 Redis 存儲不(bù)同的(de)數據；

• 不(bù)同數據結構的(de)設計，使得數據存儲時(shí)間複雜度降到(dào)最低。

合理的(de)數據編碼

• 根據字符串的(de)長度及元素的(de)個(gè)數适配不(bù)同的(de)編碼格式。

合适的(de)線程模型

• I/O 多路複用模型同時(shí)監聽客戶端連接；

• 單線程在(zài)執行過程中不(bù)需要(yào / yāo)進行上(shàng)下文切換，減少了(le／liǎo)耗時(shí)。