简单动态字符串

简单动态字符串

数据结构

简单动态字符串( simple dynamic string, SDS)用作Redis的默认字符串表示,取代 C 默认的char*类型

> set msg "hello redis" 其中键和值都是SDS

SDS还被用作缓冲区(buffer):AOF模块中的AOF缓冲区,以及客户端状态中的输入缓冲区

typedef char *sds;


struct sdshdr {

    // buf 已占用长度
    int len;

    // buf 剩余可用长度
    int free;

    // 实际保存字符串数据的地方
    char buf[];
};

2个字节长度的没必要使用int,为提高内存使用率,新版做了优化:

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3

sds指针指向buf,回退指针就可以获取其他参数

优势

SDS相对C字符串的好处

获取字符串长度复杂度为O(1)

C语言使用N+1的字符数组来表示长度N的字符串,并且以空字符\0结尾,为获取字符串长度,需要遍历到空字符为止,复杂度为O(n)

防止缓存区溢出

之外, C 字符串 不 记录 自身 长度 带来 的 另一个 问题是 容易 造成 缓冲区 溢出( buffer overflow), 如char *strcat( char *dest, const char *src);等函数,并未设置长度限制。

SDSAPI会先检查SDS的空间是否满足修改所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作

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

因为 C 字符串的长度和底层数组的长度之间存在着这种关联性, 所以每次增长或者缩短一个 C 字符串, 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作

SDS对于内存操作实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

SDS使用sdsMakeRoomFor函数扩展字符串

  • 如果原来字符串中的空余空间够用(avail >= addlen),那么它什么也不做,直接返回。
  • 如果需要分配空间,它会比实际请求的要多分配一些(len+addlen)*2,以防备接下来继续追加。它在字符串已经比较长的情况下要至少多分配SDS_MAX_PREALLOC个字节,这个常量在sds.h中定义为(1024*1024)=1MB。
  • 按分配后的空间大小,可能需要更换header类型(原来header的alloc字段太短,表达不了增加后的容量)。
  • 如果需要更换header,那么整个字符串空间(包括header)都需要重新分配(s_malloc),并拷贝原来的数据到新的位置。
  • 如果不需要更换header(原来的header够用),那么调用一个比较特殊的s_realloc,试图在原来的地址上重新分配空间。s_realloc的具体实现得看Redis编译的时候选用了哪个allocator(在Linux上默认使用jemalloc)。但不管是哪个realloc的实现,它所表达的含义基本是相同的:* * 它尽量在原来分配好的地址位置重新分配,如果原来的地址位置有足够的空余空间完成重新分配,那么它返回的新地址与传入的旧地址相同;否则,它分配新的地址块,并进行数据搬迁。
惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作: 当 SDS 的 API 需要缩短 SDS 保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是把缩短后的长度记录在len属性中,剩余空间用于未来扩展字符串用。如sds sdstrim(sds s, const char *cset)

sds sdsRemoveFreeSpace(sds s) 函数真正free掉空闲空间

二进制安全

C 字符串中的字符必须符合某种编码(比如 ASCII), 并且除了字符串的末尾之外, 字符串里面不能包含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据, 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

因此, 为了确保 Redis 可以适用于各种不同的使用场景, SDS 的 API 都是二进制安全的(binary-safe): 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据, 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的, 它被读取时就是什么样。

兼容部分C字符函数