本文基于黑马2022的Redis课程原理篇编写，课程地址：黑马程序员Redis入门到实战教程，深度透析redis底层原理+redis分布式锁+企业解决方案+黑马点评实战项目

动态字符串SDS

Redis中保存的Key是字符串，Value往往是字符串或者其他复杂数据结构。可见字符串是Redis中最常用的一种数据结构。

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

• 获取字符串长度需要遍历计算（C里的字符串是以"\0"结尾的字符数组，必须从头遍历才能确定长度，时间复杂度为O(N)）

• 非二进制安全（因为"\0"被当作结束标志，所以不能存储包含"\0"的二进制数据）

• 修改效率低且不安全（缺乏空间预分配机制，修改时容易发生缓冲区溢出或内存浪费）

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

例如，我们执行命令：set name 缘鱼

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

Redis是C语言实现的，其中SDS是一个结构体，源码如下，其中的8表示8个比特位：

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

现在读这个sds结构的字符串时会直接从数据部分读len个字符，这样就不存在二进制安全问题了，而且字符串长度也是包含在header中的，无需再计算

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

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

• 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；（扩展后为hi,Amy，6个字节，所以新空间为6×2+1=13字节）
• 如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

alloc申请的长度不包含结束表示"\0"，所以是12，但新空间确实是13字节

总结一下SDS结构的优点如下：

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

IntSet

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

结构如下：

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

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

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

• encoding：4字节
• length：4字节
• contents：2字节（每个元素占16bit） × 3（存了3个整数） = 6字节

并且因为数组中每个元素的大小都是一致的，只要知道元素的index就能快速定位到对应的地址

intset还具有自动升级功能

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

向该其中添加一个数字：50000，这个数字超出了int16_t的范围（16位有符号整数，其取值范围是：-32,768 ~ 32,767），intset会自动升级编码方式到合适的大小。

以当前案例来说流程如下：

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

小总结：

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

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

Dict

Dict介绍

Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。 Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask（效果和求余一样，但效率更高）来计算元素应该存储到数组中的哪个索引位置。

现在存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置：

假如又要存储一个k2=v2，计算后的数组角标位置同样是1：

Dict扩容

Hashtable（Dictionary的实现类之一）采用数组结合单向链表的实现。当集合中元素较多时，可能增加哈希冲突的概率，导致链表变长，从而影响查询效率。

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

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

Dict收缩

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

rehash

当哈希表需要扩容或收缩时，可能会创建新的哈希表，导致哈希表的 size 和 sizemask 变化，而 key 的查询索引与 sizemask 有关。因此必须对哈希表中的每一个 key 重新计算索引，插入新的哈希表，这个过程称为 rehash。过程是这样的：

• 计算新哈希表的 realSize，值取决于当前要做的是扩容还是收缩：
  • 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
  • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
• 按照新的 realSize 申请内存空间，创建 dictht，并赋值给 dict.ht[1]。
• 设置 dict.rehashidx = 0，标示开始 rehash。
• 将 dict.ht[0] 中的每一个 dictEntry 都重新 rehash（计算新索引并插入）到 dict.ht[1]。
• 将 dict.ht[1] 赋值给 dict.ht[0]，给 dict.ht[1] 初始化为空哈希表，然后释放被替换出来的旧哈希表的内存。
• 将 rehashidx 赋值为 -1，代表 rehash 结束。
• 在 rehash 过程中，新增操作则直接写入 ht[1]；查询、修改和删除操作则会先在 dict.ht[0] 中查找，如果没找到再在 dict.ht[1] 中查找并执行。这样可以确保 ht[0] 的数据只减不增，随着 rehash 过程的推进最终为空。

举个例子，整个过程可以描述成：

当前有一个大小为4且已装满的数组，现在需要新插入一个元素，所以就需要rehash：

创建新数组并迁移元素：

修改ht[0]中的指针：

但如果数据量特别大，rehash的时间需要很久，期间可能就会导致主线程阻塞，所以Dict的rehash是分多次、渐进式地完成，因此称为渐进式rehash

所以前面描述过程的第四点其实不够准确：

• 将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]

也就是每次只迁移一个角标的链表，直至迁移完成

问题又来了，迁移过程中需要执行增删改查应该去哪里操作？

答案是，查询、修改、删除操作时，ht[0]和ht[1]都要执行，因为数据存在的话，要么在ht[0]要么在ht[1]。若是新增操作，则直接写入ht[1]中，这样就能确保ht[0]的数据只减不增，随着rehash最终为空

