Redis 简单动态字符串

Redis 没有直接使用C语言传统的字符串表示，而是自己构建了一种命名简单动态字符串的抽象类型。并将SDS作为Redis默认的字符串表示。

SDS实现

struct sdshdr
{
    int len;        // buf中已经占用的长度
    int free;       // buf中剩余可用空间的长度
    char buf[];     // buf
};

image.png

SDS 遵循C字符串结尾的惯例'\0'

---

typedef char *sds;

sdsnewlen 函数实现

sds sdsnewlen(const void *init, size_t initlen)
{
    if (init)
        sh = zmalloc(sizeof(struct sdshdr) + initlen + 1);   // zmalloc 不初始化所分配的内存
    else
        sh = zcalloc(sizeof(struct sdshdr) + initlen + 1);   // zcalloc 将分配的内存全部初始化为 0

    // 内存分配失败，返回
    if (sh == NULL)
        return NULL;
  
    sh->len = initlen;   // 设置初始化长度     
    sh->free = 0;  // 新 sds 不预留任何空间
    // 如果有指定初始化内容，将它们复制到   sdshdr 的 buf 中 T = O(N)
    if (initlen && init)
        memcpy(sh->buf, init, initlen);      
      sh->buf[initlen] = '\0';  // 以 \0 结尾
  
    // 返回 buf 部分，而不是整个 sdshdr
    return (char *)sh->buf;
}

sdsnewlen.png

sdsMakeRoomFor 函数实现

SDS相比于C字符串优势

• 二进制安全
  C语言字符串种字符串结尾必须时\0，这使得C字符串只能保存文本，而不能保存象图片，音频，视频压缩文件这样的二进制数据。

• 常数级复杂度获取字符串长度

• 杜绝缓冲区溢出
  C语言种相当一部分的API是不安全的，容易造成缓冲区溢出，而SDS不会。

• 减少修改字符串时带来的内存重分配次数
  C语言中strcat(s, "hello world")，在s的末尾增加字符串，那么必然引起内存的重新分配，因为内存重分配设计复杂的算法，并且可能需要执行系统调用。所以它通常是一个比较耗时的操作。

  为了避免C字符串的这种缺陷，SDS通过下面2种优化策略。

  • 内存预分配
    如果SDS需要修改内容并对空间进行扩展的时候，程序会对SDS分配额外的使用空间，
    • 假设对SDS进行修改后，其len < 1MB，那么程序将会分配额外的同len大小的空间。
    • 假设对SDS进行修改后，其len >= 1MB，那么程序将会分配额外的1MB大小的空间。
  • 惰性空间释放
    当SDS需要缩短SDS保存的字符串时，程序并不立即回收内存空间，而是使用free属性将这些字节的数量记录下来。

性能测试