阅读 1

redis源码:SDS是何方人物

redis源码:SDS是何方人物

Snipaste_2020-02-16_17-29-47.png

SDS介绍:

Redis中SDS称之为简单动态字符串

sds数据结构与API相关文件是:sds.h, sds.c

最大预分配长度:

#define SDS_MAX_PREALLOC (1024*1024)复制代码

定义:

struct sdshdr {
    
// buf 中已占用空间的长度
    int len;

// buf 中剩余可用空间的长度
    int free;

// 数据空间,用于保存字符串
    char buf[];
};复制代码

说明:

举个例子:“redis”;

我们发现了一点:len的长度为5,但是实际“redis”中包含尾字符串“\0”,长度应该是6,为什么长度是5呢?

  • 因为SDS没有把空字符‘\0’的1字符计算在SDS的len中,但是为空字符分配了1字节的空间,遵循了C字符串的规则;

内存分配:

SDS采取了空间预分配的方式;分配规则如下:

  • 对SDS进行修改时,它的长度小于等于空余长度,直接返回

  • 对SDS进行修改时,它的长度大于剩余空间并且小于1M(最大预分配长度为1M),(原字符长度+扩展字符长度)*2;(注:空字符所占1个字节一直存在)

  • 对SDS进行修改时,它的长度大于1M(最大预分配长度为1M),程序就会分配(原字符长度+扩展字符长度)+ SDS_MAX_PREALLOC(1M);比如扩展后的len长度是10M,则分配长度为10M+1M = 11M;

sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

// 获取s现在空余的长度
    size_t free = sdsavail(s);

    size_t len, newlen;

// 如果长度满足,则直接返回
    if (free >= addlen) return s;

// 获取s现在所占的长度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));

//新的需要的长度
    newlen = (len+addlen);
    
    if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC,则分配2倍所需要的空间 
        newlen *= 2;
else
// 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
//判断申请内存是否成功
    if (newsh == NULL) return NULL;
// 更新 sds 的空余长度
    newsh->free = newlen - len;
// 返回 sds
    return newsh->buf;
}
复制代码


SDS相对于C字符串的好处:

  • SDS可以直接获取长度,时间复杂度为(1);C字符串获取长度的时间复杂度为O(N)

  • 设置更新SDS长度由SDS接口自动完成,不需要手动设置

  • C字符串容易造成缓冲区溢出,比如strcat函数;而SDS会判断当前剩余的空间是否足够,不够则分配空间

  • C字符串每次修改需要重新分配空间,SDS一次会分配多余的空间,不用频繁的去申请空间(注:每次都会预留1个字节用于保存空字符

  • 惰性删除:比如SDS中存储的字符串是“redisxxxxx”,如果我们将字符‘x’去掉后,剩余的空间不会被删除,下次增加字符串时可以直接使用这块空间;

  • 二进制安全:C字符串中不能含有空字符,因为最先被程序读取的空字符会被认为是字符串的结束;SDS中可以包含空字符串,因为len会记录字符串的长度;


想了解学习更多C++后台服务器方面的知识,请关注:微信公众号:====CPP后台服务器开发====
扫码关注我们
一起学习更多知识

点亮在看,你最好看!




关注下面的标签,发现更多相似文章
评论