ZipList

简介

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

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

ZipListEntry

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

• previous_entry_length：前一节点的长度，占1个或5个字节。

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

• encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节

• contents：负责保存节点的数据，可以是字符串或整数

Encoding编码

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

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

第一种以00开头的编码，编码长度为1字节，去掉高2位用于记录编码格式的00还剩6个比特位，6个比特位能表示的最大值是2的6次方减1，即63，所以第一种编码形式能记录的最大字节数为63字节

同理，第二种以01开头的编码，编码长度为2字节，去掉01还剩14个比特位，所以能记录字符串的最大字节数为2的14次方减1，即16383字节

注意，第三种以10开头的编码，编码长度为5字节，但第一个字节空着作为标识，用后面4个字节来记录字符串，所以能记录的字符串大小为2的32次方减1，即4294967295字节

例如，现在要保存字符串：“ab”和 “bc”，因为一个字符占用1字节，“ab”和 “bc”分别占用2字节，所以用00开头，长度为1字节的编码就行

所以“ab”这个字符串的entry如下，共占用4字节：

所以“ab”和 “bc”的entry如下：

所以保存了“ab”和 “bc”的整个ZipList结构如下：

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

当存的整数在0到12之间时（闭区间），就可以用最后一种编码形式，既是编码也记录了数值

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

所以保存了2和5的整个ZipList结构如下：

连锁更新问题

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

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

假设现在有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图所示：

现在要在队首插入一个长度为254字节的entry，所以原本的第一个，即现在的第二个entry的previous_entry_length需要从1个字节变成5个字节，导致这个entry的长度从250字节变成254字节，进而导致它的下一个entry也需要修改previous_entry_length的长度，以此类推，会产生一连串的空间拓展操作：

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

虽然发生的概率不大，但还是可能会发生，所以Redis 从 7.0 版本开始正式使用 ListPack 替代了 ZipList。

在 Redis 6.2 中，ListPack 已被引入并用于 Stream 数据结构的内部存储，但尚未全面替代 ZipList。直到 7.0，List、Hash、ZSet 等数据结构中的 ZipList 才被统一替换为 ListPack。

小结

ZipList特性：

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

ListPack

简介

ListPack（列表包）是Redis用来替代ZipList的一种紧凑型数据结构。与ZipList类似，它也是一块连续的内存空间，但ListPack在内部节点的设计上做了重大改进，彻底解决了ZipList的连锁更新问题。在Redis 7.0之后，List、Hash、ZSet等数据结构的底层编码都统一使用了ListPack（针对小数据量场景）。

整体结构

与ZipList不同，ListPack不再存储zltail（尾节点偏移量）和zllen（节点数量）这些头部元数据（Header Metadata），它只记录整个结构的总长度。这使得ListPack的结构更加扁平化。

ListPack 由以下部分组成：

Entry结构

每个元素由三部分组成：

编码类型

单字节编码

多字节编码

element-total-len

element-total-len表示前两部分（encoding-type + element-data）占用的字节数，占1-5字节不等。

编码规则

• 每个字节的第一位用0或1来表示当前字节是否为最后一字节：
  • 0 表示是最后一个字节
  • 1 表示不是最后一个字节
• 剩余字节逻辑上拼接在一起来存放无符号整数表示字节数
• 采用的是大端模式，即高字节保存在低地址，低字节保存在高地址

作用

这个字段主要是为了反向遍历而设计的。通过element-total-len，可以从后向前逐个解析entry，而不需要像ziplist那样依赖previous_entry_length字段。

示例演示

假设要用listpack结构存放字符串"hello"以及整数1024，表示如下图：

Entry-1（字符串"hello"）：

• encoding-type：10000101，其中前两位10表示这是短字符串编码，后6位000101=5表示字符串长度
• element-data：hello（5个字节）
• element-total-len：00000110，第一位为0表示这是最后一个字节，剩余7位0000110=6表示前两部分共6字节

Entry-2（整数1024）：

• encoding-type：11000100 00000000，前三位110表示这是13位整数编码，后13位00100 00000000=1024
• element-data：无（整数直接编码在encoding-type中）
• element-total-len：00000010，第一位为0表示这是最后一个字节，剩余7位0000010=2表示前两部分共2字节

ListPack对比ZipList

小结

1. ListPack是Redis 7.0引入的新数据结构，用于替代ziplist
2. 解决了连锁更新问题：每个entry只记录自己的长度，不记录前一个entry的长度
3. 内存紧凑：保留了ziplist内存紧凑的优点
4. 支持反向遍历：通过element-total-len字段实现
5. 多种编码方式：支持不同大小的整数和字符串，优化内存使用

