Redis rehash

隨著操作的不斷執(zhí)行， 哈希表保存的鍵值對會逐漸地增多或者減少， 為了讓哈希表的負(fù)載因子（load factor）維持在一個(gè)合理的范圍之內(nèi)， 當(dāng)哈希表保存的鍵值對數(shù)量太多或者太少時(shí)， 程序需要對哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮。

擴(kuò)展和收縮哈希表的工作可以通過執(zhí)行 rehash （重新散列）操作來完成， Redis 對字典的哈希表執(zhí)行 rehash 的步驟如下：

1. 為字典的 ht[1] 哈希表分配空間， 這個(gè)哈希表的空間大小取決于要執(zhí)行的操作， 以及 ht[0] 當(dāng)前包含的鍵值對數(shù)量 （也即是ht[0].used 屬性的值）：
   • 如果執(zhí)行的是擴(kuò)展操作， 那么 ht[1] 的大小為第一個(gè)大于等于 ht[0].used * 2 的  （2 的 n 次方冪）；
   • 如果執(zhí)行的是收縮操作， 那么 ht[1] 的大小為第一個(gè)大于等于 ht[0].used 的  。
2. 將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面： rehash 指的是重新計(jì)算鍵的哈希值和索引值， 然后將鍵值對放置到 ht[1] 哈希表的指定位置上。
3. 當(dāng) ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后 （ht[0] 變?yōu)榭毡恚?釋放 ht[0] ， 將 ht[1] 設(shè)置為 ht[0] ， 并在 ht[1] 新創(chuàng)建一個(gè)空白哈希表， 為下一次 rehash 做準(zhǔn)備。

舉個(gè)例子， 假設(shè)程序要對圖 4-8 所示字典的 ht[0] 進(jìn)行擴(kuò)展操作， 那么程序?qū)?zhí)行以下步驟：

1. ht[0].used 當(dāng)前的值為 4 ， 4 * 2 = 8 ， 而 8 （）恰好是第一個(gè)大于等于 4 的 2 的 n 次方， 所以程序會將 ht[1] 哈希表的大小設(shè)置為 8 。 圖 4-9 展示了 ht[1] 在分配空間之后， 字典的樣子。
2. 將 ht[0] 包含的四個(gè)鍵值對都 rehash 到 ht[1] ， 如圖 4-10 所示。
3. 釋放 ht[0] ，并將 ht[1] 設(shè)置為 ht[0] ，然后為 ht[1] 分配一個(gè)空白哈希表，如圖 4-11 所示。

至此， 對哈希表的擴(kuò)展操作執(zhí)行完畢， 程序成功將哈希表的大小從原來的 4 改為了現(xiàn)在的 8 。

哈希表的擴(kuò)展與收縮

當(dāng)以下條件中的任意一個(gè)被滿足時(shí)， 程序會自動(dòng)開始對哈希表執(zhí)行擴(kuò)展操作：

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

其中哈希表的負(fù)載因子可以通過公式：

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

計(jì)算得出。

比如說， 對于一個(gè)大小為 4 ， 包含 4 個(gè)鍵值對的哈希表來說， 這個(gè)哈希表的負(fù)載因子為：

load_factor = 4 / 4 = 1

又比如說， 對于一個(gè)大小為 512 ， 包含 256 個(gè)鍵值對的哈希表來說， 這個(gè)哈希表的負(fù)載因子為：

load_factor = 256 / 512 = 0.5

根據(jù) BGSAVE 命令或 BGREWRITEAOF 命令是否正在執(zhí)行， 服務(wù)器執(zhí)行擴(kuò)展操作所需的負(fù)載因子并不相同， 這是因?yàn)樵趫?zhí)行 BGSAVE 命令或BGREWRITEAOF 命令的過程中， Redis 需要?jiǎng)?chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程， 而大多數(shù)操作系統(tǒng)都采用寫時(shí)復(fù)制（copy-on-write）技術(shù)來優(yōu)化子進(jìn)程的使用效率， 所以在子進(jìn)程存在期間， 服務(wù)器會提高執(zhí)行擴(kuò)展操作所需的負(fù)載因子， 從而盡可能地避免在子進(jìn)程存在期間進(jìn)行哈希表擴(kuò)展操作， 這可以避免不必要的內(nèi)存寫入操作， 最大限度地節(jié)約內(nèi)存。

另一方面， 當(dāng)哈希表的負(fù)載因子小于 0.1 時(shí)， 程序自動(dòng)開始對哈希表執(zhí)行收縮操作。