Redis String底层结构与SDS

Redis 的五种数据结构各有特色，用对了才能发挥它的优势。很多人只用到了 String 和 Hash，却不知道 List、Set、ZSet 在特定场景下更合适。本文从应用场景出发，讲什么时候用什么类型。

一、为什么不用C字符串

#

1.1 C字符串的缺陷

C语言使用\0结尾的字符数组表示字符串：

char str[] = "hello";  // h-e-l-l-o-\0

缺陷一：获取长度O(n)

strlen(str);  // 需要遍历到\0，O(n)

缺陷二：缓冲区溢出

char str[5] = "hello";
strcat(str, " world");  // 越界写入，未定义行为

缺陷三：频繁内存分配

// 每次修改字符串长度，可能需要重新分配内存
char *str = malloc(6);
strcat(str, "!");  // 需要realloc

缺陷四：二进制不安全

// 不能包含\0字符
char str[] = "he\0llo";  // strlen返回2，实际想存6字节

#

1.2 SDS的设计目标

Redis需要一种更安全、更高效的字符串结构：

• O(1)获取长度
• 避免缓冲区溢出
• 减少内存分配次数
• 支持二进制数据

二、SDS结构

#

2.1 SDS定义

Redis 3.2之后，SDS根据字符串长度使用不同头部结构：

// sdshdr5（不再使用，但保留定义）
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags;  // 低3位存类型，高5位存长度
    char buf[];
};

// sdshdr8（长度<256）
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;        // 已使用长度
    uint8_t alloc;      // 分配的总长度（不含头部和\0）
    unsigned char flags; // 标志位
    char buf[];         // 柔性数组，实际数据
};

// sdshdr16（长度<65536）
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};

// sdshdr32
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};

// sdshdr64
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};

#

2.2 SDS内存布局

sdshdr8 示例（存储"Redis"）：
┌─────────┬─────────┬─────────┬──────┬─────┐
│  len=5  │ alloc=5 │ flags=1 │ R-e-d-i-s │ \0 │
└─────────┴─────────┴─────────┴──────┴─────┘
  1字节    1字节     1字节     5字节   1字节

总内存：1 + 1 + 1 + 5 + 1 = 9字节

注意：buf末尾仍然以\0结尾，这样可以复用部分C字符串函数。

#

2.3 SDS操作API

// 创建SDS
sds sdsnew(const char *init);
sds sdsnewlen(const void *init, size_t initlen);
sdsempty(void);

// 释放
void sdsfree(sds s);

// 获取长度（O(1)）
size_t sdslen(const sds s);

// 获取可用空间
size_t sdsavail(const sds s);

// 扩容
sds sdsMakeRoomFor(sds s, size_t addlen);

// 追加
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);

// 范围清除（惰性释放）
void sdsclear(sds s);

三、SDS核心设计

#

3.1 空间预分配

SDS修改字符串时，不仅分配需要的空间，还会预分配额外空间：

sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh = (void*)(s - sizeof(struct sdshdr));
    size_t free = sdsavail(s);
    
    // 空间足够，直接返回
    if (free >= addlen) return s;
    
    size_t len = sdslen(s);
    size_t newlen = len + addlen;
    
    // 预分配策略
    if (newlen < SDS_MAX_PREALLOC) {
        // 小于1MB，分配2倍空间
        newlen *= 2;
    } else {
        // 大于1MB，额外分配1MB
        newlen += SDS_MAX_PREALLOC;
    }
    
    // 重新分配内存
    // ...
}

策略：

• 修改后长度 < 1MB：分配2倍所需空间
• 修改后长度 >= 1MB：额外分配1MB

优势：

• 减少内存分配次数（从N次降到logN次）
• 均摊时间复杂度接近O(1)

#

3.2 惰性释放

SDS缩短字符串时，不立即释放内存：

void sdsclear(sds s) {
    struct sdshdr *sh = (void*)(s - sizeof(struct sdshdr));
    sh->len = 0;           // 长度设为0
    sh->buf[0] = '\0';     // 第一个字符设为\0
    // 注意：alloc不变，空间不释放！
}

优势：

• 后续追加操作可能不需要重新分配内存
• 避免频繁的内存分配和释放

真正释放：

sds = sdscatsds(sds, "");  // 需要时可以用sdstrim或重新创建

#

3.3 二进制安全

SDS可以存储任意二进制数据：

sds binary = sdsnewlen("\x00\x01\x02\x03", 4);
// len=4，不受\0影响

sdslen(binary);  // 返回4，不是0

因为SDS通过len字段记录长度，而不是依赖\0。

四、RedisObject编码

#

4.1 Redis对象系统

Redis所有数据都封装在redisObject中：

typedef struct redisObject {
    unsigned type:4;        // 数据类型（String/List/Hash/Set/ZSet）
    unsigned encoding:4;    // 编码方式
    unsigned lru:LRU_BITS;  // LRU时间或LFU计数
    int refcount;           // 引用计数
    void *ptr;              // 指向实际数据
} robj;

#

4.2 String的编码方式

编码	说明	转换条件
OBJ_ENCODING_RAW	SDS	字符串长度 > 44字节
OBJ_ENCODING_EMBSTR	嵌入式SDS	字符串长度 <= 44字节
OBJ_ENCODING_INT	整数	可以表示为long的字符串

