Redis底层数据结构：SDS

Redis中并没有直接使用C语言中的字符串，而是定义了一种简单动态字符串（simple dynamic string）作为Redis的默认字符串实现，简称SDS。

在Redis中，C语言的字符串只会用于一些无需对字符串修改的地方，如日志打印等。

而Redis默认的字符串实现是SDS，如set命令中的key底层即是一个SDS，而value如果是一个字符串类型，则底层也是SDS，如果value是列表，则列表里的每个元素底层都是SDS。

除了set命令外，SDS还被用作缓冲区：AOF模块中的AOF缓冲区，客户端状态中的输入缓冲区等都是SDS实现的。

SDS定义

SDS的定义在Redis源码的src目录下的sds.h和sds.c文件中，定义如下：

SDS的结构由三个属性组成：

• len属性是SDS的长度，包括已分配但未使用的空间
• free属性是剩余空间大小
• buf属性是一个char数组，用于存储数据

如上图所示即为一个SDS，该SDS的len属性为10，free属性为4，即代表该SDS一个可以容纳10个字符长度，目前还剩4个长度，可以计算出该字符串长度为6个字符，buf数组的长度为len加1，原因是SDS保留了C语言字符串末尾为一个/0字符的特性，因此多一个长度。

思考：从空间节省的角度来说，为什么要保留一个/0这样的无意义字符？

在C语言中，保留一个/0字符的目的是为了计算字符串长度，C语言在计算字符串长度时，是通过遍历数组完成的，当查询到/0字符时则认为字符串截止，即/0可以看做是一个字符串结束的标志字符。在SDS中，刚才介绍过SDS可以通过len属性和free属性来确定字符串长度，那么为什么还要保留这个结束标志？原因其实是为了兼容部分C语言的字符串函数，这样可以不用再对SDS重新编写对应的字符串处理函数。

SDS优点

• 优点一：常数时间复杂度获取字符串长度

刚才介绍/0字符的意义时说到了C语言的原生字符串和SDS分别是如何计算字符串长度的，C语言原生的字符串计算长度时，每次都需要遍历一次数组，时间复杂度即为O(N)，而SDS由于通过len和free属性记录了当前数组的状态，因此想要计算字符串疮毒时只需要根据len属性和free属性计算即可，当字符串更新同时完成len和free属性的更新，这样即可在O(1)的时间复杂度内计算出字符串的长度。

Redis通过SDS将字符串长度计算的时间复杂度从O(N)降低为O(1)，确保获取字符串长度的工作不会成为Redis的瓶颈。例如我们即使对一个特别长的字符串键反复执行STRLEN命令时，也不会对系统造成影响。

思考：其实这是一种空间换时间和类似于渐进式hash的思想，通过新增len和free两个变量记录数组的状态，避免频繁的对数组遍历，其次每次数组更新时都需要更新len和free变量，其实是将遍历数组的O(N)时间复杂度分摊到了每次数组更新上。

• 优点二：杜绝缓冲区溢出

在C语言原生的字符串中，当需要修改字符串且修改后的长度大于修改前的长度时，在修改之前需要先对原数组申请空间扩容，否则可能导致数组溢出，内容写入到相邻的下一个数组中从而改变下一个字符串的值。

在SDS中，SDS屏蔽了用户对数组空间的分配，SDS在增长之前会根据free属性自动检测是否足够修改之后的字符串所需空间，如果足够则直接修改，并更新修改之后的len和free属性，如果当前剩余空间不够，SDS会根据空间分配策略自动进行扩容，无需用户关心。

思考：类似于Java中的String类，高级容器等，会提供自动扩容，缩容的功能，具体的细节对使用者透明，能减少开发者的编码负担。

• 优点三：减少修改字符串时带来的内存重新分配次数

在C语言中，修改字符串时，无论是增加长度还是减少长度，都会需要对应的申请新的内存空间或者释放多余的内存空间的操作，这些统称为内存重新分配操作，这些操作不但繁琐，需要开发者自己实现，而且频繁的内存分配也会影响性能。

在SDS中，修改字符串时，增加长度时，SDS会根据空间分配策略自动分配，而且会多余分配一些空间，可能下次扩容时上次分配的多余空间足够使用则不用再次分配空间，减少长度时同理，当减少长度时可能并不会立刻回收空间，而是将多余的空间留下，修改free值，用于下次使用。

SDS的空间分配策略：

空间预分配：用于优化SDS的扩展，当SDS长度增加之后，如果修改后的SDS长度将小于1MB，那么分配和len长度相等的多余空间，反之分配1MB的多余空间。

惰性空间释放：用于优化SDS的字符串缩短操作：当SDS的长度缩短之后，并不会立即释放对应的空间，而是修改free属性，将多余空间保留用以下次扩展。

思考：SDS采用的也是一种空间换时间的思路，无论是扩展之后分配多余空间从而降低下次扩展时需要再次内存分配的概率，还是缩容之后并不立即回收空间而是留给下次扩容，这两种操作都会导致空闲空间增大，内存占用提升，而Redis又了很多数据压缩策略来控制内存。

• 优点四：二进制安全

在C语言原生字符串中，字符必须符合某种编码（例如ASCII），并且字符串里不能包含空格字符，否则会被认为是结束标志，因此C字符串只能存储一些文本数据，而不能存储视频，音频压缩文件这样的二进制数据。

在SDS中，由于SDS是通过len和free属性计算长度的，/0只是为了兼容C字符串，因此即便数据中含有/0也能准确的计算出数据的长度，因此Redis可以存储二进制数据，例如视频等。

总结

思考：在文章首部提到过C字符串一般用于日志打印等字符串不变的场景，那么为什么这种场景要用C字符串而不用SDS？

SDS是采用空间换时间的思路优化字符串更新时的消耗以及字符串计算长度时的消耗，因此同样一个字符串，SDS由于多出的free属性，len属性以及多余分配的空间，占用的空间是超过C字符串的，而对于日志打印的场景，一般不会涉及字符串修改以及长度统计，因此C字符串更节省空间。

Redis中的SDS和Java里的String很相似，都是对原生String进行的一层封装，屏蔽了底层一些操作的细节，方便开发者使用，同时通过空间换时间的方式优化字符串的性能。对于大多数场景，SDS都优于C字符串，而对于不涉及字符串更新和长度统计的场景，则C字符串更节省空间。