Chapter1 简单动态字符串（SDS）

1.1 什么是SDS

Redis 没有直接使用C语言的字符串(以空字符结尾的字符数组)来表示String类型，而是自己构建了一种简单动态字符串（simple dynamic string， SDS）。
在Redis中，C字符串只用来作为字符串的字面量（string literal），用在无需对字符串进行修改的地方，例如打印日志：

redisLog(REDIS_WARNING, "Redis is now reday to exit, bye bye ...")

当Redis需要一个可以被修改的字符串值时，Redis会使用SDS来表示，例如字符串的键值对：

redis>SET msg "hello world"
OK

这个操作会创建两个字符串对象：

• 键值对的 key 是一个字符串对象，底层实现是一个保存着 msg 的SDS

• 键值对的 value 也是一个字符串对象，底层实现是一个保存着 hello world 的SDS

又比如，Redis创建列表时：

redis>RPUSH fruits "apple" "banna" "cherry"
(integer) 3

这个操作会在数据库中创建一个新的键值对：

• 键值对的 key 是一个字符串对象，对象的底层实现是一个保存着字符串 msg 的SDS

• 键值对的 value 是一个列表对象，包含着三个字符串对象，分别由3个SDS实现

除了用来保存数据库中的字符串之外，SDS还被用来作为缓冲区：AOF模块中的缓冲区以及客户端状态中的输入缓冲区，都是由SDS实现的。

1.2 SDS与C字符串的区别

C语言采用长度为 N+1 的数组来表示长度为N的字符串，字符数组的最后一个元素总是空字符 '\0'，这种类型的字符串无法满足redis在效率，安全性以及功能方面的需求。

• 获取字符串长度

  C字符串

  • 并不记录自身的长度信息，所以为了获取字符串长度必须对字符数组进行遍历，这种操作的复杂度是 O(N)

  SDS

  • 有一个 len 属性，通过维护这个属性，就可以立即知道字符串的长度，复杂度是 O(1)

• 拼接字符串

  C字符串

  • 由于C字符串并不记录自身的长度，因此对字符串进行拼接时，例如函数：

    char *strcat(char *dest, const char *src)
    

    需要确保用户已经为dest分配了足够的内存来容纳src中的所有内容，如果这个条件无法满足，就会产生缓冲区溢出，造成无法预料的后果。

  SDS

  • SDS的空间分配策略
    在拼接字符串之前，sdscat函数会先检查给定的SDS的空间是否足够，如果不满足的话，API会自动扩展
    SDS的空间至执行修改所需的大小，再执行拼接操作。

• 修改字符串

  C字符串

  • 由于C字符串底层是一个字符数组，每次对字符串进行修改，都需要对保存这个C字符串的数组进行一次内存重分配操作:
    执行拼接操作，需要通过内存重分配来扩展底层数组的大小，否则会产生缓冲区溢出。
    执行截断操作，需要通过内存重分配来释放字符串不再使用的那部分空间，否则会产生内存泄露。

  SDS

  • 空间预分配（用于优化SDS的字符串增长操作）

    当SDS的API对一个SDS进行修改，需要对一个字符串进行空间扩展时，程序除了为SDS分配修改所必须的空间之外， 还会为SDS分配额外的空间：
    如果修改之后，SDS的长度小于1MB，则会分配和 len 属性同样大小的未使用空间。
    如果修改之后，SDS的长度大于或等于1MB，会为SDS分配1MB的未使用空间。
    通过空间预分配的策略，Redis可以减少连续实现字符串增长操作所需要的内存重分配次数。

  • 惰性空间释放（用于优化SDS的字符串缩短操作）

    当SDS的API需要执行缩短SDS保存的字符串时，程序并不立即回收多出来的空间，而是维护一个 free 属性，将这些字节的数量记录下来，等待将来使用。与此同时，SDS也提供了相应的API可以让我们在有需要的时候释放SDS的未使用空间，所以不必担心惰性空间释放策略会造成内存浪费。

• 二进制安全

  C字符串

  • C字符串必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则第一个空字符将被误以为是字符串的结尾，这就导致C字符串只能保存文本数据，而不能保存图片、音频、视频、压缩文件这样的二进制数据。

  SDS

  • SDS使用 len 属性而不是空字符来判断字符串是否结束，所以SDS不仅可以保存文本数据，还可以保存任意格式的二进制数据。

除了上述的部分功能外，SDS还兼容部分C字符串函数,这样就可以重用<string.h>函数库，从而避免了不必要的代码重复。

• 总结

  C字符串	SDS
  获取字符串长度的复杂度为O(N)	获取字符串长度的复杂度是O(1)
  API是不安全的，可能造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
  修改字符串长度N次必然执行N次内存重分配	修改字符串长度N次最多需要执行N次内存重分配
  只能保存文本数据	可以保存文本或二进制数据
  可以使用所有<string.h>库中的函数	可以使用一部分<string.h>库中的函数