薛小嵩blog

Redis 简单动态字符串(SDS)详解

 
  • 2024年 12月15日
  • 0 阅读

Redis 中的字符串实现是一个被称为简单动态字符串(Simple Dynamic String, SDS)的抽象数据类型，它不仅是Redis字符串对象的底层实现，也是Redis内部几乎所有需要字符串表示的地方的基础数据结构。下面让我们深入了解SDS的设计与实现。

SDS(简单动态字符串)和前文讨论的Redis字符串对象是两个不同层次的概念，它们之间存在层次关系：SDS是Redis字符串对象的底层实现方式之一。

层次关系

  1. Redis对象层：字符串对象(StringObject)是Redis的高层抽象，是一种redisObject结构
  2. 编码实现层：StringObject可以使用三种不同的编码方式(INT、EMBSTR、RAW)
  3. 底层数据结构：当使用EMBSTR或RAW编码时，字符串内容由SDS结构存储
Redis字符串对象(StringObject)
│
├── INT编码 ─────┬─► 直接在指针字段存储整数值
│                │   redisObject { 
│                │     type: REDIS_STRING,
│                │     encoding: REDIS_ENCODING_INT,
│                │     ptr: (直接存放整数值)
│                │   }
│
├── EMBSTR编码 ───┬─► 使用SDS存储字符串，且redisObject和SDS连续分配
│                 │   [redisObject][sdshdr][数据...]
│                 │   {           }{      }{     }
│                 │   一次内存分配，连续内存布局
│
└── RAW编码 ──────┬─► 使用SDS存储字符串，但redisObject和SDS分开分配
                  │   redisObject ──指针──> sdshdr ──指针──> 数据
                  │   {         }           {    }         {   }
                  │   两次内存分配，分离的内存布局

SDS的数据结构

typedef char *sds;

struct sdshdr {
    int len;    // 字符串已使用长度
    int free;   // 剩余可用长度
    char buf[]; // 实际数据
};

SDS的设计非常简洁但精巧：

  • len字段记录字符串的实际长度
  • free字段记录未使用的预分配空间
  • buf是柔性数组，存储实际字符串内容

最有趣的是，sds类型本身只是C字符串(char*)的别名，它指向buf的起始位置，这使得SDS可以被传递给C字符串函数。

内存布局

SDS在内存中的实际布局如下：

       header             实际字符串内容
+------------------+-------------------------+
| len | free | buf | h  e  l  l  o  \0      |
+------------------+-------------------------+
^                  ^
|                  |
sh                 sds指针(s)

当我们有一个SDS指针s时，它实际上指向的是字符数组的起始位置，而不是结构体的起始位置。要访问结构体，需要通过指针运算：(void*)(s - sizeof(struct sdshdr))。

SDS相比C字符串的优势

1. O(1)时间复杂度获取字符串长度

size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s - sizeof(struct sdshdr));
    return sh->len;
}

与C字符串需要遍历计算长度不同，SDS可以通过读取len字段在O(1)时间内获取长度。

2. 防止缓冲区溢出

SDS在执行字符串操作前会检查空间是否足够：

sds sdscatlen(sds s, const void *t, size_t len) {
    // 确保有足够空间再进行操作
    s = sdsMakeRoomFor(s, len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

而C语言的strcat等函数则没有这种保护机制。

3. 减少内存重分配

空间预分配策略

当SDS需要扩容时，它不仅会分配”刚好够用”的空间，还会额外分配一些预留空间：

// sdsMakeRoomFor的核心逻辑
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;           // 小于1MB翻倍
else
    newlen += SDS_MAX_PREALLOC;  // 大于1MB加1MB

这大大减少了连续追加操作时的内存重分配次数。

惰性空间释放

当SDS缩短字符串时，不会立即释放多余的空间：

// sdstrim缩短字符串后
sh->free = sh->free+(sh->len-len);  // 释放的空间加入free
sh->len = len;                      // 更新实际长度

这些空间会被保留下来以备将来使用，避免了频繁的内存分配和释放。

4. 二进制安全

C字符串以\0字符作为结束标志，无法存储包含\0的二进制数据。而SDS使用len字段确定长度，可以存储任意二进制数据，包括图片、音频等包含\0字节的数据。

5. 兼容C字符串函数

尽管SDS提供了更多的功能和安全性，它仍然保持了与C字符串函数的兼容性。SDS字符串末尾总是有一个额外的\0字符，这使得SDS可以直接传递给printf等C函数。

SDS的生命周期

1. 创建

// 从C字符串创建
sds s = sdsnew("hello");

// 创建空字符串
sds s = sdsempty();

2. 修改

// 字符串拼接
s = sdscat(s, " world");

// 格式化追加
s = sdscatprintf(s, " %d", 2023);

// 字符串裁剪
sdstrim(s, " \t\n");  // 去除首尾空白字符

3. 释放

sdsfree(s);

空间优化策略示例

以下是一个展示SDS空间预分配和惰性释放特性的例子：

// 初始状态
sdshdr { len=0, free=0, buf="" }

// 追加"hello"后
sdshdr { len=5, free=5, buf="hello" }  // 预分配了相同大小的额外空间

// 再追加" world"后(6字符)
sdshdr { len=11, free=0, buf="hello world" }  // 额外空间用完了

// 再追加"!"后(需要扩容)
sdshdr { len=12, free=12, buf="hello world!" }  // 新空间是数据长度的2倍

// 如果截断回"hello"
sdshdr { len=5, free=19, buf="hello" }  // 注意free增加了，空间没有释放
搜索