首页 > 数据库 >Redis的哈希表是如何扩容的?

Redis的哈希表是如何扩容的?

时间:2023-04-16 10:07:01浏览次数:38  
标签:扩容 rehash Redis ht 键值 表是 哈希 字典


文章目录

  • 一般面试回答
  • 哈希表结构
  • 字典数据结构
  • 解决哈希冲突
  • 扩容/缩容
  • 对字典的哈希表rehash步骤
  • 渐进式rehash
  • 渐进式rehash步骤
  • 相关问题

一般面试回答

redis 解决冲突的方法是使用链地址法,另外当容量不足的时候,则使用Rehash 进行扩容。
Rehash:
给哈希表 2 分配更大的空间,
例如是当前哈希表 1 大小的两倍;
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中;
释放哈希表 1 的空间。
渐进式rehash则是不一次性拷贝,当访问到某个数据时,再进行拷贝。

哈希表结构

Redis哈希表就是类似Java中HashMap。

Redis的哈希表是如何扩容的?_服务器


哈希表是由dictht结构体定义,table是一个数组,数组中每个元素是一个指向dictEntry结构的指针。

Redis的哈希表是如何扩容的?_服务器_02


dictEntry是哈希表的节点,每个节点保存着一个键值对key、value,value可以是一个指针、或者是一个unit64_t或int64_t整数。

next属性则是一个指向另一个哈希表节点的指针,形成一个链表,主要也是为了解决哈希冲突问题。

比如下图(一个空的哈希表):

Redis的哈希表是如何扩容的?_redis_03


索引值相同的两个节点使用链表连接起来:

Redis的哈希表是如何扩容的?_Redis_04

字典数据结构

提到哈希表的话顺便了解以下字典数据结构,毕竟它的底层就是哈希表实现的。

Redis的哈希表是如何扩容的?_服务器_05


type:指向dictType指针,保存了操作特定类型键值对的函数,Redis为不同用途的字典设置不同的类型特定函数。

privdata:保存了需要传递给不同特定函数的可选参数。

ht[2]:两个哈希表,字典使用的哈希表是ht[0],ht[1]则是当对ht[0]哈希表进行rehash时使用。

trehashidx:记录当前rehash进度,没有进行rehash则为-1。

Redis的哈希表是如何扩容的?_Redis_06


普通状态下的字典:

Redis的哈希表是如何扩容的?_redis_07

解决哈希冲突

将一个键值对添加到字典时,需要计算其哈希值和索引值,接着根据索引值将新节点放到哈希表数组的指定索引上。
计算哈希值:
hash = dict->type->hashFunction(key)
计算索引值:
hash & dict->ht[x].sizemask
键冲突:当两个或以上数量的键进行哈希之后索引值一样,也就是说两个节点要放在同一个同桶里,这时可能就会存在覆盖(冲突),那么就得解决这种冲突了。
Redis解决键冲突的方法:链地址法(separate chaining)——拉链法,假设你已了解Java HashMap原理,这里链地址法原理就不细说了。
解决哈希冲突有哪些方法?

  • 再哈希法
  • 链地址法
  • 开放地址法
  • 建立公共溢出区

扩容/缩容

为什么要进行扩容或缩容?
扩容原因:当hashtable存储的元素过多,可能由于碰撞也过多,导致其中某链表很长,最后致使查找和插入时间复杂度很大。因此当元素超多一定的时候就需要扩容。
缩容原因:当元素数量比较少的时候就需要缩容以节约不必要的内存。为了让哈希表的负载因子(load factor)维持在一个合理的范围内,会使用rehash(重新散列)操作对哈希表进行相应的扩展或收缩。负载因子的计算公式:哈希表已保存节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size扩容条件(满足任意一个即可)

  • Redis服务器目前没有在执行BGSAVEBGREWRITEAOF命令,并且哈希表的负载因子大于等于1。
  • Redis服务器目前在执行BGSAVEBGREWRITEAOF命令,并且哈希表的负载因子大于等于5。

