Redis底层数据结构之Dict

2024-04-24 03:12
文章标签 数据结构 redis 底层 dict

本文主要是介绍Redis底层数据结构之Dict,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

    • 一、概述
    • 二、Dict结构
    • 三、Dictht结构
    • 四、DictEntry结构
    • 五、核心特性

上一篇文章 reids底层数据结构之quicklist

一、概述

Redis 的 Dict 是一个高效的键值对映射数据结构,采用双哈希表实现以支持无锁的渐进式 Rehash,确保扩容或缩容时的高效性能。它通过哈希表节点以链表形式解决哈希冲突,允许快速的查找、插入和删除操作,是实现 Redis 各种数据类型和高级功能的基础架构之一。

二、Dict结构

在这里插入图片描述

type:这是一个指向 dictType 结构的指针,为该字典提供一套特定的操作函数。dictType 结构包含了一系列函数指针,用于定义键值对的复制、释放、比较等操作。这使得 dict 结构能够以通用的方式操作不同类型的键和值。

privdata:这是一个指向任意类型数据的指针,该数据会被传递给 dictType 结构中的各种函数。它允许这些函数拥有一个通用的接口,同时又能进行针对特定情境的操作。

ht[0]ht[1]: 这是两个 dictht(哈希表)数组,用于存储字典中的元素。Redis 使用一个渐进式的 rehashing 过程来扩展或缩小这个数据结构的容量。通常,所有的操作都在 ht[0] 上进行,当字典需要扩展或缩小时,元素会逐渐从 ht[0] 移动到 ht[1],这一过程是逐渐进行的,以避免长时间的阻塞

rehashidx: 这是一个标记,用来表示rehashing 进程的进度。当不在 rehashing 时,该值为 -1。当开始 rehashing 时,该值会被设置为 0,并随着 rehashing 过程的进行逐渐增加,直到 rehashing 完成,此时再次将该值设置为 -1。

iterators:这是正在对字典进行迭代的迭代器的数量。这个计数有助于管理对字典的迭代,确保即使在 rehashing 过程中也能安全地进行迭代操作。有活跃的迭代器时,可能会暂停 rehashing 过程,以保证迭代器的一致性和准确性。

三、Dictht结构

在这里插入图片描述

/* This is our hash table structure. Every dictionary has two of this as we* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {dictEntry **table;      // HashTable数组unsigned long size;     // HashTable的大小unsigned long sizemask; // HashTable大小掩码,总是等于size - 1, 通常用来计算索引unsigned long used;     // 已经使用的节点数,实际上就是HashTable中已经存在的dictEntry数量
} dictht;

Redis的字典使用HashTable作为底层实现,一个HashTable中可以保存多个哈希表结点(dictEntry), 而每个dictEntry中就保存着字典中的一个键值对, table属性就是一个数组, 数组中每个元素的类型都是指向dictEntry的指针,而size属性便是table数组的长度, sizemask总是等于size - 1, 用于计算索引信息, used属性记录当前HashTable中dictEntry的总数量

table:这是一个数组,具体类型是指向字典条目(dictEntry)指针的数组。每一个 dictEntry 包含了键值对信息。这个 table 是哈希表的本质存储结构,实际的数据(键值对)都存储在这里。

size:这个成员表示哈希表中 table 数组的大小,也就是可以容纳的 dictEntry 数目。它总是2的幂次,这是为了使用位掩码(sizemask)与运算来替代取模运算,提升计算效率。

sizemask:它是与 size 成员配合使用的位掩码。它总是等于 size - 1。当计算一个键的哈希值来确定其在 table 数组中的位置时,用哈希值对 size 取模,等价于与 sizemask 进行按位与运算。后者由于只涉及二进制位运算,因此效率更高。

used:代表哈希表中已有的元素数量,即实际已经使用的 dictEntry 数目。这个数值在添加或删除键值对时会相应地增加或减少。

四、DictEntry结构

在这里插入图片描述

struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;     /* Next entry in the same hash bucket. */
};
typedef struct {void *key;dictEntry *next;
} dictEntryNoValue;

