当前位置： 首页 > article >正文

redis 底层数据结构

article 2024/12/2 4:32:09

概述

Redis 6 和 Redis 7 之间对比：

 Redis6 和 Redis7 最大的区别就在于 Redis7 已经用 listpack 替代了 ziplist.

以下是基于 Redis 7基础分析。

RedisObject

Redis是⼀个<k,v>型的数据库，其中key通常都是string类型的字符串对象，⽽value在底层就统⼀是redisObject对象。Redis中的任意数据类型都会被封装为⼀个RedisObject，也叫做Redis对象， redisObject结构，实际上就是Redis内部抽象出来的⼀个封装所有底层数据结构的统⼀对象。这就类似于Java的⾯向对象的设计⽅式。

源码如下：

这⾥⾯⼏个核⼼字段意义如下：

  • type：Redis的上层数据类型。⽐如string,hash,set等，可以使⽤指令type key查看。

127.0.0.1:6379> set userid 1594
OK
127.0.0.1:6379> type userid
string

  • encoding： Redis内部的数据类型。可以使⽤指令 object encoding key查看。

127.0.0.1:6379> set userid 1594
OK
127.0.0.1:6379> object encoding userid
"int"

  • lru：当内存超限时会采⽤LRU算法清除内存中的对象。关于LRU与LFU，在redis.conf中有描述

# LRU means Least Recently Used

# LFU means Least Frequently Used

  • refcount：表示对象的引⽤次数。可以使⽤OBJECT REFCOUNT key 指令查看。
  • ptr：这是⼀个指针，指向真正底层的数据结构。encoding只是⼀个类型描述。实际数据是保存在ptr指向的具体结构⾥。

encoding 底层编码方式如下:

编码方式说明
0BJ_ENCODING_RAWraw编码动态字符串
OBJ_ENCODING_INTlong类型的整数的字符串
OBJ_ENCODING_HThash表(字典dict)
OBJ_ENCODING_ZIPMAP已废弃
OBJ_ENCODING_LINKEDLIST双端链表 (已废弃)
0BJ_ENCODING_ZIPLIST压缩列表(7.0 已废弃)
OBJ_ENCODING_INTSET 整数集合
OBJ_ENCODING_SKIPLIST跳表
0BJ_ENCODING_EMBSTRembstr的动态字符串
0BJ_ENCODING_QUICKLIST快速列表
0BJ_ENCODING_STREAMStream流
OBJ_ENCODING_LISTPACK紧凑列表

String 数据结构

SDS

Redis 没有直接使⽤ C 语⾔中的字符串，因为 C 语⾔字符串存在很多问题：
  • 获取字符串⻓度的需要通过运算
  • ⾮⼆进制安全
  • 不可修改
Redis 构建了⼀种新的字符串结构，称为简单动态字符串 (Simple Dynamic String)SDS 。
例如，我们执行命令： 
127.0.0.1:6379> set name hi
OK

那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“hi”的SDS。

Redis是C语言实现的，其中SDS是一个结构体，源码如下：

例如，一个包含字符串“name”的sds结构如下：

1653984648404

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS：

1653984787383

假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：

如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；

如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

1653984822363

优点：

  1. 获取字符串长度的时间复杂度为O(1)
  2. 支持动态扩容
  3. 减少内存分配次数
  4. 二进制安全

String底层结构之int

如果存储的字符串是整数值，并且⼤⼩在LONG_MAX范围内，则会采⽤INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

String底层结构之embstr

如果存储的SDS⻓度⼩于44字节，则会采⽤EMBSTR编码，此时object head与SDS是⼀段连续空间。申请内存时只需要调⽤⼀次内存分配函数，效率更⾼。

String底层结构之Raw

基本编码⽅式是RAW基于简单动态字符串（ SDS）实现，存储上限为512mb。

Hash 数据结构

Hash 结构默认采⽤ listpack 编码，⽤以节省内存。
• 当数据量较⼤时， Hash 结构会转为 HT 编码，也就是 Dict ，触发条件有两个：
① listpack 中的元素数量超过了hash-max-listpack-entries （默认512 ）
② listpack 中的任意entry⼤⼩超过了hash-max-listpack-value （默认64 字节） 
127.0.0.1:6379> config get has*
3) "hash-max-listpack-value"
4) "64"
7) "hash-max-listpack-entries"
8) "512"

Hash数据结构之 listpack

listpack(紧凑列表)可以理解为一个替代版本的ziplist，由于ziplist中有着致命的缺陷-连锁更新，在极端条件下会有着极差的性能，导致整个redis响应变慢。因此在redis5中引入了新的数据结构listpack，作为ziplist的替代版。listpack在6以后已经作为t_hash的基础底层结构。

