Fork me on GitHub

条形与波浪

随心博客 blog

bars and waves

深入 redis 源码, 动态字符串 sds

redis 作为内存数据库, 必须高效使用内存. 最常用的数据结构, 字符串, 在 redis 中由 sds 封装并广泛使用.

sds 数据结构

一个典型的 sds 结构:

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

sds 的内部并没有黑魔法, 字段 len 记录使用的字节长度, alloc 记录分配长度, buf 保存着实际的数据. len 字段的存在使得 sds 可以记录二进制数据.

注意到:

__attribute__ ((__packed__))

告诉编译器不对 struct 内部进行内存对齐, 高效利用内存.

实际上 sds 的结构 除了 sdshdr8 以外还有 sdshdr5, sdshdr16, sdshdr32 等. 除了 sdshdr5 以外, 它们的内部结构与 sdshdr8 一样都是相同的.

sdshdr5 最为紧凑:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

sdshdr5 没有字段 len, 那么它的长度怎么记录? 其实它的长度记录在了字段 flags 内部的高位字节:

#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

一个 sds 到底具体使用了哪个结构, 是由长度需求决定的:

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

可以看到 sdshdrN 中的数字 N 实际上就是指我们期望的使用长度.

sds 的方法

在了解了 sds 的内部结构后, 剩下的就是操作 sds 的各种方法, 比如 sdscmp(), sdscpy() 等等. 这些方法有很多, 但其实都是在进行一些内存复制等操作, 没有特别需要注意的地方.