Redis 原理学习笔记：SDS（动态字符串）

1. 什么是 SDS？

Redis 内部并没有直接使用 C 语言的 char* 字符串，而是使用自己实现的 SDS（Simple Dynamic String，简单动态字符串）。

SDS 是 Redis 字符串类型（String）的底层存储结构，不只是为了存储文本值，还作为很多复杂结构（如 Hash、List、ZSet）的底层基础组件。

简单说：

SDS 是对 C 字符串的安全、高效扩展，是 Redis 内部所有字符串操作的基础。

---

2. 为什么 Redis 不使用 C 的原生字符串？

C 的原生字符串（char*）存在严重缺陷：

2.1 不记录长度（strlen 需要 O(n)`）

每次获取长度都要遍历全部字符。

2.2 容易发生缓冲区溢出（Buffer Overflow）

例如使用 strcat 时，如果目标空间不足，会直接写越界导致程序崩溃。

2.3 扩容效率低

需要自己 malloc/free。

2.4 二进制不安全（不支持 \0）

遇到 \0 会被认为字符串结束。

Redis 作为高性能系统必须解决这些问题，因此设计 SDS。

---

3. SDS 的结构

SDS 的核心数据结构如下：

+---------+---------+---------+---------+
|  len    |   alloc |  flags  |  buf[]  |
+---------+---------+---------+---------+

不同长度类型（sdshdr5/8/16/32/64）略有差异，但核心字段一致：

字段	说明
len	字符串实际长度（O(1) 获取）
alloc	已分配的 buf 容量（不含结尾）
flags	类型标识（区分不同 hdr）
buf[]	真正存储字符串内容，最后统一加 \0

例如 SDS 实际内容 "hello"：

len=5
alloc=8
flags=2
buf="hello\0"

---

4. SDS 的核心优势（比 C 字符串强太多）

4.1 O(1) 获取长度（len 字段）

C 字符串要遍历，SDS 是直接存储。

strlen(char*) → O(n)
sdslen(sds) → O(1)

4.2 自动扩容（避免 buffer overflow）

写入内容不足时自动 realloc 扩容。

4.3 二进制安全（支持任意字节）

即使包含 \0 也不会截断。

4.4 避免多次内存分配（预分配，减少碎片）

4.5 杜绝越界问题（保证安全）

---

5. SDS 的空间预分配策略（非常重要）

当 SDS 扩容时，采用较为智能的策略：

5.1 小于 1MB 的字符串：

alloc = len * 2

例如：

• 写入 10 字节 → 分配 20 字节
• 写入 100 字节 → 分配 200 字节

5.2 大于 1MB 的字符串：

alloc = len + 1MB

这是为了避免非常大的字符串导致内存浪费。

---

6. SDS 的惰性释放（Lazy Free）

当字符串缩短时：

len 减少
alloc 不变

不会立即释放多余空间，称为“惰性空间释放”。

优点：

• 避免频繁 malloc/free
• 多线程环境更安全

如果需要主动收缩 SDS，可调用：

sdsRemoveFreeSpace(s)

---

7. SDS 支持的多种头结构（sdshdr5/8/16/32/64）

Redis 通过不同结构头减少内存消耗：

类型	最大长度	适用
sdshdr5	31字节	小字符串（最节省空间）
sdshdr8	255 字节	小型 key/value
sdshdr16	65KB	中等大小字符串
sdshdr32	4GB	大字符串
sdshdr64	超大（几乎用不到）	需要大空间的 value

Redis 会自动选择最佳 hdr 类型。

---

8. SDS 与 Redis String 的关系（重要）

Redis String 的编码方式包括：

• int
• embstr
• raw

其中：

• embstr / raw 的底层都是 SDS
• Redis 只是封装 SDS 作为 VALUE 存储

即：

String → RedisObject → SDS

SDS 是 String 的真正底层。

---

Redis 原理学习笔记：intset（整数集合）

一、intset 是什么？

intset（Integer Set）是 Redis 内部用于保存整数元素的集合的数据结构，是 Set 类型（无序集合）的一种底层编码方式。

当 Redis 的 Set 中所有元素都是整数、且数量较少时，Set 会自动使用 intset 存储，以节省大量内存。

当数量变大或包含非整数时，会自动转换为 hashtable。

本质上：

intset = 用连续内存数组保存有序整数集合 + 自动升级类型的高性能轻量级数据结构

---

二、intset 的数据结构布局（内部结构）

intset 底层结构如下：

typedef struct intset {
    uint32_t encoding;   // 编码方式：INTSET_ENC_INT16 / 32 / 64
    uint32_t length;     // 元素个数
    int8_t contents[];   // 按升序排列的整数数组
} intset;

字段说明：

字段	说明
encoding	元素整数类型（16/32/64位）
length	当前集合中的元素数量
contents	实际存储整数的连续数组，升序排序

三种编码方式：

encoding	对应 C 类型	范围
INTSET_ENC_INT16	int16_t	-32768 ~ 32767
INTSET_ENC_INT32	int32_t	±21 亿
INTSET_ENC_INT64	int64_t	非常大

---

三、intset 的特点

1. 紧凑存储（节省内存）

• 连续内存数组
• 不存储 hash/separate chaining 等额外开销

比 hashtable 节省大量内存。

2. 数据有序，方便二分查找

查找复杂度为：

O(log N)

比一般链式结构更快。

3. 自动升级（但不降级）

如果插入的数超过当前 bit 范围，会自动执行：

当前 encoding = int16

插入值 50000（超过 int16 范围）
→ 升级为 int32

升级步骤：

1. 扩容 contents 数组
2. 把原元素全部复制为 32bit
3. 插入新元素

升级会导致一次性内存开销，但升级后插入再不会重复升级。

注意：intset 不会降级，原有 encoding 会保持不变。

---

四、intset 的内部操作原理

1. 查找（Find）

采用二分查找，因为 contents 是升序：

O(log N)

---

2. 插入（Insert）

步骤：

1. 二分查找定位插入位置
2. 如果编码不够，触发升级
3. 扩容 contents
4. 将插入位置后的元素整体右移
5. 写入新值

复杂度：

O(N)

（因为可能移动数组元素）

---

3. 删除（Remove）

1. 二分查找定位元素
2. 删除元素并整体左移 contents

复杂度：

O(N)

---

五、intset 的自动升级机制（非常重要）

规则：

插入的整数超过当前 encoding 范围 → 自动升级

例如：

• 当前 encoding = int16
• 插入值 = 80000
  → 升级到 int32

升级过程：

1. 为 int32 * length 分配新空间
2. 将旧数组按 int32 重写
3. 插入新元素
4. 释放旧内存

升级后的性能影响：

• 升级过程有一次性开销
• 升级后读取更快（因为类型更大）
• 升级后再插入不会重复升级
• 不支持降级（编码永不缩小）

---

六、intset 与 Set（sds+dict）切换规则

Redis 的 Set 类型可能使用两种编码：

编码	说明
intset	所有元素是整数、数量不大
hashtable	元素包含非整数 或 数量过大

Redis 自动决定是否使用 intset：

规则：

1. 所有元素必须是整数
2. 元素个数 ≤ 配置的阈值（默认 512）

配置项：

set-max-intset-entries 512

若超过 512，则自动从：

intset → hashtable（dict）

该转换为自动完成。

---

八、intset 的优缺点

优点

1. 极低内存占用（连续数组 + 紧凑编码）
2. 查找 O(logN)（二分查找）
3. 自动编码选择（16/32/64 位）
4. 适合小集合（小于 512 个）

缺点

1. 插入/删除是 O(N)，大量元素会很慢
2. 升级时会触发内存复制，可能有延迟
3. 不支持降级（可能浪费空间）
4. 不适合大规模 Set（要用 Hashtable）

下面为你整理一份系统、全面、适合深入学习 Redis 内部原理的 dict、ziplist、quicklist、skiplist 学习笔记。
内容从底层结构、应用场景、时间复杂度、特点与常见面试点入手，是学习 Redis 数据结构必备的基础资料。

---

Redis 底层数据结构dict学习笔记

1. dict（哈希表）

dict 是 Redis 哈希（Hash）、集合（Set）、过期字典等多处关键结构的底层实现。

1.1 dict 的结构

dict 结构包含两张哈希表：ht[0] 和 ht[1]。

dict
├── dictht ht[0]
└── dictht ht[1]（rehash 时使用）

dictht（哈希表）结构：

dictht
├── size         哈希表大小（2 的次幂）
├── sizemask     掩码，用于计算索引，等于size - 1
├── table[]      哈希桶数组（指向链表）
└── used         已存储键值对数量

哈希桶中的元素是链地址法（拉链法）：

table[i] → dictEntry → dictEntry → ...

dictEntry 保存：

key（SDS）  
value（指针）  
next（指向下一个 dictEntry）

---

1.2 dict 的核心特点

1) 时间复杂度

平均：

查找、插入、删除：O(1)

最坏：

链表太长 → 退化成 O(n)

但 Redis 采用渐进式 rehash，很少出现性能退化。

---

1.3 渐进式 rehash（非常重要）

当负载因子过大（(>=1 并且 没有BGSAVE等后台进程运行) || > 5），Redis 会对哈希表进行扩容。

rehash 不是一次性完成，而是：

分多次、渐进式地完成

过程：

1. 扩容新表 ht[1]
2. 每次 dict 操作时迁移一部分节点
3. 最终迁移完成后关闭 rehash

优势：

• 避免一次性 rehash 导致阻塞
• 保证 Redis 的高性能特性

---

1.4 dict 的使用场景

• Hash 类型（底层从 ziplist 到 dict）
• Set 类型
• 过期字典（键过期管理）
• 数据库保存 key-value 结构

---

1.5 dict 的优缺点

优点：

• 查找 O(1)，极高性能
• 渐进式 rehash 避免卡顿
• 使用 SDS 作为 key，避免冲突

缺点：

• 内存占用较大（链表、指针）
• 适合大集合，不适合小对象