Redis 数据结构
Redis
|
|
|
126

8618 字
|
36 分钟

Redis 数据结构

1. 简单动态字符串 SDS

我们都知道 Redis 中保存的 Key 是字符串，value 往往是字符串或者字符串的集合。可见字符串是 Redis 中最常用的一种数据结构

不过 Redis 没有直接使用 C 语言中的字符串，因为 C 语言字符串存在很多问题：

image-20240105130902974

  1. 获取字符串长度的需要通过运算
  2. 非二进制安全
  3. 不可修改

Redis 构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称 SDS

例如，我们执行命令：

image-20240105131549913

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

Redis 是 C 语言实现的，其中 SDS 是一个结构体，SDS 声明了很多对应长度的结构体

例如 SDS 8 位长度的结构体 sdshdr8 源码如下：

image-20240105132139133

sdshdr8 代表该字符串的长度 len 最多由 8 位二进制位表示，也就是最长是 2^8-1 = 255，但是为了兼容 C 语言，最后也要包含一个'\0'，所以最长是 254 个字符，但是 Redis 读取时不会跟 C 语言一样将它作为结束标识来读，而是读取长度 len 个，是二进制安全的。然后还有 sdshdr16、sdshdr32、sdshdr64 等类型的 SDS 结构体，其最大长度各不相同。还有 sdshdr5，但是因为太小，已经弃用

上图右边的数字代表结构体中不同 sds 对应的 flag 的值

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

1653984648404

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

1653984787383

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

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

这种多扩展一些新空间的方式称为内存预分配

1653984822363

alloc = (2+4)*2 = 12 因为 alloc 不包含结束标识，但是后面的格子是 12+1=13 个

内存预分配：重新分配内存很消耗资源，预分配后若下次还需扩容，若空间足够就不用再分配了，减少内存分配次数

image-20240105133100494

2. 整数集合 IntSet

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

1653984923322

这里的 contents 整数数组的类型 int8_t 不是只能存储 -128~127 的整数，而是由其 encoding 决定的；其中的 encoding 包含三种模式，表示存储的整数大小不同：

1653984942385

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

image-20240105135607724

现在，数组中每个数字都在 int16_t 的范围内，因此采用的编码方式是 INTSET_ENC_INT16，每部分占用的字节大小为：

  • encoding：4 字节
  • length：4 字节
  • contents：2 字节 * 3 = 6 字节（ 每个整数的大小取决于 encoding）

constants 数组是使用指针来指向内存中的地址，地址 = startPtr + (sizeof (int16)*index)，所以为了性能考虑，很多数组的脚标都从 0 开始

IntSet 升级编码：

现在，假设有一个 intset, 元素为 {5,10,20}，采用的编码是 INTSET_ENC INT16，则每个整数占 2 字节：

image-20231022162604097

我们向该其中添加一个数字：50000，这个数字超出了 int16_t 的范围，intset 会自动升级编码方式到合适的大小。以当前案例来说流程如下：

  • 升级编码为 INTSET_ENC_INT32, 每个整数占 4 字节，并按照新的编码方式及元素个数扩容数组
  • 倒序依次将数组中的元素拷贝到扩容后的正确位置
  • 将待添加的元素放入数组末尾
  • 最后，将 inset 的 encoding 属性改为 INTSET_ENC_INT32，将 length 属性改为 4

image-20231022162731096

1653985276621

升级源码如下：

1653985304075

1653985327653

image-20231022165451003

小总结：

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

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

3. 哈希表 Dict

我们知道 Redis 是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过 Dict 来实现的

Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

1653985396560

entry 的个数 used 是可以大于哈希表的大小 size 的，因为跟 Java 中一样，哈希冲突时，会使用一个链表来存储 hash 值相同的元素

当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash 值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1&3 = 1，因此 k1=v1 要存储到数组角标 1 位置

image-20240105143714573

为什么使用 h & sizemask 与运算，而不使用求余运算？

哈希表的大小 size 初始大小为 4，且必须是 2^n，所以 sizemask = size - 1。在这种情况下，h & sizemask = h % size，并且位运算的速度通常比取模操作 更快

1653985497735

Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

字典 > 哈希表 > 哈希节点

1653985570612

1653985640422

Dict 的扩容

Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict 在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

  1. 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程
  2. 哈希表的 LoadFactor > 5

1653985716275

Dict 的收缩

