2w 字，40 張手繪圖帶你搞定 Redis 數(shù)據(jù)結(jié)構(gòu)

正文

Redis 為什么那么快？

除了它是內(nèi)存數(shù)據(jù)庫，使得所有的操作都在內(nèi)存上進(jìn)行之外，還有一個(gè)重要因素，它實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，使得我們對(duì)數(shù)據(jù)進(jìn)行增刪查改操作時(shí)，Redis 能高效的處理。

因此，這次我們就來好好聊一下 Redis 數(shù)據(jù)結(jié)構(gòu)，這個(gè)在面試中太常問了。

注意，Redis 數(shù)據(jù)結(jié)構(gòu)并不是指 String（字符串）對(duì)象、List（列表）對(duì)象、Hash（哈希）對(duì)象、Set（集合）對(duì)象和 Zset（有序集合）對(duì)象，因?yàn)檫@些是 Redis 鍵值對(duì)中值的數(shù)據(jù)類型，也就是數(shù)據(jù)的保存形式，這些對(duì)象的底層實(shí)現(xiàn)的方式就用到了數(shù)據(jù)結(jié)構(gòu)。

我畫了一張 Redis 數(shù)據(jù)類型（也叫 Redis 對(duì)象）和底層數(shù)據(jù)結(jié)構(gòu)的對(duì)應(yīng)關(guān)圖，左邊是 Redis 3.0版本的，也就是《Redis 設(shè)計(jì)與實(shí)現(xiàn)》這本書講解的版本，現(xiàn)在看還是有點(diǎn)過時(shí)了，右邊是現(xiàn)在 Github 最新的 Redis 代碼的（還未發(fā)布正式版本）。

可以看到，Redis 數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)隨著版本的更新也有所不同，比如：

• 在 Redis 3.0 版本中 List 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)由「雙向鏈表」或「壓縮表列表」實(shí)現(xiàn)，但是在 3.2 版本之后，List 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)是由 quicklist 實(shí)現(xiàn)的；

• 在最新的 Redis 代碼（還未發(fā)布正式版本）中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)了。

這次，我把新舊版本的數(shù)據(jù)結(jié)構(gòu)說圖解一遍，共有 9 種數(shù)據(jù)結(jié)構(gòu)：SDS、雙向鏈表、壓縮列表、哈希表、跳表、整數(shù)集合、quicklist、listpack。

不多 BB 了，直接發(fā)車！

鍵值對(duì)數(shù)據(jù)庫是怎么實(shí)現(xiàn)的？

在開始講數(shù)據(jù)結(jié)構(gòu)之前，先給介紹下 Redis 是怎樣實(shí)現(xiàn)鍵值對(duì)（key-value）數(shù)據(jù)庫的。

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

舉個(gè)例子，我這里列出幾種 Redis 新增鍵值對(duì)的命令：

>?SET?name?"xiaolincoding"
OK

>?HSET?person?name?"xiaolincoding"?age?18
0

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

這些命令代表著：

• 第一條命令：name 是一個(gè)字符串鍵，因?yàn)殒I的值是一個(gè)字符串對(duì)象；

• 第二條命令：person 是一個(gè)哈希表鍵，因?yàn)殒I的值是一個(gè)包含兩個(gè)鍵值對(duì)的哈希表對(duì)象；

• 第三條命令：stu 是一個(gè)列表鍵，因?yàn)殒I的值是一個(gè)包含兩個(gè)元素的列表對(duì)象；

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

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

Redis 的哈希桶是怎么保存鍵值對(duì)數(shù)據(jù)的呢？

哈希桶存放的是指向鍵值對(duì)數(shù)據(jù)的指針（dictEntry*），這樣通過指針就能找到鍵值對(duì)數(shù)據(jù)，然后因?yàn)殒I值對(duì)的值可以保存字符串對(duì)象和集合數(shù)據(jù)類型的對(duì)象，所以鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)中并不是直接保存值本身，而是保存了 void * key 和 void * value 指針，分別指向了實(shí)際的鍵對(duì)象和值對(duì)象，這樣一來，即使值是集合數(shù)據(jù)，也可以通過 void * value 指針找到。

我這里畫了一張 Redis 保存鍵值對(duì)所涉及到的數(shù)據(jù)結(jié)構(gòu)。

這些數(shù)據(jù)結(jié)構(gòu)的內(nèi)部細(xì)節(jié)，我先不展開講，后面在講哈希表數(shù)據(jù)結(jié)構(gòu)的時(shí)候，在詳細(xì)的說說，因?yàn)橛玫降臄?shù)據(jù)結(jié)構(gòu)是一樣的。這里先大概說下圖中涉及到的數(shù)據(jù)結(jié)構(gòu)的名字和用途：

• 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 個(gè)哈希表，正常情況下都是用「哈希表1」，「哈希表2」只有在 rehash 的時(shí)候才用，具體什么是 rehash，我在本文的哈希表數(shù)據(jù)結(jié)構(gòu)會(huì)講；

• ditctht 結(jié)構(gòu)，表示哈希表的結(jié)構(gòu)，結(jié)構(gòu)里存放了哈希表數(shù)組，數(shù)組中的每個(gè)元素都是指向一個(gè)哈希表節(jié)點(diǎn)結(jié)構(gòu)（dictEntry）的指針；

• dictEntry 結(jié)構(gòu)，表示哈希表節(jié)點(diǎn)的結(jié)構(gòu)，結(jié)構(gòu)里存放了 void * key 和 void * value 指針， *key 指向的是 String 對(duì)象，而 *value 則可以指向 String 對(duì)象，也可以指向集合類型的對(duì)象，比如 List 對(duì)象、Hash 對(duì)象、Set 對(duì)象和 Zset 對(duì)象。

特別說明下，void * key 和 void * value 指針指向的是 Redis 對(duì)象，Redis 中的每個(gè)對(duì)象都由 redisObject 結(jié)構(gòu)表示，如下圖：

對(duì)象結(jié)構(gòu)里包含的成員變量：

• type，標(biāo)識(shí)該對(duì)象是什么類型的對(duì)象（String 對(duì)象、 List 對(duì)象、Hash 對(duì)象、Set 對(duì)象和 Zset 對(duì)象）；

• encoding，標(biāo)識(shí)該對(duì)象使用了哪種底層的數(shù)據(jù)結(jié)構(gòu)；

• ptr，指向底層數(shù)據(jù)結(jié)構(gòu)的指針。

我畫了一張 Redis 鍵值對(duì)數(shù)據(jù)庫的全景圖，你就能清晰知道 Redis 對(duì)象和數(shù)據(jù)結(jié)構(gòu)的關(guān)系了：

接下里，就好好聊一下底層數(shù)據(jù)結(jié)構(gòu)！

SDS

字符串在 Redis 中是很常用的，鍵值對(duì)中的鍵是字符串類型，值有時(shí)也是字符串類型。

Redis 是用 C 語言實(shí)現(xiàn)的，但是它沒有直接使用 C 語言的 char* 字符數(shù)組來實(shí)現(xiàn)字符串，而是自己封裝了一個(gè)名為簡單動(dòng)態(tài)字符串（simple dynamic string，SDS） 的數(shù)據(jù)結(jié)構(gòu)來表示字符串，也就是 Redis 的 String 數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)是 SDS。

既然 Redis 設(shè)計(jì)了 SDS 結(jié)構(gòu)來表示字符串，肯定是 C 語言的 char* 字符數(shù)組存在一些缺陷。

要了解這一點(diǎn)，得先來看看 char* 字符數(shù)組的結(jié)構(gòu)。

C 語言字符串的缺陷

C 語言的字符串其實(shí)就是一個(gè)字符數(shù)組，即數(shù)組中每個(gè)元素是字符串中的一個(gè)字符。

比如，下圖就是字符串“xiaolin”的 char* 字符數(shù)組的結(jié)構(gòu)：

沒學(xué)過 C 語言的同學(xué)，可能會(huì)好奇為什么最后一個(gè)字符是“\0”？

