Redis源码学习——基础数据结构之SDS

redis是一个开源（bsd许可），内存存储的数据结构服务器，可用作数据库，高速缓存和消息队列代理。

首先介绍下redis的基础数据结构 —— sds

redis没有使用传统c语言的字符串（字符数组）表示。而是自己构建了一种名为sds(simple dymamic string)的抽象类型，作为redis的默认字符类型。 sds用于保存数据库中的字符串值，用户客户端的输入的缓冲区，aof模块中的缓冲区都是由sds实现的。

sds相比于c字符串的优点：

常数复杂度获取字符串长度

缓冲区溢出

减少改变字符串长度时带来的内存重新分配

二进制安全

同时，sds也支持c字符串的部分操作函数。

以下是sds的数据结构

redis中获取字符长度的操作是

<code>strlen key</code>

c语言中的字符串并不记录自身的长度信息。 如果我们想要获取一个c字符串的长度，我们要遍历整个字符串，直到遇到代表结尾符的'/n'为止。 毫无疑问，其复杂度是o(n)。

而在sds中，我们记录了每个sds对象中所存字符串的长度。 sds提供了一系列操作sds的函数，若出现改变数组长度的草走，都会同步更新len字段，保证len字段的实时性。 这样每个strlen的复杂度就变成了o(1).

c语言中提供了strcat方法，可以将strsrc字符串拼到strdest字符串尾部。 然而每次执行strcat操作时，都假设了我们已经strdest指针分配了足够多的内存。 然而一旦当分配的内存不足， 机会出现缓存区溢出。如下：

执行结果：

可以看到，当执行到第三次的时候，并不会由于dest已经快到其最大容量。 所以第四次strcat执行时，会出现溢出，中断程序。

而在sds中，执行sdscat操作，会判断为目标sds对象所分配的内存是否可以容纳拼接后的字符内存。 代码如下：

可以看到， 每次执行字符串拼接操作，都会判断所分配的内存是否足够，如果不足，会重新分配内存。 其他操作，例如sdsrange（仅保留部分字符串），sdstrim（裁剪特定字符）都会有以上类似逻辑，保证每次操作都会即时释放多余内存，且不会出现内存不足。

然而通过c字符串执行会改变字符串长度的操作， 也可以通过判断字符串长度实现预分配内存。每次内存重新分配都要将原内存中的字符复制到新内存中， 复杂度是o(n)，然而当我们频繁地对一个字符串进行改变长度的操作，会导致每次操作都引起一次o(n)的操作。

在sds中， 每次重新分配内存都会预留一部分作为buffer，我们可以从上文的代码中看到，重新分配内存是通过sdsmakeroomfor函数调用。 那么我们看下sdsmakeroomfor中，分配内存的策略：

redis中为了减少内存的重新分配， 使用了预留buffer的方法。 将原来n次字符串操作一定有n次o(n)复杂度的内存分配， 调整为最多有n次o(n)复杂度的内存分配。

tips： 当执行sdstrim这样减少字符串长度的操作时， 即时裁剪后多余的内存大于len的一半，sds也不会立即将多余的空间释放，而是保留下来未将来的增长操作做了优化。 且提供了sdsremovefreespace这个api，用于我们可以手动将这样多余的内存释放。

<code>二进制安全是一个主要用来处理字符串操作的编程术语。二进制安全功能本质上是把输入当作一个没有任何特殊的原生流，其在操作上应包含一个字符所能有的256种可能的值（假设为8为字符）。</code>

由于c字符串需要通过'0'判断字符串的结尾。 所以当我们储存字符串时，需要将'0'这样的特殊字符过滤掉。 在sds中，由于我们维护了字符串的长度，所以并没有这样的顾虑。 sds符合二进制安全。

由于sds的api提供的入参都是sds格式，指向的都是其buf属性的指针位置。 我们以一个创建sds的api为例：

我们可以看到，sds对象，我们获取的并不是整个sdshdr指针的位置， 而是其buf属性的指针，也就是存字符串的指针位置，且sds遵守了以'0'作为一个字符串结尾的条件（但并不是通过'0'的位置判断字符串的长度）。 这样就保证了我们对一部分c字符串接口传入sds对象的指针，是可以当作char[]用的。