Dict 除了扩容以外，每次删除元素时，也会对负载因子做检查，当 LoadFactor<0.1 时，会做哈希表收缩：

1653985743412

Dict 的 rehash

不管是扩容还是收缩，必定会调用 dictExpand（与下面 rehash 步骤中前 3 步相同）方法，其中会创建新的哈希表，导致哈希表的 size 和 sizemask 变化，而 key 的查询与 sizemask 有关。因此必须对哈希表中的 每一个 key 重新计算索引，插入新的哈希表，这个过程称为 rehash。过程是这样的：

  1. 计算新 hash 表的 realeSize，值取决于当前要做的是扩容还是收缩：
    • 如果是扩容，则新 size 为第一个大于等于 dict.ht [0].used + 1 的 2^n
    • 如果是收缩，则新 size 为第一个大于等于 dict.ht [0].used 的 2^n （不得小于 4）
  2. 按照新的 realeSize 申请内存空间，创建 dictht，并赋值给 dict.ht [1]
  3. 设置 dict.rehashidx = 0，标示开始 rehash
  4. 将 dict.ht [0] 中的每一个 dictEntry 都 rehash 到 dict.ht [1]（非渐进式哈希）
    每次执行新增、查询、修改、删除操作时，都检查一下 dict.rehashidx 是否大于 -1，如果是则将 dict.ht [0].table [rehashidx] 的 entry 链表 rehash 到 dict.ht [1]，并且将 rehashidx++。直至 dict.ht [0] 的所有数据都 rehash 到 dict.ht [1]。（每次只 rehash 一个 entry 到 ht [1]）
  5. 将 dict.ht [1] 赋值给 dict.ht [0]，给 dict.ht [1] 初始化为空哈希表，释放原来的 dict.ht [0] 的内存
  6. 将 rehashidx 赋值为 -1，代表 rehash 结束
  7. 在 rehash 过程中，新增操作，则直接写入 ht [1]，查询、修改和删除则会在 dict.ht [0] 和 dict.ht [1] 依次查找并执行。这样可以确保 ht [0] 的数据只减不增，随着 rehash 最终为空

Dict 的 rehash 并不是一次性完成的。试想一下，如果 Dict 中包含数百万的 entry, 要在一次 rehash 完成，极有可能导致主线程阻塞。因此 Dict 的 rehash: 是分多次、渐进式的完成，因此称为渐进式 rehash。流程如上列第 4 6 7 步

注：第三步只会在还未开始 rehash 时才会设置为 0 代表开始 rehash，因为用过源码我们可以看到，当正在 rehash 时我们是不会扩容与缩容的

小总结：

Dict 的结构：

  • 类似 java 的 HashTable，底层是数组加链表来解决哈希冲突
  • Dict 包含两个哈希表，ht [0] 平常用，ht [1] 用来 rehash

Dict 的伸缩：

  • 当 LoadFactor 大于 5 或者 LoadFactor 大于 1 并且没有子进程任务时，Dict 扩容
  • 当 LoadFactor 小于 0.1 时，Dict 收缩
  • 扩容大小为第一个大于等于 used + 1 的 2^n
  • 收缩大小为第一个大于等于 used 的 2^n（不得小于 4）
  • Dict 采用渐进式 rehash，每次访问 Dict 时执行一次 rehash
  • rehash 时 ht [0] 只减不增，新增操作只在 ht [1] 执行，其它操作在两个哈希表

Dict 的缺点：

  • Dict 内部大量使用指针，内存空间不连续，通过指针链接，且容易产生内存碎片，造成严重的内存浪费
  • 指针也会占据存储空间，大量指针占据很多内存

4. 压缩列表 ZipList

为节省内存，改善 Dict 哈希表的问题，出现了 ZipList

ZipList 是一种特殊的 “双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入 / 弹出操作，并且该操作的时间复杂度为 O (1)

不是双端链表，但有双端链表的特点，且内存块是连续的，不需要通过指针寻址

1653985987327

1653986020491

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数
zltail uint32_t 4 字节 记录压缩列表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量。 最大值为 UINT16_MAX （65534），如果超过这个值，此处会记录为 65535，但节点的真实数量需要遍历整个压缩列表才能计算得出
entry 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端

ZipListEntry

ZipList 中的 Entry 并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用 16 个字节，浪费内存。而是采用了下面的结构：

