redis 数据结构 （一）

注：以下源码部分，来自redis-7.0.12，redis-3.0

redis 有一个核心的对象，叫做 redisObject，用来标识所有的 key 和 value，用 结构体reidsObject来标识 String、Hash、List、Set、Zset 五种数据结构。源码位置在server.h。

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
// 使用整数值实现
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
// 使用字典实现
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */

#define OBJ_ENCODING_ZIPMAP 3  /* No longer used: old hash encoding. */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */

// 使用整数集合实现
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
// 使用跳跃表
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
// 使用EMBstr编码的简单动态字符串实现
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
// 
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */

#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */
#define LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */

#define OBJ_SHARED_REFCOUNT INT_MAX     /* Global object never destroyed. */
#define OBJ_STATIC_REFCOUNT (INT_MAX-1) /* Object allocated in the stack. */
#define OBJ_FIRST_SPECIAL_REFCOUNT OBJ_STATIC_REFCOUNT
struct redisObject {
  	// 数据类型
    unsigned type:4;
  	// 编码方式
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
  	// 数据指针
    void *ptr;
};

type 表示属于哪种数据类型，encoding 表示该数据的存储方式。也就是底层的实现的该数据类型的数据结构。

String 的数据结构

源码位置 sds.c、sds.h

int

redis 中，如果存储的是整数型值，比如set key 123，就会使用 int 的存储方式进行存储，在redisObject中的ptr属性中，就会保存该值。

SDS

SDS的相关源码描述在sds.c, sds.h中。

假如存储一个字符串值，且长度大于 32 字节，就会使用简单动态字符串（Simple Dynamic String，缩写 SDS）存储，并且设置 encoding 为 raw ；如果长度小于 32 字节，就会将 encoding 改为 embstr 来保存字符串。是可以修改的字符串，内部结构上类似于 Java 的 ArrayList，采用分配冗余空间的方式来减少内存的频繁分配。

上源码：

3.0

typedef char *sds;

struct sdshdr {
  	// 字符串长度
    unsigned int len;
  	// 空余空间
    unsigned int free;
  	// 字符数组
    char buf[];
};

len 保存了字符串的长度，free 表示 buff 数组中未使用的字节数量，buf 数组则是保存数组的每一个字符元素。

这样的结构解决了C语言本身的字符串带来的几个问题：

1. 字符串长度 len 的获取结果在 C 语言中时间复杂度为 O(n)
   • 在 C 语言中，字符串并不会记录自身的长度，因此在每次获取字符串的长度的时候都会通过遍历获得，时间复杂度为 O(n)。
   • 在 SDS 中，每次获取字符串长度，只需要获取 len 值。时间复杂度是O(1)。
2. 在 C 语言中，如果两个字符串拼接，可能会存在缓冲区溢出的情况
   • C 语言中，需要拼接字符串的操作中，如果没有分配足够长度的内存空间，就会出现缓冲区溢出的问题
   • SDS 中，会根据 len 属性判断空间是否满足需求，如果不够，会优先进行空间扩展。
3. 避免过多的内存空间重新分配的次数
   • 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 sdsMakeRoomFor(sds s, size_t addlen) {
    // 定义两个结构体
    struct sdshdr *sh, *newsh;
    // 获取 s 目前的空闲空间长度 
    size_t free = sdsavail(s);
    // 定义两个长度变量，一个用于存储扩展前的 sds 字符串，一个用于存储扩展后的 sds 字符串长度 
    size_t len, newlen;

  	// 如果空间足够，无需扩展，直接返回
    if (free >= addlen) return s;
  	// 获取 s 目前占用的长度
    len = sdslen(s);
  	// 结构体指针赋值
    sh = (void*) (s-(sizeof(struct sdshdr)));
  	// 需要的新的长度
    newlen = (len+addlen);
  	// 分配新的长度
    if (newlen < SDS_MAX_PREALLOC)
      	// 如果需要的最小新长度小于 SDS_MAX_PREALLOC ，则赋值为最小新长度的 2 倍空间
        newlen *= 2;
    else
      	// 否则新的长度空间为目前需要的最小空间，加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
  	// 操作内存
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
  	// 操作失败返回 null
    if (newsh == NULL) return NULL;
	  // 记录新的空余空间长度
    newsh->free = newlen - len;
    return newsh->buf;
}

以上函数就是动态扩容（空间预分配）策略，保证了字符串的高效追加。简而言之，当需要追加空间时，如果新的必须空间小于 1M，那么扩容为原空间（新的最小必需空间）的 2 倍，否则追加 1M 新空间。