QuickList

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

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

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

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

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

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

从 Redis 7.0 版本开始，QuickList 的每个节点已经从 ZipList 替换成了 ListPack

QuickList 是 Redis 在 3.2 版本引入的一种复合数据结构，本质是一个双向链表，但链表中每个节点存放的不是单个元素，而是一块连续内存的 ZipList（7.0 后改为 ListPack），这些小块内存各自紧凑存储多个元素，再通过链表指针串联起来，从而在灵活性和内存效率之间取得平衡——既避免了纯链表指针开销大、碎片多的问题，又解决了单一大 ZipList 申请大块连续内存时效率低下的痛点。

为了避免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

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

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

Redis 使用 LZF（Lempel-Ziv-Free） 算法进行实时压缩/解压，这是一种轻量级的无损压缩算法。

简单来说，压缩是把整个 ZipList/ListPack 节点用 LZF 算法压缩成更小的二进制块，首尾节点始终保持解压状态以保证常用操作性能，中间的"冷"数据压缩以节省内存。

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

内存结构大致如下，此时compress为1，所以首尾不压缩，中间两个节点压缩：

QuickList的特点：

• 是一个节点为ZipList的双向链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 限制了ZipList大小，避免了大块连续内存分配带来的性能问题
• 中间节点可以压缩，进一步节省了内存

SkipList

跳表是一种基于有序链表 + 多级索引的动态数据结构，通过对原始有序链表层层抽取索引节点，构建出一条条"快速通道"，使得查找不再需要逐个遍历，而是可以从最高层索引开始逐层向下逼近目标位置

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

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

指针示意图：

查找时，从最高层出发，每遇到"下一个节点比目标大"就下降一层，直到在原始链表定位到目标

核心就是用空间换时间，在有序链表之上模拟"二分查找"

索引如何动态更新？

跳表通过 随机函数（类似抛硬币）来决定新插入的节点要"晋升"到第几层索引：

• 每次插入时随机生成一个层数 K
• 将该节点添加到第 1 层到第 K 层索引中
• 这种方式避免了像平衡树那样做复杂的全局旋转调整，实现简单得多

SkipList节点源码：

SkipList内存结构示意图：

注意，虽然图中level[]中的forward指向的是下一个Level，但实际上每一级指针指向的都是这个Level所在的节点(SkipListNode)

SkipList的特点：

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

RedisObject

robj简介

什么是redisObject？

从Redis的使用者的角度来看，⼀个Redis节点包含多个database（非cluster模式下默认是16个，cluster模式下只能是1个），而一个database维护了从key space到object space的映射关系。

这个映射关系的key是string类型，⽽value可以是多种数据类型，比如： string, list, hash、set、sorted set等。可以看到，key的类型固定是string，而value可能的类型是多个。 ⽽从Redis内部实现的⾓度来看，database内的这个映射关系是用⼀个dict来维护的。

dict的key同样用一个redisObject来表达就够了，因为key类型固定是string，其内部的数据结构就是动态字符串sds。而value则比较复杂，为了在同⼀个dict内能够存储不同类型的value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是robj，全名是redisObject。

上面这些内容可能有点抽象，下面将Redis类比为一个仓库来讲解一遍：

想象你在管理一个大型仓库（Redis 数据库），仓库里存放着各种各样的货物。但是仓库有一个规定：所有货物必须装在标准集装箱里才能入库，不管你装的是水果、家具、书籍还是电子设备，外层统一用同一个规格的集装箱。这个标准集装箱，就是 redisObject。

为什么需要redisObject？

Redis 的数据库底层实际上是一个哈希表（dict），就像一个巨大的货架，每个货位上贴着标签（key），里面放着货物（value）。

现在问题来了：货架是统一的，但货物千差万别——有的货物是手机（string），有的是一整箱零件（list），有的是一摞订单（hash），有的是按价格排好的一组商品（sorted set）。如果每种货物都用自己的包装方式，货架（dict）就没法统一管理了。

解决方案：给每种货物外面都套一个一模一样的集装箱外壳（redisObject）。货架（dict）只需要认这个标准外壳就行，至于里面具体装的是什么，打开外壳再细看。