#

4.3 EMBSTR编码

EMBSTR内存布局（redisObject + sdshdr + 数据 连续内存）：
┌────────────────┬────────────────┬─────────────┐
│  redisObject   │   sdshdr8      │  buf + \0  │
│  (16字节)      │   (3字节)      │             │
└────────────────┴────────────────┴─────────────┘
               连续分配，只需一次malloc

优势：

• 只需一次内存分配
• 释放时也只需一次free
• 更好的缓存局部性

为什么是44字节？

64字节（jemalloc最小分配单位） - 16字节(redisObject) - 3字节(sdshdr8) - 1字节(\0) = 44字节

#

4.4 INT编码

// 如果字符串可以解析为long类型
robj *createStringObjectFromLongLong(long long value) {
    robj *o;
    // 小整数复用共享对象（0-9999）
    if (value >= 0 && value < OBJ_SHARED_INTEGERS) {
        o = shared.integers[value];
    } else {
        o = createObject(OBJ_STRING, NULL);
        o->encoding = OBJ_ENCODING_INT;
        o->ptr = (void*)((long)value);  // 直接存值，不分配内存！
    }
    return o;
}

优势：

• 不额外分配内存
• ptr直接存储整数值

#

4.5 编码转换

SET num "12345"        → INT编码
APPEND num "abc"       → 转换为RAW编码（因为不再是纯数字）

SET str "short"        → EMBSTR编码（<=44字节）
APPEND str "..."       → 如果超过44字节，转换为RAW编码

五、String命令的实现

#

5.1 SET命令

void setCommand(client *c) {
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    // ... 解析选项 ...
    
    // 创建或查找key
    setKey(c->db, c->argv[1], c->argv[2]);
    
    // 设置过期时间
    if (expire) setExpire(c, c->db, c->argv[1], milliseconds);
    
    addReply(c, ok ? shared.ok : shared.err);
}

#

5.2 INCR命令

void incrCommand(client *c) {
    robj *o = lookupKeyWrite(c->db, c->argv[1]);
    
    if (o && o->encoding == OBJ_ENCODING_RAW) {
        // 尝试转换为INT编码
        // ...
    }
    
    if (o && o->encoding == OBJ_ENCODING_INT) {
        long value = (long)o->ptr;
        value++;  // 直接对ptr操作，极快！
        o->ptr = (void*)value;
    }
}

#

5.3 APPEND命令

void appendCommand(client *c) {
    robj *o = lookupKeyWrite(c->db, c->argv[1]);
    
    if (o == NULL) {
        // key不存在，直接创建
        c->argv[2] = tryObjectEncoding(c->argv[2]);
        dbAdd(c->db, c->argv[1], c->argv[2]);
    } else {
        // key存在，追加
        if (o->encoding == OBJ_ENCODING_INT) {
            // 转换为RAW
            o = createStringObjectFromLongLong((long)o->ptr);
        }
        
        // 获取原字符串
        sds s = o->ptr;
        // 追加新内容
        s = sdscatsds(s, c->argv[2]->ptr);
        o->ptr = s;
    }
}

六、SDS vs C字符串对比

特性	C字符串	SDS
获取长度	O(n)	O(1)
安全性	不安全（可能溢出）	安全（自动扩容）
内存分配	每次修改可能分配	预分配减少次数
二进制安全	否（遇到\0结束）	是（按len读取）
内存使用	仅数据+\0	头部+数据+\0
适用函数	C字符串函数	部分兼容

七、实践建议

#

7.1 控制String大小

# 查看String大小
DEBUG OBJECT mykey
# 输出：value at:0x7f... refcount:1 encoding:embstr serializedlength:12 lru:... lru_seconds_idle:...

# serializedlength 可以估算内存占用

#

7.2 利用INT编码

// 使用数字作为key或value，节省内存
redis.set("counter:10001", "0");   // 使用INT编码
redis.incr("counter:10001");        // 极快的原子操作

#

7.3 避免频繁APPEND

// 不好的做法：频繁追加
for (String item : items) {
    redis.append("log", item);  // 每次都可能导致重新分配
}

// 好的做法：批量处理
StringBuilder sb = new StringBuilder();
for (String item : items) {
    sb.append(item);
}
redis.set("log", sb.toString());

八、总结

SDS是Redis最核心的数据结构之一：

设计特点	解决的问题
len字段	O(1)获取长度
alloc字段	防止缓冲区溢出
空间预分配	减少内存分配次数
惰性释放	优化缩短操作性能
二进制安全	支持任意二进制数据
多种头部	节省小字符串内存

理解SDS的设计思想：

1. 用空间换时间（len字段）
2. 预分配减少系统调用
3. 惰性策略减少不必要的操作
4. 针对不同场景优化编码

这些设计思想不仅适用于Redis，也是高性能系统设计的通用原则。

核心要点

1. String：简单的键值对，适合缓存、计数器

2. Hash：存储对象属性，适合用户信息、配置

3. List：有序列表，适合消息队列、最新列表

4. Set：无序去重，适合共同好友、抽奖

5. ZSet：有序集合，适合排行榜、积分系统

总结

选择合适的数据结构是使用 Redis 的关键。在实际项目中，根据业务需求选择合适的类型，可以提升性能和开发效率。