dict

字典(dict)是redis里最核心的數據結構,正如其全稱Remote Dictionary Service所說,redis其實就是一個字典服務,字典以key、value的形式呈現給用戶,key是簡單的字符串,而value可以是各種數據結構,好比字符串(string)、鏈表(list)、集合(set)、排序集合(zset)、哈希表(hash)等.

redis里dict的實現也比較簡單,通過鏈表來辦理哈希沖突,值得一提的是dict的動態擴展能力,當dict里元素不斷增加時,其會擴大哈希桶數,然后對現有元素進行rehash,重新分布到對應的桶上,但dict的rehash并不是一次性完成的,這樣會導致當dict里元素較多時,rehash耗時較長,導致服務阻塞.

typedef struct dict {

dict創建時,會初始化ht[0],插入和拜訪都通過ht[0]來完成,當需要rehash時,創建一個新的dict ht[1],并以桶為單位將ht[0]里的元素逐步遷移到新的ht[1]上(遷移會在拜訪dict時觸發,也可以配置redis主動在后臺周期性的遷移).所以當拜訪dict時,如果正在進行rehash,就必須先后查詢ht[0], ht[1],因為被拜訪的元素可能已經遷到新的ht[1]上；當所有的元素都遷移到ht[1]后,用ht[1]代替ht[0],并釋放掉原來的ht[0].

dict是通用的數據結構,采用void*來存儲任意類型的對象,由于需求多變,比如有的場景需要在插入元素時重新分配內存,而有的場景直接存儲指針,有的場景需要定制對象比較的方式,redis為辦理這個問題,定義了一系列的接口,用戶可以根據需求在創建dict時指定.

typedef struct dictType {

string

redis所有的key都是string類型,redis的是基于c string的一個封裝,在字符串的頭部存儲了長度信息(strlen的復雜度為O(1)),而且支持動態擴展等特性.

struct sdshdr {

redis的sds類型其實就是char*,redis創建一個string時,返回的是buf的指針,通過這個指針,就可以計算出sdshdr的位置,來拜訪到len、free等字段.

list

redis的list實現是一個雙向鏈表,與dict類似,list也可以定制對象對比、析構等辦法；list在頭結點會存儲鏈表的長度,使得獲取list長度的復雜度為O(1)；頭結點還存儲了list頭部、尾部節點的指針,使得可以從兩個方向遍歷list.

typedef struct listNode {

ziplist

雙向鏈表的的最大問題在于頭尾指針的開銷,64bit OS上,每個節點有16bytes的額外開銷,為了節省內存,當list里的元素較少而且大小較小時,redis采用ziplist的格式來實現鏈表.

ziplist實際上是二進制的形式組織鏈表,"二進制數據"的存儲鏈表頭部,記錄總長度,頭尾的位置等信息,然后每個節點除了存儲節點內容外,還記錄自身的長度,以及上一個節點的長度,這樣通過遍歷"二進制數據"就能拜訪到ziplist里所有的元素.另外,ziplist節點的長度、以及上一個節點的長度通過變長整數編碼,進一步節省內存.

set

set代表一個集合(元素不重復),集合在redis里實現為字典(字典的value為NULL)；如果set里所有的元素都是整數時,redis會以intset的形式存儲,intset是一個排序的整形數組,為節省內存,當intset里元素值在[INT16_MIN, INT16_MAX]之間時,每個數組元素占2個字節；當inset里元素值都在[INT32_MIN, INT32_MAX]之間時,每個數組元素占4個字節；否則每個元素占8個字節.

zset

zset是排序集合,與set不同的時,zset里每個元素有一個score(double類型),作為排序的尺度；redis里zset默認通過一個dict和一個ziplist來實現,dict用于維護set元素到score的映射關系,所有的元素都追加到一個skiplist來保證其排序.當zset里元素較少并且大小較小時,zset也可以ziplist的形式存儲,zset的元素以及對應的score會作為ziplist的兩個連續節點存儲.

hash

redis的hash是維護filed==>value的映射表,hash的默認實現也是dict,以通過field快速找到value；當hahs里元素較少而且大小較小時,hash也以ziplist的形式存儲以節省內存.