概覽

redis 本質是 K-V 鍵值對數據庫，底層通過字典 dict 存儲鍵值映射關系，除此之外，dict 還作為 Redis hash 結構底層的實現之一。

討論 Redis 的數據結構，可以從兩個層面出發。

第一個層面從使用者角度出發，即 Redis 暴露給外部調用的 Api：

•string

•list

•hash

•set

•sorted set

第二個層面是 Redis 的內部實現角度出發，是更為底層的數據結構實現：

•dict

•sds

•ziplist

•quicklist

•skiplist

Redis 這么做的目的還是基于高性能的考慮，在不同的場景下使用不同的底層數據結構實現，最大程度提升內存操作的效率。

例如當 sorted set，hash 存儲的數據規模較小時，底層都是通過 ziplist 實現，而當數據規模達到一定量時，sorted set 會轉換成 dict + skiplist 的底層實現，hash 會轉換成 dict 的底層實現。

本文主要討論是 Redis 關于 dict 這一底層數據結構的實現原理。

實現

dict 的實現與 JAVA jdk 中 hashmap 的實現有許多相似之處：

•關于哈希映射，key 的索引計算公式為 hash & (n - 1)，其中 hash 為 key 對應的 hash 值（Redis 通過 MurmurHash 算法計算得出），n 為哈希數組的大小•關于哈希沖突，Redis 同樣也是采用鏈地址法解決沖突

dict 在擴縮容的情況下，采用的是漸進式的 rehash 方式，這是它的特殊之處，下文會主要講到。

dict 的數據結構如下：

•type屬性是一個指向dictType結構的指針，每個dictType結構保存了一簇用于操作特定類型鍵值對的函數，Redis會為用途不同的字典設置不同的類型特定函數

•privdata屬性則保存了需要傳給那些類型特定函數的可選參數

•ht[2] 數組中存放了兩張哈希表，只有在 rehash 的過程中，ht[0] ht[1] 才都有效；正常情況下只有 ht[0] 有效，ht[1] 中沒有任何數據

•rehashidx 用來表示 rehash 過程到了哪一個索引位置，正常情況下 rehashidx = -1，表示當前沒有進行 rehash

dictht 的數據結構如下：

•dictEntry 數組，用來存放鍵值對

•size 表示當前 dictEntry 數組的大小

•sizemask，值為 size - 1，在計算 key 的索引位置時用到， index = hash & sizemask

•used 記錄現有 dict 的數據個數

正常情況下，dict 整體的數據結構如下圖所示：

rehash

隨著操作不斷執行，哈希表中的鍵值對會逐漸增加或減少，為了讓哈希表的負載因子（負載因子 = 已保存節點數量/哈希表大?。┚S持在一個合理的范圍內，當哈希表中節點數量過多或者過少時，Redis 會對哈希表進行相應的擴容或縮容，這一過程稱為 rehash。

在 rehash 操作開始前，首先要為哈希表 ht[1] 分配內存，ht[1] 之前一直是空閑狀態，終于要派上用場了，具體內存分配策略如下：

•如果是擴容操作，ht[1]的大小為第一個大于等于ht[0].used*2的2^n（2的n次方冪），舉個例子 ht[0].used = 5，觸發了擴容操作，即 ht[1].size = 5 * 2 = 10，但 10 不符合 2^n 要求，則繼續往下找到第一個符合要求的數 16，即 ht[1].size = 16

•如果是縮容操作，ht[1]的大小為第一個大于等于ht[0].used的2^n（2的n次方冪），舉個例子 ht[0].used = 5，觸發了縮容操作，則 ht[1].size = 8

ht[1] 分配完內存之后，接著進行如下操作：

•將 ht[0] 的中的節點重新計算哈希值和索引值，映射到 ht[1] 上

•當ht[0]包含的所有鍵值對都遷移到了ht[1]之后（ht[0]變為空表），釋放ht[0]，將ht[1]設置為ht[0]，并在ht[1]新創建一個空白哈希表，為下一次rehash做準備

哈希表觸發擴容的時機如下：

•服務器目前沒有在執行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負載因子大于等于1

•服務器目前正在執行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負載因子大于等于5，這么做的原因是避免在子進程存在期間進行哈希表擴容操作，從而避免不必要的內存寫入操作，最大限度節省內存

負載因子的計算公式：