dictEntry是Dictht中结点的表现形式, 每个dictEntry都保存着一个键值对, key属性指向键值对的键对象, 而v属性则保存着键值对的值, Redis采用了联合体来定义v, 使键值对的值既可以存储一个指针, 也可以存储有符号/无符号整形数据,甚至可以存储浮点形数据, Redis使用联合体的形式来存储键值对的值可以让内存使用更加精细灵活, 另外, 既然是HashTable, 不可避免会发生两个键不同但是计算出来存放索引相同的情况, 为了解决Hash冲突的问题, dictEntry还有一个next属性, 用来指向与当前dictEntry在同一个索引的下一个dictEntry.

五、核心特性

哈希算法

Redis计算哈希值和索引值方法如下:

 #1、使用字典设置的哈希函数,计算键 key 的哈希值hash = dict->type->hashFunction(key);#2、使用哈希表的sizemask属性和第一步得到的哈希值,计算索引值index = hash & dict->ht[x].sizemask;

解决哈希冲突

当两个或更多的键被哈希到同一位置时(即发生哈希冲突),Redis 通过链地址法来解决冲突,即在这个位置维护一个链表,所有哈希到这个位置的键值对都会被加入到这个链表中。

自动扩容和缩容

可以预见的是,随着我们不断的对HashTable进行操作,可能会发生以下两种情况:

  • 不断的向HashTable中添加数据,HashTable中每个索引上的dictEntry数量会越来越多,也就是单链表会越来越长,这会十分影响字典的查询效率(最坏的场景可能要把整个单链表遍历完毕才能确定一个Key对应的dictEntry是否存在), 而Redis通常被当做缓存,这种低性能的场景是不被容许的.

  • 向一个本身已经十分巨大的HashTable执行删除节点的操作,由于原先这个HashTable的size很大(也就是说table数组十分巨大,我们假设size为M), 但是执行了大量的删除操作之后,table数组中很多元素指向了NULL(由于对应的索引上已经没有任何dictEntry, 相当于一个空的单链表), HashTable中剩余结点我们假设为N,这时M远大于N,也就是说之上table数组中至少有M - N个元素指向了NULL,这是对内存空间的巨大浪费,而Redis是内存型数据库,这种浪费内存的场景也是不被容许的.

针对以上两种场景,为了让HashTable的负载因子(HashTable中所有dictEntry的数量/HashTable的size值)维持在一个合理的范围内,Redis在HashTable保存的dictEntry数量太多或者太少的时候,会对HashTable的大小进行扩展或者收缩,在没有执行Rehash操作时,字典的所有数据都存储在ht[0]所指向的HashTable中,而在Rehash操作过程中,Redis会创建一个新的HashTable, 并且令ht[1]指向它,然后逐步的将ht[0]指向的HashTable的数据迁移到ht[1]上来

判断扩展HashTable的逻辑

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{/* Incremental rehashing already in progress. Return. */if (dictIsRehashing(d)) return DICT_OK;/* If the hash table is empty expand it to the initial size. */if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);/* If we reached the 1:1 ratio, and we are allowed to resize the hash* table (global setting) or we should avoid it but the ratio between* elements/buckets is over the "safe" threshold, we resize doubling* the number of buckets. */if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)){return dictExpand(d, d->ht[0].used*2);}return DICT_OK;
}

每次获取一个Key的索引信息时,都会调用上述的_dictExpandIfNeeded(dict *d)方法判断是否需要对当前HashTable执行扩展操作,满足下列任意条件之一,便会执行扩展操作:

  • 当前ht[0]所指向的HashTable大小为0
  • 服务器目前没有执行BGSAVE或者BGREWRITEAOF操作,并且HashTable的负载因子大于等于1(d->ht[0].used >= d->ht[0].size)
  • 服务器目前正在执行BGSAVE或者BGREWRITEAOF操作,并且HashTable的负载因子大于5(dict_force_resize_ratio = 5)

判断收缩HashTable的逻辑

