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至少会带来以下两个问题：

低效获取字符串长度：获取字符串长度需求遍历整个字符串，直到null-term停止，时刻复杂度为O(n);
无法存储\0: 字符串中一旦呈现\0后边的字符就会被丢掉，导致字符串读取不完整。

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

C字符串分配的内存巨细是固定的，假如后续更改字符串需求重新分配内存。因而修改字符串的时刻复杂度至少为O(n)。

Redis对于时刻复杂度非常敏感，O(n)时刻复杂度通常只在小数据量级的数据结构或许低频的命令中运用。

SDS规划

SDS的规划体现出了空间换时刻的思想，而且还容在必定程度上能兼原生C字符串。

首先，要处理null-term的问题。咱们不基于特别字符，而是改用额定变量记载一下字符串自身的长度，为了阐述便利咱们把它叫做len。那么当：

获取字符串长度时：回来长度变量len的值，时刻复杂度O(1)。
读取字符串内容时：直到读取到变量len的长度停止，读取过程中不管呈现什么字符都不会导致整个字符串读取不完整。

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

为了处理这个问题，咱们能够在在创立字符串的时候多分配一些预留内存。只需后续的修改不超越预留内存，就能够实现原地修改了。这是典型的空间换时刻。

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

总结一下，SDS比较C字符串有以下长处：

获取字符串长度快, 时刻复杂度O(1)。
存储内容无限制，也称之为binary-safe。
修改字符串（在预留空间范围内）不必重新分配内存，时刻复杂度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的扩容规矩如下：

假如原SDS预留空间空间avail大于等于追加字符串的长度addlen，不会触发扩容。
假如追加后的字符串总长度newlen小于1MB(1024*1024)，将newlen扩容为2倍再加1(null-term)，也便是newlen = newlen * 2 + 1。
假如追加后的字符串总长度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巧妙的利用空间换时刻的思想，虽然额定献身了一些空间，可是换来的是在高频场景下更佳优异的功能表现以及更好的兼容性。希望这篇文章能对大家在日常工作中有所启发。

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

Redis数据结构之SDS

SDS

背景

C字符串缺陷

SDS规划