在 C 語言里，對(duì)字符串操作時(shí)，char * 指針只是指向字符數(shù)組的起始位置，而字符數(shù)組的結(jié)尾位置就用“\0”表示，意思是指字符串的結(jié)束。

因此，C 語言標(biāo)準(zhǔn)庫中的字符串操作函數(shù)就通過判斷字符是不是 “\0” 來決定要不要停止操作，如果當(dāng)前字符不是 “\0” ，說明字符串還沒結(jié)束，可以繼續(xù)操作，如果當(dāng)前字符是 “\0” ?是則說明字符串結(jié)束了，就要停止操作。

舉個(gè)例子，C 語言獲取字符串長度的函數(shù) strlen，就是通過字符數(shù)組中的每一個(gè)字符，并進(jìn)行計(jì)數(shù)，等遇到字符為 “\0” 后，就會(huì)停止遍歷，然后返回已經(jīng)統(tǒng)計(jì)到的字符個(gè)數(shù)，即為字符串長度。下圖顯示了 strlen 函數(shù)的執(zhí)行流程：

很明顯，C 語言獲取字符串長度的時(shí)間復(fù)雜度是 O（N）（這是一個(gè)可以改進(jìn)的地方）

C 語言字符串用 “\0” 字符作為結(jié)尾標(biāo)記有個(gè)缺陷。假設(shè)有個(gè)字符串中有個(gè) “\0” 字符，這時(shí)在操作這個(gè)字符串時(shí)就會(huì)提早結(jié)束，比如 “xiao\0lin” 字符串，計(jì)算字符串長度的時(shí)候則會(huì)是 4，如下圖：

因此，除了字符串的末尾之外，字符串里面不能含有 “\0” 字符，否則最先被程序讀入的 “\0” 字符將被誤認(rèn)為是字符串結(jié)尾，這個(gè)限制使得 C 語言的字符串只能保存文本數(shù)據(jù)，不能保存像圖片、音頻、視頻文化這樣的二進(jìn)制數(shù)據(jù)（這也是一個(gè)可以改進(jìn)的地方）

另外， C 語言標(biāo)準(zhǔn)庫中字符串的操作函數(shù)是很不安全的，對(duì)程序員很不友好，稍微一不注意，就會(huì)導(dǎo)致緩沖區(qū)溢出。

舉個(gè)例子，strcat 函數(shù)是可以將兩個(gè)字符串拼接在一起。

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

C 語言的字符串是不會(huì)記錄自身的緩沖區(qū)大小的，所以 strcat 函數(shù)假定程序員在執(zhí)行這個(gè)函數(shù)時(shí)，已經(jīng)為 dest 分配了足夠多的內(nèi)存，可以容納 src 字符串中的所有內(nèi)容，而一旦這個(gè)假定不成立，就會(huì)發(fā)生緩沖區(qū)溢出將可能會(huì)造成程序運(yùn)行終止，（這是一個(gè)可以改進(jìn)的地方）。

而且，strcat 函數(shù)和 strlen 函數(shù)類似，時(shí)間復(fù)雜度也很高，也都需要先通過遍歷字符串才能得到目標(biāo)字符串的末尾。然后對(duì)于 strcat 函數(shù)來說，還要再遍歷源字符串才能完成追加，對(duì)字符串的操作效率不高。

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

• 獲取字符串長度的時(shí)間復(fù)雜度為 ?O（N）；

• 字符串的結(jié)尾是以 “\0” 字符標(biāo)識(shí)，字符串里面不能包含有 “\0” 字符，因此不能保存二進(jìn)制數(shù)據(jù)；

• 字符串操作函數(shù)不高效且不安全，比如有緩沖區(qū)溢出的風(fēng)險(xiǎn)，有可能會(huì)造成程序運(yùn)行終止；

Redis 實(shí)現(xiàn)的 SDS 的結(jié)構(gòu)就把上面這些問題解決了，接下來我們一起看看 Redis 是如何解決的。

SDS 結(jié)構(gòu)設(shè)計(jì)

下圖就是 Redis 5.0 的 SDS 的數(shù)據(jù)結(jié)構(gòu)：

結(jié)構(gòu)中的每個(gè)成員變量分別介紹下：

• len，記錄了字符串長度。這樣獲取字符串長度的時(shí)候，只需要返回這個(gè)成員變量值就行，時(shí)間復(fù)雜度只需要 O（1）。

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

• flags，用來表示不同類型的 SDS。一共設(shè)計(jì)了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說明區(qū)別之處。

• buf[]，字符數(shù)組，用來保存實(shí)際數(shù)據(jù)。不僅可以保存字符串，也可以保存二進(jìn)制數(shù)據(jù)。

總的來說，Redis 的 SDS 結(jié)構(gòu)在原本字符數(shù)組之上，增加了三個(gè)元數(shù)據(jù)：len、alloc、flags，用來解決 C 語言字符串的缺陷。

O（1）復(fù)雜度獲取字符串長度

C 語言的字符串長度獲取 strlen 函數(shù)，需要通過遍歷的方式來統(tǒng)計(jì)字符串長度，時(shí)間復(fù)雜度是 O（N）。

而 Redis 的 SDS 結(jié)構(gòu)因?yàn)榧尤肓?len 成員變量，那么獲取字符串長度的時(shí)候，直接返回這個(gè)成員變量的值就行，所以復(fù)雜度只有 O（1）。

二進(jìn)制安全

因?yàn)?SDS 不需要用 “\0” 字符來標(biāo)識(shí)字符串結(jié)尾了，而是有個(gè)專門的 len 成員變量來記錄長度，所以可存儲(chǔ)包含 “\0” 的數(shù)據(jù)。但是 SDS 為了兼容部分 C 語言標(biāo)準(zhǔn)庫的函數(shù)， SDS 字符串結(jié)尾還是會(huì)加上 “\0” 字符。

因此， SDS 的 API 都是以處理二進(jìn)制的方式來處理 SDS 存放在 buf[] 里的數(shù)據(jù)，程序不會(huì)對(duì)其中的數(shù)據(jù)做任何限制，數(shù)據(jù)寫入的時(shí)候時(shí)什么樣的，它被讀取時(shí)就是什么樣的。

通過使用二進(jìn)制安全的 SDS，而不是 C 字符串，使得 Redis 不僅可以保存文本數(shù)據(jù)，也可以保存任意格式的二進(jìn)制數(shù)據(jù)。

不會(huì)發(fā)生緩沖區(qū)溢出

C 語言的字符串標(biāo)準(zhǔn)庫提供的字符串操作函數(shù)，大多數(shù)（比如 strcat 追加字符串函數(shù)）都是不安全的，因?yàn)檫@些函數(shù)把緩沖區(qū)大小是否滿足操作需求的工作交由開發(fā)者來保證，程序內(nèi)部并不會(huì)判斷緩沖區(qū)大小是否足夠用，當(dāng)發(fā)生了緩沖區(qū)溢出就有可能造成程序異常結(jié)束。

所以，Redis 的 SDS 結(jié)構(gòu)里引入了 alloc 和 len 成員變量，這樣 SDS API 通過 alloc - len 計(jì)算，可以算出剩余可用的空間大小，這樣在對(duì)字符串做修改操作的時(shí)候，就可以由程序內(nèi)部判斷緩沖區(qū)大小是否足夠用。

而且，當(dāng)判斷出緩沖區(qū)大小不夠用時(shí)，Redis 會(huì)自動(dòng)將擴(kuò)大 SDS 的空間大小（小于 1MB 翻倍擴(kuò)容，大于 1MB 按 1MB 擴(kuò)容），以滿足修改所需的大小。

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

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

所以，使用 SDS 即不需要手動(dòng)修改 SDS 的空間大小，也不會(huì)出現(xiàn)緩沖區(qū)溢出的問題。

節(jié)省內(nèi)存空間

SDS 結(jié)構(gòu)中有個(gè) flags 成員變量，表示的是 SDS 類型。

Redos 一共設(shè)計(jì)了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。

這 5 種類型的主要區(qū)別就在于，它們數(shù)據(jù)結(jié)構(gòu)中的 len 和 alloc 成員變量的數(shù)據(jù)類型不同。

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

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 次方。

