Redis 底层数据结构之字符串

Redis 是一种高效的非关系型数据库,高效的系统必然拥有高效的数据结构。

C 语言中的字符串

Redis 使用 C 语言编写,C 语言中的字符串有以下特点:

  • 使用长度为 N+1 的字符数组来表示长度为 N 的字符串;
  • 字符数组的最后一个元素总是空字符 '\0'。

直接使用 C 语言中的字符串作为 Redis 的底层存储结构,会面临几个问题:

  • 获取字符串长度需要遍历字符串;
  • 字符串遇到 '\0' 会被截断;
  • 修改字符串时容易造成缓冲区溢出。

为了保证字符串操作的安全性,我们需要在字符串连接、拷贝等操作前,对字符串空间进行重新分配
虽然 C 语言的性能已经很高,但 Redis 作为高性能数据库,直接使用 C 语言中的字符串结构仍然面临性能开销的问题。

Redis 中的字符串结构

Redis3.2 之前的版本中使用 SDS 这种结构体来存储字符串,SDS 结构定义如下:

struct sdshdr {
    int len;
    int free;
    char buf[];
};

因为直接存储了 buf 长度,因此获取字符长度的复杂度降为 O(1);free 记录了可用空间大小,在字符串操作时可以避免缓冲区溢出的问题。除了以上两点,Redis 还从其他方面对 SDS 做了进一步的改进。

减少修改字符串时频繁的内存重分配

虽然 free 字段能杜绝缓冲区溢出问题,但是不能避免修改字符串时的内存重分配问题,例如在使用 strcat 时,如果 free 小于需要连接的字符串长度,就需要重新分配空间,如果旧空间未释放,还会造成内存泄漏。

Redis 使用空间预分配以及惰性空间释放两种策略,对内存分配进行了一定程度的改善。

1. 空间预分配

当对 SDS 进行修改并且需要进行空间扩展时,通过以下策略决定 free 的大小:

  • 当 SDS 修改后 len < 1MB,free 多分配一倍可用空间;
  • 当 SDS 修改后 len >= 1MB,free 多分配 1MB 可用空间。

例如有一个 SDS 对象 sdshdr,我们对其进行拼接操作:

sdshdr.len = 5;
sdshdr.free = 0;
sdshdr.buf = "Redis";
sdscat(sdshdr, " String");

执行后,sdshdr.buf 内容 'Redis String',其中 len 变为 12,free 变为 12,buf 总大小为 12+12+1 = 25,如果再次执行:

sdscat(sdshdr, " Test");

此时并不需要进行空间重新分配,因为预分配的多余空间足够存储新增字符串,有效降低了修改字符串时的内存重分配次数。

2. 惰性空间释放

当我们需要缩短 SDS 中的字符串长度时,buf 中的空间并不会被立即释放,而是会记录在 free 中,等待将来使用,同时 Redis 也提供了释放 SDS 空间的接口。

二进制安全

C 语言中的字符串遇到 '\0' 就会结束,但是 Redis 中所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在buf数组里的数据,程序不会对其中的数据做任何限制、过滤、或者假设,数据在写入时是什么样的,它被读取时就是什么样。 Redis 允许 SDS buf 中间存在 '\0',使用 len 而不是 '\0' 来判断字符串的结束,这使得 Redis 不仅可以保存文本数据,还可以保存任意格式的二进制数据,扩展了 Redis 字符串的使用场景。

兼容 C 语言部分字符串操作函数

SDS 结构指针直接指向 buf,所以可以兼容 C 语言的部分字符串操作函数。


Redis3.2 后的 SDS 结构

为了进一步节省空间,Redis3.2 后将 SDS 结构分为了 5 种类型,用于支持不同长度的字符串,对于长度小于 32 位的短字符串,使用如下结构存储:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

其中 flags 大小为 1 字节,低 3 位用于存储类型标识,高 5 位存储字符串长度。

对于长度大于 32 位的字符串,flags 高 5 位已经无法存储字符串长度,Redis 使用 len 存储已使用长度,alloc 存储字符串分配的总长度:

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[];
};

sdshdr8/sdshdr32/sdshdr64 的区别仅在与 len 和 alloc 的类型不同。使用 packed 对代码修饰后,结构体可按照 1 字节对齐,进一步节省空间,并统一结构体内各属性的访问方式。


参考资料:

  1. Redis 设计与实现 —— 黄建宏
  2. Redis 5 设计与源码分析 —— 陈雷