Redis中String类型数据扩容原理分析

大家好，我是 V 哥。在 Java 中，我们有动态数组ArrayList，当插入新元素空间不足时，会进行扩容，好奇 Redis 中的 String 类型，C 语言又是怎样的实现策略，带着疑问，咱们来了解一下。

在Redis中，String类型数据的扩容主要涉及到SDS（Simple Dynamic String）的内存分配机制。SDS是Redis用来存储字符串的数据结构，它在C语言的字符数组基础上进行了封装，以支持动态扩展长度的功能。

当对一个String类型的值进行修改操作（如增加内容）时，如果现有的空间不足以容纳新的数据，Redis就会进行扩容。

在Redis中，sdsMakeRoomFor 函数是用来扩展SDS字符串的缓冲区的。这个函数的目的是确保SDS字符串有足够的空间来追加新的数据。以下是sdsMakeRoomFor函数的实现逻辑：

1. 检查现有空间：首先，函数会检查SDS字符串的现有空闲空间（由sdshdr结构的free属性记录）是否足够容纳额外的数据。如果足够，函数直接返回，不需要进行扩容。

2. 计算新长度：如果现有空间不足，函数会计算出需要的新长度。这通常是现有长度加上要添加的数据的长度。

3. 确定扩容策略：Redis采用一种预分配策略来优化内存使用和提高性能。如果新长度小于SDS_MAX_PREALLOC（通常为1MB），那么Redis会将新长度扩大两倍，以减少频繁的内存分配操作。如果新长度大于或等于SDS_MAX_PREALLOC，则会一次性分配足够的空间，避免每次扩容都只增加少量空间，导致性能下降。

4. 内存分配：根据新的扩容策略，Redis会使用s_realloc_usable（如果类型未变）或s_malloc_usable（如果类型变化，需要移动数据）来分配新的内存空间。

5. 更新SDS头部：在新的内存空间分配完成后，Redis会更新SDS的头部信息，包括长度、空闲空间等，并复制原有数据到新的内存位置。

6. 处理类型变化：如果扩容导致SDS的类型发生变化（例如，从SDS_TYPE_8变为SDS_TYPE_16），Redis还需要更新SDS的编码类型，并可能需要移动数据到新的内存位置。

在Redis 7.0版本中，SDS的内存布局有所变化，不再使用free属性，而是使用alloc属性来记录分配的空间总长度，len属性记录已使用的字符串长度。因此，alloc和len的差值就代表了空闲空间的大小。这种设计使得SDS在内存布局上更加紧凑，取消了编译器的对齐，以节省内存空间。

sdsMakeRoomFor函数的具体实现如下：

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* 如果有足够的剩余空间，直接返回 */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);

    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    //判断是否为greedy模式（为1表示greedy模式）
    //是将新长度翻倍还是额外增加`SDS_MAX_PREALLOC`
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }
    type = sdsReqType(newlen);

    /* 如果类型是SDS_TYPE_5，但是用户正在追加字符串，那么使用SDS_TYPE_8 */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */

    if (oldtype == type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
       sdssetlen(s, len);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

这个函数首先检查是否有足够的空间来追加数据，如果没有，则根据当前的字符串长度和需要追加的数据长度来计算新的总长度。如果启用了greedy模式，它会根据是否超过SDS_MAX_PREALLOC来决定是将新长度翻倍还是额外增加SDS_MAX_PREALLOC。然后，它会根据新的总长度来确定新的SDS类型，并分配新的内存空间。如果SDS的类型没有变化，它会使用s_realloc_usable来扩展现有的内存空间；如果类型变化了，它会使用s_malloc来分配新的内存空间，并将旧数据复制到新位置。最后，它会更新SDS头部信息，包括长度和分配的空间大小。

注意一下哈，在Redis 7.0版本之前的SDS实现和7.0版本之后的实现有哪些变化呢？

在Redis 7.0版本之前，SDS（Simple Dynamic String）的实现主要包括一个头部结构struct sdshdr，其中包含了记录已使用空间的len字段，记录未使用空间的free字段，以及一个字符数组buf用于存储字符串。这种设计允许SDS在O(1)时间复杂度内获取字符串长度，并且通过维护free字段来减少内存重分配的次数，提高性能。

然而，在Redis 7.0版本中，SDS的实现发生了一些变化。首先，引入了一个新的字段flags，它是一个单字节的字段，用于存储SDS的类型信息。这使得SDS的结构更加紧凑，取消了编译器的对齐，节省了内存空间。其次，free字段被移除，取而代之的是alloc字段，它表示SDS的总分配空间。因此，alloc和len的差值就代表了空闲空间的大小。这种设计使得SDS在内存布局上更加紧凑，同时保持了动态扩展长度的功能。

在Redis 7.0版本中，SDS的类型被定义为以下几种：

• SDS_TYPE_5：长度小于32的字符串，使用flags的5个最高位存储长度。
• SDS_TYPE_8：长度在1到255之间的字符串，使用1个字节存储长度。
• SDS_TYPE_16：长度在256到65535之间的字符串，使用2个字节存储长度。
• SDS_TYPE_32：长度在65536到4294967295之间的字符串，使用4个字节存储长度。
• SDS_TYPE_64：长度大于4294967295的字符串，使用8个字节存储长度。

这种设计允许SDS根据字符串的实际长度选择最合适的头部类型，从而节省内存。例如，对于短字符串，可以使用SDS_TYPE_5类型的头部，它不包含单独的长度和分配字段，而是将这些信息存储在flags字段中。

此外，Redis 7.0版本中的SDS实现还包括了一些其他的优化，例如，使用__attribute__ ((__packed__))来确保结构体在内存中紧凑排列，以及通过s_malloc和s_realloc等函数来管理内存分配，确保内存对齐的同时，也提供了灵活的内存管理。

咱们很显然可以看出，Redis 7.0版本对SDS的实现进行了优化，使其更加紧凑和高效，同时也保持了SDS的动态扩展和二进制安全的特性。这些改进有助于提高Redis在处理大量数据时的性能和资源利用率。关注威哥爱编程，学习代码乐无边