Redis 為什么那么快

redis是一種內存數據庫，所有的操作都是在內存中進行的，還有一種重要原因是：它的數據結構的設計對數據進行增刪查改操作很高效。

redis的數據結構是什么

redis數據結構是對redis鍵值對值的數據類型的底層的實現，注意不是String、List、Hash、Set、Zset、BitMap、HyperLogLog、GEO、Stream這些數據類型，而是對這些類型的底層實現。

?從上圖我們也知道數據結構主要有：：SDS、雙向鏈表、壓縮列表、哈希表、跳表、整數集合、quicklist、listpack。但是，雙向鏈表、壓縮列表已經使用quicklist、listpack替代了。

鍵值對數據庫是怎么實現的？

在講數據結構之前，我們先了解一下redis的鍵值對（key-value）是怎么實現的。

redis鍵值對的key是一個字符串對象，而value可以是redis數據類型中的任何一個對象。那這鍵值對是怎么保存的呢？

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

那么哈希桶又是怎么保存鍵值對數據的呢？

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

?上圖說明：

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，指向底層數據結構的指針。

到這里，我們大概知道edis的鍵值對（key-value）的大體實現，那么下面我們就開始聊聊這些底層實現的數據結構。

SDS

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

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

SDS 的數據結構：

?SDS 的數據結構說明：

len：記錄了字符串長度。這樣獲取字符串長度的時候，只需要返回這個成員變量值就行，時間復雜度只需要 O（1）。

alloc：分配給字符數組的空間長度。這樣在修改字符串的時候，可以通過 alloc - len 計算出剩余的空間大小，可以用來判斷空間是否滿足修改需求，如果不滿足的話，就會自動將 SDS ?的空間擴展至執行修改所需的大小，然后才執行實際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現前面所說的緩沖區溢出的問題。

flags：用來表示不同類型的 SDS。一共設計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說明區別之處。

buf[]：字符數組，用來保存實際數據。不僅可以保存字符串，也可以保存二進制數據。
?

SDS與C語言中字符串的區別

1.獲取字符串長度

因為C語言字符串本身不記錄自身的長度，若要獲取其長度，則需要遍歷字符串才能得到，時間復雜度為O(N)；而SDS在其自身的數據結構中記錄了以使用字符串空間（也就是len），所以獲取一個字符串長度的時間復雜度為O(1)

2.防止緩沖區的溢出

C 語言的字符串標準庫提供的字符串操作函數，大多數（比如 strcat 追加字符串函數）都是不安全的，因為這些函數把緩沖區大小是否滿足操作需求的工作交由開發者來保證，程序內部并不會判斷緩沖區大小是否足夠用，當發生了緩沖區溢出就有可能造成程序異常結束；SDS由于其自身記錄了長度，在每次修改SDS時：（1）API會檢查SDS的空間是否足夠；（2）若不足，則API會自動將SDS的空間擴展至所需的大小，再進行接下來的操作。由此，SDS可以避免緩沖區的溢出。

3.二進制安全

C 語言的字符串需要以?“\0” 字符來標識字符串結尾的。而SDS不需要，它是有len 成員變量來記錄長度，所以它存儲任意格式的二進制數據，就算這個數據中間有“\0”?也不會因為遇到“\0”?結束。但是 SDS 為了兼容部分 C 語言標準庫的函數， SDS 字符串結尾還是會加上 “\0” 字符。

4.減少修改字符串時內存重分配的次數

在一般的程序中，每次修改字符串都執行一次內存重分配，這是可以接受的；但是redis作為數據庫，經常用于速度要求嚴苛、數據要求頻繁修改的場合，每次修改字符串所需要內存重分配，可能會對性能造成影響。通過使用未使用的空間（alloc），SDS實現了空間預分配與惰性空間釋放兩種優化策略。

5.?節省內存空間

SDS 結構中有個 flags 成員變量，表示的是 SDS 類型。分別是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 對象的底層實現之一就是鏈表。鏈表節點的數據結構如下：

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

從定義可以看出，這是一個雙向鏈表：

?但是，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 5.0 設計了新的數據結構 listpack來替代List 對象的底層數據結構。

壓縮列表

壓縮列表的最大特點，就是它被設計成一種內存緊湊型的數據結構，占用一塊連續的內存空間，不僅可以利用 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 引入）。這兩種數據結構的設計目標，就是盡可能地保持壓縮列表節省內存的優勢，同時解決壓縮列表的「連鎖更新」的問題。

哈希表

redis中哈希鍵的底層實現之一就是字典，實際與C++語言中的哈希表一樣，都是一個鍵與一個值進行關聯，并稱為鍵值對。由于redis使用的C語言沒有這種數據結構，所以redis自己構建了字典實現。在我看來，在redis中的字典與哈希表的關系就是，字典就是對哈希表的結構的一個封裝而已，只是為了方便使用。下面會講到二者的關系。

優缺點

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

但是存在的風險也是有，在哈希表大小固定的情況下，隨著數據不斷增多，那么哈希沖突的可能性也會越高。Redis 采用了「鏈式哈希」來解決哈希沖突。

哈希表結構設計

字典的定義：

typedef struct dict{//類型特定的函數dictType * type;//私有數據void * private;//哈希表dictht ht[2];//rehash的索引int rehashidx;
} dict;

哈希表的數據結構如下：

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

其中，哈希表節點的數據結構如下：

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 結構里，無需再用一個指針指向實際的值，從而節省了內存空間。

哈希表的結構圖

?關于什么是哈希沖突和解決方案?可以查看我之前的文章解決哈希沖突的方案，不過，鏈式哈希局限性也很明顯，隨著鏈表長度的增加，在查詢這一位置上的數據的耗時就會增加，畢竟鏈表的查詢的時間復雜度是 O(n)。要想解決這一問題，就需要進行 rehash，也就是對哈希表的大小進行擴展。

哈希表擴容（rehash）

1.? 為字典的 ht[1] 哈希表分配空間（ht[1] 大小為 ht[0] 的 2^n）；

2. 將 ht[0] 中的鍵值對reahash到 ht[1] 中；

3. 當 ht[0] 中的所有數據拷貝到 ht[1] 后，釋放 ht[0];

4. 將 ht[1] 設置為 ht[0]，并在 ht[1] 新創建一個空白哈希表，為下一次rehash做準備

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

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

漸進式rehash

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

漸進式 rehash 步驟如下：

1. 為ht[1]分配空間，讓字典同時持有 ht[0] 與 ht[1] ;

2. 在字典中維持一個索引計數器變量rehashidx，并將其設置為0，表示rehash開始；

3. rehash期間，每次的修改，程序除了指定的操作外，還會將 ht[0] 在rehashidx上的所有鍵值rehash到 ht[1]，rehash完成后，rehashidx加一；

4. 當 ht[0] 中所有的數據都rehash到 ht[1] 時，rehashidx設置為-1，rehash完成

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

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

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

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

觸發 rehash 操作的條件：

當負載因子大于等于 1 ，并且 Redis 沒有在執行 bgsave 命令或者 bgrewiteaof 命令，也就是沒有執行 RDB 快照或沒有進行 AOF 重寫的時候，就會進行 rehash 操作。

當負載因子大于等于 5 時，此時說明哈希沖突非常嚴重了，不管有沒有有在執行 RDB 快照或 AOF 重寫，都會強制進行 rehash 操作。

負載因子就是：