redis 系列3 数据结构之简单动态字符串 SDS

一.  SDS概述

　　Redis 没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型，并将SDS用作Redis的默认字符串表示。Redis只会使用C字符串作为字面量。在Redis里，使用SDS来表示字符串值，是一个可以被修改的字符串，字符串“键值对”底层都是由SDS实现的。

-- 例1：客户端执行如下命令：
127.0.0.1:6379> set msg "hello world"
OK
127.0.0.1:6379> get msg
"hello world"

　　上面例1中就在数据库里创建一个新的键值对。 其中“键”是一个字符串对象，对象的底层实现是一个保存着字符串"msg" 的SDS。 "键值" 也是一个字符串对象，对象的底层实现是一个保存着字符串" hello world " 的SDS。

-- 例2: 客户端执行如下命令：
127.0.0.1:6379> rpush  fruits "apple" "banana" "cherry"
(integer) 3
127.0.0.1:6379> lrange fruits 0 -1
1) "apple"
2) "banana"
3) "cherry"

　　上面例2中也在数据库里创建一个新的键值对。其中“键”是一个字符串对象，对象的底层实现是一个保存着字符串" fruits " 的SDS。"键值"是一个列表对象，列表包含了三个字符串对象，分别由三个SDS实现。

　　SDS除了用来保存数据库中的字符串值之外，还用作缓冲区(buffer): AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区。

二. SDS 定义

　　每个SDS.h文件下的sdshdr结构表示一个SDS值, 下面是Redis源码，在github的地址是https://github.com/antirez/sds

struct  sdshdr{
    //记录buf数组中已使用字节的数量，也就是字符串的长度
     int len ;
    // 记录buf数组中未使用字节的数量
     int free;
    //字节数组，用于保存字符串
     char buf[];
}

　　在C语言中使用长度为N+1的字符数组来表示长度为N的字符串，并且字符数组最后一个元素总是空字符'\0'。 假设SDS的值为 "Redis"，那么free属性值为0, len 属性值为5, buf数组为R,e,d,i,s五个字符，最后一个字节则保存空字符'\0' 。

三. SDS与C字符串的区别

　　C语言使用简单的字符串表示方式，并不能满足Redis对字符串在安全性，效率以及功能方面的要求，从几个方面说明：

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

　　　　因为c字符串并不记录自身的长度信息，所以为了获取一个c字符串的长度，程序必须遍历整个字符串。与C 字符串不同，因为SDS在len属性中记录了SDS本身的长度，对于SDS的值为"Redis"的字节长度就是5。

　　2. 杜绝缓冲区溢出

　　　　在c中, 假设紧邻的字符串s1 和 s2， s1保存为"redis", s2保存为"mongodb",  如果修改s1的值为 redis cluster, 但修改之前没了空间，那么s1的数据将溢出到s2所在空间中。

　　　　在SDS中，会先检查给定的SDS空间是否足够，会自动扩展修改所需的大小空间。然后在执行实际的修改操作。

　　3. 减少修改字符串时带来的内存重分配次数

　　　　 在c 中，字符串的底层实现总是一个N+1个字符长的数组，因为字符串的长度和底层数组的长度之间存在着这种关联，所以每次增长或者缩短一个c字符串，程序都要对保存这个C字符串的数组进行一次内存重分配操作。

　　　　在SDS中通过未使用空间解除了字符串长度和底层数组长度之间的关联，buf数组的长度不一定就是字符数量加1， 数组里机可以包含未使用的字节，这些由free属性记录。

　　　　3.1 空间预分配

　　　　　　当SDS的API对一个SDS进行操作，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS 分配修改所必须要的空间，还会为SDS分配额外的未使用空间。额外分配的未使用空间数量由以下公式决定：

　　　　　　如果对SDS进行修改之后，SDS的长度(也即是len属性的值) 将小于1MB，那么程序分配和len属性同样大小的未使用空间。这时SDS len属性的值将和fee属性的值相同，例如：修改之后,SDS的len将变成13字节， 那么程序也会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1=27字节。

　　　　　　如果对SDS进行修改之后，SDS的len大于等于1MB, 那么程序会分配1MB的未使用空间，如果对SDS进行修改之后, SDS的len变成30MB,那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度为30MB + 1MB +1byte。

　　　　通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

　　　　3.2 惰性空间释放

　　　　　　惰性空间释放用于优化SDS的字符串缩短操作。当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短多出来的字节，而是使用free属性将这些字节的数据记录起来，并等待将来使用(缩短后未使用的空间不会释放，而是将来增长操作时，再使用这些未使用空间)。

　　4. 二进制安全

　　　　在c字符串的字符必须符合某种编码(如ASCII), 并且除了字符串的末尾之处，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误以为是字符串的结尾，这使得c字符串只能保存文本数据，不能保存图片，音频，视频，压缩文件之类的二进制数据。

　　　　为了保证Redis 可以适用各种不同的使用场景，SDS的API 都是二进制安全的，程序不会对其中的数据做任何限制，过滤，数据写入是什么，读取时就是什么。

　　5. 兼容部分C字符串函数

　　　　在SDS中会遵循C字符串以空字符结尾的惯例，总会为buf数组分配空间时多分配一个字节来容纳这个空字符，这是为了让SDS的字符串可以重用一部分(string.h>库定入的函数。

四 总结

　　4.1  C字符串与SDS之间的区别总结

　　4.2  SDS API(主要的一些API)