之所以 SDS 設(shè)計(jì)不同類型的結(jié)構(gòu)體，是為了能靈活保存不同大小的字符串，從而有效節(jié)省內(nèi)存空間。比如，在保存小字符串時(shí)，結(jié)構(gòu)頭占用空間也比較少。

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

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

舉個(gè)例子，假設(shè)下面這個(gè)結(jié)構(gòu)體，它有兩個(gè)成員變量，類型分別是 char 和 int，如下所示：

#include?

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

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

大家猜猜這個(gè)結(jié)構(gòu)體大小是多少？我先直接說答案，這個(gè)結(jié)構(gòu)體大小計(jì)算出來是 8。

這是因?yàn)槟J(rèn)情況下，編譯器是使用「字節(jié)對(duì)齊」的方式分配內(nèi)存，雖然 char 類型只占一個(gè)字節(jié)，但是由于成員變量里有 int 類型，它占用了 4 個(gè)字節(jié)，所以在成員變量為 char 類型分配內(nèi)存時(shí)，會(huì)分配 4 個(gè)字節(jié)，其中這多余的 3 個(gè)字節(jié)是為了字節(jié)對(duì)齊而分配的，相當(dāng)于有 3 個(gè)字節(jié)被浪費(fèi)掉了。

如果不想編譯器使用字節(jié)對(duì)齊的方式進(jìn)行分配內(nèi)存，可以采用了 __attribute__ ((packed)) 屬性定義結(jié)構(gòu)體，這樣一來，結(jié)構(gòu)體實(shí)際占用多少內(nèi)存空間，編譯器就分配多少空間。

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

#include?

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

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

這時(shí)打印的結(jié)果是 5（1 個(gè)字節(jié) char ?+ 4 字節(jié) int）。

可以看得出，這是按照實(shí)際占用字節(jié)數(shù)進(jìn)行分配內(nèi)存的，這樣可以節(jié)省內(nèi)存空間。

鏈表

大家最熟悉的數(shù)據(jù)結(jié)構(gòu)除了數(shù)組之外，我相信就是鏈表了。

Redis 的 List 對(duì)象的底層實(shí)現(xiàn)之一就是鏈表。C 語言本身沒有鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)的，所以 Redis 自己設(shè)計(jì)了一個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)。

鏈表節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)

先來看看「鏈表節(jié)點(diǎn)」結(jié)構(gòu)的樣子：

typedef?struct?listNode?{
????//前置節(jié)點(diǎn)
????struct?listNode?*prev;
????//后置節(jié)點(diǎn)
????struct?listNode?*next;
????//節(jié)點(diǎn)的值
????void?*value;
}?listNode;

有前置節(jié)點(diǎn)和后置節(jié)點(diǎn)，可以看的出，這個(gè)是一個(gè)雙向鏈表。

鏈表結(jié)構(gòu)設(shè)計(jì)

不過，Redis 在 listNode 結(jié)構(gòu)體基礎(chǔ)上又封裝了 list 這個(gè)數(shù)據(jù)結(jié)構(gòu)，這樣操作起來會(huì)更方便，鏈表結(jié)構(gòu)如下：

typedef?struct?list?{
????//鏈表頭節(jié)點(diǎn)
????listNode?*head;
????//鏈表尾節(jié)點(diǎn)
????listNode?*tail;
????//節(jié)點(diǎn)值復(fù)制函數(shù)
????void?*(*dup)(void?*ptr);
????//節(jié)點(diǎn)值釋放函數(shù)
????void?(*free)(void?*ptr);
????//節(jié)點(diǎn)值比較函數(shù)
????int?(*match)(void?*ptr,?void?*key);
????//鏈表節(jié)點(diǎn)數(shù)量
????unsigned?long?len;
}?list;

list 結(jié)構(gòu)為鏈表提供了鏈表頭指針 head、鏈表尾節(jié)點(diǎn) tail、鏈表節(jié)點(diǎn)數(shù)量 len、以及可以自定義實(shí)現(xiàn)的 dup、free、match 函數(shù)。

舉個(gè)例子，下面是由 list 結(jié)構(gòu)和 3 個(gè) listNode 結(jié)構(gòu)組成的鏈表。

鏈表的優(yōu)勢(shì)與缺陷

Redis 的鏈表實(shí)現(xiàn)優(yōu)點(diǎn)如下：

• listNode 鏈表節(jié)點(diǎn)的結(jié)構(gòu)里帶有 prev 和 next 指針，獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)或后置節(jié)點(diǎn)的時(shí)間復(fù)雜度只需O(1)，而且這兩個(gè)指針都可以指向 NULL，所以鏈表是無環(huán)鏈表；

• list 結(jié)構(gòu)因?yàn)樘峁┝吮眍^指針 head 和表尾節(jié)點(diǎn) tail，所以獲取鏈表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的時(shí)間復(fù)雜度只需O(1)；

• list 結(jié)構(gòu)因?yàn)樘峁┝随湵砉?jié)點(diǎn)數(shù)量 len，所以獲取鏈表中的節(jié)點(diǎn)數(shù)量的時(shí)間復(fù)雜度只需O(1)；

• listNode 鏈表節(jié)使用 void* 指針保存節(jié)點(diǎn)值，并且可以通過 list 結(jié)構(gòu)的 dup、free、match 函數(shù)指針為節(jié)點(diǎn)設(shè)置該節(jié)點(diǎn)類型特定的函數(shù)，因此鏈表節(jié)點(diǎn)可以保存各種不同類型的值；

鏈表的缺陷也是有的：

• 鏈表每個(gè)節(jié)點(diǎn)之間的內(nèi)存都是不連續(xù)的，意味著無法很好利用 CPU 緩存。能很好利用 CPU 緩存的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，因?yàn)閿?shù)組的內(nèi)存是連續(xù)的，這樣就可以充分利用 CPU 緩存來加速訪問。

• 還有一點(diǎn)，保存一個(gè)鏈表節(jié)點(diǎn)的值都需要一個(gè)鏈表節(jié)點(diǎn)結(jié)構(gòu)頭的分配，內(nèi)存開銷較大。

因此，Redis 3.0 的 List 對(duì)象在數(shù)據(jù)量比較少的情況下，會(huì)采用「壓縮列表」作為底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，它的優(yōu)勢(shì)是節(jié)省內(nèi)存空間，并且是內(nèi)存緊湊型的數(shù)據(jù)結(jié)構(gòu)。

不過，壓縮列表存在性能問題（具體什么問題，下面會(huì)說），所以 Redis 在 3.2 版本設(shè)計(jì)了新的數(shù)據(jù)結(jié)構(gòu) quicklist，并將 List 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)改由 quicklist 實(shí)現(xiàn)。

然后在 ?Redis 5.0 設(shè)計(jì)了新的數(shù)據(jù)結(jié)構(gòu) listpack，沿用了壓縮列表緊湊型的內(nèi)存布局，最終在最新的 Redis 版本，將 Hash 對(duì)象和 Zset 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)之一的壓縮列表，替換成由 ?listpack 實(shí)現(xiàn)。

壓縮列表

壓縮列表的最大特點(diǎn)，就是它被設(shè)計(jì)成一種內(nèi)存緊湊型的數(shù)據(jù)結(jié)構(gòu)，占用一塊連續(xù)的內(nèi)存空間，不僅可以利用 CPU 緩存，而且會(huì)針對(duì)不同長度的數(shù)據(jù)，進(jìn)行相應(yīng)編碼，這種方法可以有效地節(jié)省內(nèi)存開銷。

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

• 不能保存過多的元素，否則查詢效率就會(huì)降低；

• 新增或修改某個(gè)元素時(shí)，壓縮列表占用的內(nèi)存空間需要重新分配，甚至可能引發(fā)連鎖更新的問題。

因此，Redis 對(duì)象（List 對(duì)象、Hash 對(duì)象、Zset 對(duì)象）包含的元素?cái)?shù)量較少，或者元素值不大的情況才會(huì)使用壓縮列表作為底層數(shù)據(jù)結(jié)構(gòu)。

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

