一.Redis中那些你不知道的秘密-五大基本结构String的实现原理

学习使用，老鸟飞过，欢迎交流

前言

Redis已经成为解决高并发的必备利器，你可能已经把它玩的很熟了，但是对于它的底层，你又了解几分呢？

本篇文章我们来聊聊Redis中那些你不知道的秘密之Redis五大基本结构的实现原理。你也许知道Redis常用的存储结构有 String,List,Set,ZSet,Hash，但还远远不够，本文章将带你一步一步走进Redis更深处的奥秘。

简单动态字符串SDS

SDS(simple dynamic string, SDS)译为简单动态字符串，是Redis自己封装的字符串结构，如下：

struct sdshdr{
   
   
    //字符串长度，即buf已用字节的数量
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
}

SDS内存分配图

String是Redis最常用的一种存储结构了，我们都知道Redis是使用C语言开发的高性能Nosql数据库，那为什么Redis没有直接使用C的String结构，而是使用的是自己开发的String结构SDS呢？基于两个原因：①取字符串长度的时间复杂度 ②二进制安全问题

为什么要定义len

这里不得不说一下C语言的String，C语言的字符串和其他语言都差不多，底层使用char[] 实现，但是在C语言中要获取字符串的长度需要遍历整个char[] 来完成，时间复杂度是 O(N) ，性能不是最优不说，它还有一个二进制安全问题。

在 C 中使用 ‘\0’ 来标志一个字符串的结束，比如：['h','e','l','l','o','\0'], 如果有一个特殊数据正好内容中有一个空字符，那么在C中这个数据只能被识别到空字符前面部分的数据导致数据不完整，所以在C中String这种结构也是没法保存除文本数据以外的图片、音频等数据。

而Redis不一样，它的SDS结构定义了len来维护char[]的已有数据的长度，要取数据长度直接取len，复杂度为 O(1); 读取字符串不依赖终止符‘\0’,保证了二进制安全，同时可以存储图片，音频等内容。

为什么要定义free

在C语言中每次字符串增长都需要重新分配一次内存空间，这个是非常耗性能的工作，在Redis中字符串是最常用的存储类型，当然会被频繁的修改，如果每次都重新分配内存对性能的损耗极大。

那么在Redis的SDS中，存储数据的char buf[];的实际大小是 len + free + 1

• len表示字符串的长度，也表示buf中已经被使用的空间的大小。
• free表示buf中没有被使用的空间的大小。
• 其中多余的1个字节是用来存储’\0’的

即：char buf[]分配的内存空间是大于实际存储的字符串的长度的。那它为什么要多分配出 free 这一部分空间呢？①是预分配空间，防止每次修改都重新分配空间 ②防止缓冲区溢出

在C语言中，根据字符串处理特性，对于字符串的拼接、复制等操作，C语言开发者必须确保目标字符串的空间足够大，不然字符串增长时空间不够就会出现每次溢出的情况。

而在Redis中它是怎么处理的呢？每次在拼接字符串的时候，SDS的API内部会先对 free未使用的部分空间做判断看是否装得下最新的内容，如果装得下就不用开辟内存空间了，如果装不下再开辟内存空间，当然新开辟空间也不是开辟刚好放得下的空间大小，而是会额外申请len长度的空间作为 free，以便下一次使用，这是不是又是一次性能的提升呢？

SDS扩容图：

Redis的SDS如何释放内存

Redis采用的是惰性空间释放，如果Redis的String长度缩减它不会重新分配内存空间，而是通过较少len,增加free的方式来空大free的内存空间，这样的好处是减少内存重新分配，同时free可以用来进行下一次字符串拼接时使用这又是一次优化。当然也可以通过调用SDS提供的API直接释放内存，在需要的时候也能真正的释放掉多余的空间

Redis的极致优化

到此，Redis的SDS已经做了很好的优化了，但是为了把性能做到极致Redis还针对不同长度的String定制了不同的存储结构sdshdr5,sdshdr8,sdshdr32,sdshdr64。为什么这么做呢？例如：一个int占4个字节，在实际的应用中我们往往不会存储那么长的字符串，每个字符串都4个字节就太浪费空间了。

