為了拿捏?Redis?數(shù)據(jù)結(jié)構(gòu)，我畫了?20?張圖
[導(dǎo)讀]大家好，我是小林。Redis為什么那么快？除了它是內(nèi)存數(shù)據(jù)庫，使得所有的操作都在內(nèi)存上進(jìn)行之外，還有一個重要因素，它實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，使得我們對數(shù)據(jù)進(jìn)行增刪查改操作時，Redis能高效的處理。因此，這次我們就來好好聊一下Redis數(shù)據(jù)結(jié)構(gòu)，這個在面試中太常問了。注意，Redis數(shù)據(jù)...
大家好，我是小林。Redis 為什么那么快？除了它是內(nèi)存數(shù)據(jù)庫，使得所有的操作都在內(nèi)存上進(jìn)行之外，還有一個重要因素，它實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，使得我們對數(shù)據(jù)進(jìn)行增刪查改操作時，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ù)類型的底層實(shí)現(xiàn)的方式，才是數(shù)據(jù)結(jié)構(gòu)。Redis 底層的數(shù)據(jù)結(jié)構(gòu)一共有 6 種，如下圖右邊部分，它和數(shù)據(jù)類型對應(yīng)關(guān)系也如下圖：
我們下次見啦，嘻嘻
- List 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「雙向鏈表」或「壓縮表列表」實(shí)現(xiàn)；
- Hash 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「壓縮列表」或「哈希表」實(shí)現(xiàn)；
- Set 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「哈希表」或「整數(shù)集合」實(shí)現(xiàn)；
- Zset 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)由「壓縮列表」或「跳表」實(shí)現(xiàn)；
SDS
字符串在 Redis 中是很常用的，鍵值對中的鍵是字符串，值有時也是字符串。Redis 是用 C 語言實(shí)現(xiàn)的，但是它沒有直接使用 C 語言的 char* 字符數(shù)組來實(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ù)組存在一些缺陷。要了解這一點(diǎn)，得先來看看 char* 字符數(shù)組的結(jié)構(gòu)。C 語言字符串的缺陷
C 語言的字符串其實(shí)就是一個字符數(shù)組，即數(shù)組中每個元素是字符串中的一個字符。比如，下圖就是字符串“xiaolin”的 char* 字符數(shù)組的結(jié)構(gòu)：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ū)溢出將可能會造成程序運(yùn)行終止，（這是一個可以改進(jìn)的地方）。而且，strcat 函數(shù)和 strlen 函數(shù)類似，時間復(fù)雜度也很高，也都需要先通過遍歷字符串才能得到目標(biāo)字符串的末尾。然后對于 strcat 函數(shù)來說，還要再遍歷源字符串才能完成追加，對字符串的操作效率不高。好了， 通過以上的分析，我們可以得知 C 語言的字符串 不足之處以及可以改進(jìn)的地方：- 獲取字符串長度的時間復(fù)雜度為 ?O（N）；
- 字符串的結(jié)尾是以 “\0” 字符標(biāo)識，而且字符必須符合某種編碼（比如ASCII），只能保存文本數(shù)據(jù)，不能保存二進(jìn)制數(shù)據(jù)；
- 字符串操作函數(shù)不高效且不安全，比如可能會發(fā)生緩沖區(qū)溢出，從而造成程序運(yùn)行終止；
SDS 結(jié)構(gòu)設(shè)計
下圖就是 Redis 5.0 的 SDS 的數(shù)據(jù)結(jié)構(gòu)：- len，SDS 所保存的字符串長度。這樣獲取字符串長度的時候，只需要返回這個變量值就行，時間復(fù)雜度只需要 O（1）。
- alloc，分配給字符數(shù)組的空間長度。這樣在修改字符串的時候，可以通過
alloc - len計算 出剩余的空間大小，然后用來判斷空間是否滿足修改需求，如果不滿足的話，就會自動將 SDS ?的空間擴(kuò)展至執(zhí)行修改所需的大小，然后才執(zhí)行實(shí)際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現(xiàn)前面所說的緩沖區(qū)益處的問題。 - flags，SDS 類型，用來表示不同類型的 SDS。一共設(shè)計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說明區(qū)別之處。
- buf[]，字節(jié)數(shù)組，用來保存實(shí)際數(shù)據(jù)。不需要用 “\0” 字符來標(biāo)識字符串結(jié)尾了，而是直接將其作為二進(jìn)制數(shù)據(jù)處理，可以用來保存圖片等二進(jìn)制數(shù)據(jù)。它即可以保存文本數(shù)據(jù)，也可以保存二進(jìn)制數(shù)據(jù)，所以叫字節(jié)數(shù)組會更好點(diǎn)。
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é)尾了，而且 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 和 leb 成員變量，這樣 SDS API 通過alloc - len 計算，可以算出剩余可用的空間大小，這樣在對字符串做修改操作的時候，就可以由程序內(nèi)部判斷緩沖區(qū)大小是否足夠用。而且，當(dāng)判斷出緩沖區(qū)大小不夠用時，Redis 會自動將擴(kuò)大 SDS 的空間大小，以滿足修改所需的大小。在擴(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)化對齊，按照實(shí)際占用字節(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)體實(shí)際占用多少內(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ù)類型的底層實(shí)現(xiàn)之一就是鏈表。C 語言本身也是沒有鏈表這個數(shù)據(jù)結(jié)構(gòu)的，所以 Redis 自己設(shè)計了一個鏈表數(shù)據(jù)結(jié)構(gòu)。鏈表節(jié)點(diǎn)結(jié)構(gòu)設(shè)計
先來看看鏈表節(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)，可以看的出，這個是一個雙向鏈表。鏈表結(jié)構(gòu)設(shè)計
不過，Redis 在 listNode 結(jié)構(gòu)體基礎(chǔ)上又封裝了 list 這個數(shù)據(jù)結(jié)構(gòu)，這樣操作起來會更方便，鏈表結(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ù)。舉個例子，下面是由 list 結(jié)構(gòu)和 3 個 listNode 結(jié)構(gòu)組成的鏈表。- listNode 鏈表節(jié)點(diǎn)帶有 prev 和 next 指針，獲取某個節(jié)點(diǎn)的前置節(jié)點(diǎn)或后置節(jié)點(diǎn)的時間復(fù)雜度只需O(1)，而且這兩個指針都可以指向 NULL，所以鏈表是無環(huán)鏈表；
- list 結(jié)構(gòu)因為提供了表頭指針 head 和表尾節(jié)點(diǎn) tail，所以獲取鏈表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的時間復(fù)雜度只需O(1)；
- list 結(jié)構(gòu)因為提供了鏈表節(jié)點(diǎn)數(shù)量 len，所以獲取鏈表中的節(jié)點(diǎn)數(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)可以保存各種不同類型的值；
壓縮列表
壓縮列表是 Redis 數(shù)據(jù)類型為 list 和 hash 的底層實(shí)現(xiàn)之一。- 當(dāng)一個列表鍵（list）只包含少量的列表項，并且每個列表項都是小整數(shù)值，或者長度比較短的字符串，那么 Redis 就會使用壓縮列表作為列表鍵（list）的底層實(shí)現(xiàn)。
- 當(dāng)一個哈希鍵（hash）只包含少量鍵值對，并且每個鍵值對的鍵和值都是小整數(shù)值，或者長度比較短的字符串，那么 Redis 就會使用壓縮列表作為哈希鍵（hash）的底層實(shí)現(xiàn)。
壓縮列表結(jié)構(gòu)設(shè)計
壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的，它是由連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，有點(diǎn)類似于數(shù)組。- zlbytes，記錄整個壓縮列表占用對內(nèi)存字節(jié)數(shù)；
- zltail，記錄壓縮列表「尾部」節(jié)點(diǎn)距離起始地址由多少字節(jié)，也就是列表尾的偏移量；
- zllen，記錄壓縮列表包含的節(jié)點(diǎn)數(shù)量；
- zlend，標(biāo)記壓縮列表的結(jié)束點(diǎn)，特殊值 OxFF（十進(jìn)制255）。
- prevlen，記錄了前一個節(jié)點(diǎn)的長度；
- encoding，記錄了當(dāng)前節(jié)點(diǎn)實(shí)際數(shù)據(jù)的類型以及長度；
- data，記錄了當(dāng)前節(jié)點(diǎn)的實(shí)際數(shù)據(jù)；
連鎖更新
壓縮列表除了查找復(fù)雜度高的問題，壓縮列表在插入元素時，如果內(nèi)存空間不夠了，壓縮列表還需要重新分配一塊連續(xù)的內(nèi)存空間，而這可能會引發(fā)連鎖更新的問題。壓縮列表里的每個節(jié)點(diǎn)中的 ?prevlen 屬性都記錄了「前一個節(jié)點(diǎn)的長度」，而且 prevlen 屬性的空間大小跟前一個節(jié)點(diǎn)長度值有關(guān)，比如：- 如果前一個節(jié)點(diǎn)的長度小于 254 字節(jié)，那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個長度值；
- 如果前一個節(jié)點(diǎn)的長度大于等于 254 字節(jié)，那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個長度值；
哈希表
哈希表是一種保存鍵值對（key-value）的數(shù)據(jù)結(jié)構(gòu)。哈希表中的每一個 key 都是獨(dú)一無二的，程序可以根據(jù) key 查找到與之關(guān)聯(lián)的 value，或者通過 key 來更新 value，又或者根據(jù) key 來刪除整個 key-value等等。在講壓縮列表的時候，提到過 Redis 的 hash 數(shù)據(jù)類型的底層實(shí)現(xiàn)之一是壓縮列表。hash 數(shù)據(jù)類型的另外一個底層實(shí)現(xiàn)就是哈希表。那 hash 數(shù)據(jù)類型什么時候會選用哈希表作為底層實(shí)現(xiàn)呢？當(dāng)一個哈希鍵包含的 key-value 比較多，或者 key-value 中元素都是比較長多字符串時，Redis 就會使用哈希表作為哈希鍵的底層實(shí)現(xiàn)。Hash 表優(yōu)點(diǎn)在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。主要是通過 Hash 函數(shù)的計算，就能定位數(shù)據(jù)在表中的位置，緊接著可以對數(shù)據(jù)進(jìn)行操作，這就使得數(shù)據(jù)操作非?？?。但是存在的風(fēng)險也是有，在哈希表大小固定的情況下，隨著數(shù)據(jù)不斷增多，那么哈希沖突的可能性也會越高。解決哈希沖突的方式，有很多種。Redis 采用了鏈?zhǔn)焦?，在不擴(kuò)容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)鏈接起來，以便這些數(shù)據(jù)在表中仍然可以被查詢到。接下來，詳細(xì)說說哈希沖突以及鏈?zhǔn)焦！?/p>哈希沖突
哈希表實(shí)際上是一個數(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哈希沖突。實(shí)現(xiàn)的方式就是每個哈希表節(jié)點(diǎn)都有一個 next 指針，多個哈希表節(jié)點(diǎn)可以用 next 指針構(gòu)成一個單項鏈表，被分配到同一個哈希桶上的多個節(jié)點(diǎn)可以用這個單項鏈表連接起來，這樣就解決了哈希沖突。還是用前面的哈希沖突例子，key1 和 key9 經(jīng)過哈希計算后，都落在同一個哈希桶，鏈?zhǔn)焦５脑?，key1 就會通過 next 指針指向 key9，形成一個單向鏈表。rehash
Redis 會使用了兩個全局哈希表進(jìn)行 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)備。
漸進(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ù)據(jù)結(jié)構(gòu)還沒講呀，怎么就突然結(jié)束了！”實(shí)在抱歉，今天肝了一天實(shí)在沒有肝完，所有就先發(fā)出來來，后面小林會在把這篇繼續(xù)完善大家就先消化掉今天的內(nèi)容，還是蠻多的，畢竟 1 萬字呀！大家覺得還有什么可以補(bǔ)充的，可以留言說下，這樣我在補(bǔ)下篇文章的時候，可以寫上去，然后出一個完整版。我們下次見啦，嘻嘻
下載文檔
