Redis学习(1)——简单动态字符串

1，Redis简单动态字符串的简介

Redis没有直接使用C语言传统的字符串表示（Redis使用ANSI C语言语言编写），而是自己构建了一种名为简单动态字符串（simple dynamic string,SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。(C语言字符串在Redis中也有应用，不过只用在一些无须对字符串值进行修改的地方，如Redis日志的打印)

2，SDS和键值对的关系

（1）Redis的数据库里面，我们是以键值对的形式存储数据，而键值对在底层都用SDS实现。

这里的键 1 是一个字符串对象，底层的实现是一个保存字符串“1”的SDS,同理，键值对的值也是如此。

（2）除了用来存放字符串，SDS还被用来作为缓冲区（buffer）

3，SDS的底层源码

每个sds.h/sdshdr结构表示一个SDS值

 

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

 

free 0 ：表示这个SDS没有分配未使用的空间。

len 5 :表示这个SDS保存了5字节长的字符串。

buf[]：表示存储了‘r’'e'‘d’'i''s'五个字符的字符数组。而最后一个‘\0’则是Redis遵循C语言的习惯以一个空字符串结尾。但并不计入len中去，'\0'的添加是额外分配的1字节空间，它是由SDS函数自动完成的。而遵循这样的结尾的习惯也使得SDS在这里可以如C语言字符串一样，重用一些C语言的函数库。

4，C语言与SDS的区别在于：

（1）C语言如果像上面一样存放一个字符串"redis"，它的字符串的长度为：5+1（‘r’'e'‘d’'i''s'五个字符加上一个空字符'\0'）。而SDS的buf数组的长度,则是实际字符的长度，并且由len进行了记录。

在字符串长度上面的区别总结起来就是：C语言没有记录长度，而SDS记录了长度。这样的做法，也会使得C语言在获得自身字符串长度时复杂度为O（N）（从头开始遍历直到遍历到空字符串）而SDS记录了自身长度获取自身长度的复杂度为O（1）。

（2）C语言由于不记录字符串长度，在某些操作时会造成溢出。而SDS记录了长度，在空间分配时SDS API（设置和修改SDS长度由SDSAPI自动执行）对SDS进行修改时，API会先检查SDS空间是否能够满足操作需求。如果不满足API会根据执行的操作需求重新修改SDS长度。这样杜绝了溢出的情况。

（3）C语言，由于不记录自身长度，并且底层的实现是是N+1个字符长的数组，因此如果有对字符串的修改需要按照操作重新分配空间，否则就容易溢出。而SDS通过未使用空间（free属性记录未使用的空间）的分配将字符串长度和底层字符串长度分开（SDS中的底层buf[ ] 不一定等于 字符串长度）。这样的方式使得SDS实现了空间预分配和惰性空间释放。

5,空间预分配和惰性空间释放

（1）空间预分配

当对SDS的进行修改，并且存储字符空间也要修改时，是SDS不仅会被分配相应大小的空间，还会被分配未使用的空间。

分配未使用空间大小的规则：

a,当对SDS进行修改后，SDS的长度小于1MB,len的大小就是分配的未用空间（free）的大小。

例如：修改后，SDS的len属性的值为5字节，free也会是5字节，而buf[]的长度就变为了5+5+1 = 11。

b,当对SDS进行修改后，SDS的长度≥1MB,free的大小就会是1MB。

例如：修改后SDS的len为2MB，free就为1MB。buf[] 的长度为 2MB + 1MB + 1byte

通过这种分配策略，SDS减少了重新分配内存的次数。而在修改SDS之前，SDS API会通过free属性先检查未使用空间是否足够，如果够用则直接使用不用再分配内存。

（2）惰性空间释放

空间预分配用于解决SDS增长字符串的操作，而惰性空间释放则是用于缩短字符串的操作。当修改SDS，使其缩短时，那些不使用的空间不会被立即回收，而是记录到free中留待以后使用。

6，二进制安全（binary-safe）

SDS API在处理buf[ ]中的数据时，会像处理二进制一样。因此存进去是什么样，读取时就是什么样。