Redis 為什麼那麼快？

除了它是內存資料庫，使得所有的操作都在內存上進行之外，還有一個重要因素，它實現的數據結構，使得我們對數據進行增刪查改操作時，redis 能高效的處理。

因此，這次我們就來好好聊一下 Redis 數據結構，這個在面試中太常問了。

注意，Redis 數據結構並不是指 String（字符串）對象、List（列表）對象、Hash（哈希）對象、Set（集合）對象和 Zset（有序集合）對象，因為這些是 Redis 鍵值對中值的數據類型，也就是數據的保存形式，這些對象的底層實現的方式就用到了數據結構。

我畫了一張 Redis 數據類型（也叫 Redis 對象）和底層數據結構的對應關圖，左邊是 Redis 3.0版本的，也就是《Redis 設計與實現》這本書講解的版本，現在看還是有點過時了，右邊是現在 Github 最新的 Redis 代碼的（還未發布正式版本）。

可以看到，Redis 數據類型的底層數據結構隨著版本的更新也有所不同，比如：

• 在 Redis 3.0 版本中 List 對象的底層數據結構由「雙向鍊表」或「壓縮表列表」實現，但是在 3.2 版本之後，List 數據類型底層數據結構是由 quicklist 實現的；
• 在最新的 Redis 代碼（還未發布正式版本）中，壓縮列表數據結構已經廢棄了，交由 listpack 數據結構來實現了。

這次，把新舊版本的數據結構說圖解一遍，共有 9 種數據結構：sds、雙向鍊表、壓縮列表、哈希表、跳表、整數集合、quicklist、listpack。

不多 BB 了，直接發車！

鍵值對資料庫是怎麼實現的？

在開始講數據結構之前，先給介紹下 Redis 是怎樣實現鍵值對（key-value）資料庫的。

Redis 的鍵值對中的 key 就是字符串對象，而 value 可以是字符串對象，也可以是集合數據類型的對象，比如 List 對象、Hash 對象、Set 對象和 Zset 對象。

舉個例子，我這裡列出幾種 Redis 新增鍵值對的命令：

> SET name "xiaolincoding"
OK

> HSET person name "xiaolincoding" age 18
0

> RPUSH stu "xiaolin" "xiaomei"
(integer) 4

這些命令代表著：

• 第一條命令：name 是一個字符串鍵，因為鍵的值是一個字符串對象；
• 第二條命令：person 是一個哈希表鍵，因為鍵的值是一個包含兩個鍵值對的哈希表對象；
• 第三條命令：stu 是一個列表鍵，因為鍵的值是一個包含兩個元素的列表對象；

這些鍵值對是如何保存在 Redis 中的呢？

Redis 是使用了一個「哈希表」保存所有鍵值對，哈希表的最大好處就是讓我們可以用 O(1) 的時間複雜度來快速查找到鍵值對。哈希表其實就是一個數組，數組中的元素叫做哈希桶。

Redis 的哈希桶是怎麼保存鍵值對數據的呢？

哈希桶存放的是指向鍵值對數據的指針（dictEntry*），這樣通過指針就能找到鍵值對數據，然後因為鍵值對的值可以保存字符串對象和集合數據類型的對象，所以鍵值對的數據結構中並不是直接保存值本身，而是保存了 void * key 和 void * value 指針，分別指向了實際的鍵對象和值對象，這樣一來，即使值是集合數據，也可以通過 void * value 指針找到。

我這裡畫了一張 Redis 保存鍵值對所涉及到的數據結構。

這些數據結構的內部細節，我先不展開講，後面在講哈希表數據結構的時候，在詳細的說說，因為用到的數據結構是一樣的。這裡先大概說下圖中涉及到的數據結構的名字和用途：

• redisDb 結構，表示 Redis 資料庫的結構，結構體裡存放了指向了 dict 結構的指針；
• dict 結構，結構體裡存放了 2 個哈希表，正常情況下都是用「哈希表1」，「哈希表2」只有在 rehash 的時候才用，具體什麼是 rehash，我在本文的哈希表數據結構會講；
• ditctht 結構，表示哈希表的結構，結構里存放了哈希表數組，數組中的每個元素都是指向一個哈希表節點結構（dictEntry）的指針；
• dictEntry 結構，表示哈希表節點的結構，結構里存放了 void * key 和 void * value 指針， *key 指向的是 String 對象，而 *value 則可以指向 String 對象，也可以指向集合類型的對象，比如 List 對象、Hash 對象、Set 對象和 Zset 對象。

特別說明下，void * key 和 void * value 指針指向的是 Redis 對象，Redis 中的每個對象都由 redisObject 結構表示，如下圖：

對象結構里包含的成員變量：

• type，標識該對象是什麼類型的對象（String 對象、 List 對象、Hash 對象、Set 對象和 Zset 對象）；
• encoding，標識該對象使用了哪種底層的數據結構；
• ptr，指向底層數據結構的指針。

我畫了一張 Redis 鍵值對資料庫的全景圖，你就能清晰知道 Redis 對象和數據結構的關係了：

接下里，就好好聊一下底層數據結構！

SDS

字符串在 Redis 中是很常用的，鍵值對中的鍵是字符串類型，值有時也是字符串類型。

Redis 是用 C 語言實現的，但是它沒有直接使用 C 語言的 char* 字符數組來實現字符串，而是自己封裝了一個名為簡單動態字符串（simple dynamic string，SDS） 的數據結構來表示字符串，也就是 Redis 的 String 數據類型的底層數據結構是 SDS。

既然 Redis 設計了 SDS 結構來表示字符串，肯定是 C 語言的 char* 字符數組存在一些缺陷。

要了解這一點，得先來看看 char* 字符數組的結構。

C 語言字符串的缺陷

C 語言的字符串其實就是一個字符數組，即數組中每個元素是字符串中的一個字符。

比如，下圖就是字符串「xiaolin」的 char* 字符數組的結構：

沒學過 C 語言的同學，可能會好奇為什麼最後一個字符是「\0」？

在 C 語言裡，對字符串操作時，char * 指針只是指向字符數組的起始位置，而字符數組的結尾位置就用「\0」表示，意思是指字符串的結束。

