[[438194]]

本文轉(zhuǎn)載自微信公眾號(hào)「小林coding」，作者小林coding。轉(zhuǎn)載本文請(qǐng)聯(lián)系小林coding公眾號(hào)。

大家好，我是小林。

前幾天發(fā)了一篇「為了拿捏 Redis 數(shù)據(jù)結(jié)構(gòu)，我畫(huà)了 20 張圖」，收獲了很多好評(píng)，但是當(dāng)時(shí)急于發(fā)文，有些地方?jīng)]有寫(xiě)完，也有些地方寫(xiě)的不是很完善。

然后我最近花了很多時(shí)間來(lái)完善文章，不僅加入了 Redis 新版本的兩個(gè)數(shù)據(jù)結(jié)構(gòu)，也在之前的文章內(nèi)容加入了很多內(nèi)容。

這次完整版終于來(lái)了，加了億點(diǎn)點(diǎn)東西!

從之前的 1 萬(wàn)字，變成現(xiàn)在的 2 萬(wàn)字，圖更是畫(huà)到了接近 40 張!不管是內(nèi)容還是圖片，都比上一篇翻了一倍!

Redis 為什么那么快?

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

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

注意，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)。

我畫(huà)了一張 Redis 數(shù)據(jù)類型(也叫 Redis 對(duì)象)和底層數(shù)據(jù)結(jié)構(gòu)的對(duì)應(yīng)關(guān)圖，左邊是 Redis 3.0版本的，也就是《Redis 設(shè)計(jì)與實(shí)現(xiàn)》這本書(shū)講解的版本，現(xiàn)在看還是有點(diǎn)過(guò)時(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)來(lái)實(shí)現(xiàn)了。

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

不多 BB 了，直接發(fā)車(chē)!

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

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

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ù)雜度來(lái)快速查找到鍵值對(duì)。哈希表其實(shí)就是一個(gè)數(shù)組，數(shù)組中的元素叫做哈希桶。

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

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

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

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

• redisDb 結(jié)構(gòu)，表示 Redis 數(shù)據(jù)庫(kù)的結(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ì)象。

特別說(shuō)明下，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)的指針。

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

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

SDS

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

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

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

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

C 語(yǔ)言字符串的缺陷

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

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

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

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

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

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

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

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

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

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

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

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

C 語(yǔ)言的字符串是不會(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ù)雜度也很高，也都需要先通過(guò)遍歷字符串才能得到目標(biāo)字符串的末尾。然后對(duì)于 strcat 函數(shù)來(lái)說(shuō)，還要再遍歷源字符串才能完成追加，對(duì)字符串的操作效率不高。

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

• 獲取字符串長(zhǎng)度的時(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)就把上面這些問(wèn)題解決了，接下來(lái)我們一起看看 Redis 是如何解決的。

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

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

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

• len，記錄了字符串長(zhǎng)度。這樣獲取字符串長(zhǎng)度的時(shí)候，只需要返回這個(gè)成員變量值就行，時(shí)間復(fù)雜度只需要 O(1)。
• alloc，分配給字符數(shù)組的空間長(zhǎng)度。這樣在修改字符串的時(shí)候，可以通過(guò) alloc - len 計(jì)算出剩余的空間大小，可以用來(lái)判斷空間是否滿足修改需求，如果不滿足的話，就會(huì)自動(dòng)將 SDS 的空間擴(kuò)展至執(zhí)行修改所需的大小，然后才執(zhí)行實(shí)際的修改操作，所以使用 SDS 既不需要手動(dòng)修改 SDS 的空間大小，也不會(huì)出現(xiàn)前面所說(shuō)的緩沖區(qū)溢出的問(wèn)題。
• flags，用來(lái)表示不同類型的 SDS。一共設(shè)計(jì)了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說(shuō)明區(qū)別之處。
• buf[]，字符數(shù)組，用來(lái)保存實(shí)際數(shù)據(jù)。不僅可以保存字符串，也可以保存二進(jìn)制數(shù)據(jù)。

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

O(1)復(fù)雜度獲取字符串長(zhǎng)度

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

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

二進(jìn)制安全

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

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

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

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

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

所以，Redis 的 SDS 結(jié)構(gòu)里引入了 alloc 和 len 成員變量，這樣 SDS API 通過(guò) 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ì)直接使用「未使用空間」，而無(wú)須執(zhí)行內(nèi)存分配，有效的減少內(nèi)存分配次數(shù)。

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

節(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ù)組長(zhǎng)度和分配空間大小不能超過(guò) 2 的 16 次方。
• sdshdr32 則都是 uint32_t，表示表示字符數(shù)組長(zhǎng)度和分配空間大小不能超過(guò) 2 的 32 次方。

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