壓縮列表結(jié)構(gòu)設(shè)計(jì)

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的，它是由連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，有點(diǎn)類似于數(shù)組。

壓縮列表在表頭有三個(gè)字段：

• zlbytes，記錄整個(gè)壓縮列表占用對(duì)內(nèi)存字節(jié)數(shù)；

• zltail，記錄壓縮列表「尾部」節(jié)點(diǎn)距離起始地址由多少字節(jié)，也就是列表尾的偏移量；

• zllen，記錄壓縮列表包含的節(jié)點(diǎn)數(shù)量；

• zlend，標(biāo)記壓縮列表的結(jié)束點(diǎn)，固定值 0xFF（十進(jìn)制255）。

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

另外，壓縮列表節(jié)點(diǎn)（entry）的構(gòu)成如下：

壓縮列表節(jié)點(diǎn)包含三部分內(nèi)容：

• prevlen，記錄了「前一個(gè)節(jié)點(diǎn)」的長度；

• encoding，記錄了當(dāng)前節(jié)點(diǎn)實(shí)際數(shù)據(jù)的類型以及長度；

• data，記錄了當(dāng)前節(jié)點(diǎn)的實(shí)際數(shù)據(jù)；

當(dāng)我們往壓縮列表中插入數(shù)據(jù)時(shí)，壓縮列表就會(huì)根據(jù)數(shù)據(jù)是字符串還是整數(shù)，以及數(shù)據(jù)的大小，會(huì)使用不同空間大小的 prevlen 和 encoding 這兩個(gè)元素里保存的信息，這種根據(jù)數(shù)據(jù)大小和類型進(jìn)行不同的空間大小分配的設(shè)計(jì)思想，正是 Redis 為了節(jié)省內(nèi)存而采用的。

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

壓縮列表里的每個(gè)節(jié)點(diǎn)中的 ?prevlen 屬性都記錄了「前一個(gè)節(jié)點(diǎn)的長度」，而且 prevlen 屬性的空間大小跟前一個(gè)節(jié)點(diǎn)長度值有關(guān)，比如：

• 如果前一個(gè)節(jié)點(diǎn)的長度小于 254 字節(jié)，那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個(gè)長度值；

• 如果前一個(gè)節(jié)點(diǎn)的長度大于等于 254 字節(jié)，那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個(gè)長度值；

encoding 屬性的空間大小跟數(shù)據(jù)是字符串還是整數(shù)，以及字符串的長度有關(guān)：

• 如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)是整數(shù)，則 encoding 會(huì)使用 1 字節(jié)的空間進(jìn)行編碼。

• 如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)是字符串，根據(jù)字符串的長度大小，encoding 會(huì)使用 1 字節(jié)/2字節(jié)/5字節(jié)的空間進(jìn)行編碼。

連鎖更新

壓縮列表除了查找復(fù)雜度高的問題，還有一個(gè)問題。

壓縮列表新增某個(gè)元素或修改某個(gè)元素時(shí)，如果空間不不夠，壓縮列表占用的內(nèi)存空間就需要重新分配。而當(dāng)新插入的元素較大時(shí)，可能會(huì)導(dǎo)致后續(xù)元素的 prevlen 占用空間都發(fā)生變化，從而引起「連鎖更新」問題，導(dǎo)致每個(gè)元素的空間都要重新分配，造成訪問壓縮列表性能的下降。

前面提到，壓縮列表節(jié)點(diǎn)的 prevlen 屬性會(huì)根據(jù)前一個(gè)節(jié)點(diǎn)的長度進(jìn)行不同的空間大小分配：

• 如果前一個(gè)節(jié)點(diǎn)的長度小于 254 字節(jié)，那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個(gè)長度值；

• 如果前一個(gè)節(jié)點(diǎn)的長度大于等于 254 字節(jié)，那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個(gè)長度值；

現(xiàn)在假設(shè)一個(gè)壓縮列表中有多個(gè)連續(xù)的、長度在 250～253 之間的節(jié)點(diǎn)，如下圖：

因?yàn)檫@些節(jié)點(diǎn)長度值小于 254 字節(jié)，所以 prevlen 屬性需要用 1 字節(jié)的空間來保存這個(gè)長度值。

這時(shí)，如果將一個(gè)長度大于等于 254 字節(jié)的新節(jié)點(diǎn)加入到壓縮列表的表頭節(jié)點(diǎn)，即新節(jié)點(diǎn)將成為 e1 的前置節(jié)點(diǎn)，如下圖：

因?yàn)?e1 節(jié)點(diǎn)的 prevlen 屬性只有 1 個(gè)字節(jié)大小，無法保存新節(jié)點(diǎn)的長度，此時(shí)就需要對(duì)壓縮列表的空間重分配操作，并將 e1 節(jié)點(diǎn)的 prevlen 屬性從原來的 1 字節(jié)大小擴(kuò)展為 5 字節(jié)大小。

多米諾牌的效應(yīng)就此開始。

e1 原本的長度在 250～253 之間，因?yàn)閯偛诺臄U(kuò)展空間，此時(shí) e1 的長度就大于等于 254 了，因此原本 e2 保存 e1 的 prevlen 屬性也必須從 1 字節(jié)擴(kuò)展至 5 字節(jié)大小。

正如擴(kuò)展 e1 引發(fā)了對(duì) e2 擴(kuò)展一樣，擴(kuò)展 e2 也會(huì)引發(fā)對(duì) e3 的擴(kuò)展，而擴(kuò)展 e3 又會(huì)引發(fā)對(duì) e4 的擴(kuò)展…. 一直持續(xù)到結(jié)尾。

這種在特殊情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作就叫做「連鎖更新」，就像多米諾牌的效應(yīng)一樣，第一張牌倒下了，推動(dòng)了第二張牌倒下；第二張牌倒下，又推動(dòng)了第三張牌倒下….，

壓縮列表的缺陷

空間擴(kuò)展操作也就是重新分配內(nèi)存，因此連鎖更新一旦發(fā)生，就會(huì)導(dǎo)致壓縮列表占用的內(nèi)存空間要多次重新分配，這就會(huì)直接影響到壓縮列表的訪問性能。

所以說，雖然壓縮列表緊湊型的內(nèi)存布局能節(jié)省內(nèi)存開銷，但是如果保存的元素?cái)?shù)量增加了，或是元素變大了，會(huì)導(dǎo)致內(nèi)存重新分配，最糟糕的是會(huì)有「連鎖更新」的問題。

因此，壓縮列表只會(huì)用于保存的節(jié)點(diǎn)數(shù)量不多的場景，只要節(jié)點(diǎn)數(shù)量足夠小，即使發(fā)生連鎖更新，也是能接受的。

雖說如此，Redis 針對(duì)壓縮列表在設(shè)計(jì)上的不足，在后來的版本中，新增設(shè)計(jì)了兩種數(shù)據(jù)結(jié)構(gòu)：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。這兩種數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)目標(biāo)，就是盡可能地保持壓縮列表節(jié)省內(nèi)存的優(yōu)勢(shì)，同時(shí)解決壓縮列表的「連鎖更新」的問題。

哈希表

哈希表是一種保存鍵值對(duì)（key-value）的數(shù)據(jù)結(jié)構(gòu)。

哈希表中的每一個(gè) key 都是獨(dú)一無二的，程序可以根據(jù) key 查找到與之關(guān)聯(lián)的 value，或者通過 key 來更新 value，又或者根據(jù) key 來刪除整個(gè) key-value等等。

在講壓縮列表的時(shí)候，提到過 Redis 的 Hash 對(duì)象的底層實(shí)現(xiàn)之一是壓縮列表（最新 Redis 代碼已將壓縮列表替換成 listpack）。Hash 對(duì)象的另外一個(gè)底層實(shí)現(xiàn)就是哈希表。

哈希表優(yōu)點(diǎn)在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。怎么做到的呢？將 key 通過 Hash 函數(shù)的計(jì)算，就能定位數(shù)據(jù)在表中的位置，因?yàn)楣１韺?shí)際上是數(shù)組，所以可以通過索引值快速查詢到數(shù)據(jù)。

