Redis源码剖析与实战
蒋德钧
中科院计算所副研究员
新⼈⾸单¥59.9
1642 人已学习
课程目录
已更新 4 讲 / 共 33 讲
0/4登录后,你可以任选4讲全文学习。
课前导读 (2讲)
开篇词 | 阅读Redis源码能给你带来什么?
免费
01 | 带你快速攻略Redis源码的整体架构
数据结构模块 (2讲)
02 | 键值对中字符串的实现,用char*还是结构体?
03 | 如何实现一个性能优异的Hash表?
Redis源码剖析与实战
15
15
1.0x
00:00/00:00
登录|注册

03 | 如何实现一个性能优异的Hash表?

你好,我是蒋德钧。今天,我们来聊聊 Redis 中的 Hash。
我们知道,Hash 表是一种非常关键的数据结构,在计算机系统中发挥着重要作用。比如在 Memcached 中,Hash 表被用来索引数据;在数据库系统中,Hash 表被用来辅助 SQL 查询。而对于 Redis 键值数据库来说,Hash 表既是键值对中的一种值类型,同时,Redis 也使用一个全局 Hash 表来保存所有的键值对,从而既满足应用存取 Hash 结构数据需求,又能提供快速查询功能。
那么,Hash 表应用如此广泛的一个重要原因,就是从理论上来说,它能以 O(1) 的复杂度快速查询数据。Hash 表通过 Hash 函数的计算,就能定位数据在表中的位置,紧接着可以对数据进行操作,这就使得数据操作非常快速。
Hash 表这个结构也并不难理解,但是在实际应用 Hash 表时,当数据量不断增加,它的性能就经常会受到哈希冲突rehash 开销的影响。而这两个问题的核心,其实都来自于 Hash 表要保存的数据量,超过了当前 Hash 表能容纳的数据量。
那么要如何应对这两个问题呢?事实上,这也是在大厂面试中,面试官经常会考核的问题。所以你现在可以先想想,如果你在面试中遇到了这两个问题,你会怎么回答呢?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/1000字
划线
笔记
复制
该试读文章来自付费专栏《Redis源码剖析与实战》,如需阅读全部文章,
请订阅文章所属专栏新⼈⾸单¥59.9
立即订阅
登录 后留言

精选留言(1)

  • Kaito
    1、Redis 中的 dict 数据结构,采用「链式哈希」的方式存储,当哈希冲突严重时,会开辟一个新的哈希表,翻倍扩容,并采用「渐进式 rehash」的方式迁移数据

    2、所谓「渐进式 rehash」是指,把很大块迁移数据的开销,平摊到多次小的操作中,目的是降低主线程的性能影响

    3、Redis 中凡是需要 O(1) 时间获取 k-v 数据的场景,都使用了 dict 这个数据结构,也就是说 dict 是 Redis 中重中之重的「底层数据结构」

    4、dict 封装好了友好的「增删改查」API,并在适当时机「自动扩容、缩容」,这给上层数据类型(Hash/Set/Sorted Set)、全局哈希表的实现提供了非常大的便利

    5、例如,Redis 中每个 DB 存放数据的「全局哈希表、过期key」都用到了 dict:

    // server.h
    typedef struct redisDb {
        dict *dict; // 全局哈希表,数据键值对存在这
        dict *expires; // 过期 key + 过期时间 存在这
        ...
    }

    6、「全局哈希表」在触发渐进式 rehash 的情况有 2 个:

    - 增删改查哈希表时:每次迁移 1 个哈希桶(文章提到的 dict.c 中的 _dictRehashStep 函数)
    - 定时 rehash:如果 dict 一直没有操作,无法渐进式迁移数据,那主线程会默认每间隔 100ms 执行一次迁移操作。这里一次会以 100 个桶为基本单位迁移数据,并限制如果一次操作耗时超时 1ms 就结束本次任务,待下次再次触发迁移(文章没提到这个,详见 dict.c 的 dictRehashMilliseconds 函数)

    (注意:定时 rehash 只会迁移全局哈希表中的数据,不会定时迁移 Hash/Set/Sorted Set 下的哈希表的数据,这些哈希表只会在操作数据时做实时的渐进式 rehash)

    7、dict 在负载因子超过 1 时(used: bucket size >= 1),会触发 rehash。但如果 Redis 正在 RDB 或 AOF rewrite,为避免父进程大量写时复制,会暂时关闭触发 rehash。但这里有个例外,如果负载因子超过了 5(哈希冲突已非常严重),依旧会强制做 rehash(重点)

    8、dict 在 rehash 期间,查询旧哈希表找不到结果,还需要在新哈希表查询一次

    课后题:Hash 函数会影响 Hash 表的查询效率及哈希冲突情况,那么,你能从 Redis 的源码中,找到 Hash 表使用的是哪一种 Hash 函数吗?

    找到 dict.c 的 dictFind 函数,可以看到查询一个 key 在哈希表的位置时,调用了 dictHashKey 计算 key 的哈希值:

    dictEntry *dictFind(dict *d, const void *key) {
        // 计算 key 的哈希值
        h = dictHashKey(d, key);
        ...
    }

    继续跟代码可以看到 dictHashKey 调用了 struct dict 下 dictType 的 hashFunction 函数:

    // dict.h
    dictHashKey(d, key) (d)->type->hashFunction(key)

    而这个 hashFunction 是在初始化一个 dict 时,才会指定使用哪个哈希函数的。

    当 Redis Server 在启动时会创建「全局哈希表」:

    // 初始化 db 下的全局哈希表
    for (j = 0; j < server.dbnum; j++) {
        // dbDictType 中指定了哈希函数
        server.db[j].dict = dictCreate(&dbDictType,NULL);
        ...
    }

    这个 dbDictType struct 指定了具体的哈希函数,跟代码进去能看到,使用了 SipHash 算法,具体实现逻辑在 siphash.c。

    (SipHash 哈希算法是在 Redis 4.0 才开始使用的,3.0-4.0 使用的是 MurmurHash2 哈希算法,3.0 之前是 DJBX33A 哈希算法)
    2021-07-31
    4
    8
收起评论
1
返回
顶部