2023-06-17：說一說redis中漸進式rehash？

答案2023-06-17：

在Redis中，如果哈希表的數(shù)組一直保持不變，就會增加哈希沖突的可能性，從而降低檢索效率。為了解決這個問題，Redis會對數(shù)組進行擴容，通常是將數(shù)組大小擴大為原來的兩倍。然而，這個擴容過程會引起元素在哈希桶中的分散，導致元素的移動。由于元素移動會涉及IO操作，所以這個重新哈希（ReHash）過程可能會導致許多請求被阻塞。

漸進式rehash

為了避免這個問題，Redis 采用了漸進式 rehash。

在Redis中，默認使用兩個全局哈希表：哈希表1和哈希表2。最初，當你開始插入數(shù)據(jù)時，只使用哈希表1，而哈希表2沒有分配空間。隨著數(shù)據(jù)逐漸增多，Redis開始執(zhí)行漸進式rehash的過程。

1、為哈希表2分配更大的空間，例如是當前哈希表1大小的兩倍。

2、將哈希表1中的數(shù)據(jù)重新映射并拷貝到哈希表2中，確保每個元素都被正確地存儲在新的哈希桶位置上。

3、釋放哈希表1的空間，將其回收以便于系統(tǒng)的正常運行。

在上述的第二步中，涉及到大量的數(shù)據(jù)遷移和拷貝操作。如果一次性將哈希表1中的所有數(shù)據(jù)都遷移到哈希表2，將導致Redis線程被阻塞，無法提供對其他請求的服務。這將導致Redis無法快速地訪問數(shù)據(jù)。

在Redis開始執(zhí)行rehash時，Redis仍然可以正常處理客戶端請求。然而，在處理每個請求時，Redis還會額外執(zhí)行以下操作：

• ??處理第一個請求時，將哈希表1中第一個索引位置上的所有條目拷貝到哈希表2中。

• ??處理第二個請求時，將哈希表1中第二個索引位置上的所有條目拷貝到哈希表2中。

• ??如此循環(huán)，直到將所有索引位置上的數(shù)據(jù)都成功拷貝到哈希表2中。

通過將大量數(shù)據(jù)拷貝的操作分攤到處理請求的過程中，Redis巧妙地避免了一次性的大量數(shù)據(jù)拷貝開銷，從而保證了數(shù)據(jù)的快速訪問。這種處理方式確保了根據(jù)鍵尋找值的操作大致在O(1)的時間復雜度范圍內進行。通過漸進式rehash和分步式數(shù)據(jù)遷移，Redis能夠在維持性能的同時，實現(xiàn)平滑的哈希表擴容和數(shù)據(jù)遷移。