作者|萊烏

作爲一名服務端工程師，工作中你肯定和 Redis 打過(guò)交道(dào)。Redis 爲什麼(me)快，這(zhè)點想必你也知道(dào)，至少爲了面(miàn)試也做過(guò)準備。很多人知道(dào) Redis 快僅僅因爲它是基于内存實現的，對(duì)于其它原因倒是模棱兩(liǎng)可。

那麼(me)今天就(jiù)和小萊一起(qǐ)看看：

 - 思維導圖 -

基于内存實現

這(zhè)點在一開(kāi)始就(jiù)提到過(guò)了，這(zhè)裡(lǐ)再簡單說(shuō)說(shuō)。

Redis 是基于内存的數據庫，那不可避免的就(jiù)要與磁盤數據庫做對(duì)比。對(duì)于磁盤數據庫來說(shuō)，是需要將(jiāng)數據讀取到内存裡(lǐ)的，這(zhè)個過(guò)程會(huì)受到磁盤 I/O 的限制。

而對(duì)于内存數據庫來說(shuō)，本身數據就(jiù)存在于内存裡(lǐ)，也就(jiù)沒(méi)有了這(zhè)方面(miàn)的開(kāi)銷。

高效的數據結構

Redis 中有多種(zhǒng)數據類型，每種(zhǒng)數據類型的底層都(dōu)由一種(zhǒng)或多種(zhǒng)數據結構來支持。正是因爲有了這(zhè)些數據結構，Redis 在存儲與讀取上的速度才不受阻礙。這(zhè)些數據結構有什麼(me)特别的地方，各位看官接著(zhe)往下看：

1、簡單動态字符串

這(zhè)個名詞可能(néng)你不熟悉，換成(chéng) SDS 肯定就(jiù)知道(dào)了。這(zhè)是用來處理字符串的。了解 C 語言的都(dōu)知道(dào)，它是有處理字符串方法的。而 Redis 就(jiù)是 C 語言實現的，那爲什麼(me)還(hái)要重複造輪子？我們從以下幾點來看：

（1）字符串長(cháng)度處理

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

  Redis 中怎麼(me)操作呢？用一個 len 字段記錄當前字符串的長(cháng)度。想要獲取長(cháng)度隻需要獲取 len 字段即可。你看，差距不言自明。前者遍曆的時(shí)間複雜度爲 O(n)，Redis 中 O(1) 就(jiù)能(néng)拿到，速度明顯提升。

（2）内存重新分配

C 語言中涉及到修改字符串的時(shí)候會(huì)重新分配内存。修改地越頻繁，内存分配也就(jiù)越頻繁。而内存分配是會(huì)消耗性能(néng)的，那麼(me)性能(néng)下降在所難免。

而 Redis 中會(huì)涉及到字符串頻繁的修改操作，這(zhè)種(zhǒng)内存分配方式顯然就(jiù)不适合了。于是 SDS 實現了兩(liǎng)種(zhǒng)優化策略：

• 空間預分配

對(duì) SDS 修改及空間擴充時(shí)，除了分配所必須的空間外，還(hái)會(huì)額外分配未使用的空間。

具體分配規則是這(zhè)樣(yàng)的：SDS 修改後(hòu)，len 長(cháng)度小于 1M，那麼(me)將(jiāng)會(huì)額外分配與 len 相同長(cháng)度的未使用空間。如果修改後(hòu)長(cháng)度大于 1M，那麼(me)將(jiāng)分配1M的使用空間。

• 惰性空間釋放

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

SDS 縮短時(shí)，并不會(huì)回收多餘的内存空間，而是使用 free 字段將(jiāng)多出來的空間記錄下來。如果後(hòu)續有變更操作，直接使用 free 中記錄的空間，減少了内存的分配。

（3）二進(jìn)制安全

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

前面(miàn)我們提到過(guò)，C 中字符串遇到 '\0' 會(huì)結束，那 '\0' 之後(hòu)的數據就(jiù)讀取不上了。但在 SDS 中，是根據 len 長(cháng)度來判斷字符串結束的。

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

2、雙端鏈表

列表 List 更多是被(bèi)當作隊列或棧來使用的。隊列和棧的特性一個先進(jìn)先出，一個先進(jìn)後(hòu)出。雙端鏈表很好(hǎo)的支持了這(zhè)些特性。

 - 雙端鏈表 -

（1）前後(hòu)節點

 鏈表裡(lǐ)每個節點都(dōu)帶有兩(liǎng)個指針，prev 指向(xiàng)前節點，next 指向(xiàng)後(hòu)節點。這(zhè)樣(yàng)在時(shí)間複雜度爲 O(1) 内就(jiù)能(néng)獲取到前後(hòu)節點。

（2）頭尾節點

 你可能(néng)注意到了，頭節點裡(lǐ)有 head 和 tail 兩(liǎng)個參數，分别指向(xiàng)頭節點和尾節點。這(zhè)樣(yàng)的設計能(néng)夠對(duì)雙端節點的處理時(shí)間複雜度降至 O(1) ，對(duì)于隊列和棧來說(shuō)再适合不過(guò)。同時(shí)鏈表叠代時(shí)從兩(liǎng)端都(dōu)可以進(jìn)行。

