Redis底层数据结构——SDS
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空间：
如果我们需要继续添加这个空间就能用上了，减少了内存的重分配，如果空间不需要了，调用函数删掉就好了
二进制安全
C语言是判断空字符（'\0'）去判断一个字符的长度的，但是有很多数据结构经常会穿插空字符在中间，比如图片，音频，视频，压缩文件的二进制数据，就比如下面这个单词，只能识别前面的 不能识别后面的字符。
Redis就不存在这个问题了，他不是保存了字符串的长度嘛，他不判断空字符，只判断长度，所以redis也经常被拿来保存各种二进制数据。
