自学内容网 自学内容网
自学内容网 > 正文

Redis底层数据结构之SDS

🕗 发布于 2024-04-28 16:48 redis  数据结构  数据库  SDS  

目录

redis底层数据结构已完结👏👏👏：

一、概述

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

  1. 长度灵活：
    SDS 在内存中的表示包含了字符串的长度信息，因此它可以包含任意长度的数据，包括空字符(‘\0’)。这解决了 C 字符串无法存储空字符的问题。

  2. 快速获取长度：
    由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。

  3. 防止缓冲区溢出：
    在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求, 如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。

  4. 减少修改字符串时的内存重新分配次数：
    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，当我们有需要时，也可以手动释放这些未使用的空间。）

  5. 二进制安全：
    SDS 可以存储任何二进制数据，包括图片、音频等非文本数据。这是因为 SDS 不依赖 null 字符来标识字符串的结束，而是以 len 属性表示的长度来判断字符串是否结束，因此数据中可以包含任意的二进制序列。

  6. 兼容部分 C 字符串函数：
    尽管 SDS 是对 C 字符串的扩展，但它的存储布局确保了在以 \0 结尾处的内存地址上的内容可以被视为一个正常的 C 字符串，这意味着可以在不需要复制字符串的前提下，利用 C 的一些标准库函数来操作 SDS。


原文地址：https://blog.csdn.net/xiong_tai/article/details/138042674

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024