SDS

背景

SDS全称Simple Dynamic Strings，中文翻译为简单动态字符串，由antirez也就是Redis作者所发明，是用来代替C原生字符串的一种数据结构。事实上SDS的诞生远远早于Redis，antirez在职业生涯早期就一直用SDS来代替C语言里的字符串实现。字符串在Redis有更是有大量的应用，比如操作String的命令APPEND、STRLEN、SETRANGE等等。这些都对字符串的实现提出极高的性能要求，C字符串自然是无法满足其需求的。

C字符串缺点

"hello"在C字符串内存结构如下图所示。

C字符串如此不堪的最主要的原因是它是以特殊字符\0也叫null-term来判断一个字符串是否结束。

null-term至少会带来以下两个问题：

1. 低效获取字符串长度：获取字符串长度需要遍历整个字符串，直到null-term为止，时间复杂度为O(n);

2. 无法存储\0: 字符串中一旦出现\0后面的字符就会被丢弃，导致字符串读取不完整。

除了null-term，C字符串还有另外一个问题:

1. C字符串分配的内存大小是固定的，如果后续更改字符串需要重新分配内存。因此修改字符串的时间复杂度至少为O(n)。

Redis对于时间复杂度十分敏感，O(n)时间复杂度通常只在小数据量级的数据结构或者低频的命令中使用。

SDS设计

SDS的设计体现出了空间换时间的思想，并且还容在一定程度上能兼原生C字符串。

首先，要解决null-term的问题。我们不基于特殊字符，而是改用额外变量记录一下字符串本身的长度，为了阐述方便我们把它叫做len。那么当：

1. 获取字符串长度时：返回长度变量len的值，时间复杂度O(1)。
2. 读取字符串内容时：直到读取到变量len的长度为止，读取过程中无论出现什么字符都不会导致整个字符串读取不完整。

其次，还要解决修改字符串需要重新分配内存的问题。

为了解决这个问题，我们可以在在创建字符串的时候多分配一些预留内存。只要后续的修改不超过预留内存，就可以实现原地修改了。这是典型的空间换时间。

分配出来的内存空间，前面一部分存储C字符串，后面是还未使用的内存空间，因此前面一部分是能兼容C字符串的。

总结一下，SDS相比C字符串有以下优点：

1. 获取字符串长度快, 时间复杂度O(1)。
2. 存储内容无限制，也称之为binary-safe。
3. 修改字符串（在预留空间范围内）不必重新分配内存，时间复杂度O(mod)，O(mod)指的是修改字符串的时间。C字符串需要重新分配内存，因此时间复杂度为 O(n) + O(mod)

SDS既然这么厉害，SDS到底长什么样呢？我们就来揭晓谜底。

SDS数据结构

SDS结构大致上可以分为2大部分：header部分和buff部分，并且header部分和buff部分在内存中是连续的。

header部分

header部分保存的是SDS一些源数据信息。

其中:

• len表示: 字符串的长度;
• alloc表示：字符串的长度 + 额外预留空间的长度。alloc代表可用来存储字符空间的总大小，但是不包括null-term，所以是比实际分配出来的buff长度减1;

除了我们上面提到过的len和alloc，这里还多了一个flag字段。flag字段决定len和alloc的变量类型。具体什么意思呢？因为字符串大小不固定有长有短，比如我们要保存"hello"这个字符串，那么对于len和alloc变量来说，最合适的变量类型应该是uint8，用一个字节来存储就够了，如果用uint16、uint32或uint64都显得有点太浪费。基于此SDS根据需要保存的字符串长度设计了如下5种flag类型，flag本身占用1个字节，如下表所示:

flag	flag_value	字符串长度(len)字节	(len、alloc) type
SDS_TYPE_5	0	特殊	特殊
SDS_TYPE_8	1	len < (1 << 8) 256	uint8
SDS_TYPE_16	2	len < (1 << 16) 65536	uint16
SDS_TYPE_32	3	len < (1 << 32)	uint32
SDS_TYPE_64	4	len >= (1 << 32)	uint64

假设我们要保存的字符串长度为len:

