dict 是一种用于保存键值对的抽象数据结构,在 redis 中使用非常广泛,比如数据库、哈希结构的底层。
当执行下面这个命令:
> set msg "hello"
以及使用哈希结构,如:
- > hset people name "hoohack"
都会使用到 dict 作为底层数据结构的实现。
先看看字典以及相关数据结构体的定义:
- /* 字典结构 每个字典有两个哈希表,实现渐进式哈希时需要用在将旧表rehash到新表 */
- typedef struct dict {
- dictType *type; /* 类型特定函数 */
- void *privdata; /* 保存类型特定函数需要使用的参数 */
- dictht ht[2]; /* 保存的两个哈希表,ht[0]是真正使用的,ht[1]会在rehash时使用 */
- long rehashidx; /* rehashing not in progress if rehashidx == -1 rehash进度,如果不等于-1,说明还在进行rehash */
- unsigned long iterators; /* number of iterators currently running 正在运行中的遍历器数量 */
- } dict;
- /* 哈希表结构 */
- typedef struct dictht {
- dictEntry **table; /* 哈希表节点数组 */
- unsigned long size; /* 哈希表大小 */
- unsigned long sizemask; /* 哈希表大小掩码,用于计算哈希表的索引值,大小总是dictht.size - 1 */
- unsigned long used; /* 哈希表已经使用的节点数量 */
- } dictht;
- /* 哈希表节点 */
- typedef struct dictEntry {
- void *key; /* 键名 */
- union {
- void *val;
- uint64_t u64;
- int64_t s64;
- double d;
- } v; /* 值 */
- struct dictEntry *next; /* 指向下一个节点, 将多个哈希值相同的键值对连接起来*/
- } dictEntry;
- /* 保存一连串操作特定类型键值对的函数 */
- typedef struct dictType {
- uint64_t (*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;
把上面的结构定义串起来,得到下面的字典数据结构:
根据数据结构定义,把关联图画出来后,看代码的时候就更加清晰。
从图中也可以看出来,字典的哈希表里,使用了链表解决键冲突的情况,称为链式地址法。
当操作越来越多,比如不断的向哈希表添加元素,此时哈希表需要分配了更多的空间,如果接下来的操作是不断地删除哈希表的元素,那么哈希表的大小就会发生变化,更重要的是,现在的哈希表不再需要那么大的空间了,在 redis 的实现中,为了保证哈希表的负载因子维持在一个合理范围内,当哈希表保存的键值对太多或者太少时,redis 对哈希表大小进行相应的扩展和收缩,称为 rehash(重新散列)。
负载因子 = 哈希表已保存节点数量 / 哈希表大小
负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。因此,一般来说,当负载因子大于某个常数 (可能是 1,或者 0.75 等) 时,哈希表将自动扩容。
在上面的 rehash 流程图里面,rehash 的操作不是一次性就完成了的,而是分多次,渐进式地完成。
原因是,如果需要 rehash 的键值对较多,会对服务器造成性能影响,渐进式地 rehash 避免了对服务器的影响。
渐进式的 rehash 使用了 dict 结构体中的 rehashidx 属性辅助完成。当渐进式哈希开始时,rehashidx 会被设置为 0,表示从 dictEntry[0] 开始进行 rehash,每完成一次,就将 rehashidx 加 1。直到 ht[0] 中的所有节点都被 rehash 到 ht[1],rehashidx 被设置为 - 1,此时表示 rehash 结束。
- /* 实现渐进式的重新哈希,如果还有需要重新哈希的key,返回1,否则返回0
- *
- * 需要注意的是,rehash持续将bucket从老的哈希表移到新的哈希表,但是,因为有的哈希表是空的,
- * 因此函数不能保证即使一个bucket也会被rehash,因为函数最多一共会访问N*10个空bucket,不然的话,函数将会耗费过多性能,而且函数会被阻塞一段时间
- */
- int dictRehash(dict *d, int n) {
- int empty_visits = n*10; /* Max number of empty buckets to visit. */
- if (!dictIsRehashing(d)) return 0;
- while(n-- && d->ht[0].used != 0) {
- dictEntry *de, *nextde;
- assert(d->ht[0].size > (unsigned long)d->rehashidx);
- /* 找到非空的哈希表下标 */
- while(d->ht[0].table[d->rehashidx] == NULL) {
- d->rehashidx++;
- if (--empty_visits == 0) return 1;
- }
- de = d->ht[0].table[d->rehashidx];
- /* 实现将bucket从老的哈希表移到新的哈希表 */
- while(de) {
- unsigned int h;
- nextde = de->next;
- /* Get the index in the new hash table */
- h = dictHashKey(d, de->key) & d->ht[1].sizemask;
- de->next = d->ht[1].table[h];
- d->ht[1].table[h] = de;
- d->ht[0].used--;
- d->ht[1].used++;
- de = nextde;
- }
- d->ht[0].table[d->rehashidx] = NULL;
- d->rehashidx++;
- }
- /* 如果已经完成了,释放旧的哈希表,返回0 */
- if (d->ht[0].used == 0) {
- zfree(d->ht[0].table);
- d->ht[0] = d->ht[1];
- _dictReset(&d->ht[1]);
- d->rehashidx = -1;
- return 0;
- }
- /* 继续下一次rehash */
- return 1;
- }
在渐进式 rehash 期间,所有对字典的操作,包括:添加、查找、更新等等,程序除了执行指定的操作之外,还会顺带将 ht[0] 哈希表索引的所有键值对 rehash 到 ht[1]。比如添加:
- dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
- {
- int index;
- dictEntry *entry;
- dictht *ht;
- /* 如果正在rehash,顺带执行rehash操作 */
- if (dictIsRehashing(d)) _dictRehashStep(d);
- /* 获取新元素的下标,如果已经存在,返回-1 */
- if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
- return NULL;
- ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 如果正在进行rehash操作,返回ht[1],否则返回ht[0]
- entry = zmalloc(sizeof(*entry));
- entry->next = ht->table[index];
- ht->table[index] = entry;
- ht->used++;
- /* Set the hash entry fields. */
- dictSetKey(d, entry, key);
- return entry;
- }
使用一个标记值标记某项操作正在执行是编程中常用的手段,比如本文提到的 rehashidx,多利用此手段可以解决很多问题。
我在 github 有对 Redis 源码更详细的注解。感兴趣的可以围观一下,给个 star。 Redis4.0 源码注解 。可以通过 commit 记录 查看已添加的注解。
原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。
来源: https://www.cnblogs.com/hoohack/p/8241665.html