因此，C 語言標準庫中的字符串操作函數就通過判斷字符是不是 「\0」 來決定要不要停止操作，如果當前字符不是 「\0」 ，說明字符串還沒結束，可以繼續操作，如果當前字符是 「\0」 是則說明字符串結束了，就要停止操作。

舉個例子，C 語言獲取字符串長度的函數 strlen，就是通過字符數組中的每一個字符，並進行計數，等遇到字符為 「\0」 後，就會停止遍歷，然後返回已經統計到的字符個數，即為字符串長度。下圖顯示了 strlen 函數的執行流程：

很明顯，C 語言獲取字符串長度的時間複雜度是 O（N）（這是一個可以改進的地方）

C 語言字符串用 「\0」 字符作為結尾標記有個缺陷。假設有個字符串中有個 「\0」 字符，這時在操作這個字符串時就會提早結束，比如 「xiao\0lin」 字符串，計算字符串長度的時候則會是 4，如下圖：

因此，除了字符串的末尾之外，字符串裡面不能含有 「\0」 字符，否則最先被程序讀入的 「\0」 字符將被誤認為是字符串結尾，這個限制使得 C 語言的字符串只能保存文本數據，不能保存像圖片、音頻、視頻文化這樣的二進位數據（這也是一個可以改進的地方）

另外， C 語言標準庫中字符串的操作函數是很不安全的，對程式設計師很不友好，稍微一不注意，就會導致緩衝區溢出。

舉個例子，strcat 函數是可以將兩個字符串拼接在一起。

c //將 src 字符串拼接到 dest 字符串後面 char *strcat(char *dest, const char* src);

C 語言的字符串是不會記錄自身的緩衝區大小的，所以 strcat 函數假定程式設計師在執行這個函數時，已經為 dest 分配了足夠多的內存，可以容納 src 字符串中的所有內容，而一旦這個假定不成立，就會發生緩衝區溢出將可能會造成程序運行終止，（這是一個可以改進的地方）。

而且，strcat 函數和 strlen 函數類似，時間複雜度也很高，也都需要先通過遍歷字符串才能得到目標字符串的末尾。然後對於 strcat 函數來說，還要再遍歷源字符串才能完成追加，對字符串的操作效率不高。

好了， 通過以上的分析，我們可以得知 C 語言的字符串不足之處以及可以改進的地方：

• 獲取字符串長度的時間複雜度為 O（N）；
• 字符串的結尾是以 「\0」 字符標識，字符串裡面不能包含有 「\0」 字符，因此不能保存二進位數據；
• 字符串操作函數不高效且不安全，比如有緩衝區溢出的風險，有可能會造成程序運行終止；

Redis 實現的 SDS 的結構就把上面這些問題解決了，接下來我們一起看看 Redis 是如何解決的。

SDS 結構設計

下圖就是 Redis 5.0 的 SDS 的數據結構：

結構中的每個成員變量分別介紹下：

• len，記錄了字符串長度。這樣獲取字符串長度的時候，只需要返回這個成員變量值就行，時間複雜度只需要 O（1）。
• alloc，分配給字符數組的空間長度。這樣在修改字符串的時候，可以通過 alloc - len 計算出剩餘的空間大小，可以用來判斷空間是否滿足修改需求，如果不滿足的話，就會自動將 SDS 的空間擴展至執行修改所需的大小，然後才執行實際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現前面所說的緩衝區溢出的問題。
• flags，用來表示不同類型的 SDS。一共設計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，後面在說明區別之處。
• buf[]，字符數組，用來保存實際數據。不僅可以保存字符串，也可以保存二進位數據。

總的來說，Redis 的 SDS 結構在原本字符數組之上，增加了三個元數據：len、alloc、flags，用來解決 C 語言字符串的缺陷。

O（1）複雜度獲取字符串長度

C 語言的字符串長度獲取 strlen 函數，需要通過遍歷的方式來統計字符串長度，時間複雜度是 O（N）。

而 Redis 的 SDS 結構因為加入了 len 成員變量，那麼獲取字符串長度的時候，直接返回這個成員變量的值就行，所以複雜度只有 O（1）。

二進位安全

因為 SDS 不需要用 「\0」 字符來標識字符串結尾了，而是有個專門的 len 成員變量來記錄長度，所以可存儲包含 「\0」 的數據。但是 SDS 為了兼容部分 C 語言標準庫的函數， SDS 字符串結尾還是會加上 「\0」 字符。

因此， SDS 的 API 都是以處理二進位的方式來處理 SDS 存放在 buf[] 里的數據，程序不會對其中的數據做任何限制，數據寫入的時候時什麼樣的，它被讀取時就是什麼樣的。

通過使用二進位安全的 SDS，而不是 C 字符串，使得 Redis 不僅可以保存文本數據，也可以保存任意格式的二進位數據。

不會發生緩衝區溢出

C 語言的字符串標準庫提供的字符串操作函數，大多數（比如 strcat 追加字符串函數）都是不安全的，因為這些函數把緩衝區大小是否滿足操作需求的工作交由開發者來保證，程序內部並不會判斷緩衝區大小是否足夠用，當發生了緩衝區溢出就有可能造成程序異常結束。

所以，Redis 的 SDS 結構里引入了 alloc 和 len 成員變量，這樣 SDS API 通過 alloc - len 計算，可以算出剩餘可用的空間大小，這樣在對字符串做修改操作的時候，就可以由程序內部判斷緩衝區大小是否足夠用。

而且，當判斷出緩衝區大小不夠用時，Redis 會自動將擴大 SDS 的空間大小（小於 1MB 翻倍擴容，大於 1MB 按 1MB 擴容），以滿足修改所需的大小。

在擴展 SDS 空間之前，SDS API 會優先檢查未使用空間是否足夠，如果不夠的話，API 不僅會為 SDS 分配修改所必須要的空間，還會給 SDS 分配額外的「未使用空間」。

這樣的好處是，下次在操作 SDS 時，如果 SDS 空間夠的話，API 就會直接使用「未使用空間」，而無須執行內存分配，有效的減少內存分配次數。

