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

Redis是一个开源（BSD许可），内存存储的数据结构服务器，可用作数据库，高速缓存和消息队列代理。 首先介绍下Redis的基础数据结构 —— SDS Redis没有使用传统C语言的字符串（字符数组）表示。而是自己构建了一种名为sds(Simple Dymamic String)的抽象类型，作为redis的默认字符类型。 SDS用于保存数据库中的
Redis数据结构-SDS

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

首先介绍下Redis的基础数据结构 —— SDS
Redis没有使用传统C语言的字符串（字符数组）表示。而是自己构建了一种名为sds(Simple Dymamic String)的抽象类型，作为redis的默认字符类型。 SDS用于保存数据库中的字符串值，用户客户端的输入的缓冲区，AOF模块中的缓冲区都是由SDS实现的。

SDS相比于C字符串的优点：

常数复杂度获取字符串长度 缓冲区溢出 减少改变字符串长度时带来的内存重新分配 二进制安全

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

SDS的数据结构：

以下是SDS的数据结构

/*

 * 保存字符串对象的结构

struct sdshdr {

 // buf 中已占用空间的长度

 int len;

 // buf 中剩余可用空间的长度

 int free;

 // 数据空间

 char buf[];

// ps: 在redis 3.0中 为了更加节省内存，可用的sdshdr分成4种，len和free属性分别可以是uint8_t，uint16_t，uint32_t，uint64_t 这四种类型，会随着sds所保存的字符串长度不同，而分配为不同的sdshdr。 

获取长度；

Redis中获取字符长度的操作是
STRLEN key

C语言中的字符串并不记录自身的长度信息。 如果我们想要获取一个c字符串的长度，我们要遍历整个字符串，直到遇到代表结尾符的/n为止。 毫无疑问，其复杂度是O(N)。
而在sds中，我们记录了每个sds对象中所存字符串的长度。 sds提供了一系列操作sds的函数，若出现改变数组长度的草走，都会同步更新len字段，保证len字段的实时性。 这样每个STRLEN的复杂度就变成了O(1).

缓存区溢出：

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

#include stdio.h 

#include string.h 

int main(void)

 char dest[20] = "Hey ";

 for(int i = 0; i i++) {

 strcat(dest, ", Man"); 

 printf("%d time, lenght is: %ld \n", i, strlen(dest));

 return 0;

}

执行结果：

0 time, lenght is: 9

1 time, lenght is: 14

2 time, lenght is: 19

[1] 29751 abort ./str

可以看到，当执行到第三次的时候，并不会由于dest已经快到其最大容量。 所以第四次strcat执行时，会出现溢出，中断程序。
而在sds中，执行sdscat操作，会判断为目标sds对象所分配的内存是否可以容纳拼接后的字符内存。 代码如下：

sds sdscat(sds s, const char *t) {

 return sdscatlen(s, t, strlen(t));

sds sdscatlen(sds s, const void *t, size_t len) {

 struct sdshdr *sh;

 // 获取原字符长度

 size_t curlen = sdslen(s);

 // 扩展空间。 若原指针分配内存不足，则重新分配内存。 返回新的地址

 // T = O(N)

 s = sdsMakeRoomFor(s,len);

 // 若内存不足直接返回

 if (s == NULL) return NULL;

 // 获取sds句柄sdshdr 的指针位置

 sh = (void*) (s-(sizeof(struct sdshdr)));

 // 复制将t中字符串复制到目标字符串后面

 // T = O(N)

 memcpy(s+curlen, t, len);

 // 更新属性

 sdssetlen(s, curlen+len);

 // 添加新结尾符号

 s[curlen+len] = \0;

 // 返回新 sds

 return s;

}

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

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

然而通过C字符串执行会改变字符串长度的操作， 也可以通过判断字符串长度实现预分配内存。每次内存重新分配都要将原内存中的字符复制到新内存中， 复杂度是O(N)，然而当我们频繁地对一个字符串进行改变长度的操作，会导致每次操作都引起一次O(N)的操作。
在sds中， 每次重新分配内存都会预留一部分作为buffer，我们可以从上文的代码中看到，重新分配内存是通过sdsMakeRoomFor函数调用。 那么我们看下sdsMakeRoomFor中，分配内存的策略：

sds sdsMakeRoomFor(sds s, size_t addlen) {

 struct sdshdr *sh, *newsh;

 // 获取s目前剩余的空间长度

 size_t free = sdsavail(s);

 size_t len, newlen;

 // s 目前的空余空间已经足够，无须再进行扩展，直接返回

 if (free = addlen) return s;

 // 获取 s 目前已占用空间的长度

 len = sdslen(s);

 // 获取句柄指针位置

 sh = (void*) (s-(sizeof(struct sdshdr)));

 // 扩展后s至少需要的长度

 newlen = (len+addlen);

 // 根据新长度，为 s 分配新空间所需的大小

 if (newlen SDS_MAX_PREALLOC)

 // 如果新长度小于 SDS_MAX_PREALLOC 

 // 那么为它分配两倍于所需长度的空间

 // 对新建的sds或者重新分配内存的sds，都会采用此策略，保留1倍的长度

 newlen *= 2;

 else

 // 否则，所保留的buffer长度为 SDS_MAX_PREALLOC

 newlen += SDS_MAX_PREALLOC;

 // T = O(N)

 // 分配内存，获取新的指针地址

 newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

 // 若内存不足，分配失败，返回

 if (newsh == NULL) return NULL;

 // 设置剩余空间长度。

 newsh- free = newlen - len;

 // 返回 sds

 return newsh- 

}

redis中为了减少内存的重新分配， 使用了预留buffer的方法。 将原来n次字符串操作一定有n次O(N)复杂度的内存分配， 调整为最多有n次O(N)复杂度的内存分配。
tips： 当执行sdstrim这样减少字符串长度的操作时， 即时裁剪后多余的内存大于len的一半，sds也不会立即将多余的空间释放，而是保留下来未将来的增长操作做了优化。 且提供了sdsRemoveFreeSpace这个APi，用于我们可以手动将这样多余的内存释放。

二进制安全

二进制安全是一个主要用来处理字符串操作的编程术语。二进制安全功能本质上是把输入当作一个没有任何特殊的原生流，其在操作上应包含一个字符所能有的256种可能的值（假设为8为字符）。
由于C字符串需要通过0判断字符串的结尾。 所以当我们储存字符串时，需要将0这样的特殊字符过滤掉。 在sds中，由于我们维护了字符串的长度，所以并没有这样的顾虑。 sds符合二进制安全。

支持c字符串的部分操作函数

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

sds sdsnewlen(const void *init, size_t initlen) {

 struct sdshdr *sh;

 // do somethings to create sds...

 sh- len = initlen;

 sh- free = 0;

 sh- buf[initlen] = \0;

 // 返回 buf 部分，而不是整个 sdshdr

 return (char*)sh- 

}

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

【Redis】SDS 简单动态字符串 Redis没有直接复用C语言的字符串，而是新建了SDS，作为String类型的一种存储结构。 在Redis数据库里，包含字符串值的键值对都是由SDS实现的（Redis中所有的键都是由字符串对象实现的即底层是由SDS实现，Redis中所有的值对象中包含的字符串对象底层也是由SDS实现）
使用CLion调试Redis源码的超详细步骤 因为我本人主要是写Java的，有强烈的IDE依赖症，不喜欢使用文本编辑器或者命令行这样的工具，所以选择使用CLion搭建一个IDE环境来辅助 Redis 源码阅读。
【Redis】一、Redis的简单动态字符串SDS Redis没有直接使用C语言传统的字符串表示(以空字符 \0 结尾的字符数组)，而是构建了一种名为简单动态字符串SDS的抽象类型，并将SDS用作Redis的默认字符串表示。