Redis底层数据结构——SDS

作者: 坤坤坤坤杨 | 来源:发表于2022-11-28 12:24 被阅读0次

Redis设计与实现-笔记（一）
Redis底层数据结构
Redis字符串与C字符串区别
redis
Redis对象(一) - 类型和编码
redis笔记
redis数据结构--SDS
t_string.c
2020-08-16:Redis底层数据结构？
redis底层数据结构以及对象系统

Redis是C语言开发的，C语言自己就有字符类型，但是Redis却没直接采用C语言的字符串类型，而是自己构建了动态字符串（SDS）的抽象类型。Redis的key以及字符串数据结构的值, 最大的大小为 512M。

set aobing cool

就好比这样的一个命令，其实我是在Redis创建了两个SDS，一个是名为aobing的Key SDS，另一个是名为cool的Value SDS，就算是字符类型的List，也是由很多的SDS构成的Key和Value罢了，SDS在Redis中除了用作字符串，还用作缓冲区（buffer）。

redis 3.2之前版本源码如下：

struct sdshdr{
 int len;
 int free;
 char buf[];
}

redis 3.2之后版本源码如下：

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[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
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[];
};
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[];
};
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实际并未使用到. 所以实际上有四种不同的头部, 分别如下:

四种不同的头部分别表示不同长度的字符串。

len 保存了SDS保存字符串的长度。
buf[] 数组用来保存字符串的每个元素。
alloc分别以uint8, uint16, uint32, uint64表示整个SDS, 除过头部与末尾的\0, 剩余的字节数。
flags 始终为一字节, 以低三位标示着头部的类型, 高5位未使用。

1. SDS和c字符串的区别

计数方式不同

C语言对字符串长度的统计，就完全来自遍历，从头遍历到末尾，直到发现空字符就停止，以此统计出字符串的长度，这样获取长度的时间复杂度来说是0（n），大概就像下面这样

而从上面的源码中可以看到，redis自己本身就保存了长度的信息，所以获取长度的时间复杂度为0（1）。

杜绝缓冲区溢出

字符串拼接是我们经常做的操作，在C和Redis中一样，也是很常见的操作，但是问题就来了，C是不记录字符串长度的，一旦我们调用了拼接的函数，如果没有提前计算好内存，是会产生缓存区溢出的。

比如本来字符串长这样：

现在需要在后面拼接，但是没计算好内存，结果就可能这样了：

减少修改字符串时内存重分配次数

C语言字符串底层也是一个数组，每次创建的时候就创建一个N+1长度的字符，多的那个1，就是为了保存空字符的。

Redis是个高速缓存数据库，如果需要对字符串进行频繁的拼接和截断操作，如果写代码忘记了重新分配内存，就可能造成缓冲区溢出，以及内存泄露。

内存分配算法很耗时，对于一个高速缓存数据库来说，这样的开销也是我们应该要避免的。

Redis为了避免C字符串这样的缺陷，就分别采用了两种解决方案，去达到性能最大化，空间利用最大化：

空间预分配：当对SDS进行扩展操作的时候，Redis会为SDS分配好内存，并且根据特定的公式，分配多余的free空间，还有多余的1byte空间（这1byte也是为了存空字符），这样就可以避免连续执行字符串添加所带来的内存分配消耗

如果sds的长度是小于1m的话，分配2*strlen+1byte的长度
如果sds的长度大于等于1m的话，那么分配strlen+1m的内存

比如现在有这样的一个字符：

当调用了拼接函数，字符串边长了，Redis还会根据算法计算出一个free值给他备用：

再继续拼接，备用的free用上了，省去了这次的内存重分配：

在redis 3.2 之后对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用。
惰性空间释放：刚才提到了会预分配多余的空间，很多小伙伴会担心带来内存的泄露或者浪费，别担心，当我们执行完一个字符串缩减的操作，redis并不会马上收回空间，因为可以预防继续添加的操作，这样可以减少分配空间带来的消耗，当再次操作还是没用到多余空间的时候，Redis也还是会收回对于的空间，防止内存的浪费的。
还是同样的字符串

当调用了删减的函数，并不会马上释放掉free空间：

如果我们需要继续添加这个空间就能用上了，减少了内存的重分配，如果空间不需要了，调用函数删掉就好了