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
,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巧妙的利用空间换时刻
的思想,虽然额定献身了一些空间,可是换来的是在高频场景下更佳优异的功能表现以及更好的兼容性。希望这篇文章能对大家在日常工作中有所启发。
假如对文章有任何问题,请不吝赐教,谢谢大家。