圖解 Redis 數(shù)據(jù)結(jié)構(gòu)
時(shí)間：2021-12-13 13:52:04
關(guān)鍵字：
數(shù)據(jù)結(jié)構(gòu)
REDIS
字符串
節(jié)點(diǎn)
手機(jī)看文章
掃描二維碼
隨時(shí)隨地手機(jī)看文章
[導(dǎo)讀]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)并不是指tri...
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)并不是指 tring（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Zset（有序集合），因?yàn)檫@些是 Redis 鍵值對(duì)中值的數(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ù)類型對(duì)應(yīng)關(guān)系也如下圖：可以看到，有些數(shù)據(jù)類型可以由兩種 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xià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 中是很常用的，鍵值對(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”，如果不是說(shuō)明字符串還沒(méi)結(jié)束，可以繼續(xù)操作，如果是則說(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” 字符外，用 char* 字符串中的字符必須符合某種編碼（比如ASCII）。這些限制使得 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è)字符串拼接在一起。c //將 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í)，而且字符必須符合某種編碼（比如ASCII），只能保存文本數(shù)據(jù)，不能保存二進(jìn)制數(shù)據(jù)；
- 字符串操作函數(shù)不高效且不安全，比如可能會(huì)發(fā)生緩沖區(qū)溢出，從而造成程序運(yùn)行終止；
SDS 結(jié)構(gòu)設(shè)計(jì)
下圖就是 Redis 5.0 的 SDS 的數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)中的每個(gè)成員變量分別介紹下：- len，SDS 所保存的字符串長(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，SDS 類型，用來(lái)表示不同類型的 SDS。一共設(shè)計(jì)了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說(shuō)明區(qū)別之處。
- buf[]，字節(jié)數(shù)組，用來(lái)保存實(shí)際數(shù)據(jù)。不需要用 “\0” 字符來(lái)標(biāo)識(shí)字符串結(jié)尾了，而是直接將其作為二進(jìn)制數(shù)據(jù)處理，可以用來(lái)保存圖片等二進(jìn)制數(shù)據(jù)。它即可以保存文本數(shù)據(jù)，也可以保存二進(jìn)制數(shù)據(jù)，所以叫字節(jié)數(shù)組會(huì)更好點(diǎn)。
alloc - len 計(jì)算，可以算出剩余可用的空間大小，這樣在對(duì)字符串做修改操作的時(shí)候，就可以由程序內(nèi)部判斷緩沖區(qū)大小是否足夠用。
而且，當(dāng)判斷出緩沖區(qū)大小不夠用時(shí)，Redis 會(huì)自動(dòng)將擴(kuò)大 SDS 的空間大小，以滿足修改所需的大小。在擴(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 次方。
__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?
?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。
__attribute__ ((packed)) 屬性定義結(jié)構(gòu)體，這樣一來(lái)，結(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ù)組之外，相信大家最熟悉的數(shù)據(jù)結(jié)構(gòu)就是鏈表了。Redis 的 list 數(shù)據(jù)類型的底層實(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ù)。
- listNode 鏈表節(jié)點(diǎn)帶有 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)可以保存各種不同類型的值；
壓縮列表
壓縮列表是 Redis 數(shù)據(jù)類型為 list 和 hash 的底層實(shí)現(xiàn)之一。- 當(dāng)一個(gè)列表鍵（list）只包含少量的列表項(xiàng)，并且每個(gè)列表項(xiàng)都是小整數(shù)值，或者長(zhǎng)度比較短的字符串，那么 Redis 就會(huì)使用壓縮列表作為列表鍵（list）的底層實(shí)現(xiàn)。
- 當(dāng)一個(gè)哈希鍵（hash）只包含少量鍵值對(duì)，并且每個(gè)鍵值對(duì)的鍵和值都是小整數(shù)值，或者長(zhǎng)度比較短的字符串，那么 Redis 就會(huì)使用壓縮列表作為哈希鍵（hash）的底層實(shí)現(xiàn)。
壓縮列表結(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)，特殊值 OxFF（十進(jìn)制255）。
- 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ù)；
連鎖更新
壓縮列表除了查找復(fù)雜度高的問(wèn)題，壓縮列表在插入元素時(shí)，如果內(nèi)存空間不夠了，壓縮列表還需要重新分配一塊連續(xù)的內(nèi)存空間，而這可能會(huì)引發(fā)連鎖更新的問(wè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)度值；
哈希表
哈希表是一種保存鍵值對(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 數(shù)據(jù)類型的底層實(shí)現(xiàn)之一是壓縮列表。hash 數(shù)據(jù)類型的另外一個(gè)底層實(shí)現(xiàn)就是哈希表。那 hash 數(shù)據(jù)類型什么時(shí)候會(huì)選用哈希表作為底層實(shí)現(xiàn)呢？當(dāng)一個(gè)哈希鍵包含的 key-value 比較多，或者 key-value 中元素都是比較長(zhǎng)多字符串時(shí)，Redis 就會(huì)使用哈希表作為哈希鍵的底層實(shí)現(xiàn)。Hash 表優(yōu)點(diǎn)在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。主要是通過(guò) Hash 函數(shù)的計(jì)算，就能定位數(shù)據(jù)在表中的位置，緊接著可以對(duì)數(shù)據(jù)進(jìn)行操作，這就使得數(shù)據(jù)操作非?？?。但是存在的風(fēng)險(xiǎn)也是有，在哈希表大小固定的情況下，隨著數(shù)據(jù)不斷增多，那么哈希沖突的可能性也會(huì)越高。解決哈希沖突的方式，有很多種。Redis 采用了鏈?zhǔn)焦?，在不擴(kuò)容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)鏈接起來(lái)，以便這些數(shù)據(jù)在表中仍然可以被查詢到。接下來(lái)，詳細(xì)說(shuō)說(shuō)哈希沖突以及鏈?zhǔn)焦！?/p>哈希沖突
哈希表實(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 被分配到了哈希表數(shù)組的同一個(gè)哈希桶上時(shí)，此時(shí)稱這些 key 發(fā)生了沖突。鏈?zhǔn)焦?/span>
Redis 采用了「鏈?zhǔn)焦！沟姆椒▉?lái)解決哈希沖突。實(shí)現(xiàn)的方式就是每個(gè)哈希表節(jié)點(diǎn)都有一個(gè) next 指針，多個(gè)哈希表節(jié)點(diǎn)可以用 next 指針構(gòu)成一個(gè)單項(xiàng)鏈表，被分配到同一個(gè)哈希桶上的多個(gè)節(jié)點(diǎn)可以用這個(gè)單項(xiàng)鏈表連接起來(lái)，這樣就解決了哈希沖突。還是用前面的哈希沖突例子，key1 和 key9 經(jīng)過(guò)哈希計(jì)算后，都落在同一個(gè)哈希桶，鏈?zhǔn)焦５脑?，key1 就會(huì)通過(guò) next 指針指向 key9，形成一個(gè)單向鏈表。不過(guò)，鏈?zhǔn)焦＞窒扌砸埠苊黠@，隨著鏈表長(zhǎng)度的增加，在查詢這一位置上的數(shù)據(jù)的耗時(shí)就會(huì)增加，畢竟鏈表的查詢的時(shí)間復(fù)雜度是 O（n）。要想解決這一問(wèn)題，就需要進(jìn)行 rehash，就是對(duì)哈希表的大小進(jìn)行擴(kuò)展。接下來(lái)，看看 Redis 是如何實(shí)現(xiàn)的 rehash 的。rehash
Redis 會(huì)使用了兩個(gè)全局哈希表進(jìn)行 rehash。在正常服務(wù)請(qǐng)求階段，插入的數(shù)據(jù)，都會(huì)寫入到「哈希表 1」，此時(shí)的「哈希表 2 」 并沒(méi)有被分配空間。隨著數(shù)據(jù)逐步增多，觸發(fā)了 rehash 操作，這個(gè)過(guò)程分為三步：- 給「哈希表 2」 分配空間，一般會(huì)比「哈希表 1」 大 2 倍；
- 將「哈希表 1 」的數(shù)據(jù)遷移到「哈希表 2」 中；
- 遷移完成后，「哈希表 1 」的空間會(huì)被釋放，并把「哈希表 2」 設(shè)置為「哈希表 1」，然后在「哈希表 2」 新創(chuàng)建一個(gè)空白的哈希表，為下次 rehash 做準(zhǔn)備。
漸進(jìn)式 rehash
為了避免 rehash 在數(shù)據(jù)遷移過(guò)程中，因拷貝數(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ù)量越多，最終會(huì)把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。
rehash 觸發(fā)條件
介紹了 rehash 那么多，還沒(méi)說(shuō)什么時(shí)情況下會(huì)觸發(fā) rehash 操作呢？rehash 的觸發(fā)條件跟負(fù)載因子（load factor）有關(guān)系。負(fù)載因子可以通過(guò)下面這個(gè)公式計(jì)算：觸發(fā) rehash 操作的條件，主要有兩個(gè)：- 當(dāng)負(fù)載因子大于等于 1 ，并且 Redis 沒(méi)有在執(zhí)行 bgsave 命令或者 bgrewiteaof 命令，也就是沒(méi)有執(zhí)行 RDB 快照或沒(méi)有進(jìn)行 AOF 重寫的時(shí)候，就會(huì)進(jìn)行 rehash 操作。
- 當(dāng)負(fù)載因子大于等于 5 時(shí)，此時(shí)說(shuō)明哈希沖突非常嚴(yán)重了，不管有沒(méi)有有在執(zhí)行 RDB 快照或 AOF 重寫，都會(huì)強(qiáng)制進(jìn)行 rehash 操作。
下載文檔
