[TOC] ### **為什么會產生rehash？** ***** 隨著操作的不斷執行，哈希表保存的鍵值對會逐漸地增多或者減少，為了讓哈希表的負載因子（load factor）維持在一個合理的范圍之內，當哈希表保存的鍵值對數量太多或者太少時，程序需要對哈希表的大小進行相應的擴展或者收縮。 ### **觸發rehash** ***** #### **觸發自動擴展** * 服務器目前沒有在執行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負載因子大于等于1。 * 服務器目前正在執行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負載因子大于等于5。 #### **觸發自動收縮** * 當哈希表的**負載因子小于 0.1**時， 程序自動開始對哈希表執行收縮操作 #### **觸發擴展負載因子不同原因** ***** 根據BGSAVE命令或BGREWRITEAOF命令是否正在執行，服務器執行擴展操作所需的負載因子并不相同，這是因為在執行BGSAVE命令或BGREWRITEAOF命令的過程中，Redis需要創建當前服務器進程的子進程，而大多數操作系統都采用寫時復制（copy-on-write）技術來優化子進程的使用效率，所以在子進程存在期間，服務器會提高執行擴展操作所需的負載因子，從而盡可能地避免在子進程存在期間進行哈希表擴展操作，這可以避免不必要的內存寫入操作，最大限度地節約內存。 ``` 知識點： #負載因子=哈希表已保存節點數量/哈希表大小 load_factor?=?ht[0].used?/?ht[0].size ``` ### **rehash過程** ***** #### **rehash基本過程原理** * 為字典的ht[1]哈希表分配空間，這個哈希表的空間大小取決于要執行的操作，以及ht[0]當前包含的鍵值對數量（也即是ht[0].used屬性的值） * 將保存在ht[0]中的所有鍵值對rehash到ht[1]上面：rehash指的是重新計算鍵的哈希值和索引值，然后將鍵值對放置到ht[1]哈希表的指定位置上。 * 當ht[0]包含的所有鍵值對都遷移到了ht[1]之后（ht[0]變為空表），釋放ht[0]，將ht[1]設置為ht[0]，并在ht[1]新創建一個空白哈希表，為下一次rehash做準備。 ``` 知識點： 如果執行的是擴展操作，那么ht[1]的大小為第一個大于等于ht[0].used*2的2^n（2的n次方冪）； 如果執行的是收縮操作，那么ht[1]的大小為第一個大于等于ht[0].used的2^n。 ``` #### **rehash的一個例子** **執行rehash之前的字典**  ht[0].used 當前的值為 4 ， 4 * 2 = 8 ， 而 8 （2^3）恰好是第一個大于等于 4 的 2 的 n 次方， 所以程序會將 ht[1] 哈希表的大小設置為 8 。 **h1字典分配空間后**  **將ht[0]包含的四個鍵值對都rehash到ht[1]**  釋放ht[0]，并將ht[1]設置為ht[0]，然后為ht[1]分配一個空白哈希表 **完成rehash之后的狀態**  ### **漸進式rehash** ***** #### **為什么是漸進式的rehash** 如果哈希表里保存的鍵值對數量`比較大`，那么要一次性將這些鍵值對全部rehash到ht[1]的話，龐大的計算量可能會**導致服務器在一段時間內停止服務**。 #### **漸進式 rehash的過程** * 為 ht[1] 分配空間， 讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表。 在字典中維持一個索引計數器變量 rehashidx ， 并將它的值設置為 0 ， 表示 rehash 工作正式開始。 * 在 rehash 進行期間， 每次對字典執行添加、刪除、查找或者更新操作時， 程序除了執行指定的操作以外， 還會順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ， 當 rehash 工作完成之后， 程序將 rehashidx 屬性的值增一。 * 隨著字典操作的不斷執行， 最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] ， 這時程序將 rehashidx 屬性的值設為 -1 ， 表示 rehash 操作已完成。 #### **漸進式rehash的例子** **注意在整個 rehash 過程中， 字典的 rehashidx 屬性是如何變化的。** **準備開始rehash：**  **rehash索引0上的鍵值對：**  **rehash索引1上的鍵值對：**  **rehash索引2上的鍵值對：**  **rehash索引3上的鍵值對：**  **rehash執行完畢**  #### **知識點** 1. 漸進式rehash的好處在于它采取分而治之的方式，將rehash鍵值對所需的計算工作均攤到對字典的每個添加、刪除、查找和更新操作上，從而避免了集中式rehash而帶來的龐大計算量。 2. 在漸進式 rehash 進行期間， 字典的刪除（delete）、查找（find）、更新（update）等 操作會在兩個哈希表上進行 , 比如說， 要在字典里面查找一個鍵的話， 程序會先在 ht[0] 里面進行查找， 如果沒找到的話， 就會繼續到 ht[1] 里面進行查找. 3. 在漸進式 rehash 執行期間， 新添加到字典的鍵值對一律會被保存到 ht[1] 里面， 而 ht[0] 則不再進行任何添加操作： 這一措施保證了 ht[0] 包含的鍵值對數量會 只減不增， 并隨著 rehash 操作的執行而最終變成空表。 #### **漸進式rehash執行期間的哈希表操作** 因為在進行漸進式rehash的過程中，字典會同時使用ht[0]和ht[1]兩個哈希表，所以在漸進式rehash進行期間，字典的刪除（delete）、查找（find）、更新（update）等操作會在兩個哈希表上進行。例如，要在字典里面查找一個鍵的話，程序會先在ht[0]里面進行查找，如果沒找到的話，就會繼續到ht[1]里面進行查找，諸如此類。 另外，在漸進式rehash執行期間，新添加到字典的鍵值對一律會被保存到ht[1]里面，而ht[0]則不再進行任何添加操作，這一措施保證了ht[0]包含的鍵值對數量會只減不增，并隨著rehash操作的執行而最終變成空表。