1653986055253

  • previous_entry_length：前一节点的长度，占 1 个或 5 个字节
    • 如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值
    • 如果前一节点的长度大于 254 字节，则采用 5 个字节来保存这个长度值， 第一个字节为 0xfe，后四个字节才是真实长度数据
  • encoding：编码属性，记录 content 的数据类型（字符串还是整数）以及长度，占用 1 个、2 个或 5 个字节
  • contents：负责保存节点的数据，可以是字符串或整数

所以 entry 三个部分的长度都可以知晓，顺序遍历时只需要加上 entry 的长度，倒序遍历时只需要减去 pre_len

ZipList 中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值 0x1234，采用小端字节序后实际存储值为：0x3412

Encoding 编码

ZipListEntry 中的 encoding 编码分为字符串和整数两种：

  1. 字符串：如果 encoding 是以 “00”、“01” 或者 “10” 开头，则证明 content 是字符串

    编码 编码长度 字符串大小
    |00pppppp| 1 bytes <= 63 bytes(2^6)
    |01pppppp|qqqqqqqq| 2 bytes <= 16383 bytes(2^14)
    |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 5 bytes <= 4294967295 bytes(2^32)

    例如，我们要保存字符串：“ab” 和 “bc”

    1653986172002

    zlbytes、zltail、zllen 等标表示长度的属性使用小端字节序

  2. 整数：如果 encoding 是以 “11” 开始，则证明 content 是整数，且 encoding 固定只占用 1 个字节

    编码 编码长度 整数类型
    11000000 1 int16_t（2 bytes）
    11010000 1 int32_t（4 bytes）
    11100000 1 int64_t（8 bytes）
    11110000 1 24 位有符整数 (3 bytes)
    11111110 1 8 位有符整数 (1 bytes)
    1111xxxx 1 直接在 xxxx 位置保存数值，范围从 0001 ~ 1101 (十进制 1 ~ 13)，减 1 后结果为实际值（0 ~ 12）

    例如：一个 ZipList 中包含两个整数值： “2” 和 “5”

    1653986217182

    1653986282879

连锁更新

ZipList 的每个 Entry 都包含 previous_entry_length 来记录上一个节点的大小，长度是 1 个或 5 个字节：

  • 如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值
  • 如果前一节点的长度大于等于 254 字节，则采用 5 个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据

现在，假设我们有 N 个连续的、长度为 250~253 字节之间的 entry（前提），因此 entry 的 previous_entry_length 属性用 1 个字节即可表示，可是当 突然在前面插入一个长度大于 254 字节的 entry，就会发生连锁更新问题，如图所示：

1653986328124

ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生

概率很低，因为需要 N 个连续的、长度为 250~253 字节之间的 entry，条件较为苛刻

小总结：

ZipList 特性：

  • 压缩列表的可以看做一种连续内存空间的” 双向链表”
  • 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
  • 如果列表数据过多，导致链表过长，可能影响查询性能
  • 增或删较大数据时有可能发生连续更新问题

5. 快速列表 QuickList

问题 1：ZipList 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？

答：为了缓解这个问题，我们必须限制 ZipList 的长度和 entry 大小

问题 2：但是我们要存储大量数据，超出了 ZipList 最佳的上限该怎么办？

答：我们可以创建多个 ZipList 来分片存储数据

问题 3：数据拆分后比较分散，不方便管理和查找，这多个 ZipList 如何建立联系？

答：Redis 在 3.2 版本引入了新的数据结构 QuickList，它是一个双端链表，只不过链表中的 每个节点都是一个 ZipList

1653986474927

为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size 来限制

如果值为正，则代表 ZipList 的允许的 entry 个数的最大值

如果值为负，则代表 ZipList 的最大内存大小，分 5 种情况：

  • -1：每个 ZipList 的内存占用不能超过 4kb
  • -2：每个 ZipList 的内存占用不能超过 8kb
  • -3：每个 ZipList 的内存占用不能超过 16kb
  • -4：每个 ZipList 的内存占用不能超过 32kb
  • -5：每个 ZipList 的内存占用不能超过 64kb

这里的单位是 KB 更为合理，使用 kb 很容易让人产生误解，但是 Redis 配置文件中声明了 1kb = 1024bytes

# Note on units: when memory size is needed, it is possible to specify
# it in the usual form of 1k 5GB 4M and so forth:
#
# 1k => 1000 bytes
# 1kb => 1024 bytes
# 1m => 1000000 bytes
# 1mb => 1024*1024 bytes
# 1g => 1000000000 bytes
# 1gb => 1024*1024*1024 bytes
#
# units are case insensitive so 1GB 1Gb 1gB are all the same.

