Redis设计与实现——数据结构与对象
简单动态字符串（SDS）
SDS 的结构定义
- len：记录当前字符串的实际长度（不包含
\0），获取长度的时间复杂度为 O(1)。 - free：记录未使用的空间大小，用于优化内存分配。
- buf[]：实际存储字符的数组，末尾自动追加
\0（兼容 C 字符串函数）。
SDS 的核心特性
-
预分配与惰性释放
-
空间预分配：当 SDS 需要扩容时，Redis 会额外分配未使用空间（
free）以减少内存重分配次数：若扩容后
len< 1MB：分配len的等量空间（总空间 =len+free+ 1 = 2 *len+ 1）。若扩容后
len≥ 1MB：固定分配 1MB 未使用空间（总空间 =len+ 1MB + 1）。 -
惰性空间释放：当 SDS 缩短时，不立即回收内存，而是通过
free记录剩余空间，供后续操作复用。
-
-
二进制安全：SDS 的
buf可以存储任意二进制数据（包括\0），因为长度由len字段记录，而非依赖\0判断结束。 -
兼容 C 字符串函数：SDS 的
buf末尾自动追加\0，可直接使用<string.h>中的函数（如strcmp()）。 -
杜绝缓冲区溢出：所有修改操作（如拼接）前会检查剩余空间（
free），不足时自动扩容。
链表
链表的定义与结构
- 链表结点
- 双向链接：每个节点包含指向前驱和后继的指针，支持双向遍历。
- 值类型灵活：
value字段为void*类型，可指向任意数据（字符串、整数、对象等）。
- 链表对象（
list）- 头尾指针：直接访问头尾节点，使
LPUSH、RPUSH等操作时间复杂度为 O(1)。 - 长度字段：
len直接记录节点数量，无需遍历即可获取长度（时间复杂度 O(1)）。 - 多态性支持：通过函数指针实现值的复制、释放和比较，支持不同类型数据的存储。
- 头尾指针：直接访问头尾节点，使
链表的特性
-
双向无环链表
-
双向：每个节点包含前驱和后继指针，支持双向遍历。
-
无环：头节点的
prev和尾节点的next均为NULL，避免循环引用。
-
-
高效的头尾操作
-
头部插入/删除：直接通过
list->head操作，时间复杂度 O(1)。 -
尾部插入/删除：直接通过
list->tail操作，时间复杂度 O(1)。
-
-
多态性与类型安全
-
存储任意数据：节点值通过
void*指针存储，支持字符串、整数、对象等。 -
自定义函数：通过
dup、free、match函数实现类型相关的操作，例如：dup：深拷贝节点值（如复制一个 SDS 字符串）。free：释放节点值占用的内存（如销毁一个 Redis 对象）。match：比较节点值与给定值是否相等。
-
字典
字典的结构定义
-
哈希表（
dictht）- size：哈希表的大小，初始为 4，每次扩容为当前大小的 2 倍。
- sizemask：哈希掩码，用于计算键的索引（
hash & sizemask）。 - table：指向哈希桶数组的指针，每个桶是一个链表（链地址法）。
-
哈希节点（
dictEntry）- key：指向键的指针（如 SDS 字符串）。
- v：值的联合体，支持指针、整数、浮点数等类型。
- next：指向冲突链中的下一个节点。
-
字典对象（
dict）- ht[2]：两个哈希表，正常操作使用
ht[0]，Rehash 时逐步迁移到ht[1]。 - rehashidx：记录 Rehash 的进度（从 0 到
ht[0].size-1）。 - type：指向
dictType结构的指针，包含键和值的操作函数（如哈希函数、键比较函数）。
- ht[2]：两个哈希表，正常操作使用
核心机制与算法
-
哈希函数：Redis 默认使用 MurmurHash2 算法计算键的哈希值。
-
键冲突解决
-
链地址法：哈希冲突的节点通过链表连接，新节点插入链表的头部（时间复杂度 O(1)）。
-
负载因子：
load_factor = ht[0].used / ht[0].size，触发扩容的默认阈值是load_factor ≥ 1（可配置）。
-
-
渐进式 Rehash：当哈希表需要扩容或缩容时，Redis 通过渐进式 Rehash 避免一次性迁移所有数据导致的阻塞：
-
准备阶段：为
ht[1]分配新空间；设置rehashidx = 0，表示 Rehash 开始。 -
迁移阶段：Redis 迁移
ht[0].table[rehashidx]的所有节点到ht[1]；rehashidx递增，直到所有桶迁移完成。 -
完成阶段：释放
ht[0]，将ht[1]设置为ht[0]；重置ht[1]为空表，rehashidx = -1。
-
跳跃表Skiplist
跳跃表的定义与结构
-
跳跃表节点（
zskiplistNode）- ele：存储元素的唯一标识（如用户 ID），类型为 SDS 字符串。
- score：排序分值（如用户的积分），支持浮点数。
- backward：指向前驱节点，用于从尾到头遍历。
- level[]：
forward——指向后继节点的指针；span——当前层到下一个节点的跨度，用于计算元素排名。
-
跳跃表对象（
zskiplist）- header：头节点，包含所有可能的层级（默认 32 层），初始化时各层
forward指向NULL。 - tail：尾节点，支持快速逆序遍历。
- length：记录元素数量，获取长度的时间复杂度为 O(1)。
- level：记录当前跳跃表的最高层，决定查找路径的起始层。
- header：头节点，包含所有可能的层级（默认 32 层），初始化时各层
跳跃表的核心特性
-
多层链表结构
-
层级随机生成：每个节点的层数在插入时随机确定（幂次定律：层数越高概率越低），确保高层级稀疏分布。
-
查找路径优化：从最高层开始查找，逐步降层，跳过大量节点（类似二分查找）。
-
-
排序与唯一性
-
按分值排序：节点按
score升序排列，相同score的节点按ele的字典序排列。 -
成员唯一性：
ele唯一，插入重复ele时直接更新score。
-
-
范围查询支持
-
ZRANGE、ZRANK：利用
span字段快速计算排名或遍历区间。 -
ZREVRANGE：通过
backward指针逆序访问。
-
Redis 中的应用
-
有序集合（Sorted Set）
-
底层实现：当有序集合元素较多时，使用跳跃表（
zset结构包含跳跃表和字典，字典用于 O(1) 查找ele对应的score）。 -
典型命令：
ZADD——插入元素；ZRANGE——按排名范围获取元素；ZRANK——获取元素排名。
-
-
集群节点管理：集群模式下，跳跃表用于维护槽（Slot）与节点的映射关系。
整数集合
整数集合的结构定义
- encoding：编码方式，决定每个元素占用的字节数，
INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64。 - length：集合中元素的数量。
- contents[]：元素的实际存储数组，元素按值从小到大排序，且无重复。
核心机制：动态升级
-
触发条件：当插入一个无法用当前编码表示的整数时，整数集合自动升级编码。
-
升级步骤
- 计算新编码：根据插入值的大小选择最小兼容编码。
- 扩容内存：重新分配空间，计算新编码下的总字节数（
length * new_encoding_size）。 - 数据迁移：从后向前依次将旧元素转换为新编码，避免覆盖问题。
- 插入新元素：根据新元素的值插入到正确位置（保持有序性）。
- 更新结构：修改
encoding字段，完成升级。
Redis 中的应用
- 集合键（Set Key）：当集合元素全为整数且数量小于
set-max-intset-entries（默认512）时，Redis 使用整数集合。 - 性能优化：小规模整数集合的内存效率远超哈希表（如存储 100个int16仅需 200 + 8 字节，而哈希表需至少 100个entry）。
压缩列表Ziplist
压缩列表的结构
-
头部元数据
-
zlbytes（4字节）：整个压缩列表占用的内存字节数。
-
zltail（4字节）：尾节点（最后一个Entry）的偏移量（便于快速定位尾节点）。
-
zllen（2字节）：节点数量（若值 ≤ 65535则为实际数量，否则需遍历计算）。
-
-
节点（Entry）结构
-
prevlen：前驱节点的长度（字节数），用于逆向遍历。
-
encoding：当前节点的数据类型和长度编码。
-
content：实际存储的数据（整数或字节数组）。
-
-
结束标记：0xFF标识压缩列表的结尾。
核心机制与操作
-
编码方式
-
整数编码：根据数值范围选择最小编码（如
int16_t、int24_t、int32_t、int64_t）。 -
字符串编码：短字符串（长度 ≤ 63字节）：
encoding占1字节（2 + 6）；长字符串：encoding占2或5字节，记录长度。
-
-
连锁更新（Cascade Update）
-
触发条件：插入或删除导致某个节点的
prevlen从1字节扩展为5字节（或反之）。 -
影响：可能引发后续多个节点的
prevlen更新，最坏时间复杂度为 O(N^2)。 -
优化：实际场景中概率极低，Redis未做特殊处理。
-
Redis 中的应用
- 列表键（List Key）：当元素均为小整数或短字符串，且数量小于
list-max-ziplist-entries（默认512）时，使用压缩列表。 - 哈希键（Hash Key）：当字段和值均为小数据，且字段数小于
hash-max-ziplist-entries（默认512）时，使用压缩列表。 - 有序集合（Zset）：早期版本中，小规模有序集合使用压缩列表存储元素（分值相邻存储），现已被快速列表（Quicklist）替代。
对象
对象类型（type）
| 类型常量 | 对象类型 | 底层数据结构 | 示例命令 |
|---|---|---|---|
REDIS_STRING | 字符串对象 | SDS、整数、embstr 编码的 SDS | SET, GET, INCR |
REDIS_LIST | 列表对象 | 压缩列表（Ziplist）、双向链表 | LPUSH, RPOP, LRANGE |
REDIS_HASH | 哈希对象 | 压缩列表、字典（Dict） | HSET, HGET, HKEYS |
REDIS_SET | 集合对象 | 整数集合（Intset）、字典 | SADD, SMEMBERS |
REDIS_ZSET | 有序集合对象 | 压缩列表、跳跃表（SkipList）+ 字典 | ZADD, ZRANGE |
编码方式（encoding）
| 编码常量 | 说明 | 适用对象类型 |
|---|---|---|
REDIS_ENCODING_INT | 整数编码（long 类型） | 字符串对象 |
REDIS_ENCODING_EMBSTR | embstr 编码的 SDS（短字符串） | 字符串对象 |
REDIS_ENCODING_RAW | SDS 字符串（长字符串） | 字符串对象 |
REDIS_ENCODING_HT | 字典（哈希表） | 集合、哈希对象 |
REDIS_ENCODING_ZIPLIST | 压缩列表 | 列表、哈希、有序集合对象 |
REDIS_ENCODING_INTSET | 整数集合 | 集合对象 |
REDIS_ENCODING_SKIPLIST | 跳跃表 + 字典 | 有序集合对象 |
REDIS_ENCODING_QUICKLIST | 快速列表（Redis 3.2+，链表+压缩列表） | 列表对象 |
REDIS_ENCODING_STREAM | 流（Stream，Redis 5.0+） | 流对象 |
对象的核心机制
-
类型检查与命令多态
-
类型检查：执行命令前，Redis 检查操作的键的值对象类型是否匹配。
-
多态命令：同一命令对不同编码的对象执行不同操作。
-
-
内存优化：动态编码转换
对象类型 初始编码 转换条件 转换后编码 字符串对象 EMBSTR字符串长度增加至 >44字节 RAW（SDS）列表对象 ZIPLIST元素数量 > list-max-ziplist-entries或元素长度 >list-max-ziplist-valueQUICKLIST哈希对象 ZIPLIST字段数量 > hash-max-ziplist-entries或字段/值长度 >hash-max-ziplist-valueHT（字典）集合对象 INTSET插入非整数元素或元素数量 > set-max-intset-entries（默认512）HT（字典）有序集合对象 ZIPLIST元素数量 > zset-max-ziplist-entries或元素长度 >zset-max-ziplist-valueSKIPLIST+ 字典 -
内存管理：引用计数与共享对象
-
引用计数（
refcount）对象被创建时
refcount=1。对象被引用时
refcount++（如被加入数据库、被客户端缓存）。对象被解除引用时
refcount--，当refcount=0时释放内存。
-
-
共享对象：Redis 预先创建
0~9999的整数对象供全局共享，减少重复创建。 -
空转时间（
lru）与淘汰策略-
LRU 模式：
lru字段记录对象最后一次被访问的时间戳（精度为秒），用于volatile-lru或allkeys-lru淘汰策略。 -
LFU 模式：
lru字段分为两部分（高 16 位分钟级时间戳，低 8 位访问频率），用于volatile-lfu或allkeys-lfu。
-