为什么BGSAVEBGREWRITEAOF命令是否在执行,Redis服务器哈希表执行扩容所需的负载因子不相同(1或5)?
BGSAVE:用于在后台异步保存当前数据库的数据到磁盘。
BGREWRITEAOF:用于异步执行一个 AOF( Append Only File ) 文件重写操作。
因为当执行BGSAVEBGREWRITEAOF命令过程中,Redis需要创建服务器进程的子进程,操作系统采用的是COW,即 写时复制 copy-on-write的技术来优化子进程的使用效率。所以在子进程存在时,服务器会提高执行扩容所需的负载因子,从而尽可能避免在子进程存在期间进行扩容,可以避免不必要的内存写入操作,最大限度节约内存

缩容的条件:哈希表的负载因子小于0.1。

对字典的哈希表rehash步骤

  • 为ht[1]分配空间:扩展操作,那么ht[1] 的大小为第一个大于等于ht[0] .used*2的2的n次幂;收缩操作,那么ht[1] 的大小为第一个大于等于ht[0].used 的2的n次幂
  • 将ht[0]中的数据转移到ht[1]中,在转移的过程中,重新计算键的哈希值和索引值,然后将键值对放置到ht[1]的指定位置。
  • 当ht[0]的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),将ht[0]释放,然后将ht[1]设置成ht[0],最后为ht[1]分配一个空白哈希表:

开始哈希前:

Redis的哈希表是如何扩容的?_键值对_08


为ht[1]分配空间,ht[0].used当前值为4,8恰好是第一个大于等于4的2的N次幂,那么当前就会将ht[1]哈希表大小设置为8。

Redis的哈希表是如何扩容的?_键值对_09


将ht[0]的键值对都rehash到ht[1]

Redis的哈希表是如何扩容的?_服务器_10


释放ht[0],将ht[1]设置为ht[0],ht[1]再设置为空的哈希表

Redis的哈希表是如何扩容的?_redis_11

渐进式rehash

为什么要进行渐进式rehash?
在元素数量较少时,rehash会非常快的进行,但是当元素数量达到几百万、甚至几个亿时进行rehash将会是一个非常耗时的操作。如果一次性将成万上亿的元素的键值对rehash到ht[1],庞大的计算量可能会导致服务器在一段时间内停止服务,这是非常危险的!所以,rehash这个动作不能一次性、集中式的完成,而是分多次、渐进式地完成。

渐进式rehash步骤

  • 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。
  • 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始
  • 在rehash进行期间,每次对字典执行CRUD:添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后,程序将rehashidx+1(表示下次将rehash下一个桶)。
  • 随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1表示rehash完成。

渐进式rehash的好处:在于它采取分而治之的方式,将rehash键值对所需的计算工作均摊对字典的每个添加、删除、查找和更新操作上,从而避免了集中式rehash 而带来的庞大计算量

准备进行渐进式rehash:

Redis的哈希表是如何扩容的?_服务器_12


此时rehashidx=0,也就是会将索引为0的键值对进行迁移

Redis的哈希表是如何扩容的?_服务器_13


接着,rehashidx继续递增,假如到最后将索引3的进行迁移

Redis的哈希表是如何扩容的?_键值对_14


渐进式rehash结束

Redis的哈希表是如何扩容的?_键值对_15


在迁移过程中,会不会造成读少数据?

不会,因为在迁移时,首先会从ht[0]读取数据,如果ht[0]读不到,则会去ht[1]读。

在迁移过程中,新增加的数据会存放在哪个ht?

迁移过程中,新增的数据只会存在ht[1]中,而不会存放到ht[0],ht[0]只会减少不会新增。

相关问题

Redis的字典渐进式扩容与ConcurrentHashMap的扩容策略比较?那么他们在扩容、CRUD时有什么区别呢?

时间对比:
一个单线程渐进扩容,一个多线程协同扩容。在平均的情况下,是ConcurrentHashMap快。这也意味着,扩容时所需要
花费的空间能够更快的进行释放。
读操作:
两者的性能相差不多。
写操作:
Redis的字典返回更快些,因为它不像ConcurrentHashMap那样去帮着扩容(当要写的桶位已经搬到了newTable时),等扩容完才能进行操作,而redis则是直接将新加的元素添加到ht[1]
删除操作:
和写操作一样。

如果内存资源吃紧,希望能够进行快速的扩容方便释放扩容时需要的辅助空间,选择多线程协同扩容。
如果对于写和删除操作要求迅速,那么可以选择单线程渐进扩容。


