Redis简单动态字符串（ simple dynamic string， SDS）

本文总阅读量次

1、简单动态字符串(SDS)

  • Redis没有使用C语言传统的字符串表示（以空字符结尾的字符数组），而是自己构建了一种名为简单动态字符串的抽象类型，并将SDS用作Redis的默认字符串表示。
在Redis里面，C字符串只会作为字符串字面量用在一些无需对字符串值进行修改的地方，比如打印日志。


当Redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis就会使用SDS来表示字符串值，比如在Redis的数据库里面，包含字符串值的键值对在底层都是由SDS实现的。

举个例子，如果客户端执行命令：

​ ​
redis> SET msg “hello world”
OK
那么Redis将在数据中创建一个新的键值对，其中：

* 键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串 “msg” 的SDS。
* 键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串“hello world”的SDS。

又比如， 如果客户端执行命令： 

    redis> RPUSH fruits "apple" "bannan" "cherry"
    (integer) 3
那么Redis将在数据库中创建一个新的键值对，其中：

  • 键值对的键是一个字符串对象，对象的底层实现是一个保存了字符串“fruits”的SDS。

  • 键值对的值也是一个字符串对象，列表对象包含了三个字符串对象，这三个字符串对象分别有三个SDS实现，第一个SDS保存着字符串apple， 第二个SDS保存着bannan，第三个SDS保存着cherry。

    除了用来保存数据库中的字符串值之外，SDS还被用作缓存区（buffer）

缓冲区

​ C语言给字符串开辟一个存储空间，如果对此存储空间的使用超过开辟的空间，会导致内存溢出。例如使用字符串拼接等方式时，就很容易出现此问题。而如果每次拼接之前都要计算每个字符串的长度，时间上又要耗费很久。

​ redis的SDS中内置一个sdscat函数，也是用于字符串的拼接。但是在执行操作之前，其会先检查空间是否足够，通过比较当前字符串的free与即将拼接字符串的len的大小，就知道是否可以拼接。如果free的值不够，会再申请内存空间，避免溢出。

修改字符串时的内存重分配

​ C语言的字符串长度和底层数组之间存在关联，因此字符串长度增加时需要再分配存储空间，避免溢出；字符串长度减少时，需要释放存储空间，避免内存泄漏。

由于redis中，字符串频繁修改是很经常发生的事情，redis的一个应用场景就是变量频繁修改的场景。为了避免C语言的不断重分配空间，redis进行了改进。

​ redis的sds，主要是通过free字段，来进行判断。通过未使用空间大小，实现了空间预分配和惰性空间释放。

​ 1）空间预分配

空间预分配用于优化字符串的增长操作，实现方式为：当需要增长字符串时，sds不仅会分配足够的空间用于增长，还会预分配未使用空间。

分配的规则是，如果增长字符串后，新的字符串比1MB小，则额外申请字符串当前所占空间的大小作为free值；如果增长后，字符串长度超过1MB，则额外申请1MB大小。

例如，字符串增长后，大小是50kb，则额外申请50kb作为未使用空间。如果字符串增长后的大小是20mb，则额外申请1mb作为未使用空间。以上两种情况都为将\0计算在内，因此，实际上还会需要1字节作为\0存放的空间。

上述机制，避免了redis字符串增长情况下频繁申请空间的情况。每次字符串增长之前，sds会先检查空间是否足够，如果足够则直接使用预分配的空间，否则按照上述机制申请使用空间。该机制，使得字符串增长n次，需要申请空间的次数，从必定为n次的情况，降为最多n次的情况。

2）懒惰空间释放

懒惰空间释放用于优化sds字符串缩短的操作，实现方式为：当需要缩短sds的长度时，并不立即释放空间，而是使用free来保存剩余可用长度，并等待将来使用。当有剩余空间，而有有增长字符串操作时，则又会调用空间预分配机制。

当redis内存空间不足时，会自动释放sds中未使用的空间，因此也不需要担心内存泄漏问题。

二进制安全

​ C语言的字符必须符合某种编码，例如ascii，且字符串除了末尾之外，不能有空格，否则会被当作是另一个字符串。这些限制使得c语言的字符串只能保存不含空格的文本，不能保存图片、视频等二进制数据，也不能保存包含空格的文本。

而保存图片、大段文本等内容，也是redis的常用场景。因此，redis也对此进行优化。因此，sds是二进制安全的，写入的是什么内容，返回的也是什么内容，并没有限制。

​ redis的sds，用buf保存字符串，保存的就是一系列的二进制数据。因为，sds考虑字符串长度，是通过len属性，而不是通过\0来判断。

C语言字符串函数

​ redis兼容c语言对于字符串末尾采用\0进行处理，这样使得其可以复用部分c语言字符串函数的代码，实现代码的精简性。

总结——C语言字符串和SDS字符串比较
C字符串 Redis SDS
获取字符串长度时间复杂的O(n) 获取字符串长度时间复杂的O(1)
字符串长度增加可能造成缓冲区溢出 字符串长度增加不会造成缓冲区溢出
修改字符串长度n次，必然n次内存重分配 修改字符串长度n次，最多n次内存重分配
只保存不含空格文本 保存任意二进制数据和文本数据
可以使用<string.h>库所有函数 可以使用部分<string.h>库的函数