Redis 漸進(jìn)式 rehash

上一節(jié)說過， 擴(kuò)展或收縮哈希表需要將 ht[0] 里面的所有鍵值對(duì) rehash 到 ht[1] 里面， 但是， 這個(gè) rehash 動(dòng)作并不是一次性、集中式地完成的， 而是分多次、漸進(jìn)式地完成的。

這樣做的原因在于， 如果 ht[0] 里只保存著四個(gè)鍵值對(duì)， 那么服務(wù)器可以在瞬間就將這些鍵值對(duì)全部 rehash 到 ht[1] ； 但是， 如果哈希表里保存的鍵值對(duì)數(shù)量不是四個(gè)， 而是四百萬、四千萬甚至四億個(gè)鍵值對(duì)， 那么要一次性將這些鍵值對(duì)全部 rehash 到 ht[1] 的話， 龐大的計(jì)算量可能會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)。

因此， 為了避免 rehash 對(duì)服務(wù)器性能造成影響， 服務(wù)器不是一次性將 ht[0] 里面的所有鍵值對(duì)全部 rehash 到 ht[1] ， 而是分多次、漸進(jìn)式地將 ht[0] 里面的鍵值對(duì)慢慢地 rehash 到 ht[1] 。

以下是哈希表漸進(jìn)式 rehash 的詳細(xì)步驟：

1. 為 ht[1] 分配空間， 讓字典同時(shí)持有 ht[0] 和 ht[1] 兩個(gè)哈希表。
2. 在字典中維持一個(gè)索引計(jì)數(shù)器變量 rehashidx ， 并將它的值設(shè)置為 0 ， 表示 rehash 工作正式開始。
3. 在 rehash 進(jìn)行期間， 每次對(duì)字典執(zhí)行添加、刪除、查找或者更新操作時(shí)， 程序除了執(zhí)行指定的操作以外， 還會(huì)順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對(duì) rehash 到 ht[1] ， 當(dāng) rehash 工作完成之后， 程序?qū)?nbsp;rehashidx 屬性的值增一。
4. 隨著字典操作的不斷執(zhí)行， 最終在某個(gè)時(shí)間點(diǎn)上， ht[0] 的所有鍵值對(duì)都會(huì)被 rehash 至 ht[1] ， 這時(shí)程序?qū)?nbsp;rehashidx 屬性的值設(shè)為 -1 ， 表示 rehash 操作已完成。

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

圖 4-12 至圖 4-17 展示了一次完整的漸進(jìn)式 rehash 過程， 注意觀察在整個(gè) rehash 過程中， 字典的 rehashidx 屬性是如何變化的。

漸進(jìn)式 rehash 執(zhí)行期間的哈希表操作

因?yàn)樵谶M(jìn)行漸進(jìn)式 rehash 的過程中， 字典會(huì)同時(shí)使用 ht[0] 和 ht[1] 兩個(gè)哈希表， 所以在漸進(jìn)式 rehash 進(jìn)行期間， 字典的刪除（delete）、查找（find）、更新（update）等操作會(huì)在兩個(gè)哈希表上進(jìn)行： 比如說， 要在字典里面查找一個(gè)鍵的話， 程序會(huì)先在 ht[0] 里面進(jìn)行查找， 如果沒找到的話， 就會(huì)繼續(xù)到 ht[1] 里面進(jìn)行查找， 諸如此類。

另外， 在漸進(jìn)式 rehash 執(zhí)行期間， 新添加到字典的鍵值對(duì)一律會(huì)被保存到 ht[1] 里面， 而 ht[0] 則不再進(jìn)行任何添加操作： 這一措施保證了 ht[0] 包含的鍵值對(duì)數(shù)量會(huì)只減不增， 并隨著 rehash 操作的執(zhí)行而最終變成空表。