Redis資料結構

字典（dict）是redis裡最核心的資料結構，正如其全稱Remote Dictionary Service所說，redis其實就是一個字典服務，字典以key、value的形式呈現給使用者，key是簡單的字元串，而value可以是各種資料結構，比如字元串（string）、連結清單（list）、集合（set）、排序集合（zset）、哈希表（hash）等。

redis裡dict的實作也比較簡單，通過連結清單來解決哈希沖突，值得一提的是dict的動态擴充能力，當dict裡元素不斷增加時，其會擴大哈希桶數，然後對現有元素進行rehash，重新分布到對應的桶上，但dict的rehash并不是一次性完成的，這樣會導緻當dict裡元素較多時，rehash耗時較長，導緻服務阻塞。

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時指定。

redis所有的key都是string類型，redis的是基于c string的一個封裝，在字元串的頭部存儲了長度資訊（strlen的複雜度為O(1)）,并且支援動态擴充等特性。

redis的sds類型其實就是char*，redis建立一個string時，傳回的是buf的指針，通過這個指針，就可以計算出sdshdr的位置，來通路到len、free等字段。

redis的list實作是一個雙向連結清單，與dict類似，list也可以定制對象對比、析構等方法；list在頭結點會存儲連結清單的長度，使得擷取list長度的複雜度為O(1)；頭結點還存儲了list頭部、尾部節點的指針，使得可以從兩個方向周遊list。

雙向連結清單的的最大問題在于頭尾指針的開銷，64bit OS上，每個節點有16bytes的額外開銷，為了節省記憶體，當list裡的元素較少并且大小較小時，redis采用ziplist的格式來實作連結清單。

ziplist實際上是二進制的形式組織連結清單，"二進制資料"的存儲連結清單頭部，記錄總長度，頭尾的位置等資訊，然後每個節點除了存儲節點内容外，還記錄自身的長度，以及上一個節點的長度，這樣通過周遊"二進制資料"就能通路到ziplist裡所有的元素。另外，ziplist節點的長度、以及上一個節點的長度通過變長整數編碼，進一步節省記憶體。

set代表一個集合（元素不重複），集合在redis裡實作為字典（字典的value為NULL）；如果set裡所有的元素都是整數時，redis會以intset的形式存儲，intset是一個排序的整形數組，為節省記憶體，當intset裡元素值在[INT16_MIN, INT16_MAX]之間時，每個數組元素占2個位元組；當inset裡元素值都在[INT32_MIN, INT32_MAX]之間時，每個數組元素占4個位元組；否則每個元素占8個位元組。

zset是排序集合，與set不同的時，zset裡每個元素有一個score（double類型），作為排序的标準；redis裡zset預設通過一個dict和一個ziplist來實作，dict用于維護set元素到score的映射關系，所有的元素都追加到一個skiplist來保證其排序。當zset裡元素較少并且大小較小時，zset也可以ziplist的形式存儲，zset的元素以及對應的score會作為ziplist的兩個連續節點存儲。

redis的hash是維護filed==>value的映射表，hash的預設實作也是dict，以通過field快速找到value；當hahs裡元素較少并且大小較小時，hash也以ziplist的形式存儲以節省記憶體。