為了拿捏?Redis?數(shù)據(jù)結(jié)構(gòu)，我畫了?40?張圖（完整版）
時間：2021-12-07 15:51:59
關(guān)鍵字：
數(shù)據(jù)結(jié)構(gòu)
REDIS
節(jié)點
字符串
手機(jī)看文章
掃描二維碼
隨時隨地手機(jī)看文章
[導(dǎo)讀]大家好，我是小林。前幾天發(fā)了一篇「為了拿捏Redis數(shù)據(jù)結(jié)構(gòu)，我畫了20張圖」，收獲了很多好評，但是當(dāng)時急于發(fā)文，有些地方?jīng)]有寫完，也有些地方寫的不是很完善。然后我最近花了很多時間來完善文章，不僅加入了Redis新版本的兩個數(shù)據(jù)結(jié)構(gòu)，也在之前的文章內(nèi)容加入了很多內(nèi)容。這次完整版終...
大家好，我是小林。前幾天發(fā)了一篇「為了拿捏 Redis 數(shù)據(jù)結(jié)構(gòu)，我畫了 20 張圖」，收獲了很多好評，但是當(dāng)時急于發(fā)文，有些地方?jīng)]有寫完，也有些地方寫的不是很完善。然后我最近花了很多時間來完善文章，不僅加入了 Redis 新版本的兩個數(shù)據(jù)結(jié)構(gòu)，也在之前的文章內(nèi)容加入了很多內(nèi)容。這次完整版終于來了，加了億點點東西！從之前的 1 萬字，變成現(xiàn)在的 2 萬字，圖更是畫到了接近 40 張！不管是內(nèi)容還是圖片，都比上一篇翻了一倍！
好了， 通過以上的分析，我們可以得知 C 語言的字符串不足之處以及可以改進(jìn)的地方：
正文
Redis 為什么那么快？除了它是內(nèi)存數(shù)據(jù)庫，使得所有的操作都在內(nèi)存上進(jìn)行之外，還有一個重要因素，它實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，使得我們對數(shù)據(jù)進(jìn)行增刪查改操作時，Redis 能高效的處理。因此，這次我們就來好好聊一下 Redis 數(shù)據(jù)結(jié)構(gòu)，這個在面試中太常問了。注意，Redis 數(shù)據(jù)結(jié)構(gòu)并不是指 String（字符串）對象、List（列表）對象、Hash（哈希）對象、Set（集合）對象和 Zset（有序集合）對象，因為這些是 Redis 鍵值對中值的數(shù)據(jù)類型，也就是數(shù)據(jù)的保存形式，這些對象的底層實現(xiàn)的方式就用到了數(shù)據(jù)結(jié)構(gòu)。我畫了一張 Redis 數(shù)據(jù)類型（也叫 Redis 對象）和底層數(shù)據(jù)結(jié)構(gòu)的對應(yīng)關(guān)圖，左邊是 Redis 3.0版本的，也就是《Redis 設(shè)計與實現(xiàn)》這本書講解的版本，現(xiàn)在看還是有點過時了，右邊是現(xiàn)在 Github 最新的 Redis 代碼的（還未發(fā)布正式版本）。- 在 Redis 3.0 版本中 List 對象的底層數(shù)據(jù)結(jié)構(gòu)由「雙向鏈表」或「壓縮表列表」實現(xiàn)，但是在 3.2 版本之后，List 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)是由 quicklist 實現(xiàn)的；
- 在最新的 Redis 代碼（還未發(fā)布正式版本）中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)了。
鍵值對數(shù)據(jù)庫是怎么實現(xiàn)的？
在開始講數(shù)據(jù)結(jié)構(gòu)之前，先給介紹下 Redis 是怎樣實現(xiàn)鍵值對（key-value）數(shù)據(jù)庫的。Redis 的鍵值對中的 key 就是字符串對象，而 value 可以是字符串對象，也可以是集合數(shù)據(jù)類型的對象，比如 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 是一個列表鍵，因為鍵的值是一個包含兩個元素的列表對象；
- redisDb 結(jié)構(gòu)，表示 Redis 數(shù)據(jù)庫的結(jié)構(gòu)，結(jié)構(gòu)體里存放了指向了 dict 結(jié)構(gòu)的指針；
- dict 結(jié)構(gòu)，結(jié)構(gòu)體里存放了 2 個哈希表，正常情況下都是用「哈希表1」，「哈希表2」只有在 rehash 的時候才用，具體什么是 rehash，我在本文的哈希表數(shù)據(jù)結(jié)構(gòu)會講；
- ditctht 結(jié)構(gòu)，表示哈希表的結(jié)構(gòu)，結(jié)構(gòu)里存放了哈希表數(shù)組，數(shù)組中的每個元素都是指向一個哈希表節(jié)點結(jié)構(gòu)（dictEntry）的指針；
- dictEntry 結(jié)構(gòu)，表示哈希表節(jié)點的結(jié)構(gòu)，結(jié)構(gòu)里存放了 void * key 和 void * value 指針， *key 指向的是 String 對象，而 *value 則可以指向 String 對象，也可以指向集合類型的對象，比如 List 對象、Hash 對象、Set 對象和 Zset 對象。
- type，標(biāo)識該對象是什么類型的對象（String 對象、 List 對象、Hash 對象、Set 對象和 Zset 對象）；
- encoding，標(biāo)識該對象使用了哪種底層的數(shù)據(jù)結(jié)構(gòu)；
- ptr，指向底層數(shù)據(jù)結(jié)構(gòu)的指針。
SDS
字符串在 Redis 中是很常用的，鍵值對中的鍵是字符串類型，值有時也是字符串類型。Redis 是用 C 語言實現(xiàn)的，但是它沒有直接使用 C 語言的 char* 字符數(shù)組來實現(xiàn)字符串，而是自己封裝了一個名為簡單動態(tài)字符串（simple dynamic string，SDS） 的數(shù)據(jù)結(jié)構(gòu)來表示字符串，也就是 Redis 的 String 數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)是 SDS。既然 Redis 設(shè)計了 SDS 結(jié)構(gòu)來表示字符串，肯定是 C 語言的 char* 字符數(shù)組存在一些缺陷。要了解這一點，得先來看看 char* 字符數(shù)組的結(jié)構(gòu)。C 語言字符串的缺陷
C 語言的字符串其實就是一個字符數(shù)組，即數(shù)組中每個元素是字符串中的一個字符。比如，下圖就是字符串“xiaolin”的 char* 字符數(shù)組的結(jié)構(gòu)：strlen，就是通過字符數(shù)組中的每一個字符，并進(jìn)行計數(shù)，等遇到字符為 “\0” 后，就會停止遍歷，然后返回已經(jīng)統(tǒng)計到的字符個數(shù)，即為字符串長度。下圖顯示了 strlen 函數(shù)的執(zhí)行流程：?//將?src?字符串拼接到?dest?字符串后面
?char?*strcat(char?*dest,?const?char*?src);
C 語言的字符串是不會記錄自身的緩沖區(qū)大小的，所以 strcat 函數(shù)假定程序員在執(zhí)行這個函數(shù)時，已經(jīng)為 dest 分配了足夠多的內(nèi)存，可以容納 src 字符串中的所有內(nèi)容，而一旦這個假定不成立，就會發(fā)生緩沖區(qū)溢出將可能會造成程序運行終止，（這是一個可以改進(jìn)的地方）。而且，strcat 函數(shù)和 strlen 函數(shù)類似，時間復(fù)雜度也很高，也都需要先通過遍歷字符串才能得到目標(biāo)字符串的末尾。然后對于 strcat 函數(shù)來說，還要再遍歷源字符串才能完成追加，對字符串的操作效率不高。好了， 通過以上的分析，我們可以得知 C 語言的字符串不足之處以及可以改進(jìn)的地方：
- 獲取字符串長度的時間復(fù)雜度為 ?O（N）；
- 字符串的結(jié)尾是以 “\0” 字符標(biāo)識，字符串里面不能包含有 “\0” 字符，因此不能保存二進(jìn)制數(shù)據(jù)；
- 字符串操作函數(shù)不高效且不安全，比如有緩沖區(qū)溢出的風(fēng)險，有可能會造成程序運行終止；
SDS 結(jié)構(gòu)設(shè)計
下圖就是 Redis 5.0 的 SDS 的數(shù)據(jù)結(jié)構(gòu)：- len，記錄了字符串長度。這樣獲取字符串長度的時候，只需要返回這個成員變量值就行，時間復(fù)雜度只需要 O（1）。
- alloc，分配給字符數(shù)組的空間長度。這樣在修改字符串的時候，可以通過
alloc - len計算出剩余的空間大小，可以用來判斷空間是否滿足修改需求，如果不滿足的話，就會自動將 SDS ?的空間擴(kuò)展至執(zhí)行修改所需的大小，然后才執(zhí)行實際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現(xiàn)前面所說的緩沖區(qū)溢出的問題。 - flags，用來表示不同類型的 SDS。一共設(shè)計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說明區(qū)別之處。
- buf[]，字符數(shù)組，用來保存實際數(shù)據(jù)。不僅可以保存字符串，也可以保存二進(jìn)制數(shù)據(jù)。
O（1）復(fù)雜度獲取字符串長度
C 語言的字符串長度獲取 strlen 函數(shù)，需要通過遍歷的方式來統(tǒng)計字符串長度，時間復(fù)雜度是 O（N）。而 Redis 的 SDS 結(jié)構(gòu)因為加入了 len 成員變量，那么獲取字符串長度的時候，直接返回這個成員變量的值就行，所以復(fù)雜度只有 O（1）。二進(jìn)制安全
因為 SDS 不需要用 “\0” 字符來標(biāo)識字符串結(jié)尾了，而是有個專門的 len 成員變量來記錄長度，所以可存儲包含 “\0” 的數(shù)據(jù)。但是 SDS 為了兼容部分 C 語言標(biāo)準(zhǔn)庫的函數(shù)， SDS 字符串結(jié)尾還是會加上 “\0” 字符。因此， SDS 的 API 都是以處理二進(jìn)制的方式來處理 SDS 存放在 buf[] 里的數(shù)據(jù)，程序不會對其中的數(shù)據(jù)做任何限制，數(shù)據(jù)寫入的時候時什么樣的，它被讀取時就是什么樣的。通過使用二進(jìn)制安全的 SDS，而不是 C 字符串，使得 Redis 不僅可以保存文本數(shù)據(jù)，也可以保存任意格式的二進(jìn)制數(shù)據(jù)。不會發(fā)生緩沖區(qū)溢出
C 語言的字符串標(biāo)準(zhǔn)庫提供的字符串操作函數(shù)，大多數(shù)（比如 strcat 追加字符串函數(shù)）都是不安全的，因為這些函數(shù)把緩沖區(qū)大小是否滿足操作需求的工作交由開發(fā)者來保證，程序內(nèi)部并不會判斷緩沖區(qū)大小是否足夠用，當(dāng)發(fā)生了緩沖區(qū)溢出就有可能造成程序異常結(jié)束。所以，Redis 的 SDS 結(jié)構(gòu)里引入了 alloc 和 len 成員變量，這樣 SDS API 通過alloc - len 計算，可以算出剩余可用的空間大小，這樣在對字符串做修改操作的時候，就可以由程序內(nèi)部判斷緩沖區(qū)大小是否足夠用。而且，當(dāng)判斷出緩沖區(qū)大小不夠用時，Redis 會自動將擴(kuò)大 SDS 的空間大?。ㄐ∮?1MB 翻倍擴(kuò)容，大于 1MB 按 1MB 擴(kuò)容），以滿足修改所需的大小。在擴(kuò)展 SDS 空間之前，SDS API 會優(yōu)先檢查未使用空間是否足夠，如果不夠的話，API 不僅會為 SDS 分配修改所必須要的空間，還會給 SDS 分配額外的「未使用空間」。這樣的好處是，下次在操作 SDS 時，如果 SDS 空間夠的話，API 就會直接使用「未使用空間」，而無須執(zhí)行內(nèi)存分配，有效的減少內(nèi)存分配次數(shù)。所以，使用 SDS 即不需要手動修改 SDS 的空間大小，也不會出現(xiàn)緩沖區(qū)溢出的問題。節(jié)省內(nèi)存空間
SDS 結(jié)構(gòu)中有個 flags 成員變量，表示的是 SDS 類型。Redos 一共設(shè)計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。這 5 種類型的主要區(qū)別就在于，它們數(shù)據(jù)結(jié)構(gòu)中的 len 和 alloc 成員變量的數(shù)據(jù)類型不同。比如 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 的數(shù)據(jù)類型都是 uint16_t，表示字符數(shù)組長度和分配空間大小不能超過 2 的 16 次方。
- sdshdr32 則都是 uint32_t，表示表示字符數(shù)組長度和分配空間大小不能超過 2 的 32 次方。
__attribute__ ((packed)) ，它的作用是：告訴編譯器取消結(jié)構(gòu)體在編譯過程中的優(yōu)化對齊，按照實際占用字節(jié)數(shù)進(jìn)行對齊。比如，sdshdr16 類型的 SDS，默認(rèn)情況下，編譯器會按照 16 字節(jié)對齊的方式給變量分配內(nèi)存，這意味著，即使一個變量的大小不到 16 個字節(jié)，編譯器也會給它分配 16 個字節(jié)。舉個例子，假設(shè)下面這個結(jié)構(gòu)體，它有兩個成員變量，類型分別是 char 和 int，如下所示：#include?
?struct?test1?{
????char?a;
????int?b;
?}?test1;
int?main()?{
?????printf("%lu\n",?sizeof(test1));
?????return?0;
}
大家猜猜這個結(jié)構(gòu)體大小是多少？我先直接說答案，這個結(jié)構(gòu)體大小計算出來是 8。__attribute__ ((packed)) 屬性定義結(jié)構(gòu)體，這樣一來，結(jié)構(gòu)體實際占用多少內(nèi)存空間，編譯器就分配多少空間。比如，我用 __attribute__ ((packed)) 屬性定義下面的結(jié)構(gòu)體 ，同樣包含 char 和 int 兩個類型的成員變量，代碼如下所示：#include?
struct?__attribute__((packed))?test2??{
????char?a;
????int?b;
?}?test2;
int?main()?{
?????printf("%lu\n",?sizeof(test2));
?????return?0;
}
這時打印的結(jié)果是 5（1 個字節(jié) char ? 4 字節(jié) int）。鏈表
大家最熟悉的數(shù)據(jù)結(jié)構(gòu)除了數(shù)組之外，我相信就是鏈表了。Redis 的 List 對象的底層實現(xiàn)之一就是鏈表。C 語言本身沒有鏈表這個數(shù)據(jù)結(jié)構(gòu)的，所以 Redis 自己設(shè)計了一個鏈表數(shù)據(jù)結(jié)構(gòu)。鏈表節(jié)點結(jié)構(gòu)設(shè)計
先來看看「鏈表節(jié)點」結(jié)構(gòu)的樣子：typedef?struct?listNode?{
????//前置節(jié)點
????struct?listNode?*prev;
????//后置節(jié)點
????struct?listNode?*next;
????//節(jié)點的值
????void?*value;
}?listNode;
有前置節(jié)點和后置節(jié)點，可以看的出，這個是一個雙向鏈表。鏈表結(jié)構(gòu)設(shè)計
不過，Redis 在 listNode 結(jié)構(gòu)體基礎(chǔ)上又封裝了 list 這個數(shù)據(jù)結(jié)構(gòu)，這樣操作起來會更方便，鏈表結(jié)構(gòu)如下：typedef?struct?list?{
????//鏈表頭節(jié)點
????listNode?*head;
????//鏈表尾節(jié)點
????listNode?*tail;
????//節(jié)點值復(fù)制函數(shù)
????void?*(*dup)(void?*ptr);
????//節(jié)點值釋放函數(shù)
????void?(*free)(void?*ptr);
????//節(jié)點值比較函數(shù)
????int?(*match)(void?*ptr,?void?*key);
????//鏈表節(jié)點數(shù)量
????unsigned?long?len;
}?list;
list 結(jié)構(gòu)為鏈表提供了鏈表頭指針 head、鏈表尾節(jié)點 tail、鏈表節(jié)點數(shù)量 len、以及可以自定義實現(xiàn)的 dup、free、match 函數(shù)。舉個例子，下面是由 list 結(jié)構(gòu)和 3 個 listNode 結(jié)構(gòu)組成的鏈表。鏈表的優(yōu)勢與缺陷
Redis 的鏈表實現(xiàn)優(yōu)點如下：- listNode 鏈表節(jié)點的結(jié)構(gòu)里帶有 prev 和 next 指針，獲取某個節(jié)點的前置節(jié)點或后置節(jié)點的時間復(fù)雜度只需O(1)，而且這兩個指針都可以指向 NULL，所以鏈表是無環(huán)鏈表；
- list 結(jié)構(gòu)因為提供了表頭指針 head 和表尾節(jié)點 tail，所以獲取鏈表的表頭節(jié)點和表尾節(jié)點的時間復(fù)雜度只需O(1)；
- list 結(jié)構(gòu)因為提供了鏈表節(jié)點數(shù)量 len，所以獲取鏈表中的節(jié)點數(shù)量的時間復(fù)雜度只需O(1)；
- listNode 鏈表節(jié)使用 void* 指針保存節(jié)點值，并且可以通過 list 結(jié)構(gòu)的 dup、free、match 函數(shù)指針為節(jié)點設(shè)置該節(jié)點類型特定的函數(shù)，因此鏈表節(jié)點可以保存各種不同類型的值；
- 鏈表每個節(jié)點之間的內(nèi)存都是不連續(xù)的，意味著無法很好利用 CPU 緩存。能很好利用 CPU 緩存的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，因為數(shù)組的內(nèi)存是連續(xù)的，這樣就可以充分利用 CPU 緩存來加速訪問。
- 還有一點，保存一個鏈表節(jié)點的值都需要一個鏈表節(jié)點結(jié)構(gòu)頭的分配，內(nèi)存開銷較大。
壓縮列表
壓縮列表的最大特點，就是它被設(shè)計成一種內(nèi)存緊湊型的數(shù)據(jù)結(jié)構(gòu)，占用一塊連續(xù)的內(nèi)存空間，不僅可以利用 CPU 緩存，而且會針對不同長度的數(shù)據(jù)，進(jìn)行相應(yīng)編碼，這種方法可以有效地節(jié)省內(nèi)存開銷。但是，壓縮列表的缺陷也是有的：- 不能保存過多的元素，否則查詢效率就會降低；
- 新增或修改某個元素時，壓縮列表占用的內(nèi)存空間需要重新分配，甚至可能引發(fā)連鎖更新的問題。
壓縮列表結(jié)構(gòu)設(shè)計
壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的，它是由連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，有點類似于數(shù)組。- zlbytes，記錄整個壓縮列表占用對內(nèi)存字節(jié)數(shù)；
- zltail，記錄壓縮列表「尾部」節(jié)點距離起始地址由多少字節(jié)，也就是列表尾的偏移量；
- zllen，記錄壓縮列表包含的節(jié)點數(shù)量；
- zlend，標(biāo)記壓縮列表的結(jié)束點，固定值 0xFF（十進(jìn)制255）。
- prevlen，記錄了「前一個節(jié)點」的長度；
- encoding，記錄了當(dāng)前節(jié)點實際數(shù)據(jù)的類型以及長度；
- data，記錄了當(dāng)前節(jié)點的實際數(shù)據(jù)；
- 如果前一個節(jié)點的長度小于 254 字節(jié)，那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個長度值；
- 如果前一個節(jié)點的長度大于等于 254 字節(jié)，那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個長度值；
- 如果當(dāng)前節(jié)點的數(shù)據(jù)是整數(shù)，則 encoding 會使用 1 字節(jié)的空間進(jìn)行編碼。
- 如果當(dāng)前節(jié)點的數(shù)據(jù)是字符串，根據(jù)字符串的長度大小，encoding 會使用 1 字節(jié)/2字節(jié)/5字節(jié)的空間進(jìn)行編碼。
連鎖更新
壓縮列表除了查找復(fù)雜度高的問題，還有一個問題。壓縮列表新增某個元素或修改某個元素時，如果空間不不夠，壓縮列表占用的內(nèi)存空間就需要重新分配。而當(dāng)新插入的元素較大時，可能會導(dǎo)致后續(xù)元素的 prevlen 占用空間都發(fā)生變化，從而引起「連鎖更新」問題，導(dǎo)致每個元素的空間都要重新分配，造成訪問壓縮列表性能的下降。前面提到，壓縮列表節(jié)點的 prevlen 屬性會根據(jù)前一個節(jié)點的長度進(jìn)行不同的空間大小分配：- 如果前一個節(jié)點的長度小于 254 字節(jié)，那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個長度值；
- 如果前一個節(jié)點的長度大于等于 254 字節(jié)，那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個長度值；
壓縮列表的缺陷
空間擴(kuò)展操作也就是重新分配內(nèi)存，因此連鎖更新一旦發(fā)生，就會導(dǎo)致壓縮列表占用的內(nèi)存空間要多次重新分配，這就會直接影響到壓縮列表的訪問性能。所以說，雖然壓縮列表緊湊型的內(nèi)存布局能節(jié)省內(nèi)存開銷，但是如果保存的元素數(shù)量增加了，或是元素變大了，會導(dǎo)致內(nèi)存重新分配，最糟糕的是會有「連鎖更新」的問題。因此，壓縮列表只會用于保存的節(jié)點數(shù)量不多的場景，只要節(jié)點數(shù)量足夠小，即使發(fā)生連鎖更新，也是能接受的。雖說如此，Redis 針對壓縮列表在設(shè)計上的不足，在后來的版本中，新增設(shè)計了兩種數(shù)據(jù)結(jié)構(gòu)：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。這兩種數(shù)據(jù)結(jié)構(gòu)的設(shè)計目標(biāo)，就是盡可能地保持壓縮列表節(jié)省內(nèi)存的優(yōu)勢，同時解決壓縮列表的「連鎖更新」的問題。哈希表
哈希表是一種保存鍵值對（key-value）的數(shù)據(jù)結(jié)構(gòu)。哈希表中的每一個 key 都是獨一無二的，程序可以根據(jù) key 查找到與之關(guān)聯(lián)的 value，或者通過 key 來更新 value，又或者根據(jù) key 來刪除整個 key-value等等。在講壓縮列表的時候，提到過 Redis 的 Hash 對象的底層實現(xiàn)之一是壓縮列表（最新 Redis 代碼已將壓縮列表替換成 listpack）。Hash 對象的另外一個底層實現(xiàn)就是哈希表。哈希表優(yōu)點在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。怎么做到的呢？將 key 通過 Hash 函數(shù)的計算，就能定位數(shù)據(jù)在表中的位置，因為哈希表實際上是數(shù)組，所以可以通過索引值快速查詢到數(shù)據(jù)。但是存在的風(fēng)險也是有，在哈希表大小固定的情況下，隨著數(shù)據(jù)不斷增多，那么哈希沖突的可能性也會越高。解決哈希沖突的方式，有很多種。Redis 采用了「鏈?zhǔn)焦！箒斫鉀Q哈希沖突，在不擴(kuò)容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)串起來，形成鏈接起，以便這些數(shù)據(jù)在表中仍然可以被查詢到。接下來，詳細(xì)說說哈希表。哈希表結(jié)構(gòu)設(shè)計
Redis 的哈希表結(jié)構(gòu)如下：typedef?struct?dictht?{
????//哈希表數(shù)組
????dictEntry?**table;
????//哈希表大小
????unsigned?long?size;??
????//哈希表大小掩碼，用于計算索引值
????unsigned?long?sizemask;
????//該哈希表已有的節(jié)點數(shù)量
????unsigned?long?used;
}?dictht;
可以看到，哈希表是一個數(shù)組（dictEntry **table），數(shù)組的每個元素是一個指向「哈希表節(jié)點（dictEntry）」的指針。typedef?struct?dictEntry?{
????//鍵值對中的鍵
????void?*key;
????//鍵值對中的值
????union?{
????????void?*val;
????????uint64_t?u64;
????????int64_t?s64;
????????double?d;
????}?v;
????//指向下一個哈希表節(jié)點，形成鏈表
????struct?dictEntry?*next;
}?dictEntry;
dictEntry 結(jié)構(gòu)里不僅包含指向鍵和值的指針，還包含了指向下一個哈希表節(jié)點的指針，這個指針可以將多個哈希值相同的鍵值對鏈接起來，以此來解決哈希沖突的問題，這就是鏈?zhǔn)焦！?/p>另外，這里還跟你提一下，dictEntry 結(jié)構(gòu)里鍵值對中的值是一個「聯(lián)合體 v」定義的，因此，鍵值對中的值可以是一個指向?qū)嶋H值的指針，或者是一個無符號的 64 位整數(shù)或有符號的 64 位整數(shù)或double 類的值。這么做的好處是可以節(jié)省內(nèi)存空間，因為當(dāng)「值」是整數(shù)或浮點數(shù)時，就可以將值的數(shù)據(jù)內(nèi)嵌在 dictEntry 結(jié)構(gòu)里，無需再用一個指針指向?qū)嶋H的值，從而節(jié)省了內(nèi)存空間。哈希沖突
哈希表實際上是一個數(shù)組，數(shù)組里多每一個元素就是一個哈希桶。當(dāng)一個鍵值對的鍵經(jīng)過 Hash 函數(shù)計算后得到哈希值，再將(哈希值 % 哈希表大小)取模計算，得到的結(jié)果值就是該 key-value 對應(yīng)的數(shù)組元素位置，也就是第幾個哈希桶。什么是哈希沖突呢？舉個例子，有一個可以存放 8 個哈希桶的哈希表。key1 經(jīng)過哈希函數(shù)計算后，再將「哈希值 % 8 」進(jìn)行取模計算，結(jié)果值為 1，那么就對應(yīng)哈希桶 1，類似的，key9 和 key10 分別對應(yīng)哈希桶 1 和桶 6。
鏈?zhǔn)焦?/span>
Redis 采用了「鏈?zhǔn)焦！沟姆椒▉斫鉀Q哈希沖突。鏈?zhǔn)焦Ｊ窃趺磳崿F(xiàn)的？實現(xiàn)的方式就是每個哈希表節(jié)點都有一個 next 指針，用于指向下一個哈希表節(jié)點，因此多個哈希表節(jié)點可以用 next 指針構(gòu)成一個單項鏈表，被分配到同一個哈希桶上的多個節(jié)點可以用這個單項鏈表連接起來，這樣就解決了哈希沖突。還是用前面的哈希沖突例子，key1 和 key9 經(jīng)過哈希計算后，都落在同一個哈希桶，鏈?zhǔn)焦５脑挘琸ey1 就會通過 next 指針指向 key9，形成一個單向鏈表。
rehash
哈希表結(jié)構(gòu)設(shè)計的這一小節(jié)，我給大家介紹了 Redis 使用 dictht 結(jié)構(gòu)體表示哈希表。不過，在實際使用哈希表時，Redis 定義一個 dict 結(jié)構(gòu)體，這個結(jié)構(gòu)體里定義了兩個哈希表（ht[2]）。typedef?struct?dict?{
????…
????//兩個Hash表，交替使用，用于rehash操作
????dictht?ht[2];?
????…
}?dict;
之所以定義了 2 個哈希表，是因為進(jìn)行 rehash 的時候，需要用上 2 個哈希表了。- 給「哈希表 2」 分配空間，一般會比「哈希表 1」 大 2 倍；
- 將「哈希表 1 」的數(shù)據(jù)遷移到「哈希表 2」 中；
- 遷移完成后，「哈希表 1 」的空間會被釋放，并把「哈希表 2」 設(shè)置為「哈希表 1」，然后在「哈希表 2」 新創(chuàng)建一個空白的哈希表，為下次 rehash 做準(zhǔn)備。
漸進(jìn)式 rehash
為了避免 rehash 在數(shù)據(jù)遷移過程中，因拷貝數(shù)據(jù)的耗時，影響 Redis 性能的情況，所以 Redis 采用了漸進(jìn)式 rehash，也就是將數(shù)據(jù)的遷移的工作不再是一次性遷移完成，而是分多次遷移。漸進(jìn)式 rehash 步驟如下：- 給「哈希表 2」 分配空間；
- 在 rehash 進(jìn)行期間，每次哈希表元素進(jìn)行新增、刪除、查找或者更新操作時，Redis 除了會執(zhí)行對應(yīng)的操作之外，還會順序?qū)ⅰ腹１?1 」中索引位置上的所有 key-value 遷移到「哈希表 2」 上；
- 隨著處理客戶端發(fā)起的哈希表操作請求數(shù)量越多，最終在某個時間嗲呢，會把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。
rehash 觸發(fā)條件
介紹了 rehash 那么多，還沒說什么時情況下會觸發(fā) rehash 操作呢？rehash 的觸發(fā)條件跟負(fù)載因子（load factor）有關(guān)系。負(fù)載因子可以通過下面這個公式計算：- 當(dāng)負(fù)載因子大于等于 1 ，并且 Redis 沒有在執(zhí)行 bgsave 命令或者 bgrewiteaof 命令，也就是沒有執(zhí)行 RDB 快照或沒有進(jìn)行 AOF 重寫的時候，就會進(jìn)行 rehash 操作。
- 當(dāng)負(fù)載因子大于等于 5 時，此時說明哈希沖突非常嚴(yán)重了，不管有沒有有在執(zhí)行 RDB 快照或 AOF 重寫，都會強(qiáng)制進(jìn)行 rehash 操作。
整數(shù)集合
整數(shù)集合是 ?Set 對象的底層實現(xiàn)之一。當(dāng)一個 Set 對象只包含整數(shù)值元素，并且元素數(shù)量不時，就會使用整數(shù)集這個數(shù)據(jù)結(jié)構(gòu)作為底層實現(xiàn)。整數(shù)集合結(jié)構(gòu)設(shè)計
整數(shù)集合本質(zhì)上是一塊連續(xù)內(nèi)存空間，它的結(jié)構(gòu)定義如下：typedef?struct?intset?{
????//編碼方式
????uint32_t?encoding;
????//集合包含的元素數(shù)量
????uint32_t?length;
????//保存元素的數(shù)組
????int8_t?contents[];
}?intset;
可以看到，保存元素的容器是一個 contents 數(shù)組，雖然 contents 被聲明為 int8_t 類型的數(shù)組，但是實際上 contents 數(shù)組并不保存任何 int8_t 類型的元素，contents 數(shù)組的真正類型取決于 intset 結(jié)構(gòu)體里的 encoding 屬性的值。比如：- 如果 encoding 屬性值為 INTSET_ENC_INT16，那么 contents 就是一個 int16_t 類型的數(shù)組，數(shù)組中每一個元素的類型都是 int16_t；
- 如果 encoding 屬性值為 INTSET_ENC_INT32，那么 contents 就是一個 int32_t 類型的數(shù)組，數(shù)組中每一個元素的類型都是 int32_t；
- 如果 encoding 屬性值為 INTSET_ENC_INT64，那么 contents 就是一個 int64_t 類型的數(shù)組，數(shù)組中每一個元素的類型都是 int64_t；
整數(shù)集合的升級操作
整數(shù)集合會有一個升級規(guī)則，就是當(dāng)我們將一個新元素加入到整數(shù)集合里面，如果新元素的類型（int32_t）比整數(shù)集合現(xiàn)有所有元素的類型（int16_t）都要長時，整數(shù)集合需要先進(jìn)行升級，也就是按新元素的類型（int32_t）擴(kuò)展 contents 數(shù)組的空間大小，然后才能將新元素加入到整數(shù)集合里，當(dāng)然升級的過程中，也要維持整數(shù)集合的有序性。整數(shù)集合升級的過程不會重新分配一個新類型的數(shù)組，而是在原本的數(shù)組上擴(kuò)展空間，然后在將每個元素按間隔類型大小分割，如果 encoding 屬性值為 INTSET_ENC_INT16，則每個元素的間隔就是 16 位。舉個例子，假設(shè)有一個整數(shù)集合里有 3 個類型為 int16_t 的元素。整數(shù)集合升級有什么好處呢？如果要讓一個數(shù)組同時保存 int16_t、int32_t、int64_t 類型的元素，最簡單做法就是直接使用 int64_t 類型的數(shù)組。不過這樣的話，當(dāng)如果元素都是 int16_t 類型的，就會造成內(nèi)存浪費的情況。整數(shù)集合升級就能避免這種情況，如果一直向整數(shù)集合添加 int16_t 類型的元素，那么整數(shù)集合的底層實現(xiàn)就一直是用 int16_t 類型的數(shù)組，只有在我們要將 int32_t 類型或 int64_t 類型的元素添加到集合時，才會對數(shù)組進(jìn)行升級操作。因此，整數(shù)集合升級的好處是節(jié)省內(nèi)存資源。
整數(shù)集合支持降級操作嗎？不支持降級操作，一旦對數(shù)組進(jìn)行了升級，就會一直保持升級后的狀態(tài)。比如前面的升級操作的例子，如果刪除了 65535 元素，整數(shù)集合的數(shù)組還是 int32_t 類型的，并不會因此降級為 int16_t 類型。
跳表
Redis 只有在 Zset 對象的底層實現(xiàn)用到了跳表，跳表的優(yōu)勢是能支持平均 O(logN) 復(fù)雜度的節(jié)點查找。Zset 對象是唯一一個同時使用了兩個數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的 Redis 對象，這兩個數(shù)據(jù)結(jié)構(gòu)一個是跳表，一個是哈希表。這樣的好處是既能進(jìn)行高效的范圍查詢，也能進(jìn)行高效單點查詢。typedef?struct?zset?{
????dict?*dict;
????zskiplist?*zsl;
}?zset;
Zset 對象能支持范圍查詢（如 ZRANGEBYSCORE 操作），這是因為它的數(shù)據(jù)結(jié)構(gòu)設(shè)計采用了跳表，而又能以常數(shù)復(fù)雜度獲取元素權(quán)重（如 ZSCORE 操作），這是因為它同時采用了哈希表進(jìn)行索引。接下來，詳細(xì)的說下跳表。跳表結(jié)構(gòu)設(shè)計
鏈表在查找元素的時候，因為需要逐一查找，所以查詢效率非常低，時間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過來的，實現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。那跳表長什么樣呢？我這里舉個例子，下圖展示了一個層級為 3 的跳表。- L0 層級共有 5 個節(jié)點，分別是節(jié)點1、2、3、4、5；
- L1 層級共有 3 個節(jié)點，分別是節(jié)點 2、3、5；
- L2 層級只有 1 個節(jié)點，也就是節(jié)點 3 。
typedef?struct?zskiplistNode?{
????//Zset?對象的元素值
????sds?ele;
????//元素權(quán)重值
????double?score;
????//后向指針
????struct?zskiplistNode?*backward;
????//節(jié)點的level數(shù)組，保存每層上的前向指針和跨度
????struct?zskiplistLevel?{
????????struct?zskiplistNode?*forward;
????????unsigned?long?span;
????}?level[];
}?zskiplistNode;
Zset 對象要同時保存元素和元素的權(quán)重，對應(yīng)到跳表節(jié)點結(jié)構(gòu)里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節(jié)點都有一個后向指針，指向前一個節(jié)點，目的是為了方便從跳表的尾節(jié)點開始訪問節(jié)點，這樣倒序查找時很方便。跳表是一個帶有層級關(guān)系的鏈表，而且每一層級可以包含多個節(jié)點，每一個節(jié)點通過指針連接起來，實現(xiàn)這一特性就是靠跳表節(jié)點結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類型的 level 數(shù)組。level 數(shù)組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個跳表節(jié)點的指針」和「跨度」，跨度時用來記錄兩個節(jié)點之間的距離。比如，下面這張圖，展示了各個節(jié)點的跨度。typedef?struct?zskiplist?{
????struct?zskiplistNode?*header,?*tail;
????unsigned?long?length;
????int?level;
}?zskiplist;
跳表結(jié)構(gòu)里包含了：- 跳表的頭尾節(jié)點，便于在O(1)時間復(fù)雜度內(nèi)訪問跳表的頭節(jié)點和尾節(jié)點；
- 跳表的長度，便于在O(1)時間復(fù)雜度獲取跳表節(jié)點的數(shù)量；
- 跳表的最大層數(shù)，便于在O(1)時間復(fù)雜度獲取跳表中層高最大的那個節(jié)點的層數(shù)量；
跳表節(jié)點查詢過程
查找一個跳表節(jié)點的過程時，跳表會從頭節(jié)點的最高層開始，逐一遍歷每一層。在遍歷某一層的跳表節(jié)點時，會用跳表節(jié)點中的 SDS 類型的元素和元素的權(quán)重來進(jìn)行判斷，共有兩個判斷條件：- 如果當(dāng)前節(jié)點的權(quán)重「小于」要查找的權(quán)重時，跳表就會訪問該層上的下一個節(jié)點。
- 如果當(dāng)前節(jié)點的權(quán)重「等于」要查找的權(quán)重時，并且當(dāng)前節(jié)點的 SDS 類型數(shù)據(jù)「小于」要查找的數(shù)據(jù)時，跳表就會訪問該層上的下一個節(jié)點。
- 先從頭節(jié)點的最高層開始，L2 指向了「元素：abc，權(quán)重：3」節(jié)點，這個節(jié)點的權(quán)重比要查找節(jié)點的小，所以要訪問該層上的下一個節(jié)點；
- 但是該層上的下一個節(jié)點是空節(jié)點，于是就會跳到「元素：abc，權(quán)重：3」節(jié)點的下一層去找，也就是 leve[1];
- 「元素：abc，權(quán)重：3」節(jié)點的 ?leve[1] 的下一個指針指向了「元素：abcde，權(quán)重：4」的節(jié)點，然后將其和要查找的節(jié)點比較。雖然「元素：abcde，權(quán)重：4」的節(jié)點的權(quán)重和要查找的權(quán)重相同，但是當(dāng)前節(jié)點的 SDS 類型數(shù)據(jù)「大于」要查找的數(shù)據(jù)，所以會繼續(xù)跳到「元素：abc，權(quán)重：3」節(jié)點的下一層去找，也就是 leve[0]；
- 「元素：abc，權(quán)重：3」節(jié)點的 leve[0] 的下一個指針指向了「元素：abcd，權(quán)重：4」的節(jié)點，該節(jié)點正是要查找的節(jié)點，查詢結(jié)束。
跳表節(jié)點層數(shù)設(shè)置
跳表的相鄰兩層的節(jié)點數(shù)量的比例會影響跳表的查詢性能。舉個例子，下圖的跳表，第二層的節(jié)點數(shù)量只有 1 個，而第一層的節(jié)點數(shù)量有 6 個。那怎樣才能維持相鄰兩層的節(jié)點數(shù)量的比例為 2 : 1 ?呢？如果采用新增節(jié)點或者刪除節(jié)點時，來調(diào)整跳表節(jié)點以維持比例的方法的話，會帶來額外的開銷。Redis 則采用一種巧妙的方法是，跳表在創(chuàng)建節(jié)點的時候，隨機(jī)生成每個節(jié)點的層數(shù)，并沒有嚴(yán)格維持相鄰兩層的節(jié)點數(shù)量比例為 2 : 1 的情況。具體的做法是，跳表在創(chuàng)建節(jié)點時候，會生成范圍為[0-1]的一個隨機(jī)數(shù)，如果這個隨機(jī)數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個隨機(jī)數(shù)，直到隨機(jī)數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點的層數(shù)。這樣的做法，相當(dāng)于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。
quicklist
在 Redis 3.0 之前，List 對象的底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表或者壓縮列表。然后在 ?Redis 3.2 的時候，List 對象的底層改由 quicklist 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。其實 quicklist 就是「雙向鏈表 壓縮列表」組合，因為一個 quicklist 就是一個鏈表，而鏈表中的每個元素又是一個壓縮列表。在前面講壓縮列表的時候，我也提到了壓縮列表的不足，雖然壓縮列表是通過緊湊型的內(nèi)存布局節(jié)省了內(nèi)存開銷，但是因為它的結(jié)構(gòu)設(shè)計，如果保存的元素數(shù)量增加，或者元素變大了，壓縮列表會有「連鎖更新」的風(fēng)險，一旦發(fā)生，會造成性能下降。quicklist 解決辦法，通過控制每個鏈表節(jié)點中的壓縮列表的大小或者元素個數(shù)，來規(guī)避連鎖更新的問題。因為壓縮列表元素越少或越小，連鎖更新帶來的影響就越小，從而提供了更好的訪問性能。quicklist 結(jié)構(gòu)設(shè)計
quicklist 的結(jié)構(gòu)體跟鏈表的結(jié)構(gòu)體類似，都包含了表頭和表尾，區(qū)別在于 quicklist 的節(jié)點是 quicklistNode。typedef?struct?quicklist?{
????//quicklist的鏈表頭
????quicklistNode?*head;??????//quicklist的鏈表頭
????//quicklist的鏈表頭
????quicklistNode?*tail;?
????//所有壓縮列表中的總元素個數(shù)
????unsigned?long?count;
????//quicklistNodes的個數(shù)
????unsigned?long?len;???????
????...
}?quicklist;
接下來看看，quicklistNode 的結(jié)構(gòu)定義：typedef?struct?quicklistNode?{
????//前一個quicklistNode
????struct?quicklistNode?*prev;?????//前一個quicklistNode
????//下一個quicklistNode
????struct?quicklistNode?*next;?????//后一個quicklistNode
????//quicklistNode指向的壓縮列表
????unsigned?char?*zl;??????????????
????//壓縮列表的的字節(jié)大小
????unsigned?int?sz;????????????????
????//壓縮列表的元素個數(shù)
????unsigned?int?count?:?16;????????//ziplist中的元素個數(shù)?
????....
}?quicklistNode;
可以看到，quicklistNode 結(jié)構(gòu)體里包含了前一個節(jié)點和下一個節(jié)點指針，這樣每個 quicklistNode 形成了一個雙向鏈表。但是鏈表節(jié)點的元素不再是單純保存元素值，而是保存了一個壓縮列表，所以 quicklistNode 結(jié)構(gòu)體里有個指向壓縮列表的指針 *zl。我畫了一張圖，方便你理解 quicklist 數(shù)據(jù)結(jié)構(gòu)。在向 quicklist 添加一個元素的時候，不會像普通的鏈表那樣，直接新建一個鏈表節(jié)點。而是會檢查插入位置的壓縮列表是否能容納該元素，如果能容納就直接保存到 quicklistNode 結(jié)構(gòu)里的壓縮列表，如果不能容納，才會新建一個新的 quicklistNode 結(jié)構(gòu)。quicklist 會控制 quicklistNode 結(jié)構(gòu)里的壓縮列表的大小或者元素個數(shù)，來規(guī)避潛在的連鎖更新的風(fēng)險，但是這并沒有完全解決連鎖更新的問題。listpack
quicklist 雖然通過控制 quicklistNode 結(jié)構(gòu)里的壓縮列表的大小或者元素個數(shù)，來減少連鎖更新帶來的性能影響，但是并沒有完全解決連鎖更新的問題。因為 quicklistNode 還是用了壓縮列表來保存元素，壓縮列表連鎖更新的問題，來源于它的結(jié)構(gòu)設(shè)計，所以要想徹底解決這個問題，需要設(shè)計一個新的數(shù)據(jù)結(jié)構(gòu)。于是，Redis 在 5.0 新設(shè)計一個數(shù)據(jù)結(jié)構(gòu)叫 listpack，目的是替代壓縮列表，它最大特點是 listpack 中每個節(jié)點不再包含前一個節(jié)點的長度了，壓縮列表每個節(jié)點正因為需要保存前一個節(jié)點的長度字段，就會有連鎖更新的隱患。我看了 Redis 的 Github，在最新 ?6.2 發(fā)行版本中，Redis Hash 對象、Set 對象的底層數(shù)據(jù)結(jié)構(gòu)的壓縮列表還未被替換成 listpack，而 Redis 的最新代碼（還未發(fā)布版本）已經(jīng)將所有用到壓縮列表底層數(shù)據(jù)結(jié)構(gòu)的 Redis 對象替換成 listpack 數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，估計不久將來，Redis 就會發(fā)布一個將壓縮列表為 listpack 的發(fā)行版本。listpack 結(jié)構(gòu)設(shè)計
listpack 采用了壓縮列表的很多優(yōu)秀的設(shè)計，比如還是用一塊連續(xù)的內(nèi)存空間來緊湊地保存數(shù)據(jù)，并且為了節(jié)省內(nèi)存的開銷，listpack 節(jié)點會采用不同的編碼方式保存不同大小的數(shù)據(jù)。我們先看看 listpack 結(jié)構(gòu)：- encoding，定義該元素的編碼類型，會對不同長度的整數(shù)和字符串進(jìn)行編碼；
- data，實際存放的數(shù)據(jù)；
- len，encoding data的總長度；
參考資料：
- 《Redis設(shè)計與實現(xiàn)》
- 《Redis 源碼剖析與實戰(zhàn)》
下載文檔