所以，使用 SDS 即不需要手動修改 SDS 的空間大小，也不會出現緩衝區溢出的問題。

節省內存空間

SDS 結構中有個 flags 成員變量，表示的是 SDS 類型。

Redos 一共設計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。

這 5 種類型的主要區別就在於，它們數據結構中的 len 和 alloc 成員變量的數據類型不同。

比如 sdshdr16 和 sdshdr32 這兩個類型，它們的定義分別如下：

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};


struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc; 
    unsigned char flags;
    char buf[];
};

可以看到：

• sdshdr16 類型的 len 和 alloc 的數據類型都是 uint16_t，表示字符數組長度和分配空間大小不能超過 2 的 16 次方。
• sdshdr32 則都是 uint32_t，表示表示字符數組長度和分配空間大小不能超過 2 的 32 次方。

之所以 SDS 設計不同類型的結構體，是為了能靈活保存不同大小的字符串，從而有效節省內存空間。比如，在保存小字符串時，結構頭占用空間也比較少。

除了設計不同類型的結構體，Redis 在編程上還使用了專門的編譯優化來節省內存空間，即在 struct 聲明了 __attribute__ ((packed)) ，它的作用是：告訴編譯器取消結構體在編譯過程中的優化對齊，按照實際占用字節數進行對齊。

比如，sdshdr16 類型的 SDS，默認情況下，編譯器會按照 16 字節對齊的方式給變量分配內存，這意味著，即使一個變量的大小不到 16 個字節，編譯器也會給它分配 16 個字節。

舉個例子，假設下面這個結構體，它有兩個成員變量，類型分別是 char 和 int，如下所示：

#include <stdio.h>

 struct test1 {
    char a;
    int b;
 } test1;

int main() {
     printf("%lu\n", sizeof(test1));
     return 0;
}

大家猜猜這個結構體大小是多少？我先直接說答案，這個結構體大小計算出來是 8。

這是因為默認情況下，編譯器是使用「字節對齊」的方式分配內存，雖然 char 類型只占一個字節，但是由於成員變量里有 int 類型，它占用了 4 個字節，所以在成員變量為 char 類型分配內存時，會分配 4 個字節，其中這多餘的 3 個字節是為了字節對齊而分配的，相當於有 3 個字節被浪費掉了。

如果不想編譯器使用字節對齊的方式進行分配內存，可以採用了 __attribute__ ((packed)) 屬性定義結構體，這樣一來，結構體實際占用多少內存空間，編譯器就分配多少空間。

比如，我用 __attribute__ ((packed)) 屬性定義下面的結構體 ，同樣包含 char 和 int 兩個類型的成員變量，代碼如下所示：

#include <stdio.h>

struct __attribute__((packed)) test2  {
    char a;
    int b;
 } test2;

int main() {
     printf("%lu\n", sizeof(test2));
     return 0;
}

這時列印的結果是 5（1 個字節 char + 4 字節 int）。

可以看得出，這是按照實際占用字節數進行分配內存的，這樣可以節省內存空間。

---

鍊表

大家最熟悉的數據結構除了數組之外，我相信就是鍊表了。

Redis 的 List 對象的底層實現之一就是鍊表。C 語言本身沒有鍊表這個數據結構的，所以 Redis 自己設計了一個鍊表數據結構。

鍊表節點結構設計

先來看看「鍊表節點」結構的樣子：

typedef struct listNode {
    //前置節點
    struct listNode *prev;
    //後置節點
    struct listNode *next;
    //節點的值
    void *value;
} listNode;

有前置節點和後置節點，可以看的出，這個是一個雙向鍊表。

鍊表結構設計

不過，Redis 在 listNode 結構體基礎上又封裝了 list 這個數據結構，這樣操作起來會更方便，鍊表結構如下：

typedef struct list {
    //鍊表頭節點
    listNode *head;
    //鍊表尾節點
    listNode *tail;
    //節點值複製函數
    void *(*dup)(void *ptr);
    //節點值釋放函數
    void (*free)(void *ptr);
    //節點值比較函數
    int (*match)(void *ptr, void *key);
    //鍊表節點數量
    unsigned long len;
} list;

list 結構為鍊表提供了鍊表頭指針 head、鍊表尾節點 tail、鍊表節點數量 len、以及可以自定義實現的 dup、free、match 函數。

舉個例子，下面是由 list 結構和 3 個 listNode 結構組成的鍊表。

鍊表的優勢與缺陷

Redis 的鍊表實現優點如下：

• listNode 鍊表節點的結構裡帶有 prev 和 next 指針，獲取某個節點的前置節點或後置節點的時間複雜度只需O(1)，而且這兩個指針都可以指向 NULL，所以鍊表是無環鍊表；
• list 結構因為提供了表頭指針 head 和表尾節點 tail，所以獲取鍊表的表頭節點和表尾節點的時間複雜度只需O(1)；
• list 結構因為提供了鍊表節點數量 len，所以獲取鍊表中的節點數量的時間複雜度只需O(1)；
• listNode 鍊表節使用 void* 指針保存節點值，並且可以通過 list 結構的 dup、free、match 函數指針為節點設置該節點類型特定的函數，因此鍊表節點可以保存各種不同類型的值；

鍊表的缺陷也是有的：

• 鍊表每個節點之間的內存都是不連續的，意味著無法很好利用 CPU 緩存。能很好利用 CPU 緩存的數據結構就是數組，因為數組的內存是連續的，這樣就可以充分利用 CPU 緩存來加速訪問。
• 還有一點，保存一個鍊表節點的值都需要一個鍊表節點結構頭的分配，內存開銷較大。

因此，Redis 3.0 的 List 對象在數據量比較少的情況下，會採用「壓縮列表」作為底層數據結構的實現，它的優勢是節省內存空間，並且是內存緊湊型的數據結構。

不過，壓縮列表存在性能問題（具體什麼問題，下面會說），所以 Redis 在 3.2 版本設計了新的數據結構 quicklist，並將 List 對象的底層數據結構改由 quicklist 實現。

然後在 Redis 5.0 設計了新的數據結構 listpack，沿用了壓縮列表緊湊型的內存布局，最終在最新的 Redis 版本，將 Hash 對象和 Zset 對象的底層數據結構實現之一的壓縮列表，替換成由 listpack 實現。

