[[407448]]

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

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

Redis中使用哈希表作為底層實現的是叫做字典的數據結構，字典又稱為符號表、關聯數組或映射(map)。是一種保存鍵值對的抽象數據結構。

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

由于Redis是用C語言寫的，所以要搞懂C的相關實現原理去看源碼的話就要對C語言有一定的了解。

目錄

1、哈希表結構

哈希表例子

2、字典數據結構

字典例子

3、解決哈希沖突

4、擴容/縮容——rehash

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

4.2、看一次哈希表rehash擴容過程

5、漸進式rehash

5.1、漸進式rehash步驟

5.2、看下一次完整的漸進式rehash擴容的過程

6、總結

01哈希表結構

哈希表是由dictht結構體定義，table是一個數組，數組中每個元素是一個指向dictEntry結構的指針。

dictEntry是哈希表的節點，每個節點保存著一個鍵值對key、value，value可以是一個指針、或者是一個unit64_t或int64_t整數。

next屬性則是一個指向另一個哈希表節點的指針，形成一個鏈表，主要也是為了解決哈希沖突問題。

哈希表例子

一個空的哈希表

索引值相同的兩個節點使用鏈表連接起來

02字典數據結構

其實說到哈希表的話順便要了解下字典這種數據結構，畢竟它的底層就是哈希表來實現，可以了解下擴容縮容相關的。

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

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

ht[2]：兩個哈希表，字典使用的哈希表是ht[0]，ht[1]則是當對ht[0]哈希表進行rehash時使用。

trehashidx：記錄當前rehash進度，沒有進行rehash則為-1。

字典例子

普通狀態下的字典

03解決哈希沖突

將一個鍵值對添加到字典時，需要計算其哈希值和索引值，接著根據索引值將新節點放到哈希表數組的指定索引上。

計算哈希值：

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

計算索引值：

hash & dict->ht[x].sizemask 

鍵沖突：當兩個或以上數量的鍵進行哈希之后索引值一樣，也就是說兩個節點要放在同一個同桶里，這時可能就會存在覆蓋(沖突)，那么就得解決這種沖突了。

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

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

04擴容/縮容——rehash

首先，我們要清楚為什么要進行擴容或縮容?

擴容原因：當hashtable存儲的元素過多，可能由于碰撞也過多，導致其中某天鏈表很長，最后致使查找和插入時間復雜度很大。因此當元素超多一定的時候就需要擴容。

縮容原因：當元素數量比較少的時候就需要縮容以節約不必要的內存。

為了讓哈希表的負載因子(load factor)維持在一個合理的范圍內，會使用rehash(重新散列)操作對哈希表進行相應的擴展或收縮。

負載因子的計算公式：哈希表已保存節點數量 / 哈希表大小 load_factor = ht[0].used / ht[0].size

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

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

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

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

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

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

1)為ht[1]分配空間

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

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

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

3)當ht[0]的所有鍵值對都遷移到了ht[1]之后(ht[0]變為空表)，將ht[0]釋放，然后將ht[1]設置成ht[0]，最后為ht[1]分配一個空白哈希表：

4.2、看一次哈希表rehash擴容過程

1)開始rehash之前

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

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

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

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

rehash擴容完成

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

因為當執行BGSAVE或BGREWRITEAOF命令過程中，Redis需要創建服務器進程的子進程，操作系統采用的是COW，即寫時復制copy-on-write的技術來優化子進程的使用效率。所以在子進程存在時，服務器會提高執行擴容所需的負載因子，從而盡可能避免在子進程存在期間進行擴容，可以避免不必要的內存寫入操作，最大限度節約內存。

05漸進式rehash

為什么需要漸進式rehash呢?

在元素數量較少時，rehash會非常快的進行，但是當元素數量達到幾百、甚至幾個億時進行rehash將會是一個非常耗時的操作。如果一次性將成萬上億的元素的鍵值對rehash到ht[1]，龐大的計算量可能會導致服務器在一段時間內停止服務，這是非常危險的!所以，rehash這個動作不能一次性、集中式的完成，而是分多次、漸進式地完成。

5.1、漸進式rehash步驟：

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

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

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

4)隨著字典操作的不斷執行，最終在某個時間點上，ht[0]的所有鍵值對都會被rehash至ht[1]，這時程序將rehashidx屬性的值設為-1，表示rehash完成。

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

5.2、看下一次完整的漸進式rehash擴容的過程

1)準備進行漸進式rehash

準備rehash

2)此時rehashidx=0,也就是會將索引為0的鍵值對進行遷移

rehash索引0上的鍵值對

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

最后一次rehash，索引為3上的鍵值對進行遷移

4)漸進式rehash結束

rehash結束

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

在遷移的過程中，會不會造成讀少數據?

不會，因為在遷移時，首先會從ht[0]讀取數據，如果ht[0]讀不到，則會去ht[1]讀。

在遷移過程中，新增加的數據會存放在哪個ht?

遷移過程中，新增的數據只會存在ht[1]中，而不會存放到ht[0]，ht[0]只會減少不會新增。

06總結

1)字典被Redis廣泛應用于各種功能，比如數據庫和哈希鍵。

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

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

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

5)哈希表rehash的條件：

擴容：(滿足任一即可)

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

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

縮容：哈希表的負載因子小于0.1。

6)BGSAVE或BGREWRITEAOF命令是否在執行，Redis服務器哈希表執行擴容所需的負載因子不相同。因為此時子進程使用寫時復制copy on write，需要占用一定的內存，所以需要提高擴容所需的負載因子，從而盡可能避免在子進程存在期間進行擴容，可以避免不必要的內存寫入操作，最大限度節約內存。

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

也就是引出這個問題：

Redis的字典漸進式擴容與ConcurrentHashMap的擴容策略比較?那么他們在擴容、CRUD時有什么區別呢?

1)擴容所花費的時間對比

一個單線程漸進擴容，一個多線程協同擴容。在平均的情況下，是ConcurrentHashMap快。這也意味著，擴容時所需要

花費的空間能夠更快的進行釋放。

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

3)寫操作，Redis的字典返回更快些，因為它不像ConcurrentHashMap那樣去幫著擴容(當要寫的桶位已經搬到了newTable時)，等擴容完才能進行操作，而redis則是直接將新加的元素添加到ht[1]。

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

最后，我們應該選擇單線程漸進式擴容還是選擇多線程協同式擴容?具體問題具體分析：

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

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

參考資料：

#1《redis設計與實現》

#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