redis渐进式rehash

天翼云开发者社区
• 阅读 153

本文分享自天翼云开发者社区《redis渐进式rehash》,作者: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]的顺序依次进行查询。

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
Linux实战教学笔记45:NoSQL数据库之redis持久化存储(一)
第1章redis存储系统1.1redis概述REmoteDIctionaryServer(Redis)是一个基于keyvalue键值对的持久化数据库存储系统。redis和大名鼎鼎的Memcached缓存服务软件很像,但是redis支持的数据存储类型比memcached更丰富,包括strings(字符串),lists(列
Stella981 Stella981
3年前
Redis5版本集群搭建
一、简介1.1Redis是什么Redis是一个开源的,使用ANSIC编写,高性能的KeyValue的NoSQL数据库。1.2Redis特点(1)基于内存(2)可持久化数据(3)具有丰富的数据结构类型,适应非关系型数据的存储需求(4)支持绝大多数主流开发语言,如C
Stella981 Stella981
3年前
Redis 为什么这么快? Redis 的有序集合 zset 的底层实现原理是什么? —— 跳跃表 skiplist
Redis有序集合zset的底层实现——跳跃表skiplistRedis简介Redis是一个开源的内存中的数据结构存储系统,它可以用作:数据库、缓存和消息中间件。它支持多种类型的数据结构,如字符串(Strings),散列(Hash),列表(List),集合(S
Stella981 Stella981
3年前
Redis为什么这么快
Redis简介Redis是一个开源的内存中的数据结构存储系统,它可以用作:数据库、缓存和消息中间件它支持多种类型的数据结构,如字符串(String),散列(Hash),列表(List),集合(Set),有序集合(SortedSet或者是ZSet)与范围查询,Bitmaps,Hyperloglogs和
Stella981 Stella981
3年前
Redis安装及前后置启动
Redis简单介绍及在Linux上安装(这里测试用是版本:redis3.0.0.tar.gz)一:什么是Redis?redis就是C语言编写的一个高性能的键值存储(keyvalue)的非关系型数据库(NoSql)。二:非关系型数据库的优点与缺点优点:可以轻松地处理海量数据缺点:1.没有主外键,
Stella981 Stella981
3年前
Redis实现之对象(一)
对象前面我们介绍了Redis的主要数据结构,如:简单动态字符串SDS、双端链表、字典、压缩列表、整数集合等。Redis并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象,每种对象都用到了至少一种我们之前介绍的数据结构通过这五种
Stella981 Stella981
3年前
Redis01
前言Redis用了这么久,一直没有认真的去了解其内部的数据结构和实现原理。从今天开始正式系统性的学习Redis。首先,还是从工作中经常打交道的数据类型开始说起,然后,在说到其内部使用的数据结构。Redis的简介Redis是一个开源的高性能的keyvalue数据库,与其他的keyvalue缓存产品相比有以下三个特点:
Stella981 Stella981
3年前
Redis的认识和基本操作
 Redis是什么Redis是一个高性能的开源的、C语言写的Nosql(非关系型数据库),数据保存在内存中。Redis是以keyvalue形式存储的Nosql,和传统的关系型数据库不一样。不一定遵循传统数据库的一些基本要求,比如说,不遵循sql标准,事务,表结构等等,非关系型数据库严格上不是一种数据库,应该是一种数据结构
Stella981 Stella981
3年前
Redis的简介
Redis简介Redis是一个高性能的keyvalue数据库。支持复杂的数据结构,支持持久化,支持主从集群,支持高可用,支持较大的value存储...Redis是一个nosql,非关系型数据库。Redis与其他keyvalue缓存产品有以下几个特点:Reids是基于内存
Redis数据结构(一)-Redis的数据存储及String类型的实现
1引言Redis作为基于内存的非关系型的KV数据库。因读写响应快速、原子操作、提供了多种数据类型String、List、Hash、Set、SortedSet、在项目中有着广泛的使用,今天我们来探讨下下Redis的数据结构是如何实现的。
天翼云开发者社区
天翼云开发者社区
Lv1
天翼云是中国电信倾力打造的云服务品牌,致力于成为领先的云计算服务提供商。提供云主机、CDN、云电脑、大数据及AI等全线产品和场景化解决方案。
文章
696
粉丝
15
获赞
40