listpack的整体结构如下：


和 ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。不过，为了避免 ziplist 引起的连锁更新问题，listpack 中的每个列表项不再像 ziplist 列表项那样，保存其前一个列表项的长度，它只会包含三个方面内容：

  1.     当前元素的编码类型（entry-encoding）
  2.     元素数据 (entry-content)
  3.     编码类型和元素数据这两部分的长度 (entry-length)
核⼼是entry中原本记录前⼀个entry的⻓度，现在改为记录⾃⼰的⻓度。这样，就不会再因为前⼀个entry变化⽽影响⾃⼰的⻓度。这样也就没有了连锁更新的问题。

Hash数据结构之 hashtable

在Redis中hashtable就是字典dict，Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）。

代码

 结构图

当我们向 Dict 添加键值对时， Redis ⾸先根据 key 计算出 hash 值 (h ），然后利⽤ h& sizemask来计算元素应该存储到数组中的哪个索引位置。
Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过⻓，则效率会⼤⼤降低。
Dict 在每次新增键值对时都会检查负载因⼦（ LoadFactor =used/size ），满⾜以下两种情况时会触发哈希表扩容：
• 哈希表的 LoadFactor >= 1 ，并且服务器没有执⾏ SAVE 或 REWRITEAOF
等进程
• 哈希表的 LoadFactor>5 ；

Dict 除了扩容以外，每次删除元素时，也会对负载因⼦做检查，当 LoadFactor ＜ 0.1 时，会做哈希表收缩：
if个⼤于等于minimal的 2 n

 

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的 size 和 sizemask 变化，⽽ key 的查询与 sizemask 有关。因此必须对哈希表中的每⼀个 key 重新计 算索引，插⼊新的哈希表，这个过程称为 rehash 。过程是这样的：
  1.  计算新hash表的realsize，即第⼀个⼤于等于dict.ht[0].used的2n
  2.  按照新的realsize申请内存空间，创建dictht，并赋值给dict.ht[1]
  3. 设置rehashidx= 0，标示开始rehash
  4. 将dict.ht[0]中的每⼀个dictEntry都rehash到dict.ht[1]每次执⾏新增、查询、修改、删除操作时，都检查⼀下dict.rehashidx是否⼤于 -1，如果是则将ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，井且将 rehashidx++。直⾄dict.ht[0]的所有数据都rehash到dict.ht[1]
  5. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表
  6. 将rehashidx赋值为-1，代表rehash结束
  7. 在rehash过程中，新增操作，则直接写⼊ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执⾏。这样可以确保h[0]的数据只减不增，随着 rehash最终为空

RedisObject

List 数据结构

List 结构默认采⽤ listpack 编码，⽤以节省内存。
• 当数据量较⼤时，List 结构会转为 quicklist，触发条件有1个：
  list-max-listpack-size 每个 list 中包含的节点⼤⼩或个数。正数表示个数，负数 -1 到 -5 表示⼤⼩。
  •  - 5：每个quicklist节点上的listpack大小不能超过64Kb（1kb=1024 bytes，即64*1024 bytes）
  •  -4：每个quicklist节点上的listpack大小不能超过32Kb（1kb=1024 bytes，即32*1024 bytes）
  •  -3：每个quicklist节点上的listpack大小不能超过16Kb（1kb=1024 bytes，即16*1024 bytes）
  •  -2：默认值，每个quicklist节点上的listpack大小不能超过8Kb（1kb=1024 bytes，即8*1024                 bytes）
  • -1：每个quicklist节点上的listpack大小不能超过4Kb（1kb=1024 bytes，即4*1024 bytes）
127.0.0.1:6379> config get lis*
3) "list-compress-depth"
4) "0"
5) "list-max-listpack-size"
6) "-2"

List 数据结构之 listpack

同Hash数据结构之 listpack 一样，参考上文。

List 数据结构之 quicklist

listpack 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。但是我们要存储大量数据，超出了listpack最佳的上限，那怎么办？

Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个 listpack。我们就可以将数据存到多个 listpack中。

quicklistNode中间保存的数据结构。 在Redis6以前是ziplist，到Redis7中改为了listpack。

总结：

QuickList的特点：

  • 是一个节点为listpack的双端链表
  • 节点采用listpack，解决了传统链表的内存占用问题
  • 控制了listpack大小，解决连续内存空间申请效率问题
  • 中间节点可以压缩，进一步节省了内存

