【Redis 设计与实现】第二章 动态字符串

李林翰 16/05/29 09:11:46

【Redis 设计与实现】第二章 动态字符串

Redis没有直接使用C语言中的传统字符串,而是自己构建了一个简单的动态字符串(Simple dynamic string, SDS)的抽象类型。Redis使用C语言的字符串只是当该字符串为字符串常量的时候使用,一般都是直接构造SDS的对象来使用。另:AOF模块中,Redis还会使用SDS作为缓冲区来用。

我们接下来详细说说这个SDS。

SDS的定义

typedef char *sds;

struct sdshdr {
    // buf 已占用长度
    int len;
    // buf 剩余可用长度
    int free;
    // 实际保存字符串数据的地方
    char buf[];
};

Example: "hello world" 字符串在Redis中保存的状态
struct sdshdr {
    len = 11;
    free = 0;
    buf = "hello world\0";  // buf 的实际长度为 len + 1
};

注意 : len的大小不包括最后’\0’字符。

SDS与C字符串的区别

SDS和C字符串的比较

  • SDS取字符串的大小的时间复杂度是O(1),而C语言字符串获取大小的时间复杂度是O(n)。原因是SDS的结构体中len属性保存的就是SDS保存的字符串长度。
  • C语言字符串正因为没有保存自身的大小,有时候容易出现安全方面的问题。SDS的API对SDS进行修改时候,首先会检查SDS的空间是否足够,不够会将SDS的空间拓展到需要的大小。然后才进行实际上的修改,所以不会有缓冲区溢出的问题。

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

我们在使用字符串的时候,最容易改变自身大小的方法就是增加(append)截断(trim)了。

  • 增加时,如果不通过内存重分配操作,很有可能发生缓冲区溢出的问题。
  • 截断时,如果不通过内存重分配操作,很有可能发生内存泄漏的问题。

众所周知,内存重分配牵扯“非配空间,数据迁移和释放原有空间”等操作,所以内存重分配是一件非常耗时的事情。我们要尽可能的减少在修改字符串时带来的内存分配次数。

通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化策略。

  1. 空间预分配:当SDS的API对一个SDS进行修改,并且需要对SDS进行空间拓展时候,程序不仅会为SDS分配修改时所必要的空间,还会为SDS分配额外的未使用空间。
  2. 惰性空间释放:当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录下来,并等待将来使用。(但Redis提供了相应的API,可以真正释放SDS的未使用空间,所以不用担心内存泄露的问题。)

二进制安全

C语言字符串必须符合某种编码(ASCII编码),并且除了字符串的末尾之外,字符串里面不能包含空字符,否则空字符会被误认为是字符串的末尾。但是SDS可以,所以SDS还可以保存像图片、音频、视频、压缩文件这样的二进制数据。(buf为字节数组,通过这样的方式来实现)

兼容部分C字符串函数

虽然SDS的API都是二进制安全的,但它们一样遵循C字符串以空字符结尾的惯例。虽然这个字符不占大小,但是在分配的时候,SDS会默认分配len+1大小的空间。

SDS API

Alt text