Redis底层数据结构之dict、ziplist、quicklist详解

目录
  • 1 Redis dict
    • 1.1 扩缩容的条件
    • 1.2 渐进式rehash操作
  • 2 Redis ziplist
    • 2.1 ziplist结构
    • 2.2 entry结构
  • 3 Redis quicklist

此前我们学习了常见的Reids数据类型,这些数据类型都需要底层的数据结构的支持,现在我们来看看Redis常见的底层数据结构:dict、ziplist、quicklist。

1 Redis dict

dict就是“字典”的意思,它是Redis中的一种使用的非常多的底层的数据结构,除了hash会使用字段之外,整个 Redis 数据库的所有 key 和 value 也组成了一个全局字典dict,还有带过期时间的 key 也是一个字典expires(存储在 RedisDb 数据结构中)。

Redis 中的字典相当于 JDK1.7中的 HashMap,内部实现也差不多类似,都是通过 “数组 + 链表” 的链地址法来解决部分哈希冲突,同时这样的结构也吸收了两种不同数据结构的优点。

和JDK1.7中的hashmap不同的是,Reids的字典结构内部包含两个hashtable变量,通常情况下只有一个hashtable有值,另一个为空表,但是在字典扩容缩容时,需要分配新的hashtable,并且使用了一种叫做渐进式搬迁(rehash)的机制来提高dict的缩放效率,这时候两个hashtable分别存储旧的和新的 hashtable,待搬迁结束后,旧的将被删除,新的 hashtable 取而代之。

1.1 扩缩容的条件

正常情况下,当 hash 表中元素的个数等于数组的长度时,就会开始扩容,扩容的新数组是原数组大小的2倍。不过如果 Redis 正在做 BGSAVE或者BGREWRITEAOF(持久化),为了减少内存占用,Redis 尽量不去扩容,但是如果 hash 表非常满了,达到了数组长度的 5 倍了,这个时候就会强制扩容。

当 hash 表因为元素逐渐被删除变得越来越稀疏时,Redis 会对 hash 表进行缩容来减少hash表的第一维数组空间占用。所用的条件是:元素个数低于数组长度的10%,缩容不会考虑 Redis 是否在做 bgsave。

1.2 渐进式rehash操作

在扩容和收缩的时候,如果哈希字典中有很多元素,一次性将这些键从ht0(正在使用的hashtable)全部rehash到ht1(另一个空的hashtable)的话,由于Redis是单线程模型,那么可能会导致服务器在一段时间内停止服务。所以,采用渐进式rehash的方式,数据的迁移并不是一步完成的,因此dict内部还有一个rehashidx属性用来控制rehash,默认置为-1。

  • 为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操作结束。
  • 把ht[1]设置为ht[0],并重新在ht[1]上新建一个空表,为下次rehash做准备。

渐进式rehash采用的是一种分而治之的方式,它以bucket(桶)为基本单位进行渐进式的数据迁移,每步完成一个bucket的迁移,直至所有数据迁移完毕。这种方式将rehash的操作分摊在每一个的访问中,避免集中式rehash而带来的庞大计算量。

在渐进式rehash的过程中,如果有删除、修改、查询操作,则会在两个哈希表ht[0]和ht[1]上进行,先操作ht[0],如果没找到,再操作ht[1],则新增的数据则会被保存在ht[1]中,ht[0]中包含的键值对数量会只减不增,并随着 rehash 操作的执行而最终变成空表。

2 Redis ziplist

ziplist又名压缩列表,见其名知其意,这种数据结构就比较节省内存空间,Redis中对于list(3.2版本之前)、hash、zset类型的数据,如果元素较少,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来存储。

ziplist本身可以有序也可以无序。当作为list(3.2版本之前)和hash的底层实现时,节点之间没有顺序;当作为zset的底层实现时,节点之间会按照score大小顺序排列,元素和score被分别存储为两个节点,元素在前,score在后。

ziplist的节省空间是相较于数组而言的,ziplist和数组一样同样采用一整块连续的空间来存储数据,数组在实际存储时,每一个元素所占的实际大小是一样的,并且是以最大的元素的大小为准,这样就能进行快速的根据索引访问,而ziplist则允许每一个entry节点(对于数组中的元素)所占的实际大小不同,另外,节点之间没有存储前驱和后继的指针,以此节约空间。

ziplist支持正序或者倒序的遍历,往ziplist里插入一个entry 时间复杂度 平均:O(n),最坏:O(n²),从ziplist里删除一个entry 时间复杂度 平均:O(n), 最坏:O(n²)。最坏为O(n²)是因为Redis连锁更新导致的,但这种情况出现的概率不高。

ziplist和数组类似,删除和添加节点都可能涉及到其他节点位置的移动,因此只适用于元素数据量较少,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串的情况。