---

壓縮列表

壓縮列表的最大特點，就是它被設計成一種內存緊湊型的數據結構，占用一塊連續的內存空間，不僅可以利用 CPU 緩存，而且會針對不同長度的數據，進行相應編碼，這種方法可以有效地節省內存開銷。

但是，壓縮列表的缺陷也是有的：

• 不能保存過多的元素，否則查詢效率就會降低；
• 新增或修改某個元素時，壓縮列表占用的內存空間需要重新分配，甚至可能引發連鎖更新的問題。

因此，Redis 對象（List 對象、Hash 對象、Zset 對象）包含的元素數量較少，或者元素值不大的情況才會使用壓縮列表作為底層數據結構。

接下來，就跟大家詳細聊下壓縮列表。

壓縮列表結構設計

壓縮列表是 Redis 為了節約內存而開發的，它是由連續內存塊組成的順序型數據結構，有點類似於數組。

壓縮列表在表頭有三個欄位：

• zlbytes，記錄整個壓縮列表占用對內存字節數；
• zltail，記錄壓縮列表「尾部」節點距離起始地址由多少字節，也就是列表尾的偏移量；
• zllen，記錄壓縮列表包含的節點數量；
• zlend，標記壓縮列表的結束點，固定值 0xFF（十進位255）。

在壓縮列表中，如果我們要查找定位第一個元素和最後一個元素，可以通過表頭三個欄位的長度直接定位，複雜度是 O(1)。而查找其他元素時，就沒有這麼高效了，只能逐個查找，此時的複雜度就是 O(N) 了，因此壓縮列表不適合保存過多的元素。

另外，壓縮列表節點（entry）的構成如下：

壓縮列表節點包含三部分內容：

• prevlen，記錄了「前一個節點」的長度；
• encoding，記錄了當前節點實際數據的類型以及長度；
• data，記錄了當前節點的實際數據；

當我們往壓縮列表中插入數據時，壓縮列表就會根據數據是字符串還是整數，以及數據的大小，會使用不同空間大小的 prevlen 和 encoding 這兩個元素里保存的信息，這種根據數據大小和類型進行不同的空間大小分配的設計思想，正是 Redis 為了節省內存而採用的。

分別說下，prevlen 和 encoding 是如何根據數據的大小和類型來進行不同的空間大小分配。

壓縮列表里的每個節點中的 prevlen 屬性都記錄了「前一個節點的長度」，而且 prevlen 屬性的空間大小跟前一個節點長度值有關，比如：

• 如果前一個節點的長度小於 254 字節，那麼 prevlen 屬性需要用 1 字節的空間來保存這個長度值；
• 如果前一個節點的長度大於等於 254 字節，那麼 prevlen 屬性需要用 5 字節的空間來保存這個長度值；

encoding 屬性的空間大小跟數據是字符串還是整數，以及字符串的長度有關：

• 如果當前節點的數據是整數，則 encoding 會使用 1 字節的空間進行編碼。
• 如果當前節點的數據是字符串，根據字符串的長度大小，encoding 會使用 1 字節/2位元組/5位元組的空間進行編碼。

連鎖更新

壓縮列表除了查找複雜度高的問題，還有一個問題。

壓縮列表新增某個元素或修改某個元素時，如果空間不不夠，壓縮列表占用的內存空間就需要重新分配。而當新插入的元素較大時，可能會導致後續元素的 prevlen 占用空間都發生變化，從而引起「連鎖更新」問題，導致每個元素的空間都要重新分配，造成訪問壓縮列表性能的下降。

前面提到，壓縮列表節點的 prevlen 屬性會根據前一個節點的長度進行不同的空間大小分配：

• 如果前一個節點的長度小於 254 字節，那麼 prevlen 屬性需要用 1 字節的空間來保存這個長度值；
• 如果前一個節點的長度大於等於 254 字節，那麼 prevlen 屬性需要用 5 字節的空間來保存這個長度值；

現在假設一個壓縮列表中有多個連續的、長度在 250～253 之間的節點，如下圖：

因為這些節點長度值小於 254 字節，所以 prevlen 屬性需要用 1 字節的空間來保存這個長度值。

這時，如果將一個長度大於等於 254 字節的新節點加入到壓縮列表的表頭節點，即新節點將成為 e1 的前置節點，如下圖：

因為 e1 節點的 prevlen 屬性只有 1 個字節大小，無法保存新節點的長度，此時就需要對壓縮列表的空間重分配操作，並將 e1 節點的 prevlen 屬性從原來的 1 字節大小擴展為 5 字節大小。

多米諾牌的效應就此開始。

e1 原本的長度在 250～253 之間，因為剛才的擴展空間，此時 e1 的長度就大於等於 254 了，因此原本 e2 保存 e1 的 prevlen 屬性也必須從 1 字節擴展至 5 字節大小。

正如擴展 e1 引發了對 e2 擴展一樣，擴展 e2 也會引發對 e3 的擴展，而擴展 e3 又會引發對 e4 的擴展…. 一直持續到結尾。

這種在特殊情況下產生的連續多次空間擴展操作就叫做「連鎖更新」，就像多米諾牌的效應一樣，第一張牌倒下了，推動了第二張牌倒下；第二張牌倒下，又推動了第三張牌倒下….，

壓縮列表的缺陷

空間擴展操作也就是重新分配內存，因此連鎖更新一旦發生，就會導致壓縮列表占用的內存空間要多次重新分配，這就會直接影響到壓縮列表的訪問性能。

所以說，雖然壓縮列表緊湊型的內存布局能節省內存開銷，但是如果保存的元素數量增加了，或是元素變大了，會導致內存重新分配，最糟糕的是會有「連鎖更新」的問題。

因此，壓縮列表只會用於保存的節點數量不多的場景，只要節點數量足夠小，即使發生連鎖更新，也是能接受的。

雖說如此，Redis 針對壓縮列表在設計上的不足，在後來的版本中，新增設計了兩種數據結構：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。這兩種數據結構的設計目標，就是儘可能地保持壓縮列表節省內存的優勢，同時解決壓縮列表的「連鎖更新」的問題。

