redis渐进式rehash-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心
  • 博客访问: 265287
  • 博文数量: 619
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 5320
  • 用 户 组: 普通用户
  • 注册时间: 2022-03-07 15:28
个人简介

天翼云是中国电信倾力打造的云服务品牌,致力于成为领先的云计算服务提供商。提供云主机、cdn、云电脑、大数据及ai等全线产品和场景化凯发app官方网站的解决方案。

文章分类

全部博文(619)

文章存档

2024年(170)

2023年(247)

2022年(202)

我的朋友
相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·

分类: nosql

2024-08-02 17:51:47

本文分享自天翼云开发者社区《》,作者:l****n

 

redis是k-v型数据库,其内部设计了一种dict类型的数据结构用来存储键值结构。

 

dict 通常的存储结构是 key-value 形式的,通过 hash 函数对 key 求 hash 值来确定 value 的位置,因此也叫 hash 表,是一种用来解决算法中查找问题的数据结构,默认的算法复杂度接近 o(1)。

 

使用哈希表总是会遇到哈希碰撞问题,dict使用拉链法将发生碰撞的元素组成链表,挂在发生碰撞的桶下,但是随着存储元素的不断增加,碰撞发生的几率也不断增大,一个桶下链接的链表长度越来越长,定位一个key的时间复杂度就无法保证了,redis作为内存数据库,本身追求的是更高的处理性能,线性增加的耗时无疑是不能接受的,为了减少hash碰撞,需要创建一个更长的hash表,让元素能够均匀的分布在hash表上。

 

所以,dict内部定义了两个hashtable,分别是dictht[0]和dictht[1],元素数量不多时,dict只在dictht[0]上存储元素,dictht[1]不分配空间。当dictht[0]的元素个数达到一定数量,会触发扩容过程,让dictht[1]指向一个2倍长度的空间,然后进行rehash, 将dictht[0]上的元素重新映射到dictht[1]上。

 

如果dictht[0]上有很多元素,进行rehash无疑是一个很耗时的过程,加上redis是单线程,如果想一次完成rehash,就会很长时间的阻塞业务,所以redis选择渐进式rehash。每次dictht[0]收到一个请求,只会将一个索引上的链表进行重新映射。

 

在将数据拷贝至dictht[1]时,dictht[0]仍然对客户端提供服务。rehash期间,如果有新的插入元素请求时,直接将元素插入到dictht[1]中,有客户端查询请求到来, 按照dictht[0]->dictht[1]的顺序依次进行查询。

阅读(66) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图