2.1 ziplist结构

Redis的ziplist采用一系列特殊编码的连续内存块,一个压缩列表出了在头部包含一些整体信息之外,剩下的部分可以包含任意多个节点(entry)。

整体结构如下:

  1. zlbytes:32位无符号整数,表示ziplist的整体长度(字节)。在对ziplist重新分配内存或者计算zlend的位置时有用。
  2. zltail:32位无符号整数,最后一个节点距离头部的偏移量,通过该偏移量程序无需遍历整个ziplist即可确定尾节点的地址,在反向遍历ziplist或者pop尾部节点的时候很有用。
  3. zllen:16位无符号整数,ziplist的节点(entry)个数。当小于值小于65535时,该值时准确的,等于65535(16位的最大值)时,需要遍历整个链表才能得到真实节点数量。
  4. entry:ziplist中的数据节点,长度不固定,自己的长度保存在每一个entry节点内部。
  5. zlend:8位无符号整数固定值为0xFF,用于标记ziplist的结尾。

2.2 entry结构

ziplist的entry用于存储正数或者字符串(字节数组),且每个节点的长度都是不一样的,因此节点的长度只能由这个节点自己来保存,Redis的ziplist中,entry由三部分构成:

  • previous_entry_length:8bit或者40bit,用于记录上一个节点的长度(字节),为了方便反向遍历ziplist。
  • encoding:当前节点数据的编码规则,即data属性的数据类型以及长度。
  • content:当前节点的值,可以是数字或字符串(字节数组)。

previous_entry_length用于记录上一个节点的长度(字节),为了方便反向遍历ziplist,其本身的长度可能是8bit或者40bit。

  1. 如果前一节点的长度小于254字节,那么prevlengh属性的长度为1字节,前一节点的长度就保存在这一个字节里面,这样更加节约内存。
  2. 如果前一节点的长度大于等于254字节,那么prevlengh属性的总长度为5字节,第一字节被固定设置为0xFE(十进制值254),而之后的四个字节则用于保存前一节点的长度。
  3. 第二种情况下,第一个字节254而不用255(0xFF)是因为255是zlend的值,它用于判断ziplist是否到达尾部。

content表示当前节点的值,可以是数字或字符串(字节数组),encoding 表示当前节点数据的编码规则,即data属性的数据类型以及长度,其中encoding其中高2位用来区分整数节点和字符串节点(高2位为11时是整数节点),根据值的类型不同,一共有九种编码类型。

字节数组的encoding类型3种,encoding有8位、16位、40位三种长度,context的长度也是变化的:

encoding长度 encoding格式 content格式
8bit 高两位固定00,后6位表示字节数组的长度 长度小于等于63(2^6-1)字节的字节数组
16bit 高两位固定01,后14位表示字节数组的长度。 长度小于等于16383(2^14-1)字节的字节数组
40bit 高两位固定10,后38位表示字节数组的长度。 长度小于等于4294967295(2^32-1)字节的字节数组

整数值的encoding类型6种,固定长度8位,高两位固定11,表示整数,因此需要后两位来表示不同的整数类型。整数类型的content的长度虽然也是可变的,但固定范围内的整数长度一样,也就是说content长度只有固定的几种。

encoding长度 encoding格式 content格式
1bit 1111xxxx,后四位用来表示content。 4bit长的无符号整数,即介于0至12之间,没有content字段,在encoding中存储。
11111110 8bit,有符号整数。
11000000 16bit,有符号整数。
11110000 24bit,有符号整数。
11010000 32bit,有符号整数。
11100000 64bit,有符号整数。

3 Redis quicklist

Redis 的list在3.2版本之前在元素较少时实际上是采用ziplist结构,当链表entry数据超过512、或单个value 长度超过64,底层就会转化成linkedlist编码,而Redis3.2及其之后则采用quicklist结构代替ziplist和linkedlist。

ziplist存储在一段连续的内存上,所以存储和查找效率很高,顺序IO访问。但是,它不利于修改操作,插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,适用于存储整数和短字符串。

双向链表linkedlist便于在表的两端进行push和pop操作,在插入节点上复杂度很低,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个prev 和 next指针(64 位操作系统占用 8 个字节);其次,双向链表的各个节点是单独的内存块,地址不连续,随机IO访问,节点多了容易产生内存碎片,影响内存管理效率。

quickList将 linkedList 按段切分,每一段使用 zipList 来紧凑存储,多个 zipList 之间使用双向指针串接起来。

首先quickList就是一个标准的双向链表的配置,有head 和tail节点,每个节点是一个quicklistNode节点,包含prev和next指针,内部还包含一个ziplist,使用ziplist来保存数据,而ziplist实际上含有多个entry节点,保存着数据。相当与一个quicklistNode节点保存的是一片数据,而不再是一个数据。

