Code前端首页关于Code前端联系我们

深入阐述Redis Hash实现原理(哈希表)

terry 2年前 (2023-09-27) 阅读数 127 #数据结构与算法

1。什么是

Redis Hash(哈希表)是一种字段值对(键值对)的集合,类似于Python中的字典和Java中HashMap中的字典。字段对应一个值。您可以使用数组以 O(1) 的时间复杂度查找相关数组。您还可以使用字段来更新或删除键值对。

Redis 哈希表由数组 + 链表组成。每个数组元素占用的槽称为哈希桶。当存在哈希冲突时,就会发生。这个桶下面挂着链表,用“拉链法”解决哈希冲突问题

简单来说,就是使用哈希计算将键均匀映射到哈希表。 Redis Hash(散列表)实现原理深度图解图2-18

图2-18

2.动动脑筋

Hash Hash数据类型实际上有两种基本的存储数据结构。

  1. 听写结构。
  2. 7.0版本之前使用ziplist,然后用listpack替换。

通常采用dict数据结构来存储数据,每个字段值对代表一个dictEntry节点进行存储。

只有同时满足以下两个条件时,才会使用listpack数据结构(7.0版本之前使用ziplist)来替代dict存储,键值对按字段优先、值排序最后,紧密相连的方法是将每个键值对放在列表的末尾

  • 每个键值对中字段和值的位大小小于hash-max-listpack-value配置的值(默认64)。
  • 字段值对 键值对的数量小于hash-max-listpack-entries配置的值(默认512)。

每次将数据写入哈希表时,中的函数hashTypeConvertListpack()。 t_hash.c判断底层结构是否需要转换。

当插入和修改的数据不满足上述两个条件时,哈希表的基本存储结构转换为结构dict。需要注意的是,不能从字典退化为列表

虽然无法使用listpack来操作O(1)时间复杂度的数据,但是使用listpack可以大大减少内存占用,而且数据量比较小,所以性能上并没有太大的差别。

为了隐藏顶层的哈希表,并在底层使用不同的数据结构存储方式,抽象了一个hashTypeIterator来实现哈希表的查询。

数据类型Hash使用listpack存储数据时的情况,如图2-19所示。 Redis Hash(散列表)实现原理深度图解图2-19

图2-19

listpack数据结构之前已经介绍过。接下来,我将向您展示听写的样子。

Redis 数据库是一个全局哈希表。通常,我只会使用哈希表ht_table[0]。图2-20是一个没有中断的字典。 Redis Hash(散列表)实现原理深度图解图2-20

图2-20

dict字典在源代码中由dict结构dict.h表示。

struct dict {
    dictType *type;
  // 真正存储数据的地方,分别存放两个指针
    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx;

    int16_t pauserehash;
    signed char ht_size_exp[2];
};
  • dictType *type,一个存储函数的结构体,定义了一些函数指针。通过设置自定义函数,字典键和值可用于存储任何类型的数据。
  • 重点关注dictEntry **ht_table[2],它存储了两个辅助dictEntry指针,指针指向dictEntry指针数组。
  • ht_used[2],记录每个哈希表使用了多少个槽(例如字段长度为32,则使用12个)。
  • rehasidx,用于指示是否进行rehashing操作,-1表示不进行rehashing操作。如果正在执行 rehash,则其值是正在执行当前 rehash 操作的哈希表 ht_table[0] dictEntry 数组的索引。
  • pauserehash 表示 rehash 状态。当大于0时,表示暂停重试。如果小于0,则表示发生了错误。

继续观看dictEntry。数组中的每个元素都是dictEntry类型,它存储键值对,代表一个字典节点。指针

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
  • *key指向键值对中的一个键,它实际上指向一个SDS实例。
  • v 是表示键值对中的值的联接。一次只有一个字段具有值。使用union的目的是为了节省内存。
    • *val 如果值是非数字类型,则使用该指针存储。
    • uint64_t u64,当值为无符号整数时使用此字段进行存储。
    • int64_t s64 如果该值为有符号整数,则使用此字段来存储它。
    • double d,该值为使用该字段存储的浮点数。
  • *next指向下一个节点指针。当哈希表数据增加时,不同key得到的哈希值可以相同,也就是说多个key对应一个哈希段。这就是哈希值。希腊冲突。 Redis 使用 zips 方法,该方法使用链表将数据链接在一起。

