关于redis:Redis源码剖析与实战-学习笔记-Day2-键值对中字符串的实现用char还是结构体

Redis 绝大部分操作都会波及到 key，应用特地宽泛，所以须要尽量满足以下三个要求：

1. 能反对丰盛且高效的字符串操作，比方字符串追加、拷贝、比拟、获取长度等；
2. 能保留二进制数据，比方 byte[]等；
3. 节俭内存开销。

从零碎设计的角度来看，咱们该如何设计实现字符串呢？

Redis 设计了简略动静字符串 (Simple Dynamic String) 的构造，用来示意字符串。相比于 C 语言中的字符串实现，SDS 这种字符串的实现形式，会晋升字符串的操作效率，并且能够用来保留二进制数据。

(1) 为什么 Redis 里的字符串不必 char*？

Redis 是用 c 语言编写的，为什么 Redis 的 key 不间接应用 char* ?

来看看 char* 字符数组的构造。
char 字符数组的构造比较简单，用一块间断的内存空间，顺次寄存了字符串中的每一个字符数组构造，结尾地位就用 ”\0″ 示意，示意完结。

不应用 char* 的起因

1. 操作效率低：获取字符串长度需遍历整个字符数组，O(N)复杂度
2. 二进制不平安：无奈存储蕴含 \0 的数据
3. 批改字符串遗记分配内存容易造成缓冲区溢出 (buffer overflow)。
4. 批改字符串须要从新分配内存，波及零碎调用。

SDS 劣势

1. 操作效率高：获取长度无需遍历，O(1)复杂度
2. 二进制平安：因独自记录长度字段，所以可存储蕴含 “\0” 的数据
3. 兼容 C 字符串函数，可间接应用字符串 API

另外 Redis 在操作 SDS 时，为了防止频繁操作字符串时，每次「申请、开释」内存的开销，还做了这些优化：

• 内存预调配：SDS 扩容，会多申请一些内存（小于 1MB 翻倍扩容，大于 1MB 按 1MB 扩容）
• 多余内存不开释：SDS 缩容，不开释多余的内存，下次应用可间接复用这些内存

(2) SDS 设计思维

SDS 构造里蕴含了一个字符数组 buf[]，用来保留理论数据。
同时，SDS 构造里还蕴含了三个元数据，别离是字符数组现有长度 len、调配给字符数组的空间长度 alloc，以及 SDS 类型 flags。

(2.1) SDS 定义

redis 6.0 版本源码 https://github.com/redis/redi…

Redis 里 SDS 定义，这里以 sdshdr64 为例

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; // 字符数组已应用长度   /* used */
    uint64_t alloc; // 字符数组的已调配空间，不包含构造体和完结字符   /* excluding the header and null terminator */
    unsigned char flags; /* SDS 类型 占用一字节 理论应用了 3bit，5bit 未应用 */ /* 3 lsb of type, 5 unused bits */
    char buf[];  /** 理论存储的数据 */};

类型 sds 是 char* 的别名（alias）
构造 sdshdr 则保留了 len、alloc flags和 buf[] 四个属性

uint64_t 定义是 typedef unsigned long long uint64_t; 所以 uint64_t 长度是 8 字节
unsigned long long conflict with uint64_t?

SDS 实质还是字符数组，只是在字符数组根底上减少了额定的元数据。
在 Redis 中须要用到字符数组时，就间接应用 sds 这个别名。

(2.2) SDS 函数列表

(2.2) 创立字符串

在创立新的字符串时，Redis 会调用 SDS 创立函数 sdsnewlen。

