Redis源码剖析--简单动态字符串sds

柔光的暖阳◎ 2022-06-08 00:21 218阅读 0赞

Redis 没有直接使用 C 语言传统的字符串表示， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。

Redis中所有的键都是用sds格式来保存的， 包括一部分值的保存，也是用的sds格式。

## SDS的定义 ##

sds.h中的定义如下：

/* * 类型别名，用于指向 sdshdr 的 buf 属性 */
    typedef char *sds;

sds包含两部分，在最基本的字符数组之外，加了两个字符数组信息，还有一个类似header的信息，header中包括了一下几个部分：

*  len：表示字符串真正的长度，不包含空终止字符
 *  alloc：表示字符串的最大容量，不包含Header和最后的空终止字符
 *  flags：表示header的类型

这样做的好处是能够马上知道字符串的长度和剩余空间，而无需遍历一遍字符数组计算长度。

同时，由于在c语言中一般都是通过字符数组最后的”\\0”来判断字符串的结束，而sds可以无视这些特殊字符的存在，可以直接根据len来获取完整的字符串。

此外，在修改字符串的时候，sds能够减少空间与分配的次数，提高运行效率，具体的可以稍后看代码中的实现。

## SDS基本操作 ##

### SDS初始化 ###

sds sdsnewlen(const void *init, size_t initlen) {
        void *sh;
        sds s;
        //根据长度判断创建header的类型
        char type = sdsReqType(initlen);
        /* Empty strings are usually created in order to append. Use type 8
         * since type 5 is not good at this. */
        if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
        //获取header的长度
        int hdrlen = sdsHdrSize(type);
        unsigned char *fp; /* flags pointer. */
    
        //分配空间，header长度+字符串长度+结束字符
        sh = s_malloc(hdrlen+initlen+1);
        if (!init)
            memset(sh, 0, hdrlen+initlen+1);
        if (sh == NULL) return NULL;
        //s是字符串真正保存的地址
        s = (char*)sh+hdrlen;
        //fp表示header中的flag
        fp = ((unsigned char*)s)-1;
        switch(type) { case SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS); break; }
            case SDS_TYPE_8: {
                SDS_HDR_VAR(8,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
            case SDS_TYPE_16: {
                SDS_HDR_VAR(16,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
            case SDS_TYPE_32: {
                SDS_HDR_VAR(32,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
            case SDS_TYPE_64: {
                SDS_HDR_VAR(64,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
        }
        if (initlen && init)
            //如果有初始内容，复制
            memcpy(s, init, initlen);
        s[initlen] = '\0';
        return s;
    }

根据初始化长度的不同，生成的header也不同

/* 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[];
    };

len表示已使用的长度， alloc表示分配的长度，包括header的长度和终止符，flag用来标记header的类型。

### SDS复制函数 ###

/* Duplicate an sds string. */
    //输入sds， 返回复制成功后的地址
    sds sdsdup(const sds s) {
        return sdsnewlen(s, sdslen(s));
    }

### SDS释放函数 ###

/* Free an sds string. No operation is performed if 's' is NULL. */
    void sdsfree(sds s) {
        if (s == NULL) return;
        s_free((char*)s-sdsHdrSize(s[-1]));
        //s[-1] 得到header中的flag， 然后通过sdsHdrSize获得header的大小， 相减得到header的地址
        //s_free释放
    }

### 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;
    
        // s 目前的空余空间已经足够，无须再进行扩展，直接返回
        /* Return ASAP if there is enough space left. */
        if (avail >= addlen) return s;
    
        len = sdslen(s);
        sh = (char*)s-sdsHdrSize(oldtype);
        // s 最少需要的长度
        newlen = (len+addlen);
        if (newlen < SDS_MAX_PREALLOC)
            // 如果新长度小于 SDS_MAX_PREALLOC 
            // 那么为它分配两倍于所需长度的空间
            newlen *= 2;
        else
            // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
            newlen += SDS_MAX_PREALLOC;
    
        // 得到新的type类型
        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. */
        if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    
        hdrlen = sdsHdrSize(type);
        if (oldtype==type) { 
            // 如果前后类型不变, 无需更改header，realloc
            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);
        }
        // 重新设置header中的alloc参数
        sdssetalloc(s, newlen);
        return s;
    }

*  当要增加字符在SDS之后的时候，先判断目前的剩余长度是否满足条件，如果慢煮条件，直接将字符串添加在后边
 *  如果当前的剩余空间不够，需要对SDS进行扩容。如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ， 那么程序分配和 len 属性同样大小的未使用空间， 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子， 如果进行修改之后， SDS 的 len 将变成 13 字节， 那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。
 *  如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。 比如， 如果进行修改之后， SDS 的 len 将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

## SDS小结 ##

SDS提供了一系列函数，不一一列出。 参考《redis设计与实现》一书的说明，SDS与C字符串的区别如下

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