redis 5.0.7 源碼閱讀——字典dict

redis中字典相關的文件為：dict.h與dict.c 與其說是一個字典，道不如說是一個哈希表。一、數據結構 dictEntry 1 typedef struct dictEntry { 2 void *key; 3 union { 4 void *val; 5 uint64_t u64; 6 ...

redis中字典相關的文件為：dict.h與dict.c

與其說是一個字典，道不如說是一個哈希表。

一、數據結構

dictEntry

 1 typedef struct dictEntry {
 2     void *key;
 3     union {
 4         void *val;
 5         uint64_t u64;
 6         int64_t s64;
 7         double d;
 8     } v;
 9     struct dictEntry *next;
10 } dictEntry;

dictEntry是一個kv對的單向鏈表，其中v是一個聯合體，支持數字，或者是指向一塊記憶體的指針。

 1 /*
 2 +---------------+
 3 |void *key      |
 4 +---------------+
 5 |union{...} v   |
 6 +---------------+
 7 |dictEntry *next|---+
 8 +---------------+   |
 9                     |
10 +---------------+ <-+
11 |void *key      |
12 +---------------+
13 |union{...} v   |
14 +---------------+
15 |dictEntry *next|
16 +---------------+
17 */

為了節約篇幅，後續用以下結構表示：

1 /*
2 +---+  +---+
3 |K|V|->|K|V|->NULL
4 +---+  +---+
5 */

dictht

 1 typedef struct dictht {
 2     dictEntry **table;
 3     unsigned long size;
 4     /*
 5         這樣寫可能更容易理解
 6         const unsigned long size = 4;
 7         dictEntry *table[size];
 8     */
 9     
10 
11     unsigned long sizemask;
12     //sizemask，始終為size-1
13 
14     unsigned long used;
15     //當前總dictEntry數量
16 } dictht;

dictht是一個hash table，整體結構大致為：

 1 /*
 2 +----------------------+   +---> +-----------------+  +---+
 3 |dictEntry **table     |---+     |dictEntry *bucket|->|K|V|->NULL
 4 +----------------------+         +-----------------+  +---+
 5 |unsigned long size = 4|         |dictEntry *bucket|->NULL
 6 +----------------------+         +-----------------+
 7 |unsigned long sizemask|         |dictEntry *bucket|->NULL
 8 +----------------------+         +-----------------+
 9 |unsigned long used    |         |dictEntry *bucket|->NULL
10 +----------------------+         +-----------------+ 
11 */

其中，table指向大小為sizeof(dictEntry*) * size的一片記憶體空間，每個dictEntry*可以視為一個bucket，每個bucket下掛著一個dictEntry單向鏈表。

size的值始終為2的位數，而sizemask的值始終為size-1，其作用是決定kv對要掛在哪個bucket上。

舉個例子，size=4時，sizemask=3，其二進位為 0011，若通過hash函數計算出來key對應的hash值hash_value為5，二進位為0101，則通過位運算 sizemask & hash_value = 0011 & 0101 = 0001，十進位為1，則將會掛在idx = 1的bucket上。

dictType

1 typedef struct dictType {
2     uint64_t (*hashFunction)(const void *key);
3     void *(*keyDup)(void *privdata, const void *key);
4     void *(*valDup)(void *privdata, const void *obj);
5     int (*keyCompare)(void *privdata, const void *key1, const void *key2);
6     void (*keyDestructor)(void *privdata, void *key);
7     void (*valDestructor)(void *privdata, void *obj);
8 } dictType;

dictType用於自定義一些操作的方法，如拷貝key、拷貝value、銷毀key、銷毀value，比較key，以及hash函數。

dict

1 typedef struct dict {
2     dictType *type;
3     void *privdata;
4     dictht ht[2];
5     long rehashidx; /* rehashing not in progress if rehashidx == -1 */
6     unsigned long iterators; /* number of iterators currently running */
7 } dict;

之前提到的dictType與dictht都是dict的成員變數。除此之外，還有privdata，是在創建dict的時候調用者傳入，用於特定操作時回傳給函數的。如：

 1 #define dictFreeVal(d, entry) \
 2     if ((d)->type->valDestructor) \
 3         (d)->type->valDestructor((d)->privdata, (entry)->v.val)
 4 
 5 #define dictSetVal(d, entry, _val_) do { \
 6     if ((d)->type->valDup) \
 7         (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
 8     else \
 9         (entry)->v.val = (_val_); \
10 } while(0)
11 
12 #define dictSetSignedIntegerVal(entry, _val_) \
13     do { (entry)->v.s64 = _val_; } while(0)
14 
15 #define dictSetUnsignedIntegerVal(entry, _val_) \
16     do { (entry)->v.u64 = _val_; } while(0)
17 
18 #define dictSetDoubleVal(entry, _val_) \
19     do { (entry)->v.d = _val_; } while(0)
20 
21 #define dictFreeKey(d, entry) \
22     if ((d)->type->keyDestructor) \
23         (d)->type->keyDestructor((d)->privdata, (entry)->key)
24 
25 #define dictSetKey(d, entry, _key_) do { \
26     if ((d)->type->keyDup) \
27         (entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
28     else \
29         (entry)->key = (_key_); \
30 } while(0)
31 
32 #define dictCompareKeys(d, key1, key2) \
33     (((d)->type->keyCompare) ? \
34         (d)->type->keyCompare((d)->privdata, key1, key2) : \
35         (key1) == (key2))

rehashidx，是與ht[2]配合實現漸進式rehash操作的。若使用一步到位的方式，當key的數量非常大的時候，rehashing期間，是會卡死所有操作的。

iterators，是用於記錄當前使用的安全迭代器數量，與rehashing操作有關。整體結構如下：

 1 /*
 2 +---------+    /+-----------+   +-->+----------+  +---+
 3 |dictType*|   / |dictEntry**|---+   |dictEntry*|->|K|V|->NULL
 4 +---------+  /  +-----------+       +----------+  +---+
 5 |privdata | /   |size       |       |dictEntry*|->NULL
 6 +---------+/    +-----------+       +----------+
 7 |ht[2]    |     |sizemask   |       |dictEntry*|->NULL
 8 +---------+\    +-----------+       +----------+
 9 |rehashidx| \   |used       |       |dictEntry*|->NULL
10 +---------+  \  +-----------+       +----------+ 
11 |iterators|   \ 
12 +---------+    \+-----------+
13                 |dictEntry**|-->NULL
14                 +-----------+
15                 |size       |
16                 +-----------+
17                 |sizemask   |
18                 +-----------+
19                 |used       |
20                 +-----------+
21 */

二、創建

 1 static void _dictReset(dictht *ht)
 2 {
 3     ht->table = NULL;
 4     ht->size = 0;
 5     ht->sizemask = 0;
 6     ht->used = 0;
 7 }
 8 
 9 int _dictInit(dict *d, dictType *type,
10         void *privDataPtr)
11 {
12     _dictReset(&d->ht[0]);
13     _dictReset(&d->ht[1]);
14     d->type = type;
15     d->privdata = privDataPtr;
16     d->rehashidx = -1;
17     d->iterators = 0;
18     return DICT_OK;
19 }
20 
21 dict *dictCreate(dictType *type,
22         void *privDataPtr)
23 {
24     dict *d = zmalloc(sizeof(*d));
25 
26     _dictInit(d,type,privDataPtr);
27     return d;
28 }

可以調用dictCreate創建一個空的dict，它會分配好dict的空間，並初始化所有成員變數。在這裡把privdata傳入並保存。搜了一下整個redis源碼的dictCreate調用，看到傳入的值全為NULL。目前的理解暫時不清楚這個變數是什麼時候賦值的。初始化後的dict結構如下：

 1 /*
 2 +------------+    /+-----------+   
 3 |dictType*   |   / |dictEntry**|-->NULL
 4 +------------+  /  +-----------+   
 5 |privdata    | /   |size=0     |   
 6 +------------+/    +-----------+   
 7 |ht[2]       |     |sizemask=0 |   
 8 +------------+\    +-----------+   
 9 |rehashidx=-1| \   |used=0     |   
10 +------------+  \  +-----------+   
11 |iterators=0 |   \ 
12 +------------+    \+-----------+
13                    |dictEntry**|-->NULL
14                    +-----------+
15                    |size=0     |
16                    +-----------+
17                    |sizemask=0 |
18                    +-----------+
19                    |used=0     |
20                    +-----------+
21 */

剛創建好的dict是存不了任何數據的，其兩個hash table的size都為0。這裡先說明一下resize操作：

 1 #define DICT_HT_INITIAL_SIZE     4
 2 
 3 static unsigned long _dictNextPower(unsigned long size)
 4 {
 5     unsigned long i = DICT_HT_INITIAL_SIZE;
 6 
 7     if (size >= LONG_MAX) return LONG_MAX + 1LU;
 8     while(1) {
 9         if (i >= size)
10             return i;
11         i *= 2;
12     }
13 }
14 
15 /* Expand or create the hash table */
16 int dictExpand(dict *d, unsigned long size)
17 {
18     /* the size is invalid if it is smaller than the number of
19      * elements already inside the hash table */
20     if (dictIsRehashing(d) || d->ht[0].used > size)
21         return DICT_ERR;
22 
23     dictht n; /* the new hash table */
24     unsigned long realsize = _dictNextPower(size);
25 
26     /* Rehashing to the same table size is not useful. */
27     if (realsize == d->ht[0].size) return DICT_ERR;
28 
29     /* Allocate the new hash table and initialize all pointers to NULL */
30     n.size = realsize;
31     n.sizemask = realsize-1;
32     n.table = zcalloc(realsize*sizeof(dictEntry*));
33     n.used = 0;
34 
35     /* Is this the first initialization? If so it's not really a rehashing
36      * we just set the first hash table so that it can accept keys. */
37     if (d->ht[0].table == NULL) {
38         d->ht[0] = n;
39         return DICT_OK;
40     }
41 
42     /* Prepare a second hash table for incremental rehashing */
43     d->ht[1] = n;
44     d->rehashidx = 0;
45     return DICT_OK;
46 }
47 
48 int dictResize(dict *d)
49 {
50     int minimal;
51 
52     if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
53     minimal = d->ht[0].used;
54     if (minimal < DICT_HT_INITIAL_SIZE)
55         minimal = DICT_HT_INITIAL_SIZE;
56     return dictExpand(d, minimal);
57 }

_dictNextPower用於獲取當前要分配給hash table的size，得到的值一定是2的倍數，初始值為4。

dictExpand，從源碼註釋上看，它是為了擴容hash table，或者創建一個。它不允許與rehashing操作同時進行，也不能強制縮容。在使用_dictNextPower得到需要的size之後，它先是使用一個臨時變數n去分配空間，然後進行判斷，若ht[0].table的值為NULL，則認為是剛create出來的dict，直接把n賦值給ht[0]，否則給ht[1]，並開始rehashing操作。

dictResize操作就不用多說了。

三、rehashing操作

若有這樣一個dict，假設K1、K2、K3、K4計算出來的hash值分別為0、5、2、7，使用sizemask計算出來的idx分別為0、1、2、3

 1 /*
 2                                                       +----+
 3                                                    +->|K1|V|->NULL
 4 +------------+    /+-----------+  +->+----------+ /   +----+
 5 |dictType*   |   / |dictEntry**|--+  |dictEntry*|/    +----+
 6 +------------+  /  +-----------+     +----------+ +-->|K2|V|->NULL
 7 |privdata    | /   |size=4     |     |dictEntry*|/    +----+
 8 +------------+/    +-----------+     +----------+
 9 |ht[2]       |     |sizemask=3 |     |dictEntry*|\    +----+
10 +------------+\    +-----------+     +----------+ +-->|K3|V|->NULL
11 |rehashidx=-1| \   |used=4     |     |dictEntry*|\    +----+
12 +------------+  \  +-----------+     +----------+ \   +----+
13 |iterators=0 |   \                                 +->|K4|V|->NULL
14 +------------+    \+-----------+                      +----+
15                    |dictEntry**|-->NULL
16                    +-----------+
17                    |size=0     |
18                    +-----------+
19                    |sizemask=0 |
20                    +-----------+
21                    |used=0     |
22                    +-----------+
23 */

 1 static int _dictExpandIfNeeded(dict *d)
 2 {
 3     /* Incremental rehashing already in progress. Return. */
 4     if (dictIsRehashing(d)) return DICT_OK;
 5 
 6     /* If the hash table is empty expand it to the initial size. */
 7     if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
 8 
 9     /* If we reached the 1:1 ratio, and we are allowed to resize the hash
10      * table (global setting) or we should avoid it but the ratio between
11      * elements/buckets is over the "safe" threshold, we resize doubling
12      * the number of buckets. */
13     if (d->ht[0].used >= d->ht[0].size &&
14         (dict_can_resize ||
15          d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
16     {
17         return dictExpand(d, d->ht[0].used*2);
18     }
19     return DICT_OK;
20 }

通過函數_dictExpandIfNeeded，可知當used >= size且dict_can_resize == TRUE的時候，需要調用dictExpand進入rehashing狀態。dict_can_resize預設為1

1 static int dict_can_resize = 1;
2 static unsigned int dict_force_resize_ratio = 5;

需要的size為當前used * 2，即為8。調用dictExpand之後的結構：

 1 /*
 2                                                        +----+
 3                                                     +->|K1|V|->NULL
 4                                    +->+----------+ /   +----+
 5                                    |  |dictEntry*|/    +----+
 6                                    |  +----------+ +-->|K2|V|->NULL
 7                                    |  |dictEntry*|/    +----+
 8  +------------+    /+-----------+  |  +----------+
 9  |dictType*   |   / |dictEntry**|--+  |dictEntry*|\    +----+
10  +------------+  /  +-----------+     +----------+ +-->|K3|V|->NULL
11  |privdata    | /   |size=4     |     |dictEntry*|\    +----+
12  +------------+/    +-----------+     +----------+ \   +----+
13  |ht[2]       |     |sizemask=3 |                   +->|K4|V|->NULL
14  +------------+\    +-----------+                      +----+
15  |rehashidx=0 | \   |used=4     | 
16  +------------+  \  +-----------+  
17  |iterators=0 |   \                
18  +------------+    \+-----------+  +->+----------+
19                     |dictEntry**|--+  |dictEntry*|->NULL
20                     +-----------+     +----------+
21                     |size=8     |     |dictEntry*|->NULL
22                     +-----------+     +----------+
23                     |sizemask=7 |     |dictEntry*|->NULL
24                     +-----------+     +----------+
25                     |used=0     |     |dictEntry*|->NULL
26                     +-----------+     +----------+
27                                       |dictEntry*|->NULL
28                                       +----------+
29                                       |dictEntry*|->NULL
30                                       +----------+
31                                       |dictEntry*|->NULL
32                                       +----------+
33                                       |dictEntry*|->NULL
34                                       +----------+
35 */

根據rehashing操作

 1 int dictRehash(dict *d, int n) {
 2     int empty_visits = n*10; /* Max number of empty buckets to visit. */
 3     if (!dictIsRehashing(d)) return 0;
 4 
 5     while(n-- && d->ht[0].used != 0) {
 6         dictEntry *de, *nextde;
 7 
 8         /* Note that rehashidx can't overflow as we are sure there are more
 9          * elements because ht[0].used != 0 */
10         assert(d->ht[0].size > (unsigned long)d->rehashidx);
11         while(d->ht[0].table[d->rehashidx] == NULL) {
12             d->rehashidx++;
13             if (--empty_visits == 0) return 1;
14         }
15         de = d->ht[0].table[d->rehashidx];
16         /* Move all the keys in this bucket from the old to the new hash HT */
17         while(de) {
18             uint64_t h;
19 
20             nextde = de->next;
21             /* Get the index in the new hash table */
22             h = dictHashKey(d, de->key) & d->ht[1].sizemask;
23             de->next = d->ht[1].table[h];
24             d->ht[1].table[h] = de;
25             d->ht[0].used--;
26             d->ht[1].used++;
27             de = nextde;
28         }
29         d->ht[0].table[d->rehashidx] = NULL;
30         d->rehashidx++;
31     }
32 
33     /* Check if we already rehashed the whole table... */
34     if (d->ht[0].used == 0) {
35         zfree(d->ht[0].table);
36         d->ht[0] = d->ht[1];
37         _dictReset(&d->ht[1]);
38         d->rehashidx = -1;
39         return 0;
40     }
41 
42     /* More to rehash... */
43     return 1;
44 }

rehashing操作將會把ht[0]里，rehashidx的值對應的bucket下的所有dictEntry，移至ht[1]，之後對rehashidx進行自增處理。當ht[0]->used為0時，認為ht[0]的所有dictEntry已經移至ht[1]，此時return 0，否則 return 1，告訴調用者，還需要繼續進行rehashing操作。同時，rehashing時允許最多跳過10n的空bucket，就要退出流程。假設傳入的n=1，即只進行一次rehashing操作，轉換至完成之後的結構：

 1 /*
 2                                                        
 3                                                     +->NULL
 4                                    +->+----------+ /   
 5                                    |  |dictEntry*|/    +----+
 6                                    |  +----------+ +-->|K2|V|->NULL
 7                                    |  |dictEntry*|/    +----+
 8  +------------+    /+-----------+  |  +----------+
 9  |dictType*   |   / |dictEntry**|--+  |dictEntry*|\    +----+
10  +------------+  /  +-----------+     +----------+ +-->|K3|V|->NULL
11  |privdata    | /   |size=4     |     |dictEntry*|\    +----+
12  +------------+/    +-----------+     +----------+ \   +----+
13  |ht[2]       |     |sizemask=3 |                   +->|K4|V|->NULL
14  +------------+\    +-----------+                      +----+
15  |rehashidx=1 | \   |used=3     | 
16  +------------+  \  +-----------+  
17  |iterators=0 |   \                
18  +------------+    \+-----------+  +->+----------+   +----+
19                     |dictEntry**|--+  |dictEntry*|-->|K1|V|->NULL
20                     +-----------+     +----------+   +----+ 
21                     |size=8     |     |dictEntry*|->NULL
22                     +-----------+     +----------+
23                     |sizemask=7 |     |dictEntry*|->NULL
24                     +-----------+     +----------+
25                     |used=1     |     |dictEntry*|->NULL
26                     +-----------+     +----------+
27                                       |dictEntry*|->NULL
28                                       +----------+
29                                       |dictEntry*|->NULL
30                                       +----------+
31                                       |dictEntry*|->NULL
32                                       +----------+
33                                       |dictEntry*|->NULL
34                                       +----------+
35 */

所有節點移完時：

 1 /*
 2                                                        
 3                                                   
 4                                    +->+----------+
 5                                    |  |dictEntry*|->NULL
 6                                    |  +----------+
 7                                    |  |dictEntry*|->NULL    
 8  +------------+    /+-----------+  |  +----------+
 9  |dictType*   |   / |dictEntry**|--+  |dictEntry*|->NULL    
10  +------------+  /  +-----------+     +----------+
11  |privdata    | /   |size=4     |     |dictEntry*|->NULL    
12  +------------+/    +-----------+     +----------+ 
13  |ht[2]       |     |sizemask=3 |                  
14  +------------+\    +-----------+                      
15  |rehashidx=4 | \   |used=0     | 
16  +------------+  \  +-----------+  
17  |iterators=0 |   \                
18  +------------+    \+-----------+  +->+----------+   +----+
19                     |dictEntry**|--+  |dictEntry*|-->|K1|V|->NULL
20                     +-----------+     +----------+   +----+ 
21                     |size=8     |     |dictEntry*|->NULL
22                     +-----------+     +----------+   +----+
23                     |sizemask=7 |     |dictEntry*|-->|K3|V|->NULL
24                     +-----------+     +----------+   +----+
25                     |used=4     |     |dictEntry*|->NULL
26                     +-----------+     +----------+
27                                       |dictEntry*|->NULL
28                                       +----------+   +----+
29                                       |dictEntry*|-->|K2|V|->NULL
30                                       +----------+   +----+
31                                       |dictEntry*|->NULL
32                                       +----------+   +----+
33                                       |dictEntry*|-->|K4|V|->NULL
34                                       +----------+   +----+ 
35 */

此時ht[0]->used為0，釋放原ht[0]的hash table，把ht[1]賦值給ht[0]，並設置ht[1] = NULL，最後重置rehashidx=-1，rehashing操作結束

 1 /*
 2  +------------+    /+-----------+   +-->+----------+   +----+
 3  |dictType*   |   / |dictEntry**|---+   |dictEntry*|-->|K1|V|->NULL
 4  +------------+  /  +-----------+       +----------+   +----+
 5  |privdata    | /   |size=8     |       |dictEntry*|->NULL
 6  +------------+/    +-----------+       +----------+   +----+
 7  |ht[2]       |     |sizemask=7 |       |dictEntry*|-->|K3|V|->NULL
 8  +------------+\    +-----------+       +----------+   +----+
 9  |rehashidx=-1| \   |used=4     |       |dictEntry*|->NULL
10  +------------+  \  +-----------+       +----------+
11  |iterators=0 |   \                     |dictEntry*|->NULL
12  +------------+    \+-----------+       +----------+   +----+
13                     |dictEntry**|->NULL |dictEntry*|-->|K2|V|->NULL
14                     +-----------+       +----------+   +----+
15                     |size=0     |       |dictEntry*|->NULL
16                     +-----------+       +----------+   +----+
17                     |sizemask=0 |       |dictEntry*|-->|K4|V|->NULL
18                     +-----------+       +----------+   +----+
19                     |used=0     |     
20                     +-----------+     
21 */

rehashing操作的觸發共有兩種方式

1、定時操作

 1 long long timeInMilliseconds(void) {
 2     struct timeval tv;
 3 
 4     gettimeofday(&tv,NULL);
 5     return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
 6 }
 7 
 8 /* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
 9 int dictRehashMilliseconds(dict *d, int ms) {
10     long long start = timeInMilliseconds();
11     int rehashes = 0;
12 
13     while(dictRehash(d,100)) {
14         rehashes += 100;
15         if (timeInMilliseconds()-start > ms) break;
16     }
17     return rehashes;
18 }