【Redis】基础数据结构-字典

这篇具有很好参考价值的文章主要介绍了【Redis】基础数据结构-字典。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Redis 字典

基本语法

字典是Redis中的一种数据结构,底层使用哈希表实现,一个哈希表中可以存储多个键值对,它的语法如下,其中KEY为键,field和value为值(也是一个键值对):

HSET key field value

根据Key和field获取value:

HGET key field

哈希表

数据结构
dictht

dictht是哈希表的数据结构定义:

  • table:哈希表数组,数组中的元素是dictEntry类型的
  • size:哈希表数组的大小
  • sizemask:哈希表大小掩码,一般等于size-1
  • used:已有节点的数量(存储键值对的数量)
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

【Redis】基础数据结构-字典,Redis,redis,数据结构,数据库

dictEntry

dictEntry是哈希表节点的结构定义:

  • key:键值对中的键
  • v:键值对中的值
  • next:由于会出现哈希冲突,所以next是指向下一个节点的指针
typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next; // 指向下一个节点的指针
} dictEntry;

【Redis】基础数据结构-字典,Redis,redis,数据结构,数据库

dict

dict是Redis中字典的结构定义:

  • type:指向dictType的指针
  • privdata
  • ht[2]:一个dictht类型的数组,数组大小为2,保存了两个哈希表,rehash时使用
  • rehashidx:记录了当前rehash的进度
  • pauserehash:rehash暂停标记,大于0表示没有进行rehash
typedef struct dict {
    dictType *type; // 
    void *privdata; // 私有数据
    dictht ht[2]; // 保存了两个哈希表
    long rehashidx; // rehash的进度标记
    int16_t pauserehash; 
} dict;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;

【Redis】基础数据结构-字典,Redis,redis,数据结构,数据库

哈希冲突

一个键值对放入哈希表的时候,会根据key的值,计算一个hash值,然后根据hash值与哈希表大小掩码做与运算得到一个索引值,索引值决定元素放入哪个哈希桶中(落入哈希表数组哪个索引位置处)。

 // 计算hash值
 hash = dictHashKey(d,key)
 // 计算索引
 idx = hash & d->ht[table].sizemask;

在进行哈希计算的时候,不可避免会出现哈希冲突,出现哈希冲突的时候,Redis采用链式哈希解决冲突,也就是落入同一个桶中的元素,使用链表将这些冲突的元素链起来(dictEntry中的next指针)。

【Redis】基础数据结构-字典,Redis,redis,数据结构,数据库

rehash

由于Redis采用链式哈希解决冲突,那么在冲突频繁的场景下,链表会变得越来越长,这种情况下查找效率是比较低下的,需要遍历链表对比KEY的值来获取数据,为了处理效率低下的问题,需要对哈希表进行扩容,扩容的过程称为rehash。

在dict结构替中ht保存了两个哈希表,ht[0]用于数据正常的增删改查,ht[1]用于rehash:

(1)正常情况下,所有的增删改查操作都在ht[0]中进行;

(2)需要进行rehash时,会使用ht[1]建立新的哈希表,并将ht[0]中的数据迁移到ht[1]中;

(3)迁移完成后,ht[0]的空间被释放,然后将ht[1]地址赋给ht[0],ht[1]的大小被设为0,ht[0]重新接收正常的请求,回到了第(1)步的状态;

rehash的触发条件
/* 判断是否需要扩容 */
static int _dictExpandIfNeeded(dict *d)
{
    /* 如果已经处于rehash状态中直接返回 */
    if (dictIsRehashing(d)) return DICT_OK;

    /* 如果ht[0]的大小为0,意味着哈希表为空,此时做初始化操作 */
    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) &&
        dictTypeExpandAllowed(d))
    {   
        // 进行扩容
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

/* 由于扩容需要分配内存,这里检查字典类型分配是否被允许*/
static int dictTypeExpandAllowed(dict *d) {
    if (d->type->expandAllowed == NULL) return 1;
    return d->type->expandAllowed(
                    _dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),
                    (double)d->ht[0].used / d->ht[0].size);
}

d->ht[0].used/d->ht[0].size : 节点数量与哈希表数组大小的比例,称作负载因子

dict_force_resize_ratio 的默认值是 5。

  1. ht[0]的大小为0,此时哈希表是空的,相当于对哈希表做一个初始化的操作。
  2. 如果哈希表中存储的节点数量大于或者等于哈希表数组的大小,并且哈希表可以扩容或者负载因子大于dict_force_resize_ratio(默认值为5),根据字典的类型判断允许分配内存,满足这三个条件开始扩容。