仓库概念	Redis 概念	说明
仓库	Redis Database	一个数据库实例，默认有 16 个
货架	dict（哈希表）	底层存储 key → value 映射的容器
货架标签	key（SDS）	key 永远是字符串，统一标签格式
集装箱	redisObject	套在 value 外面的通用包装
箱内货物	真正数据	SDS / 跳表 / 压缩列表……
箱体标签「类型」	type 字段	STRING / LIST / HASH / SET / ZSET
箱内打包方式	encoding 字段	raw / int / ziplist / skiplist……

简单来说，redisObject 就是一个"万能外壳"，它让底层的哈希表（dict）可以用完全相同的方式去管理 string、list、hash、set、zset 这些完全不同类型的数据——哈希表只认 redisObject，至于里面具体是什么，由 type 和 encoding 这两个"标签"来告诉上层应该怎么解读。

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

编码方式

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

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

五种基础数据类型

String

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

• 当字符串长度较长或无法用其他编码时，会采用 RAW 编码，基于简单动态字符串（SDS）实现，存储上限为 512MB。

• 如果字符串长度小于等于 44 字节，则会采用 EMBSTR 编码（在 Redis 3.2 之前，阈值曾为 39 字节），此时 object head 与 SDS 是一段连续空间，申请内存时只需要一次内存分配。

• 如果存储的字符串是整数值，并且可以用 long 类型表示（即值在 LONG_MIN 与 LONG_MAX 之间），则会采用 INT 编码：直接将该整数值保存在 RedisObject 的 ptr 指针中（将整数值直接转为 void* 存进 ptr，ptr 的值就是该整数，刚好 8 字节），不再需要 SDS 了。

确切地说，String 在 Redis 中是用一个 robj（redisObject） 来表示的。这个 robj 可能编码成以下三种内部表示：

不同命令对三种编码的处理方式

数值操作（incr / decr）：

• INT 编码 ，则直接进行加减，无需转换
• RAW / EMBSTR 编码，则先尝试把 SDS 字符串转成 long long，转成功后再进行加减

字符串操作（append / setbit / getrange）：

这类命令把值始终当作字符串的字节序列来处理，而不是把值当作内部存储的 long long 来操作。即使当前编码是 OBJ_ENCODING_INT，Redis 也会先把 long long 转回 SDS 字符串，再执行操作。

为什么必须把 long long 转回 SDS 字符串？

假设字符串的值是 “32”，按字符串字节序列来解读：

字符 ‘3’，其ASCII码是51（十进制），二进制表示为0 0 1 1 0 0 1 1

字符 ‘2’，其ASCII码是50（十进制），二进制表示为0 0 1 1 0 0 1 0

执行 SETBIT key 7 0 时，把第 7 位（从0开始数）从 1 改为 0，结果为字符串"22"，符合预期

如果把值当作 long long 整数 32 来处理，其 64 位表示为 0x0000000000000020。在内存中（小端序）的实际字节排列是：

1
2

地址低 → 地址高
0x20   0x00   0x00   0x00   0x00   0x00   0x00   0x00

第一个字节是 0x20，以二进制展开就是0 0 1 0 0 0 0 0，此时第7位（从0开始数，也就是最后一位）本来就是0，执行 SETBIT key 7 0 后，结果不变，依旧是字符串"32"，与预期不符

两种解读方式下，同一个 bit 位置对应的是完全不同的含义，所以直接对 long long 做位操作会得到错误结果。这就是为什么 append、setbit、getrange 这些命令会先把 long long 整数转成 SDS 字符串，再进行操作。

List

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

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

• LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
• ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
• ListPack：列表包，可以从双端访问，内存占用低，存储上限低
• QuickList：LinkedList + ZipList/ListPack，可以从双端访问，内存占用较低，包含多个ZipList/ListPack，存储上限高

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

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

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

• 在 7.0之后，将QuickList中的ZipList替换为ListPack，下图由AI生成，仅供参考：

Set

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

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

可以看出，Set对查询元素的效率要求非常高（需要频繁判断元素是否存在），什么样的数据结构可以满足？ HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）

• Set是Redis中的集合，不保证元素有序，可以满足元素唯一、查询效率极高。当元素数量较多或不满足紧凑编码条件时，Set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为NULL。
• 如果存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries（默认512），Set会采用IntSet编码，以节省内存。后续每次插入元素都会再次判断是否符合条件，若不符合则会转换为HT编码。

流程演示：

现有一个IntSet编码的Set集合，现在要往里面插入一个字符串"m1"

会先转换为HT编码，然后再向其中插入这个字符串

ZSet

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

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

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

• SkipList：可以排序，并且可以同时存储score和element（member）
• HT（Dict）：可以键值存储，并且可以根据key找value

