Redis笔记-结构篇-字符串

注意：本系列文章分析的 Redis 源码版本：https://github.com/Sidfate/redis ，是文章发布时间的最新版。

众所周知，redis 是用 c 语言写的。学过 c 语言的同学想必也对 c 语言中的字符串类型有所认识，c 语言没有专门定义字符串数据类型(如其他语言中的string)，它用以 '/0' 结尾的字符数组 char[] 来表示一个逻辑意义上的字符串。字符串字面值的类型就是const char类型的数组，所以是无法被更改的。这样的字符串我们称之为 “C 风格字符串”(C-style character string)，实际上就是以空字符 null 结尾的字符数组，例如：

    char greeting[] = "Hello";

它实际的储存形式：

SDS

Redis 中并没有直接用 c 的字符串格式，而是新建了一个结构 SDS（Simple Dynamic String），让我们先来看下它的定义：

    typedef char *sds;

char* 也可以表示字符串，只不过是变量是指针的形式。

我们可以看到 sds 其实就是char* ，那不就是我们说的 c风格字符串吗？并不是，sds和char * 并不等同，实际上往下看源码 sds 还包含一个 header 结构：

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

大家可以忽略 sdshdr5，官方解释中说明它还没被使用到。

上面的结构体定义出现了一个奇怪的东西： __attribute__ ((__packed__))，它是什么呢？__attribute ((packed)) 的作用就是告诉编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐。简单解释下就是系统出于一定的目的一般会要求结构体分配的内存是内部最大元素的整数倍，最大元素一般是 2^n ，但是加上 __attribute ((packed))  ，就表明结构体的大小就是定义的大小，不受系统内存对齐的约束（关于内存对齐的说明以后关注我之后的文章）。我们来看下实际这些 headers 的占用大小：

printf("%ld\n", sizeof(struct sdshdr8));  // 3
printf("%ld\n", sizeof(struct sdshdr16)); // 5
printf("%ld\n", sizeof(struct sdshdr32)); // 9
printf("%ld\n", sizeof(struct sdshdr64)); // 17

分别定义了这么几个结构类似但不同类型的 header 的意义是什么呢？是为了能让不同长度的字符串可以使用不同大小的 header，从而节省内存。可以看到 redis 在字符串结构上下了很多的功夫去节省内存，因为字符串结构使用的实在是太频繁，越是频繁被使用到的内容，越要去考虑内存的优化。

所以一个真正意义上的 sds 字符串，由在内存地址紧挨着的两部分组成：header + 字符数组。

由于 header 里面直接记录了字符串的长度 len，所以我们可以以 O(1) 的复杂度获取字符串长度。

另外 flags 的定义如下：

    // flags值的定义
    #define SDS_TYPE_5  0
    #define SDS_TYPE_8  1
    #define SDS_TYPE_16 2
    #define SDS_TYPE_32 3
    #define SDS_TYPE_64 4

还有一个 alloc 是字节数组总共分配的内存大小，例如一个字符串 “Sidfate”，它字节数组的 len 是 7，真实字符串长度加上 NULL 结束符的话长度是 8，但它实际可能占用了大小可能要大于 8，预留一些字节可以进行修改和拼接的操作，由此你可以知道 redis 的字符串是支持动态变更的。假设它实际占用了 16 个字节，那么 alloc 的值就是 15，因为要减去最后的一个 NULL 结束符，no pic say jb：

另外，redis 字符串对 c 语言字符串的兼容性也体现出来了，仍然保留了以 '\0' 结尾的风格，因为也能支持 c 语言中字符串的函数。

为什么 SDS 中头是和字符数组紧挨着的？

之前提到的节省内存是一点，更重要的事你要明白 redis 中的 sds 是 char* ，所有字符数组才是主体，紧挨着的好处就是可以通过字符串数组的地址 - 字节的方式直接获取到 header 里面的信息。这就相当于我知道了字符串的地址，header结构的地址也知道，header中各个字段的值也知道了。

用户角度的字符串

在我们使用过程中，一般就把 set 命令设置的值当做字符串，但实际上这个值根据值的不同在底层的储存形式也是不同的，大家可以试下下面的几个命令：

    127.0.0.1:6379> set test_str "test"
    OK
    127.0.0.1:6379> object encoding test_str
    "embstr"
    127.0.0.1:6379> set test_str "123"
    OK
    127.0.0.1:6379> object encoding test_str
    "int"
    127.0.0.1:6379> set test_str "12345678901234567890"
    OK
    127.0.0.1:6379> object encoding test_str
    "embstr"
    127.0.0.1:6379> set test_str "123456789012345678901234567890123456789012345"
    OK
    127.0.0.1:6379> object encoding test_str
    "raw"

总结下来就是：

• int 编码：保存long 型的64位有符号整数
• embstr 编码：保存长度小于44字节的字符串
• raw 编码：保存长度大于44字节的字符串

int值我们就不说了，储存 “123” 一般需要 3 个字节，但是储存数字 123 只要几个位就能表示了

，所以能转成数字的字符串都用 int 编码节约内存了。接下来说下 embstr 和 raw 的故事：

为什么分界线是 44 字节？

这个就要从一个结构说起了，

    struct RedisObject {
        int4 type; // 4bits
        int4 encoding; // 4bits
        int24 lru; // 24bits
        int32 refcount; // 4bytes
        void *ptr; // 8bytes，64-bit system
    } robj;

这是 redis 通用的对象结构，具体的说明之后还会有文章详细说，这里我先简单说明下它的大小计算下来是 16个字节，其中 ptr 指向的就是具体的 redis 对象。

如果指向的是一个 sds 结构，我们知道 sds 的头占用了 3 个字节，所以分配一个字符串的最小空间占用为 19 字节 (16+3)。

redis 使用 jemalloc 内存分配器，jemalloc会分配8，16，32，64等字节的内存。为了容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，稍微大点的字符串就会分配64字节，redis 认为超过 64 字节就是大字符串了。所以 64 - 19 = 45字节，再取出末尾的 null 结束符，所以字符串达到 44 字节是一个临界点。小于等于 44 字节的小字符串以 embstr 形式储存，为了节省内存，只调用一次内存分配函数来分配一块连续的空间，如下。

而一个大于 44 字节的大字符串则会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构，所以它的 ptr 指向的不连续的 一个 sds 头地址。

总结

本文的内容比较多也比较重要，可以看到 redis 为了常用的字符串做了相当多的优化操作，下面总结下 Redis 字符串 与 C风格字符串的区别（想不到吧）：

• redis 字符串是二进制安全的，即可以储存任意的二进制内容，也可以安全的使用一些拼接截取等函数；c 字符串不行，只能是以 '\0' 结尾的字符内容，使用中还容易造成缓冲区溢出。
• redis 字符串可以动态修改，c 字符串不能修改。
• redis 字符串可以兼容 c 字符串的函数，并且可以以 O(1) 的方式直接获取字符串长度，而 c 语言字符串需要用到遍历函数，复杂度 O(n)。
• redis 字符串可以有预留空间，保证在修改字符串，例如拼接截取的时候不需要重新分配内存，节省了内存分配的消耗。

最后讲一下 redis 字符串的扩容机制：

• 如果对 SDS 进行修改之后， SDS 的长度 len 将小于 1MB ， 那么程序分配和 len 同样大小的未使用空间（相当于扩大一倍），如果进行修改之后，len 将变成 13 字节， 那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存 null 结束符）。
• 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1MB ， 那么程序会分配 1MB 的未使用空间。 举个例子， 如果进行修改之后，len 将变成 30 MB ， 那么程序会分配 1MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。