32
Redis數據結構
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 {
dictType *type;
void *privdata;
dictht ht[2];
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} 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 {
unsigned int (*hashFunction)(const void *key); // key的hash方法
void *(*keyDup)(void *privdata, const void *key); // 插入元素時，複製key對象的方法
void *(*valDup)(void *privdata, const void *obj); // 插入元素時，複製value對象的方法
int (*keyCompare)(void *privdata, const void *key1, const void *key2); // key比較的方法
void (*keyDestructor)(void *privdata, void *key); // 刪除元素時，釋放key的方法
void (*valDestructor)(void *privdata, void *obj); // 刪除元素時，釋放value的方法
} dictType;
string
redis所有的key都是string類型，redis的是基於c string的一個封裝，在字符串的頭部存儲了長度信息（strlen的複雜度為O(1)）,並且支持動態擴展等特性。
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};
typedef char *sds;
redis的sds類型其實就是char*，redis創建一個string時，返回的是buf的指針，通過這個指針，就可以計算出sdshdr的位置，來訪問到len、free等字段。
list
redis的list實現是一個雙向鏈表，與dict類似，list也可以定製對象對比、析構等方法；list在頭結點會存儲鏈表的長度，使得獲取list長度的複雜度為O(1)；頭結點還存儲了list頭部、尾部節點的指針，使得可以從兩個方向遍曆list。
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr); // 複製鏈表節點value的方法
void (*free)(void *ptr); // 釋放鏈表節點value的方法
int (*match)(void *ptr, void *key); // 鏈表節點對比方法
unsigned long len;
} list;
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的形式存儲以節省內存。
最後更新：2017-04-01 13:37:09