圖解 Redis 數(shù)據(jù)結(jié)構(gòu)
[導(dǎo)讀]Redis為什么那么快？除了它是內(nèi)存數(shù)據(jù)庫，使得所有的操作都在內(nèi)存上進行之外，還有一個重要因素，它實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，使得我們對數(shù)據(jù)進行增刪查改操作時，Redis能高效的處理。因此，這次我們就來好好聊一下Redis數(shù)據(jù)結(jié)構(gòu)，這個在面試中太常問了。注意，Redis數(shù)據(jù)結(jié)構(gòu)并不是指tri...
Redis 為什么那么快？除了它是內(nèi)存數(shù)據(jù)庫，使得所有的操作都在內(nèi)存上進行之外，還有一個重要因素，它實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，使得我們對數(shù)據(jù)進行增刪查改操作時，Redis 能高效的處理。因此，這次我們就來好好聊一下 Redis 數(shù)據(jù)結(jié)構(gòu)，這個在面試中太常問了。注意，Redis 數(shù)據(jù)結(jié)構(gòu)并不是指 tring（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Zset（有序集合），因為這些是 Redis 鍵值對中值的數(shù)據(jù)類型，并不是數(shù)據(jù)結(jié)構(gòu)。這些數(shù)據(jù)類型的底層實現(xiàn)的方式，才是數(shù)據(jù)結(jié)構(gòu)。Redis 底層的數(shù)據(jù)結(jié)構(gòu)一共有 6 種，如下圖右邊部分，它和數(shù)據(jù)類型對應(yīng)關(guān)系也如下圖：可以看到，有些數(shù)據(jù)類型可以由兩種 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，比如：
- List 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「雙向鏈表」或「壓縮表列表」實現(xiàn)；
- Hash 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「壓縮列表」或「哈希表」實現(xiàn)；
- Set 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「哈希表」或「整數(shù)集合」實現(xiàn)；
- Zset 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「壓縮列表」或「跳表」實現(xiàn)；
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)：沒學(xué)過 C 語言的同學(xué)，可能會好奇為什么最后一個字符是“\0”？在 C 語言里，對字符串操作時，char * 指針只是指向字符數(shù)組的起始位置，而字符數(shù)組的結(jié)尾位置就用“\0”表示，意思是指字符串的結(jié)束。因此，C 語言標(biāo)準(zhǔn)庫中字符串的操作函數(shù)，就通過判斷字符是不是“\0”，如果不是說明字符串還沒結(jié)束，可以繼續(xù)操作，如果是則說明字符串結(jié)束了，停止操作。舉個例子，C 語言獲取字符串長度的函數(shù) strlen，就是通過字符數(shù)組中的每一個字符，并進行計數(shù)，等遇到字符為“\0”后，就會停止遍歷，然后返回已經(jīng)統(tǒng)計到的字符個數(shù)，即為字符串長度。下圖顯示了 strlen 函數(shù)的執(zhí)行流程：很明顯，C 語言獲取字符串長度操作的時間復(fù)雜度是 O（N）（這是一個可以改進的地方）C 語言的字符串用 “\0” 字符作為結(jié)尾標(biāo)記有個缺陷。假設(shè)有個字符串中有個 “\0” 字符，這時在操作這個字符串時就會提早結(jié)束，比如 “xiao\0lin” 字符串，計算字符串長度的時候則會是 4，如下圖：還有，除了字符串中不能 “\0” 字符外，用 char* 字符串中的字符必須符合某種編碼（比如ASCII）。這些限制使得 C 語言的字符串只能保存文本數(shù)據(jù)，不能保存像圖片、音頻、視頻文化這樣的二進制數(shù)據(jù)（這也是一個可以改進的地方）C 語言標(biāo)準(zhǔn)庫中字符串的操作函數(shù)是很不安全的，對程序員很不友好，稍微一不注意，就會導(dǎo)致緩沖區(qū)溢出。舉個例子，strcat 函數(shù)是可以將兩個字符串拼接在一起。c //將 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ū)溢出將可能會造成程序運行終止，（這是一個可以改進的地方）。而且，strcat 函數(shù)和 strlen 函數(shù)類似，時間復(fù)雜度也很高，也都需要先通過遍歷字符串才能得到目標(biāo)字符串的末尾。然后對于 strcat 函數(shù)來說，還要再遍歷源字符串才能完成追加，對字符串的操作效率不高。好了， 通過以上的分析，我們可以得知 C 語言的字符串 不足之處以及可以改進的地方：- 獲取字符串長度的時間復(fù)雜度為 ?O（N）；
- 字符串的結(jié)尾是以 “\0” 字符標(biāo)識，而且字符必須符合某種編碼（比如ASCII），只能保存文本數(shù)據(jù)，不能保存二進制數(shù)據(jù)；
- 字符串操作函數(shù)不高效且不安全，比如可能會發(fā)生緩沖區(qū)溢出，從而造成程序運行終止；
SDS 結(jié)構(gòu)設(shè)計
下圖就是 Redis 5.0 的 SDS 的數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)中的每個成員變量分別介紹下：- len，SDS 所保存的字符串長度。這樣獲取字符串長度的時候，只需要返回這個變量值就行，時間復(fù)雜度只需要 O（1）。
- alloc，分配給字符數(shù)組的空間長度。這樣在修改字符串的時候，可以通過
alloc - len 計算 出剩余的空間大小，然后用來判斷空間是否滿足修改需求，如果不滿足的話，就會自動將 SDS ?的空間擴展至執(zhí)行修改所需的大小，然后才執(zhí)行實際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現(xiàn)前面所說的緩沖區(qū)益處的問題。
- flags，SDS 類型，用來表示不同類型的 SDS。一共設(shè)計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說明區(qū)別之處。
- buf[]，字節(jié)數(shù)組，用來保存實際數(shù)據(jù)。不需要用 “\0” 字符來標(biāo)識字符串結(jié)尾了，而是直接將其作為二進制數(shù)據(jù)處理，可以用來保存圖片等二進制數(shù)據(jù)。它即可以保存文本數(shù)據(jù)，也可以保存二進制數(shù)據(jù)，所以叫字節(jié)數(shù)組會更好點。
alloc - len 計算，可以算出剩余可用的空間大小，這樣在對字符串做修改操作的時候，就可以由程序內(nèi)部判斷緩沖區(qū)大小是否足夠用。
而且，當(dāng)判斷出緩沖區(qū)大小不夠用時，Redis 會自動將擴大 SDS 的空間大小，以滿足修改所需的大小。在擴展 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ù)進行對齊。
比如，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ù)組之外，相信大家最熟悉的數(shù)據(jù)結(jié)構(gòu)就是鏈表了。Redis 的 list 數(shù)據(jù)類型的底層實現(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ù)。
- listNode 鏈表節(jié)點帶有 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é)點可以保存各種不同類型的值；
壓縮列表
壓縮列表是 Redis 數(shù)據(jù)類型為 list 和 hash 的底層實現(xiàn)之一。- 當(dāng)一個列表鍵（list）只包含少量的列表項，并且每個列表項都是小整數(shù)值，或者長度比較短的字符串，那么 Redis 就會使用壓縮列表作為列表鍵（list）的底層實現(xiàn)。
- 當(dāng)一個哈希鍵（hash）只包含少量鍵值對，并且每個鍵值對的鍵和值都是小整數(shù)值，或者長度比較短的字符串，那么 Redis 就會使用壓縮列表作為哈希鍵（hash）的底層實現(xiàn)。
壓縮列表結(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é)束點，特殊值 OxFF（十進制255）。
- prevlen，記錄了前一個節(jié)點的長度；
- encoding，記錄了當(dāng)前節(jié)點實際數(shù)據(jù)的類型以及長度；
- data，記錄了當(dāng)前節(jié)點的實際數(shù)據(jù)；
連鎖更新
壓縮列表除了查找復(fù)雜度高的問題，壓縮列表在插入元素時，如果內(nèi)存空間不夠了，壓縮列表還需要重新分配一塊連續(xù)的內(nèi)存空間，而這可能會引發(fā)連鎖更新的問題。壓縮列表里的每個節(jié)點中的 ?prevlen 屬性都記錄了「前一個節(jié)點的長度」，而且 prevlen 屬性的空間大小跟前一個節(jié)點長度值有關(guān)，比如：- 如果前一個節(jié)點的長度小于 254 字節(jié)，那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個長度值；
- 如果前一個節(jié)點的長度大于等于 254 字節(jié)，那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個長度值；
哈希表
哈希表是一種保存鍵值對（key-value）的數(shù)據(jù)結(jié)構(gòu)。哈希表中的每一個 key 都是獨一無二的，程序可以根據(jù) key 查找到與之關(guān)聯(lián)的 value，或者通過 key 來更新 value，又或者根據(jù) key 來刪除整個 key-value等等。在講壓縮列表的時候，提到過 Redis 的 hash 數(shù)據(jù)類型的底層實現(xiàn)之一是壓縮列表。hash 數(shù)據(jù)類型的另外一個底層實現(xiàn)就是哈希表。那 hash 數(shù)據(jù)類型什么時候會選用哈希表作為底層實現(xiàn)呢？當(dāng)一個哈希鍵包含的 key-value 比較多，或者 key-value 中元素都是比較長多字符串時，Redis 就會使用哈希表作為哈希鍵的底層實現(xiàn)。Hash 表優(yōu)點在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。主要是通過 Hash 函數(shù)的計算，就能定位數(shù)據(jù)在表中的位置，緊接著可以對數(shù)據(jù)進行操作，這就使得數(shù)據(jù)操作非?？?。但是存在的風(fēng)險也是有，在哈希表大小固定的情況下，隨著數(shù)據(jù)不斷增多，那么哈希沖突的可能性也會越高。解決哈希沖突的方式，有很多種。Redis 采用了鏈?zhǔn)焦＃诓粩U容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)鏈接起來，以便這些數(shù)據(jù)在表中仍然可以被查詢到。接下來，詳細(xì)說說哈希沖突以及鏈?zhǔn)焦！?/p>哈希沖突
哈希表實際上是一個數(shù)組，數(shù)組里多每一個元素就是一個哈希桶。當(dāng)一個鍵值對的鍵經(jīng)過 Hash 函數(shù)計算后得到哈希值，再將(哈希值 % 哈希表大小)取模計算，得到的結(jié)果值就是該 key-value 對應(yīng)的數(shù)組元素位置，也就是第幾個哈希桶。舉個例子，有一個可以存放 8 個哈希桶的哈希表。key1 經(jīng)過哈希函數(shù)計算后，再將「哈希值 % 8 」進行取模計算，結(jié)果值為 1，那么就對應(yīng)哈希桶 1，類似的，key9 和 key10 分別對應(yīng)哈希桶 1 和桶 6。此時，key1 和 key9 對應(yīng)到了相同的哈希桶中，這就發(fā)生了哈希沖突。因此，當(dāng)有兩個以上數(shù)量的 kay 被分配到了哈希表數(shù)組的同一個哈希桶上時，此時稱這些 key 發(fā)生了沖突。鏈?zhǔn)焦?/span>
Redis 采用了「鏈?zhǔn)焦！沟姆椒▉斫鉀Q哈希沖突。實現(xiàn)的方式就是每個哈希表節(jié)點都有一個 next 指針，多個哈希表節(jié)點可以用 next 指針構(gòu)成一個單項鏈表，被分配到同一個哈希桶上的多個節(jié)點可以用這個單項鏈表連接起來，這樣就解決了哈希沖突。還是用前面的哈希沖突例子，key1 和 key9 經(jīng)過哈希計算后，都落在同一個哈希桶，鏈?zhǔn)焦５脑挘琸ey1 就會通過 next 指針指向 key9，形成一個單向鏈表。不過，鏈?zhǔn)焦＞窒扌砸埠苊黠@，隨著鏈表長度的增加，在查詢這一位置上的數(shù)據(jù)的耗時就會增加，畢竟鏈表的查詢的時間復(fù)雜度是 O（n）。要想解決這一問題，就需要進行 rehash，就是對哈希表的大小進行擴展。接下來，看看 Redis 是如何實現(xiàn)的 rehash 的。rehash
Redis 會使用了兩個全局哈希表進行 rehash。在正常服務(wù)請求階段，插入的數(shù)據(jù)，都會寫入到「哈希表 1」，此時的「哈希表 2 」 并沒有被分配空間。隨著數(shù)據(jù)逐步增多，觸發(fā)了 rehash 操作，這個過程分為三步：- 給「哈希表 2」 分配空間，一般會比「哈希表 1」 大 2 倍；
- 將「哈希表 1 」的數(shù)據(jù)遷移到「哈希表 2」 中；
- 遷移完成后，「哈希表 1 」的空間會被釋放，并把「哈希表 2」 設(shè)置為「哈希表 1」，然后在「哈希表 2」 新創(chuàng)建一個空白的哈希表，為下次 rehash 做準(zhǔn)備。
漸進式 rehash
為了避免 rehash 在數(shù)據(jù)遷移過程中，因拷貝數(shù)據(jù)的耗時，影響 Redis 性能的情況，所以 Redis 采用了漸進式 rehash，也就是將數(shù)據(jù)的遷移的工作不再是一次性遷移完成，而是分多次遷移。漸進式 rehash 步驟如下：- 給「哈希表 2」 分配空間；
- 在 rehash 進行期間，每次哈希表元素進行新增、刪除、查找或者更新操作時，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ù)載因子可以通過下面這個公式計算：觸發(fā) rehash 操作的條件，主要有兩個：- 當(dāng)負(fù)載因子大于等于 1 ，并且 Redis 沒有在執(zhí)行 bgsave 命令或者 bgrewiteaof 命令，也就是沒有執(zhí)行 RDB 快照或沒有進行 AOF 重寫的時候，就會進行 rehash 操作。
- 當(dāng)負(fù)載因子大于等于 5 時，此時說明哈希沖突非常嚴(yán)重了，不管有沒有有在執(zhí)行 RDB 快照或 AOF 重寫，都會強制進行 rehash 操作。
下載文檔
