推荐学习

• Redis让我凉在美团一面，摸爬滚打3个月，二战逆袭成功斩获Offer
• 10.24程序员节，喜得一套「MySQL性能优化金字塔法则」

一、sds的结构

sds的定义

sds.h

//定义了一个char 指针
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 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
//lsb 代表有效位的意思，
//__attribute__ ((__packed__)) 代表structure 采用手动对齐的方式。
struct __attribute__ ((__packed__)) sdshdr8 {
    //buf 已经使用的长度
    uint8_t len; /* used */
    //buf 分配的长度，等于buf[]的总长度-1，因为buf有包括一个/0的结束符
    uint8_t alloc; /* excluding the header and null terminator */
    //只有3位有效位，因为类型的表示就是0到4，所有这个8位的flags 有5位没有被用到
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    //实际的字符串存在这里
    char buf[];
};
// 与上面的变化只有len和alloc， 就是长度不同而已
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[];
};
// 与上面的变化只有len和alloc， 就是长度不同而已
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[];
};
// 与上面的变化只有len和alloc， 就是长度不同而已
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[];
};

可以看到sds 这种结构在不同长度下，大体的结构是相同，唯一不同的 sdshdr5也没用到过。

sds的初始化

/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 * If SDS_NOINIT is used, the buffer is left uninitialized;
 *
 * The string is always null-termined (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * mystring = sdsnewlen("abc",3);
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
// 因为sds 在最前面指定了整个字符的长度，即使中间出现\0结束符，也能正常编译， 而不至于担心因为出现了结束符/0，而导致解码失败。
sds sdsnewlen(const void *init, size_t initlen) {
    // 这个指针会指向整个sds开始的地方
    void *sh;
    // sds 实际上也是一个指针，
    // 但是s指向整个struct buf开始的位置
    sds s;
    //根据不同的长度返回不同的类型的sds
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    // 空string 往往用于append ， 在这里可以看到sds type 5 类型会被怒sds type 8 替换掉
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    //获取struct的长度
    int hdrlen = sdsHdrSize(type);
    // flag 指针，这个指针就是用来表示sds 是哪个类型的
    unsigned char *fp; /* flags pointer. */
    //分配空间 这里+1 为的是分配一个结束符号
    sh = s_malloc(hdrlen+initlen+1);
    // sh在这里指向了这个刚刚分配的内存地址
    if (sh == NULL) return NULL;
    // 判断是否是init阶段
    if (init==SDS_NOINIT)
        init = NULL;
    // 如果不是init阶段则清0
    else if (!init)
        //init 不为空的话
        // 将sh这块内存全部设置为0
        memset(sh, 0, hdrlen+initlen+1);
    //s 指向了字符串开始的地址，hdrlen 可以看错sds head
    s = (char*)sh+hdrlen;
    //因为可以看到地址的顺序是 len,alloc,flag,buf,目前s是指向buf，
    //那么后退1位,fp 正好指向了flag对应的地址。
    fp = ((unsigned char*)s)-1;
    //下面就是根据
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            //这里使用了内连方法，让sh这个变量赋值了struct sdshdr
            SDS_HDR_VAR(8,s);
            //下面就是初始化长度，这里就没啥好说的了
            sh->len = initlen;
            sh->alloc = initlen;
            //fp 对应的地址赋值了对应的type，type 的取值是1-4
            *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;
        }
    }
    //如果两者都不为空，则init 这个对应的字符串，赋值给s
    if (initlen && init)
        //这里是给buf赋值初始化
        memcpy(s, init, initlen);
    // 分配一个结束符   
    s[initlen] = '\0';
    return s;
}

// 下面的方法，为上面的init 里面用到的工具方法
// 根据不同的string size 返回不同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;
//这里应该是考虑到32位系统的原因   
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}
// 根据不同的类型返回struct的长度
static inline int sdsHdrSize(char type) {
    //SDS_TYPE_MASK的作用是清除不必要的位数 SDS_TYPE_MASK 为00000111
    switch(type&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return sizeof(struct sdshdr5);
        case SDS_TYPE_8:
            return sizeof(struct sdshdr8);
        case SDS_TYPE_16:
            return sizeof(struct sdshdr16);
        case SDS_TYPE_32:
            return sizeof(struct sdshdr32);
        case SDS_TYPE_64:
            return sizeof(struct sdshdr64);
    }
    return 0;
}
#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
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
// 可以看到s本来是指向buf的位置，减去struct的长度正好就是开始的位置
// 然后sh就指向了整个sds开始的位置
// T就是占位符，返回不同类型的struct
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
//下面这个就是直接返回对应的struct
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
//这个类型的可以不关注因为没有被用到
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

sds 图解

sds 扩容