（3）鏈表長(cháng)度

頭節點裡(lǐ)同時(shí)還(hái)有一個參數 len，和上邊提到的 SDS 裡(lǐ)類似，這(zhè)裡(lǐ)是用來記錄鏈表長(cháng)度的。因此獲取鏈表長(cháng)度時(shí)不用再遍曆整個鏈表，直接拿到 len 值就(jiù)可以了，這(zhè)個時(shí)間複雜度是 O(1)。

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

3、壓縮列表

雙端鏈表我們已經(jīng)熟悉了。不知道(dào)你有沒(méi)有注意到一個問題：如果在一個鏈表節點中存儲一個小數據，比如一個字節。那麼(me)對(duì)應的就(jiù)要保存頭節點，前後(hòu)指針等額外的數據。

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

于是，壓縮列表上場了！

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

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

4、字典

Redis 作爲 K-V 型數據庫，所有的鍵值都(dōu)是用字典來存儲的。

日常學(xué)習中使用的字典你應該不會(huì)陌生，想查找某個詞通過(guò)某個字就(jiù)可以直接定位到，速度非常快。這(zhè)裡(lǐ)所說(shuō)的字典原理上是一樣(yàng)的，通過(guò)某個 key 可以直接獲取到對(duì)應的value。

字典又稱爲哈希表，這(zhè)點沒(méi)什麼(me)可說(shuō)的。哈希表的特性大家都(dōu)很清楚，能(néng)夠在 O(1) 時(shí)間複雜度内取出和插入關聯的值。

5、跳躍表

作爲 Redis 中特有的數據結構-跳躍表，其在鏈表的基礎上增加了多級索引來提升查找效率。

 這(zhè)是跳躍表的簡單原理圖，每一層都(dōu)有一條有序的鏈表，最底層的鏈表包含了所有的元素。這(zhè)樣(yàng)跳躍表就(jiù)可以支持在 O(logN) 的時(shí)間複雜度裡(lǐ)查找到對(duì)應的節點。

下面(miàn)這(zhè)張是跳表真實的存儲結構，和其它數據結構一樣(yàng)，都(dōu)在頭節點裡(lǐ)記錄了相應的信息，減少了一些不必要的系統開(kāi)銷。

 合理的數據編碼

對(duì)于每一種(zhǒng)數據類型來說(shuō)，底層的支持可能(néng)是多種(zhǒng)數據結構，什麼(me)時(shí)候使用哪種(zhǒng)數據結構，這(zhè)就(jiù)涉及到了編碼轉化的問題。

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

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

List：字符串長(cháng)度及元素個數小于一定範圍使用 ziplist 編碼，任意條件不滿足，則轉化爲 linkedlist 編碼；

Hash：hash 對(duì)象保存的鍵值對(duì)内的鍵和值字符串長(cháng)度小于一定值及鍵值對(duì)；

Set：保存元素爲整數及元素個數小于一定範圍使用 intset 編碼，任意條件不滿足，則使用 hashtable 編碼；

Zset：zset 對(duì)象中保存的元素個數小于及成(chéng)員長(cháng)度小于一定值使用 ziplist 編碼，任意條件不滿足，則使用 skiplist 編碼。

合适的線程模型

Redis 快的原因還(hái)有一個是因爲使用了合适的線程模型：

1、I/O多路複用模型

• I/O ：網絡 I/O

• 多路：多個 TCP 連接

• 複用：共用一個線程或進(jìn)程

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

 應對(duì)大量的請求，Redis 中使用 I/O 多路複用程序同時(shí)監聽多個套接字，并將(jiāng)這(zhè)些事(shì)件推送到一個隊列裡(lǐ)，然後(hòu)逐個被(bèi)執行。最終將(jiāng)結果返回給客戶端。

2、避免上下文切換

你一定聽說(shuō)過(guò)，Redis 是單線程的。那麼(me)單線程的 Redis 爲什麼(me)會(huì)快呢？

因爲多線程在執行過(guò)程中需要進(jìn)行 CPU 的上下文切換，這(zhè)個操作比較耗時(shí)。Redis 又是基于内存實現的，對(duì)于内存來說(shuō)，沒(méi)有上下文切換效率就(jiù)是最高的。多次讀寫都(dōu)在一個CPU 上，對(duì)于内存來說(shuō)就(jiù)是最佳方案。

3、單線程模型

順便提一下，爲什麼(me) Redis 是單線程的。

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

這(zhè)張圖裡(lǐ)，接收到用戶的請求後(hòu)，全部推送到一個隊列裡(lǐ)，然後(hòu)交給文件事(shì)件分派器，而它是單線程的工作方式。Redis 又是基于它工作的，所以說(shuō) Redis 是單線程的。

 
總結

基于内存實現

• 數據都(dōu)存儲在内存裡(lǐ)，減少了一些不必要的 I/O 操作，操作速率很快。

高效的數據結構

• 底層多種(zhǒng)數據結構支持不同的數據類型，支持 Redis 存儲不同的數據；

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

合理的數據編碼

• 根據字符串的長(cháng)度及元素的個數适配不同的編碼格式。

合适的線程模型

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

• 單線程在執行過(guò)程中不需要進(jìn)行上下文切換，減少了耗時(shí)。