Redis-SDS

SDS

SDS（simple dynamic string），简单动态字符串，Redis String类型数据结构的底层实现。

Redis是用C语言开发的，但是Redis对于那些需要动态修改的字符串在其底层就会使用SDS，如：Redis中的key-value键值对含有字符串值的，都是由SDS实现，具体的：

1. 在Redis执行一个最简单的set命令，这时Redis会新建一个键值对：

127.0.0.1:6379> set test "测试"

此时键值对的key和value都是字符串对象，而对象的底层实现分别是两个保存着字符串test和测试的SDS结构。

2. 向一个列表中压入数据，Redis 又会新建一个键值对：

127.0.0.1:6379> lpush test "测试1" "测试2"

这时候键值对的键和上边一样，还是由SDS实现的字符串对象，键值对的值是包含两个字符串对象的列表对象了，而这两个对象的底层也是由SDS实现。

Redis也支持使用C语言的传统字符串，只不过会用在一些不需要对字符串修改的地方，比如静态的字符输出。

SDS结构

SDS的数据结构，主要由 len、free、buf[] 这三个属性组成：

struct sdshdr{int free; // buf[]数组未使用字节的数量int len; // buf[]数组所保存的字符串的长度char buf[]; // 保存字符串的数组
}

其中：

• buf[] 为实际保存字符串的char类型数组；

• free表示buf[]数组未使用字节的数量；

• len表示buf[]数组所保存的字符串的长度。

例如上图表示的是buf[]保存长度为6个字节的字符串(一个汉字3个字节)，未使用的字节数free为0，但是眼尖的同学会发现这明明是7个字符，还有一个"\0"啊？

上边提到过SDS没有完全直接使用C的字符串，但还是沿用了一些C特性的，比如遵循C的字符串以空字符结尾的规则，这样还可以使用一部分C字符串的函数。而对于SDS来说，空字符占用的一字节是不计算在len属性里的，会为他分配额外的空间。

SDS优点

效率高

工作中使用Redis，经常会通过STRLEN命令得到一个字符串的长度，在SDS结构中len属性记录了字符串的长度，所以获取一个字符串长度直接取len的值，时间复杂度是O(1)。

而如果用C字符串，在获取一个字符串长度时，需对整个字符串进行遍历，直至遍历到空字符结束（C中遇到空格符代表一个完整字符串），此时的复杂度是O(n)。在高并发场景下频繁遍历字符串，获取字符串的长度很有可能成为Redis的性能瓶颈，所以SDS性能更好一些。

数据溢出

上边提到C字符串是不记录自身长度的，相邻的两个字符串存储的方式可能如下图，为字符串分配了合适的内存空间。

如果此时如果想把“程序员内点事”改成“程序员内点事123”，可之前分配的内存只有18个字节，修改后的字符串需要21个字节才能放下，没办法只能侵占相邻字符串的空间，自身数据溢出导致其他字符串的内容被修改。

而SDS很好的规避了这点，当需要修改数据时，首先会检查当前SDS空间free是否满足，不满足则自动扩容空间至修改所需的大小，然后再执行修改，如下图所示：

不过有个特殊的地方，在把“程序员内点事”的6个字节扩容到“程序员内点事123”9个字节后，发现free属性的值变成了扩容后字符串的总长度，这就涉及到下边要说的内存重分配策略了。

内存重分配

C字符串长度是一定的，所以每次在增长或者缩短字符串时，都要做内存的重分配，而内存重分配算法通常又是一个比较耗时的操作，如果程序不经常修改字符串还是可以接受的。

但很不幸，Redis作为一个数据库，数据肯定会被频繁修改，如果每次修改都要执行一次内存重分配，那么就会严重影响性能。

SDS通过两种内存重分配策略，很好的解决了字符串在增长和缩短时的内存分配问题。

1.空间预分配

空间预分配策略用于优化SDS字符串增长操作，当修改字符串并需对SDS的空间进行扩展时，不仅会为SDS分配修改所必要的空间，还会为SDS分配额外的未使用空间free，下次再修改就先检查未使用空间free是否满足，满足则不用在扩展空间。

通过空间预分配策略，Redis可以有效的减少字符串连续增长操作所产生的内存重分配次数。

额外分配未使用空间free的规则：

• 如果对 SDS 字符串修改后，len 值小于 1M，那么此时额外分配未使用空间 free 的大小与len相等。
• 如果对 SDS 字符串修改后，len 值大于等于 1M，那么此时额外分配未使用空间 free 的大小为1M。

2.惰性空间释放

惰性空间释放策略则用于优化SDS字符串缩短操作，当缩短SDS字符串后，并不会立即执行内存重分配来回收多余的空间，而是用free属性将这些空间记录下来，如果后续有增长操作，则可直接使用。

数据格式多样性

C字符串中的字符必须符合某些特定的编码格式，而且上边也提到，C字符串以\0空字符结尾标识一个字符串结束，所以字符串里边是不能包含\0的，不然就会被误认是多个。

由于这种限制，使得C字符串只能保存文本数据，像音视频、图片等二进制格式的数据是无法存储的。

Redis 会以处理二进制的方式操作buf数组中的数据，所以对存入其中的数据未做任何的限制、过滤，只要存进来什么样，取出来还是什么样。

参考：

阿里面试这样问：redis 为什么把简单的字符串设计成 SDS？