源码解析Redis底层数据结构——简单动态字符串

Redis底层数据结构-简单动态字符串

源码

source/redis/src/sds.h sds.c

定义

简单动态字符串(SDS，simple dynamie String)，Redis底层是C编写的，但是Redis并没有直接使用C语言的字符串类型，而是自己创建了一套新的字符串类型，下面为SDS源码定义：

每个

sds.h/sdshdr

结构表示一个 SDS 值：

struct sdshdr { // redis 3.0
    int len;     // 记录 buf 数组中已使用字节的数量，等于 SDS 所保存字符串的长度
    int free;    // 记录 buf 数组中未使用字节的数量
    char buf[];  // 字节数组，用于保存字符串
};

// redis 4.0
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
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 */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
           

上面列举了redis 3.0 和 4.0中sds的定义，可以看出大牛们为了追求内存的极限，将sds细化成sdshdr8，sdshdr16，sdshdr32，sdshdr64

SDS与C字符串的区别

既然redis不直接沿用C语言的字符串，肯定有其用意，那么两者直接到底有什么区别？

1. 查询

C语言中采用n+1的方式存放字符串，1代表空字符 '\0’结尾。为了获取字符串的长度，需要遍历整个字符串，直到遇到 '\0’结尾符，时间复杂度为O(n)。如下图：

SDS获取长度，只需要访问len属性就能得出，时间复杂度为O(1)，设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的， 使用 SDS 无须进行任何手动修改长度的工作。

通过上面的比较得出：使用 SDS 而不是 C 字符串， Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ， 这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。

1. 修改字符串

   C 字符串不记录自身长度
   • 如果执行增长字符串的操作， 比如拼接操作（append）， 那么在执行这个操作之前， 程序需要先通过内存重分配来扩展底层数组的空间大小 —— 如果忘了这一步就会产生缓冲区溢出。
   • 如果执行缩短字符串的操作， 比如截断操作（trim）， 那么在执行这个操作之后， 程序需要通过内存重分配来释放字符串不再使用的那部分空间 —— 如果忘了这一步就会产生内存泄漏

​

SDS扩容空间预分配(函数sdsMakeRoomFor())

​ 对 SDS 进行空间扩展的时候， 会进行空间的预分配（先定义4个概念，avail：剩余的可用空间，len：SDS原字符串的总字节，addlen：新增字符串占有的总字节，newlen = len + addlen），预分配规则如下：

• 如果 avail > addlen，不扩容
• 如果 newlen < SDS_MAX_PREALLOC(1024*1024=1MB)， 扩容后的容量 = 2 * newlen
• 如果 newlen >= SDS_MAX_PREALLOC(1024*1024=1MB)， 扩容后的容量 = newlen + SDS_MAX_PREALLOC，也就是 扩容后的容量 = newlen + 1MB

SDS扩容源码
/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 获取 s 目前的空余空间长度
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    // s 目前的空余空间已经足够，无须再进行扩展，直接返回
    if (avail >= addlen) return s;

   // 在未超出SDS_MAX_PREALLOC前，扩容都是按2倍的方式扩容，超出后只能递增 
    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    // s 最少需要的长度
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    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. */
     /*  在真正使用过程中不会用到type5，如果遇到type5直接使用type8*/
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
         // 内存不足，分配失败，返回
        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(hdrlen+newlen+1);
         // 内存不足，分配失败，返回
        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);
    }
    sdssetalloc(s, newlen);
    return s;
}
           

SDS缩容惰性空间释放(sdsRemoveFreeSpace())

惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用

free

属性将这些字节的数量记录起来， 并等待将来使用。

/* Remove the part of the string from left and from right composed just of
 * contiguous characters found in 'cset', that is a null terminted C string.
 *
 * After the call, the modified sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call.
 *
 * Example:
 *
 * s = sdsnew("AA...AA.a.aa.aHelloWorld     :::");
 * s = sdstrim(s,"Aa. :");
 * printf("%s\n", s);
 *
 * Output will be just "Hello World".
 */
sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}
           

1. 二进制安全

   C字符串中’\0’代表结束符，查询的时候是根据’\0’来结束，如果存储二进制文件，一旦文件中含有’\0’，就会被当做结尾符，后面的内容就会被丢弃，造成数据不安全，而SDS也沿用了C字符串根据’\0’来结束的特性，但是查询是直接获取len属性，所以SDS 的 API 都是二进制安全的（binary-safe）。

总结

C 字符串	SDS
获取字符串长度的复杂度为 O(N) 。	获取字符串长度的复杂度为 O(1) 。
API 是不安全的，可能会造成缓冲区溢出。	API 是安全的，不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。	修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。	可以保存文本或者二进制数据。
可以使用所有 <string.h> 库中的函数。	可以使用一部分 <string.h> 库中的函数。

说明： 本博客介绍了sds扩容和缩容2个函数，其他的API建议读者自行去阅读