几分钟教你掌握Redis简单动态字符串SDS

正文

Redis 没有直接使用 C 语言传统的字符串表示(而是以空字符结尾的字符数组,以下简称 C 字符串),自己构建了一种名为简单动态字符串(simple dynamic string,SDS) 的抽象类型,并将 SDS 用作 Redis 的默认字符串表示。

在 Redis 里面,C 字符串只会作为字符串字面量(string literal),用在一些无须对字符串值进行修改的地方,比如打印日志:

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

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

举个例子,如果客户端执行命令:

redis> SET msg "hello world"
OK

那么 Redis 将在数据库中创建了一个新的键值对,其中:

  • 键值对的键是一个字符串对象,对象的底层实现是一个保存着字符串 "msg" 的 SDS 。
  • 键值对的值也是一个字符串对象,对象的底层实现是一个保存着字符串 "hello world" 的SDS。

又比如说,如果客户端执行命令:

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

那么 Redis 将在数据库中创建一个新的键值对,其中:

  • 键值对的键是一个字符串对象,对象的底层实现是一个保存了字符串 "fruits" 的 SDS 。
  • 键值对的值是一个列表对象,列表对象包含了三个字符串对象,这三个字符串对象分别由三个 SDS 实现:第一个 SDS 保存着字符串 "apple" ,第二个 SDS 保存着字符串 "banana" ,第三个 SDS 保存着字符串 "cherry"

除了用来保存数据库中的字符串值之外,SDS 还被用作缓冲区(buffer):AOF 模块中的 AOF 缓冲区,以及客户端状态中的输入缓冲区,都是由 SDS 实现的,在之后介绍 AOF 持久化和客户端状态的时候,我们会看到 SDS 在这两个模块中的应用。

AOF中记录的是每一个命令的详细信息,包括完整的命令类型、参数等。只要产生写命令,就会实时写入到AOF文件中

SDS的定义

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

与C字符串的区别

C语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串,并且字符数组的最后一个元素总是空字符 '\0'

获取字符串长度

因为 C 字符串并不记录自身的长度信息,所以为了获取一个 C 字符串的长度,程序必须遍历整个字符串O(N)O(N)O(N) 。

和 C 字符串不同,因为 SDS 在 len 属性中记录了 SDS 本身的长度,所以获取一个 SDS 长度的复杂度仅为 O(1)O(1)O(1) 。

杜绝缓冲区溢出

C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出(buffer overflow)。

假设程序里有两个在内存中紧邻着的 C 字符串 s1 和 s2 ,其中 s1 保存了字符串 "Redis" ,而 s2 则保存了字符串 "MongoDB" .

如果一个程序员决定通过执行:strcat(s1, "Cluster")将 s1 的内容修改为 "Redis Cluster" ,但粗心的他却忘了在执行 strcat 之前为 s1 分配足够的空间,那么在 strcat 函数执行之后,s1 的数据将溢出到 s2 所在的空间中,导致 s2 保存的内容被意外地修改。

SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当 SDS API 需要对 SDS 进行修改时,API 会先检查 SDS 的空间是否满足修改所需的要求,如果不满足的话,API 会自动将 SDS 的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用 SDS 既不需要手动修改 SDS 的空间大小,也不会出现前面所说的缓冲区溢出问题。

减少内存分配次数

因为 C 字符串的长度和底层数组的长度之间存在着这种关联性,所以每次增长或者缩短一个 C 字符串,程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作,在 SDS 中,数组里面可以包含未使用的字节,而这些字节的数量就由 SDS 的 free 属性记录。并实现了两种优化策略:

空间预分配,当进行字符串增长操作时,程序会额外分配空间,并记录的free字段

比如原长度为8的字符串,新增5个长度后,总共为13长度,则预分配13+13+1=27字节(额外一字节用于保存空字符串)

对于大于1M来说,分配空间为原有总长度+1MB+1byte

比如增加完字符串后长度为15MB,则为15MB+1MB+1byte

惰性空间释放,当进行字符串缩短操作时,程序不立即重新分配内存,而是用free属性将这些字节的数量记录起来。

二进制安全

C字符串中不能包含空字符串,否则会被误认为是字符串结尾。所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据,程序不会对其中的数据做任何限制、过滤、或者假设 ——数据在写入时是什么样的,它被读取时就是什么样。

作者:golandscape

%s 个评论

要回复文章请先登录注册