Redis源码阅读(一) SDS简单动态字符串

本文主要是介绍Redis源码阅读(一) SDS简单动态字符串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

tag: #Redis #源码阅读 #数据结构

代码链接:
https://github.com/redis/redis/blob/unstable/src/sds.h
https://github.com/redis/redis/blob/unstable/src/sds.c

数据结构

sds的定义

sds定义是一个char* 类型指针的别名, 我们在传递sds的时候实质上就是传递的C风格字符串. 实际上sds的做法是把属性放到了字符串内存地址的前面, 后文会再提到.
typedef char *sds;

sds头结构(sdshdr)

实际上sds真正的控制结构在sdshdr(sds header)里. 一个典型的sdshdr长这样

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; // 已使用的空间长度
    uint8_t alloc; //分配的可用空间大小(不包括header和末尾0)
    unsigned char flags; //低3位储存类型, 高5位保留
    char buf[]; //实际C-Style String储存的位置, sds的值指向的就是这块地址
};

SDS根据储存内容长度的不同有5种定义, 储存的属性大同小异, 区别在于类型最后的数字说明了len和alloc占用的位数, 主要目的是优化SDS结构的空间占用. 储存不同长度的字符串会分配对应的sdshdr类型储存, 这块代码在sds.c的sdsReqType函数里.
各种长度字符串使用的sdshdr类型:

sdshdr5, length<32 (1<<5)时使用
sdshdr8, length<256 (1<<8)时使用
sdshdr16, length<65536 (1<<16)时使用
sdshdr32, length<4294967296 (1<<32)时使用
sdshdr64, length>4294967296 时使用

sdshdr5类型比较特别, 实际上头部只占用了一个8位组. flag的低3位储存了sds的类型, 高5位被利用起来储存了sds的长度. 并且不像其他类型一样还有一个alloc属性. 有效缩短了短字符串的空间占用. 但也因为sdshdr5没有alloc属性, 它注定是没有办法扩容的, 一旦需要append则必须升级到更高的类型.

header里一共有四个属性: len, alloc, flags 和 buf.
len 好理解, 实时维护当前sds的长度, 取字符串长度就可以优化到O(1)的时间完成, 简单的空间换时间思路.
**alloc **和redis的预分配策略有关, 熟悉C++ vector 或者 Java的ArrayList的同学可能比较容易联想到类似的策略. SDS在创建一个新的字符串时候不会只分配刚刚好的内存大小, 而是按一定的策略额外分配一部分空间, 便于后面append或者修改. 于是这里需要一个alloc的属性记录分配的可用空间大小.
**flags **是一个固定1个字节长的标记, 里面的低3位储存了当前这个sds的类型:

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

**buf **这是一个C风格字符串, 字符的内容就存在这里. 也是sds类型指向的内存位置. 当调用sdsnew()接口创建一个新的sds时, 返回的地址就指向这块内存. 这也就保证了sds和C语言库函数的兼容能力. 类似strlen(), strcmp()可以直接处理sds字符.
header部分结束, 留一个小问题: 既然sds储存的地址是指向buf的, 那么我们要怎么拿到sdshdr里的属性呢?

接口函数

函数	作用	算法复杂度
sdsnewlen	创建一个指定长度的 sds ，接受一个 C 字符串作为初始化值	O(N)O(N)
sdsempty	创建一个只包含空白字符串 "" 的 sds	O(1)O(1)
sdsnew	根据给定 C 字符串，创建一个相应的 sds	O(N)O(N)
sdsdup	复制给定 sds	O(N)O(N)
sdsfree	释放给定 sds	O(N)O(N)
sdsupdatelen	更新给定 sds 所对应 sdshdr 结构的 free 和 len	O(N)O(N)
sdsclear	清除给定 sds 的内容，将它初始化为 ""	O(1)O(1)
sdsMakeRoomFor	对 sds 所对应 sdshdr 结构的 buf 进行扩展	O(N)O(N)
sdsRemoveFreeSpace	在不改动 buf 的情况下，将 buf 内多余的空间释放出去	O(N)O(N)
sdsAllocSize	计算给定 sds 的 buf 所占用的内存总数	O(1)O(1)
sdsIncrLen	对 sds 的 buf 的右端进行扩展（expand）或修剪（trim）	O(1)O(1)
sdsgrowzero	将给定 sds 的 buf 扩展至指定长度，无内容的部分用 \0 来填充	O(N)O(N)
sdscatlen	按给定长度对 sds 进行扩展，并将一个 C 字符串追加到 sds 的末尾	O(N)O(N)
sdscat	将一个 C 字符串追加到 sds 末尾	O(N)O(N)
sdscatsds	将一个 sds 追加到另一个 sds 末尾	O(N)O(N)
sdscpylen	将一个 C 字符串的部分内容复制到另一个 sds 中，需要时对 sds 进行扩展	O(N)O(N)
sdscpy	将一个 C 字符串复制到 sds	O(N)

