【面试】Redis底层数据结构——SDS动态字符串

雨点打透心脏的1/2处 2023-05-21 07:25 201阅读 0赞

# SDS简单动态字符串 #

## 数据结构 ##

### 3.2之前 ###

typedef char *sds
    struct sdschar {
        
        // buf[] 中已使用的字节数
        int len;
        // buf[] 中未使用的字节数
        int free;
        // 字符数组，用于实际存储字符串内容
        char buf[];
    }

### 3.2之后 ###

对于不同长度的字符串，使用不同的数据结构

/* 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 {
         // 对应字符串长度小于 1<<5（32）
        unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr8 {
         // 对应字符串长度小于 1<<8（256）
        uint8_t len; /* used（目前已经使用的长度）*/
        uint8_t alloc; /* excluding the header and null terminator（分配的总长度）*/
        unsigned char flags; /* 3 lsb of type, 5 unused bits（3bit用来表示类型，剩余的5bit目前没用） */
        char buf[]; // 字符数组，用于实际存储字符串内容
    };
    struct __attribute__ ((__packed__)) sdshdr16 {
         // 对应字符串长度小于 1<<16（64k）
        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[];
    };
    struct __attribute__ ((__packed__)) sdshdr32 {
         // 对应字符串长度小于 1<<32（4G）
        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[];
    };
    struct __attribute__ ((__packed__)) sdshdr64 {
         // 对应字符串长度小于 1<<64
        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[];
    };

## 优势 ##

### 能够以O(1)时间复杂度来获取字符串的长度 ###

原生的`char*`需要遍历直到`\0`来获取长度，而SDS可以直接记录当前已使用的长度。

### 避免缓冲区溢出 ###

缓冲区溢出是指：在进行字符串拼接时避免溢出的数据覆盖在合法的数据上  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjMyMjMwOQ_size_16_color_FFFFFF_t_70]  
在追加`YYY`的时候错误将`XXX`覆盖掉了。所以作者封装了`sdscatlen`来解决这个问题。

sds sdscatlen(sds s, const void *t, size_t len) {
        
        struct sdshdr *sh;
        size_t curlen = sdslen(s); // 获取当前已用的长度（就是直接返回sds数据结构中的len字段）
        s = sdsMakeRoomFor(s,len); // 判断是否要扩容，如果需要，执行扩容操作
        if (s == NULL) return NULL;
        sh = (void*) (s-sizeof *sh);;
        memcpy(s+curlen, t, len);
        sh->len = curlen+len; // 修改len字段
        sh->free = sh->free-len; // 修改free字段
        s[curlen+len] = '\0'; // 填充终结字符"\0"
        return s;    
    }
    sds sdsMakeRoomFor(sds s, size_t addlen) {
        
        struct sdshdr *sh, *newsh;
        size_t free = sdsavail(s); // 获取未使用的字节数（就是直接返回sds数据结构中的free字段）
        size_t len, newlen;
    
        if (free >= addlen) return s; // 如果free还够用，直接返回
        len = sdslen(s);
        sh = (void*) (s-sizeof *sh);;
        newlen = (len+addlen);
        if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC的值为 1024*1024，也就是1M
            newlen *= 2; // 如果追加新字符串后，长度小于1M，则直接申请两倍的空间备用
        else
            newlen += SDS_MAX_PREALLOC; // 如果追加新字符串之后，长度大于1M，则多申请1M备用
        newsh = realloc(sh, sizeof *newsh+newlen+1);
        if (newsh == NULL) return NULL;
    
        newsh->free = newlen - len; // 因为这时候还没有做实际的字符串追加，所以 free = newlen - len
        return newsh->buf;
    }

### 减少字符串变更带来的内存重分配次数 ###

预先分配了一定的空间，保证了一个字符串连续增长N次所需要的内存重分配次数，从必定N次，降低到了最多N次。

字符串长度控制在44字节内，能够降低空间分配(embstr)次数，提升内存使用效率

### 对二进制数据更加友好 ###

SDS并不以`\0`作为字符串结尾的判断，而是每次总会读取len所记录长度的字符串。

### SDS的惰性空间释放 ###

如果字符串长度缩小时，sds并不会自动进行空间释放。它仍然会保留已申请的所有空间，以做备用。可以通过函数 `sdsRemoveFreeSpace`手动释放。

### 内存对齐 ###

对于CPU而言，每次从内存中存取数据都需要一定的开销。为了减少存取次数，CPU每次总会以2/4/8/16/32字节为单位进行存取操作。这个存取单位就叫做内存存取粒度。  
为了迎合CPU的这种存取机制，应用程序应该尽可能相关联的数据所占用的数据块儿大小，刚好是存取单位字节数的整数倍，这样才能够保证CPU的存取次数最小。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjMyMjMwOQ_size_16_color_FFFFFF_t_70]: /images/20230521/a08d5ac1de014ffc960753c0c0d1f47d.png