但是存在的風(fēng)險(xiǎn)也是有，在哈希表大小固定的情況下，隨著數(shù)據(jù)不斷增多，那么哈希沖突的可能性也會(huì)越高。

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

Redis 采用了「鏈?zhǔn)焦！箒斫鉀Q哈希沖突，在不擴(kuò)容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)串起來，形成鏈接起，以便這些數(shù)據(jù)在表中仍然可以被查詢到。

接下來，詳細(xì)說說哈希表。

哈希表結(jié)構(gòu)設(shè)計(jì)

Redis 的哈希表結(jié)構(gòu)如下：

typedef?struct?dictht?{
????//哈希表數(shù)組
????dictEntry?**table;
????//哈希表大小
????unsigned?long?size;??
????//哈希表大小掩碼，用于計(jì)算索引值
????unsigned?long?sizemask;
????//該哈希表已有的節(jié)點(diǎn)數(shù)量
????unsigned?long?used;
}?dictht;

可以看到，哈希表是一個(gè)數(shù)組（dictEntry **table），數(shù)組的每個(gè)元素是一個(gè)指向「哈希表節(jié)點(diǎn)（dictEntry）」的指針。

哈希表節(jié)點(diǎn)的結(jié)構(gòu)如下：

typedef?struct?dictEntry?{
????//鍵值對(duì)中的鍵
????void?*key;

????//鍵值對(duì)中的值
????union?{
????????void?*val;
????????uint64_t?u64;
????????int64_t?s64;
????????double?d;
????}?v;
????//指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
????struct?dictEntry?*next;
}?dictEntry;

dictEntry 結(jié)構(gòu)里不僅包含指向鍵和值的指針，還包含了指向下一個(gè)哈希表節(jié)點(diǎn)的指針，這個(gè)指針可以將多個(gè)哈希值相同的鍵值對(duì)鏈接起來，以此來解決哈希沖突的問題，這就是鏈?zhǔn)焦！?/p>

另外，這里還跟你提一下，dictEntry 結(jié)構(gòu)里鍵值對(duì)中的值是一個(gè)「聯(lián)合體 v」定義的，因此，鍵值對(duì)中的值可以是一個(gè)指向?qū)嶋H值的指針，或者是一個(gè)無符號(hào)的 64 位整數(shù)或有符號(hào)的 64 位整數(shù)或double 類的值。這么做的好處是可以節(jié)省內(nèi)存空間，因?yàn)楫?dāng)「值」是整數(shù)或浮點(diǎn)數(shù)時(shí)，就可以將值的數(shù)據(jù)內(nèi)嵌在 dictEntry 結(jié)構(gòu)里，無需再用一個(gè)指針指向?qū)嶋H的值，從而節(jié)省了內(nèi)存空間。

哈希沖突

哈希表實(shí)際上是一個(gè)數(shù)組，數(shù)組里多每一個(gè)元素就是一個(gè)哈希桶。

當(dāng)一個(gè)鍵值對(duì)的鍵經(jīng)過 Hash 函數(shù)計(jì)算后得到哈希值，再將(哈希值 % 哈希表大小)取模計(jì)算，得到的結(jié)果值就是該 key-value 對(duì)應(yīng)的數(shù)組元素位置，也就是第幾個(gè)哈希桶。

什么是哈希沖突呢？

舉個(gè)例子，有一個(gè)可以存放 8 個(gè)哈希桶的哈希表。key1 經(jīng)過哈希函數(shù)計(jì)算后，再將「哈希值 % 8 」進(jìn)行取模計(jì)算，結(jié)果值為 1，那么就對(duì)應(yīng)哈希桶 1，類似的，key9 和 key10 分別對(duì)應(yīng)哈希桶 1 和桶 6。

此時(shí)，key1 和 key9 對(duì)應(yīng)到了相同的哈希桶中，這就發(fā)生了哈希沖突。

因此，當(dāng)有兩個(gè)以上數(shù)量的 kay 被分配到了哈希表中同一個(gè)哈希桶上時(shí)，此時(shí)稱這些 key 發(fā)生了沖突。

鏈?zhǔn)焦?/span>

Redis 采用了「鏈?zhǔn)焦?/strong>」的方法來解決哈希沖突。

鏈?zhǔn)焦Ｊ窃趺磳?shí)現(xiàn)的？

實(shí)現(xiàn)的方式就是每個(gè)哈希表節(jié)點(diǎn)都有一個(gè) next 指針，用于指向下一個(gè)哈希表節(jié)點(diǎn)，因此多個(gè)哈希表節(jié)點(diǎn)可以用 next 指針構(gòu)成一個(gè)單項(xiàng)鏈表，被分配到同一個(gè)哈希桶上的多個(gè)節(jié)點(diǎn)可以用這個(gè)單項(xiàng)鏈表連接起來，這樣就解決了哈希沖突。

還是用前面的哈希沖突例子，key1 和 key9 經(jīng)過哈希計(jì)算后，都落在同一個(gè)哈希桶，鏈?zhǔn)焦５脑?，key1 就會(huì)通過 next 指針指向 key9，形成一個(gè)單向鏈表。

不過，鏈?zhǔn)焦＞窒扌砸埠苊黠@，隨著鏈表長度的增加，在查詢這一位置上的數(shù)據(jù)的耗時(shí)就會(huì)增加，畢竟鏈表的查詢的時(shí)間復(fù)雜度是 O(n)。

要想解決這一問題，就需要進(jìn)行 rehash，也就是對(duì)哈希表的大小進(jìn)行擴(kuò)展。

接下來，看看 Redis 是如何實(shí)現(xiàn)的 rehash 的。

rehash

哈希表結(jié)構(gòu)設(shè)計(jì)的這一小節(jié)，我給大家介紹了 Redis 使用 dictht 結(jié)構(gòu)體表示哈希表。不過，在實(shí)際使用哈希表時(shí)，Redis 定義一個(gè) dict 結(jié)構(gòu)體，這個(gè)結(jié)構(gòu)體里定義了兩個(gè)哈希表（ht[2]）。

typedef?struct?dict?{
????…
????//兩個(gè)Hash表，交替使用，用于rehash操作
????dictht?ht[2];?
????…
}?dict;

之所以定義了 2 個(gè)哈希表，是因?yàn)檫M(jìn)行 rehash 的時(shí)候，需要用上 2 個(gè)哈希表了。

在正常服務(wù)請(qǐng)求階段，插入的數(shù)據(jù)，都會(huì)寫入到「哈希表 1」，此時(shí)的「哈希表 2 」 并沒有被分配空間。

隨著數(shù)據(jù)逐步增多，觸發(fā)了 rehash 操作，這個(gè)過程分為三步：

• 給「哈希表 2」 分配空間，一般會(huì)比「哈希表 1」 大 2 倍；

• 將「哈希表 1 」的數(shù)據(jù)遷移到「哈希表 2」 中；

• 遷移完成后，「哈希表 1 」的空間會(huì)被釋放，并把「哈希表 2」 設(shè)置為「哈希表 1」，然后在「哈希表 2」 新創(chuàng)建一個(gè)空白的哈希表，為下次 rehash 做準(zhǔn)備。

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

這個(gè)過程看起來簡單，但是其實(shí)第二步很有問題，如果「哈希表 1 」的數(shù)據(jù)量非常大，那么在遷移至「哈希表 2 」的時(shí)候，因?yàn)闀?huì)涉及大量的數(shù)據(jù)拷貝，此時(shí)可能會(huì)對(duì) Redis 造成阻塞，無法服務(wù)其他請(qǐng)求。

漸進(jìn)式 rehash

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

漸進(jìn)式 rehash 步驟如下：

• 給「哈希表 2」 分配空間；

• 在 rehash 進(jìn)行期間，每次哈希表元素進(jìn)行新增、刪除、查找或者更新操作時(shí)，Redis 除了會(huì)執(zhí)行對(duì)應(yīng)的操作之外，還會(huì)順序?qū)ⅰ腹１?1 」中索引位置上的所有 key-value 遷移到「哈希表 2」 上；

