Redis Hashes 數據類型簡述
Redis Hashes 是我們日常使用中比較高頻的 Redis 數據類型,內部使用 Redis 字典結構存儲,底層基於哈希表結構實現。
下面從哈希表節點,哈下表結構,Redis 字典,Redis 字典元素操作,Redis rehash 幾點來簡要概述。
一、Redis 哈希表節點
Redis 內部定義哈希表節點 dictEntry,用於存儲具體的數據,其主要包括鍵 key,值 v,及外向指針。
1、dictEntry 具體定義
typedef struct dictEntry { void *key; union{ void *val; uint64_t u64; int64_t s64; } v;
struct dictEntry *next; //下一個節點指針
} dictEntry;
key:鍵值對 key
v:鍵值對 value,可以是指向指針,或者具體的類型。
next:為指向下一個節點的指針,用於處理鍵哈希衝突問題。相同哈希值鍵的鍵值對會以鏈表的形式存在同一位置。
2、示例哈希表節點數據
如下,哈希表容量 size 為 4,掩碼 sizemask 為 3 ,內部存儲了兩個鍵值對(k1、v1)、(k2、v2),已使用容量 used 為 2:
二、Redis 哈希表結構
Redis 內部定義哈希表結構 dictht,用於存儲實際的(k、v)鍵值對,其主要包括哈希表數組,容量、已使用容量及掩碼。
1、dictht 具體定義
typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht
table:哈希表數組,為指向 dictEntry 類型數組的指針,存儲具體的鍵值對元素。
size:哈希表容量,規劃申請的容量
sizemask:哈希表大小掩碼,用於索引計算,計算方式為 size – 1
used:已使用容量,實際存儲的(k、v)鍵值對數
2、示例哈希表數據
如下,哈希表容量 size 為 4,掩碼 sizemask 為 3 ,內部存儲了一個鍵值對(k1、v1),已使用容量 used 為 1:
三、Redis 字典實現
Redis 字典基於上述的哈希表實現,其主要包括內部特定類型函數、私有數據、哈希表數組及 rehash 進度標識等數據。
1、dict:
typedef struct dict{ dictType *type; void *privdata; dictht ht[2]; int rehashidx; } dict
type:類型為dictType,保存了用於操作特定類型鍵的函數,和 privdata 共同服務於構建 Redis 多態字典。
privdate:和type協同使用,為需要傳遞給特定類型函數的可選參數。
ht:哈希表數組,類型為dictht,ht[0] 為實際存儲數據使用,ht[1] 為 rehash 時使用。
ehashidx:rehash 進度標誌,-1 代表當前不在 rehash 進程中。
2、Redis 字典示例數據
如下,包含兩個元素的 Redis 字典:
四、Redis 字典添加元素
向字 Redis 典中添加元素主要涉及以下幾步操作:
1、計算鍵值對鍵的哈希值
hash = dict->type->hashFunction(key)
上面第三節我們提到過 Redis 字典的屬性 type,應用其內部的哈希函數得到鍵哈希值。
2、計算需要放入的位置索引
index = hash & dict->ht[0].sizemask
使用上一步計算得到的哈希值與哈希表的 sizemask 屬性進行【與操作】得到需要放入的位置索引值
3、鍵衝突解決
沒有完美的哈希函數,哈希衝突無法避免,實際應用中,多個鍵往往會被索引到同一個位置時,這種現象,我們稱之為鍵衝突。
Redis 採用鏈地址法解決鍵衝突:也即將衝突的鍵值對組成一個鏈表放到同一個哈希位置上。
上面第二節我們介紹過 dictEntry 的結構,其中包含一個指向另一個節點的指針 next。
這裡需要說明的一點是:衝突節點插入時,是插入到鏈表的頭部,這樣只需要執行操作一次操作即可,也即時間複雜度為 O(1)。
如下圖:(k2,v2)與(k1,v1)發生衝突,直接將(k2,v2)插入到鏈表頭部:
五、Redis rehash
Redis rehash 是指 Redis 字典重新規劃哈希表空間佔用的過程。Redis 字典往往伴隨著元素的增刪改等操作,隨著元素的增多或減少,需要適時地進行 Redis 字典容量的重新規劃。
1、負載因子
哈希表使用負載因子(load_factor)來標識當前哈希表的使用狀態,計算公式為:已保存節點數量(dict.ht[0].used)/ 哈希表容量(dict.ht[0].size)。它需要保持在一個合理的範圍,以保障資源的最優利用。通常需要適時的對哈希表進行擴展或者收縮來對負載因子進行維護。
這裡涉及到一個問題,就是什麼時候需要進行伸縮維護?
a)擴展時機:
觸發 rehash 實際收到 當前 Redis 伺服器狀態影響,即有無後台 bgsave 及 bgrewriteaop 操作:
-
無操作,則觸發 load_factor 標準為 >= 1
-
當前有操作,則觸發 load_factor 標準為 >= 5
Redis 伺服器通過 fork 子進程形式執行 bgsave 及 bgrewriteaop 操作,此期間整個服務的資源耗費較大,為了避免可能發生的 rehash 帶來額外的資源壓力,伺服器往往會調高觸發執行 rehash 操作的負載因子界限,以降低觸發 rehash 的頻率。
b)收縮時機:
load_factor < 0.1
2、Redis rehash 基本過程
Redis rehash 過程主要包括空間分配、rehash 執行、重定向三個過程
a) 空間分配:
空間分配是指 為 dict.ht[1] 分配空間
所需要的空間大小計算如下:
擴展:最小n滿足2n >= dict.ht[0].used * 2
收縮:最小n滿足2n >= dict.ht[0].used
如下圖:ht[0].used = 3,假定無bg相關任務,則h[1]大小需要計算:2n >= 3 * 2 = 6
n = 3,ht[1].size = 23 = 8
b) rehash 執行
此過程會逐一對 dict.ht[0] 中的元素,依據dict.ht[1] 特性(sizemask)重新計算索引值,並放置到 dict.ht[1] 中。
如下圖:h[0] 中的元素以被完全 rehash 到 h[1] 中存儲:
c) 重定向
當所有元素遷移完畢後,Redis 會釋放調 dict.ht[0] 的空間佔用,並將 dict.ht[1] 設置為 dict.ht[0],並重新在 dict.ht[1] 上創建空的哈希表,以用於下次 rehash 使用。
如下圖:重新指向完畢,並創建了新的 ht[1]:
六、Redis rehash 並非一蹴而就
針對實際存儲中不同容量的字典數據,Redis 採用不同的措施進行 rehash 執行:對於數據量較小的字典可以直接一次性的執行rehash;而對於數據量較大的字典數據,直接一次性的執行 rehash 會導致服務資源的集中佔用,影響正常的服務響應。因此需要進行分而治之,採用漸進式執行過程。
漸進式 rehash 會用到上面第三節我們介紹的 dict 字典結構中的 rehashidx 屬性,用以標識當前 rehash 進度。
關於漸進式 rehash 過程中 rehashidx 操作如下:
-
首先將rehashidx置0,標示rehash開始
-
每次rehash一個元素,rehashidx值增加1
-
當最終所有元素rehash完成,將rehashidx置-1。
漸進式 rehash 進程中對正常的服務請求的處理如下:
1、刪除、查找、更新:
會涉及到兩個哈希表(ht[0]、ht[1])操作,如查找元素,首先嘗試在ht[0]上查找,找不到,則繼續在h[1]上查找。
2、添加
添加元素只會在h[1]上操作,h[0] 上元素此過程保持只減不增。