其默认值为 -2：

1653986642777

除了控制 ZipList 的大小，QuickList 还可以对节点的 ZipList 做压缩。通过配置项 list-compress-depth 来控制。因为链表一般都是从首尾访问较多，中间节点的访问次数较少，所以首尾是不压缩的。这个参数是 控制首尾不压缩的节点个数：

  • 0: 特殊值，代表不压缩
  • 1: 标示 QuickList 的首尾各有 1 个节点不压缩，中间节点压缩
  • 2: 标示 QuickList 的首尾各有 2 个节点不压缩，中间节点压缩
  • 以此类推

其默认值为：0：

image-20231023112549395

以下是 QuickList 的和 QuickListNode 的结构源码：

1653986667228

我们接下来用一段流程图来描述当前的这个结构

1653986718554

总结：

QuickList 的特点：

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

6. 跳表 SkipList

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

  • 元素按照升序排列存储
  • 节点可能包含多个指针，指针跨度不同，最高跨度可高达 32 层，由底层函数进行具体推算适合多少层跨度的指针

1653986771309

源码如下：

1653986813240

1653986877620

跳表的时间复杂度 是 log2N：

如果链表里有 N 个结点，会有多少级索引呢？

按照我们前面讲的，两两取首。每两个结点会抽出一个结点作为上一级索引的结点，以此估算：

  • 第一级索引的结点个数大约就是 n/2，
  • 第二级索引的结点个数大约就是 n/4，
  • 第三级索引的结点个数大约就是 n/8，依次类推……

也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k 级索引结点的个数就是 n/(2^k)。最高级索引有 2 个，所以 n/(2^k) = 2 –> k = log2n - 1 ，算上原始链表，就是 log2n

跳表的空间复杂度是 O (N)：

比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢？

我们来分析一下跳表的空间复杂度

  • 第一步：首先原始链表长度为 n，

  • 第二步：两两取首，每层索引的结点数： n/2, n/4, n/8 … , 8, 4, 2 每上升一级就减少一半，直到剩下 2 个结点，以此类推；如果我们把每层索引的结点数写出来，就是一个等比数列

    这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n) 。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。

  • 第三步：思考三三取首，每层索引的结点数：n/3, n/9, n/27 … , 9, 3, 1 以此类推

    第一级索引需要大约 n/3 个结点，第二级索引需要大约 n/9 个结点。每往上一级，索引结点个数都除以 3。为了方便计算，我们假设最高一级的索引结点个数是 1。我们把每级索引的结点个数都写下来，也是一个等比数列n/3+n/9+n/27+…+9+3+1=n/2。尽管空间复杂度还是 O(n) ，但比上面的每两个结点抽一个结点的索引构建方法，要减少了一半的索引结点存储空间。 所以空间复杂度是 O (n)

小总结：

SkipList 的特点：

  • 跳跃表是一个双向链表，每个节点都包含 score 和 ele 值
  • 节点按照 score 值排序，score 值一样则按照 ele 字典排序
  • 每个节点都可以包含多层指针，层数是 1 到 32 之间的随机数
  • 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
  • 增删改查效率与红黑树基本一致，实现却更简单

7. RedisObject

Redis 中的任意数据类型的键和值都会被封装为一个 RedisObject，也叫做 Redis 对象，源码如下：

1653986956618

所以每个 Redis 对象头就要占据 16 个字节 (0.5+0.5+3+4+8)，所以推荐使用集合的类型来存储数据。比如：存储 10 个字符串需要 10 个对象头，也就浪费 160 个字节，若使用 list 来存储，只需要 1 个对象头

Redis 的编码方式：

Redis 中会根据存储的数据类型不同，选择不同的编码方式，共包含 11 种不同类型：

编号 编码方式 说明
0 OBJ_ENCODING_RAW raw 编码动态字符串
1 OBJ_ENCODING_INT long 类型的整数的字符串
2 OBJ_ENCODING_HT hash 表（字典 dict）
3 OBJ_ENCODING_ZIPMAP 已废弃
4 OBJ_ENCODING_LINKEDLIST 双端链表（早期 Redis 使用）
5 OBJ_ENCODING_ZIPLIST 压缩列表
6 OBJ_ENCODING_INTSET 整数集合
7 OBJ_ENCODING_SKIPLIST 跳表
8 OBJ_ENCODING_EMBSTR embstr 的动态字符串
9 OBJ_ENCODING_QUICKLIST 快速列表
10 OBJ_ENCODING_STREAM Stream 流

