发布于 由admin

Redis SDS (Simple Dynamic Strings) 深度解析：字符串的动态伸缩与优化

各位观众，晚上好！今天咱们来聊聊Redis SDS，也就是Simple Dynamic Strings，简单动态字符串。别看名字挺朴实，这玩意儿在Redis里可是个顶梁柱，支撑着Redis高效的字符串处理。

一、字符串，永恒的话题

在编程的世界里，字符串是基本的数据类型之一，可以说无处不在。C语言作为老牌选手，对字符串的处理方式，大家都懂的，就是char数组，结尾再加个。

  • C字符串的痛点：

    • 获取长度： 每次都要strlen一下，O(n)复杂度，性能啊！
    • 缓冲区溢出： 稍微不注意，就越界了，安全隐患大大滴。
    • 修改麻烦： 字符串内容修改起来，一不小心就得重新分配内存，效率低下。

简单来说，C字符串就像一个定长的水杯，你倒少了没事，倒多了就溢出来了。

二、SDS：Redis的救星

为了解决C字符串的这些痛点，Redis设计了自己的字符串实现，也就是SDS。SDS就像一个带刻度的水杯，告诉你现在有多少水，还能根据你的需求自动调整大小。

  • SDS的结构体：
struct sdshdr {
    // 记录buf数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];
};
  • 结构体图示：
+-------+-------+---------------------+
|  len  |  free |       buf[]         |
+-------+-------+---------------------+
|       |       | "Redis"           |
+-------+-------+---------------------+

  • SDS的优势：

    • O(1)复杂度获取长度： 直接访问len属性，瞬间搞定。
    • 杜绝缓冲区溢出： 修改字符串前，SDS会先检查空间是否足够，不够就自动扩展。
    • 减少内存重分配： 预分配策略，避免频繁的内存操作。
    • 二进制安全： 可以存储任意二进制数据，不仅仅是文本字符串。
    • 兼容C字符串： 可以直接使用C标准库的字符串函数。

三、SDS的实现细节

接下来，咱们深入了解一下SDS的一些关键实现。

  1. 空间预分配：

    这是SDS性能优化的关键。SDS在扩展空间时，不仅仅扩展到所需的长度，还会预留一部分空间。

    • 如果修改后len小于1MB： 那么free会和len一样大，比如len变成了100字节，那么还会分配100字节的free空间，buf的总长度变成200字节。
    • 如果修改后len大于等于1MB： 那么free会分配1MB，比如len变成了2MB，那么free为1MB，buf的总长度变成3MB。

    这种策略可以减少后续字符串增长时的内存分配次数。

  2. 惰性空间释放：

    缩短字符串时，SDS并不会立即释放多余的空间，而是将这些空间留作以后使用。这可以避免频繁的内存释放和分配。 当然，如果需要，也可以手动释放多余的空间。

  3. 二进制安全：

    SDS使用len属性记录字符串的实际长度，而不是像C字符串那样依赖。这意味着SDS可以存储包含的任意二进制数据。

  4. SDS的创建与销毁：

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

// 销毁SDS
void sdsfree(sds s);
    • sdsnewlen：根据给定的初始内容和长度创建SDS。
    • sdsnew：根据C字符串创建SDS。
    • sdsempty：创建一个空的SDS。
    • sdsfree：释放SDS占用的内存。

  5. SDS的扩展与收缩：

    // 扩展SDS的空间
sds sdsMakeRoomFor(sds s, size_t addlen);

// 移除SDS未使用空间
sds sdsRemoveFreeSpace(sds s);

//将sds长度设置为给定长度
sds sdsAllocSize(sds s);

// 增加SDS长度
sds sdscatlen(sds s, const void *t, size_t len);

// 复制字符串到SDS
sds sdscpylen(sds s, const char *t, size_t len);
    • sdsMakeRoomFor：确保SDS有足够的空间容纳新的内容。
    • sdsRemoveFreeSpace：释放SDS中未使用的空间。
    • sdscatlen：将指定长度的字符串追加到SDS末尾。
    • sdscpylen：将指定长度的字符串复制到SDS。

四、SDS的类型变迁

为了进一步节省内存，SDS针对不同长度的字符串，使用了不同的结构体定义。

  • SDS的结构体家族：
typedef char *sds; /* 代表一个SDS字符串 */

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used len, excluding the header and null term */
    uint8_t alloc; /* excluding the header and null term */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used len, excluding the header and null term */
    uint16_t alloc; /* excluding the header and null term */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used len, excluding the header and null term */
    uint32_t alloc; /* excluding the header and null term */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used len, excluding the header and null term */
    uint64_t alloc; /* excluding the header and null term */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

  • SDS的类型：

    • sdshdr5：适用于长度小于32字节的字符串。（Redis 5.0及之前版本未使用）
    • sdshdr8：适用于长度小于256字节的字符串。
    • sdshdr16：适用于长度小于65536字节的字符串。
    • sdshdr32：适用于长度小于4294967296字节的字符串。
    • sdshdr64：适用于长度小于18446744073709551616字节的字符串。

  • 类型变迁的意义：

    选择合适的结构体，可以有效地节省内存空间。例如，如果字符串长度只有几十个字节，使用sdshdr8就足够了，没必要用sdshdr64浪费空间。 SDS在进行字符串操作时，会根据字符串的长度，自动进行类型变迁。 比如，如果一个sdshdr8类型的字符串，长度超过了255字节，那么就会自动升级为sdshdr16类型。