哈希表

哈希表是一種保存鍵值對（key-value）的數據結構。

哈希表中的每一個 key 都是獨一無二的，程序可以根據 key 查找到與之關聯的 value，或者通過 key 來更新 value，又或者根據 key 來刪除整個 key-value等等。

在講壓縮列表的時候，提到過 Redis 的 Hash 對象的底層實現之一是壓縮列表（最新 Redis 代碼已將壓縮列表替換成 listpack）。Hash 對象的另外一個底層實現就是哈希表。

哈希表優點在於，它能以 O(1) 的複雜度快速查詢數據。怎麼做到的呢？將 key 通過 Hash 函數的計算，就能定位數據在表中的位置，因為哈希表實際上是數組，所以可以通過索引值快速查詢到數據。

但是存在的風險也是有，在哈希表大小固定的情況下，隨著數據不斷增多，那麼哈希衝突的可能性也會越高。

解決哈希衝突的方式，有很多種。

Redis 採用了「鏈式哈希」來解決哈希衝突，在不擴容哈希表的前提下，將具有相同哈希值的數據串起來，形成連結起，以便這些數據在表中仍然可以被查詢到。

接下來，詳細說說哈希表。

哈希表結構設計

Redis 的哈希表結構如下：

typedef struct dictht {
    //哈希表數組
    dictEntry **table;
    //哈希表大小
    unsigned long size;  
    //哈希表大小掩碼，用於計算索引值
    unsigned long sizemask;
    //該哈希表已有的節點數量
    unsigned long used;
} dictht;

可以看到，哈希表是一個數組（dictEntry **table），數組的每個元素是一個指向「哈希表節點（dictEntry）」的指針。

哈希表節點的結構如下：

typedef struct dictEntry {
    //鍵值對中的鍵
    void *key;

    //鍵值對中的值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //指向下一個哈希表節點，形成鍊表
    struct dictEntry *next;
} dictEntry;

dictEntry 結構里不僅包含指向鍵和值的指針，還包含了指向下一個哈希表節點的指針，這個指針可以將多個哈希值相同的鍵值對連結起來，以此來解決哈希衝突的問題，這就是鏈式哈希。

另外，這裡還跟你提一下，dictEntry 結構里鍵值對中的值是一個「聯合體 v」定義的，因此，鍵值對中的值可以是一個指向實際值的指針，或者是一個無符號的 64 位整數或有符號的 64 位整數或double 類的值。這麼做的好處是可以節省內存空間，因為當「值」是整數或浮點數時，就可以將值的數據內嵌在 dictEntry 結構里，無需再用一個指針指向實際的值，從而節省了內存空間。

哈希衝突

哈希表實際上是一個數組，數組裡多每一個元素就是一個哈希桶。

當一個鍵值對的鍵經過 Hash 函數計算後得到哈希值，再將(哈希值 % 哈希表大小)取模計算，得到的結果值就是該 key-value 對應的數組元素位置，也就是第幾個哈希桶。

什麼是哈希衝突呢？

舉個例子，有一個可以存放 8 個哈希桶的哈希表。key1 經過哈希函數計算後，再將「哈希值 % 8 」進行取模計算，結果值為 1，那麼就對應哈希桶 1，類似的，key9 和 key10 分別對應哈希桶 1 和桶 6。

此時，key1 和 key9 對應到了相同的哈希桶中，這就發生了哈希衝突。

因此，當有兩個以上數量的 kay 被分配到了哈希表中同一個哈希桶上時，此時稱這些 key 發生了衝突。

鏈式哈希

Redis 採用了「鏈式哈希」的方法來解決哈希衝突。

鏈式哈希是怎麼實現的？

實現的方式就是每個哈希表節點都有一個 next 指針，用於指向下一個哈希表節點，因此多個哈希表節點可以用 next 指針構成一個單項鍊表，被分配到同一個哈希桶上的多個節點可以用這個單項鍊表連接起來，這樣就解決了哈希衝突。

還是用前面的哈希衝突例子，key1 和 key9 經過哈希計算後，都落在同一個哈希桶，鏈式哈希的話，key1 就會通過 next 指針指向 key9，形成一個單向鍊表。

不過，鏈式哈希局限性也很明顯，隨著鍊表長度的增加，在查詢這一位置上的數據的耗時就會增加，畢竟鍊表的查詢的時間複雜度是 O(n)。

要想解決這一問題，就需要進行 rehash，也就是對哈希表的大小進行擴展。

接下來，看看 Redis 是如何實現的 rehash 的。

rehash

哈希表結構設計的這一小節，我給大家介紹了 Redis 使用 dictht 結構體表示哈希表。不過，在實際使用哈希表時，Redis 定義一個 dict 結構體，這個結構體裡定義了兩個哈希表（ht[2]）。

typedef struct dict {
    …
    //兩個Hash表，交替使用，用於rehash操作
    dictht ht[2]; 
    …
} dict;

之所以定義了 2 個哈希表，是因為進行 rehash 的時候，需要用上 2 個哈希表了。

在正常服務請求階段，插入的數據，都會寫入到「哈希表 1」，此時的「哈希表 2 」 並沒有被分配空間。

隨著數據逐步增多，觸發了 rehash 操作，這個過程分為三步：

• 給「哈希表 2」 分配空間，一般會比「哈希表 1」 大 2 倍；
• 將「哈希表 1 」的數據遷移到「哈希表 2」 中；
• 遷移完成後，「哈希表 1 」的空間會被釋放，並把「哈希表 2」 設置為「哈希表 1」，然後在「哈希表 2」 新創建一個空白的哈希表，為下次 rehash 做準備。

為了方便你理解，我把 rehash 這三個過程畫在了下面這張圖：

這個過程看起來簡單，但是其實第二步很有問題，如果「哈希表 1 」的數據量非常大，那麼在遷移至「哈希表 2 」的時候，因為會涉及大量的數據拷貝，此時可能會對 Redis 造成阻塞，無法服務其他請求。

漸進式 rehash