创建一个sds的完整过程

创建一个新SDS的函数是sdsnewlen(), 点开代码可以看到它只是调用了另一个底层函数_sdsnewlen()

sds sdsnewlen(const void *init, size_t initlen) {
    return _sdsnewlen(init, initlen, 0);
}

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh; // sdshdr的指针
    sds s; //sds的指针(sh->buf)
    char type = sdsReqType(initlen); //根据初始长度获取匹配的sds类型
    // 空sds创建出来的目的一般是为了往里面填充数据, 所以这种情况下升级到type8处理.
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); //sdshdr的大小(不包括sds占用)
    unsigned char *fp; //指向flags的指针(sh->flags)
    size_t usable; //剩余可用空间大小

    assert(initlen + hdrlen + 1 > initlen); //防止溢出
    sh = trymalloc? //为sdshdr分配空间
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1); //无初始值, 初始化内存为全0
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s); //这个宏里对sh做了一个类型转换, 注意两个sh的作用域
            sh->len = initlen; 
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen); //复制初始值
    s[initlen] = '\0'; //添加C-style string的末尾0
    return s; //将sds返回, 此时s在其他函数眼里就是一个常规的C字符串
}

在这里的31行第一次出现了SDS_HDR_VAR()这一个宏的使用, 这个宏的用法是把一个sds传进去, 它会替你创建好一个名为
sh的sdshdr指针, 我们就通过这个指针来访问sds的属性. 例如:

sds s = sdsnewlen("hello world", 33);
SDS_HDR_VAR(8,s); // 第一个参数是sds的规格类型, 这个例子里是sdshdr8, 第二个参数是sds本身
printf("the length of s is: %d", sh->len);

用法就类似这样, 而这个SDS_HDR_VAR()是怎么做到的? 其实他只是一个简单的宏替换, 我们看看它的定义:
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
这里的##正式的名字叫记号粘贴运算符, 对于不熟悉C/C++的小伙伴可以理解为##T出现的地方(包括##在内)在编译前会整个被传进来的T替换掉. 把我们刚刚调用的宏函数翻译一下:
struct sdshdr8 sh = (void)(s-sizeof(struct sdshdr8));
非常的简单粗暴, sh就是在s的指针上往前移动了一个header长度的距离.
这是一个相当危险的操作, 对于输入没有任何检查, 程序能正常运行完全依赖于程序员的正确调用. 如果调用者不小心传了一个原生字符串进去, 程序大概率也不会马上崩溃, 而是积累一堆脏数据并且继续参与后续的操作. 等到你发现不对劲的时候, 原始错误的现场早已经被破坏了. 并且这种问题也不容易被复现, 在debug的时候就会是一场噩梦.
所以这个操作总结一下就是: 很酷, 但是好孩子千万不要学.

sds的扩容机制

前面提到SDS会预留一定长度的空间以备append的需要, 如果这部分预留的空间被耗尽了, 这时候就要靠扩容机制发挥作用.
sds的扩容函数在sdsMakeRoomFor(), 实际上底层调用的是_sdsMakeRoomFor()函数. 当函数第三个参数greedy为1时, 会分配冗余的空间以备后用.

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    // 如果目前剩余空间足够, 则直接返回.
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) { //如果greedy参数为1
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2; // 新空间需求在1M以下, 则直接分配所需的2倍空间.
        else
            newlen += SDS_MAX_PREALLOC; // 新空间需求空间在1M以上, 则在满足需求后额外分配1M空间.
    }
    // 如果greedy参数为0的话, 则每次空间分配都只能分配到刚好够用的空间.

    type = sdsReqType(newlen);

    // sdshdr5没有属性记录总空间, 也就无法计算出剩余的可使用空间, 不能支持扩容. 因此扩容
    // 返回的sds至少也是type8.
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type); // 计算扩容后的sds头部大小
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        // 如果新旧sds是同样的类型, 那么尝试在原有地址上分配空间
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        // 如果新旧sds类型不同, 则sds头部大小也不同, 必须开辟新内存并且迁移数据
        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;
}

Ref

简单动态字符串 ‒ Redis 设计与实现
C语言宏的定义和宏的使用方法(#define)

这篇关于Redis源码阅读(一) SDS简单动态字符串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Redis教程

Redis源码阅读(一) SDS简单动态字符串

数据结构

sds的定义

sds头结构(sdshdr)

接口函数

创建一个sds的完整过程

sds的扩容机制

Ref

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