五、SDS的实际应用

SDS在Redis中被广泛应用，几乎所有需要存储字符串的地方，都使用了SDS。

  • 应用场景：

    • 键名： Redis的键名就是SDS。
    • 键值： 如果键的值是字符串，那么这个字符串也是SDS。
    • AOF缓冲区： AOF持久化时，记录的命令也是SDS。
    • 客户端输入缓冲区： 客户端发送的命令，也会存储在SDS中。

六、SDS的优缺点

任何技术都有两面性，SDS也不例外。

  • 优点：

    • 高效性： O(1)复杂度获取长度，避免缓冲区溢出，减少内存重分配。
    • 安全性： 二进制安全，可以存储任意数据。
    • 灵活性： 可以自动扩展和收缩空间，适应不同的字符串长度。
    • 内存优化： 根据字符串长度选择不同的结构体，节省内存空间。

  • 缺点：

    • 空间浪费： 预分配空间可能会导致一定的空间浪费，尤其是在字符串长度变化不大的情况下。 不过，这种空间浪费通常是可以接受的，毕竟性能更重要。
    • 复杂性： 相对于C字符串，SDS的实现更加复杂，需要更多的代码维护。

七、SDS与C字符串的对比

为了更清晰地了解SDS的优势，咱们来对比一下SDS和C字符串。

特性 C字符串 SDS
获取长度 O(n) O(1)
缓冲区溢出 容易发生 不会发生
内存重分配 频繁发生 较少发生
二进制安全 不安全 安全
空间占用 固定长度 可变长度，可优化内存

八、SDS的源码分析 (简要)

因为篇幅有限，这里只简单展示几个关键函数的源码片段，让大家感受一下SDS的实现细节。

  1. sdsnewlen：创建SDS
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);

    /* Empty string is zero terminated. */
    if (init == SDS_NOINIT) init = NULL;
    size_t hdrlen = sdsHdrSize(type);
    if (initlen + hdrlen + 1 < SDS_MAX_PREALLOC)
        sh = zmalloc(hdrlen + initlen + 1);
    else
        sh = zmalloc(hdrlen + initlen + 1);
    if (sh == NULL) return NULL;
    if (type == SDS_TYPE_5) {
        *sh = type | (initlen << SDS_TYPE_BITS);
        s = (char*)sh + 1;
    } else if (type == SDS_TYPE_8) {
        SDS_HDR_VAR(8,sh);
        sh->len = initlen;
        sh->alloc = initlen;
        sh->flags = type;
        s = (char*)sh + hdrlen;
    } else if (type == SDS_TYPE_16) {
        SDS_HDR_VAR(16,sh);
        sh->len = initlen;
        sh->alloc = initlen;
        sh->flags = type;
        s = (char*)sh + hdrlen;
    } else if (type == SDS_TYPE_32) {
        SDS_HDR_VAR(32,sh);
        sh->len = initlen;
        sh->alloc = initlen;
        sh->flags = type;
        s = (char*)sh + hdrlen;
    } else {
        SDS_HDR_VAR(64,sh);
        sh->len = initlen;
        sh->alloc = initlen;
        sh->flags = type;
        s = (char*)sh + hdrlen;
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '';
    return s;
}

这段代码的关键在于：

  • 根据字符串长度选择合适的SDS类型。
  • 分配内存，并初始化len、free等属性。
  • 将初始内容复制到buf中，并以结尾。
  1. sdsMakeRoomFor：扩展SDS的空间
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    size_t hdrlen;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (void*)(s - sdsHdrSize(oldtype));
    newlen = len + addlen;
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /* Don't use realloc if allocation size is smaller than the original one. */
    if (type == oldtype) {
        newsh = zrealloc(sh, sdsHdrSize(oldtype) + newlen + 1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh + sdsHdrSize(oldtype);
    } else {
        /* Type needs upgrade. */
        newsh = zmalloc(sdsHdrSize(type) + newlen + 1);
        if (newsh == NULL) return NULL;
        sdsHdrSize(type);
        SDS_HDR_VAR(8,newsh);
        sh->len = len;
        sh->alloc = newlen;
        sh->flags = type;
        memcpy((char*)newsh + sdsHdrSize(type), s, len+1);
        zfree(sh);
        s = (char*)newsh + sdsHdrSize(type);
    }
    s[-1] = type;
    SDS_HDR_VAR(8,s - sdsHdrSize(type));
    sh->alloc = newlen;
    return s;
}

这段代码的关键在于：

  • 检查剩余空间是否足够。
  • 计算新的长度，并根据预分配策略进行扩展。
  • 如果需要，进行类型升级。
  • 重新分配内存，并更新len、free等属性。

九、Redis 7.0 的 SDS 改进

在 Redis 7.0 中，SDS 进行了进一步的改进，主要是引入了 SDS_FLAG_SHARE 标志，用于共享字符串。 这使得多个 Redis 对象可以共享同一个 SDS 字符串，从而节省内存。 这种优化主要用于存储相同字符串的场景，例如配置项、常量等。

十、总结

SDS作为Redis的核心数据结构之一，其设计和实现都非常精妙。它不仅解决了C字符串的痛点，还通过预分配、惰性释放、类型变迁等优化手段，实现了高效的字符串处理。 理解SDS的原理，可以帮助我们更好地理解Redis的底层机制，从而更好地使用和优化Redis。 希望今天的分享对大家有所帮助！ 谢谢大家！

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注