int htNeedsResize(dict *dict) {long long size, used;size = dictSlots(dict);used = dictSize(dict);return (size > DICT_HT_INITIAL_SIZE &&(used*100/size < HASHTABLE_MIN_FILL));
}/* Resize the table to the minimal size that contains all the elements,
* but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize(dict *d)
{int minimal;if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;minimal = d->ht[0].used;if (minimal < DICT_HT_INITIAL_SIZE)minimal = DICT_HT_INITIAL_SIZE;return dictExpand(d, minimal);
}

Redis会定期的检查数据库字典HashTable的状态,当HashTable的负载因子小于0.1时,会自动的对HashTable执行收缩操作

rehash过程

  • 分配空间:为ht[1]指向的HashTable分配空间, 分配空间的大小取决于要执行的操作,以及ht[0]所指向HashTable中dictEntry结点的数量, 也就是ht[0].used中记录的值:
    • 如果当前执行的是扩展操作,那么新HashTable的大小为第一个大于等于2 * ht[0].used的2的n次方幂
    • 如果当前执行的是收缩操作,那么新HashTable的大小为第一个大于等于ht[0].used的2的n次方幂
  • 渐进式rehash:将ht[0]所指向HashTable中的所有dictEntry节点都迁移到ht[1]所指向的新HashTable上(由于两个HashTable的size不同,所以在迁移过程中要重新计算dictEntry的索引,这也就是rehash的关键所在)
  • 迁移完成:当迁移完成之后,ht[0]所指向的HashTable中已经没有任何节点,释放该HashTable, 并且令ht[0]指向迁入节点的新HashTable, 最后为ht[1]创建一个空白的HashTable,为下一次rehash做准备

在这里插入图片描述
说明:可以看到当前rehashidx指向ht[0]的索引2,这说明ht[0][0, rehashidx - 1]对应buckets上的dictEntry都已经迁移完毕,另外我们发现正在执行渐进式rehash字典中的数据一部分在ht[0]中,而另一部分在ht[1]中,所以在渐进式rehash执行期间,字典的删除,查找以及更新操作,都会在两个HashTable上执行(先尝试在ht[0]上执行操作,如果没有成功,则再尝试在ht[1]上进行操作),而在渐进式rehash执行期间,如果我们需要往字典中添加新的结点,则会一律添加到ht[1]上,这样可以保证ht[0]上的结点只减不增(也就是已经迁移过的buckets不会再出现新的结点)

渐进式rehash

为了避免rehash过程阻塞服务器,Redis采用渐进式rehash策略。在进行rehash期间,所有的读写操作都会同时在ht[0]ht[1]上进行,并逐步将ht[0]上的键值对迁移到ht[1]

rehash触发条件

  • 负载因子过高(扩容):
    • 当前ht[0]所指向的HashTable大小为0
    • 服务器目前没有执行BGSAVE或者BGREWRITEAOF操作,并且HashTable的负载因子大于等于1(d->ht[0].used >= d->ht[0].size)
    • 服务器目前正在执行BGSAVE或者BGREWRITEAOF操作,并且HashTable的负载因子大于5(dict_force_resize_ratio = 5)
  • 负载因子过低(缩容):
    • Redis会定期的检查数据库字典HashTable的状态,当HashTable的负载因子小于0.1时,会自动的对HashTable执行收缩操作

Dict优缺点

Dict 提供了快速的键值对查找和插入性能,能高效地支持数据的增删改查操作;然而,在内存使用上它可能不如一些更紧凑的数据结构高效,尤其是在存储大量小对象时,还有当哈希表发生扩容或收缩时可能会有短暂的性能下降。

参考 redis底层数据结构-Dict

这篇关于Redis底层数据结构之Dict的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/930612

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表(Hash Table)是一种数据结构,它通过将键(Key)映射到值(Value)的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希

Redis中使用布隆过滤器解决缓存穿透问题

一、缓存穿透(失效)问题 缓存穿透是指查询一个一定不存在的数据,由于缓存中没有命中,会去数据库中查询,而数据库中也没有该数据,并且每次查询都不会命中缓存,从而每次请求都直接打到了数据库上,这会给数据库带来巨大压力。 二、布隆过滤器原理 布隆过滤器(Bloom Filter)是一种空间效率很高的随机数据结构,它利用多个不同的哈希函数将一个元素映射到一个位数组中的多个位置,并将这些位置的值置

Lua 脚本在 Redis 中执行时的原子性以及与redis的事务的区别

在 Redis 中,Lua 脚本具有原子性是因为 Redis 保证在执行脚本时,脚本中的所有操作都会被当作一个不可分割的整体。具体来说,Redis 使用单线程的执行模型来处理命令,因此当 Lua 脚本在 Redis 中执行时,不会有其他命令打断脚本的执行过程。脚本中的所有操作都将连续执行,直到脚本执行完成后,Redis 才会继续处理其他客户端的请求。 Lua 脚本在 Redis 中原子性的原因

TL-Tomcat中长连接的底层源码原理实现

长连接:浏览器告诉tomcat不要将请求关掉。  如果不是长连接,tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(