redis基础数据结构-sds简介

数据结构

1
2
3
4
5
6
7
8
9
/* context 	= "hello"
* len = 5 不包含redis自动添加的'\0'
* free = 0 预分配和惰性释放
* buf[5] = '\0' 自动添加一个'\0'在末尾,'\0'对外透明 */
struct sdshdr {
long len;
long free;
char buf[];
};

特点

  • 空间预分配和惰性释放
    • 避免频繁的系统调用造成的CPU耗时
    • 减少内存碎片
  • 二进制安全和兼容部分C的string函数
    • 尾部自动添加’\0’,以及len字段 实现了装载二进制数据的能力和兼容部分C的string函数
    • 明确的len和free避免了缓冲区的溢出
  • 降低获取len的复杂度
    • 相比C原始风格的字符串风格,sds可以直接读取len字段来获得len,从而将复杂度从0(n)优化为0(1)

重要接口实现

  • 构建指定长度的sds

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    sh = zmalloc(sizeof(struct sdshdr)+initlen+0+1); // initlen:len 0:free 1:'\0'
    if (sh == NULL) sdsOomAbort();
    sh->len = initlen;
    sh->free = 0;
    if (initlen) {
    if (init) memcpy(sh->buf, init, initlen);
    else memset(sh->buf,0,initlen); // 空指针则填充'\0'
    }
    sh->buf[initlen] = '\0'; // 添加哨兵'\0'
    return (char*)sh->buf; // NOTE: 这里返回的是buf
    }
    • 初始化时没有预分配MEM,因为一般而言sds是只读的,未修改则先不预分配空间
  • 修改sds的长度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    static sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s);
    size_t len, newlen;

    if (free >= addlen) return s;
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen)*2; // 直接预分配一倍
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) sdsOomAbort();
    newsh->free = newlen - len;
    return newsh->buf;
    }
    • 这里可以看到作者的思路,既然此sds被修改,那么很有可能再次修改,所以为了频繁系统调用,这里预分配一部分内存
-------------本文结束 感谢阅读-------------