redis源码分析之底层数据结构(一)-动态字符串sds

1.绪论

我们知道redis是由c语言实现的，c语言中是自带字符串的，但是为什么redis还要再实现自己的动态字符串呢，这种动态字符串的底层数据结构是怎样的呢?接下来我们带着这些问题来看一看redis中的动态字符串sds。

2.sds的组成

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 *///整个sds字符串的大小uint16_t alloc; /* excluding the header and null terminator *///表示是5种sds字符串中的哪一种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[];
};

可以看出redis中sds是一个动态数组，它由长度+sds占据内存大小+sds的类型+加一个数组组成。如果用图表示如下：

可以看出redis的sds和java中的ArrayList是类似的。

3.sds的优点

为什么redis需要重新实现一个字符串呢？主要有如下的几点考虑：

3.1.常数时间复杂度获取字符串长度

普通字符串以'\0'结尾，而sds存取了整个字符串占据多少个字符。所以普通字符串需要用o(n)的复杂度获取到字符串长度，而sds以o(1)的复杂度获取到字符串长度；

3.2.存储特殊符号\0

sds能够存储特殊符号\0'，当时c语言原生的字符串以'\0'结尾，不能存储\0，保证二进制安全；

3.3.内存动态分配，防止杜绝缓冲区溢出

c语言原生字符串，内存一但分配，大小便固定，比如在调用'append key'命令的时候，会实现字符串拼接的功能，如果超出缓冲器大小，会超出分配内存大小而报错；
但是sds实现了动态扩展的功能，在拼接前，会检查内存是否够用，如果不够用，便会进行动态扩容，而如果数组的剩余空间过多，便会进行缩容。

3.3.1 动态扩容

当新的字符串占用空间超出分配内存空间时，会进行动态分配，并且会提前考虑预分配一部分空间，防止内存的频繁分配问题。

3.3.2 动态缩容 

当已使用内存小于分配内存的部分比例时，会进行动态缩容，并且采用惰性释放的策略，不使用的数据并不会立即清除，而是等待有新的字符串写入的时候进行覆盖。

3.4.节约内存

在高版本的redis中，将存储字符数值分成了5类，分别是sdshdr5 、sdshdr8 、sdshdr16 、sdshdr32 、sdshdr64 ，redis会根据存储的字符内容来判断采用哪个中字符串尽显存储数据。比如如果用户写入的字符串只包含abcd这种英文字母，每个字符串用一个字节便能存储。sds便会考虑采用sdshdr8来进行存储.

4.总结

可以看出redis的sds其实就相当于java中的ArrayList，都具有动态扩容，缩容等功能。

5.参考

[1] 黄建宏 redis设计与实现

[2] https://juejin.cn/book/7144917657089736743/section/7144917738698326019