其中，SDS_MAX_PREALLOC定义在sds,h中：

#define SDS_MAX_PREALLOC (1024*1024)

大小为 1 M，这就是空间内存分配策略中，1M 的来源。

惰性空间释放

/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    zfree(s-sizeof(struct sdshdr));
}

很简洁的释放方法。

/* Modify an sds string in-place to make it empty (zero length).
 * However all the existing buffer is not discarded but set as free space
 * so that next append operations will not require allocations up to the
 * number of bytes previously available. */
void sdsclear(sds s) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    sh->free += sh->len;
    sh->len = 0;
    sh->buf[0] = '\0';
}

为了性能，减少频繁申请内存的开销，SDS 提供了不直接释放内存，而是通过重置统计值达到清空目的的方法。在此仅将 SDS 的 len 归零，此处的 buf 并没有做清空操作，新的数据可以进行覆写，而不用重新申请内存。

这样的惰性空间释放策略，SDS 避免了缩短字符串时所需的内存重新分配操作，并为将来可能有的增长操作提供了优化。

追加操作

/* Append the specified null termianted C string to the sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscat(sds s, const char *t) {
    // 实际执行操作
    return sdscatlen(s, t, strlen(t));
}

/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
    // 定义结构体指针
    struct sdshdr *sh;
    // 获取当前 s 的长度
    size_t curlen = sdslen(s);

    // 执行容量检查，其中包含扩容操作
    s = sdsMakeRoomFor(s,len);
    // 为空返回
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    // 拼接字符串，复制 t 中的内容到字符串后
    memcpy(s+curlen, t, len);
    // 记录长度
    sh->len = curlen+len;
    // 记录空闲空间
    sh->free = sh->free-len;
    // 字符串结尾加上结束符
    s[curlen+len] = '\0';
    return s;
}

对于追加操作，上层暴露的方法为sdscat，其最终调用的方法是sdscarlen。其中涉及上文提过的容量检查。函数中，len 、curlen 等长度值是不含结束符的。而拼接时用的 memcpy 方法将两个字符串拼接在一起，指定了相关长度，故该过程保证了二进制安全，最后结束需要加上结束符。

补充：关于二进制安全问题，因为 C语言中是以遇到的第一个空字符\0来识别是否到了字符串末尾，因此其只能保存文本数据，不能保存图片、音频、视频和压缩文件等二进制数据，否则可能出现字符串不完整的问题，所以其是二进制不安全的。而 SDS 是以字符串长度识别是否结束的，避免了这个问题。

存在的问题

SDS 的设计是优秀的，它能够以 O(1) 的事件复杂度得到字符串的长度，并解决了二进制安全问题和缓存区移除问题，能够高效的对字符串进行追加操作，避免了频繁的扩容和缩容。

但是它仍然存在些许问题：

• 不同长度的字符串是否有必要占用相同大小的头？

一个 int 占 4 个字节，一个字节是 8 位，共可以表示 2147483648 个正数。而实际应用中，存放在 redis 中的字符串往往没有这么长，每个字符串都要用 4 字节未免太浪费了。

我们考虑三种情况：短字符串，len 和 free 的长度为 1 字节就够了；长字符串，用 2 字节或者 4 字节；更长的字符串，考虑用 8 字节。

这样仍然存在问题：

1. 怎么区分 短字符串、长字符串、更长的字符串
2. 对于短字符串来说，头部可能还是太长了。如果存在长度为 1 字节的字符串，len 和 free 本身就占了 2 字节。

对于问题 1 ，我们需要额外的字段 flags 来做类型的标识。用最小的 1 字节来存储，并且把 flags 加载柔性数组 buf 之前。这样虽然多了 1 字节，但是通过偏移柔性数组的指针即能快速定位 flags，区分类型，也可以接受。对于问题 2 ，由于 len 已经是最小的 1 字节了，再压缩只能考虑用位来存储长度了。

结合两个问题，5种类型（长度 1 字节、2 字节、4 字节、8 字节、小于 1 字节）的 SDS 至少需要 3 位来存储类型（2^8），1 个字节 8位，剩余的 5 位正好可以满足长度小于 32 的短字符串用来存储长度。

redis 3.2 以后的 SDS 结构就是这样操作的。

7.0

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 {
    // 低 3 位用来存储类型，高 5 位用来存储长度
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

对于 sdshdr5 来说，结构如下，flags 占 1 个字节，其低三位（bit）表示 type，共可表示 2^3 种状态，高 5 位（bit）表示长度。能表示的长度为 0～2^5-1。flags 后面就是字符串的内容。

而对于长度大于 31 的字符串，1 个字节这时候就不够了。

回到最开始的思路，将 len 和 free 单独存放。就有了 sdshdr8、sdshdr16、sdshdr32、sdshdr64。以 sdshdr8 为例：

其中，头结构一共占了 S[1(len)+1(alloc)+1(flags)] 个字节。其中 flags 的内容，与 sdshdr 5 类似，只是后 5 位不再存储长度了。

目前 redis 源码中，对于类型的定义如下：

#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

sdshdr8、sdshdr16、sdshdr32、sdshdr64 源码如下：

struct __attribute__ ((__packed__)) sdshdr8 {
    // 已使用长度，1 字节存储，表示buf种已占字节数
    uint8_t len; /* used */
    // 总长度，1 字节存储，表示 buf 中已分配字节数，不同于 free，记录的是为 buf 分配的总长度
    uint8_t alloc; /* excluding the header and null terminator */
    // 低 3 位存储类型，高 5 位预留，标识当前结构体的类型
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    // 柔性数组，真正存储字符串的数据空间
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
  	// 已使用长度，2 字节存储
    uint16_t len; /* used */
    // 总长度，2 字节存储
    uint16_t alloc; /* excluding the header and null terminator */
  	// 低 3 位存储类型，高 5 位预留
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
  	// 柔性数组
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    // 已使用长度，4 字节存储
    uint32_t len; /* used */
    // 总长度，4 字节存储
    uint32_t alloc; /* excluding the header and null terminator */
  	// 低 3 位存储类型，高 5 位预留
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
  	// 柔性数组
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
  	// 已使用长度，8 字节存储
    uint64_t len; /* used */
    // 总长度，8 字节存储
    uint64_t alloc; /* excluding the header and null terminator */
  	// 低 3 位存储类型，高 5 位预留
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
  	// 柔性数组
    char buf[];
};

