圖解 Redis 數(shù)據(jù)結(jié)構(gòu)
掃描二維碼
隨時(shí)隨地手機(jī)看文章
- 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)焦5脑?,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?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 操作。