/* 
 * 应用“init”指针和“initlen”指定的内容创立一个新的 sds 字符串。* 
 * 该字符串始终以 null 结尾
 * 所以你能够这么创立一个 sds 字符串：*   mystring = sdsnewlen("abc",3);
 * 
 * 您能够应用 printf() 打印字符串，因为字符串开端有一个隐含的 \0。* 该字符串是二进制平安的，并且能够在两头蕴含 "\0" 字符，因为长度存储在 sds 头部中。*/
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s; // sds 类型变量 即 char* 字符数组
    // 获取 SDS_TYPE    SDS_TYPE_8 ~ SDS_TYPE_64
    char type = sdsReqType(initlen);
    // 元数据长度
    int hdrlen = sdsHdrSize(type);
    
    // 新建 SDS 构造，并分配内存空间 
    // hdrlen 是构造体的长度  initlen 是字符串长度  1 是最初结束符 "\0" 的长度
    sh = s_malloc(hdrlen+initlen+1);

    // sds 类型变量指向 SDS 构造体中的 buf 数组，sh 指向 SDS 构造体起始地位，hdrlen 是 SDS 构造体中元数据的长度
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;

    switch(type) {
        // 省略局部代码 ...
        // 
        case SDS_TYPE_64: {SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }

    if (initlen && init)
        memcpy(s, init, initlen); // 将要传入的字符串拷贝给 sds 变量 s
    s[initlen] = '\0'; // 字符数组 开端设置成 "\0"，示意字符串完结
    return s;
}

/**
 * 创立一个空的(长度为 0) sds 字符串。* 即便在这种状况下，字符串也始终具备隐含的空项。*/
sds sdsempty(void) {return sdsnewlen("",0);
}

(2.3) 删除

/**
 * 开释 sds 字符串。* 如果“s”为 NULL，则不执行任何操作。*/
void sdsfree(sds s) {if (s == NULL) return;
    // 只开释字符数组
    // 减去 header 的长度
    s_free((char*)s-sdsHdrSize(s[-1]));
}

(2.4) SDS 批改

SDS 构造中记录了字符数组已占用的空间和被调配的空间，这就比传统 C 语言实现的字符串能带来更高的操作效率。

以字符串追加操作为例。Redis 中实现字符串追加的函数是 sds.c 文件中的 sdscatlen 函数。这个函数的参数一共有三个，别离是指标字符串 s、源字符串 t 和要追加的长度 len，源码如下所示：

/* 
 * 将由“t”（共“len”个字节）指向的指定二进制平安字符串附加到指定的 sds 字符串“s”的开端。* 
 * 调用后，传递的 sds 字符串不再无效，所有援用必须替换为调用返回的新指针。*
 * @param s
 * @param *t
 * @param len
 */
sds sdscatlen(sds s, const void *t, size_t len) {
    // 获取指标字符串 s 的以后长度
    size_t curlen = sdslen(s);
    // 依据要追加的长度 len 和指标字符串 s 的现有长度，判断是否要减少新的空间
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    // 将源字符串 t 中 len 长度的数据拷贝到指标字符串结尾
    memcpy(s+curlen, t, len);
    // 设置指标字符串的最新长度：拷贝前长度 curlen 加上拷贝长度
    sdssetlen(s, curlen+len);
    // 拷贝后，在指标字符串结尾加上 \0
    s[curlen+len] = '\0';
    return s;
}

首先，依据以后字符串长度和要追加的长度，判断是否要给指标字符串新增空间。
其次，在保障了指标字符串的空间足够后，将源字符串中指定长度 len 的数据追加到指标字符串。
最初，设置指标字符串的最新长度。

SDS 把指标字符串的空间检查和扩容封装在了 sdsMakeRoomFor 函数中，并且在波及字符串空间变动的操作中，如追加、复制等，会间接调用该函数。

(2.5) 查问

/**
 * 已应用字符数据的长度
 */