• 隨著處理客戶端發(fā)起的哈希表操作請(qǐng)求數(shù)量越多，最終在某個(gè)時(shí)間嗲呢，會(huì)把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。

這樣就巧妙地把一次性大量數(shù)據(jù)遷移工作的開銷，分?jǐn)偟搅硕啻翁幚碚?qǐng)求的過程中，避免了一次性 rehash 的耗時(shí)操作。

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

比如，查找一個(gè) key 的值的話，先會(huì)在「哈希表 1」 里面進(jìn)行查找，如果沒找到，就會(huì)繼續(xù)到哈希表 2 里面進(jìn)行找到。

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

rehash 觸發(fā)條件

介紹了 rehash 那么多，還沒說什么時(shí)情況下會(huì)觸發(fā) rehash 操作呢？

rehash 的觸發(fā)條件跟負(fù)載因子（load factor）有關(guān)系。

負(fù)載因子可以通過下面這個(gè)公式計(jì)算：

觸發(fā) rehash 操作的條件，主要有兩個(gè)：

• 當(dāng)負(fù)載因子大于等于 1 ，并且 Redis 沒有在執(zhí)行 bgsave 命令或者 bgrewiteaof 命令，也就是沒有執(zhí)行 RDB 快照或沒有進(jìn)行 AOF 重寫的時(shí)候，就會(huì)進(jìn)行 rehash 操作。

• 當(dāng)負(fù)載因子大于等于 5 時(shí)，此時(shí)說明哈希沖突非常嚴(yán)重了，不管有沒有有在執(zhí)行 RDB 快照或 AOF 重寫，都會(huì)強(qiáng)制進(jìn)行 rehash 操作。

整數(shù)集合

整數(shù)集合是 ?Set 對(duì)象的底層實(shí)現(xiàn)之一。當(dāng)一個(gè) Set 對(duì)象只包含整數(shù)值元素，并且元素?cái)?shù)量不時(shí)，就會(huì)使用整數(shù)集這個(gè)數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn)。

整數(shù)集合結(jié)構(gòu)設(shè)計(jì)

整數(shù)集合本質(zhì)上是一塊連續(xù)內(nèi)存空間，它的結(jié)構(gòu)定義如下：

typedef?struct?intset?{
????//編碼方式
????uint32_t?encoding;
????//集合包含的元素?cái)?shù)量
????uint32_t?length;
????//保存元素的數(shù)組
????int8_t?contents[];
}?intset;

可以看到，保存元素的容器是一個(gè) contents 數(shù)組，雖然 contents 被聲明為 int8_t 類型的數(shù)組，但是實(shí)際上 contents 數(shù)組并不保存任何 int8_t 類型的元素，contents 數(shù)組的真正類型取決于 intset 結(jié)構(gòu)體里的 encoding 屬性的值。比如：

• 如果 encoding 屬性值為 INTSET_ENC_INT16，那么 contents 就是一個(gè) int16_t 類型的數(shù)組，數(shù)組中每一個(gè)元素的類型都是 int16_t；

• 如果 encoding 屬性值為 INTSET_ENC_INT32，那么 contents 就是一個(gè) int32_t 類型的數(shù)組，數(shù)組中每一個(gè)元素的類型都是 int32_t；

• 如果 encoding 屬性值為 INTSET_ENC_INT64，那么 contents 就是一個(gè) int64_t 類型的數(shù)組，數(shù)組中每一個(gè)元素的類型都是 int64_t；

不同類型的 contents 數(shù)組，意味著數(shù)組的大小也會(huì)不同。

整數(shù)集合的升級(jí)操作

整數(shù)集合會(huì)有一個(gè)升級(jí)規(guī)則，就是當(dāng)我們將一個(gè)新元素加入到整數(shù)集合里面，如果新元素的類型（int32_t）比整數(shù)集合現(xiàn)有所有元素的類型（int16_t）都要長時(shí)，整數(shù)集合需要先進(jìn)行升級(jí)，也就是按新元素的類型（int32_t）擴(kuò)展 contents 數(shù)組的空間大小，然后才能將新元素加入到整數(shù)集合里，當(dāng)然升級(jí)的過程中，也要維持整數(shù)集合的有序性。

整數(shù)集合升級(jí)的過程不會(huì)重新分配一個(gè)新類型的數(shù)組，而是在原本的數(shù)組上擴(kuò)展空間，然后在將每個(gè)元素按間隔類型大小分割，如果 encoding 屬性值為 INTSET_ENC_INT16，則每個(gè)元素的間隔就是 16 位。

舉個(gè)例子，假設(shè)有一個(gè)整數(shù)集合里有 3 個(gè)類型為 int16_t 的元素。

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

擴(kuò)容完 contents 數(shù)組空間大小后，需要將之前的三個(gè)元素轉(zhuǎn)換為 int32_t 類型，并將轉(zhuǎn)換后的元素放置到正確的位上面，并且需要維持底層數(shù)組的有序性不變，整個(gè)轉(zhuǎn)換過程如下：

整數(shù)集合升級(jí)有什么好處呢？

如果要讓一個(gè)數(shù)組同時(shí)保存 int16_t、int32_t、int64_t 類型的元素，最簡單做法就是直接使用 int64_t 類型的數(shù)組。不過這樣的話，當(dāng)如果元素都是 int16_t 類型的，就會(huì)造成內(nèi)存浪費(fèi)的情況。

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

因此，整數(shù)集合升級(jí)的好處是節(jié)省內(nèi)存資源。

整數(shù)集合支持降級(jí)操作嗎？

不支持降級(jí)操作，一旦對(duì)數(shù)組進(jìn)行了升級(jí)，就會(huì)一直保持升級(jí)后的狀態(tài)。比如前面的升級(jí)操作的例子，如果刪除了 65535 元素，整數(shù)集合的數(shù)組還是 int32_t 類型的，并不會(huì)因此降級(jí)為 int16_t 類型。

跳表

Redis 只有在 Zset 對(duì)象的底層實(shí)現(xiàn)用到了跳表，跳表的優(yōu)勢(shì)是能支持平均 O(logN) 復(fù)雜度的節(jié)點(diǎn)查找。

Zset 對(duì)象是唯一一個(gè)同時(shí)使用了兩個(gè)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的 Redis 對(duì)象，這兩個(gè)數(shù)據(jù)結(jié)構(gòu)一個(gè)是跳表，一個(gè)是哈希表。這樣的好處是既能進(jìn)行高效的范圍查詢，也能進(jìn)行高效單點(diǎn)查詢。

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

Zset 對(duì)象能支持范圍查詢（如 ZRANGEBYSCORE 操作），這是因?yàn)樗臄?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)采用了跳表，而又能以常數(shù)復(fù)雜度獲取元素權(quán)重（如 ZSCORE 操作），這是因?yàn)樗瑫r(shí)采用了哈希表進(jìn)行索引。

接下來，詳細(xì)的說下跳表。

跳表結(jié)構(gòu)設(shè)計(jì)

鏈表在查找元素的時(shí)候，因?yàn)樾枰鹨徊檎?，所以查詢效率非常低，時(shí)間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過來的，實(shí)現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。

那跳表長什么樣呢？我這里舉個(gè)例子，下圖展示了一個(gè)層級(jí)為 3 的跳表。

圖中頭節(jié)點(diǎn)有 L0~L2 三個(gè)頭指針，分別指向了不同層級(jí)的節(jié)點(diǎn)，然后每個(gè)層級(jí)的節(jié)點(diǎn)都通過指針連接起來：

• L0 層級(jí)共有 5 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn)1、2、3、4、5；

• L1 層級(jí)共有 3 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn) 2、3、5；

• L2 層級(jí)只有 1 個(gè)節(jié)點(diǎn)，也就是節(jié)點(diǎn) 3 。