• SDS_TYPE_5：这个比较特殊，注释上说未被使用，但是也不完全准确，无论如何这个类型都不是我们讨论的重点。
• SDS_TYPE_8: 当len 小于 1 << 8，也就是小于256时，变量len和alloc用uint8类型。
• SDS_TYPE_16: 当len 小于 1 << 16，也就是小于65536时，变量len和alloc用uint16类型。
• SDS_TYPE_32: 当len 小于 1 << 32，也就是小于4294967296时，变量len和alloc用uint32类型。
• SDS_TYPE_64: 当len 大于等于 1 << 32，也就是大于等于4294967296时，变量len和alloc用uint64类型。

我们来举个简单例子，假设我们要用SDS("hello")保存"hello"这个字符串。"hello"长度为5个字节，len为5，是小于 1 << 8。因此flag为SDS_TYPE_8，len、alloc变量类型为uint8各自占用一个字节，flag始终占用1个字节，如下图所示：

len值为5：表示hello字符串长度为5个字节；

alloc值为12: 表示一共分配出来可用空间12字节。buff总长度为13字节，由于null-term要额外占用1字节不能计算在内，因此需要减1；

flag值为1: 表示的是SDS_TYPE_8类型；

再来举一个例子，假设我们要用SDS保存256个"a"。256个"a"长度为256个字节，len为256，是等于 1 << 8 并且小于 1 << 16，因此flag为SDS_TYPE_16。len、alloc变量类型为uint16各自占用两个字节，flag始终占用1个字节，如下图所示：

len值为256: 保存256需要占用2个字节，16进制为01,00。但由于我的电脑是M1 Mac需要用小端保存，所以实际字节顺序为00,01。

alloc值为266: 同上，266小端表为0A,01。

flag值为2: 表示的是SDS_TYPE_16类型。

buff部分

Buff比较简单主要分为2个部分: 第一个部分是原生的C字符串，以null-term结尾，第二个部分是还未使用的额外空间，如下图所示。

前面说过SDS可以在一定程度上兼容C字符串，只要C-String部分是`binary-safe`，用户可以拿到SDS的buff起始地址（图中return to user），在只读场景当作原生C字符串使用。

还是以前面的"hello"字符串为例：

buff部分索引0~5存储"hello"的C字符串，索引6到索引12是预留空间还未使用。如果后续需要追加字符串并且在8个字节以内，即可直接修改，无需重新分配内存空间。

SDS扩容规则

当我们要往原SDS追加字符串时会触发SDS的扩容，为了阐述方便，我们定义如下变量：

len = 原SDS长度;

avail = 原SDS剩余预留空间长度;

addlen = 追加字符串的长度;

newlen = len + addlen 追加后字符串的总长度;

SDS的扩容规则如下：

1. 如果原SDS预留空间空间avail大于等于追加字符串的长度addlen，不会触发扩容。

2. 如果追加后的字符串总长度newlen小于1MB(1024*1024)，将newlen扩容为2倍再加1(null-term)，也就是newlen = newlen * 2 + 1。

3. 如果追加后的字符串总长度newlen大于等于1MB(1024*1024)，将newlen额外扩容1MB再加1(null-term)，也就是newlen = newlen + 1MB + 1。

需要注意的是，如果newlen大于flag所指定的范围，flag的类型也需要随之变大。

我们来举几个例子，依次看一下这3个扩容规则：

规则1：假设有如下图的SDS("hello")，我们要追加字符串",world"。

变量初始化如下：

len = 5;

avail = alloc - len = 12 - 5 = 7;

addlen = “,world”的长度 = 6;

newlen = 5 + 6 = 11;

按照扩容规则，avail > addlen，不会触发扩容，因此可以原地追加，追加后的SDS如下图所示：

规则2：上面的SDS("hello,world")基础上，我们继续追加字符串";nihao"。

变量初始化如下：

len = 11;

avail = alloc - len = 12 - 11 = 1;

addlen = “;nihao”的长度 = 6;

newlen = 11 + 6 = 17;

按照扩容规则，avail < addlen，不满足规则1，newlen < 1MB，满足扩容规则2，因此扩容后的newlen为：

newlen = 17 * 2 + 1 = 35;

如下图所示：

规则3: 我就不细说了，按公式照代入就是了，相信大家也都能理解。

总结

SDS巧妙的利用空间换时间的思想，虽然额外牺牲了一些空间，但是换来的是在高频场景下更佳优异的性能表现以及更好的兼容性。希望这篇文章能对大家在日常工作中有所启发。

如果对文章有任何问题，请不吝赐教，谢谢大家。