当前位置: 首页 > redis, 分布式系统 > 正文

解读Redis dict核心数据结构

关键字:
1 星2 星3 星4 星5 星 (暂无评分)
Loading ... Loading ...
baidu_share

Redis中最重要的数据结构就是dict,每个redisDb中包含一个指针指向dict。

相关数据结构 redis.h

1
2
#define DICT_OK 0
#define DICT_ERR 1

dictEntry类似于一个node,它保存者key,value,next用于iterator迭代时使用

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

每个dict都拥有一个自己dictType,使得每个dict不同,如hash函数不同,键值复制,比较不同等等,使得dict的用途多元化

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

dictht 是一个哈希表,每个dict中含有两个dictht,多的一个是用于扩容时使用, size指的是table指针数组的大小,这里使用了当hash值相同时,每个table[index]是一个dictEntry*, 使得hash值相同的两个dictEntry能成链表保存,这里的size永远是2的指数方,这样sizemask=size-1,(用于计算到的hash值&sizemask)在size范围内。used就是dictht中dictEntry的数量

1
2
3
4
5
6
7
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;

table,index,分别为此时iterator位于的表的位置,nextEntry用于safe iterator进行删除操作时,提前保存下一个entry。

1
2
3
4
5
6
7
8
9
/* If safe is set to 1 this is a safe iteartor, that means, you can call
* dictAdd, dictFind, and other functions against the dictionary even while
* iterating. Otherwise it is a non safe iterator, and only dictNext()
* should be called while iterating. */
typedef struct dictIterator {
    dict *d;
    int table, index, safe;
    dictEntry *entry, *nextEntry;
} dictIterator;

dict的创建和释放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/* Create a new hash table */
dict *dictCreate(dictType *type,
void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));
 
    _dictInit(d,type,privDataPtr);
    return d;
}
 
/* Reset a hash table already initialized with ht_init().
* NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}
 
/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,
void *privDataPtr)
{
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}
 
/* Clear & Release the hash table */
void dictRelease(dict *d)
{
    _dictClear(d,&d->ht[0]);
    _dictClear(d,&d->ht[1]);
    zfree(d);
}
 
/* Destroy an entire dictionary */
int _dictClear(dict *d, dictht *ht)
{
    unsigned long i;
 
/* Free all the elements */
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        dictEntry *he, *nextHe;
 
        if ((he = ht->table[i]) == NULL) continue;
        while(he) {
            nextHe = he->next;
            dictFreeKey(d, he);
            dictFreeVal(d, he);
            zfree(he);
            ht->used--;
            he = nextHe;
        }
    }
/* Free the table and the allocated cache structure */
    zfree(ht->table);
/* Re-initialize the table */
    _dictReset(ht);
    return DICT_OK; /* never fails */
}

创建和释放dict结构没有不同之处,简单的初始化dict结构,将两个dictht都设为NULL,在增加dictEntry时才会初始化dictht表结构。

dict扩容 dict扩容是redis实现dict结构最重要也是最复杂的操作。我们用Q&A的方式来解释整个扩容过程。
何时需要扩容? 每次增加dictEntry时,都会调用一次_dictExpandIfNeeded()这个函数。 1.如果dict正在扩容,则返回正常DICT_OK 2.如果dict刚刚初始化,也就是两个dictht都为NULL,则调用dictExpand()函数初始化。dictExpand()同样会做一次判断两个dictht都为NULL,然后直接赋给ht[0]。 3.如果可以扩容(dict_can_resize=1),那么只要现在表中键总数大于表的长度就开始扩容。如果不能扩容(也就是dict_can_resize=0),但是如果表中键总数与表的长度的比值大于某一个阀值(由dict_force_resize_ratio静态变量决定),那么就强制扩容。

扩容是怎么进行的? 之前所说的每个dict中都有两个哈希表结构dictht *ht[2]。当开始扩容时,把第一个ht作为原始表,第二个作为扩容后的表。dict中rehashidx决定了目前扩容的进度。

