SDS设计与源码分析

传统的C实现的字符串char*的不足之处？

• 1、以'\0'为字符串结尾，无法实现任意的字符串的保存，会被截断。
• 2、无法进行高效的操作，例如获取字符串长度、比较、追加等操作。
• 3、无法保存二进制类型。
• 4、操作复杂，追加，创建等操作涉及到内存的分配。

redis设计的SDS的优点？

• 1、高效的操作。redis以高效为名，高效的数据结构是保障。设计高效的字符串操作的数据接口。
• 2、保存任意字符串。C中的字符串实现以'/0'为结尾，无法保存任意的字符串。
• 3、保存二进制类型。
• 4、动态管理。C中的字符串操作需要自己管理内存的申请和释放，redis设计了自己的数据结构，在内部封装了对内存的操作，不需要自己维护。同时提供了动态扩容，惰性删除等操作。
• 5、节省内存。redis区分了4种不同大小的SDS类型，分别是SDSHDR8、SDSHDR16、SDSHDR32、SDSHDR64、其区别在于其结构体内的len和alloc，表示字符串的最大长度。通过attribute((packed))来告诉编译器通过紧凑的方式来分配内存（一般编译器都是按照8字节对齐的方式来分配内存）。

SDS源码分析

SDSHDR5不会被使用。

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;/*8s[-1]z直接获取到了SDS中的flags*/
    int hdrlen;
    size_t usable;

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

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (newlen < SDS_MAX_PREALLOC)/*小于1M，则申请需要内存的两倍*/
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;/*否则申请内存为所需内存➕1M*/

    type = sdsReqType(newlen);/*计算最新长度所需的SDS类型*/

    /* 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. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;/*不使用 type 5*/

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > len);  /* 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 {/*如果是新的类型，则涉及到字符串的拷贝，此时会存在短暂的旧内存消耗，所以SDS不应该保存较大内存的数据*/
        /* 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;
}

sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    size_t avail = sdsavail(s);
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if there is no space left. */
    if (avail == 0) return s;

    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    type = sdsReqType(len);
    hdrlen = sdsHdrSize(type);

    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
    if (oldtype==type || type > SDS_TYPE_8) {/*如果类型不变或者需要较大的内存时，只是调用了s_realloc()不做内存的真正释放*/
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else {/*否则将进行数据类型的替换，需要释放原先的类型的内存*/
        newsh = s_malloc(hdrlen+len+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, len);
    return s;
}

redis中SDS的使用

SDS作为redis非常基础的数据结构使用非常的广泛：

• 键。
• 客户端输入缓冲区。
• slowlog。
  ……