五种数据类型对应的编码：

Redis 中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

数据类型 编码方式
OBJ_STRING int、embstr、raw
OBJ_LIST LinkedList 和 ZipList（3.2 以前)、QuickList（3.2 以后）
OBJ_SET intset、HT
OBJ_ZSET ZipList、HT 和 SkipList
OBJ_HASH ZipList、HT

8. String

String 是 Redis 中最常见的数据存储类型：

底层实现⽅式：动态字符串 sds 或者 long

String 的内部存储结构⼀般是 sds（Simple Dynamic String，可以动态扩展内存），但是如果⼀个 String 类型的 value 的值是数字，那么 Redis 内部会把它转成 long 类型来存储，从⽽减少内存的使用

  • 其基本编码方式是 RAW，基于简单动态字符串（SDS）实现，存储上限为 512MB

    1653987103450

  • 如果存储的 SDS 长度小于等于 44 字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段 连续空间。申请内存时只需要调用一次内存分配函数，效率更高

    1653987172764

1653987159575

由图：若 SDS 长度为 44 字节，那么 RedisObject (对象头 16 字节)+SDS (采用 sdshdr8：1+1+1+44+1) 的大小刚好为 64 字节，Redis 底层分配内存的算法是 jemalloc，会以 2^n 做内存分配，而 64 字节刚好是 2^6，分配内存时不会产生内存碎片

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

    image-20231023150257495

总结：

1653987202522

可使用 object encoding key 查看 key 的字符编码

确切地说，String 在 Redis 中是⽤⼀个 robj 来表示的，用来表示 String 的 robj 可能编码成 3 种内部表⽰：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT。其中前两种编码使⽤的是 sds 来存储，最后⼀种 OBJ_ENCODING_INT 编码直接把 string 存成了 long 型。在对 string 进行 incr, decr 等操作的时候：

  • 如果它内部是 OBJ_ENCODING_INT 编码，那么可以直接进行加减操作
  • 如果它内部是 OBJ_ENCODING_RAW 或 OBJ_ENCODING_EMBSTR 编码，那么 Redis 会先试图把 sds 存储的字符串转成 long 型，如果能转成功，再进行加减操作

对⼀个内部表示成 long 型的 string 执行 append, setbit, getrange 这些命令，针对的仍然是 string 的值（即⼗进制表示的字符串），而不是针对内部表⽰的 long 型进⾏操作

比如字符串“32”，如果按照字符数组来解释，它包含两个字符，它们的 ASCII 码分别是 0x33 和 0x32。当我们执行命令 setbit key 7 0 的时候，相当于把字符 0x33 变成了 0x32，这样字符串的值就变成了“22”。⽽如果将字符串“32” 按照内部的 64 位 long 型来解释，那么它是 0x0000000000000020，在这个基础上执⾏ setbit 位操作，结果就完全不对了。因此，在这些命令的实现中，会把 long 型先转成字符串再进行相应的操作

9. List

Redis 的 List 类型可以从首、尾操作列表中的元素：

1653987240622

哪一个数据结构能满足上述特征？

  • LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
  • ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
  • QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个 ZipList，存储上限高（同时具备二者的优点）

Redis 的 List 结构类似一个双端链表，可以从首、尾操作列表中的元素：

在 3.2 版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当元素数量小于 512 并且元素大小小于 64 字节时采用 ZipList 编码，超过则采用 LinkedList 编码。

在 3.2 版本之后，Redis 统一采用 QuickList 来实现 List：

1653987313461

image-20240108150855494

10. Set

Set 是 Redis 中的单列集合，满足下列特点：

  • 不保证有序性
  • 保证元素唯一
  • 求交集、并集、差集

1653987342550

可以看出，Set 对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？

HashTable，也就是 Redis 中的 Dict，不过 Dict 是双列集合（可以存键、值对）

Set 是 Redis 中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高

  • 为了查询效率和唯一性，set 采用 HT 编码（Dict）。Dict 中的 key 用来存储元素，value 统一为 null
  • 当存储的所有数据都是整数，并且元素数量不超过 set-max-intset-entries (默认值为 512) 时，Set 会采用 IntSet 编码，以节省内存

1653987388177

