2021-07-04 10:24  阅读(216)
文章分类:死磕 Redis 文章标签:死磕 Java死磕 Redis
© 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

字符串使我们在编程过程中使用最为广泛的对象了,在 Redis 中同样如此。我们知道 Redis 是 C 语言实现的,但是 Redis 放弃了 C 语言传统的字符串而是自己创建了一种名为简单动态字符串 SDS(Simple Dynamic String)的抽象类型,并将 SDS 用作 Redis 的默认字符串表示,其主要原因就是传统的字符串表示方式并不能满足 Redis 对字符串在安全性、效率、以及功能方面的要求。所以这篇文章就来说说 SDS。

在 Redis 里面,只会将 C 语言字符串当做字符串字面量,用于一些无须对字符串进行修改的地方,比如打印日志。在大多数场景下,Redis 都是使用 SDS 来作为字符串的表示。

对比 C 语言字符串,SDS 具有如下优点:

  1. 常数复杂度获取字符串长度。
  2. 杜绝缓冲区溢出。
  3. 减少修改字符串长度时所需的内存重分配次数。
  4. 二进制安全。
  5. 兼容部分 C 字符串函数。

SDS 的定义

SDS 的源码主要实现在 sds.csds.h 两个文件中。其定义为:

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

从上述代码可以看出,每一个 sdshdr 都是由以下几个部分组成(sdshdr5除外):

  • len:SDS 字符串已使用的空间
  • alloc:申请的空间,减去len就是未使用的空间,初始时和len一致。
  • flag:只使用了低三位表示类型,细化了SDS的分类,根据字符串的长度的不同选择不同的 SDS 结构体,而结构体的主要区别是 len 和 alloc 的类型,这样做可以节省一部分空间大小,毕竟在 Redis 字符串非常多,进一步的可以节省空间。
  • buf:char 类型数组,表示不定长字符串。

SDS 采用一段连续的内存空间来存储字符串,下图是字符串 “Redis” 在内存中的示例图:

SDS 与 C 字符串的区别

SDS相比C字符串,在安全性、性能、功能性具有优势:

  1. 安全性:防止缓冲区溢出、二进制安全
  2. 性能:获取字符串长度、空间预分配、惰性释放
  3. 功能性:二进制安全、兼容部分C字符串函数

缓冲区溢出

缓冲区溢出(buffer overflow):是这样的一种异常,当程序将数据写入缓冲区时,会超过缓冲区的边界,并覆盖相邻的内存位置。

C 字符串不记录自身长度,不会自动进行边界检查,所以会增加溢出的风险。如下面函数

char* strcat(char* dest, const char* src);

该函数是将 src 字符串内容拼接到 dest 字符串的末尾。假如有 s1 = “Redis”,s2 = "MongoDB",如下:

当执行 strcat(s1,'Cluster') 时,未给 s1 分配足够的内存空间,s1 的数据将会溢出到 s2 所在的内存空间,导致 s2 保存的内容被修改,如下:

与 C 字符串不同,SDS 杜绝了发生缓存溢出的可能性,他会按照如下步骤进行:

  1. 先检查 SDS 的空间是否满足修改所需的要求
  2. 如果不满足要求的话,API 会自动将 SDS 的空间扩展到执行修改所需的大小
  3. 最后才是执行实际的修改操作

例子可见:sds.c/sdscat

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

常数复杂度获取字符串长度

我们知道 C 字符串是不会记录自身的长度信息,因此我们要获取一个 C 字符串的长度,需要变脸整个字符串,直到遇到第一个 '\0',复杂度为 O(n)。但是 SDS 记录了自身长度 len,因此其复杂度降为 O(1) 就能获取字符串的长度。

空间预分配

当 SDS 的 API 要对一个 SDS 进行修改,并且需要对 SDS 进行空间扩展的时候,程序不仅会为 SDS 分配修改所必须要的空间,还会为 SDS 分配额外的未使用的空间,具体策略见 sds.c/sdsMakeRoomFor,如下:

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    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;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    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) {
        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);
    }
    sdssetalloc(s, newlen);
    return s;
}
  • 如果对 SDS 进行修改后,SDS 的长度小于 1MB,那么则扩大两倍,若 SDS 的长度大于等于 1MB,那么则会增加 1MB。

通过空间预分配策略,Redis 可以减少联系执行字符串增长操作所需的内存分配次数。

惰性释放

预分配空间用于优化 SDS 字符串增长操作,惰性释放则用于优化字符串缩短的操作:当 SDS 的 API 需要缩短 SDS 保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是回归到 alloc 属性中,并等待将来使用。

通过惰性释放策略,SDS 避免了缩短字符串时所需的内存重分配操作,并为将来可能有的增长操作提供了优化。

二进制安全

二进制安全(binary-safe):指能处理任意的二进制数据,包括非ASCII和null字节。

我们知道 C 字符串是以空字符(\0)结尾,所以除了字符串的末尾之外,字符串里面不能包含任何的空字符,否则最先被程序读入的空字符会被误认为是字符串的结尾。这些限制使得 C 字符串只能保存文本数据,不能保存图像、视频、音频等二进制数据。

而 SDS 不会对数据做任何限制、过滤、假设,数据在写入时是什么样子的,它被读取时就是什么样的。因此 Redis 不仅可以保存文本数据,还可以保存任意格式的二进制数据。

参考

点赞(0)
版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> 【死磕 Redis】----- Redis 数据结构:sds
上一篇
【死磕 Redis】----- Redis 数据结构:dict
下一篇
【死磕 Redis】----- Redis 数据结构:ziplist