Redis底层数据结构之SDS

news/2024/5/14 11:58:47

一、概述

Redis 中的 SDS（Simple Dynamic String，简单动态字符串）是 Redis 用于存储字符串值的底层实现，是对 C 语言传统字符串（以 null 结尾的字符数组）的改良，内部结构类似于 C 语言的字符数组，但额外存储了字符串长度和分配空间大小，避免了 C 字符串的缺陷。SDS 用于解决 C 字符串的一些限制和安全性问题, 具有动态扩容的特点. 其实现位于src/sds.h与src/sds.c中。SDS 除了保存数据库中的字符串值以外，SDS 还可以作为缓冲区（buffer）：包括 AOF 模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

二、SDS结构

struct sdshdr {uint32_t len;    //字符串长度uint32_t alloc;  //字符串空间大小unsigned char flags; //表示sds的类型（8位）char buf[];  //用于存储字符串数据
};

在这里插入图片描述

三、为什么使用SDS

长度灵活：
SDS 在内存中的表示包含了字符串的长度信息，因此它可以包含任意长度的数据，包括空字符(‘\0’)。这解决了 C 字符串无法存储空字符的问题。
快速获取长度：
由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。
防止缓冲区溢出：
在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求, 如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。
减少修改字符串时的内存重新分配次数：
C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。而对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：
- 空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。
  - 如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS len 属性的值将和 free 属性的值相同。举个例子，如果进行修改之后， SDS 的 len 将变成 13 字节，那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。
  - 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ，那么程序会分配 1 MB 的未使用空间。举个例子，如果进行修改之后， SDS 的 len 将变成 30 MB ，那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。
- 惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）
二进制安全：
SDS 可以存储任何二进制数据，包括图片、音频等非文本数据。这是因为 SDS 不依赖 null 字符来标识字符串的结束，而是以 len 属性表示的长度来判断字符串是否结束，因此数据中可以包含任意的二进制序列。
兼容部分 C 字符串函数：
尽管 SDS 是对 C 字符串的扩展，但它的存储布局确保了在以 \0 结尾处的内存地址上的内容可以被视为一个正常的 C 字符串，这意味着可以在不需要复制字符串的前提下，利用 C 的一些标准库函数来操作 SDS。