MySQL:“为什么 ht_table[2] 存储两个指向哈希表的指针?一个哈希表还不够吗?”

默认情况下,ht_table 用于读取[0] 写入数据时,当哈希表中的数据越来越多,哈希冲突严重时,哈希段的链表会比较长,这会导致查询性能下降。

我找到了一种快速且牢不可破的方法。当哈希表存储的键值对过多或过少时,就需要通过重新散列(rehashing)来扩大或缩小哈希表。

扩展和缩减

  1. 为了高性能和减少哈希冲突,我将创建一个哈希表ht_table[1],其大小等于[used 2] ,即,每次扩容时,都会在哈希表ht_table [0]的基础上创建一个新的哈希表表ht_table [1],使已用空间增加一倍。相反,如果是收缩操作,则根据 ht_table [0] 使用空间的两倍来创建新的哈希表。
  2. 重新计算键值对的哈希值,获取键值对所在段在新哈希表ht_table [1]中的位置,并将键值对迁移到新的哈希表。
  3. 所有键值对迁移完成后,修改指针并释放空间。具体来说,指针ht_table[0]指向扩展后的哈希表,恢复小哈希表原来的内存空间。指针ht_table[1]指向NULL。为下一次扩张或收缩做好准备。 ?这意味着当前没有 RDB 线程和 AOF 重写线程在运行。这两个操作比较容易影响性能,不扩容就会火上浇油。
  4. 执行命令BGSAVEBGREWRITEAOF且冲突严重时负载因子大于等于5。(如果太大或等于5。不会运行,查询效率会太慢)。

负载因子=哈希表存储空间dicInput节点数/哈希表桶数。理想情况下,每个哈希段中存储一个 dictEntry 节点,负载因子 = 1。

MySQL:“需要迁移大量数据。重新处理操作不会长时间阻塞主线程吗?时间?”

为了避免主线程阻塞带来的性能问题,我没有一次性迁移所有key,而是将迁移操作拆分到每个请求中多次,以避免集中rehash造成的长期阻塞。这种方法称为渐进式rehash

在进行渐进式rehash时,dict会使用两个哈希表ht_table[0]ht_table[1],具体步骤为rehashing 如下:

  1. rehashidx 设置为 0,表示刷新开始执行。
  2. 在刷新期间,每当服务器处理客户端执行添加、搜索、删除操作时,或者对听写哈希表进行更新操作,除了执行指定的操作外,还会检查当前的dict是否处于re-state,如果是,则会对该segment的所有键值对进行哈希Rehash列表ht_table[0]中索引位置为rehashidx的链表到哈希表到哈希表。这个hash当扇区数据迁移完成后,rehashidx加1,表示接下来要迁移的扇区的位置。
  3. 当所有键值对迁移完毕后,将rehashidx设置为-1,表示重新处理操作已完成。 ?如果一个哈希表没有找到,则到另一个哈希表中查找。但是,追加操作只会在新的哈希表上执行。

    MySQL:“如果请求少的话,用两个哈希表用不了多久。”

    好问题,Redis Server 在初始化时,会注册并定期执行一个时间事件。

    serverCron函数除了重新哈希之外还主要处理以下任务。

    • 过期的密钥将被删除。
    • 监控服务启动状态。
    • 更新统计数据。
    • 渐进式重新哈希。
    • 运行 BGSAVE / AOF 覆盖并停止子进程。
    • 处理客户时间限制。
    • ……

    是不是很贴心,既能保证性能,又能防止浪费内存。好了,今天的基本哈希表数据结构的实现原理就到此为止。

版权声明

本文仅代表作者观点,不代表Code前端网立场。
本文系作者Code前端网发表,如需转载,请注明页面地址。

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

热门