文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Redis内部数据结构Dict的实现方法

2024-04-02 19:55

关注

我们平时用Redis的时候,只是了解到了它对外的一些结构,如:string、list、set、hash、zset,但是我们却很少能了解到Redis内部用的存储结构,小编将在这篇文章和大家秀一下Redis中的一个内部结构——dict。

一、dict是什么

不知道大家在用Redis的时候有没有注意到,我们在使用大多数Redis命令的时候,都会让你输入一个key,后面才会让你输入具体的值。

我们本篇文章所述的dict在Redis中最主要的作用就是用于维护Redis数据库中所有Key、value映射的数据结构,也就是我们在输入set、zadd等命令时输入的key与后面值的映射。321,上代码。代码来源(dict.h)。 如下代码所示,dict结构体里面有一个dictht 数组,dictht 里面的dictEntry 就是具体存放key、value映射关系的。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
typedef struct dictht {
    dictEntry **table;
    unsigned long size; //  hashtable 容量
    unsigned long sizemask;  // size -1
    unsigned long used;  // hashtable 元素个数   used / size =1
} dictht;
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];// ht[0] , ht[1] =null
    long rehashidx; 
    unsigned long iterators; 
} dict;

小贴纸:dictEntry 中用到了union联合体这种结构。也就是多个变量的结构同时使用一块内存区域,区域的取值大小为该结构中长度最大的变量的值。这有利于减少内存碎片,提高内存利用率,在Java中的压缩指针技术就用到了联合体。

二、dict数据结构

1.结构梳理

我们仔细看上面代码中的结构,小编可以直接告诉你,其实它就是一个哈希表结构,在Java中相当于一个HashMap,因为Redis需要保证快速响应,所以选择哈希表作为存储结构是一个不错的决定。我们这里只一起了解结构中存具体数据的部分。

小贴纸:Redis中的渐进式扩容,采用的是在内存中放置两个哈希表结构,无需扩容时,使用的是哈希表0,在扩容期间,将扩容标识设置为true,当有新数据进来的时候,发现正在扩容,就会在将新数据直接放入哈希表1。而表0中的数据会在每次有请求命令并且请求的数据在表0中时,将请求命令涉及到的数据直接挂到表1上。 在扩容期间如果执行查找命令会查找表0+表1的数据。

当然,Redis如果一直不执行命令的话。它也会有一个后台定时任务,对字典进行主动搬迁,它不会对未完成的事置之不理

// 服务器定时任务
void databaseCron() {
    ...
    if (server.activerehashing) {
        for (j = 0; j < dbs_per_call; j++) {
            int work_done = incrementallyRehash(rehash_db);
            if (work_done) {
                
                break;
            } else {
                
                rehash_db++;
                rehash_db %= server.dbnum;
            }
        }
    }
}

2. 扩容条件


static int _dictExpandIfNeeded(dict *d)
{
    
    if (dictIsRehashing(d)) return DICT_OK;

    
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    
    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;
}

3. 缩容条件

既然有扩容,当前就有缩容,要不占那么大内存不是浪费吗?

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));
}

dict结构的实现相对来说比较简单,本文就介绍到这。

到此这篇关于Redis内部数据结构Dict的实现方法的文章就介绍到这了,更多相关redis dict数据结构内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