[[407448]]

騰訊面試官：說說Redis的哈希表是如何擴(kuò)容的?

面試者：what?額......，(我懵了!)這個(gè)我還沒了解過，尬...。但我了解java里面的HashMap的擴(kuò)容，我覺得應(yīng)該有相通的一些原理在里面吧，然后我就把HashMap的擴(kuò)容機(jī)制balabla的說了一遍......

Redis中使用哈希表作為底層實(shí)現(xiàn)的是叫做字典的數(shù)據(jù)結(jié)構(gòu)，字典又稱為符號(hào)表、關(guān)聯(lián)數(shù)組或映射(map)。是一種保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。

如果你對Java HashMap有所了解的話，那么Redis哈希表就是類似Java中HashMap。

由于Redis是用C語言寫的，所以要搞懂C的相關(guān)實(shí)現(xiàn)原理去看源碼的話就要對C語言有一定的了解。

目錄

1、哈希表結(jié)構(gòu)

哈希表例子

2、字典數(shù)據(jù)結(jié)構(gòu)

字典例子

3、解決哈希沖突

4、擴(kuò)容/縮容——rehash

4.1、對字典的哈希表rehash步驟

4.2、看一次哈希表rehash擴(kuò)容過程

5、漸進(jìn)式rehash

5.1、漸進(jìn)式rehash步驟

5.2、看下一次完整的漸進(jìn)式rehash擴(kuò)容的過程

6、總結(jié)

01哈希表結(jié)構(gòu)

哈希表是由dictht結(jié)構(gòu)體定義，table是一個(gè)數(shù)組，數(shù)組中每個(gè)元素是一個(gè)指向dictEntry結(jié)構(gòu)的指針。

dictEntry是哈希表的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)保存著一個(gè)鍵值對key、value，value可以是一個(gè)指針、或者是一個(gè)unit64_t或int64_t整數(shù)。

next屬性則是一個(gè)指向另一個(gè)哈希表節(jié)點(diǎn)的指針，形成一個(gè)鏈表，主要也是為了解決哈希沖突問題。

哈希表例子

一個(gè)空的哈希表

索引值相同的兩個(gè)節(jié)點(diǎn)使用鏈表連接起來

02字典數(shù)據(jù)結(jié)構(gòu)

其實(shí)說到哈希表的話順便要了解下字典這種數(shù)據(jù)結(jié)構(gòu)，畢竟它的底層就是哈希表來實(shí)現(xiàn)，可以了解下擴(kuò)容縮容相關(guān)的。

type：指向dictType指針，保存了操作特定類型鍵值對的函數(shù)，Redis為不同用途的字典設(shè)置不同的類型特定函數(shù)。

privdata：保存了需要傳遞給不同特定函數(shù)的可選參數(shù)。

ht[2]：兩個(gè)哈希表，字典使用的哈希表是ht[0]，ht[1]則是當(dāng)對ht[0]哈希表進(jìn)行rehash時(shí)使用。

trehashidx：記錄當(dāng)前rehash進(jìn)度，沒有進(jìn)行rehash則為-1。

字典例子

普通狀態(tài)下的字典

03解決哈希沖突

將一個(gè)鍵值對添加到字典時(shí)，需要計(jì)算其哈希值和索引值，接著根據(jù)索引值將新節(jié)點(diǎn)放到哈希表數(shù)組的指定索引上。

計(jì)算哈希值：

hash = dict->type->hashFunction(key) 

計(jì)算索引值：

hash & dict->ht[x].sizemask 

鍵沖突：當(dāng)兩個(gè)或以上數(shù)量的鍵進(jìn)行哈希之后索引值一樣，也就是說兩個(gè)節(jié)點(diǎn)要放在同一個(gè)同桶里，這時(shí)可能就會(huì)存在覆蓋(沖突)，那么就得解決這種沖突了。

Redis解決鍵沖突的方法：鏈地址法(separate chaining)——拉鏈法，假設(shè)你已了解Java HashMap原理，這里鏈地址法原理就不細(xì)說了。

插入一個(gè)題外話(也是筆者遇過的一道面試題)：解決哈希沖突有什么方法?答案：①再哈希法;②鏈地址法;③開放地址法;④建立公共溢出區(qū)。(每種方法可以自行簡單了解下即可)

04擴(kuò)容/縮容——rehash

首先，我們要清楚為什么要進(jìn)行擴(kuò)容或縮容?

擴(kuò)容原因：當(dāng)hashtable存儲(chǔ)的元素過多，可能由于碰撞也過多，導(dǎo)致其中某天鏈表很長，最后致使查找和插入時(shí)間復(fù)雜度很大。因此當(dāng)元素超多一定的時(shí)候就需要擴(kuò)容。

縮容原因：當(dāng)元素?cái)?shù)量比較少的時(shí)候就需要縮容以節(jié)約不必要的內(nèi)存。