為了避免 rehash 在數據遷移過程中，因拷貝數據的耗時，影響 Redis 性能的情況，所以 Redis 採用了漸進式 rehash，也就是將數據的遷移的工作不再是一次性遷移完成，而是分多次遷移。

漸進式 rehash 步驟如下：

• 給「哈希表 2」 分配空間；
• 在 rehash 進行期間，每次哈希表元素進行新增、刪除、查找或者更新操作時，Redis 除了會執行對應的操作之外，還會順序將「哈希表 1 」中索引位置上的所有 key-value 遷移到「哈希表 2」 上；
• 隨著處理客戶端發起的哈希表操作請求數量越多，最終在某個時間嗲呢，會把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。

這樣就巧妙地把一次性大量數據遷移工作的開銷，分攤到了多次處理請求的過程中，避免了一次性 rehash 的耗時操作。

在進行漸進式 rehash 的過程中，會有兩個哈希表，所以在漸進式 rehash 進行期間，哈希表元素的刪除、查找、更新等操作都會在這兩個哈希表進行。

比如，查找一個 key 的值的話，先會在「哈希表 1」 裡面進行查找，如果沒找到，就會繼續到哈希表 2 裡面進行找到。

另外，在漸進式 rehash 進行期間，新增一個 key-value 時，會被保存到「哈希表 2 」裡面，而「哈希表 1」 則不再進行任何添加操作，這樣保證了「哈希表 1 」的 key-value 數量只會減少，隨著 rehash 操作的完成，最終「哈希表 1 」就會變成空表。

rehash 觸發條件

介紹了 rehash 那麼多，還沒說什麼時情況下會觸發 rehash 操作呢？

rehash 的觸發條件跟負載因子（load factor）有關係。

負載因子可以通過下面這個公式計算：

觸發 rehash 操作的條件，主要有兩個：

• 當負載因子大於等於 1 ，並且 Redis 沒有在執行 bgsave 命令或者 bgrewiteaof 命令，也就是沒有執行 RDB 快照或沒有進行 AOF 重寫的時候，就會進行 rehash 操作。
• 當負載因子大於等於 5 時，此時說明哈希衝突非常嚴重了，不管有沒有有在執行 RDB 快照或 AOF 重寫，都會強制進行 rehash 操作。

整數集合

整數集合是 Set 對象的底層實現之一。當一個 Set 對象只包含整數值元素，並且元素數量不時，就會使用整數集這個數據結構作為底層實現。

整數集合結構設計

整數集合本質上是一塊連續內存空間，它的結構定義如下：

typedef struct intset {
    //編碼方式
    uint32_t encoding;
    //集合包含的元素數量
    uint32_t length;
    //保存元素的數組
    int8_t contents[];
} intset;

可以看到，保存元素的容器是一個 contents 數組，雖然 contents 被聲明為 int8_t 類型的數組，但是實際上 contents 數組並不保存任何 int8_t 類型的元素，contents 數組的真正類型取決於 intset 結構體裡的 encoding 屬性的值。比如：

• 如果 encoding 屬性值為 INTSET_ENC_INT16，那麼 contents 就是一個 int16_t 類型的數組，數組中每一個元素的類型都是 int16_t；
• 如果 encoding 屬性值為 INTSET_ENC_INT32，那麼 contents 就是一個 int32_t 類型的數組，數組中每一個元素的類型都是 int32_t；
• 如果 encoding 屬性值為 INTSET_ENC_INT64，那麼 contents 就是一個 int64_t 類型的數組，數組中每一個元素的類型都是 int64_t；

不同類型的 contents 數組，意味著數組的大小也會不同。

整數集合的升級操作

整數集合會有一個升級規則，就是當我們將一個新元素加入到整數集合裡面，如果新元素的類型（int32_t）比整數集合現有所有元素的類型（int16_t）都要長時，整數集合需要先進行升級，也就是按新元素的類型（int32_t）擴展 contents 數組的空間大小，然後才能將新元素加入到整數集合里，當然升級的過程中，也要維持整數集合的有序性。

整數集合升級的過程不會重新分配一個新類型的數組，而是在原本的數組上擴展空間，然後在將每個元素按間隔類型大小分割，如果 encoding 屬性值為 INTSET_ENC_INT16，則每個元素的間隔就是 16 位。

舉個例子，假設有一個整數集合里有 3 個類型為 int16_t 的元素。

現在，往這個整數集合中加入一個新元素 65535，這個新元素需要用 int32_t 類型來保存，所以整數集合要進行升級操作，首先需要為 contents 數組擴容，在原本空間的大小之上再擴容多 80 位（4x32-3x16=80），這樣就能保存下 4 個類型為 int32_t 的元素。

擴容完 contents 數組空間大小後，需要將之前的三個元素轉換為 int32_t 類型，並將轉換後的元素放置到正確的位上面，並且需要維持底層數組的有序性不變，整個轉換過程如下：

整數集合升級有什麼好處呢？

如果要讓一個數組同時保存 int16_t、int32_t、int64_t 類型的元素，最簡單做法就是直接使用 int64_t 類型的數組。不過這樣的話，當如果元素都是 int16_t 類型的，就會造成內存浪費的情況。

整數集合升級就能避免這種情況，如果一直向整數集合添加 int16_t 類型的元素，那麼整數集合的底層實現就一直是用 int16_t 類型的數組，只有在我們要將 int32_t 類型或 int64_t 類型的元素添加到集合時，才會對數組進行升級操作。

因此，整數集合升級的好處是節省內存資源。

整數集合支持降級操作嗎？

不支持降級操作，一旦對數組進行了升級，就會一直保持升級後的狀態。比如前面的升級操作的例子，如果刪除了 65535 元素，整數集合的數組還是 int32_t 類型的，並不會因此降級為 int16_t 類型。

---

跳表

Redis 只有在 Zset 對象的底層實現用到了跳表，跳表的優勢是能支持平均 O(logN) 複雜度的節點查找。

Zset 對象是唯一一個同時使用了兩個數據結構來實現的 Redis 對象，這兩個數據結構一個是跳表，一個是哈希表。這樣的好處是既能進行高效的範圍查詢，也能進行高效單點查詢。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

