Redis原理再学习02：数据结构-动态字符串sds

Redis原理再学习：动态字符串sds

字符

字符就是英文里的一个一个英文字母，比如：a。中文里的单个汉字，比如：好。

字符串就是多个字母或多个汉字组成，比如字符串：redis，中文字符串：你好吗。

英文字符，如果按照 ASCII 码计算，一个字符占用 1 个字节。

中文字符的编码就比较复杂点，一个字符占用空间一般是 2 个字节，有的也用 3-4 个字节。

它有很多格式编码，有 gb2312，gbk， utf8 等等。

具体可以看看这篇文章：常见的中文字符编码。

动态字符串sds定义

看看 redis3.0 中的字符数据结构定义，sds.h/sdshdr

// https://github.com/redis/redis/blob/3.0/src/sds.h#L41
// redis3.0 低版本容易理解

// sds 兼容 C 语言风格字符串，并且还可以存到 sdshdr 结构的 buf 里 
typedef char *sds;

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

• len：记录 buf 数组中字符的长度

• free：记录 buf 中未使用的字节的数量

• buf：字节数组，保存字符串

不过到了 redis3.2 后，进一步优化了 SDS 的数据结构：

// https://github.com/redis/redis/blob/3.2/src/sds.h#L42
typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 { // 对应的字符串长度小于 1<<5
    unsigned char flags;/* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 对应的字符串长度小于 1<<8
    uint8_t len; // 已使用长度，1 字节/* 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 { // 对应的字符串长度小于 1<<16
    uint16_t len; // 已使用长度，2 字节
    uint16_t alloc; 
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 { // 对应的字符串长度小于 1<<32
    uint32_t len; // 已使用长度，4 字节
    uint32_t alloc; 
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 { // 对应的字符串长度小于 1<<64
    uint64_t len; // 已使用长度，8 字节
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};

针对不同长度的字符串，申请相应的数据存储类型，从而有效的节约了内存使用，进一步优化存储。进一步压榨 redis 的性能。

sdshdr为什么要这样设计

C 语言中的字符数组难道不够用吗？(redis3.0)

对于普通的字符串操作，C 语言中的字符数组是够用的。但是，redis 定位是高性能 kv 数据库，所以对于 redis 是不够用的。

从哪些方面优化才能扣出一点点性能呢？

1. 空间换时间：一次多分配一些空间，下次增加字符串时不需要在进行分配空间的操作了。这个叫预分配。

   ? 还有，截断字符串时，也不需要归还空间，而是用 free 属性记录，下次可以在复用空间，这个叫惰性空间释放。

2. 获取字符串长度复杂度 O(1)：sdshdr 里面定义了一个属性 len，操作字符串时会自动计算字符串的长度并赋值给这个 len 属性。所以在 redis 的一些命令中，不需要在计算一次字符串长度，而计算这个长度复杂度是 O(N)。比如 strlen 命令。

除了上面的 2 点，还有哪些好处？

1. 避免缓存区溢出：因为 SDS 的空间分配策略杜绝了发生缓冲区溢出的可能性。因为 SDS 的 API 会先检查空间是否满足修改所需的要求，不满足的话会自动扩展修改所需的空间大小。
2. 二进制安全：得益于 sds api 的设计，所有 sds api 都会以处理二进制的方式处理 sds 存放在 buf 数组里的数据，判断字符串是否到达结尾，不是以C语言里的 \0 来判断，而是用 sdshdr 结构里的 len 属性。这就避免了字符串中间遇到 \0 而发生错误判断。

SDS内存怎么分配

其实上面我们也有提到，一种是预分配，一种是惰性分配（惰性释放）。

1. 预分配

空间预分配用于优化sds字符串增长的操作：

• 如果对 sds 进行修改时，sds 的 len < 1MB，那么会分配和 len 长度相同的未使用空间，未使用空间长度记录到 free。
• 如果对 sds 进行修改时，sds 的 len > 1MB，那么分配 1MB 的未使用空间，记录到 free。

通过这种预分配策略，减少 Redis 执行字符串增长操作时，所需内存重新分配的次数，提高 redis 的效率。

空间预分配代码 sds.c/sdsMakeRoomFor:

// https://github.com/redis/redis/blob/3.0/src/sds.c#L129
/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s); // 获取未使用空间free值
    size_t len, newlen;

    if (free >= addlen) return s; // free 如果够用直接返回
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen); // 扩展后的新长度
    // #define SDS_MAX_PREALLOC (1024*1024)
    if (newlen < SDS_MAX_PREALLOC) // 新长度小于定义的最大预分配长度(1MB)，那么把新长度直接扩大2倍
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;// 新长度大于定义的最大预分配长度(1MB)，那么 newlen+1MB
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); // 获取新空间的地址
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len; // 更新未使用空间 free
    return newsh->buf;
}

// https://github.com/redis/redis/blob/3.0/src/sds.h#L52
// 获取 sds 未使用空间长度，free
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

// https://github.com/redis/redis/blob/3.0/src/sds.h#L47
// 获取 sds 中实际字符串长度，len
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

// https://github.com/redis/redis/blob/3.0/src/sds.h#L34
#define SDS_MAX_PREALLOC (1024*1024)

2.惰性分配（惰性释放）

惰性分配，就是惰性空间释放，用于对优化sds的字符串缩减操作。

• 如果 sds 保存的字符串缩减时，sds api 并不会直接回收内存，而是用 free 属性成员将不用内存字节大小记录下来，等待将来使用。

这样就优化了对内存的操作。

代码 sds.c/sdsclear:

/* Modify an sds string in-place to make it empty (zero length).
 * However all the existing buffer is not discarded but set as free space
 * so that next append operations will not require allocations up to the
 * number of bytes previously available. */
// https://github.com/redis/redis/blob/3.0/src/sds.c#L112
void sdsclear(sds s) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    sh->free += sh->len; // 新的free = 新的free + 使用空间len
    sh->len = 0; // 已使用空间置为 0
    sh->buf[0] = '\0'; // 字符串置为空
}

sdshdr存储字符串示例

比如 sdshdr 存储一个字符串 Redis，如下图：

? （《Redis设计与实现》）

存储 Redis 字符串时 sdshdr 各属性解释：

• free：值为 0，表示 sdshdr 中没有未使用的空间

• len：值为 5，表示 sdshdr 保存了一个 5 字节长度的字符串

• buf：char 类型的数组，数组前 5 个字节保存了 R, e, d, i, s 五个字符，结尾保存了空字符 '\0'。这个遵循了 c 语言中空字符串结尾惯例。保存这个空字符串的 1 字节长度不计算在 sdshdr 的 len 属性里。

参考

• 《redis设计与实现》 作者：黄健宏
• redis.io
• github redis