本文分享自天翼雲開發者社區《redis漸進式rehash》，作者:l****n Redis是k-v型資料庫，其內部設計了一種dict類型的數據結構用來存儲鍵值結構。 dict 通常的存儲結構是 Key-Value 形式的，通過 Hash 函數對 key 求 Hash 值來確定 Value 的位置，因 ...
本文分享自天翼雲開發者社區《redis漸進式rehash》，作者:l****n
Redis是k-v型資料庫，其內部設計了一種dict類型的數據結構用來存儲鍵值結構。
dict 通常的存儲結構是 Key-Value 形式的，通過 Hash 函數對 key 求 Hash 值來確定 Value 的位置，因此也叫 Hash 表，是一種用來解決演算法中查找問題的數據結構，預設的演算法複雜度接近 O(1)。
使用哈希表總是會遇到哈希碰撞問題，dict使用拉鏈法將發生碰撞的元素組成鏈表，掛在發生碰撞的桶下，但是隨著存儲元素的不斷增加，碰撞發生的幾率也不斷增大，一個桶下鏈接的鏈表長度越來越長，定位一個key的時間複雜度就無法保證了，redis作為記憶體資料庫，本身追求的是更高的處理性能，線性增加的耗時無疑是不能接受的，為了減少hash碰撞，需要創建一個更長的hash表，讓元素能夠均勻的分佈在hash表上。
所以，Dict內部定義了兩個hashtable，分別是dictht[0]和dictht[1]，元素數量不多時，dict只在dictht[0]上存儲元素，dictht[1]不分配空間。當dictht[0]的元素個數達到一定數量，會觸發擴容過程，讓dictht[1]指向一個2倍長度的空間，然後進行rehash， 將dictht[0]上的元素重新映射到dictht[1]上。
如果dictht[0]上有很多元素，進行rehash無疑是一個很耗時的過程，加上redis是單線程，如果想一次完成rehash，就會很長時間的阻塞業務，所以redis選擇漸進式rehash。每次dictht[0]收到一個請求，只會將一個索引上的鏈表進行重新映射。
在將數據拷貝至dictht[1]時，dictht[0]仍然對客戶端提供服務。Rehash期間，如果有新的插入元素請求時，直接將元素插入到dictht[1]中，有客戶端查詢請求到來, 按照dictht[0]->dictht[1]的順序依次進行查詢。