Zset 對象能支持範圍查詢（如 ZRANGEBYSCORE 操作），這是因為它的數據結構設計採用了跳表，而又能以常數複雜度獲取元素權重（如 ZSCORE 操作），這是因為它同時採用了哈希表進行索引。

接下來，詳細的說下跳表。

跳表結構設計

鍊表在查找元素的時候，因為需要逐一查找，所以查詢效率非常低，時間複雜度是O(N)，於是就出現了跳表。跳表是在鍊表基礎上改進過來的，實現了一種「多層」的有序鍊表，這樣的好處是能快讀定位數據。

那跳表長什麼樣呢？我這裡舉個例子，下圖展示了一個層級為 3 的跳表。

圖中頭節點有 L0~L2 三個頭指針，分別指向了不同層級的節點，然後每個層級的節點都通過指針連接起來：

• L0 層級共有 5 個節點，分別是節點1、2、3、4、5；
• L1 層級共有 3 個節點，分別是節點 2、3、5；
• L2 層級只有 1 個節點，也就是節點 3 。

如果我們要在鍊表中查找節點 4 這個元素，只能從頭開始遍歷鍊表，需要查找 4 次，而使用了跳表後，只需要查找 2 次就能定位到節點 4，因為可以在頭節點直接從 L2 層級跳到節點 3，然後再往前遍歷找到節點 4。

可以看到，這個查找過程就是在多個層級上跳來跳去，最後定位到元素。當數據量很大時，跳表的查找複雜度就是 O(logN)。

那跳表節點是怎麼實現多層級的呢？這就需要看「跳表節點」的數據結構了，如下：

