Redis(版本4.0)日记20210801--简单动态字符串

无限递归 2021-08-10

366

今天这篇日记主要记录一下Redis中的字符串类型----简单动态字符串SDS，看了这个名字是不是还挺好奇的，好像这个简单动态字符串并不是那么简单。如日记内容有问题，欢迎留言指正，共同学习。

C语言字符串类型？

C语言中想要表示一个字符串，需要用字符串常量（指向字符串首字符地址的指针）或者字符数组来表示，并且会以 \0 作为结尾。求字符串长度，需要遍历字符串计数算出，即时间复杂度在O(n)，n为字符串 \0 之前所有字符的个数。

参考文章：https://www.cnblogs.com/tongye/p/10688941.html

例如：

// 一个指向字符串常量"Hello C!"第一个元素地址的指针
// 内容长度声明后固定，不可更改
// 实际字符串是"Hello C!\0"
// strlen(msg) == 8
char *msg = "Hello C!";


// 下面两种方式等价，name是一个字符字符数组
// 实际字符串是"huba\0"
// strlen(name) == 4
char name[] = {'h', 'u', 'b', 'a'};
char name[] = "huba";


// 如果字符串中间出现\0，那么就会认为到了字符串的结尾
// strlen(message) == 4
// 所以非二进制安全
char message[] = "huba\0bbbbb";

简单动态字符串结构？

看了C语言的字符串结构之后，那我们再来看一下Redis中的SDS是一个什么样的结构：

其实Redis中的SDS就是对C语言的字符数组进行了一定的封装，增加了len以及free属性。源码如下：https://github.com/antirez/sds

struct sdshdr {
    int len; // 当前buf中字符的个数
    int free; // buf剩余可用空间
    char buf[]; // 存储字符串的字符数组
};

+------------+------------------------+-----------+---------------\
| Len | Free | H E L L O W O R L D \n | Null term |  Free space   \
+------------+------------------------+-----------+---------------\
             |
             `-> Pointer returned to the user.

空间预分配策略？

当追加字符串后len的长度 < 1M ，那么将分配与len相等的空间出来，比如开始时len = 5Byte，然后追加了 5 个字符进去，现在len = 10Byte , 10Byte < 1M , 此时就会预分配10Byte，即 len = 10Byte，free = 10Byte

当追加字符串后len的长度 > 1M，那么将分配1M的空间出来，比如开始时len = 2M，然后追加了 10 个字符串进去，那么现在 len = 2M + 10Byte，free = 1M

源码分析：

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 当前SDS字符串可用字节数
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;


    /* Return ASAP if there is enough space left. */
    // 如果可用字节数 >= 要分配的字节数，直接返回
    if (avail >= addlen) return s;


    // 获取当前SDS字符串的占用字节数（len）
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    // 新占用字节数 = 当前占用字节数 + 要追加的字节数
    newlen = (len+addlen);
    // 如果新占用字节数 < 1024 * 1024字节
    // #define SDS_MAX_PREALLOC (1024*1024)
    // SDS_MAX_PREALLOC = 1024 * 1024 = 1MB
    // 则预分配字节数 = 新占用字节数 * 2
    // 否则预分配字节数 = 新占用字节数 + 1M
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;


    // ... 省略
    return s;
}

为什么用SDS而不是直接用C字符串？

SDS获取长度len和剩余可用空间free，时间复杂度为O(1)
不用担心忘记手动分配内存或者分配内存不足导致的内存溢出或内容覆盖问题。
SDS是二进制安全的（有len属性，不以\0作为字符串的结尾标志，而是通过len长度来判断字符串是否结束）
空间预分配以及惰性空间释放，减少内存分配次数
兼容部分C语言字符串的方法，可以直接使用（结构中也存在\0标志，所以可以兼容部分C语言字符串的方法）

redis

文章转载自无限递归，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

Redis(版本4.0)日记20210801--简单动态字符串

评论