Redis中每个键值对都是一个redisObject,包含type(类型)和encoding(编码)两个字段。同一种type在不同条件下使用不同的encoding,这是Redis内存优化的核心设计。
redisObject {
unsigned type:4; // 类型: STRING/LIST/HASH/SET/ZSET
unsigned encoding:4; // 编码: int/embstr/raw/ziplist/quicklist/
// intset/hashtable/skiplist/...
unsigned lru:24; // LRU时间
int refcount; // 引用计数
void *ptr; // 指向底层数据结构的指针
}
编码选择逻辑:
┌──────────────────────────────┐
│ 值是整数 且 <= LONG_MAX ? │
│ 是 → int 编码(直接存在ptr) │
│ 否 ↓ │
│ 字符串长度 <= 44字节 ? │
│ 是 → embstr 编码 │
│ 否 → raw 编码(SDS) │
└──────────────────────────────┘
embstr vs raw:
┌─────────────────────────────────┐
│ embstr (≤44字节): │
│ ┌─────────────────────────────┐ │
│ │ redisObject | sdshdr | data │ │ ← 一次内存分配,连续内存
│ └─────────────────────────────┘ │
│ 优点: 一次分配、缓存友好 │
│ 缺点: 只读,修改会转为raw │
├─────────────────────────────────┤
│ raw (>44字节): │
│ ┌──────────┐ ┌─────────────┐│
│ │redisObject│─→ │ SDS | data ││ ← 两次内存分配
│ └──────────┘ └─────────────┘│
└─────────────────────────────────┘
SDS(Simple Dynamic String)结构:
struct sdshdr {
int len; // 已用长度
int free; // 剩余空间
char buf[]; // 字节数组
};
SDS vs C字符串:
| 维度 | C字符串 | SDS |
|-----------|---------------|-----------------|
| 获取长度 | O(N)遍历 | O(1)直接读len |
| 缓冲区溢出 | 可能溢出 | 空间预分配,安全 |
| 修改内存 | 每次realloc | 预分配+惰性释放 |
| 二进制安全 | \0结尾,不安全 | len判断,二进制安全|
Redis 3.2之后,List底层统一使用quicklist(双向链表 + ziplist)。
quicklist结构:
┌──────────────────────────────────────────────────┐
│ quicklist │
│ head │
│ ↓ │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ quicklistNode│⇄→│ quicklistNode│⇄→ ... │
│ │ ziplist: │ │ ziplist: │ │
│ │ [e1][e2][e3] │ │ [e4][e5][e6] │ │
│ └─────────────┘ └─────────────┘ │
│ │
│ 每个节点是一个ziplist(压缩列表) │
│ 节点间双向链表连接 │
└──────────────────────────────────────────────────┘
设计思想:
- 单纯链表: 内存碎片多,指针占用大(前驱+后继=16字节/节点)
- 单纯ziplist: 数据量大时realloc性能差
- quicklist: 折中方案,每个节点存一个ziplist,兼顾内存和性能
配置参数:
list-max-ziplist-size -2 # 每个ziplist不超过8KB
list-compress-depth 1 # 中间节点LZF压缩
编码转换条件:
field数量 ≤ 512 且 每个value ≤ 64字节 → ziplist
否则 → hashtable(字典)
ziplist存储Hash:
┌──────────────────────────────────────────┐
│ ziplist: [field1][value1][field2][value2]│ ← key-value紧挨存储
└──────────────────────────────────────────┘
查找: 顺序遍历,field数量少时足够快
hashtable存储Hash:
┌──────────────────────────────────────────┐
│ dict │
│ ht[0]: ┌─────┬─────┬─────┬─────┐ │
│ │ k/v │ k/v │ k/v │ ... │ │ ← O(1)查找
│ └─────┴─────┴─────┴─────┘ │
│ rehash时用ht[1]逐步迁移 │
└──────────────────────────────────────────┘
渐进式rehash:
1. 分配ht[1]空间(2倍ht[0])
2. 每次CRUD操作迁移ht[0]中一个桶到ht[1]
3. 全部迁移完成后,ht[0]←ht[1],释放旧ht[0]
4. 避免一次性rehash导致服务卡顿
编码转换条件:
所有元素都是整数 且 数量 ≤ 512 → intset
否则 → hashtable
intset结构(整数集合):
┌──────────────────────────────────┐
│ encoding: INT16/INT32/INT64 │
│ length: 3 │
│ contents: [1][5][9] │ ← 有序数组,二分查找O(logN)
└──────────────────────────────────┘
升级过程(小→大):
1. 新加入一个INT64值,当前encoding是INT16
2. 扩展数组大小(length × INT64大小)
3. 将已有元素从INT16转为INT64(从后往前转换)
4. 插入新元素
注意: 不支持降级
hashtable存储Set:
只存key,value为NULL → 类似Java的HashSet
编码转换条件:
元素数量 ≤ 128 且 每个元素 ≤ 64字节 → ziplist
否则 → skiplist + hashtable
ziplist存储ZSet:
[element1][score1][element2][score2] ← 紧凑存储,按score有序
skiplist + hashtable:
hashtable: member → score (O(1)查分数)
skiplist: 按score排序 (O(logN)查排名/范围查询)
跳表结构示意:
Level 4: 1 ────────────────────────────────────── 9
Level 3: 1 ──────────────────── 5 ──────────────── 9
Level 2: 1 ────── 3 ────── 5 ────── 7 ────────── 9
Level 1: 1 ─ 2 ─ 3 ─ 4 ─ 5 ─ 6 ─ 7 ─ 8 ─ 9
查找score=7的过程:
Level 4: 1→9(9>7,下移)
Level 3: 1→5(5<7,右移)→9(9>7,下移)
Level 2: 5→7(7=7,命中!)
总共4次比较,而链表需要7次
每个节点随机建索引层(约25%概率,即1/4):
0层: 所有节点
1层: 约25%节点
2层: 约6.25%节点
k层: 约(1/4)^k节点
空间复杂度: O(N),每个节点平均1.33个指针
ZSet为什么用跳表不用红黑树?
| 对比维度 | 跳表 | 红黑树 |
|---|---|---|
| 查找 | O(logN) | O(logN) |
| 插入/删除 | O(logN) | O(logN) |
| 范围查询 | O(logN+M),直接遍历底层链表 | 需要中序遍历,实现复杂 |
| 实现难度 | 简单,代码量少 | 复杂,旋转操作多 |
| 内存占用 | 每节点约1.33指针 | 每节点2指针+颜色位 |
| 并发友好 | 局部锁容易实现 | 旋转影响范围大 |
面试话术: "ZSet用跳表是因为范围查询更方便。ZRANGEBYSCORE只需要在底层链表上遍历即可,而红黑树范围查询需要中序遍历,实现复杂。跳表代码简单,内存可以接受(每个节点约1.33个指针)。虽然理论上和红黑树复杂度相同,但工程实现上优势明显。"
原理: 概率算法,基于伯努利试验
内存: 固定12KB(16384个桶,每桶6bit)
误差: 0.81%标准误差
用途: UV统计、DAU统计
命令:
PFADD uv:20260523 "user1" "user2" "user3"
PFCOUNT uv:20260523 # 返回估算基数
PFMERGE uv:all uv:20260523 uv:20260522 # 合并
原理: bit位数组,底层就是String
操作: SETBIT/GETBIT/BITCOUNT/BITOP
内存: 1亿用户在线状态 ≈ 100M/8 ≈ 12.5MB
场景:
- 签到打卡: SETBIT sign:uid:202605 22 1 (22号签到)
- 在线状态: SETBIT online uid 1
- 统计活跃: BITCOUNT active:20260523
原理: radix tree + listpack
特点: 支持消费者组模型(类似Kafka)
命令: XADD/XREAD/XGROUP/XACK
用途: 消息队列、审计日志
Stream vs List:
- Stream支持消费者组,List不支持
- Stream消息可ACK,List不能
- Stream支持消息回溯,List不能
| 操作 | 数据类型 | 底层编码 | 时间复杂度 | 说明 |
|---|---|---|---|---|
| GET/SET | String | int/embstr/raw | O(1) | 直接寻址 |
| LPUSH/RPOP | List | quicklist | O(1) | 头尾操作 |
| LINDEX | List | quicklist | O(N) | 需遍历ziplist |
| HGET/HSET | Hash | ziplist | O(N) | 顺序查找 |
| HGET/HSET | Hash | hashtable | O(1) | 哈希定位 |
| SADD/SISMEMBER | Set | intset | O(logN) | 二分查找 |
| SADD/SISMEMBER | Set | hashtable | O(1) | 哈希定位 |
| ZADD | ZSet | ziplist | O(N) | 插入需移动 |
| ZADD | ZSet | skiplist | O(logN) | 跳表查找 |
| ZRANGE | ZSet | skiplist | O(logN+M) | 链表遍历 |
| ZRANK | ZSet | skiplist | O(logN) | 跳表查找 |
| 类型 | 小数据编码 | 转换条件(满足全部) | 大数据编码 |
|---|---|---|---|
| String | int | 值为整数且<=LONG_MAX | - |
| String | embstr | 长度<=44字节 | raw |
| Hash | ziplist | field<=512 且 val<=64B | hashtable |
| List | quicklist | 始终 | quicklist |
| Set | intset | 全整数 且 数量<=512 | hashtable |
| ZSet | ziplist | 元素<=128 且 val<=64B | skiplist+ht |
面试话术: "Redis数据结构有自动编码转换机制。String短于44字节用embstr一次分配,长了转raw两次分配。Hash在field不超过512且value不超过64字节时用ziplist省内存,否则转hashtable保证性能。Set元素全是整数且不超过512个时用intset有序数组,否则转hashtable。ZSet元素不超过128且value不超过64字节时用ziplist,否则用跳表+哈希表。这些阈值都可以通过配置调整。"
1. 一个key的值是"hello world"(11字节),它底层是什么编码?如果执行APPEND追加到50字节,编码会发生什么变化?
2. 为什么Redis 3.2以后用quicklist替代了ziplist和linkedlist两种编码?quicklist的设计取舍是什么?
3. ZSet实现排行榜,当成员数为50时底层是什么编码?当成员增长到200时呢?为什么?
4. 解释SDS的"空间预分配"和"惰性释放"策略,它们分别解决了什么问题?
5. 如果面试官问"为什么Redis不用B树或红黑树做有序集合",你该怎么回答?请从范围查询、实现复杂度、并发友好三个维度分析。