為了讓哈希表的負(fù)載因子(load factor)維持在一個(gè)合理的范圍內(nèi)，會(huì)使用rehash(重新散列)操作對哈希表進(jìn)行相應(yīng)的擴(kuò)展或收縮。

負(fù)載因子的計(jì)算公式：哈希表已保存節(jié)點(diǎn)數(shù)量 / 哈希表大小 load_factor = ht[0].used / ht[0].size

擴(kuò)容的條件：(滿足任一即可)

1)Redis服務(wù)器目前沒有在執(zhí)行BGSAVE或BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于1。

2)Redis服務(wù)器目前在執(zhí)行BGSAVE或BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于5。

(此處為什么負(fù)載因子不同呢?)

縮容的條件：哈希表的負(fù)載因子小于0.1。

4.1、對字典的哈希表rehash步驟

1)為ht[1]分配空間

擴(kuò)展操作，那么ht[1] 的大小為第一個(gè)大于等于ht[0] .used*2的2的n次冪

收縮操作，那么ht[1] 的大小為第一個(gè)大于等于ht[0].used 的2的n次冪

2)將ht[0]中的數(shù)據(jù)轉(zhuǎn)移到ht[1]中，在轉(zhuǎn)移的過程中，重新計(jì)算鍵的哈希值和索引值，然后將鍵值對放置到ht[1]的指定位置。

3)當(dāng)ht[0]的所有鍵值對都遷移到了ht[1]之后(ht[0]變?yōu)榭毡?，將ht[0]釋放，然后將ht[1]設(shè)置成ht[0]，最后為ht[1]分配一個(gè)空白哈希表：

4.2、看一次哈希表rehash擴(kuò)容過程

1)開始rehash之前

2)為ht[1]分配空間，ht[0].used當(dāng)前值為4，8恰好是第一個(gè)大于等于4的2的N次冪，那么當(dāng)前就會(huì)將ht[1]哈希表大小設(shè)置為8。

3)將ht[0]的鍵值對都rehash到ht[1]

ht[0]鍵值對都已遷移到ht[1]

4)釋放ht[0]，將ht[1]設(shè)置為ht[0]，ht[1]再設(shè)置為空的哈希表

rehash擴(kuò)容完成

為什么BGSAVE或BGREWRITEAOF命令是否在執(zhí)行，Redis服務(wù)器哈希表執(zhí)行擴(kuò)容所需的負(fù)載因子不相同(1或5)?

因?yàn)楫?dāng)執(zhí)行BGSAVE或BGREWRITEAOF命令過程中，Redis需要?jiǎng)?chuàng)建服務(wù)器進(jìn)程的子進(jìn)程，操作系統(tǒng)采用的是COW，即寫時(shí)復(fù)制copy-on-write的技術(shù)來優(yōu)化子進(jìn)程的使用效率。所以在子進(jìn)程存在時(shí)，服務(wù)器會(huì)提高執(zhí)行擴(kuò)容所需的負(fù)載因子，從而盡可能避免在子進(jìn)程存在期間進(jìn)行擴(kuò)容，可以避免不必要的內(nèi)存寫入操作，最大限度節(jié)約內(nèi)存。

05漸進(jìn)式rehash

為什么需要漸進(jìn)式rehash呢?

在元素?cái)?shù)量較少時(shí)，rehash會(huì)非?？斓倪M(jìn)行，但是當(dāng)元素?cái)?shù)量達(dá)到幾百、甚至幾個(gè)億時(shí)進(jìn)行rehash將會(huì)是一個(gè)非常耗時(shí)的操作。如果一次性將成萬上億的元素的鍵值對rehash到ht[1]，龐大的計(jì)算量可能會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)，這是非常危險(xiǎn)的!所以，rehash這個(gè)動(dòng)作不能一次性、集中式的完成，而是分多次、漸進(jìn)式地完成。

5.1、漸進(jìn)式rehash步驟：

1)為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表。

2)在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將它的值設(shè)置為0，表示rehash工作正式開始。

3)在rehash進(jìn)行期間，每次對字典執(zhí)行CRUD：添加、刪除、查找或者更新操作時(shí)，程序除了執(zhí)行指定的操作以外，還會(huì)順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]，當(dāng)rehash工作完成之后，程序?qū)ehashidx+1(表示下次將rehash下一個(gè)桶)。

4)隨著字典操作的不斷執(zhí)行，最終在某個(gè)時(shí)間點(diǎn)上，ht[0]的所有鍵值對都會(huì)被rehash至ht[1]，這時(shí)程序?qū)ehashidx屬性的值設(shè)為-1，表示rehash完成。

漸進(jìn)式rehash的好處在于它采取分而治之的方式，將rehash鍵值對所需的計(jì)算工作均攤到對字典的每個(gè)添加、刪除、查找和更新操作上，從而避免了集中式rehash 而帶來的龐大計(jì)算量。

