Redis 字典

发表于2022-03-23更新于2022-05-07阅读次数

字典结构


dict 描述一个字典，其中的 dictht 描述哈希表，其中的 dictEntry 描述键值对结构

字典dict数据结构

Redis中的字典是由dict.h/dict结构表示

1
2
3
4
5
6
7
8
9
10
11
typedef struct dict{
   //类型特定函数
	dictType *type;
	//私有数据
	void *privdata;
	//哈希表
	dictht ht[2];
	//rehash索引，表示当前正在h[0]哪个**table链上进行rehash
	//当rehash不在进行时，值为-1
	int rehashidx;
}dict;

ht属性是一个包含两个项的数组，数组中的每个顶都是一个dictht哈希表，一般情况下只使用ht[0]哈希表，ht[1]哈希表只会在进行rehash时使用，包括rehashidx也是在rehash时用到的。

哈希表dictht数据结构

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht{
     //哈希表数组
     dictEntry **table;
     //哈希表大小
     unsigned long size;
     //哈希表大小掩码，用于计算索引值
     //总是等于 size-1
     unsigned long sizemask;
     //该哈希表已有节点的数量
     unsigned long used;
     }dictht；

table属性是一个数组，数组中的每一个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键应该被放在什么位置

哈希表节点dictEntry数据结构

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对；

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;

     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry；

保存的值（v）可以是一个指针，或者一个uint_t整数，又或者是一个int64_t整数

hash冲突解决


当键k0和k1的经过散列函数得到索引值都为1时，就会使用next指针将两个节点连接起来。而由于节点没有指向链尾的指针，因此新的节点总是插入到链表的头部，排在已有节点的前面。

rehash

触发条件

散列表负载因子越大，代表空闲位置越少，冲突也就越多，散列表的性能会下降。为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表存储的键值对太多或者太少，程序要对哈希表的大小进行相应的扩展或者收缩。
负载因子计算方式:
负载因子=哈希表以保存的节点数量/哈希表的大小，load_factor=ht[0].used/ht[0].size

  • 服务器目前没有执行的BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
  • 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5
  • 当负载因子小于0.1时，程序自动开始执行收缩操作
    Redis这么做的目的是基于操作系统创建子进程后写时复制技术，避免不必要的写入操作。

原理

  • 为ht[1]分配空间， 让字典同时持有ht[0]和ht[1]两个哈希表。ht[1]的大小取决于要执行的操作以及ht[0]当前包含的键值对数量(即:ht[0].used的属性值)
  • 扩展操作：ht[1]的大小为 第一个大于等于ht[0].used*2的2的n次方幂。如:ht[0].used=3则ht[1]的大小为8，ht[0].used=4则ht[1]的大小为8。
  • 收缩操作: ht[1]的大小为 第一个大于等于ht[0].used的2的n次方幂

  • 将保存在ht[0]中的键值对重新计算键的散列值和索引值，然后放到ht[1]指定的位置上

  • 将ht[0]包含的所有键值对都迁移到了ht[1]之后，释放ht[0],将ht[1]设置为ht[0],并创建一个新的ht[1]哈希表为下一次rehash做准备

渐进式rehash

为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成。当负载因子触达阈值之后，只申请新空间，但并不将老的数据搬移到新散列表中。当有新数据要插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次一次性数据搬移，插入操作就都变得很快了。

rehash步骤

  • 为 ht[1]分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  • 在字典中维持一个索引计数器变量rehashidx， 并将它的值设置为0 ，表示rehash工作正式开始
  • 在rehash进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1] ， 当rehash工作完成之后， 程序将rehashidx ++。
  • 随着字典操作的不断执行， 最终在某个时间点上， ht[0]的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

源码如下：

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
//
int dictRehash(dict *d, int n) {
	if (!dictIsRehashing(d)) return 0;
	while (n--) { 
		dictEntry *de, *nextde;
		if (d->ht[0].used == 0) {   // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
			zfree(d->ht[0].table);
			d->ht[0] = d->ht[1];
			_dictReset(&d->ht[1]);
			d->rehashidx = -1;
			return 0;
		}
 
		// Note that rehashidx can't overflow as we are sure there are more
		// elements because ht[0].used != 0
		// 确保 rehashidx 没有越界
		assert(d->ht[0].size > (unsigned)d->rehashidx);
 
		while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;    // 略过数组中为空的索引，找到下一个非空索引
 
		de = d->ht[0].table[d->rehashidx];
		while (de) {
			unsigned int h;
			nextde = de->next;
			// 计算新哈希表的哈希值，以及节点插入的索引位置
			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++;
	}
	return 1;

}

参数 n，这个参数用于控制单次最多转移空桶数量。
正常情况下，一次 rehash 只会转移一个桶，但如果上一次转移了索引为1的那个桶，下一次来会遍历后面一个桶，如果继续为空就继续向后遍历，直到找到一个存储了我们节点的非空桶，极端情况下，如果字典表中只有最后一个桶有节点，那么一次的 rehash 就要遍历所有的桶，时间复杂度 O(n)，这会导致客户端等待过长时间，所以新版本中额外传一个参数 n 用于控制最多遍历的空桶数。

方法的尾部会进行一个校验，如果当前桶转移结束后，当前字典的 rehash 过程完全结束，那么修改 ht[0] 指针引用，让他指向新的字典表 ht[1]，并设置 rehashidx 为 -1，标记整个字典 rehash 结束。

rehashidx一共有三种状态，0表示要开始进行rehash，-1表示rehash结束或目前没有进行，其它值就表示正在进行rehash。

set指令rehash过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    int index;
    dictEntry *entry;
    dictht *ht;
 
    if (dictIsRehashing(d)) _dictRehashStep(d);
 
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->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;
}

当我们添加键值对的方法，函数的最开头逻辑就是调用 dictIsRehashing 方法判断当前的字典表是否处于 rehash 状态，也即判断 rehashidx 是否不等于 -1 。

默认情况下，一次 rehash 过程，redis 允许最多 10 空桶的访问就要返回，不得逗留。值得注意的是，方法的后续逻辑会判断当前字典如果正在进行 rehash，那么新的键值对将不再向 ht[0] 中添加，而直接转而添加到 ht[1] 中。

get指令rehash过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;
 
    if (d->ht[0].used + d->ht[1].used == 0) return NULL; 
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

可以看到，同样也是有 dictIsRehashing 方法的判断，如果字典处于 rehash 状态，即需要去完成一个桶的转移，然后才能返回。值得注意的是，方法的中间逻辑是嵌套在一个 for 循环中的，供两次循环，第一次从 ht[0] 中搜索我们给定 key 的键值对，如果没有找到，第二次循环将从 ht[1] 中搜索我们要查询的键值对。

总结

  • 在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行
  • 如果是查找的话，就会现在ht[0]中查找，没有就去ht[1]中找，但是如果是增加的话，就会一律保存到ht[1]中，不会再像ht[0]中进行任何添加操作，保证ht[0]中的数据只减不增，直到他变成一个空表

参考资料