static inline size_t sdslen(const sds s) {
    // SDS_TYPE  
    unsigned char flags = s[-1];
    // #define SDS_TYPE_MASK 7 也就是 SDS_TYPE_MASK 对应二进制是 0111  
    // flags 的左边 3 位 按位与  
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            // 返回对应的字符长度
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

flags & SDS_TYPE_MASK 进行与运算，SDS_TYPE_MASK 对应二进制是 0000 0000 0000 0111，无论 flags 是多少，最大是0111，也就是 7

#define SDS_TYPE_5  0  // 对应二进制 0000
#define SDS_TYPE_8  1  // 对应二进制 0001
#define SDS_TYPE_16 2  // 对应二进制 0010
#define SDS_TYPE_32 3  // 对应二进制 0011
#define SDS_TYPE_64 4  // 对应二进制 0100
#define SDS_TYPE_MASK 7

/**
 * 可用长度 = 已调配 - 已应用
 * avail = alloc - len 
 *
 * @param s 
 */
static inline size_t sdsavail(const sds s) {
    // SDS_TYPE
    unsigned char flags = s[-1];
    // 
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {return 0;}
        case SDS_TYPE_8: {SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

(2.6) 内存预调配

// file:  src/sds.c

/* 
 * 扩充 sds 字符串开端的可用空间，以便调用者确定调用此函数后能够笼罩字符串开端后的 addlen 个字节，再加上一个 nul 项的字节。*
 * 留神：这不会扭转 sdslen() 返回的 sds 字符串的长度，而只会扭转咱们领有的可用缓冲区空间。* 
 * @param s 
 * @param addlen 要增加的长度
 */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 可用长度
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen; // 构造体长度

    /* 如果残余空间足够，请尽快返回。*/
    if (avail >= addlen) return s;

    len = sdslen(s); // 字符串长度 / 已应用字符数组长度
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen); // 须要的字符长度 = 当初的字符串长度 + 须要减少的字符长度
    assert(newlen > len);   /* Catch size_t overflow */
    // 申请的字符串长度 newlen < 1KB 调配 newlen*2 的长度
    // 否则调配 newlen + 1KB 的长度
    if (newlen < SDS_MAX_PREALLOC) // 申请的新字符串长度 newlen < 1024*1024 (1KB) 
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC; 

    // 判断 SDS_TYPE
    type = sdsReqType(newlen);

    // 不要应用 SDS_TYPE_5：用户追加到字符串，SDS_TYPE_5 无奈记住空格，因而必须在每次追加操作时调用 sdsMakeRoomFor()。if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    // header 长度 / 构造体长度
    hdrlen = sdsHdrSize(type);
    // 确保 构造体长度 + 申请字符串长度 + 完结字符长度 > 申请的长度
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    // 判断 SDS_TYPE 有没有变动 
    if (oldtype==type) { // SDS_TYPE_8 == SDS_TYPE_8 
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else { // SDS_TYPE_8 != SDS_TYPE_16
        // 因为标头大小发生变化，须要将字符串向前挪动，并且无奈应用 realloc
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        // 将字符串拷贝给 sds 变量 s
        memcpy((char*)newsh+hdrlen, s, len+1);
        // 开释老的 sh 
        s_free(sh);
        // sds 类型变量指向 SDS 构造体中的 buf 数组，sh 指向 SDS 构造体起始地位，hdrlen 是 SDS 构造体中元数据的长度
        s = (char*)newsh+hdrlen;
        // 字符数组 设置 SDS_TYPE
        s[-1] = type;
        // 设置 sds 字符串长度
        sdssetlen(s, len);
    }
    // 设置已调配空间的长度
    sdssetalloc(s, newlen);
    return s;
}

备注

// file:  src/sds.c

#define SDS_MAX_PREALLOC (1024*1024)

(2.7) SDS 内存优化

(2.6.1) 紧凑型设计

SDS 构造中有一个元数据 flags，示意的是 SDS 类型。
事实上，SDS 一共设计了 5 种类型，别离是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
这 5 种类型的次要区别就在于，它们数据结构中的字符数组现有长度 len 和调配空间长度 alloc，这两个元数据的数据类型不同。

这里以 sdshdr64 为例

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; // 字符数组已应用长度   /* used */
    uint64_t alloc; // 字符数组的已调配空间，不包含构造体和完结字符   /* excluding the header and null terminator */
    unsigned char flags; /* SDS 类型 占用一字节 理论应用了 3bit，5bit 未应用 */ /* 3 lsb of type, 5 unused bits */
    char buf[];  /** 理论存储的数据 */};

现有长度 len 和已调配空间 alloc 的数据类型都是 uint64_t。uint64_t 是 64 位无符号整型，会占用 8 字节的内存空间。
当字符串类型是 sdshdr64 时，它能示意的字符数组长度（包含数组最初一位 \0）不会超过 2^64 字节（2 的 64 次方）。

元数据各自占用的内存空间在 sdshdr8、sdshdr16、sdshdr32、sdshdr64 类型中，则别离是 1 字节、2 字节、4 字节 和 8 字节。

SDS 之所以设计不同的构造头（即不同类型），是为了能灵便保留不同大小的字符串，从而无效节俭内存空间。** 因为在保留不同大小的字符串时，构造头占用的内存空间也不一样，这样一来，在保留小字符串时，构造头占用空间也比拟少。

(2.6.2) 编译优化

Redis 在编程上还应用了专门的编译优化来节俭内存空间。
struct __attribute__ ((__packed__)) sdshdr64，attribute ((packed))的作用就是通知编译器，在编译 sdshdr64 构造时，不要应用字节对齐的形式，而是采纳紧凑的形式分配内存。

这是因为在默认状况下，编译器会依照 8 字节对齐的形式，给变量分配内存。也就是说，即便一个变量的大小不到 8 个字节，编译器也会给它调配 8 个字节。
Redis 采纳了 __attribute__ ((packed)) 属性定义构造体，构造体理论占用多少内存空间，编译器就调配多少空间。

#include <stdio.h>
int main() {struct __attribute__((packed)) s2{
      char a;
      int b;
    } ts2;
    printf("%lu\n", sizeof(ts2));
    return 0;
}

当你运行这段代码时，你能够看到，打印的后果是 5，示意编译器用了紧凑型内存调配，s2 构造体只占用 5 个字节的空间。

(3) 应用 SDS 字符串的中央

1. server.h 文件中的 redisObject 对象，key 和 value 都是对象，key（键对象）都是 SDS 简略动静字符串对象
2. cluter.c 的 clusterGenNodesDescription 函数中。这个函数代表以 csv 格局记录以后节点已知所有节点的信息。
3. client.h 的 clusterLink 构造体中。clusterLink 蕴含了与其余节点进行通信所需的全副信息，用 SDS 来存储输入缓冲区和输出缓冲区。
4. server.h 的 client 构造体中。缓冲区 querybuf、pending_querybuf 用的 sds 数据结构。
5. networking.c 中的 catClientInfoString 函数。获取客户端的各项信息，将它们贮存到 sds 值 s 外面，并返回。
6. sentinel.c 中的 sentinelGetMasterByName 函数。依据名字查找主服务器，而参数名字会先转化为 SDS 后再去找主服务器。
7. server.h 中的构造体 redisServer，aof_buf 缓存区用的 是 sds。
8. slowlog.h 中的构造体 slowlogEntry，用来记录慢查问日志，其余 client 的名字和 ip 地址用的是 sds。

SDS 字符串在 Redis 外部模块实现中也被宽泛应用，你能在 Redis server 和客户端的实现中，找到应用 SDS 字符串的中央么？
1、Redis 中所有 key 的类型就是 SDS（详见 db.c 的 dbAdd 函数）
2、Redis Server 在读取 Client 发来的申请时，会先读到一个缓冲区中，这个缓冲区也是 SDS（详见 server.h 中 struct client 的 querybuf 字段）
3、写操作追加到 AOF 时，也会先写到 AOF 缓冲区，这个缓冲区也是 SDS（详见 server.h 中 struct client 的 aof_buf 字段）

参考资料

https://weikeqin.com/tags/redis/