每次插入都会检查是否满足 都是整数 和 数量不超过 set-max-intset-entries 这两个条件，如果不满足，则会将 IntSet 编码转换为 HT 编码：

image-20231023220917496

结构如下：

1653987454403

11. Zset

ZSet 也就是 SortedSet，其中每一个元素都需要指定一个 score 值和 member 值：

  • 可以根据 score 值排序
  • member 必须唯一
  • 可以根据 member 查询分数

1653992091967

因此，zset 底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足？

  • SkipList：可以排序，并且可以同时存储 score 和 ele 值（member），但是无法根据 key 查询 val
  • HT（Dict）：可以键值存储，并且可以根据 key 找 value，但是无法排序

所以 ZSet 选择全都要，在 RedisObject 和数据结构中间加了一层结构体 struct zset，如图：

1653992121692

o->encoding 只写了 SKIPLIST，但是其实是两种

1653992172526

此时使用 SkipList 和 Dict 的唯一缺点：内存占用太高

当元素数量不多时，HT 和 SkipList 的优势不明显，而且更耗内存。因此 zset 还会采用 ZipList 结构来节省内存，不过需要 同时满足两个条件：

  1. 元素数量小于 zset_max_ziplist_entries， 默认值 128
  2. 每个元素都小于 zset_max_ziplist_value 字节， 默认值 64

ziplist 本身没有排序功能，而且没有键值对的概念，因此需要有 zset 通过编码实现：

  • ZipList 是连续内存，因此 score 和 element 是紧挨在一起的两个 entry， element 在前，score 在后
  • score 越小越接近队首，score 越大越接近队尾，按照 score 值升序排列

1653992299740

ZSet 创建和新元素插入过程：

image-20231023224645053

既然拥有 ZSet 和 ZipList 两种类型的编码，那么也会和 Set 一样出现编码转换的问题：

image-20231023224837164

可以看到：ZipList 转化为 HT 和 SkipList 的条件除了上列的两个外，还有一个方法：ziplistSafeToAdd () ，内容是若 ZipList 的总大小超过 1G，也会转化为 HT 和 SkipList（ZSet 和 Hash 都这样），但是正常情况下，128 * 64 < 1G

12. Hash

hash 结构如下：

1653992339937

zset 集合如下：

1653992360355

Hash 结构与 Redis 中的 Zset 非常类似：

  • 都是键值存储
  • 都需求根据键获取值
  • 键必须唯一

区别如下：

  • zset 的键是 member，值是 score；hash 的键和值都是任意值
  • zset 要根据 score 排序；hash 则无需排序

因此，Hash 底层采用的编码与 Zset 也基本一致，只需要把排序有关的 SkipList 去掉即可：

  • Hash 结构默认采用 ZipList 编码，用以节省内存。 ZipList 中相邻的两个 entry 分别保存 field 和 value
  • 当数据量较大时，Hash 结构会转为 HT 编码，也就是 Dict，触发条件有两个：
    • ZipList 中的元素数量超过了 hash-max-ziplist-entries（默认 512）
    • ZipList 中的任意 entry 大小超过了 hash-max-ziplist-value（默认 64 字节）

当满足上面两个条件其中之⼀的时候，Redis 就使⽤ dict 字典来实现 hash

1653992413406

image-20231025001845044

image-20231025002529678

image-20231025143251031

可以看到：ZipList 转化为 HT 的条件除了上列的两个外，还有一个方法：ziplistSafeToAdd ()，内容是若 ZipList 的总大小超过 1G，也会转化为 HT（ZSet 和 Hash 都这样）

Redis 的 hash 之所以这样设计，是因为当 ziplist 变得很⼤的时候，它有如下几个缺点：

  • 每次插⼊或修改引发的 realloc 操作会有更⼤的概率造成内存拷贝，从而降低性能
  • ⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据
  • 当 ziplist 数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为 ziplist 上的查找需要进行遍历

总之，ziplist 本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存 realloc，可能导致内存拷贝

🌟 如果您喜欢我的文章，欢迎赞赏支持，您的支持是我创作的最大动力！🌟
🖋 作者：Enndfp
🔗链接：https://blog.enndfp.cn
📜版权声明：您可以自由转载，但请务必注明原文地址，感谢您的尊重与支持~
Redis
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Redis 分布式缓存

							
							

							
Redis 通讯协议和内存回收

							
							

							
Redis 网络模型

							
							

							
缓存

							
							

							
命令