dict_can_resize

dict_can_resize用来判断哈希表是否可以扩容,有两种状态,值分别为1和0,1代表可以扩容,0代表禁用扩容:

void dictEnableResize(void) {
    dict_can_resize = 1;
}

void dictDisableResize(void) {
    dict_can_resize = 0;
}

updateDictResizePolicy中对dict_can_resize的状态进行了控制,当前没有RDB子进程并且也没有AOF子进程时设置dict_can_resize状态为可扩容:


void updateDictResizePolicy(void) {
    // 没有RDB子进程并且也没有AOF子进程
    if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
        dictEnableResize(); // 启用扩容
    else
        dictDisableResize(); // 禁用扩容
}
扩容大小

从代码中可以看到,扩容后哈希表数组的大小为已经存储的节点数量+1:

// 进行扩容
return dictExpand(d, d->ht[0].used + 1);

一些旧版本中扩容后的大小为已存储节点数量的2倍:

dictExpand(d, d->ht[0].used*2);
渐进式hash

当哈希表存储节点内容比较多时,需要将原来的节点一个一个拷贝到新的哈希表中,此时Redis主线程无法执行其他请求,造成阻塞,影响性能,为了解决这个问题,引入了渐进式hash。

渐进式hash并不会一次把旧节点全部拷贝到新的哈希表中,而是分多次渐进式的完成拷贝,其中rehashidx记录了迁移进度,每一次迁移的过程中会更新rehashidx的值,下一次进行数据迁移的时候,从rehashidx的位置开始迁移,在dictRehash中可以看到迁移的处理:

  1. 方法传入了一个参数n,代表本次需要迁移几个哈希桶
  2. 根据需要迁移哈希桶的数量,循环处理每一个哈希桶:
    • 如果当前哈希桶中为空,继续下一个桶的处理rehashidx++
    • 如果当前哈希桶不为空,将当前桶中的所有节点迁移到新的哈希表中,然后更新rehashidx的值继续处理下一个桶
  3. 如果已经处理够了n个桶,或者哈希表的所有数据已经迁移完毕,则结束迁移。
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;
    // 循环处理每一个哈希桶,n为需要迁移哈希桶的数量
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        // 如果当前哈希桶没有存储数据
        while(d->ht[0].table[d->rehashidx] == NULL) {
            // rehashidx的值是哈希表数组的某个索引值(指向了某个哈希桶),意味着当前迁移到数组的哪个索引位置处
            d->rehashidx++; // 继续下一个桶
            if (--empty_visits == 0) return 1;
        }
       
        de = d->ht[0].table[d->rehashidx];
        // 如果当前的哈希桶中存储着数据,将哈希桶存储的所有数据迁移到新的哈希表中
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        // rehashidx,继续迁移下一个哈希桶
        d->rehashidx++;
    }

    /* 判断ht[0]的节点是否迁移完成 */
    if (d->ht[0].used == 0) {
        // 释放ht[0]的空间
        zfree(d->ht[0].table);
        // 将ht[0]指向ht[1]
        d->ht[0] = d->ht[1];
        // 重置ht[1]的大小为0
        _dictReset(&d->ht[1]);
        // 设置rehashidx,-1代表rehash结束
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

_dictRehashStep

_dictRehashStep中可以看到调用dictRehash时,每次迁移哈希桶的数量为1:

static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}

总结

  1. Redis字典底层使用哈希表实现。

  2. 键值对放入哈希表的时候,会根据key的值,计算hash值,出现哈希冲突的时候,Redis采用链式哈希解决冲突,使用链表将这些冲突的元素链起来。

  3. 由于Redis采用链式哈希解决冲突,那么在冲突频繁的场景下,链表会变得越来越长,这种情况下查找效率是比较低下的,需要遍历链表对比KEY的值来获取数据,为了处理效率低下的问题,需要对哈希表进行扩容,扩容的过程称为rehash。

  4. 当哈希表存储节点内容比较多时,进行rehas的时候主线程无法执行其他请求,造成阻塞,影响性能,所以采用了渐进式hash,渐进式hash并不会一次把旧节点全部拷贝到新的哈希表中,而是分多次渐进式的完成拷贝。

参考

黄健宏《Redis设计与实现》

极客时间 - Redis源码剖析与实战(蒋德钧)

美团针对Redis Rehash机制的探索和实践

Redis版本:redis-6.2.5文章来源地址https://www.toymoban.com/news/detail-729191.html