如果我们这样分配内存：短字符串len+free的长度为1个字节就够了，长字符串使用2个字节或者4个字节，更惨的字符串使用8个字节，这样会不会跟省内存？但是这样的话应该如何来区分这几种类型呢？在Redis 5.0版本中做了这样的改变：

sdshdr5{
   
   
    //flags一个字节8位，低3位存储类型，高5位存储长度
    unsigned char flags;
    //buf存放实际的内容
    char buf[];
}

Redis增加了flags占1字节(8bit)，低三位用来表示String的type(短字符串，长字符串...)，高5位存储长度len。

sdshdr5结构如下：

这样的话能够表示的长度区间为 0 到 31（2的5次方-1），那么如果字符串长度大于31呢？1个字节就存储不下了，按照之前的思路，把len和free单独存放，SDS几种存储结构如下：

/* sdshdr5和其他几种结构不一样 */
struct __attribute__ ((__packed__)) sdshdr5 {
   
   
    unsigned char flags; /* 低三位表示类型, 高五位表示字符串长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
   
   
    uint8_t len; /* 字符串已用长度，1个字节存储*/
    uint8_t alloc; /* 分配总长度，1个字节存储 */
    unsigned char flags; /* 低3位表示类型，高5位未使用作为预留空间 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
   
   
    uint16_t len; /* 字符串已用长度,2字节*/
    uint16_t alloc; /* 分配总长度,2字节 */
    unsigned char flags; /* 低3位表示类型，高5位未使用作为预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
   
   
    uint32_t len; /* 字符串已用长度,4字节*/
    uint32_t alloc; /* 分配总长度,4字节 */
    unsigned char flags; /* 低3位表示类型，高5位未使用作为预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
   
   
    uint64_t len; /* 字符串已用长度,8字节*/
    uint64_t alloc; /* 分配总长度，8字节 */
    unsigned char flags; /* 低3位表示类型，高5位未使用作为预留 */
    char buf[];
};

• len:表示buf已经占用的字节数
• alloc:表示buf分配的总数量，和len相减就是free的字节数
• flags:表示SDS类型，第3位表示类型，高5位预留
• buf:真正存储字符串数据的空间，是一个char[]数组。

可以看到，sdshdr5和其他几种不一太样。sdshdr5是把len放在flags中，而后面几种是把len和总长度alloc单独提出来，flags前3位表示类型，后5位作为预留。

这样一来那Redis该如何区分字符串长度来使用不同的存储类型呢？简单，做一个字符串长度判断即可，如下：

sds sdsnewlen(const void *init, size_t initlen) {
   
   
    void *sh;
    sds s;
    /* 计算出字符串长度，选择不同的SDS的类型 */
    char type = sdsReqType(initlen);
    /*SDS_TYPE_5  转换成SDS_TYPE_8 */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
   /* 计算不同的头部需要长度 */
    int hdrlen = sdsHdrSize(type);
    /* 指向flags */
    unsigned char *fp; 

    /* 分配内存，+1是用来存储\0，兼容C语言的 */
    sh = s_malloc(hdrlen+initlen+1);
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;

    s = (char*)sh+hdrlen;

    fp = ((unsigned char*)s)-1;

    /* 根据不同的类型，初始化sdsHeader */
    switch(type) {
   
   
        case SDS_TYPE_5: {
   
   
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
   
   
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
   
   
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
   
   
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        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);
    s[initlen] = '\0';
    return s;
}

好了文章就讲到这把，那么Redis对于String到底做了什么样的处理呢，这里总结一下：

• Redis定义了自己的String结构即：SDS
• 为了解决二进制安全问题SDS定义了len来表示已有字符串长度
• 为了防止缓冲区溢出SDS在分配内存的时候做了预留空间即：free部分
• 内存惰性释放，多余的内存加入free做预留，也是优化了内存频繁分配
• 针对不同的String长度定制了不同的SDS结构

如果面试官问你：Redis为什么那么快，你怎么答？

• Redis是单线程，没有锁的竞争，没有线程切换的性能开销
• Redis基于内存读写并发能力强
• Redis结构简单key-value存储
• Redis采用多路IO复用模型
• Redis对String做了极致优化SDS

是不是可以把Redis底层的优化加上？
Redis源码地址：https://github.com/antirez/sds/blob/master/sds.c

文章结束，希望对你有所帮助