如果我們要在鏈表中查找節(jié)點(diǎn) 4 這個(gè)元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點(diǎn) 4，因?yàn)榭梢栽陬^節(jié)點(diǎn)直接從 L2 層級(jí)跳到節(jié)點(diǎn) 3，然后再往前遍歷找到節(jié)點(diǎn) 4。

可以看到，這個(gè)查找過程就是在多個(gè)層級(jí)上跳來跳去，最后定位到元素。當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度就是 O(logN)。

那跳表節(jié)點(diǎn)是怎么實(shí)現(xiàn)多層級(jí)的呢？這就需要看「跳表節(jié)點(diǎn)」的數(shù)據(jù)結(jié)構(gòu)了，如下：

typedef?struct?zskiplistNode?{
????//Zset?對(duì)象的元素值
????sds?ele;
????//元素權(quán)重值
????double?score;
????//后向指針
????struct?zskiplistNode?*backward;

????//節(jié)點(diǎn)的level數(shù)組，保存每層上的前向指針和跨度
????struct?zskiplistLevel?{
????????struct?zskiplistNode?*forward;
????????unsigned?long?span;
????}?level[];
}?zskiplistNode;

Zset 對(duì)象要同時(shí)保存元素和元素的權(quán)重，對(duì)應(yīng)到跳表節(jié)點(diǎn)結(jié)構(gòu)里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個(gè)跳表節(jié)點(diǎn)都有一個(gè)后向指針，指向前一個(gè)節(jié)點(diǎn)，目的是為了方便從跳表的尾節(jié)點(diǎn)開始訪問節(jié)點(diǎn)，這樣倒序查找時(shí)很方便。

跳表是一個(gè)帶有層級(jí)關(guān)系的鏈表，而且每一層級(jí)可以包含多個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)通過指針連接起來，實(shí)現(xiàn)這一特性就是靠跳表節(jié)點(diǎn)結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類型的 level 數(shù)組。

level 數(shù)組中的每一個(gè)元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個(gè)跳表節(jié)點(diǎn)的指針」和「跨度」，跨度時(shí)用來記錄兩個(gè)節(jié)點(diǎn)之間的距離。

比如，下面這張圖，展示了各個(gè)節(jié)點(diǎn)的跨度。

第一眼看到跨度的時(shí)候，以為是遍歷操作有關(guān)，實(shí)際上并沒有任何關(guān)系，遍歷操作只需要用前向指針就可以完成了。

跨度實(shí)際上是為了計(jì)算這個(gè)節(jié)點(diǎn)在跳表中的排位。具體怎么做的呢？因?yàn)樘碇械墓?jié)點(diǎn)都是按序排列的，那么計(jì)算某個(gè)節(jié)點(diǎn)排位的時(shí)候，從頭節(jié)點(diǎn)點(diǎn)到該結(jié)點(diǎn)的查詢路徑上，將沿途訪問過的所有層的跨度累加起來，得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳表中的排位。

舉個(gè)例子，查找圖中節(jié)點(diǎn) 3 在跳表中的排位，從頭節(jié)點(diǎn)開始查找節(jié)點(diǎn) 3，查找的過程只經(jīng)過了一個(gè)層（L3），并且層的跨度是 3，所以節(jié)點(diǎn) 3 在跳表中的排位是 3。

另外，圖中的頭節(jié)點(diǎn)其實(shí)也是 zskiplistNode 跳表節(jié)點(diǎn)，只不過頭節(jié)點(diǎn)的后向指針、權(quán)重、元素值都會(huì)被用到，所以圖中省略了這部分。

問題來了，由誰定義哪個(gè)跳表節(jié)點(diǎn)是頭節(jié)點(diǎn)呢？這就介紹「跳表」結(jié)構(gòu)體了，如下所示：

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

跳表結(jié)構(gòu)里包含了：

• 跳表的頭尾節(jié)點(diǎn)，便于在O(1)時(shí)間復(fù)雜度內(nèi)訪問跳表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)；

• 跳表的長度，便于在O(1)時(shí)間復(fù)雜度獲取跳表節(jié)點(diǎn)的數(shù)量；

• 跳表的最大層數(shù)，便于在O(1)時(shí)間復(fù)雜度獲取跳表中層高最大的那個(gè)節(jié)點(diǎn)的層數(shù)量；

跳表節(jié)點(diǎn)查詢過程

查找一個(gè)跳表節(jié)點(diǎn)的過程時(shí)，跳表會(huì)從頭節(jié)點(diǎn)的最高層開始，逐一遍歷每一層。在遍歷某一層的跳表節(jié)點(diǎn)時(shí)，會(huì)用跳表節(jié)點(diǎn)中的 SDS 類型的元素和元素的權(quán)重來進(jìn)行判斷，共有兩個(gè)判斷條件：

• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「小于」要查找的權(quán)重時(shí)，跳表就會(huì)訪問該層上的下一個(gè)節(jié)點(diǎn)。

• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「等于」要查找的權(quán)重時(shí)，并且當(dāng)前節(jié)點(diǎn)的 SDS 類型數(shù)據(jù)「小于」要查找的數(shù)據(jù)時(shí)，跳表就會(huì)訪問該層上的下一個(gè)節(jié)點(diǎn)。

如果上面兩個(gè)條件都不滿足，或者下一個(gè)節(jié)點(diǎn)為空時(shí)，跳表就會(huì)使用目前遍歷到的節(jié)點(diǎn)的 level 數(shù)組里的下一層指針，然后沿著下一層指針繼續(xù)查找，這就相當(dāng)于跳到了下一層接著查找。

舉個(gè)例子，下圖有個(gè) 3 層級(jí)的跳表。

如果要查找「元素：abcd，權(quán)重：4」的節(jié)點(diǎn)，查找的過程是這樣的：

• 先從頭節(jié)點(diǎn)的最高層開始，L2 指向了「元素：abc，權(quán)重：3」節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的權(quán)重比要查找節(jié)點(diǎn)的小，所以要訪問該層上的下一個(gè)節(jié)點(diǎn)；

• 但是該層上的下一個(gè)節(jié)點(diǎn)是空節(jié)點(diǎn)，于是就會(huì)跳到「元素：abc，權(quán)重：3」節(jié)點(diǎn)的下一層去找，也就是 leve[1];

• 「元素：abc，權(quán)重：3」節(jié)點(diǎn)的 ?leve[1] 的下一個(gè)指針指向了「元素：abcde，權(quán)重：4」的節(jié)點(diǎn)，然后將其和要查找的節(jié)點(diǎn)比較。雖然「元素：abcde，權(quán)重：4」的節(jié)點(diǎn)的權(quán)重和要查找的權(quán)重相同，但是當(dāng)前節(jié)點(diǎn)的 SDS 類型數(shù)據(jù)「大于」要查找的數(shù)據(jù)，所以會(huì)繼續(xù)跳到「元素：abc，權(quán)重：3」節(jié)點(diǎn)的下一層去找，也就是 leve[0]；

• 「元素：abc，權(quán)重：3」節(jié)點(diǎn)的 leve[0] 的下一個(gè)指針指向了「元素：abcd，權(quán)重：4」的節(jié)點(diǎn)，該節(jié)點(diǎn)正是要查找的節(jié)點(diǎn)，查詢結(jié)束。

跳表節(jié)點(diǎn)層數(shù)設(shè)置

跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量的比例會(huì)影響跳表的查詢性能。

舉個(gè)例子，下圖的跳表，第二層的節(jié)點(diǎn)數(shù)量只有 1 個(gè)，而第一層的節(jié)點(diǎn)數(shù)量有 6 個(gè)。

這時(shí)，如果想要查詢節(jié)點(diǎn) 6，那基本就跟鏈表的查詢復(fù)雜度一樣，就需要在第一層的節(jié)點(diǎn)中依次順序查找，復(fù)雜度就是 O(N) 了。所以，為了降低查詢復(fù)雜度，我們就需要維持相鄰層結(jié)點(diǎn)數(shù)間的關(guān)系。

跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量最理想的比例是 2:1，查找復(fù)雜度可以降低到 O(logN)。

下圖的跳表就是，相鄰兩層的節(jié)點(diǎn)數(shù)量的比例是 2 : 1。