它们唯一的区别是 len 和 alloc 的占用存储长度不同。

额外，在源码中存在__attribute__ ((__packed__))。在 C 语言中，结构体会按照所有变量中最宽的基本数据类型做字节对齐。

所谓字节对齐，在计算机中内存大小的基本单位是字节（byte），理论上来讲，可以从任意地址访问某种基本数据类型，但是实际上，计算机并非逐字节大小读写内存，而是以2,4,或8的 倍数的字节块来读写内存，如此一来就会对基本数据类型的合法地址作出一些限制，即它的地址必须是2，4或8的倍数。那么就要求各种数据类型按照一定的规则在空间上排列，这就是对齐。

例如 sdshdr32，len、alloc 占用 4 字节，flags 占用 1 字节，buf 是柔性数组，在修饰前，将会按 4 字节对齐大小为 4 * 3 个字节，会存在 3 个字节的填充字节。修饰过后，会按 1 字节对齐，或者理解为取消在编译过程中的优化对齐，此时总空间大小为 11 个字节。

字节对齐是一种提高计算机读写性能的做法，取消字节对齐后可以使结构体在任意平台的计算机上都具有相同的大小，节省了空间，但是牺牲了部分性能。

这样做还有另一个好处：

SDS 返回给上层的，并不是结构体的首地址，而是指向内容的 buf 指针。此时按 1 字节对齐，故 SDS 创建成功后，无论是 sdshdr8、sdshdr16、sdshdr32、sdshdr64，都可以通过(char*)sh+hdrlen得到 buf 指针地址，其中 hdrlen 是结构体的长度，通过 sizeof 计算得到。修饰过后，无论是 sdshdr8、sdshdr16、sdshdr32、sdshdr64，都可以通过计算的到的 buf[-1] 找到 flags，因为此时按 1 字节对齐，不存在填充字节。

如果没有 packed 修饰，需要对不同的结构进行不同处理，实现更复杂。

创建字符串