所以ZSet底层由SkipList负责排序和范围查询，HT负责维护member到score的映射并保证唯一性

为什么单独一种结构不够？

先说 SkipList：

• 它可以按 score 排序、支持范围查询（ZRANGE、ZRANGEBYSCORE），这些都很完美。
• 但它的致命弱点是：按 member 查找时需要遍历。如果要查某个 member 的 score（ZSCORE），或者更新/删除某个已有 member，SkipList 只能从头一个一个找，O(n)，太慢。

再说 HashTable：

• 它可以 O(1) 按 member 查 score，而且 key 唯一天然保证了 member 不重复。
• 但它无法排序，做不了 ZRANGE（按排名返回）、ZRANGEBYSCORE（按分数范围返回）这类操作。

所以结论是：

• SkipList 只管排序和范围查询：按 score 排序存储，支撑 ZRANGE、ZRANGEBYSCORE 等操作。
• HashTable 只管 member → score 的快速映射：O(1) 找到某个 member 对应的 score，同时利用 key 唯一性保证 member 不重复。当需要更新一个已有 member 的 score 时，HT 先 O(1) 查到旧 score，再去 SkipList 里定位并修改节点——没有 HT 这一步就会退化成 O(n)。

两者各司其职，互相补齐对方的短板。不够由于编码只能写一种，源码里写的编码格式只有SkipList

结构如下：

当元素数量不多时，HT 和 SkipList 的优势不明显，而且更耗内存。因此 ZSet 在数据量较小时还会采用 ZipList（7.0 前）/ ListPack（7.0 后）结构来节省内存，不过需要同时满足两个条件：

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

ZipList/ListPack 本身只是紧凑的连续内存结构，不提供排序和键值对语义。因此在 ZSet 使用这种编码时，由 ZSet 的代码逻辑来手动维护：

插入时遍历找到正确的排序位置，member 和 score 成对紧挨存储（member 在前、score 在后），整体按 score 升序排列。元素少时 O(n) 的插入成本完全可以接受，换来的是内存的显著节省。

ListPack同理。

Hash

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

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

区别如下：

• ZSet 的键是 member（字符串类型），值是 score（数字类型）；Hash 的键和值都是字符串，但值不像 ZSet 那样被约束为数字
• ZSet 要根据 score 排序；Hash 则无需排序

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

Hash结构默认采用 ZipList（7.0 前）/ ListPack（7.0 后）编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value

当数据量增大，满足以下任一条件时，Hash 结构会从 ZipList/ListPack 编码转为 HT（Dict）编码：

• 元素数量超过了 hash-max-ziplist-entries（默认 512）
• field 或 value 的长度超过了 hash-max-ziplist-value（默认 64 字节）

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

• 每次插入或修改引发的 realloc 操作会有更大的概率造成内存拷贝，从而降低性能。
• 一旦发生内存拷贝，拷贝成本也相应增加，因为要拷贝更大的一块数据。
• 当 ZipList 数据项过多时，在上面查找指定数据项的性能会变得很低，因为 ZipList 的查找需要遍历。

总之，ZipList 设计上本就是各数据项紧密排列在连续内存空间中，这种结构并不擅长修改操作。一旦数据发生改动，就可能引发内存 realloc，进而导致内存拷贝。

什么是内存 realloc 和内存拷贝?

用一个类比来解释：

内存 realloc

C 语言中，realloc 的作用是"给已分配的内存扩容"。比如你原来申请了 64 字节的连续内存，现在想存更多数据需要 128 字节，你就调用 realloc。

realloc 分两种情况：

• 原地扩容：如果当前内存后面还有空闲空间，直接往后延伸就行，不需要搬数据。这是最理想的情况。
• 搬新家：如果后面没有多余空间了，realloc 会另找一块足够大的连续内存，把旧数据全部搬过去，然后释放旧内存。

内存拷贝

就是上面"搬新家"时发生的动作——把旧内存中的数据逐字节复制到新内存中。数据量越大，拷贝越慢。ZipList 是个连续内存块，一旦某个元素要扩容（比如把短的 value 改长），就可能触发 realloc，然后整块内存全部拷贝一遍。元素越多、总内存越大，这个开销就越不可接受。

这也是为什么 Redis 在小数据量时用 ZipList（省内存，拷贝成本低），大数据量时切换为 HT（链表/跳表的修改成本是 O(1)，不存在整块拷贝问题）。

默认使用ZipList时：

被转换为HT编码时：