那怎樣才能維持相鄰兩層的節(jié)點(diǎn)數(shù)量的比例為 2 : 1 ?呢？

如果采用新增節(jié)點(diǎn)或者刪除節(jié)點(diǎn)時(shí)，來調(diào)整跳表節(jié)點(diǎn)以維持比例的方法的話，會(huì)帶來額外的開銷。

Redis 則采用一種巧妙的方法是，跳表在創(chuàng)建節(jié)點(diǎn)的時(shí)候，隨機(jī)生成每個(gè)節(jié)點(diǎn)的層數(shù)，并沒有嚴(yán)格維持相鄰兩層的節(jié)點(diǎn)數(shù)量比例為 2 : 1 的情況。

具體的做法是，跳表在創(chuàng)建節(jié)點(diǎn)時(shí)候，會(huì)生成范圍為[0-1]的一個(gè)隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個(gè)隨機(jī)數(shù)，直到隨機(jī)數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點(diǎn)的層數(shù)。

這樣的做法，相當(dāng)于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。

quicklist

在 Redis 3.0 之前，List 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表或者壓縮列表。然后在 ?Redis 3.2 的時(shí)候，List 對(duì)象的底層改由 quicklist 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

其實(shí) quicklist 就是「雙向鏈表 + 壓縮列表」組合，因?yàn)橐粋€(gè) quicklist 就是一個(gè)鏈表，而鏈表中的每個(gè)元素又是一個(gè)壓縮列表。

在前面講壓縮列表的時(shí)候，我也提到了壓縮列表的不足，雖然壓縮列表是通過緊湊型的內(nèi)存布局節(jié)省了內(nèi)存開銷，但是因?yàn)樗慕Y(jié)構(gòu)設(shè)計(jì)，如果保存的元素?cái)?shù)量增加，或者元素變大了，壓縮列表會(huì)有「連鎖更新」的風(fēng)險(xiǎn)，一旦發(fā)生，會(huì)造成性能下降。

quicklist 解決辦法，通過控制每個(gè)鏈表節(jié)點(diǎn)中的壓縮列表的大小或者元素個(gè)數(shù)，來規(guī)避連鎖更新的問題。因?yàn)閴嚎s列表元素越少或越小，連鎖更新帶來的影響就越小，從而提供了更好的訪問性能。

quicklist 結(jié)構(gòu)設(shè)計(jì)

quicklist 的結(jié)構(gòu)體跟鏈表的結(jié)構(gòu)體類似，都包含了表頭和表尾，區(qū)別在于 quicklist 的節(jié)點(diǎn)是 quicklistNode。

typedef?struct?quicklist?{
????//quicklist的鏈表頭
????quicklistNode?*head;??????//quicklist的鏈表頭
????//quicklist的鏈表頭
????quicklistNode?*tail;?
????//所有壓縮列表中的總元素個(gè)數(shù)
????unsigned?long?count;
????//quicklistNodes的個(gè)數(shù)
????unsigned?long?len;???????
????...
}?quicklist;

接下來看看，quicklistNode 的結(jié)構(gòu)定義：

typedef?struct?quicklistNode?{
????//前一個(gè)quicklistNode
????struct?quicklistNode?*prev;?????//前一個(gè)quicklistNode
????//下一個(gè)quicklistNode
????struct?quicklistNode?*next;?????//后一個(gè)quicklistNode
????//quicklistNode指向的壓縮列表
????unsigned?char?*zl;??????????????
????//壓縮列表的的字節(jié)大小
????unsigned?int?sz;????????????????
????//壓縮列表的元素個(gè)數(shù)
????unsigned?int?count?:?16;????????//ziplist中的元素個(gè)數(shù)?
????....
}?quicklistNode;

可以看到，quicklistNode 結(jié)構(gòu)體里包含了前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)指針，這樣每個(gè) quicklistNode 形成了一個(gè)雙向鏈表。但是鏈表節(jié)點(diǎn)的元素不再是單純保存元素值，而是保存了一個(gè)壓縮列表，所以 quicklistNode 結(jié)構(gòu)體里有個(gè)指向壓縮列表的指針 *zl。

我畫了一張圖，方便你理解 quicklist 數(shù)據(jù)結(jié)構(gòu)。

在向 quicklist 添加一個(gè)元素的時(shí)候，不會(huì)像普通的鏈表那樣，直接新建一個(gè)鏈表節(jié)點(diǎn)。而是會(huì)檢查插入位置的壓縮列表是否能容納該元素，如果能容納就直接保存到 quicklistNode 結(jié)構(gòu)里的壓縮列表，如果不能容納，才會(huì)新建一個(gè)新的 quicklistNode 結(jié)構(gòu)。

quicklist 會(huì)控制 quicklistNode 結(jié)構(gòu)里的壓縮列表的大小或者元素個(gè)數(shù)，來規(guī)避潛在的連鎖更新的風(fēng)險(xiǎn)，但是這并沒有完全解決連鎖更新的問題。

listpack

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

因?yàn)?quicklistNode 還是用了壓縮列表來保存元素，壓縮列表連鎖更新的問題，來源于它的結(jié)構(gòu)設(shè)計(jì)，所以要想徹底解決這個(gè)問題，需要設(shè)計(jì)一個(gè)新的數(shù)據(jù)結(jié)構(gòu)。

于是，Redis 在 5.0 新設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)叫 listpack，目的是替代壓縮列表，它最大特點(diǎn)是 listpack 中每個(gè)節(jié)點(diǎn)不再包含前一個(gè)節(jié)點(diǎn)的長度了，壓縮列表每個(gè)節(jié)點(diǎn)正因?yàn)樾枰４媲耙粋€(gè)節(jié)點(diǎn)的長度字段，就會(huì)有連鎖更新的隱患。

我看了 Redis 的 Github，在最新 ?6.2 發(fā)行版本中，Redis Hash 對(duì)象、Set 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)的壓縮列表還未被替換成 listpack，而 Redis 的最新代碼（還未發(fā)布版本）已經(jīng)將所有用到壓縮列表底層數(shù)據(jù)結(jié)構(gòu)的 Redis 對(duì)象替換成 listpack 數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，估計(jì)不久將來，Redis 就會(huì)發(fā)布一個(gè)將壓縮列表為 listpack 的發(fā)行版本。

listpack 結(jié)構(gòu)設(shè)計(jì)

listpack 采用了壓縮列表的很多優(yōu)秀的設(shè)計(jì)，比如還是用一塊連續(xù)的內(nèi)存空間來緊湊地保存數(shù)據(jù)，并且為了節(jié)省內(nèi)存的開銷，listpack 節(jié)點(diǎn)會(huì)采用不同的編碼方式保存不同大小的數(shù)據(jù)。

我們先看看 listpack 結(jié)構(gòu)：

listpack 頭包含兩個(gè)屬性，分別記錄了 listpack 總字節(jié)數(shù)和元素?cái)?shù)量，然后 listpack 末尾也有個(gè)結(jié)尾標(biāo)識(shí)。圖中的 listpack entry 就是 listpack 的節(jié)點(diǎn)了。

每個(gè) listpack 節(jié)點(diǎn)結(jié)構(gòu)如下：

主要包含三個(gè)方面內(nèi)容：

• encoding，定義該元素的編碼類型，會(huì)對(duì)不同長度的整數(shù)和字符串進(jìn)行編碼；

• data，實(shí)際存放的數(shù)據(jù)；

• len，encoding+data的總長度；

可以看到，listpack 沒有壓縮列表中記錄前一個(gè)節(jié)點(diǎn)長度的字段了，listpack 只記錄當(dāng)前節(jié)點(diǎn)的長度，當(dāng)我們向 listpack 加入一個(gè)新元素的時(shí)候，不會(huì)影響其他節(jié)點(diǎn)的長度字段的變化，從而避免了壓縮列表的連鎖更新問題。

參考資料：

• 《Redis設(shè)計(jì)與實(shí)現(xiàn)》

• 《Redis 源碼剖析與實(shí)戰(zhàn)》