到了这里,关于【Redis】基础数据结构-字典的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Python】基础数据结构:列表——元组——字典——集合

    Python提供了多种内置的数据结构,包括列表( List )、元组( Tuple )和字典( Dictionary )。这些数据结构在Python编程中都有着广泛的应用,但它们各有特点和适用场景。 列表是一种有序的集合,可以随时添加和删除其中的元素。列表是可变的,也就是说,你可以修改列表的

    2024年02月10日
    浏览(51)
  • Python-基础篇-数据结构-列表、元组、字典、集合

    列表、元组 字典、集合 💬正如在现实世界中一样,直到我们拥有足够多的东西,才迫切需要一个储存东西的容器,这也是我坚持把数据结构放在最后面的原因一一直到你掌握足够多的技能,可以创造更多的数据,你才会重视数据结构的作用。这些储存大量数据的容器,在

    2024年01月21日
    浏览(129)
  • Redis学习路线(2)—— Redis的数据结构

    一、Redis的数据结构 Redis是一个Key-Value的数据库,key一般是String类型,不过Value的类型却有很多: String: Hello World Hash: {name: \\\"jack\\\", age: 21} List: [A - B - C - C] Set: {A, B, C} SortedSet: {A: 1, B: 2, C: 3} GEO: {A: (120.3, 30.5)} BitMap: 0110110101110101011 HyperLog: 0110110101110101011 由于Redis对数据

    2024年02月15日
    浏览(43)
  • 【Redis】Redis中的数据结构和内部编码

    type命令实际返回的就是当前键的数据结构类型,它们分别是:string(字符串)、list(列表)、hash(哈希)、set(集合)、zset(有序集合),但这些只是Redis对外的数据结构, 实际上Redis针对每种数据结构都有⾃⼰的底层内部编码实现,⽽且是多种实现,这样Redis会在合适的

    2024年02月07日
    浏览(42)
  • redis1之安装redis,启动,常用数据结构

      目录 redis安装与启动、常见数据结构 启动  Redis客户端 数据结构与常见的命令  redis的通用命令  String类型的用法 Hash命令的用法  List命令  Set命令  SortedSet类型用法 1,在linux上安装上gcc的依赖,我这里是centos7.6,gcc是4.5 我们在LInux上查看一下我们的系统信息  我这里安装

    2024年02月06日
    浏览(48)
  • Redis的数据结构

    Redis是一款高性能的键值存储数据库,支持多种数据结构。在Redis中,数据结构是指在Redis中存储和操作数据的方式。Redis支持的数据结构包括字符串、哈希表、列表、集合和有序集合。 字符串是Redis中最基本的数据结构,可以存储任何类型的数据,包括数字、文本和二进制数

    2024年02月09日
    浏览(40)
  • redis核心数据结构

    redis下载地址:Download | Redis linux进入redis目录首先使用make命令进行c++的编译,修改redis.conf文件: 启动退出相关命令: redis五种数据结构图: 1、常用命令 2、应用场景 1)、单值缓存 2)、对象缓存 3)、分布式锁  4)、计数器 5) 、计数器 6) 、分布式系统全局序列号 1、

    2024年02月09日
    浏览(40)
  • Redis底层数据结构

    SDS全称是Simple Dynamic String,具有如下显著的特点: 常数复杂度获取字符串长度:C语言获取一个字符串的长度需要遍历整个字符串时间复杂度为O(N),而SDS在属性len中记录了字符串长度,获取字符串长度的时间复杂度为O(1)。 杜绝缓冲区溢出:C字符串在执行拼接字符串时,如果

    2024年02月13日
    浏览(46)
  • Redis数据结构简介

    对redis来说,所有的key(键)都是字符串。     1.String 字符串类型 是redis中最基本的数据类型,一个key对应一个value。   String类型是二进制安全的,意思是 redis 的 string 可以包含任何数据。如数字,字符串,jpg图片或者序列化的对象。   使用:get 、 set 、 del 、 incr、 decr 等

    2024年02月07日
    浏览(45)
  • Redis - 底层数据结构

    Redis 的底层数据结构主要以下几种: SDS(Simple Dynamic String, 简单动态字符串) ZipList(压缩列表) QuickList(快表) Dict(字典) IntSet(整数集合) ZSkipList(跳跃表) 在 Redis 中,并不会直接使用 C 语言自带的字符串结构作为实际的存储结构,而只是将字符串作为字面量使用,大多数情况使用自

    2023年04月12日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包