/* 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-terminated (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 _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
  	// 根据字符串长度选择不同的类型
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8; // 强制将 sds_type_5 转化为 sds_type_8
  	// 计算不同的类型，头信息需要的长度
    int hdrlen = sdsHdrSize(type);
  	// 指向 flags 的指针
    unsigned char *fp; /* flags pointer. */
    size_t usable;

  	
    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
  	// 尝试申请内存
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    // 特殊情况
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
      	// 复制字符串
        memset(sh, 0, hdrlen+initlen+1);
  
  	// s 是指向 buf 的指针
    s = (char*)sh+hdrlen;
  	// fp 是 flags 的指针，s 是柔性数组 buf 的指针，-1 即指向 flags
    fp = ((unsigned char*)s)-1;
  	// 可用空间
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
  	// 根据字符的类型初始化成员变量(len， alloc， flags)，SDS_HDR_VAR的作用是定义
    // sh临时变量（sdshdr*）指向sdshdr的起始位置，用于后面取len和alloc赋值
    switch(type) {
        case SDS_TYPE_5: {
          	// 左移 3 位，即低三位为 0 ，高五位为字符串长度，然后长度和类型执行异或操作，即为 flags 的值
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
  	// 结尾追加结束符
    s[initlen] = '\0';
    return s;
}

可以看到在创建字符串时，redis 会根据字符串的长度选择不同的类型。然后根据类型的不同，分配的头部大小也不同。

需要注意的是，在创建 sdshdr5 类型，在创建空字符串时，会强制转化成 sdshdr8。

原因可能是因为 sdshdr5 可能会频繁的引发扩容，所以直接创建为 sdshdr8。

另外，在长度计算时，有 +1 操作，是为了算上结束符\0。

返回值是指向 SDS 结构 buf 的指针。

释放

/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

#define SDS_TYPE_MASK 7

static inline int sdsHdrSize(char type) {
    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;
}

释放操作，通过 s 向前移动一位，获取到 type 类型，根据不同的类型计算头信息大小，释放对应空间。

扩容

/* 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.
 * If there's already sufficient free space, this function returns without any
 * action, if there isn't sufficient free space, it'll allocate what's missing,
 * and possibly more:
 * When greedy is 1, enlarge more than needed, to avoid need for future reallocs
 * on incremental growth.
 * When greedy is 0, enlarge just enough so that there's free space for 'addlen'.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
  	// sds_type_mask 定义为 7，二进制位 00000111，和 flags 位进行 & 操作，即可获得该 sds 类型。
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
  	// buf 
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
      	// 扩容
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }

    type = sdsReqType(newlen);

  	// 结构 5 不支持扩容
    /* 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);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
  	// 无需更改类型，通过 realloc 扩大柔性数组即可
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
      	// 这里指向 buf 的指针 s 被更新了
        s = (char*)newsh+hdrlen;
    } else {
      	// 类型修改后，头部长度发生了变化，不能进行 realloc 操作，需要重新开辟内存，拼接结束后，释放旧指针
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);// 按长度重新计算空间
        if (newsh == NULL) return NULL;
      	// 复制原来 buf 的内容
        memcpy((char*)newsh+hdrlen, s, len+1);
      	// 释放旧指针
        s_free(sh);
      	// 偏移 sds 结构的起始地址，得到字符串起始地址
        s = (char*)newsh+hdrlen;
      	// 为 flags 赋值
        s[-1] = type;
      	// 为 len 赋值
        sdssetlen(s, len);
    }
  	// 为 alloc 赋值
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

#define SDS_TYPE_MASK 7

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
}

逻辑相较于之前没什么变化。多了按照新长度重新选择存储类型，并分配新的空间的操作。如果需要更改类型，则需要重新开辟内存，并将原字符串的 buf 内容移动到新位置。

总结

对于3.2以前的 SDS 结构，包括字符串长度 len，剩余可用空间 free，以及柔性数组 buf。上层调用时，SDS 直接返回 buf，由于 buf 是直接指向内容的指针，故兼容 C 语言函数，而当真正读取内容时，通过偏移得到 len 来限制读取长度，而非\0，保证了二进制安全。同时读取字符串长度的时间复杂度为 O(1)，也可以避免缓存区溢出的问题。

SDS 通过空间预分配策略，在每次空间分配时，给字符串多分配一些空闲空间，避免了频繁扩容的问题。在进行字符串追加时，一般是不需要频繁重新分配内存的。

通过惰性空间释放策略，SDS 避免了缩短字符串时所需要的内存重新分配操作。并为将来可能有的增长操作提供了优化。

为了进一步压缩空间，在 3.2 之后，SDS 变成了 sdshdr5 中的版本，将 sdshdr5 的类型和长度放在同一属性中，用 flags 的低 3 位存储类型，高 5 位存储长度。

但是创建空字符串时，sdshdr5 会被 sdshdr8 所替代。因为 redis 认为，在创建空字符串后，可能会频繁发生追加操作，这个会引发频繁的扩容操作，所以直接定义为 sdshdr8 类型。

在扩容时，SDS 在设计字符串修改处，会调用 sdsMakeroomFor 函数进行检查，根据不同的情况动态的扩容，该操作对上层透明。