标签:扩容,rehash,Redis,ht,键值,表是,哈希,字典
From: https://blog.51cto.com/u_15911055/6193304

相关文章

  • 分布式缓存--Redis
    目录一、单点Redis的问题二、Redis持久化2.1RDB持久化2.1.1单机安装Redis2.1.2RDB内部机制2.1.3RDB异步持久化2.1.14RDB的缺点2.2AOF持久化2.2.1AOF内部机制2.2.2AOF文件优化2.3RDB和AOF的比较三、Redis主从3.1主从架构3.1.1配置主从关系3.1.2主从关系测试3.2数据......
  • redis的 CLIENT LIST 详解
    redis>CLIENTLISTaddr=127.0.0.1:43143fd=6age=183idle=0flags=Ndb=0sub=0psub=0multi=-1qbuf=0qbuf-free=32768obl=0oll=0omem=0events=rcmd=clientaddr=127.0.0.1:43163fd=5age=35idle=15flags=Ndb=0sub=0psub=0multi=-1qbuf=0qbuf-free=0......
  • redis 数据重定向到文件方便查看
    背景:其实吧,就是因为每次都要一串命令进去redis敲,觉得很不方便,所以就用命令什么来生成个文本什么的,这样方便也省事啊,话不多说,直接上命令了,比如我现在最想要看的就是这个redis连过来的那堆ip的一些客户端信息啥的,直接就echo 这个值放进导成文本echo"clientlist"|/home/redis/red......
  • Redis安装(Linux CentOS)
    1.环境介绍主机系统:CentOSRedis版本:7.0.102.安装过程检查GCC版本gcc-vredis6.0以上需要gcc5.3,升级gcc。如果安装的redis版本低于6.0,这一步可以忽略yum-yinstallcentos-release-sclyum-yinstalldevtoolset-9-gccdevtoolset-9-gcc-c++devtoolse......
  • docker:Dockerfile、docker私有仓库、dockercompose介绍、dockercompose部署flask+redi
    目录一、Dockerfile1.1常用和不常用命令1.2dockerfile构建一个djagno项目二、docker私有仓库2.1镜像传到官方仓库2.2镜像分层2.3私有仓库搭建三、dockercompose介绍四、dockercompose部署flask+redis项目4.1新建flask项目app.py4.2编写Dockerfile--》用于构建flask项目的......
  • Redis相关操作
    Redis相关文档一.Redis简单使用​ redis作为一款目前这个星球上性能最高的非关系型数据库之一.拥有每秒近十万次的读写能力.其实力只能用恐怖来形容.1.安装redisredis是我见过这个星球上最好安装的软件了.比起前面的那一坨.它简直了...直接把压缩包解压.然后配置一下......
  • docker,Dockerfile,docker私有仓库,dockercompose介绍,dockercompose部署flask+redis项目,d
    内容回顾容器操作dockerstart容器id启动容器dockerstop容器id停止容器dockerrm 容器id删除容器ockerrm`dockerps-aq`#正在运行的容器不能删除dockerexec容器id命令让容器执行命令dockercp宿主机目录容器id:容器目录#目录要存在dockercp容......
  • redis 没用
    Redis高频面试题及答案 1.redis是什么?redis是nosql(也是个巨大的map)单线程,但是可处理1秒10w的并发(数据都在内存中)使用java对redis进行操作类似jdbc接口标准对mysql,有各类实现他的实现类,我们常用的是druid其中对redis,我们通常用Jedis(也为我们提供了连......
  • 局域网跨机器访问其他机器上虚拟机的Redis
    以上修改完毕之后就可以从别人的电脑访问你主机的ip地址+主机端口号直接访问虚拟机的redis了(防火墙开放了主机的相应端口)然后直接下一步下一步到名称自己起个名称点击完成就可以了......
  • redis_exporter
    监听的端口9121https://github.com/oliver006/redis_exporteroliver006/redis_exporterquay.io/oliver006/redis_exporterdockerrun--rm-it--entrypoint=/redis_exporter--name=tempoliver006/redis_exporter-redis.addr172.29.2.10:7000-config-command=CONFIG-re......