Set 数据结构

  1. 如果set的数据都是不超过64位的数字(⼀个long数字).就使⽤intset存储 IntSet 。
  2. 如果set的数据不是数字，并且数据的数量没有大于128且数据⼤⼩小于64，就⽤listpack存储。
  3. 如果数据的数量大于128或数据⼤⼩小于64，就改为使⽤hashtable存储。
127.0.0.1:6379> config get set*
3) "set-max-listpack-value"
4) "64"
5) "set-max-listpack-entries"
6) "128"
7) "set-max-intset-entries"
8) "512"

Set 数据结构之 IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。
结构如下：

其中的encoding包含三种模式，表示存储的整数大小不同：

 为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

总结：

Intset可以看做是特殊的整数数组，具备一些特点：

  • Redis会确保Intset中的元素唯一、有序
  • 具备类型升级机制，可以节省内存空间
  • 底层采用二分查找方式来查询


Set 数据结构之 listpask

同Hash数据结构之 listpack 一样，参考上文。

Set 数据结构之 hashtable

同Hash数据结构之 hashtable一样，参考上文。

ZSet 数据结构

  1. 如果set 数据的数量没有大于128且数据⼤⼩小于64，就⽤listpack存储。
  2. 如果数据的数量大于128或数据⼤⼩小于64，就改为使⽤skiplist 存储。
127.0.0.1:6379> config get zset*
1) "zset-max-listpack-entries"
2) "128"
7) "zset-max-listpack-value"
8) "64"

ZSet 数据结构之 listpask

同Hash数据结构之 listpack 一样，参考上文。

ZSet 数据结构之 skiplist

zset类型的数据，底层需要先按照score进⾏排序。排序过程中是需要移动内存的。如果节
点数据不是太多，将这些内存移动完后，重新整理成⼀个类似数据Array的listpack结果是
可以接受的。但是如果数据量太⼤(节点数和数据⼤⼩)，那么频繁移动内存，开销就⽐较⼤
了。这时，显然以链表这种零散的数据结构是⽐较合适的。
但是，对于⼀个单链表结构来说，要检索链表中的某⼀个数据，只能从头到尾遍历链表。
时间复杂度是O(N)，性能是⽐较低的。
如何对链表结构进⾏优化呢？skiplist跳表就是⼀种思路。skiplist的优化思路是构建多层逐
级缩减的⼦索引，⽤更多的索引来提升搜索的性能。
skiplist是⼀种典型的⽤空间换时间的解决⽅案，优点是数据检索的性能⽐较⾼。时间复杂
度是O(logN)，空间复杂度是O(N)。但是他的缺点也很明显，就是更新链表时，维护索引
的成本相对更⾼。因此，skiplist适合那些数据量⽐较⼤，且是读多写少的应⽤场景。


http://www.kler.cn/a/417974.html

相关文章：

  • 微服务即时通讯系统的实现（服务端）----（3）
  • 基于TensorFlow的手写体数字识别训练与测试
  • Qt桌面应用开发 第七天（绘图事件 绘图设备）
  • 基于Pytorch的CIFAR100数据集上从ResNet50到VGG16的知识蒸馏实验记录
  • Linux命令系列-常见查看系统资源命令
  • C# 数据类型详解：掌握数据类型及操作为高效编码奠定基础
  • YOLO系列论文综述（从YOLOv1到YOLOv11）【第12篇：YOLOv9——可编程梯度信息(PGI)+广义高效层聚合网络(GELAN)】
  • Rust学习笔记_02——数组
  • 可视化大屏系统如何实现3D数据导入与Web交互？
  • SpringAi整合大模型(进阶版)
  • MyBatis-Plus - 查询解析数据异常处理
  • Linux内核机制自学笔记
  • spring-boot自定义ApplicationListener及源码分析
  • SVN迁移至Git，保留commit提交记录
  • 使用Spring Data MongoDB中的MongoTemplate实现分组查询最新的数据
  • 设计模式---建造者模式
  • 迅为RK3588开发板Android12源码定制开发-安装adb驱动
  • 飙升Vue.js组件开发
  • Flutter 1.1：下载Flutter环境
  • 一个鸿蒙开发者的探索：实现相册访问功能
  • Python+Pytest+Yaml+Allure数据参数化（DDT）数据驱动（一）
  • 前端css实例
  • 【04】Selenium+Python 手动添加Cookie免登录（实例）
  • 何时在 SQL 中使用 CHAR、VARCHAR 和 VARCHAR(MAX)
  • Golang context 的作用和实现原理
  • 7. 现代卷积神经网络