quickList将二者的优点结合起来,在宏观上是一个双向链表结构,插入、删除quicklistNode节点的成本很低,不需要移动其他节点的位置,而在微观上,每一个quicklistNode节点又是一个个的ziplist,内部包含多个数据,ziplist内存连续,减少了内存碎片,同时由于每一个ziplist不是很大(大小可以配置),因此插入和删除操作不会进行大量的数据移动。

相关文章:

https://redis.io/topics/data-types

https://redis.io/topics/data-types-intro

到此这篇关于Redis的底层数据结构之dict、ziplist、quicklist详解的文章就介绍到这了,更多相关Redis底层数据结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Redis底层数据结构详解

    Redis作为Key-Value存储系统,数据结构如下: Redis没有表的概念,Redis实例所对应的db以编号区分,db本身就是key的命名空间. 比如:user:1000作为key值,表示在user这个命名空间下id为1000的元素,类似于user表的id=1000的行. RedisDB结构 Redis中存在"数据库"的概念,该结构由redis.h中的redisDb定义. 当redis 服务器初始化时,会预先分配 16 个数据库 所有数据库保存到结构 redisServer 的一

  • redis中的数据结构和编码详解

    redis中的数据结构和编码:     背景: 1>redis在内部使用redisObject结构体来定义存储的值对象. 2>每种类型都有至少两种内部编码,Redis会根据当前值的类型和长度来决定使用哪种编码实现. 3>编码类型转换在Redis写入数据时自动完成,这个转换过程是不可逆的,转换规则只能从小内存编码向大内存编码转换.     源码: 值对象redisObject: typedef struct redisObject {                 unsigned ty

  • redis数据结构之intset的实例详解

    redis数据结构之intset的实例详解 在redis中,intset主要用于保存整数值,由于其底层是使用数组来保存数据的,因而当对集合进行数据添加时需要对集合进行扩容和迁移操作,因而也只有在数据量不大时redis才使用该数据结构来保存整数集合.其具体的底层数据结构如下: typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; }

  • 详解redis数据结构之sds

    详解redis数据结构之sds 字符串在redis中使用非常广泛,在redis中,所有的数据都保存在字典(Map)中,而字典的键就是字符串类型,并且对于很大一部分字典值数据也是又字符串组成的.以下是sds的具体存储结构: 从图中可以看出,sds的属性有三个:len.free和buf数组.这里len字段是用来保存sds字符串中所包含字符数目的,free字段则是用来保存buf数组中空余的部分的长度的,而buf数组则是实际用来保存字符串的.比如如下结构保存了"Hello World!"这个字

  • Redis中5种数据结构的使用场景介绍

    一.redis 数据结构使用场景 原来看过 redisbook 这本书,对 redis 的基本功能都已经熟悉了,从上周开始看 redis 的源码.目前目标是吃透 redis 的数据结构.我们都知道,在 redis 中一共有5种数据结构,那每种数据结构的使用场景都是什么呢? String--字符串 Hash--字典 List--列表 Set--集合 Sorted Set--有序集合 下面我们就来简单说明一下它们各自的使用场景: 1. String--字符串 String 数据结构是简单的 key-

  • redis内部数据结构之SDS简单动态字符串详解

    前言 reids 没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组)而是构建了一种名为简单动态字符串的抽象类型,并为redis的默认字符串表示,因为C字符串不能满足redis对字符串的安全性.效率以及功能方面的需求 1.SDS 定义 在C语言中,字符串是以'\0'字符结尾(NULL结束符)的字符数组来存储的,通常表达为字符指针的形式(char *).它不允许字节0出现在字符串中间,因此,它不能用来存储任意的二进制数据. sds的类型定义 typedef char *sds; 每个sds

  • 详解Redis数据结构之跳跃表

    1.简介 我们先不谈Redis,来看一下跳表. 1.1.业务场景 场景来自小灰的算法之旅,我们需要做一个拍卖行系统,用来查阅和出售游戏中的道具,类似于魔兽世界中的拍卖行那样,还有以下需求: 拍卖行拍卖的商品需要支持四种排序方式,分别是:按价格.按等级.按剩余时间.按出售者ID排序,排序查询要尽可能地快.还要支持输入道具名称的精确查询和不输入名称的全量查询. 这样的业务场景所需要的数据结构该如何设计呢?拍卖行商品列表是线性的,最容易表达线性结构的是数组和链表.假如用有序数组,虽然查找的时候可以使用

  • 详解redis数据结构之压缩列表

     详解redis数据结构之压缩列表 redis使用压缩列表作为列表键和哈希键的底层实现之一.当一个列表键只包含少量的列表项,并且每个列表项都是由小整数值或者是短字符串组成,那么redis就会使用压缩列表存储列表项:同理,当一个哈希表包含的键值对都是由小整数值或者是短字符串组成,并且存储的键值对数目不多时,redis也会使用压缩列表来存储哈希表.以下是压缩列表存储结构: zlbytes长度为4个字节,记录了整个压缩列表所占用的字节数 zltail长度为4个字节,记录了压缩列表起始位置到压缩列表尾节

  • Redis底层数据结构之dict、ziplist、quicklist详解

    目录 1 Redis dict 1.1 扩缩容的条件 1.2 渐进式rehash操作 2 Redis ziplist 2.1 ziplist结构 2.2 entry结构 3 Redis quicklist 此前我们学习了常见的Reids数据类型,这些数据类型都需要底层的数据结构的支持,现在我们来看看Redis常见的底层数据结构:dict.ziplist.quicklist. 1 Redis dict dict就是"字典"的意思,它是Redis中的一种使用的非常多的底层的数据结构,除了h

  • redis bitmap数据结构之java对等操作详解

    目录 1. redis基本的bitmap操作命令 2. java中的原生bitmap 3. java和redis的bitmap互操作 在之前的文章中,我们有说过bitmap,bitmap在很多场景可以应用,比如黑白名单,快速判定,登录情况等等.总之,bitmap是以其高性能出名.其基本原理是一位存储一个标识,其他衍生知道咱就不说了,而redis就是以这种原生格式存储的. 实际上,redis是基于string的数据结构实现了bitmap的功能. 1. redis基本的bitmap操作命令 最基本的

  • Redis实现延迟队列的全流程详解

    目录 1.前言 1.1.什么是延迟队列 1.2.应用场景 1.3.为什么要使用延迟队列 2.Redis sorted set 3.Redis 过期键监听回调 4.Quartz定时任务 5.DelayQueue 延迟队列 6.RabbitMQ 延时队列 7.时间轮 1.前言 1.1.什么是延迟队列 延时队列相比于普通队列最大的区别就体现在其延时的属性上,普通队列的元素是先进先出,按入队顺序进行处理,而延时队列中的元素在入队时会指定一个延迟时间,表示其希望能够在经过该指定时间后处理.从某种意义上来讲

  • Go底层channel实现原理及示例详解

    目录 概念: 使用场景: 底层数据结构: 操作: 创建 发送 接收 关闭 案例分析: 概念: Go中的channel 是一个队列,遵循先进先出的原则,负责协程之间的通信(Go 语言提倡不要通过共享内存来通信,而要通过通信来实现内存共享,CSP(Communicating Sequential Process)并发模型,就是通过 goroutine 和 channel 来实现的) 使用场景: 停止信号监听 定时任务 生产方和消费方解耦 控制并发数 底层数据结构: 通过var声明或者make函数创建

  • Android开发数据结构算法ArrayList源码详解

    目录 简介 ArrayList源码讲解 初始化 扩容 增加元素 一个元素 一堆元素 删除元素 一个元素 一堆元素 修改元素 查询元素 总结 ArrayList优点 ArrayList的缺点 简介 ArrayList是List接口的一个实现类,它是一个集合容器,我们通常会通过指定泛型来存储同一类数据,ArrayList默认容器大小为10,自身可以自动扩容,当容量不足时,扩大为原来的1.5倍,和上篇文章的Vector的最大区别应该就是线程安全了,ArrayList不能保证线程安全,但我们也可以通过其

  • 数据结构 栈的操作实例详解

    数据结构 栈的操作实例详解 说明: 往前学习数据结构,想运行一个完整的顺序栈的程序都运行不了,因为书上给的都是一部分一部分的算法,并没有提供一个完整可运行的程序,听了实验课,自己折腾了一下,总算可以写一个比较完整的顺序栈操作的小程序,对于栈也慢慢开始有了感觉.下面我会把整个程序拆开来做说明,只要把这些代码放在一个文件中,用编译器就可以直接编译运行了. 一.实现 1.程序功能 关于栈操作的经典程序,首当要提及进制数转换的问题,利用栈的操作,就可以十分快速地完成数的进制转换. 2.预定义.头文件导入

  • 数据结构之数组Array实例详解

    数据结构之数组Array实例详解 数组Array 基本操作 Status InitArray(int dimm,...)//若维数dim和随后的各维长度合法,则构造相应的数组A,并返回OK Status DestroyArray() //销毁数组A Status Locate(va_list ap,int &off) //若ap指示的各下标值合法,则求出该元素在A中相对地址off Status Value(ElemType &e,...) //A是n维数组,e为元素变量,随后是n个下标值.

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

随机推荐