Redis 核心数据结构总览（对象系统设计）
Redis支持五种基本数据类型：String、List、Set、Hash、ZSet，还有Stream和Module类型。但底层实现不是一对一的，而是通过对象系统（redisObject）抽象，让一种类型可以有多种编码方式，根据数据特征自动选择最优实现。
一、redisObject：统一的对象抽象
所有Redis值都封装成redisObject：
1// server.h
2typedef struct redisObject {
3 unsigned type:4; // 类型，4位，取值0-15
4 unsigned encoding:4; // 编码，4位，取值0-15
5 unsigned lru:LRU_BITS; // LRU时间（24位）或LFU 数据
6 int refcount; // 引用计数
7 void *ptr; // 指向实际数据的指针
8} robj;
16字节的结构体，包含了Redis值的全部信息。
1.1 type：对象类型
1#define OBJ_STRING 0 // 字符串
2#define OBJ_LIST 1 // 列表
3#define OBJ_SET 2 // 集合
4#define OBJ_ZSET 3 // 有序集合
5#define OBJ_HASH 4 // 哈希
6#define OBJ_MODULE 5 // 模块类型
7#define OBJ_STREAM 6 // 流
TYPE key 命令返回的就是这个type字段。
1.2 encoding：编码方式
同一种类型可以有多种底层实现：
1#define OBJ_ENCODING_RAW 0 // 原始SDS字符串
2#define OBJ_ENCODING_INT 1 // 整数编码
3#define OBJ_ENCODING_HT 2 // 哈希表（dict）
4#define OBJ_ENCODING_ZIPMAP 3 // zipmap（已废弃）
5#define OBJ_ENCODING_LINKEDLIST 4 // 链表（已废弃）
6#define OBJ_ENCODING_ZIPLIST 5 // 压缩列表
7#define OBJ_ENCODING_INTSET 6 // 整数集合
8#define OBJ_ENCODING_SKIPLIST 7 // 跳表
9#define OBJ_ENCODING_EMBSTR 8 // 嵌入式字符串
10#define OBJ_ENCODING_QUICKLIST 9 // 快速列表
11#define OBJ_ENCODING_STREAM 10 // 流
OBJECT ENCODING key 命令可以查看编码方式。
1.3 lru：LRU/LFU信息
24位字段，复用于两种场景：
LRU模式：存储最后一次访问时间（秒级精度的低24位）
1#define LRU_BITS 24
2#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) // 约194天
3#define LRU_CLOCK_RESOLUTION 1000 // 1秒更新一次
4
5unsigned int getLRUClock(void) {
6 return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
7}
LFU 模式：高16位存储上次衰减时间，低8位存储访问频率
1+----------------+--------+
2| 16 bits | 8 bits |
3| Last Decr Time | Log_C |
4+----------------+--------+
1.4 refcount：引用计数
1#define OBJ_SHARED_REFCOUNT INT_MAX // 共享对象的引用计数
2
3void incrRefCount(robj *o) {
4 if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount++;
5}
6
7void decrRefCount(robj *o) {
8 if (o->refcount == 1) {
9 // 引用计数归零，释放对象
10 switch(o->type) {
11 case OBJ_STRING: freeStringObject(o); break;
12 case OBJ_LIST: freeListObject(o); break;
13 case OBJ_SET: freeSetObject(o); break;
14 case OBJ_ZSET: freeZsetObject(o); break;
15 case OBJ_HASH: freeHashObject(o); break;
16 case OBJ_MODULE: freeModuleObject(o); break;
17 case OBJ_STREAM: freeStreamObject(o); break;
18 default: serverPanic("Unknown object type"); break;
19 }
20 zfree(o);
21 } else {
22 if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");
23 if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount--;
24 }
25}
引用计数用于：
- 对象共享（共享整数）
- 参数传递时避免拷贝
- 自动内存回收
1.5 ptr：数据指针
指向实际的底层数据结构，根据encoding不同指向不同类型。
二、String类型
String有三种编码方式：
2.1 INT编码
整数值且范围在 LONG_MIN 到 LONG_MAX 之间：
1// object.c
2robj *createStringObjectFromLongLongWithOptions(long long value, int valueobj) {
3 robj *o;
4
5 // 小整数用共享对象
6 if (value >= 0 && value < OBJ_SHARED_INTEGERS && valueobj == 0) {
7 incrRefCount(shared.integers[value]);
8 o = shared.integers[value];
9 } else {
10 if (value >= LONG_MIN && value <= LONG_MAX) {
11 o = createObject(OBJ_STRING, NULL);
12 o->encoding = OBJ_ENCODING_INT;
13 o->ptr = (void*)((long)value); // 直接存值，不用指针
14 } else {
15 o = createObject(OBJ_STRING, sdsfromlonglong(value));
16 }
17 }
18 return o;
19}
INT编码的优化：ptr直接存整数值，不分配额外内存。
2.2 EMBSTR编码
短字符串（≤44 字节）用嵌入式编码：
1#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
2
3robj *createEmbeddedStringObject(const char *ptr, size_t len) {
4 // 一次分配：robj + sds header + 字符串内容
5 robj *o = zmalloc(sizeof(robj) + sizeof(struct sdshdr8) + len + 1);
6 struct sdshdr8 *sh = (void*)(o+1); // 紧跟在robj后面
7
8 o->type = OBJ_STRING;
9 o->encoding = OBJ_ENCODING_EMBSTR;
10 o->ptr = sh->buf; // ptr指向sh->buf
11 o->refcount = 1;
12
13 sh->len = len;
14 sh->alloc = len;
15 sh->flags = SDS_TYPE_8;
16 if (ptr == SDS_NOINIT) {
17 sh->buf[len] = '\0';
18 } else if (ptr) {
19 memcpy(sh->buf, ptr, len);
20 sh->buf[len] = '\0';
21 }
22 return o;
23}
内存布局：
1+-------------+------------+-------+
2| redisObject | sdshdr8 | "..." |
3| 16 bytes | 3 bytes | len+1 |
4+-------------+------------+-------+
5 ▲ ▲
6 │ │
7 o->ptr sdshdr8
一次malloc，一次free，内存连续，缓存友好。44字节的限制是为了让整个对象不超过64字节（jemalloc 的一个内存块大小）。
2.3 RAW编码
长字符串（>44字节）用RAW编码：
1robj *createRawStringObject(const char *ptr, size_t len) {
2 // 两次分配：robj和sds分开
3 sds s = sdsnewlen(ptr, len);
4 robj *o = createObject(OBJ_STRING, s);
5 o->encoding = OBJ_ENCODING_RAW;
6 return o;
7}
内存布局：
1redisObject (16B) SDS
2+-------------+ +------------+-------+
3| type/enc... | | sdshdr | "..." |
4| ptr ───────────────▶| len/alloc | |
5+-------------+ +------------+-------+
2.4 String编码转换
1// object.c
2robj *tryObjectEncoding(robj *o) {
3 long value;
4 sds s = o->ptr;
5 size_t len;
6
7 if (o->encoding == OBJ_ENCODING_RAW) {
8 len = sdslen(s);
9 // 尝试转成整数
10 if (string2l(s, len, &value)) {
11 // 小整数用共享对象
12 if (value >= 0 && value < OBJ_SHARED_INTEGERS) {
13 decrRefCount(o);
14 incrRefCount(shared.integers[value]);
15 return shared.integers[value];
16 } else {
17 // 整数编码
18 if (value >= LONG_MIN && value <= LONG_MAX) {
19 o->encoding = OBJ_ENCODING_INT;
20 sdsfree(s);
21 o->ptr = (void*)((long)value);
22 return o;
23 }
24 }
25 }
26 }
27 return o;
28}
三、List类型
Redis3.2之后，List统一用quicklist：
1// quicklist.h
2typedef struct quicklist {
3 quicklistNode *head;
4 quicklistNode *tail;
5 unsigned long count; // 元素总数
6 unsigned long len; // 节点数
7 int fill : 16; // 每个ziplist的大小限制
8 unsigned int compress : 16; // 中间节点压缩深度
9} quicklist;
10
11typedef struct quicklistNode {
12 struct quicklistNode *prev;
13 struct quicklistNode *next;
14 unsigned char *zl; // ziplist
15 unsigned int sz; // ziplist字节数
16 unsigned int count : 16; // ziplist元素数
17 unsigned int encoding : 2; // RAW或LZF压缩
18 unsigned int container : 2; // NONE或ziplist
19 unsigned int recompress : 1;
20 unsigned int attempted_compress : 1;
21 unsigned int extra : 10;
22} quicklistNode;
结构：
1quicklist
2 │
3 ▼
4+------------------+ +------------------+
5| Node: ziplist |────▶| Node: ziplist |────▶ ...
6| [a,b,c,d,e] |◀────│ [f,g,h,i,j] |
7+------------------+ +------------------+
quicklist是linked list + ziplist的混合体：
- linked list：插入删除O(1)，但内存不连续，指针开销大
- ziplist：内存连续，但插入删除要移动内存O(N)
quicklist取长补短：每个节点是一个ziplist，节点之间用链表连接。
创建List对象：
1// object.c
2robj *createQuicklistObject(void) {
3 quicklist *l = quicklistCreate();
4 robj *o = createObject(OBJ_LIST, l);
5 o->encoding = OBJ_ENCODING_QUICKLIST;
6 return o;
7}
四、Set类型
Set有两种编码：
4.1 INTSET编码
元素都是整数，且数量少：
1// intset.h
2typedef struct intset {
3 uint32_t encoding; // INTSET_ENC_INT16/INT32/INT64
4 uint32_t length;
5 int8_t contents[]; // 有序整数数组
6} intset;
特点：
- 有序数组，二分查找O(log N)
- 自动升级编码：插入int64时整体升级
- 内存紧凑
1// object.c
2robj *createIntsetObject(void) {
3 intset *is = intsetNew();
4 robj *o = createObject(OBJ_SET, is);
5 o->encoding = OBJ_ENCODING_INTSET;
6 return o;
7}
4.2 HT编码（哈希表）
元素包含非整数，或数量超限：
1robj *createSetObject(void) {
2 dict *d = dictCreate(&setDictType, NULL);
3 robj *o = createObject(OBJ_SET, d);
4 o->encoding = OBJ_ENCODING_HT;
5 return o;
6}
4.3 Set编码转换
1// t_set.c
2#define OBJ_SET_MAX_INTSET_ENTRIES 512
3
4int setTypeConvert(robj *setobj, int enc) {
5 if (enc == OBJ_ENCODING_HT) {
6 dict *d = dictCreate(&setDictType, NULL);
7 intset *is = setobj->ptr;
8 int64_t intele;
9 char buf[32];
10
11 // 遍历intset，逐个插入哈希表
12 while (intsetGet(is, 0, &intele)) {
13 ll2string(buf, 32, intele);
14 dictAdd(d, sdsnew(buf), NULL);
15 }
16 setobj->encoding = OBJ_ENCODING_HT;
17 zfree(is);
18 setobj->ptr = d;
19 }
20 return C_OK;
21}
转换触发条件：
- 插入非整数值
- 元素数量超过512
五、Hash类型
Hash有两种编码：
5.1 ZIPLIST编码
元素少，key/value都短：
1robj *createHashObject(void) {
2 unsigned char *zl = ziplistNew();
3 robj *o = createObject(OBJ_HASH, zl);
4 o->encoding = OBJ_ENCODING_ZIPLIST;
5 return o;
6}
ziplist存储格式：
1[field1 length][field1][value1 length][value1][field2 length][field2]...
5.2 HT编码
元素多，或key/value长：
1robj *createHashObject(void) {
2 unsigned char *zl = ziplistNew();
3 robj *o = createObject(OBJ_HASH, zl);
4 o->encoding = OBJ_ENCODING_ZIPLIST;
5 return o;
6}
5.3 Hash编码转换
1// t_hash.c
2void hashTypeConvert(robj *o, int enc) {
3 if (o->encoding == OBJ_ENCODING_ZIPLIST) {
4 hashTypeConvertZiplist(o, enc);
5 } else if (o->encoding == OBJ_ENCODING_HT) {
6 serverPanic("Not implemented");
7 }
8}
转换触发条件（可配置）：
- 元素数量超过
hash-max-ziplist-entries（默认512） - 单个value长度超过
hash-max-ziplist-value（默认64）
六、ZSet类型
ZSet有两种编码：
6.1 ZIPLIST编码
元素少，member/score都短：
1robj *createZsetZiplistObject(void) {
2 unsigned char *zl = ziplistNew();
3 robj *o = createObject(OBJ_ZSET, zl);
4 o->encoding = OBJ_ENCODING_ZIPLIST;
5 return o;
6}
ziplist存储：member1, score1, member2, score2, … 按score排序。
6.2 SKIPLIST编码
元素多：
1// server.h
2typedef struct zset {
3 dict *dict; // member -> score映射
4 zskiplist *zsl; // score有序的跳表
5} zset;
6
7typedef struct zskiplist {
8 struct zskiplistNode *header, *tail;
9 unsigned long length;
10 int level; // 最高层数
11} zskiplist;
12
13typedef struct zskiplistNode {
14 sds ele;
15 double score;
16 struct zskiplistNode *backward;
17 struct zskiplistLevel {
18 struct zskiplistNode *forward;
19 unsigned long span; // 跨度，用于排名计算
20 } level[];
21} zskiplistNode;
创建ZSet对象：
1robj *createZsetObject(void) {
2 zset *zs = zmalloc(sizeof(*zs));
3 zs->dict = dictCreate(&zsetDictType, NULL);
4 zs->zsl = zslCreate();
5 robj *o = createObject(OBJ_ZSET, zs);
6 o->encoding = OBJ_ENCODING_SKIPLIST;
7 return o;
8}
为什么要同时维护dict和skiplist？
| 操作 | dict | skiplist |
|---|---|---|
| ZSCORE | O(1) ✗ | O(log N) |
| ZRANGE | O(N) ✗ | O(log N + M) |
| ZRANK | O(N) ✗ | O(log N) |
两者结合，各种操作都高效。
6.3 ZSet编码转换
触发条件：
- 元素数量超过
zset-max-ziplist-entries（默认128） - 单个member长度超过
zset-max-ziplist-value（默认64）
七、Stream类型
Stream是Redis 5.0新增的类型，用于消息队列场景：
1// stream.h
2typedef struct stream {
3 rax *rax; // 存储ID -> 消息的映射
4 uint64_t length; // 消息数量
5 streamID last_id; // 最后一条消息ID
6 streamID first_id; // 第一条消息ID
7 streamID max_deleted_entry_id; // 最大已删除ID
8 rax *cgroups; // 消费者组
9} stream;
10
11typedef struct streamID {
12 uint64_t ms; // 毫秒时间戳
13 uint64_t seq; // 序列号
14} streamID;
创建 Stream 对象：
1robj *createStreamObject(void) {
2 stream *s = streamNew();
3 robj *o = createObject(OBJ_STREAM, s);
4 o->encoding = OBJ_ENCODING_STREAM;
5 return o;
6}
八、类型编码对照表
| 类型 | 可能的编码 | 使用条件 |
|---|---|---|
| String | INT | 整数，范围 [LONG_MIN, LONG_MAX] |
| String | EMBSTR | 字符串长度≤44字节 |
| String | RAW | 字符串长度>44字节 |
| List | QUICKLIST | 始终 |
| Set | INTSET | 全整数，数量≤512 |
| Set | HT | 其他 |
| Hash | ZIPLIST | 元素数≤512，value长度≤64 |
| Hash | HT | 其他 |
| ZSet | ZIPLIST | 元素数≤128，member长度≤64 |
| ZSet | SKIPLIST | 其他 |
| Stream | STREAM | 始终 |
— END —