SDS Redis 自定义字符串底层结构

1、什么是SDS?

Redis 自定的字符串存储结构，关于redis，你需要了解的几点！中我们对此有过简要说明。

Redis 底层是用C语言编写的，可是在字符存储上，并未使用C原生的String类型，而是定义了自己的字符串结构 Simple Dynamic Stirng，简称SDS。

SDS基本结构如下：

struct sdshdr {

int len; // 记录buf数组中已使用字节的数量，等于SDS所保存字符串的长度

int free; // 记录buf数组中未使用字节的数量

char buf[];// 字节数组，用于保存字符串

};

例如，字符串“Redis”存储示意图为：

图1

当前存储字符串长度为5，未使用长度为0，字节数组存储的字符为“Redis\0”。

这里需要注意的是：内部数据数组存储字符串形式符合C语言要求，以‘\0’结尾。且len字符串长度不包含结尾标识符‘\0’。

buf[]的这种遵循C语言形式的存储，使得Redis可以直接使用C语言的相关字符串函数进行SDS对象的操作。

二、SDS的优势

1、O(1)时间复杂度获取字符串长度

SDS内部维护着一个字符串长度的len变量，可以直接读取，时间复杂度为O(1)。

对于传统的C字符串：字符+“\0”，想要获取字符长度，则需要遍历整个字符串，直到遇到结束字符，时间复杂度为O(n)。

2、缓冲区溢出规避

所谓缓冲区溢出即所需要的内存超出了实际的内存。因此对于C字符串来说，要特别注意内存分配，回收使用问题。

比如，向一个现有字符串内添加特定字符时，需要保证当前已经分配了这足够的内存。

图2

与C不同的是，SDS的空间预分配策略可以避免缓冲区溢出发生，

当需要对SDS进行操作时，首先会检查当前空间是否满足需求，不足则扩展当前分配空间。内存检查相对于C变成了内部预置操作。

3、减少内存重分配次数

上面我们讲到过，C字符操作前都需要进行内存的分配操作，同时，操作完成后，也需要进行相应的内存回收操作。一次操作至少涉及一次内存分配操作。

大家都知道内存的重分配是一个比较复杂且需精细控制的过程，耗时耗资源。针对此弊端，Redis 在SDS内存配置策略上采用了空间预分配+惰性删除相结合的策略。

a）空间预分配：

空间预分配用于优化SDS字符扩展操作。

所谓预分配，也即是说在一次扩展操作中，扩展的空间大小会大于实际需要的空间大小。

如下，图1执行图2操作后SDS变更为：

图3

预分配空间的大小基于以下规则计算：

SDS len

SDS len>=1M：分配1M空间作为预分配空间；

这样，在下次进行字符操作的时候，如果所需要的空间小于当前SDS free空间，则可以直接行操作，而不需要再执行内存扩展，重分配操作。

SDS的预分配机制使得一次扩展操作所需的内存重分配次数变为

b）惰性删除机制

所谓惰性删除，即调整删除SDS中部分数据时，不会立刻执行内存重分配，而是会保留空出来内存，并更新内部free属性。以备将来有字符扩展需求，可以直接使用。

当然，Redis也提供了主动释放未使用内存的方法。

如下，删除“ent”之后的SDS结构：

图4

SDS的内存分配机制，尤其对于以写为主的应用场景，能够提供更加优异的性能表现。

3、二进制安全

C字符串由于特殊的编码要求只能保存文本数据。

SDS相关的功能方法会以二进制的形式来操作SDS存储的数据，没有任何中间操作，存储最原始的数据，因此不会有字符层面的因素影响。

SDS可以保存任何源的二进制数据，字符、图片、文件或者序列化的对象等等。