5.2、看下一次完整的漸進(jìn)式rehash擴(kuò)容的過程

1)準(zhǔn)備進(jìn)行漸進(jìn)式rehash

準(zhǔn)備rehash

2)此時(shí)rehashidx=0,也就是會(huì)將索引為0的鍵值對進(jìn)行遷移

rehash索引0上的鍵值對

3)接著，rehashidx繼續(xù)遞增，假如到最后將索引3的進(jìn)行遷移，如下：

最后一次rehash，索引為3上的鍵值對進(jìn)行遷移

4)漸進(jìn)式rehash結(jié)束

rehash結(jié)束

了解了漸進(jìn)式rehash的原理和過程，那么可能會(huì)有下面這些疑問：

在遷移的過程中，會(huì)不會(huì)造成讀少數(shù)據(jù)?

不會(huì)，因?yàn)樵谶w移時(shí)，首先會(huì)從ht[0]讀取數(shù)據(jù)，如果ht[0]讀不到，則會(huì)去ht[1]讀。

在遷移過程中，新增加的數(shù)據(jù)會(huì)存放在哪個(gè)ht?

遷移過程中，新增的數(shù)據(jù)只會(huì)存在ht[1]中，而不會(huì)存放到ht[0]，ht[0]只會(huì)減少不會(huì)新增。

06總結(jié)

1)字典被Redis廣泛應(yīng)用于各種功能，比如數(shù)據(jù)庫和哈希鍵。

2)Redis字典底層是有哈希表實(shí)現(xiàn)，每個(gè)字典包含兩個(gè)哈希表ht[0]、ht[1]，ht[1]在rehash時(shí)才有作用。

3)哈希表使用鏈地址法解決哈希沖突，被分配到同一個(gè)索引的鍵值對會(huì)連接成一個(gè)單向鏈表。

4)哈希表進(jìn)行rehash不是一次性完成，而是分多次、漸進(jìn)式完成的。

5)哈希表rehash的條件：

擴(kuò)容：(滿足任一即可)

a)Redis服務(wù)器目前沒有在執(zhí)行BGSAVE或BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于1。

b)Redis服務(wù)器目前在執(zhí)行BGSAVE或BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于5。

縮容：哈希表的負(fù)載因子小于0.1。

6)BGSAVE或BGREWRITEAOF命令是否在執(zhí)行，Redis服務(wù)器哈希表執(zhí)行擴(kuò)容所需的負(fù)載因子不相同。因?yàn)榇藭r(shí)子進(jìn)程使用寫時(shí)復(fù)制copy on write，需要占用一定的內(nèi)存，所以需要提高擴(kuò)容所需的負(fù)載因子，從而盡可能避免在子進(jìn)程存在期間進(jìn)行擴(kuò)容，可以避免不必要的內(nèi)存寫入操作，最大限度節(jié)約內(nèi)存。

了解了Redis字典哈希表擴(kuò)容，那么你知道與Java ConcurrentHashMap(1.8)的擴(kuò)容有什么不同嗎?

也就是引出這個(gè)問題：

Redis的字典漸進(jìn)式擴(kuò)容與ConcurrentHashMap的擴(kuò)容策略比較?那么他們在擴(kuò)容、CRUD時(shí)有什么區(qū)別呢?

1)擴(kuò)容所花費(fèi)的時(shí)間對比

一個(gè)單線程漸進(jìn)擴(kuò)容，一個(gè)多線程協(xié)同擴(kuò)容。在平均的情況下，是ConcurrentHashMap快。這也意味著，擴(kuò)容時(shí)所需要

花費(fèi)的空間能夠更快的進(jìn)行釋放。

2)讀操作，兩者的性能相差不多。

3)寫操作，Redis的字典返回更快些，因?yàn)樗幌馛oncurrentHashMap那樣去幫著擴(kuò)容(當(dāng)要寫的桶位已經(jīng)搬到了newTable時(shí))，等擴(kuò)容完才能進(jìn)行操作，而redis則是直接將新加的元素添加到ht[1]。

4)刪除操作，與寫一樣。

最后，我們應(yīng)該選擇單線程漸進(jìn)式擴(kuò)容還是選擇多線程協(xié)同式擴(kuò)容?具體問題具體分析：

1)如果內(nèi)存資源吃緊，希望能夠進(jìn)行快速的擴(kuò)容方便釋放擴(kuò)容時(shí)需要的輔助空間，且那么選擇后者。

2)如果對于寫和刪除操作要求迅速，那么可以選擇前者。

參考資料：

#1《redis設(shè)計(jì)與實(shí)現(xiàn)》

#2 https://blog.csdn.net/jiji1995/article/details/64127460

#3 https://blog.csdn.net/u010710458/article/details/80604740

#4 源碼分析：https://www.jianshu.com/p/a57a6e389a03