typedef struct zskiplistNode {
    //Zset 對象的元素值
    sds ele;
    //元素權重值
    double score;
    //後向指針
    struct zskiplistNode *backward;

    //節點的level數組，保存每層上的前向指針和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

Zset 對象要同時保存元素和元素的權重，對應到跳表節點結構里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節點都有一個後向指針，指向前一個節點，目的是為了方便從跳表的尾節點開始訪問節點，這樣倒序查找時很方便。

跳表是一個帶有層級關係的鍊表，而且每一層級可以包含多個節點，每一個節點通過指針連接起來，實現這一特性就是靠跳表節點結構體中的zskiplistLevel 結構體類型的 level 數組。

level 數組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結構體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結構體裡定義了「指向下一個跳表節點的指針」和「跨度」，跨度時用來記錄兩個節點之間的距離。

比如，下面這張圖，展示了各個節點的跨度。

第一眼看到跨度的時候，以為是遍歷操作有關，實際上並沒有任何關係，遍歷操作只需要用前向指針就可以完成了。

跨度實際上是為了計算這個節點在跳表中的排位。具體怎麼做的呢？因為跳表中的節點都是按序排列的，那麼計算某個節點排位的時候，從頭節點點到該結點的查詢路徑上，將沿途訪問過的所有層的跨度累加起來，得到的結果就是目標節點在跳表中的排位。

舉個例子，查找圖中節點 3 在跳表中的排位，從頭節點開始查找節點 3，查找的過程只經過了一個層（L3），並且層的跨度是 3，所以節點 3 在跳表中的排位是 3。

另外，圖中的頭節點其實也是 zskiplistNode 跳表節點，只不過頭節點的後向指針、權重、元素值都會被用到，所以圖中省略了這部分。

問題來了，由誰定義哪個跳表節點是頭節點呢？這就介紹「跳表」結構體了，如下所示：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

跳表結構里包含了：

• 跳表的頭尾節點，便於在O(1)時間複雜度內訪問跳表的頭節點和尾節點；
• 跳表的長度，便於在O(1)時間複雜度獲取跳表節點的數量；
• 跳表的最大層數，便於在O(1)時間複雜度獲取跳表中層高最大的那個節點的層數量；

跳表節點查詢過程

查找一個跳表節點的過程時，跳表會從頭節點的最高層開始，逐一遍歷每一層。在遍歷某一層的跳表節點時，會用跳表節點中的 SDS 類型的元素和元素的權重來進行判斷，共有兩個判斷條件：

• 如果當前節點的權重「小於」要查找的權重時，跳表就會訪問該層上的下一個節點。
• 如果當前節點的權重「等於」要查找的權重時，並且當前節點的 SDS 類型數據「小於」要查找的數據時，跳表就會訪問該層上的下一個節點。

如果上面兩個條件都不滿足，或者下一個節點為空時，跳表就會使用目前遍歷到的節點的 level 數組裡的下一層指針，然後沿著下一層指針繼續查找，這就相當於跳到了下一層接著查找。

舉個例子，下圖有個 3 層級的跳表。

如果要查找「元素：abcd，權重：4」的節點，查找的過程是這樣的：

• 先從頭節點的最高層開始，L2 指向了「元素：abc，權重：3」節點，這個節點的權重比要查找節點的小，所以要訪問該層上的下一個節點；
• 但是該層上的下一個節點是空節點，於是就會跳到「元素：abc，權重：3」節點的下一層去找，也就是 leve[1];
• 「元素：abc，權重：3」節點的 leve[1] 的下一個指針指向了「元素：abcde，權重：4」的節點，然後將其和要查找的節點比較。雖然「元素：abcde，權重：4」的節點的權重和要查找的權重相同，但是當前節點的 SDS 類型數據「大於」要查找的數據，所以會繼續跳到「元素：abc，權重：3」節點的下一層去找，也就是 leve[0]；
• 「元素：abc，權重：3」節點的 leve[0] 的下一個指針指向了「元素：abcd，權重：4」的節點，該節點正是要查找的節點，查詢結束。

跳表節點層數設置

跳表的相鄰兩層的節點數量的比例會影響跳表的查詢性能。

舉個例子，下圖的跳表，第二層的節點數量只有 1 個，而第一層的節點數量有 6 個。

這時，如果想要查詢節點 6，那基本就跟鍊表的查詢複雜度一樣，就需要在第一層的節點中依次順序查找，複雜度就是 O(N) 了。所以，為了降低查詢複雜度，我們就需要維持相鄰層結點數間的關係。

跳表的相鄰兩層的節點數量最理想的比例是 2:1，查找複雜度可以降低到 O(logN)。

下圖的跳表就是，相鄰兩層的節點數量的比例是 2 : 1。

那怎樣才能維持相鄰兩層的節點數量的比例為 2 : 1 呢？

如果採用新增節點或者刪除節點時，來調整跳表節點以維持比例的方法的話，會帶來額外的開銷。

Redis 則採用一種巧妙的方法是，跳表在創建節點的時候，隨機生成每個節點的層數，並沒有嚴格維持相鄰兩層的節點數量比例為 2 : 1 的情況。

具體的做法是，跳表在創建節點時候，會生成範圍為[0-1]的一個隨機數，如果這個隨機數小於 0.25（相當於概率 25%），那麼層數就增加 1 層，然後繼續生成下一個隨機數，直到隨機數的結果大於 0.25 結束，最終確定該節點的層數。

這樣的做法，相當於每增加一層的概率不超過 25%，層數越高，概率越低，層高最大限制是 64。

quicklist

在 Redis 3.0 之前，List 對象的底層數據結構是雙向鍊表或者壓縮列表。然後在 Redis 3.2 的時候，List 對象的底層改由 quicklist 數據結構實現。

其實 quicklist 就是「雙向鍊表 + 壓縮列表」組合，因為一個 quicklist 就是一個鍊表，而鍊表中的每個元素又是一個壓縮列表。

在前面講壓縮列表的時候，我也提到了壓縮列表的不足，雖然壓縮列表是通過緊湊型的內存布局節省了內存開銷，但是因為它的結構設計，如果保存的元素數量增加，或者元素變大了，壓縮列表會有「連鎖更新」的風險，一旦發生，會造成性能下降。

quicklist 解決辦法，通過控制每個鍊表節點中的壓縮列表的大小或者元素個數，來規避連鎖更新的問題。因為壓縮列表元素越少或越小，連鎖更新帶來的影響就越小，從而提供了更好的訪問性能。

quicklist 結構設計

quicklist 的結構體跟鍊表的結構體類似，都包含了表頭和表尾，區別在於 quicklist 的節點是 quicklistNode。

typedef struct quicklist {
    //quicklist的鍊表頭
    quicklistNode *head;      //quicklist的鍊表頭
    //quicklist的鍊表頭
    quicklistNode *tail; 
    //所有壓縮列表中的總元素個數
    unsigned long count;
    //quicklistNodes的個數
    unsigned long len;       
    ...
} quicklist;

接下來看看，quicklistNode 的結構定義：

typedef struct quicklistNode {
    //前一個quicklistNode
    struct quicklistNode *prev;     //前一個quicklistNode
    //下一個quicklistNode
    struct quicklistNode *next;     //後一個quicklistNode
    //quicklistNode指向的壓縮列表
    unsigned char *zl;              
    //壓縮列表的的字節大小
    unsigned int sz;                
    //壓縮列表的元素個數
    unsigned int count : 16;        //ziplist中的元素個數 
    ....
} quicklistNode;

可以看到，quicklistNode 結構體裡包含了前一個節點和下一個節點指針，這樣每個 quicklistNode 形成了一個雙向鍊表。但是鍊表節點的元素不再是單純保存元素值，而是保存了一個壓縮列表，所以 quicklistNode 結構體裡有個指向壓縮列表的指針 *zl。

我畫了一張圖，方便你理解 quicklist 數據結構。

在向 quicklist 添加一個元素的時候，不會像普通的鍊表那樣，直接新建一個鍊表節點。而是會檢查插入位置的壓縮列表是否能容納該元素，如果能容納就直接保存到 quicklistNode 結構里的壓縮列表，如果不能容納，才會新建一個新的 quicklistNode 結構。

quicklist 會控制 quicklistNode 結構里的壓縮列表的大小或者元素個數，來規避潛在的連鎖更新的風險，但是這並沒有完全解決連鎖更新的問題。

listpack

quicklist 雖然通過控制 quicklistNode 結構里的壓縮列表的大小或者元素個數，來減少連鎖更新帶來的性能影響，但是並沒有完全解決連鎖更新的問題。

因為 quicklistNode 還是用了壓縮列表來保存元素，壓縮列表連鎖更新的問題，來源於它的結構設計，所以要想徹底解決這個問題，需要設計一個新的數據結構。

於是，Redis 在 5.0 新設計一個數據結構叫 listpack，目的是替代壓縮列表，它最大特點是 listpack 中每個節點不再包含前一個節點的長度了，壓縮列表每個節點正因為需要保存前一個節點的長度欄位，就會有連鎖更新的隱患。

我看了 Redis 的 Github，在最新 6.2 發行版本中，Redis Hash 對象、Set 對象的底層數據結構的壓縮列表還未被替換成 listpack，而 Redis 的最新代碼（還未發布版本）已經將所有用到壓縮列表底層數據結構的 Redis 對象替換成 listpack 數據結構來實現，估計不久將來，Redis 就會發布一個將壓縮列表為 listpack 的發行版本。

listpack 結構設計

listpack 採用了壓縮列表的很多優秀的設計，比如還是用一塊連續的內存空間來緊湊地保存數據，並且為了節省內存的開銷，listpack 節點會採用不同的編碼方式保存不同大小的數據。

我們先看看 listpack 結構：

listpack 頭包含兩個屬性，分別記錄了 listpack 總字節數和元素數量，然後 listpack 末尾也有個結尾標識。圖中的 listpack entry 就是 listpack 的節點了。

每個 listpack 節點結構如下：

主要包含三個方面內容：

• encoding，定義該元素的編碼類型，會對不同長度的整數和字符串進行編碼；
• data，實際存放的數據；
• len，encoding+data的總長度；

可以看到，listpack 沒有壓縮列表中記錄前一個節點長度的欄位了，listpack 只記錄當前節點的長度，當我們向 listpack 加入一個新元素的時候，不會影響其他節點的長度欄位的變化，從而避免了壓縮列表的連鎖更新問題。

原連結：https://www.cnblogs.com/xiaolincoding/p/15628854.html

歡迎點讚+轉發+關注！大家的支持是我分享最大的動力！！！