入门
Redis 支持哪些数据类型？各自的应用场景是什么？
五大基础数据类型
一句话原理：Redis提供五种核心数据类型：String（字符串）、Hash（哈希）、List（列表）、Set（集合）、ZSet（有序集合），每种类型底层采用不同的数据结构实现，满足多样化的业务场景需求。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // Redis 对象头结构（redisObject）
typedef struct redisObject {
unsigned type:4; // 数据类型：String/Hash/List/Set/ZSet
unsigned encoding:4; // 底层编码：int/embstr/raw/ziplist/linkedlist/skiplist等
void *ptr; // 指向底层数据结构的指针
// ...
} robj;
// 各类型的type常量
#define OBJ_STRING 0 // 字符串
#define OBJ_LIST 1 // 列表
#define OBJ_SET 2 // 集合
#define OBJ_ZSET 3 // 有序集合
#define OBJ_HASH 4 // 哈希
|
项目场景：在社交APP中，用户信息用Hash存储，粉丝列表用Set存储，时间线用List存储，排行榜用ZSet存储，页面统计数据用String的原子自增。五种数据类型完美覆盖90%的业务场景。
String（字符串）
一句话原理：String是最基础的键值对类型，value可以是字符串、数字或二进制数据，支持原子自增自减、位操作、批量操作等，底层采用**动态字符串（SDS）**实现，获取长度时间复杂度O(1)。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| // String底层编码
// 1. int编码：存储整数
// 2. embstr编码：短字符串（<44字节），内存连续
// 3. raw编码：长字符串，使用SDS（简单动态字符串）
struct sdshdr {
int len; // 已使用长度
int free; // 空闲长度
char buf[]; // 字符数组（自动追加\0）
};
// 常用命令源码
void setCommand(client *c) {
robj *key = c->argv[1];
robj *val = c->argv[2];
// 尝试将值编码为int/embstr/raw
robj *encoded = tryObjectEncoding(val);
setKey(c->db, key, encoded);
}
// 原子自增实现
void incrCommand(client *c) {
robj *o = lookupKeyWrite(c->db, c->argv[1]);
// 将字符串转为整数，执行+1操作
o = incrDecrCommand(c, o, 1); // 线程安全
}
|
项目场景：在电商系统中，用String存储商品库存，利用INCR/DECR实现秒杀库存扣减；用SETBIT/GETBIT实现用户签到功能，每月只需32字节；用SETEX存储短信验证码并自动过期；用MSET/MGET批量获取用户信息。
Hash（哈希）
一句话原理：Hash类似Java的HashMap<String, String>，适合存储对象类型数据，可以单独读写某个字段，内存占用比String更优，底层使用**压缩列表（ziplist）或哈希表（hashtable）**实现。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| // Hash底层编码
// 1. ziplist：当field-value数量少且值小时，使用压缩列表（连续内存）
// 2. hashtable：当数据量大时，转为哈希表
// 压缩列表结构
struct ziplist {
uint32_t zlbytes; // 整个压缩列表占用的字节数
uint32_t zltail; // 列表尾部的偏移量
uint16_t zllen; // 节点数量
uint8_t entry[]; // 节点列表（交替存储field和value）
}
// 哈希表结构
typedef struct dict {
dictht ht[2]; // 两个哈希表（用于rehash）
long rehashidx; // rehash进度
// ...
}
// HSET命令实现
void hsetCommand(client *c) {
robj *o = lookupKeyWrite(c->db, c->argv[1]);
if (!o) {
// 创建新哈希对象
o = createHashObject();
dbAdd(c->db, c->argv[1], o);
}
// 调用底层哈希表或压缩列表的添加操作
hashTypeSet(o, c->argv[2], c->argv[3]);
}
|
项目场景：在用户中心，用Hash存储用户信息，每个用户一个key，字段包括name、age、email等。需要修改邮箱时，只需HSET user:1001 email new@mail.com，无需读取整个对象；用HGETALL获取完整信息，内存占用比String方式（序列化整个对象）减少30%以上。
List（列表）
一句话原理：List是双向链表，支持从两端插入弹出，可用作栈或队列，实现消息队列、最新消息列表等功能，底层使用压缩列表（quicklist前身）或双向链表，新版Redis统一使用quicklist（压缩列表+链表）。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| // List底层编码（Redis 3.2+统一使用quicklist）
typedef struct quicklist {
quicklistNode *head; // 头节点
quicklistNode *tail; // 尾节点
long count; // 总元素数量
int compress; // 压缩深度
}
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl; // 指向压缩列表
int sz; // 压缩列表大小
int count; // 压缩列表中元素数量
}
// LPUSH/RPUSH命令实现
void pushGenericCommand(client *c, int where) {
robj *lobj = lookupKeyWrite(c->db, c->argv[1]);
if (!lobj) {
// 创建新列表
lobj = createQuicklistObject();
dbAdd(c->db, c->argv[1], lobj);
}
// 遍历所有参数，依次添加到列表
for (int j = 2; j < c->argc; j++) {
listTypePush(lobj, c->argv[j], where);
}
}
|
项目场景：在IM系统中，用List存储聊天记录，LPUSH新消息，LTRIM保留最近100条；在任务队列中，用LPUSH生产任务，RPOP消费任务，实现先进先出队列；在文章系统中，用LPUSH存储最新文章ID，配合LRANGE实现分页。
Set（集合）
一句话原理：Set是无序的字符串集合，支持交集、并集、差集等集合运算，适合用于标签系统、好友关系、去重等场景，底层使用整数集合（intset）或哈希表。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| // Set底层编码
// 1. intset：当所有元素都是整数且数量少时，使用整数集合（有序数组，二分查找）
// 2. hashtable：当数据量大或含字符串时，转为哈希表（值为NULL）
typedef struct intset {
uint32_t encoding; // 编码方式（16/32/64位）
uint32_t length; // 元素数量
int8_t contents[]; // 元素数组（有序，无重复）
}
// SADD命令实现
void saddCommand(client *c) {
robj *set = lookupKeyWrite(c->db, c->argv[1]);
if (!set) {
set = setTypeCreate(c->argv[2]); // 根据第一个元素选择编码
dbAdd(c->db, c->argv[1], set);
}
int added = 0;
for (int j = 2; j < c->argc; j++) {
if (setTypeAdd(set, c->argv[j])) added++; // 添加成功计数
}
addReplyLongLong(c, added);
}
// 集合运算（交集）
void sinterCommand(client *c) {
// 获取所有集合
robj *sets[argc-1];
for (int j = 1; j < argc; j++) {
sets[j-1] = lookupKeyRead(c->db, c->argv[j]);
}
// 计算交集并返回
sinterGenericCommand(c, sets, argc-1);
}
|
项目场景：在电商系统中，用Set存储商品标签，SADD product:1001:tags "手机" "5G" "华为"，通过SINTER实现标签组合查询（手机+5G）；在社交APP中，用Set存储粉丝关系，SISMEMBER fans:1001 1002判断是否已关注；在去重场景中，用SADD保证唯一性。
ZSet（有序集合）
一句话原理：ZSet在Set基础上增加了分数（score），元素按分数排序，支持范围查询和排名操作，适合排行榜、延时队列、范围查询等场景，底层使用跳表（skiplist）+哈希表实现。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| // ZSet底层结构：跳表 + 哈希表
typedef struct zset {
dict *dict; // 哈希表：元素 -> 分数（快速查找）
zskiplist *zsl; // 跳表：按分数排序（支持范围查询）
}
// 跳表节点
typedef struct zskiplistNode {
sds ele; // 元素
double score; // 分数
struct zskiplistNode *backward; // 后退指针
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned int span; // 跨度
} level[]; // 多层索引
}
// ZADD命令实现
void zaddCommand(client *c) {
robj *zobj = lookupKeyWrite(c->db, c->argv[1]);
if (!zobj) {
zobj = createZsetObject(); // 创建跳表+哈希
dbAdd(c->db, c->argv[1], zobj);
}
// 遍历参数（score-element对）
for (int j = 2; j < c->argc; j += 2) {
double score = atof(c->argv[j]->ptr);
robj *ele = c->argv[j+1];
zsetAdd(zobj, score, ele, &flags); // 同时更新跳表和哈希
}
}
|
项目场景：在直播系统中，用ZSet存储礼物排行榜，ZINCRBY gift:rank:room:1001 100 1002为用户1002增加100积分；用ZREVRANGE gift:rank:room:1001 0 9获取前十名。在任务调度中，用ZSet实现延时队列，时间戳作为分数，轮询获取到期的任务。
完整实战指南
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| /**
* Redis数据类型完整实战指南
*/
public class RedisDataTypeGuide {
/**
* 1. 数据类型对比表
*/
public class TypeComparison {
// 类型 底层结构 适用场景
// String SDS 缓存、计数器、分布式锁
// Hash ziplist/hashtable 对象存储、配置信息
// List quicklist 消息队列、最新列表
// Set intset/hashtable 标签、好友关系、去重
// ZSet skiplist+dict 排行榜、延时队列、范围查询
}
/**
* 2. 编码转换条件
*/
public class EncodingConditions {
// String: int(整数) <-> embstr(短文本) <-> raw(长文本)
// Hash: ziplist -> hashtable (field > 512或value > 64字节)
// List: quicklist自动管理
// Set: intset -> hashtable (元素类型变化或数量 > 512)
// ZSet: ziplist -> skiplist (元素 > 128或value > 64字节)
}
/**
* 3. 内存优化建议
*/
public class MemoryOptimization {
// 1. 用Hash替代String存储对象（减少key数量）
// 2. 设置合理过期时间
// 3. 使用ziplist编码（控制元素数量和大小）
// 4. 使用整数ID作为key
// 5. 用BITMAP存储布尔状态
}
/**
* 4. 面试必备
*/
public class InterviewQA {
// Q: Redis为什么这么快？
// A: 内存存储 + 单线程模型 + IO多路复用 + 高效数据结构
// Q: ZSet底层为什么用跳表不用平衡树？
// A: 跳表实现简单，范围查询方便，支持灵活的分数调整
// Q: List和ZSet都能做排行榜，区别？
// A: List按插入顺序，ZSet按分数排序且支持动态更新
// Q: Hash的ziplist和hashtable如何选择？
// A: 数据量小用ziplist，数据量大用hashtable
}
}
/**
* 数据类型总结表
*
* 类型 常用命令 时间复杂度
* String SET/GET/INCR/DECR/MSET/MGET O(1)
* Hash HSET/HGET/HGETALL/HDEL/HINCRBY O(1)
* List LPUSH/RPUSH/LPOP/RPOP/LRANGE O(1)两端操作
* Set SADD/SREM/SISMEMBER/SINTER O(1)单个操作
* ZSet ZADD/ZREM/ZRANGE/ZREVRANGE O(logN)
*/
// 面试金句
// "Redis的五种数据类型就像'瑞士军刀'的五个工具：
// String是'主刀'（基础功能），
// Hash是'螺丝刀'（修对象），
// List是'锯子'（处理序列），
// Set是'镊子'（处理关系），
// ZSet是'量尺'（精确排序）。
// 在电商系统中，我用String做库存扣减，Hash存用户信息，
// List做消息队列，Set做商品标签，ZSet做销量排行榜。
// 理解每种类型的特性和底层结构，才能在设计系统时做出最佳选择。"
|
String 类型和 Hash 类型存储对象的区别？如何选择？
核心原理：存储结构与内存布局
一句话原理：String存储对象是将整个对象序列化为一个字符串（如JSON）整体存储，每次操作需全量读写；Hash存储对象是将对象的每个字段作为独立key-value存储，支持部分读写，内存布局和操作粒度有本质区别。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| // String存储对象：整体序列化
// 用户对象示例：{"id":1001,"name":"张三","age":25,"email":"zhangsan@qq.com"}
SET user:1001 "{\"id\":1001,\"name\":\"\u5f20\u4e09\",\"age\":25,\"email\":\"zhangsan@qq.com\"}"
// Redis内存中：一个key对应一个序列化后的字符串
// key: "user:1001"
// value: 整个JSON字符串（占连续内存）
// ============ Hash存储对象：字段独立 ============
HSET user:1001 id 1001 name "张三" age 25 email "zhangsan@qq.com"
// Redis内存中：一个key对应一个Hash对象
// key: "user:1001"
// field: "id", value: "1001"
// field: "name", value: "张三"
// field: "age", value: "25"
// field: "email", value: "zhangsan@qq.com"
// Redis底层编码（以ziplist为例）
// ziplist结构：[总字节][尾偏移][元素数][field][value][field][value]...
// 字段名和字段值交替存储在连续内存中
|
项目场景：在用户信息系统中，如果每次都需要读写全部字段（如用户详情页），String更简单；如果经常需要修改单个字段（如更新用户头像、修改年龄），Hash更合适。
内存占用对比：序列化开销 vs 字段冗余
一句话原理：String存储存在序列化/反序列化开销，但字段名不重复存储；Hash存储无需序列化，但每个字段名都会重复存储，导致内存占用更高。当字段较多时，Hash可能比String多占用30-50%内存。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| /**
* 内存占用对比计算
*/
// 示例对象：用户信息
// id:1001 (4字节数值)
// name:"张三" (6字节UTF-8)
// age:25 (2字节数值)
// email:"zhangsan@qq.com" (18字节)
// address:"北京市朝阳区" (15字节)
// ============ String方式 ============
// JSON序列化后："{\"id\":1001,\"name\":\"张三\",\"age\":25,\"email\":\"zhangsan@qq.com\",\"address\":\"北京市朝阳区\"}"
// 实际存储：约120字节（包含字段名、引号、逗号、花括号）
// 优点：字段名只出现一次
// 缺点：每次操作都需要JSON解析/序列化
// ============ Hash方式 ============
// 每个字段单独存储，字段名重复
// field "id" (2字节) + value "1001" (4字节) = 6字节
// field "name" (4字节) + value "张三" (6字节) = 10字节
// field "age" (3字节) + value "25" (2字节) = 5字节
// field "email" (5字节) + value "zhangsan@qq.com" (18字节) = 23字节
// field "address" (7字节) + value "北京市朝阳区" (15字节) = 22字节
// 总计：约66字节（不含元数据开销）
// 缺点：字段名重复存储，但总内存可能更低（因为无需JSON结构）
// Redis内存诊断命令
> MEMORY USAGE user:1001 // 查看String方式内存占用
> MEMORY USAGE user:1001 // 查看Hash方式内存占用
// 编码选择阈值
// Hash使用ziplist的条件：所有field和value长度 < 64字节 && 字段数 < 512
// 超过阈值会转为hashtable，内存开销更大
|
项目场景：在配置中心系统中，存储应用配置（几十个配置项）。经过实际测试，用Hash存储比用JSON String内存节省30%，且修改单个配置时无需重写整个JSON。但对于只有2-3个字段的简单对象，String反而更节省内存。
操作效率对比：全量读写 vs 部分读写
一句话原理：String操作是原子性全量读写，每次修改都需要读取-反序列化-修改-序列化-写入整个对象，适合整体更新场景；Hash支持字段级原子操作，修改单个字段无需读取其他字段，适合频繁部分更新场景。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| /**
* 操作效率对比
*/
// ============ String方式：修改年龄 ============
// 1. GET user:1001 → 获取整个JSON字符串
// 2. JSON解析为对象
// 3. 修改age字段
// 4. 对象重新序列化为JSON
// 5. SET user:1001 新JSON → 写回
// 伪代码
String json = redis.get("user:1001");
User user = JSON.parse(json, User.class);
user.setAge(26);
redis.set("user:1001", JSON.stringify(user));
// 问题：网络传输全量数据，多次内存操作，并发时可能丢失更新
// ============ Hash方式：修改年龄 ============
// 一次原子操作
HSET user:1001 age 26
// 伪代码
redis.hset("user:1001", "age", "26");
// 优势：网络传输少量数据，原子操作，无需读取其他字段
// ============ 批量获取 ============
// String方式：获取所有字段
GET user:1001 // 一次性获取全部
// Hash方式：获取所有字段
HGETALL user:1001 // 获取全部
// Hash方式：获取部分字段
HMGET user:1001 name email // 只获取指定字段
|
项目场景：在在线游戏中，玩家属性包括等级、经验、金币、装备等。玩家打怪时只修改经验值，用Hash只需HINCRBY player:1001 exp 100，原子高效；但进入玩家详情页时需要展示全部属性，用HGETALL一次获取，性能依然优秀。
完整对比与选型指南
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
| /**
* String vs Hash 完整选型指南
*/
public class StringVsHashGuide {
/**
* 1. 详细对比表
*/
public class ComparisonTable {
// 维度 String Hash
// 存储方式 序列化字符串 字段独立存储
// 内存占用 字段名不重复，但有JSON结构开销 字段名重复，但无结构开销
// 读操作 全量读（网络传输全量） 可部分读（传输少）
// 写操作 全量写（需要先读后写） 可部分写（直接修改）
// 原子性 整体原子，但修改需先读后写 字段级原子操作
// 灵活性 修改任何字段都要重写整个对象 可独立修改任意字段
// 复杂度 需序列化/反序列化 无需序列化
// 适合场景 整体读写多，修改少 频繁部分修改
}
/**
* 2. 选择决策树
*/
public class DecisionTree {
// 1. 对象字段数？
// ├─ 很少（≤3） → String（简单）
// └─ 较多（>3） → 转到2
// 2. 是否经常修改单个字段？
// ├─ 是 → Hash（部分更新优势）
// └─ 否 → 转到3
// 3. 是否需要字段过期时间不同？
// ├─ 是 → String（每个字段单独存为String）
// └─ 否 → 转到4
// 4. 内存敏感度？
// ├─ 高 → 实测对比MEMORY USAGE
// └─ 低 → Hash（功能更灵活）
// 5. 开发维护成本？
// ├─ 想简单 → String（直接JSON）
// └─ 想规范 → Hash（结构化）
}
/**
* 3. 实战场景示例
*/
public class RealWorldScenarios {
// 场景1：用户Session（推荐String）
// 原因：通常一次读写全部，修改不频繁，JSON便于跨语言
SET session:token "{\"userId\":1001,\"loginTime\":\"2023-01-01\",\"expire\":3600}"
// 场景2：商品详情（推荐Hash）
// 原因：不同字段更新频率不同（库存频繁，标题偶尔，描述很少）
HSET product:1001 title "iPhone 14" price 5999 stock 100 desc "..."
HINCRBY product:1001 stock -1 // 秒杀时只减库存
// 场景3：配置信息（推荐Hash）
// 原因：需要独立修改某个配置项
HSET config:system db_url "jdbc:mysql://..." max_connections 100 cache_size 512
// 场景4：计数器集合（推荐String）
// 原因：INCR命令就是为String设计的
INCR page_view:index
INCRBY user:1001:score 50
// 场景5：对象列表（推荐String或单独key）
// 如果存储文章列表，建议每个文章一个Hash，用Set保存ID列表
SADD articles:latest 1001 1002 1003
HGETALL article:1001
}
/**
* 4. 混合使用策略
*/
public class HybridStrategy {
// 方案：核心字段用Hash，扩展字段用String
// Hash存储经常访问和修改的字段
HSET user:1001 id 1001 name "张三" age 25 avatar "avatar.jpg"
// String存储不常用的扩展信息
SET user:1001:ext "{\"address\":\"北京\",\"hobby\":[\"读书\",\"游泳\"],\"signature\":\"hello\"}"
// 优势：平衡了内存和灵活性
}
/**
* 5. 性能测试代码
*/
public class PerformanceTest {
public void benchmark() {
// 测试10万次修改年龄操作
// String方式（模拟）
String json = redis.get("user:1001");
User user = JSON.parse(json);
user.setAge(newAge);
redis.set("user:1001", JSON.stringify(user));
// 耗时：约500ms（包含网络传输和JSON解析）
// Hash方式
redis.hset("user:1001", "age", String.valueOf(newAge));
// 耗时：约50ms（一次网络往返）
// Hash比String快10倍左右
}
}
}
/**
* 选型总结表
*
* 场景 推荐类型 原因
* 用户Session String 一次性读写，跨语言
* 商品详情 Hash 频繁修改库存
* 配置信息 Hash 独立修改各配置项
* 计数器 String INCR命令高效
* 对象列表（如文章列表） Set+Hash 组合使用
* 日志数据 String 追加写入
* 地理位置信息 String GEO命令底层是String
*
* 最佳实践：
* 1. 字段数 < 5且修改少 → String
* 2. 字段数多或部分更新频繁 → Hash
* 3. 不确定时，用Hash更灵活
* 4. 大文本内容单独存String
*/
// 面试金句
// "String和Hash存储对象就像'打包托运'和'零担物流'的区别：
// String是把所有东西打成一个'集装箱'（JSON），整体运输，
// 优点是省了贴标签（字段名不重复），但想换其中一件就得打开整个箱子；
// Hash是把每件货物贴上标签（字段名），独立运输，
// 可以只换其中一件，但要给每件都贴标签（字段名重复）。
// 在电商系统中，商品详情用Hash，因为库存要经常修改；
// 用户登录Session用String，因为每次都是整体读写。
// 理解这个区别，才能根据业务特点做出最优的数据模型设计。"
|
List 和 Set 的区别？ZSet 的底层实现是什么？
List vs Set：核心区别
一句话原理：List是有序可重复的集合，基于双向链表（quicklist）实现，支持两端操作；Set是无序不重复的集合，基于哈希表或整数集合实现，支持集合运算，两者在"顺序性"和"唯一性"上有本质区别。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| // List底层结构：quicklist（压缩列表+双向链表）
typedef struct quicklist {
quicklistNode *head; // 头节点
quicklistNode *tail; // 尾节点
long count; // 总元素数量
int compress; // 压缩深度
} quicklist;
typedef struct quicklistNode {
struct quicklistNode *prev; // 前驱指针
struct quicklistNode *next; // 后继指针
unsigned char *zl; // 指向压缩列表（ziplist）
int sz; // 压缩列表大小
int count; // 压缩列表中元素数量
} quicklistNode;
// List特性：有序、可重复、两端操作
LPUSH list "A" "B" "C" // 列表变为: C B A
RPUSH list "D" // 列表变为: C B A D
// 可以包含重复元素：LPUSH list "A" → 列表中有两个"A"
// ============ Set底层结构 ============
// Set底层编码（根据元素类型自动选择）
// 1. intset：当所有元素都是整数且数量少时
typedef struct intset {
uint32_t encoding; // 编码方式（16/32/64位）
uint32_t length; // 元素数量
int8_t contents[]; // 有序整数数组（二分查找）
} intset;
// 2. hashtable：当元素类型复杂或数量多时
typedef struct dict {
dictht ht[2]; // 两个哈希表（渐进式rehash）
long rehashidx; // rehash进度
} dict;
// Set特性：无序、不重复、集合运算
SADD set "A" "B" "C" // 添加三个元素
SADD set "A" // 返回0，因为"A"已存在
SMEMBERS set // 返回无序集合，可能是"C" "A" "B"
// 集合运算
SINTER set1 set2 // 交集
SUNION set1 set2 // 并集
SDIFF set1 set2 // 差集
|
项目场景：在IM系统中，用List存储聊天记录，保证消息顺序（有序）且允许重复内容（可重复）；用Set存储好友列表，确保好友不重复（不重复），同时支持共同好友查询（集合运算）。
ZSet（有序集合）底层实现
一句话原理：ZSet是Set的升级版，在唯一性基础上增加了分数（score）排序，底层采用跳表（skiplist） + **哈希表（dict）**的复合结构，跳表保证排序和范围查询效率（O(logN)），哈希表保证元素快速查找（O(1)）。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| /**
* ZSet底层结构详解
*/
typedef struct zset {
dict *dict; // 哈希表：元素 -> 分数（用于快速查找和唯一性保证）
zskiplist *zsl; // 跳表：按分数排序（用于范围查询和排名）
} zset;
// ============ 哈希表部分：O(1)查找元素 ============
// key: 元素值
// value: 分数
// 作用：快速判断元素是否存在，获取元素分数，删除元素时无需遍历跳表
// ============ 跳表部分：高效排序和范围查询 ============
typedef struct zskiplist {
struct zskiplistNode *header; // 头节点（最高层起点）
struct zskiplistNode *tail; // 尾节点
long length; // 元素数量
int level; // 当前最大层数
} zskiplist;
// 跳表节点
typedef struct zskiplistNode {
sds ele; // 存储的元素（字符串）
double score; // 分数（排序依据）
struct zskiplistNode *backward; // 后退指针（用于逆序）
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned int span; // 跨度（用于快速计算排名）
} level[]; // 柔性数组，每层一个指针+跨度
} zskiplistNode;
// ZADD命令实现：同时操作跳表和哈希表
void zaddCommand(client *c) {
// 1. 查找或创建zset对象
robj *zobj = lookupKeyWrite(c->db, c->argv[1]);
if (!zobj) {
zobj = createZsetObject(); // 创建跳表+哈希表
dbAdd(c->db, c->argv[1], zobj);
}
// 2. 遍历参数（score-element对）
for (int j = 2; j < c->argc; j += 2) {
double score = atof(c->argv[j]->ptr);
sds ele = c->argv[j+1]->ptr;
// 3. 同时更新跳表和哈希表
zsetAdd(zobj, score, ele, &flags);
// 跳表：插入节点并维护多层索引
// 哈希表：添加或更新元素->分数映射
}
}
// ZRANGE命令实现：范围查询
void zrangeCommand(client *c) {
robj *zobj = lookupKeyRead(c->db, c->argv[1]);
zskiplist *zsl = zobj->ptr;
long start = atoi(c->argv[2]->ptr);
long end = atoi(c->argv[3]->ptr);
// 从跳表中获取指定范围的节点
zskiplistNode *node = zsl->header->level[0].forward;
// 跳过前面的元素
for (long i = 0; i < start; i++) {
node = node->level[0].forward;
}
// 返回范围内的元素
for (long i = start; i <= end; i++) {
addReplyBulk(c, node->ele);
node = node->level[0].forward;
}
}
|
项目场景：在直播系统中，需要实时维护礼物排行榜。ZSet完美满足需求：用ZINCRBY原子增加用户分数，ZREVRANGE获取排行榜前十，ZRANK查看用户排名。跳表保证范围查询高效，哈希表保证快速查找用户当前分数。
ZSet vs 其他结构的性能对比
一句话原理：ZSet通过跳表+哈希表的组合，在插入、更新、删除、范围查询、单点查询五种操作间取得完美平衡，时间复杂度均为O(logN)或O(1)，而List和Set各有短板。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| /**
* 数据结构性能对比表（以代码注释形式）
*/
public class DataStructureComparison {
// 操作 List Set ZSet
// 插入 O(1)两端 O(1) O(logN)
// 删除 O(N)中间查找 O(1) O(logN)
// 查找 O(N) O(1) O(1)+O(logN)
// 范围查询 O(N)切片 不支持 O(logN+M)
// 排名查询 不支持 不支持 O(logN)
// 集合运算 不支持 O(N) 不支持
// 唯一性 不支持 ✅ ✅
// 有序性 ✅ ❌ ✅
}
// ZRANK排名查询实现（利用跳表跨度）
long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x = zsl->header;
long rank = 0;
// 从最高层向下搜索
for (int i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele, ele) <= 0))) {
rank += x->level[i].span; // 累加跨度
x = x->level[i].forward;
}
}
return rank;
}
// ZCOUNT统计分数范围内元素数量
unsigned long zslCount(zskiplist *zsl, double min, double max) {
zskiplistNode *node = zslFirstInRange(zsl, min, max); // 找到第一个
unsigned long count = 0;
while (node && node->score <= max) {
count++;
node = node->level[0].forward;
}
return count;
}
|
项目场景：在游戏系统中，需要查询"等级在50-60级之间的玩家数量"（ZCOUNT）、“某玩家全球排名”（ZRANK）、“前100名玩家”（ZREVRANGE）、“给玩家增加经验”（ZINCRBY）。ZSet一条命令解决所有需求，如果用List+其他结构组合，至少需要3-5种数据结构配合。
完整实战指南
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| /**
* List、Set、ZSet完整实战指南
*/
public class RedisDataTypesGuide {
/**
* 1. 选型决策树
*/
public class DecisionTree {
// 1. 是否需要元素唯一？
// ├─ 是 → 转到2
// └─ 否 → List（消息队列、日志、最新消息）
// 2. 是否需要排序？
// ├─ 是 → ZSet（排行榜、延时队列）
// └─ 否 → Set（标签、好友关系、去重）
// 3. 是否需要集合运算？
// ├─ 是 → Set（共同好友、推荐系统）
// └─ 否 → 按其他需求选择
}
/**
* 2. 实战场景示例
*/
public class RealScenarios {
// 场景1：消息队列（List）
// LPUSH生产，RPOP消费，支持阻塞读取BRPOP
LPUSH task:queue "task1" "task2" "task3"
RPOP task:queue // 获取"task1"（FIFO）
// 场景2：最新消息（List）
LPUSH news:latest "news1" "news2" "news3"
LTRIM news:latest 0 99 // 只保留最新100条
// 场景3：好友关系（Set）
SADD friends:1001 1002 1003 1004 // 用户1001的好友
SADD friends:1002 1001 1005 // 共同好友查询
SINTER friends:1001 friends:1002 // 返回[1001]
// 场景4：商品标签（Set）
SADD tag:phone 1001 1002 1003 // 手机类商品
SADD tag:5g 1001 1003 1004 // 5G商品
SINTER tag:phone tag:5g // 5G手机
// 场景5：排行榜（ZSet）
ZADD rank:game 1000 "player1" 2000 "player2" 1500 "player3"
ZINCRBY rank:game 500 "player1" // 增加分数
ZREVRANGE rank:game 0 9 WITHSCORES // 前十名
// 场景6：延时队列（ZSet）
ZADD delay:queue 1640995200 "task1" // 时间戳作为分数
ZADD delay:queue 1641081600 "task2"
// 轮询获取到期的任务
ZRANGEBYSCORE delay:queue 0 1640995200
}
/**
* 3. 编码优化
*/
public class EncodingOptimization {
// ZSet编码选择
// 1. ziplist：元素数量 < 128 && 所有元素长度 < 64字节
// 2. skiplist+dict：超过阈值
// 查看编码
> OBJECT ENCODING rank:game // "skiplist"或"ziplist"
// 配置阈值（redis.conf）
// zset-max-ziplist-entries 128
// zset-max-ziplist-value 64
}
/**
* 4. 面试必备
*/
public class InterviewQA {
// Q: 为什么ZSet用跳表不用平衡树？
// A: 跳表实现简单，范围查询方便，内存占用可控，支持灵活的分数调整
// Q: ZSet的跳表层数如何决定？
// A: 随机生成，层数概率分布，最大32层
// Q: ZSet的分数可以相同吗？
// A: 可以，相同分数时按字典序排序
// Q: ZSet和List都能实现排行榜，区别？
// A: List按插入顺序，ZSet按分数排序且支持动态更新和范围查询
}
}
/**
* 数据类型总结表
*
* 类型 有序 唯一 底层结构 时间复杂度
* List ✅ ❌ quicklist 两端O(1)，中间O(N)
* Set ❌ ✅ intset/hashtable O(1)
* ZSet ✅ ✅ skiplist+dict O(logN)
*
* 性能指标（百万级数据）：
* ZSet插入：约200ns
* ZSet范围查询：约50ns + 结果集大小
* ZSet排名查询：约150ns
*/
// 面试金句
// "List、Set、ZSet就像三种不同的'容器'：
// List是'传送带'（有序可重复，从一端放另一端取），
// Set是'储物箱'（无序不重复，适合装标签），
// ZSet是'自动货架'（按重量排序，快速存取）。
// 在游戏系统中，排行榜必须用ZSet，因为要按分数排序并动态更新；
// 消息队列用List，保证顺序即可；
// 好友关系用Set，要的就是不重复和共同好友查询。
// 理解每种容器的特性和底层实现，才能在设计系统时游刃有余。"
|
底层原理
Redis 的 String 类型底层是如何实现的？（SDS 的优势）
SDS核心原理：动态字符串
一句话原理：Redis的String类型底层使用SDS（Simple Dynamic String，简单动态字符串）实现，它是一个预分配空间、记录长度、二进制安全的动态字符串结构，彻底解决了C语言字符串的缓冲区溢出、获取长度O(n)等问题。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| // C语言字符串（以\0结尾）
char *c_str = "hello"; // 内存: 'h' 'e' 'l' 'l' 'o' '\0'
// 问题1：获取长度需遍历 O(n)
// 问题2：拼接时需手动分配内存，易缓冲区溢出
// 问题3：不能存储二进制数据（遇到\0会截断）
// ============ Redis SDS结构（3.2版本前） ============
struct sdshdr {
int len; // 已使用长度（不包括\0）
int free; // 空闲长度（未使用空间）
char buf[]; // 字符数组（自动追加\0）
};
// ============ Redis SDS结构（3.2版本后，优化内存） ============
// 根据字符串长度不同，使用不同结构体，节省内存
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; // 已使用长度（1字节，最大255）
uint8_t alloc; // 总分配长度（1字节）
unsigned char flags; // 类型标志
char buf[]; // 字符数组
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; // 已使用长度（2字节，最大65535）
uint16_t alloc; // 总分配长度（2字节）
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; // 已使用长度（4字节）
uint32_t alloc; // 总分配长度（4字节）
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; // 已使用长度（8字节）
uint64_t alloc; // 总分配长度（8字节）
unsigned char flags;
char buf[];
};
|
项目场景：在电商系统中，存储用户Session信息（如JSON格式的用户数据），长度通常在几百字节到几KB之间。SDS的预分配机制让字符串可以动态增长，而二进制安全特性确保可以存储任意格式的数据（包括图片的Base64编码）。
SDS五大核心优势
一句话原理：SDS相比C字符串有五大优势：常数复杂度获取长度、杜绝缓冲区溢出、减少内存重分配次数、二进制安全、兼容C字符串函数，这些优势共同奠定了Redis高性能的基础。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| /**
* SDS五大优势源码解析
*/
// ============ 优势1：常数复杂度获取长度 ============
// C字符串：需要遍历 O(n)
int c_str_len = strlen(c_str); // 遍历直到遇到\0
// SDS：直接读取len字段 O(1)
sds s = "hello";
size_t len = sdslen(s); // 直接返回len字段值
// ============ 优势2：杜绝缓冲区溢出 ============
// C字符串拼接（危险操作）
char *c_str = malloc(10);
strcpy(c_str, "hello");
strcat(c_str, " world"); // 严重！超出分配内存，覆盖相邻内存
// SDS自动扩容（安全操作）
sds s = sdsnew("hello");
s = sdscat(s, " world"); // 自动检查空间，不够则扩容
// SDS扩容策略源码
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh = (void*) (s - sizeof(struct sdshdr));
// 如果空闲空间足够，直接返回
if (sh->free >= addlen) return s;
// 计算新长度：新长度 = 原长度 + 需要增加的长度
size_t newlen = sh->len + addlen;
// 预分配策略：新长度小于1M时翻倍，大于1M时增加1M
if (newlen < SDS_MAX_PREALLOC) {
newlen *= 2; // 翻倍预分配
} else {
newlen += SDS_MAX_PREALLOC; // 增加1M
}
// 重新分配内存
sh = s_realloc(sh, sizeof(struct sdshdr) + newlen + 1);
sh->alloc = newlen;
sh->free = newlen - sh->len;
return sh->buf;
}
// ============ 优势3：减少内存重分配次数 ============
// 通过空间预分配和惰性空间释放，避免频繁malloc/free
// 追加操作示例
sds s = sdsnew("hello"); // len=5, alloc=5, free=0
s = sdscat(s, " world"); // 扩容：len=11, alloc=22, free=11
s = sdscat(s, "!"); // 无需扩容：len=12, free=10
// 字符串缩短时，并不释放内存
s = sdscut(s, 5); // 只修改len，free增加
// 惰性释放：等待将来可能的追加操作
// ============ 优势4：二进制安全 ============
// C字符串以\0结尾，不能存储二进制数据
char data[] = "hello\0world"; // 遇到\0就被截断
// SDS通过len字段确定数据长度，可以存储任意二进制数据
sds s = sdsnewlen("hello\0world", 11); // 存储11字节，包括中间的\0
size_t len = sdslen(s); // 返回11，正确获取长度
// ============ 优势5：兼容部分C字符串函数 ============
// SDS保留了\0结尾，可以复用部分C库函数
sds s = sdsnew("hello");
printf("%s\n", s); // 可以正常打印，因为buf最后有\0
// 注意：只适用于没有中间\0的情况
|
项目场景：在消息队列中，消息内容可能包含二进制数据（如序列化的对象、图片等）。SDS的二进制安全特性让Redis可以直接存储这些数据，无需Base64编码转换，节省了CPU开销和存储空间。
SDS三种编码方式
一句话原理：Redis根据字符串内容和长度，采用三种编码方式：int（整数）、embstr（短字符串）、raw（长字符串），在性能和内存占用间取得最佳平衡。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /**
* String三种编码方式
*/
// 1. int编码：存储整数（小于1亿）
// 当value可以被解析为整数且小于OBJ_SHARED_INTEGERS（默认10000）时
// 直接使用共享整数对象，极致节省内存
> SET page:count 100
> OBJECT ENCODING page:count // 返回 "int"
// 2. embstr编码：存储短字符串（长度<=44字节）
// 一次分配内存，redisObject和sds连续存储，减少内存碎片
> SET name "zhangsan"
> OBJECT ENCODING name // 返回 "embstr"
struct redisObject {
unsigned type:4;
unsigned encoding:4;
void *ptr; // 指向sds
// ... 其他字段
};
// embstr时，ptr指向的内存紧跟在redisObject后面
// 3. raw编码：存储长字符串（长度>44字节）
// 分两次分配内存，redisObject和sds分开存储
> SET article "very long content..." // 超过44字节
> OBJECT ENCODING article // 返回 "raw"
// 编码转换规则
// int → 非数字操作 → raw
// embstr → 修改操作 → raw（embstr只读，修改就转raw）
// embstr → 长度超过44 → raw
// Redis中创建字符串的源码
robj *createStringObject(const char *ptr, size_t len) {
if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) { // 44字节
return createEmbeddedStringObject(ptr, len); // embstr
} else {
return createRawStringObject(ptr, len); // raw
}
}
|
项目场景：在计数器场景（如页面访问量）用int编码，直接操作整数无需序列化；在存储用户姓名（短字符串）时用embstr编码，内存紧凑；在存储文章内容（长文本）时用raw编码，灵活扩展。三种编码自动适配，开发人员无需关心。
完整实战指南
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| /**
* SDS完整实战指南
*/
public class SDSGuide {
/**
* 1. 内存优化建议
*/
public class MemoryOptimization {
// 1. 短字符串用embstr（自动）
// 2. 整数用int编码（自动）
// 3. 避免频繁修改embstr（会转成raw）
// 4. 用批处理减少网络开销
// 查看字符串编码
> OBJECT ENCODING key
// 查看内存占用
> MEMORY USAGE key
}
/**
* 2. 常用操作时间复杂度
*/
public class TimeComplexity {
// SET/GET: O(1)
// APPEND: O(n) 但SDS预分配减少重分配
// STRLEN: O(1) 直接读len
// INCR/DECR: O(1)
// GETRANGE: O(n) 需要拷贝数据
}
/**
* 3. 面试必备
*/
public class InterviewQA {
// Q: SDS为什么用int、free字段，而不是用\0结尾？
// A: 获取长度O(1)、预分配减少重分配、二进制安全
// Q: SDS扩容策略是怎样的？
// A: 新长度<1M翻倍，>1M加1M
// Q: embstr和raw的区别？
// A: embstr内存连续一次分配，raw分开分配，embstr只读
// Q: SDS为什么兼容C字符串函数？
// A: 保留了\0结尾，但只适用于无中间\0的情况
}
}
/**
* SDS总结表
*
* 优势 说明 性能提升
* O(1)获取长度 直接读取len字段 遍历O(n) → O(1)
* 杜绝溢出 自动扩容 避免程序崩溃
* 预分配 减少内存重分配 减少内存操作90%
* 二进制安全 通过len字段确定长度 支持任意数据
* 内存优化 int/embstr/raw自适应编码 极致节省内存
*
* 内存布局：
* int: redisObject直接存储值
* embstr: redisObject + SDS连续内存
* raw: redisObject和SDS分开存储
*/
// 面试金句
// "SDS是Redis String的灵魂设计，它解决了C字符串的三大'先天缺陷'：
// 就像把'人力计算'升级为'智能仪表盘'：
// C字符串要数到结尾才知道长度（O(n)），SDS一眼看到仪表盘（O(1)）；
// C字符串拼接像'盲人开车'（容易撞车溢出），SDS有'预判雷达'（预分配空间）；
// C字符串遇到'\0'就'刹车'（不能存二进制），SDS按'里程表'行驶（长度字段）。
// 在存储用户Session时，SDS的预分配机制让频繁追加的JWT token也能高效处理，
// 而二进制安全特性让Redis可以无缝对接各种序列化协议。"
|
ZSet 的底层数据结构是什么？（跳表 + 哈希表）
一句话原理
ZSet 采用“跳表 + 哈希表”的双结构组合设计，利用哈希表实现 O(1) 的单点查询，同时利用跳表实现 O(log N) 的范围查询与排序，通过指针共享实现空间换时间。
一句话源码
在 Redis 源码 server.h 中，zset 结构体定义包含 dict *dict 和 zskiplist *zsl 两个成员，插入数据时会并行更新这两个结构以维持数据一致性。
一句话项目/场景
在电商“实时销量排行榜”场景中，直接利用 ZSet 的跳表特性通过 ZRANGE 命令毫秒级获取 Top N 商品，同时利用哈希表特性通过 ZSCORE 高效校验用户是否已购买，避免了传统关系型数据库多表关联查询的性能瓶颈。
跳表是什么？为什么 ZSet 用跳表而不用红黑树或 B+ 树？
跳表核心原理
一句话原理：跳表是一种多层索引的链表，通过在有序链表上增加多级随机索引，实现类似二分查找的效率，平均时间复杂度O(logN)，同时保持链表顺序遍历和范围查询的优势。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /**
* 跳表数据结构源码解析
*/
// 跳表节点
typedef struct zskiplistNode {
sds ele; // 存储的元素（字符串）
double score; // 分数（排序依据）
struct zskiplistNode *backward; // 后退指针（用于逆序）
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned int span; // 跨度（用于快速计算排名）
} level[]; // 柔性数组，每层一个指针+跨度
} zskiplistNode;
// 跳表结构
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头尾节点
unsigned long length; // 元素数量
int level; // 当前最大层数
} zskiplist;
// 跳表查询过程（查找分数为100的元素）
// 1. 从最高层（level 3）开始，沿着前进指针向右移动
// L3: head -> node1(score=30) -> node4(score=120) (120>100，向下)
// 2. 降到第2层继续
// L2: node1(30) -> node2(50) -> node3(80) -> node4(120) (120>100，向下)
// 3. 降到第1层
// L1: node3(80) -> target(100) 找到目标
//
// 整个过程类似二分查找，但通过随机索引实现
// 跳表插入时随机决定层数
int zslRandomLevel(void) {
int level = 1;
// 每次有25%的概率增加一层
while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) {
level += 1;
}
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
|
项目场景：在游戏排行榜中，需要实时查询"玩家排名第几"、“前100名玩家”、“分数在1000-2000之间的玩家数量”。跳表的多层索引让这些操作都能在O(logN)时间内完成，支撑千万级玩家的实时排名。
跳表 vs 红黑树 vs B+树
一句话原理：ZSet选择跳表而非红黑树或B+树，主要基于三个原因：范围查询效率（跳表链表结构天然支持顺序访问）、实现简单（无旋转/变色等复杂操作）、并发友好（锁粒度可控）。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| /**
* 三种数据结构对比
*/
// ============ 1. 跳表 vs 红黑树 ============
// 红黑树（平衡二叉树）特点：
// - 查找/插入/删除 O(logN)
// - 范围查询需要中序遍历，实现复杂
// - 插入删除需要旋转和变色，实现复杂
// - 内存占用：每个节点2个指针（左右子节点）+颜色标记
// 跳表特点：
// - 查找/插入/删除 O(logN)
// - 范围查询直接沿着底层链表遍历 O(logN+M)
// - 插入删除通过修改指针，无需复杂旋转
// - 实现简单，代码量只有红黑树的1/3
// 范围查询对比
// 红黑树范围查询（获取分数在100-200之间的元素）
// 需要：找到第一个≥100的节点，然后中序遍历，涉及递归/栈
// 跳表范围查询（ZRANGEBYSCORE）
zskiplistNode *zslFirstInRange(zskiplist *zsl, double min, double max) {
zskiplistNode *x = zsl->header;
// 找到第一个≥min的节点
for (int i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward && x->level[i].forward->score < min) {
x = x->level[i].forward;
}
}
x = x->level[0].forward;
// 直接沿着底层链表遍历即可
return (x && x->score <= max) ? x : NULL;
}
// ============ 2. 跳表 vs B+树 ============
// B+树特点：
// - 多路搜索树，节点存储多个key
// - 叶子节点用链表连接，适合范围查询
// - 主要用于数据库索引（磁盘IO优化）
// 跳表特点：
// - 内存数据结构，无需考虑磁盘IO
// - 实现比B+树简单得多
// - 随机层数设计避免了复杂的节点分裂合并
// 为什么不用B+树？
// B+树是为磁盘存储优化，节点大小通常等于磁盘页（4KB）
// 内存中这种设计反而浪费空间，且节点分裂合并成本高
// Redis作者评论（源码注释）
// 红黑树实现更复杂，而跳表实现简单且足够高效
// There's no reason to use a red-black tree instead of a skiplist.
|
项目场景：在延时队列中，需要按时间排序并支持范围查询（获取所有到期任务）。跳表的底层链表可以快速顺序遍历所有元素，而红黑树需要复杂的中序遍历；跳表的实现简单也让Redis代码更易维护，这是工程实践的重要考量。
ZSet的复合结构：跳表+哈希表
一句话原理：ZSet采用跳表+哈希表的复合结构，哈希表负责快速单点查询（O(1)），跳表负责范围查询和排序（O(logN)），两者结合既保证了元素唯一性，又实现了高效的有序操作。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| /**
* ZSet复合结构源码解析
*/
typedef struct zset {
dict *dict; // 哈希表：元素 -> 分数（用于快速查找和唯一性保证）
zskiplist *zsl; // 跳表：按分数排序（用于范围查询和排名）
} zset;
// ZADD操作：同时更新两个结构
int zsetAdd(robj *zobj, double score, sds ele, int *flags) {
zset *zs = zobj->ptr;
dictEntry *de = dictFind(zs->dict, ele); // 先查哈希表
if (de != NULL) {
// 元素已存在，更新分数
double oldscore = *(double*)dictGetVal(de);
// 1. 更新哈希表中的分数
dictSetVal(zs->dict, de, &score);
// 2. 更新跳表中的位置（删除再插入）
zslDelete(zs->zsl, oldscore, ele);
zslInsert(zs->zsl, score, ele);
} else {
// 元素不存在，插入新元素
// 1. 插入跳表
zslInsert(zs->zsl, score, ele);
// 2. 插入哈希表
dictAdd(zs->dict, ele, &score);
}
}
// ZRANK查询排名（利用跳表跨度）
unsigned long zsetGetRank(zset *zs, double score, sds ele) {
// 先查哈希表确认元素存在，然后去跳表计算排名
dictEntry *de = dictFind(zs->dict, ele);
if (!de) return -1;
// 跳表计算排名（利用span字段）
return zslGetRank(zs->zsl, score, ele);
}
// ZSCORE获取分数（利用哈希表）
double zsetGetScore(zset *zs, sds ele) {
dictEntry *de = dictFind(zs->dict, ele);
return de ? *(double*)dictGetVal(de) : 0;
}
|
项目场景：在直播间礼物排行榜中，需要同时支持：查询某用户当前排名（ZRANK）、给用户增加礼物值（ZINCRBY）、获取前十名（ZREVRANGE）。哈希表让ZSCORE和ZINCRBY直接定位元素，跳表让排名和范围查询高效，两者缺一不可。
完整实战指南
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| /**
* 跳表与ZSet完整实战指南
*/
public class SkipListGuide {
/**
* 1. 时间复杂度对比表
*/
public class ComplexityComparison {
// 操作 跳表 红黑树 B+树
// 插入 O(logN) O(logN) O(logN)
// 删除 O(logN) O(logN) O(logN)
// 查找 O(logN) O(logN) O(logN)
// 范围查询 O(logN+M) O(logN+M) O(logN+M)
// 实现复杂度 简单 复杂 复杂
// 内存占用 中 低 高（节点存储多个key）
// 并发友好 是 否（需要全局锁） 否
}
/**
* 2. 跳表核心特性
*/
public class SkipListFeatures {
// 1. 随机层数：平均每个节点1/(1-p)层，p=0.25
// 2. 空间复杂度：O(N)，平均每个节点1.33个指针
// 3. 查询效率：平均logN次比较
// 跳表高度与元素数量的关系
// 元素数 最大层数 平均层数
// 1000 10 4
// 1万 14 5
// 100万 20 6
}
/**
* 3. ZSet应用场景
*/
public class ZSetScenarios {
// 场景1：排行榜
ZADD rank:game 1000 "player1"
ZINCRBY rank:game 500 "player1"
ZREVRANGE rank:game 0 9 WITHSCORES // 前十名
ZRANK rank:game "player1" // 查询排名
// 场景2：延时队列
ZADD delay:queue 1640995200 "task1"
ZADD delay:queue 1641081600 "task2"
ZRANGEBYSCORE delay:queue 0 1640995200 // 获取到期的任务
// 场景3：热点新闻（按点击量排序）
ZINCRBY news:hot 1 "news:1001"
ZREVRANGE news:hot 0 9 // 热点新闻TOP10
// 场景4：商品销量榜
ZINCRBY sales:day 5 "product:2001" // 增加销量
ZREVRANGE sales:day 0 9 WITHSCORES // 日销量榜
}
/**
* 4. 面试必备
*/
public class InterviewQA {
// Q: 跳表的层数如何决定？
// A: 随机生成，概率1/4，最大32层
// Q: 跳表为什么比红黑树更适合ZSet？
// A: 范围查询方便，实现简单，并发友好
// Q: 跳表的空间复杂度？
// A: O(N)，平均每个节点1.33个指针
// Q: ZSet为什么还要用哈希表？
// A: 快速单点查询（O(1)），保证唯一性
}
}
/**
* 跳表总结表
*
* 特性 说明
* 结构 多层有序链表
* 查询方式 从高层向低层逐层搜索
* 时间复杂度 O(logN)
* 空间复杂度 O(N) + O(N logN) 指针
* 实现复杂度 低（约200行C代码）
*
* 优势：
* 1. 范围查询友好（链表遍历）
* 2. 实现简单（无旋转/变色）
* 3. 并发友好（锁粒度可控）
* 4. 内存占用可控
*/
// 面试金句
// "跳表就像'城市地铁系统'：
// 底层是'地面道路'（普通链表），
// 上层是'快速地铁'（索引层），
// 要去城市另一端，先坐地铁快速穿过大片区域，再换地面道路到具体位置。
// 红黑树像'单轨列车'，虽然也快，但想中途下车看风景（范围查询）就麻烦了；
// B+树像'高铁网络'，为跨城设计（磁盘IO），在城市里（内存）反而太笨重。
// 在排行榜系统中，跳表的'地铁+地面'设计让ZSet既能快速找到玩家排名，
// 又能轻松遍历前100名，完美匹配业务需求。"
|
Redis 的哈希表是如何实现的？rehash 的过程是怎样的？
哈希表核心结构
一句话原理：Redis的哈希表基于拉链法解决冲突，采用渐进式rehash机制，通过维护两个哈希表（ht[0]和ht[1]）实现平滑扩容，在扩容时分多次迁移数据，避免一次性rehash带来的服务停顿。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| /**
* Redis哈希表核心数据结构
*/
// 哈希表节点（链地址法）
typedef struct dictEntry {
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值（支持多种类型）
struct dictEntry *next; // 指向下一个节点（解决冲突）
} dictEntry;
// 哈希表（每个表包含多个桶）
typedef struct dictht {
dictEntry **table; // 桶数组（指向dictEntry指针的指针）
unsigned long size; // 桶的数量（哈希表大小）
unsigned long sizemask; // 掩码 = size - 1（用于计算索引）
unsigned long used; // 已使用的节点数量
} dictht;
// Redis字典（核心结构）
typedef struct dict {
dictType *type; // 类型特定函数（hash函数、key比较等）
void *privdata; // 私有数据
dictht ht[2]; // 两个哈希表（ht[0]主表，ht[1]用于rehash）
long rehashidx; // rehash进度（-1表示未进行）
int16_t pauserehash; // 暂停rehash标志
} dict;
|
项目场景：在缓存系统中，当数据量从100万增长到1000万时，哈希表需要扩容。如果没有渐进式rehash，扩容期间所有读写请求都会被阻塞，导致服务不可用。Redis的渐进式rehash让扩容过程对客户端透明，保证了高可用性。
渐进式rehash完整过程
一句话原理：rehash分为初始化、分批迁移、完成切换三个阶段：先为ht[1]分配更大空间，设置rehashidx=0；然后在每次增删改查操作时，顺带将ht[0]的一个桶迁移到ht[1]；全部迁移完成后交换ht[0]和ht[1]，rehashidx置为-1。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| /**
* 渐进式rehash源码解析
*/
// ============ 1. rehash初始化：触发扩容 ============
// 检查是否需要扩容（每次添加元素时调用）
static int _dictExpandIfNeeded(dict *d) {
// 如果正在rehash，直接返回
if (dictIsRehashing(d)) return DICT_OK;
// 如果负载因子 >= 1（BGSAVE/BGREWRITEAOF时负载因子 >= 5）
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) {
// 扩容为原大小的2倍
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
// 初始化rehash
int dictExpand(dict *d, unsigned long size) {
// 计算实际大小（2的幂次方）
unsigned long realsize = _dictNextPower(size);
dictht n; // 新哈希表
n.size = realsize;
n.sizemask = realsize - 1;
n.table = zcalloc(realsize * sizeof(dictEntry*));
n.used = 0;
d->ht[1] = n; // 新表作为ht[1]
d->rehashidx = 0; // 开始rehash
return DICT_OK;
}
// ============ 2. 单步rehash：迁移一个桶 ============
// 每次增删改查时调用，迁移一个桶
int dictRehash(dict *d, int n) {
int empty_visits = n * 10; // 最多跳过空桶数
while (n-- && d->ht[0].used != 0) {
// 找到下一个非空桶
while (d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits <= 0) return 1;
}
// 获取当前桶的链表头
dictEntry *de = d->ht[0].table[d->rehashidx];
// 将链表中的所有节点迁移到ht[1]
while (de) {
dictEntry *next = de->next;
// 重新计算在ht[1]中的索引
unsigned int h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = next;
}
// 清空当前桶
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
return d->ht[0].used == 0; // 返回是否完成
}
// ============ 3. 查找操作在rehash中的处理 ============
dictEntry *dictFind(dict *d, const void *key) {
// 如果正在rehash，先执行一步迁移
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算哈希值
unsigned int h = dictHashKey(d, key);
// 先在ht[0]查找
dictEntry *he = d->ht[0].table[h & d->ht[0].sizemask];
while (he) {
if (dictCompareKeys(d, key, he->key)) return he;
he = he->next;
}
// 如果正在rehash，再到ht[1]查找
if (dictIsRehashing(d)) {
he = d->ht[1].table[h & d->ht[1].sizemask];
while (he) {
if (dictCompareKeys(d, key, he->key)) return he;
he = he->next;
}
}
return NULL;
}
// ============ 4. 插入操作在rehash中的处理 ============
int dictAdd(dict *d, void *key, void *val) {
// 如果正在rehash，直接插入到ht[1]
if (dictIsRehashing(d)) {
return dictAddRaw(d, key, val, 1); // 插入到ht[1]
}
return dictAddRaw(d, key, val, 0); // 插入到ht[0]
}
// ============ 5. rehash完成 ============
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
while (dictRehash(d, 100)) { // 每次迁移100个桶
rehashes += 100;
if (timeInMilliseconds() - start > ms) break;
}
// 如果ht[0]为空，完成rehash
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1]; // 将ht[1]赋值给ht[0]
_dictReset(&d->ht[1]);
d->rehashidx = -1;
}
return rehashes;
}
|
项目场景：在电商秒杀系统中，缓存了10万个商品信息。当促销活动开始时，瞬间涌入百万级商品数据，触发哈希表扩容。如果一次性rehash，服务会暂停几十毫秒，导致大量请求超时。渐进式rehash将扩容分散到后续的每个请求中，用户完全感知不到延迟变化。
rehash触发条件与优化策略
一句话原理：rehash触发由负载因子控制：默认负载因子>=1时开始扩容，>=5时强制扩容；当负载因子<0.1时开始缩容。同时，Redis通过子进程优化（BGSAVE期间提高负载因子阈值）避免不必要的rehash。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| /**
* rehash触发条件与优化
*/
// ============ 1. 负载因子计算 ============
// 负载因子 = used / size
// 扩容触发：负载因子 >= 1（默认）
// 强制扩容触发：负载因子 >= 5（BGSAVE期间）
// 缩容触发：负载因子 < 0.1
// ============ 2. 子进程优化 ============
int dict_can_resize = 1; // 是否可以扩容
void dictEnableResize(void) {
dict_can_resize = 1;
}
void dictDisableResize(void) {
dict_can_resize = 0;
}
// 在BGSAVE/BGREWRITEAOF期间，禁止rehash
void updateDictResizePolicy(void) {
if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
dictEnableResize(); // 没有子进程，可以rehash
else
dictDisableResize(); // 有子进程，禁止rehash（提高阈值）
}
// ============ 3. 缩容触发 ============
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
// 如果负载因子小于0.1，需要缩容
return (size > DICT_HT_INITIAL_SIZE && (used*100/size < HASHTABLE_MIN_FILL));
}
void tryResizeHashTables(int dbid) {
if (htNeedsResize(server.db[dbid].dict))
dictResize(server.db[dbid].dict); // 缩容为used的最小2的幂次方
}
|
项目场景：在凌晨低峰期，缓存数据量减少，Redis自动触发缩容，释放内存给操作系统。同时，在BGSAVE期间提高扩容阈值，避免写时复制带来的内存膨胀，这是Redis内存优化的经典实践。
完整实战指南
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| /**
* Redis哈希表完整实战指南
*/
public class HashTableGuide {
/**
* 1. rehash过程图示
*/
public class RehashDiagram {
// 初始状态：
// ht[0]: size=4, used=3
// [0] -> key1 -> key2
// [1] -> key3
// [2] -> NULL
// [3] -> NULL
// ht[1]: NULL (size=0)
// rehashidx = -1
// 触发扩容后：
// ht[1]: size=8, used=0
// [0...7] -> all NULL
// rehashidx = 0
// 第1次操作：迁移桶0
// 将key1和key2重新哈希到ht[1]的位置
// rehashidx = 1
// 第N次操作：所有桶迁移完成
// ht[0]清空，释放内存
// ht[0] = ht[1]
// ht[1]重置，rehashidx = -1
}
/**
* 2. 监控rehash状态
*/
public class MonitorRehash {
// 查看哈希表状态
> INFO stats
// 输出包含：
// hash_max_zipmap_entries 512
// hash_max_zipmap_value 64
// 查看键的编码类型
> OBJECT ENCODING myhash
// "hashtable" 或 "ziplist"
// 查看当前rehash进度（通过debug命令）
> DEBUG HTSTATS 0 // 查看数据库0的哈希表状态
}
/**
* 3. 性能优化建议
*/
public class OptimizationTips {
// 1. 预分配空间：如果知道数据量，可以用dictExpand提前扩容
// 2. 控制负载因子：避免频繁rehash
// 3. 使用hash-max-ziplist-entries控制小对象编码
// 配置示例（redis.conf）
// hash-max-ziplist-entries 512
// hash-max-ziplist-value 64
// activerehashing yes // 主动rehash
}
/**
* 4. 面试必备
*/
public class InterviewQA {
// Q: 渐进式rehash怎么保证一致性？
// A: 查找同时在两个表进行，新增只在ht[1]
// Q: rehash期间会阻塞服务吗？
// A: 不会，每次只迁移一个桶
// Q: 负载因子为什么在BGSAVE期间提高？
// A: 避免写时复制导致内存膨胀
// Q: rehash失败怎么办？
// A: 内存不足时返回错误，数据仍保留在原表
}
}
/**
* 哈希表总结表
*
* 阶段 操作 说明
* 扩容触发 负载因子>=1 开始rehash
* 初始化 ht[1]分配为2倍大小 准备空间
* 渐进迁移 每次操作迁移一个桶 均摊成本
* 查找操作 同时在两个表查找 保证一致性
* 插入操作 只插入到ht[1] 简化逻辑
* 完成 交换ht[0]和ht[1] 清理ht[1]
*
* 关键参数：
* - 负载因子：used/size
* - 扩容阈值：1（默认），5（BGSAVE）
* - 缩容阈值：0.1
* - 桶大小：2的幂次方
*/
// 面试金句
// "Redis的渐进式rehash就像'搬家不搬家'的神奇操作：
// 正常搬家要停业一天（一次性rehash），
// Redis却能做到'边营业边搬家'：
// 白天正常营业时，每接待一个顾客就搬一件家具（每次操作迁移一个桶），
// 顾客完全感觉不到在搬家，月底发现已经搬完了。
// 在电商大促期间，即使缓存数据暴涨，客户也感受不到扩容的延迟，
// 这就是Redis高可用的核心秘诀。理解渐进式rehash，
// 就理解了Redis如何在保证性能的同时实现动态扩容。"
|
Redis 的 List 在元素较少和较多时分别用什么结构存储？（quicklist）
quicklist核心原理
一句话原理：Redis的List底层使用quicklist（快速列表）存储，它是双向链表和压缩列表的结合体：每个节点是一个ziplist（压缩列表），多个节点通过双向指针连接，在内存效率和操作性能间取得平衡。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| /**
* quicklist核心数据结构
*/
// quicklist主结构
typedef struct quicklist {
quicklistNode *head; // 头节点
quicklistNode *tail; // 尾节点
unsigned long count; // 所有ziplist中的元素总数
unsigned long len; // quicklist节点数量
int fill : 16; // 每个节点ziplist最大大小（正数表示元素个数，负数表示字节数限制）
unsigned int compress : 16; // 压缩深度（两端不压缩的节点数）
} quicklist;
// quicklist节点
typedef struct quicklistNode {
struct quicklistNode *prev; // 前驱指针
struct quicklistNode *next; // 后继指针
unsigned char *zl; // 指向压缩列表（ziplist）
unsigned int sz; // ziplist的总字节数
unsigned int count : 16; // ziplist中的元素数量
unsigned int encoding : 2; // 编码方式（RAW或LZF压缩）
unsigned int container : 2; // 存储容器（NONE或PLAIN或PACKED）
unsigned int recompress : 1; // 是否需要重新压缩
unsigned int attempted_compress : 1; // 是否尝试过压缩
unsigned int extra : 10; // 扩展字段
} quicklistNode;
// 压缩列表结构（ziplist）
typedef struct ziplist {
uint32_t zlbytes; // 整个压缩列表占用的字节数
uint32_t zltail; // 列表尾部的偏移量
uint16_t zllen; // 节点数量
uint8_t entry[]; // 节点列表（每个节点包含前一节点长度、编码、内容）
} ziplist;
|
项目场景：在IM系统中，每个聊天室的消息列表可能存储数千条消息。如果使用普通链表，每个节点都要存储prev/next指针，内存开销大；如果使用单一ziplist，插入和删除操作需要大量内存移动。quicklist通过分块存储完美解决了这个问题。
元素较少时：单个ziplist
一句话原理：当List元素较少或单个元素较小时，quicklist只有一个节点，这个节点的ziplist连续存储所有元素，利用内存紧凑的特性节省空间，同时保持Cache友好。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /**
* 元素较少时的存储结构
*/
// 示例：LPUSH list "A" "B" "C"（元素少，只有3个）
// 此时quicklist结构：
// head ──→ quicklistNode
// │
// zl ──→ ziplist
// ├── entry1: "A"
// ├── entry2: "B"
// └── entry3: "C"
// 查看List编码
> LPUSH smalllist "A" "B" "C"
> OBJECT ENCODING smalllist
"quicklist" // 虽然底层是quicklist，但只有一个节点
// ziplist内部结构（连续内存）
// [zlbytes][zltail][zllen][entry1][entry2][entry3][end]
// entry结构：prevlen + encoding + content
// 创建ziplist的源码
unsigned char *ziplistNew(void) {
unsigned int bytes = ZIPLIST_HEADER_SIZE + ZIPLIST_END_SIZE;
unsigned char *zl = zmalloc(bytes);
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = 0;
zl[bytes - 1] = ZIP_END;
return zl;
}
// 检查是否需要拆分ziplist
int quicklistNodeExceedsLimit(quicklistNode *node, int fill) {
if (fill < 0) { // 负数表示字节限制
return node->sz > -fill; // 是否超过字节限制
} else {
return node->count > fill; // 是否超过元素个数限制
}
}
|
项目场景：在配置中心中，存储某个应用的最近10条操作日志。这10条日志使用单个ziplist存储，内存占用极小，且遍历时CPU缓存命中率高，读取性能极佳。
元素较多时：多个ziplist节点
一句话原理：当List元素增多，单个ziplist达到阈值（默认8KB或元素数>8192）时，quicklist会拆分为多个节点，每个节点是一个独立的ziplist，节点间通过双向指针连接，平衡了内存利用率和操作性能。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| /**
* 元素较多时的存储结构
*/
// 当元素增多时，ziplist会拆分
> LPUSH largelist "A1" "A2" ... (超过8192个元素)
// 结构变为：
// head ──→ quicklistNode1 ──→ quicklistNode2 ──→ quicklistNode3
// │ │ │
// zl1 zl2 zl3
// [A1..A1000] [A1001..A2000] [A2001..A3000]
// 插入新元素时的处理
void quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
// 检查头节点是否有空间
if (likely(_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
// 头节点还有空间，直接插入
_quicklistNodePush(quicklist->head, value, sz, 0);
} else {
// 头节点已满，创建新节点
quicklistNode *node = quicklistCreateNode();
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
quicklistInsertNodeBefore(quicklist, quicklist->head, node);
}
}
// 判断节点是否允许插入
int _quicklistNodeAllowInsert(const quicklistNode *node, const int fill, const size_t sz) {
if (unlikely(!node)) return 0;
int ziplist_overhead;
// 估算插入后ziplist的大小
size_t new_sz = node->sz + sz + ziplist_overhead;
if (fill < 0) { // 按字节限制
return new_sz <= -fill;
} else { // 按元素个数限制
return node->count < fill;
}
}
// 配置参数（redis.conf）
list-max-ziplist-size -2 // 负数表示字节限制：-1=4KB，-2=8KB，-3=16KB，-4=32KB，-5=64KB
list-compress-depth 0 // 压缩深度：0表示都不压缩
|
项目场景：在直播聊天室中，消息列表可能达到数十万条。quicklist将消息分块存储，每块8KB，这样插入新消息时只需操作最后一块，删除旧消息时释放整块，避免了频繁的内存移动，性能稳定。
quicklist的压缩优化
一句话原理：quicklist支持LZF压缩算法，可以对中间节点进行压缩，只保留两端节点的数据，在内存紧张时牺牲少量CPU换取大幅内存节省，通过list-compress-depth配置压缩深度。
一句话源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| /**
* quicklist压缩机制
*/
// 配置压缩深度（redis.conf）
list-compress-depth 1 // 两端各保留1个节点不压缩，其他压缩
// 压缩节点
void quicklistCompressNode(quicklistNode *node) {
// 使用LZF算法压缩ziplist
size_t comp_size = LZF_compress(node->zl, node->sz, node->compress, LZF_MAX_COMPRESS);
if (comp_size > 0) {
node->encoding = QUICKLIST_NODE_ENCODING_LZF;
node->compress_size = comp_size;
// 释放原始ziplist内存
zfree(node->zl);
node->zl = node->compress;
}
}
// 解压缩节点
unsigned char *quicklistDecompressNode(quicklistNode *node) {
if (node->encoding == QUICKLIST_NODE_ENCODING_LZF) {
// 解压LZF数据
unsigned char *decomp = zmalloc(node->sz);
LZF_decompress(node->compress, node->compress_size, decomp, node->sz);
node->encoding = QUICKLIST_NODE_ENCODING_RAW;
zfree(node->compress);
node->zl = decomp;
}
return node->zl;
}
// 访问节点时自动解压
quicklistNode *quicklistNext(quicklistIter *iter) {
quicklistNode *node = iter->current;
// 如果是压缩节点，先解压
if (node->encoding == QUICKLIST_NODE_ENCODING_LZF) {
node->zl = quicklistDecompressNode(node);
}
return node;
}
|
项目场景：在物联网设备数据缓存中，需要存储大量历史数据，但内存有限。通过设置list-compress-depth 2，压缩中间的历史数据，只保留最新的几条数据解压状态，内存占用减少70%，同时保证最新数据的快速访问。
完整实战指南
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| /**
* quicklist完整实战指南
*/
public class QuicklistGuide {
/**
* 1. 配置参数详解
*/
public class Configuration {
// list-max-ziplist-size
// 正数：每个节点最多包含的元素个数（如 5）
// 负数：每个节点最多占用的字节数
// -1: 4KB
// -2: 8KB（默认）
// -3: 16KB
// -4: 32KB
// -5: 64KB
// list-compress-depth
// 0: 都不压缩
// 1: 两端各1个节点不压缩
// 2: 两端各2个节点不压缩
// ...以此类推
}
/**
* 2. 性能特性
*/
public class Performance {
// 操作 时间复杂度 说明
// LPUSH/RPUSH O(1) 只需操作头/尾节点
// LPOP/RPOP O(1) 只需操作头/尾节点
// LINDEX O(N) 需要遍历节点
// LINSERT O(N) 需要查找位置
// LRANGE O(N) 需要遍历
// 优化建议：用LRANGE批量获取，避免多次LINDEX
}
/**
* 3. 内存监控
*/
public class MemoryMonitor {
// 查看List内存占用
> MEMORY USAGE mylist
(integer) 10240
// 查看List结构信息
> DEBUG QUICKLIST mylist
// 输出节点数、压缩情况等
}
/**
* 4. 面试必备
*/
public class InterviewQA {
// Q: quicklist为什么要用ziplist作为节点？
// A: 减少指针开销，提高内存利用率
// Q: 压缩深度设置多少合适？
// A: 读写均衡设1，内存紧张设2，压缩全部设0（一般不推荐）
// Q: quicklist和普通链表有什么区别？
// A: quicklist节点内部用ziplist，减少内存碎片
// Q: 如何估算quicklist内存？
// A: 节点数×（节点开销 + 每个ziplist大小）
}
}
/**
* quicklist总结表
*
* 场景 结构 优势
* 元素少 单个ziplist 内存紧凑，CPU缓存友好
* 元素多 多个ziplist节点 避免大块内存移动
* 内存紧张 压缩中间节点 节省内存70%+
*
* 配置调优：
* - 读多写少：增大ziplist大小，减少节点数
* - 写多读少：减小ziplist大小，减少内存移动
* - 内存紧张：增加压缩深度
*/
// 面试金句
// "quicklist就像'分页存储的连环画'：
// 每页（ziplist）是一个小册子，连续画了几十页故事，
// 多个小册子用线装订起来（双向链表），
// 想看最后一页，先翻到最后一个小册子，再翻到最后一页。
// 当故事很短，一册就够了（元素少）；
// 故事很长，就分成多册（元素多）；
// 中间的故事看得少，还可以压成'缩略版'（LZF压缩）。
// 这种设计让Redis List既能高效处理百万级消息队列，
// 又能极致节省内存，是工程实践的典范。"
|