/* 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， 这里有一点，如果sds本身还有剩余空间，那么多分配的空间等于 addlen-leftlen
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //获取剩余可用的空间
    size_t avail = sdsavail(s);
    size_t len, newlen;
    //在上面图解里面s的指针是这段空间的中间 ,那么-1就正好指向了flag
    char type,oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    //如果可用空间大于需要增加的长度，那么直接返回
    if (avail >= addlen) return s;
    //len 已使用长度
    len = sdslen(s);
    //sh 回到指向了这个sds的起始位置。
    sh = (char*)s-sdsHdrSize(oldtype);
    // newlen 代表最小需要的长度
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        //但是实际会分配2倍的长度，如果空间小于最大阈值
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    //获取新长度的类型
    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        //sh是开始地址，在开始地址的基础上，分配更多的空间，
        // 逻辑如同初始化部分，hdrlen 是head的长度，即struct本身大小
        // 后面newlen 是buf 大小， +1 是为了结束符号
        // sds 通常情况下是可以直接打印的
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        //s继续指向中间位置
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        //如果类型发生变化，地址内容不可复用，所以找新的空间。
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        //复制原来的str到新的sds 上面,
        //newsh+hdrlen 等于sds buf 地址开始的位置
        //s 原buf的位置
        //len+1 把结束符号也复制进来
        memcpy((char*)newsh+hdrlen, s, len+1);
        //释放前面的内存空间
        s_free(sh);
        //调整s开始的位置，即地址空间指向新的buf开始的位置
        s = (char*)newsh+hdrlen;
        //-1 正好到了flag的位置
        s[-1] = type;
        //分配len的值
        sdssetlen(s, len);
    }
    //分配alloc的值
    sdssetalloc(s, newlen);
    //返回新的sds
    return s;
}
// 给len 设值
static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}
// 获取当前sds,可用的长度。
static inline size_t sdsavail(const sds s) {
    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;
}

/* sdsalloc() = sdsavail() + sdslen() */
// 获取alloc的长度
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}
// 给 alloc 设值
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

上面主要讲了sds是如何扩容的，可以看到sds的最大特点是可以预分配内存，在扩容方面也非常的高效。不用复制来复制去

为什么要使用内存不对齐（非常重要，全网讲sds唯一讲到这点就在这里）

在看下面之前首先要对内存对齐有个基本概念，为什么要内存对齐了，这里就涉及到cpu的工作原理相关了，可以百度cpu工作原理，主要是跟内存地址和寄存器的映射关系有关，但是有两条定理可以在这里了解。

1. 一个32位的cpu， 每一个周期从内存里面能读到32位的数据。
2. 基于这个原因和寄存器的原因，cpu的每次读的地址开始是4的倍数，打个比方我们要读地址2上面长度为4的数据，那么就需要两个周期， cpu首先得从0-3地址上面读数据，然后再从3-7的地址上面的数据， 在这里我们可以看到内存对齐的作用。
   那么问题来了，对于redis 作者一个对内存和cpu 用到极致的作者，为什么还要用非对齐的sds了，原因在于sds的本身结构注定只能非对齐状态。
   请看下图，在对齐状态我们的结构体在内存里面表现形势是如何的。

可以看到不同类型的sds 下面，pad 的位数也是不同的，那么我们要从sds 指针位置访问到flag，在不知道类型的情况下是不可能了，那么有同学又要发问了，去掉sdshdr8的结构不就行了吗，从理论来说这样牺牲的内存也不会太多，也保证了性能，但是这仅仅是在32位系统下面的结构，如果在64位系统，那可能又是另外一个结构了。 好的那么有同学又要说了 我们能不能把指针放到flag开始的位置。答案也是不能，1，这样我们就没办法完美兼容string， 2， 这样我们也会引入各种类型判断调整，所以redis 最后还是用到内存不对齐这个方案。

总结

1. 可以看到sds相较于普通c语言string 来说，是二进制安全的，因为string 没有长度标示当一段地址里面存在多个结束符号，string是没有办法访问到第一个/0后面的内容的，而正好sds的结构弥补了这一缺点。
2. sds 对于动态扩容也是string 无法比拟的，如sds的结构让sds可以预分配内存，甚至在原有长度类型不变的基础上，可以在原来内存使用基础上。实现动态扩容，上文代码也讲解得非常清晰。那么这样的好处又是啥了，如果一个string 非常长的情况下，如果要在原来的String基础上做append 操作，那么需要把内容复制到新的地址上面，而这件事情是一件非常耗费性能的一件事，而sds正好解决这件事，尤其在将网络io数据转化为具体命令操作的时候，要经常对字符串做append操作。所以sds结构非常适合redis。
3. 且sds也可以直接当做string来使用，巧妙的指针使用也是让sds完美兼容string。
   至于为什么要讲sds，因为在redis 最基础的数据除了字典就是sds，所以在我们讲redis如何从网络报文转化为具体执行的命令前，我们得先熟悉下sds这个结构。

作者： 偷懒的程序员-小彭

原文链接：https://blog.csdn.net/qq_33361976/article/details/109014012