专栏首页chenchenchenredis中hash扩容过程

redis中hash扩容过程

数据结构

Redis一共支持5种数据结构,hash是其中的一种,在hash扩容的时候采用的是渐进式rehash的方式。要想深入理解渐进式rehash,首先要了解以下Redis中hash的数据结构。

哈希表节点

typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next; // 下一个节点
} dictEntry;

哈希表

/* 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; // 哈希表数组
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 掩码,计算索引值,size-1
    unsigned long used; // 哈希表已有节点的数量
} dictht;

字典

typedef struct dict {
    dictType *type; // 类型特定函数
    void *privdata; // 私有数据
    dictht ht[2]; // 哈希表
    // rehash索引
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} 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);
} dictType;

扩容

背景

redis字典(hash表)当数据越来越多的时候,就会发生扩容,也就是rehash

对比

java中的hashmap,当数据数量达到阈值的时候(0.75),就会发生rehash,hash表长度变为原来的二倍,将原hash表数据全部重新计算hash地址,重新分配位置,达到rehash目的

哈希算法原理

当向字典中添加一个元素时(假设此时 rehashidx = -1,也就是没有进行rehash),首先通过dict->type->hashFunction计算该元素的hash值,然后通过hash & dict->ht[x].sizemask计算哈希地址index。如果该元素对应的下标没有数据,则直接添加,否则采用链地址法添加到hash对应index元素的链表尾部。

rehash原理

字典中包含一个数据结构dictht的ht数组,一般情况下字典只是用ht[0]用来存储数据,ht[1]在rehash时使用。

随着操作的不断执行,哈希表中的元素会逐渐增加或者减少,为了让哈希表的负载因子维持在一个合理的范围内,程序需要对哈希表的大小进行相应的扩容和收缩。步骤如下:

为ht[1]哈希表分配空间。如果是扩容操作,ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂,如果是收缩操作,ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂

将保存在ht[0]中的所有键值对rehash到ht[1]:rehash指的是重新计算键的哈希值和索引值,然后将键值对放到ht[1]对应位置上

当ht[0]包含的所有键值对都迁移到ht[1]之后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备

渐进式rehash原理

在扩容和收缩的时候,如果哈希字典中有很多元素,一次性将这些键全部rehash到ht[1]的话,可能会导致服务器在一段时间内停止服务。所以,采用渐进式rehash的方式,详细步骤如下:

为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表

将rehashindex的值设置为0,表示rehash工作正式开始

在rehash期间,每次对字典执行增删改查操作是,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1],当rehash工作完成以后,rehashindex的值+1

随着字典操作的不断执行,最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1],这时将rehashindex的值设置为-1,表示rehash操作结束

渐进式rehash采用的是一种分而治之的方式,将rehash的操作分摊在每一个的访问中,避免集中式rehash而带来的庞大计算量。

需要注意的是在渐进式rehash的过程,如果有增删改查操作时,如果index大于rehashindex,访问ht[0],否则访问ht[1]

扩容过程

redis中的hash表采用的是渐进式hash的方式: 1、redis字典(hash表)底层有两个数组,还有一个rehashidx用来控制rehash

2、初始默认hash长度为4,当元素个数与hash表长度一致时,就发生扩容,hash长度变为原来的二倍

3、redis中的hash则是执行的单步rehash的过程:

每次的增删改查,rehashidx+1,然后执行对应原hash表rehashidx索引位置的rehash

步骤

为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表

将rehashindex的值设置为0,表示rehash工作正式开始

在rehash期间,每次对字典执行增删改查操作是,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1],当rehash工作完成以后,rehashindex的值+1

随着字典操作的不断执行,最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1],这时将rehashindex的值设置为-1,表示rehash操作结束

渐进式rehash采用的是一种分而治之的方式,将rehash的操作分摊在每一个的访问中,避免集中式rehash而带来的庞大计算量。

需要注意的是在渐进式rehash的过程,如果有增删改查操作时,如果index大于rehashindex,访问ht[0],否则访问ht[1]。

参考:

Redis中渐进式rehash:https://www.manongdao.com/article-2333291.html

redis中的hash扩容渐进式rehash过程https://blog.csdn.net/qq_38262266/article/details/107727116

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis 基本数据结构三:哈希

    几乎所有的编程语言都提供了哈希(hash)类型,例如 Java 中的 Map,python 中的字典,在Redis中,哈希类型是指键的值本身又是一个键值对结构,...

    CoderJed
  • 干货 | 携程Redis治理演进之路(二)

    本文为联合撰稿,作者团队包括:布莱德,携程技术专家;向晨,携程数据库专家;骋成,携程技术专家;小峰,携程高级软件工程师。

    携程技术
  • redis学习笔记(一)数据结构

    redis的快主要体现在我们可以根据键值对能以微妙级别的速度找到数据,并快速完成操作。

    虞大大
  • 细品Redis高性能数据结构之hash对象

    上一节讲Redis的高性能字符串结构SDS,今天我们来看一下redis的hash对象。

    居士
  • 细品redis的Scan和Keys命令

    抽象一点说,假设开始槽位的二进制数是 xxx,那么该槽位中的元素将被 rehash 到 0xxx 和 1xxx(xxx+8) 中。 如果字典长度由 16 位扩...

    居士
  • Redis 基础知识

    常用的包括**String、List、Hash、Set、Sorted Set**,不常用的包含GEO、Bitmap、HyperLogLog;底层数据结构包括简单...

    少羽大怪兽
  • redis:切片

    单台redis的管理内存能力是有限的,如果保存有海量的缓存数据,则一台redis无法操作

    许喜朝
  • 面试官:说说Redis的Hash底层 我:......(来自阅文的面试题)

    hello,各位小可爱们,又见面了。今天这篇文章来自去年面试阅文的面试题,结果被虐了。这一part不说了,下次专门开一篇,写下我面试被虐的名场面,尴尬的不行,全...

    陈琛
  • 面试官:说说Redis的Hash底层 我:......(来自阅文的面试题)

    hello,各位小可爱们,又见面了。今天这篇文章来自去年面试阅文的面试题,结果被虐了。这一part不说了,下次专门开一篇,写下我面试被虐的名场面,尴尬的不行,全...

    陈琛
  • 013.Redis Cluster架构原理

    Redis Cluster是Redis的分布式解决方案,在3.0版本正式推出,解决单master架构的内存、并发、流量等瓶颈,以达到负载均衡的目的。

    CoderJed
  • 你确定不来了解一下Redis中Hash的原理吗

    Hash 也可以用来存储用户信息,和 String 不同的是 Hash 可以对用户信息的每个字段单独存储,String 则需要序列化用户的所有字段后存储.并且 ...

    大数据真好玩
  • 美团针对Redis Rehash机制的探索和实践

    Squirrel(松鼠)是美团技术团队基于Redis Cluster打造的缓存系统。经过不断的迭代研发,目前已形成一整套自动化运维体系,涵盖一键运维集群、细粒度...

    美团技术团队
  • Redis基础「5种基本数据结构」

    Redis 是一个开源,高级的键值存储和一个适用的解决方案,用于构建高性能,可扩展的 Web 应用程序。Redis 也被作者戏称为 数据结构服务器 ,这意味着使...

    Java3y
  • 数据库如何做到平滑扩容

    为了增加db的并发能力,常见的方案就是对数据进行sharding,也就是常说的分库分表,这个需要在初期对数据规划有一个预期,从而预先分配出足够的库来处理。

    程序员小王
  • Redis 设计思路学习与总结

    下半年利用空余时间研究和分析了部分Redis源码,本文从网络模型、数据结构和内存管理、持久化和多机协作四个角度对redis的设计思路进行了分析,若有不正确之处,...

    云加社区
  • Redis学习系列四Hash(字典)

    Redis中的Hash字典相当于C#中的Hashtable,是一种无序字典,内存存储了很对的键值对,实现上和Hashtable一样,都是"数组+链表"二维结构,...

    郑小超.
  • Redis原理 -基础数据结构

    动态字符串,类似arraylist,当字符串长度消息1M时,扩容是加倍现有空间,超过1M,扩容时会多扩1M空间,字符串长度最大为512M

    王小明_HIT
  • 深入理解Redis的scan命令

    熟悉Redis的人都知道,它是单线程的。因此在使用一些时间复杂度为O(N)的命令时要非常谨慎。可能一不小心就会阻塞进程,导致Redis出现卡顿。

    Jackeyzhe
  • Redis中hash、set、zset的底层数据结构原理

    hash的底层存储有两种数据结构,一种是ziplist,另外一种是hashtable,这两种数据结构我们之前都有讲解,ziplist就是上文提到的结构,hash...

    用户2781897

扫码关注云+社区

领取腾讯云代金券