redis源码学习之sds简单动态字符串

我就是我 2022-07-13 14:51 299阅读 0赞

参考用书，《Redis设计与实现》黄建宏著。

虽然没有实际在项目中用过redis，不过很多人推荐学习redis的代码。

Redis使用C语言编写，里面有很多跟C语言相似的内容，也兼容C语言的函数，代码量不大。

# 简单动态字符串 #

用来保存key-value，在redis底层key和value用SDS保存。  
SDS是一个结构体，它的定义如下：

/*
     * 保存字符串对象的结构
     */
    struct sdshdr {
    
        // buf 中已占用空间的长度
        int len;
    
        // buf 中剩余可用空间的长度
        int free;
    
        // 数据空间
        char buf[];
    };

实际上，redis中还进行了一次类型重定义：

typedef char * sds;

这样，用sds指向buf\[\]，事实上，有时候我们只关注buf里面的内容，而并不关注，已占用的空间和未使用的空间，不过，如果我们要获取这两个成员变量时怎么办？  
redis的做法也很巧妙，直接计算地址。

static inline size_t sdslen(const sds s) {
        struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
        return sh->len;
    }
    static inline size_t sdsavail(const sds s) {
        struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
        return sh->free;
    }

# SDS的特性 #

## 1.SDS的字符串都是null-terminated。 ##

也就是说，它的结尾都是`'\0'`，这一点肯C语言是一样的，因此C语言的很多汗是它是兼容的。比如，从SDS中的申请空间API中可以看到：

sds sdsnewlen(const void *init, size_t initlen) {
    
        struct sdshdr *sh;
        if (init) {
            // zmalloc 不初始化所分配的内存
            sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
        } else {
       //
            // zcalloc 将分配的内存全部初始化为 0
            sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
        }//分配空间时要考虑结构体的大小+数据长度+1的'\0'
    //...
    //...
        // 以 \0 结尾
        sh->buf[initlen] = '\0';
    
        // 返回 buf 部分，而不是整个 sdshdr
        return (char*)sh->buf;
    }

但是SDS是二进制安全的，也就是说’\\0’可以出现在字串中间。

## 2.惰性空间释放 ##

书中提到这种情况下并没有直接释放空间，结构体中的len成员设置为0，free设置为len，看了源码之后确实如此：

void sdsclear(sds s) {
    
        // 取出 sdshdr
        struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    
        // 重新计算属性
        sh->free += sh->len;
        sh->len = 0;
    
        // 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
        sh->buf[0] = '\0';
    }

## 3.空间分配策略 ##

这部分有点类似STL中的vector重新申请空间，比如说在一些函数调用例如sdscat，源空间不够追加时，需要扩容。redis设计了`sds sdsMakeRoomFor(sds s, size_t addlen)`，很形象。  
策略很简单：  
1.如果追加的内容小于sds中剩余的空间，即`addlen<free`，则直接返回无需扩容。  
2.如果追加后的内容长度newlen小于1MB，则再分配newlen大小的空间：`newlen*=2`  
3.如果追加后的长度大于1MB，则再分配1MB的空间。`newlen+=1024*1024`

关于这个1MB，在redis中有一个宏

#define SDS_MAX_PREALLOC 1024*1024
    //-------------------------------------------//
    sds sdsMakeRoomFor(sds s, size_t addlen) {
    
        struct sdshdr *sh, *newsh;
    
        // 获取 s 目前的空余空间长度
        size_t free = sdsavail(s);
    
        size_t len, newlen;
    
        // s 目前的空余空间已经足够，无须再进行扩展，直接返回
        if (free >= addlen) return s;
    
        // 获取 s 目前已占用空间的长度
        len = sdslen(s);
        sh = (void*) (s-(sizeof(struct sdshdr)));
    
        // s 最少需要的长度
        newlen = (len+addlen);
    
        // 根据新长度，为 s 分配新空间所需的大小
        //#define SDS_MAX_PREALLOC 1024*1024
        if (newlen < SDS_MAX_PREALLOC)
            // 如果新长度小于 SDS_MAX_PREALLOC 
            // 那么为它分配两倍于所需长度的空间
            newlen *= 2;
        else
            // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
            newlen += SDS_MAX_PREALLOC;
        // T = O(N)
        newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    
        // 内存不足，分配失败，返回
        if (newsh == NULL) return NULL;
    
        // 更新 sds 的空余长度
        newsh->free = newlen - len;
    
        // 返回 sds
        return newsh->buf;
    }

# 总结 #

SDS这部分代码比较简单，还需要考虑的问题就是：  
redis对malloc、free等这些空间管理函数进行了一层封装。