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 = 2= 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] 上元素此過程保持只減不增。