Redis数据结构 - 字典
字典是一种存储健值对(key-value)的抽象数据结构。在字典中,一个Key和一个Value进行关联,这些关联的键和值就成为健值对。字典中每个Key都是独一无二的,程序通过Key来更新对应的Value。
C语言中没有内置字典,Redis构建了自己的字典实现。字典在Redis中应用相当广泛,比如Redis数据库就是使用字典作为底层实现的,对数据库的CURD也是构建在对字典的操作之上。字典还是哈希健的底层实现之一。
字典的实现
Redis的字典使用哈希表作为底层实现,一个哈希表里边可以有多个哈希表节点,每个哈希表节点就保存字典中的一个健值对。
哈希表
1 | //哈希表 |
- table 属性是一个数组,数组中每个元素都指向dictEntity(哈希表节点)结构的指针,每个dictEntity结构保存着一个健值对。
- size 属性记录哈希表的大小,也是table数组的大小。
- used 属性记录了哈希表目前已有的健值对数量。
- sizemask 属性的值总是等于size-1,这个属性和哈希值一起决定一个健应该放在table数组的哪个索引上边。
哈希表节点
1 | //哈希表节点 |
key 属性保存着健值对应的健,v属性保存对应的值。其中v属性可以是指针,或者是unit64_t整数,又或者是int64_t整数。next属性是指向下个哈希节点的指针,用以解决健冲突。
字典
1 | //字典 |
type 属性 和 privdata属性是针对不同类型的健值对,为创建多态字典而设置的:
- type 属性是一个指向dicType结构的指针,每个dicType结构保存了一簇用于操作特定类型健值对的函数,Redis会为用途不同的字典设置不同的类型特定函数。
- privdata 属性保存了需要传给那些特定类型函数的可选参数。
1 | typedef struct dicType { |
- ht 属性包含2个哈希表,一般情况下字典只使用ht[0]哈希表, 而ht[1]哈希表只会在对字典进行rehash的时候使用。
- rehashidx 是一个记录当前rehash进度的属性,如果没有rehash则为-1。
哈希算法
当要将一个新的健值对添加到字典里时,程序首先根据健值对的健计算出哈希值和索引值。然后根据索引值将包含健值对的哈希节点放到哈希数组指定索引上。
- 使用字典设置的哈希函数,计算出健key的哈希值
- hash = dict->type->hashFunction(key);
- 使用哈希表的sizemask属性和哈希值,计算出索引值。具体使用的哈希表由字典的rehashidx决定
- index = hash & dict->ht[0].sizemask;
解决健冲突
当有2个或2个以上数量的健被分配到哈希表同一个索引上时,称为冲突。Redis使用链地址法来解决冲突。
每个哈希节点都有一个next指针,多个哈希节点可以通过next指针构成一个单向链。被分配到同一个索引上的多个哈希节点使用单向链连接起来,这就解决了健冲突。
考虑到速度,程序总是将新的哈希节点添加到链表的表头位置。
rehash
随着对字典不断的操作,哈希表存储的健值对数量会发生变化,为了让哈希表的负载因子维持在一个合理的范围,程序需要对哈希表进行扩容或收缩。
Redis对字典的rehash步骤如下
为字典的ht[1]哈希表分配空间。
- 如果执行的扩容操作,那么ht[1]的大小为第一个大于等于 ht[0].used*2 的 2的n次幂。(例如,当ht[0].used = 9,即哈希表中有9个哈希节点扩容时。扩容大小为大于等于18的第一个2的n次幂,为:32)
- 如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于 ht[0].used 的2的n次幂。(例如,当ht[0].used = 9,即哈希表中有9个哈希节点收缩时。扩容大小为大于等于9的第一个2的n次幂,为:16)
将保存在ht[0]中的所有健值对rehash到ht[1]上边。即重新计算索引值,然后将对应的哈希节点放知道ht[1]哈希表对应的索引上。
当ht[0]中包含的所有健值对都迁移到ht[1]之后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下次rehash作准备。
渐进式rehash
当数据量比较大时,为避免rehash对服务器造成性能问题,服务器不是一次性的将ht[0]中的所有健全部rehash到ht[1]中,而是分多次、渐进式进行操作。
- 为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操作完成。
渐进式rehash的好处是采用分治方式,将rehash健值所需的操作分摊到对字典的每个添加、删除、查找和更新操作上。从而避免集中式rehash带来的性能影响。
在执行渐进式rehash的过程中,字典会同时使用ht[0]和ht[1]两个哈希表,所以在渐进式rehash期间,字典的操作会在两个哈希表上进行。比如需要查找某个健的话,现在ht[0]上进行,如果没有找到,则在ht[1]上进行。
另外新添加的字典健值对一律会保存在ht[1]上,不在ht[0]上操作保证了ht[0]中的健值对数量只减不增,最终变成空表。
本文标题:Redis数据结构 - 字典
文章作者:梁通
发布时间:2020-10-23
最后更新:2020-10-23
原始链接:http://www.liangtong.site/2020/10/23/database_20201023_redis_dict/
版权声明:Copyright© 2016-2020 liangtong 版权所有