扩容过程什么时候执行? 当决定开始扩容后,dict中rehashidx赋为0,然后有两个函数来进行扩容。

1
2
int dictRehash(dict *d, int n);
int dictRehashMilliseconds(dict *d, int ms);

第一个函数中n决定每次rehash(也就是转移dictEntry)的次数,第二个函数决定调用rehash函数的时间。 每次执行查找,增加,删除操作都会执行一次dictRehash(1)(如果正在扩容),使得整个漫长的扩容过程隐含在每一次简单的操作中。
dict的hash函数 dict中hash函数有一个通用函数:

1
2
3
4
5
6
7
unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
unsigned int hash = dict_hash_function_seed;
 
    while (len--)
    hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
    return hash;
}

针对整型又有另外一个:

1
2
3
4
5
6
7
8
9
{
    key += ~(key << 15);
    key ^= (key >> 10);
    key += (key << 3);
    key ^= (key >> 6);
    key += ~(key << 11);
    key ^= (key >> 16);
    return key;
}

对hash函数没有太多了解,因此也无法判断这个函数的效果相比其他如何和优点。

dict的增加,替代,删除,查找键值 查找键值:

1
2
int dictAdd(dict *d, void *key, void *val);
dictEntry *dictAddRaw(dict *d, void *key);

dictFind根据key返回相应的dictEntry,而dictFetchValue()返回相应的值。

增加键值:

1
2
int dictAdd(dict *d, void *key, void *val);
dictEntry *dictAddRaw(dict *d, void *key);

dictAddRaw()属于较低级的函数,它暴露了dictEntry给用户,用户可以根据返回dictEntry进行额外的操作,它调用_dictKeyIndex()得到key哈希后的值,也就是dictht中table指针数组的下标,如果该key已经存在返回-1(值得注意的是_dictKeyIndex()只用于在dictAddRaw()中调用,而是否扩容判断就在_dictKeyIndex()中,因此,只有增加dictEntry操作才会判断是否扩容)。dictAdd()是dictAddRaw的包装函数,直接调用了dictAddRaw,并且对这个dictEntry进行值的赋予。 另外值得注意的是增加操作如果在扩容时期时,会直接添加到扩容后的表。

替换键值:

1
2
int dictReplace(dict *d, void *key, void *val);
dictEntry *dictReplaceRaw(dict *d, void *key);

dictReplaceRaw()也是dictAddRaw的包装函数,只不过它会调用dictFind()首先查找是否有这个键,如果没有直接调用dictAddRaw(),如果有,那么返回存在的dictEntry。dictReplace()会首先尝试调用dictAdd(),如果添加失败,那么再调用dictFind()得到存在的dictEntry,再对值进行覆盖。这么考虑是因为往往替代操作很大一部分key在表中是不存在的,直接添加免去了查找。节约了运行时间。

删除键值:

1
2
int dictDelete(dict *d, const void *key);
int dictDeleteNoFree(dict *d, const void *key);

两个函数都是静态函数 static int dictGenericDelete(dict *d, const void *key, int nofree) 的包装函数,只是在是否释放掉键值上不同。 dictGenericDelete()跟dictAddRaw()类似,都是尝试得到对应key的dictEntry,如果有,则删除。

迭代器操作

1
2
3
4
dictIterator *dictGetIterator(dict *d);
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);

dictGetIterator()初始化了dictIterator,dictGetSafeIterator()包装了dictGetIterator(),只是将safe属性赋为1。 dictNext()参数会判断iterator是否safe,如果safe,那么计入dict结构中的iterators。这个iterators决定是否在增加,删除,查找过程中调用rehash过程。

本文固定链接: http://www.chepoo.com/redis-dict-analysis.html | IT技术精华网

解读Redis dict核心数据结构:等您坐沙发呢!

发表评论