除了設(shè)計(jì)不同類型的結(jié)構(gòu)體，Redis 在編程上還使用了專門(mén)的編譯優(yōu)化來(lái)節(jié)省內(nèi)存空間，即在 struct 聲明了 __attribute__ ((packed)) ，它的作用是：告訴編譯器取消結(jié)構(gòu)體在編譯過(guò)程中的優(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 <stdio.h> 
 
 struct test1 { 
    char a; 
    int b; 
 } test1; 
 
int main() { 
     printf("%lu\n", sizeof(test1)); 
     return 0; 
} 

大家猜猜這個(gè)結(jié)構(gòu)體大小是多少?我先直接說(shuō)答案，這個(gè)結(jié)構(gòu)體大小計(jì)算出來(lái)是 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)體，這樣一來(lái)，結(jié)構(gòu)體實(shí)際占用多少內(nèi)存空間，編譯器就分配多少空間。

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

#include <stdio.h> 
 
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 語(yǔ)言本身沒(méi)有鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)的，所以 Redis 自己設(shè)計(jì)了一個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)。

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

先來(lái)看看「鏈表節(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ì)

不過(guò)，Redis 在 listNode 結(jié)構(gòu)體基礎(chǔ)上又封裝了 list 這個(gè)數(shù)據(jù)結(jié)構(gòu)，這樣操作起來(lái)會(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，所以鏈表是無(wú)環(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)值，并且可以通過(guò) 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ù)的，意味著無(wú)法很好利用 CPU 緩存。能很好利用 CPU 緩存的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，因?yàn)閿?shù)組的內(nèi)存是連續(xù)的，這樣就可以充分利用 CPU 緩存來(lái)加速訪問(wèn);
• 還有一點(diǎn)，保存一個(gè)鏈表節(jié)點(diǎn)的值都需要一個(gè)鏈表節(jié)點(diǎn)結(jié)構(gòu)頭的分配，內(nèi)存開(kā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)。

不過(guò)，壓縮列表存在性能問(wèn)題(具體什么問(wèn)題，下面會(huì)說(shuō))，所以 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ì)不同長(zhǎng)度的數(shù)據(jù)，進(jìn)行相應(yīng)編碼，這種方法可以有效地節(jié)省內(nèi)存開(kāi)銷。

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

• 不能保存過(guò)多的元素，否則查詢效率就會(huì)降低;
• 新增或修改某個(gè)元素時(shí)，壓縮列表占用的內(nèi)存空間需要重新分配，甚至可能引發(fā)連鎖更新的問(wèn)題。

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

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

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

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開(kā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è)元素，可以通過(guò)表頭三個(gè)字段的長(zhǎng)度直接定位，復(fù)雜度是 O(1)。而查找其他元素時(shí)，就沒(méi)有這么高效了，只能逐個(gè)查找，此時(shí)的復(fù)雜度就是 O(N) 了，因此壓縮列表不適合保存過(guò)多的元素。

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

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

• prevlen，記錄了「前一個(gè)節(jié)點(diǎn)」的長(zhǎng)度;
• encoding，記錄了當(dāng)前節(jié)點(diǎn)實(shí)際數(shù)據(jù)的類型以及長(zhǎng)度;
• 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)存而采用的。

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

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

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

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

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

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

連鎖更新

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

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

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

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

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

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

這時(shí)，如果將一個(gè)長(zhǎng)度大于等于 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é)大小，無(wú)法保存新節(jié)點(diǎn)的長(zhǎng)度，此時(shí)就需要對(duì)壓縮列表的空間重分配操作，并將 e1 節(jié)點(diǎn)的 prevlen 屬性從原來(lái)的 1 字節(jié)大小擴(kuò)展為 5 字節(jié)大小。

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

e1 原本的長(zhǎng)度在 250～253 之間，因?yàn)閯偛诺臄U(kuò)展空間，此時(shí) e1 的長(zhǎng)度就大于等于 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ì)直接影響到壓縮列表的訪問(wèn)性能。

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

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

雖說(shuō)如此，Redis 針對(duì)壓縮列表在設(shè)計(jì)上的不足，在后來(lái)的版本中，新增設(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í)解決壓縮列表的「連鎖更新」的問(wèn)題。

哈希表

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

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

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

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

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

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

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

接下來(lái)，詳細(xì)說(shuō)說(shuō)哈希表。

哈希表結(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ì)鏈接起來(lái)，以此來(lái)解決哈希沖突的問(wèn)題，這就是鏈?zhǔn)焦！?/p>

另外，這里還跟你提一下，dictEntry 結(jié)構(gòu)里鍵值對(duì)中的值是一個(gè)「聯(lián)合體 v」定義的，因此，鍵值對(duì)中的值可以是一個(gè)指向?qū)嶋H值的指針，或者是一個(gè)無(wú)符號(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)里，無(wú)需再用一個(gè)指針指向?qū)嶋H的值，從而節(jié)省了內(nèi)存空間。

哈希沖突

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

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

什么是哈希沖突呢?

舉個(gè)例子，有一個(gè)可以存放 8 個(gè)哈希桶的哈希表。key1 經(jīng)過(guò)哈希函數(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)焦?/strong>

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

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

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

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; 

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

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

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;