Redis数据结构源码解析(一) SDS

C语言存储字符串的问题

C语言中没有类似Java中的String高级对象

在Java中 String用的不亦乐乎，其自带的 equals、split、charAt等方法真的很方便，但是C是没有这种高级对象的。

如果在C语言中使用字符串有两种方式：

1. 使用字符串指针 const char *str = "hello";
2. 使用数组 const char str[] = "hello";

方法一最大的缺陷在于字符串定义后即不能修改，所以更多情况下还是使用数组。

二进制安全

C语言中表示字符串结尾的符号是 \0 ，如果字符串本身就具有 \0 字符，就会被截断，即非二进制安全。

计算字符串的长度性能低

C语言中有一个计算字符串长度的函数 strlen，但这个函数与Java的不一样，需要遍历整个字符串来计算长度，时间复杂度是O（n），如果需要在循环中计算，性能将十分低下。

字符串拼接性能低

因为C语言字符串不记录长度，对于一个长度n的字符串来说，底层是n+1的字符数组（n是我们要存的字符，1是最后的结束符 \0）。

底层虽然使用了n+1的字符数组，但是在使用 strlen方法的时候不会计算 \0

Simple Dynamic String 简单的动态字符串

在 redis3.2之前，sds只有一个类型，定义如下：

struct sdshdr {
    unsigned int len; // 当前的长度
    unsigned int free; // 剩余可用长度
    char buf[]; // 实际存放的地方
};

在后续版本中改为了

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; // sds的当前长度(单位是字节)
    uint8_t alloc; // sds分配的内存大小(单位是字节)
    unsigned char flags; // sdshdr的类型
    char buf[]; // 实际存放的地方
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; 
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
....

sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 一共五个方法，其中官方注解有些到 sdshdr5还没有被使用过。

类型机制

上面介绍了一共有五个 sdshdrX方法，看着都差不多只是 len和 alloc 类型不同，为什么要这么做呢？

其实也很简单就是省内存，而且真的是把能省就省发挥到了机制，在做业务开发的时候很少会为了这点内存再去做一套特殊的处理…

节省内存

我们已知的是 len和 alloc服务于字符串的长度，分别记录字符串长度和

• uint8: 字符串的长度最大(2^8)-1 = 255
• uint16: 字符串的长度最大(2^16)-1 = 35535
• uint32: 字符串的长度最大(2^32)-1 = 4294967295
• uint64: 字符串的长度最大(2^64)-1 = 1.8446744e+19

绝大多数情况下字符串的长度都不会超过35536，如果使用 uint64存储几十个几百就太浪费了。

最大长度问题

虽然类型限制了最大长度为(2^64)-1 ，但是真正限制的并不是它。

getBitOffsetFromArgument 是一个计算偏移量防止为负或者溢出的方法。在其方法内有这么一个判断：

/* Limit offset to server.proto_max_bulk_len (512MB in bytes by default) */
if ((loffset < 0) || (loffset >> 3) >= server.proto_max_bulk_len)
{
    addReplyError(c,err);
    return C_ERR;
}

根据源码注释可以看到，他是设置了512MB的一个长度限制，超出会返回异常。

在 config.c 文件中会对配置对象统一的定义。

createLongLongConfig("proto-max-bulk-len", NULL, MODIFIABLE_CONFIG, 1024*1024, LONG_MAX, server.proto_max_bulk_len, 512ll*1024*1024, MEMORY_CONFIG, NULL, NULL), /* Bulk request max size */

字符串的追加与扩容

redis> SET msg "hello world"
OK

redis> APPEND msg " again!"
(integer) 18

redis> GET msg
"hello world again!"

如上执行了一个简单的字符串追加工作。接下来以伪代码的形式介绍整个过程经历了什么。

SET 命令，创建一个SDS对象

struct sdshdr {
    len = 11;
    free = 0;
    buf = "hello world\0";
}

执行 APPEND 命令

此时相应的 sdshdr 被更新，字符串 " again!" 会被追加到原来的 "hello world" 之后：

struct sdshdr {
    len = 18;
    free = 18;
    buf = "hello world again!\0                  ";     // 空白的地方为预分配空间，共 18 + 18 + 1 个字节
}

不难发现，free从0->18，len从11->18，这次扩容整体从11->22（18-11+18）。

具体代码

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);      // 获取当前字符串的长度
    s = sdsMakeRoomFor(s,len);      // 扩容
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);       // 内存拷贝
    sdssetlen(s, curlen+len);       // 更新len属性
    s[curlen+len] = '\0';           // 末尾追加一个\0
    return s;
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;  //定义两个 sdshdr 结构体指针
    size_t avail = sdsavail(s); // 获取 s 目前空闲空间长度
    size_t len, newlen, reqlen; // len为扩展前长度,newlen为扩展后长度
    char type, oldtype = s[-1] & SDS_TYPE_MASK; // 用作sdsType的判断
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */ 
    if (avail >= addlen) return s; // 如果可用空间大于添加的长度，直接返回

    len = sdslen(s);// 获取 s 目前已占用空间的长度
    sh = (char*)s-sdsHdrSize(oldtype);  //结构体指针赋值
    reqlen = newlen = (len+addlen); // 复制扩展后长度,原长度+扩展的长度数
    assert(newlen > len);   /* Catch size_t overflow */
    // 开始设定扩展后长度
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于SDS_MAX_PREALLOC(1M),新长度直接翻倍
        // 这也就是上面为什么从11->22
        newlen *= 2;
    else
        // 否则每次新增一个SDS_MAX_PREALLOC单位也就是1M
        newlen += SDS_MAX_PREALLOC;

    // 此时有了新长度需要重新获取一下sds的类型,也就是sdshdr5,sdshdr8...
    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    // 作者示意不要使用sdshdr5,会变转换为sdshdr8
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    // 对比扩容前后类型是否改变，做对应的处理，不重要
    if (oldtype==type) {
        // 没有改变,在原空间分配
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        // 重新分配空间
        // 并删除原空间
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

编码格式

在Redis中为了进一步的节省内存还为SDS设置了三种编码格式：

• OBJ_ENCODING_EMBSTR：长度小于44字节的字符串，该编码中 RedisObject、SDS放置在连续的内存中。
• OBJ_ENCODING_RAW：长度大于44字节,除此之外与 OBJ_ENCODING_EMBSTR区别仅在于是否为连续内存
• OBJ_ENCODING_INT: 有时候我们会在String寸INT类型的自然数，例如一个手机号如果为字符串则需要11字节，如果使用long long 只需要8字节。

总结

• Redis 的字符串表示为 sds ，而不是 C 字符串（以 \0 结尾的 char*），相比较有如下特性
  • 在计算字符长度时更高效，直接读取 len熟悉为O(1)复杂度，传统C语言需要逐个遍历为O(n)
  • 提供更高效的扩容机制，牺牲一部分内存的情况下换取更快的追加速度
  • 二进制安全，不强制通过 \0作为结尾。也就是说在SDS中可以存储任何值

致谢

• Redis源码解析 - 有赞技术团队
• Redis 设计与实现
• Redis动态字符串SDS源码学习