Redis源码学习：SDS设计与内存管理

为什么Redis选择SDS

1、缓解C语言字符串的缺陷

在 C 语言中可以使用 char* 字符数组来实现字符串。每个字符串分配一段连续的内存空间，依次存放字符串中的每一个字符，最后以null字符结尾。这种设计存在以下问题：
image.png

1、低效的操作
每次获取字符串长度都需要遍历字符串，找到null字符的位置，时间复杂度为O(n)。

2、二进制不安全
C字符串不能存储二进制数据，假如要存储的二进制图片中包含了null字符，会把它看做是字符串的结尾，出现错误。

3、缓冲区溢出
字符串操作（如拼接、复制）容易导致缓冲区溢出，进而引发安全问题。

2、提升性能和灵活性

SDS设计解决了传统C字符串存在的问题,提供了更高效、更安全的字符串操作能力,主要体现在以下几个方面:

1) 获取字符串长度的高效性

传统的C字符串需要线性遍历来获取长度,时间复杂度为O(n)。而SDS在结构体中维护了len字段,可以在常数时间O(1)内直接获取字符串长度,大大提升了效率。

2) 防止缓冲区溢出的安全性

C字符串在拼接、复制等操作时,很容易出现缓冲区溢出的问题,从而导致安全隐患。SDS则通过动态分配内存的方式,在字符串操作时自动调整内存大小,从根本上避免了缓冲区溢出。

3) 存储二进制数据的灵活性

传统C字符串由于使用null字符作为结尾标记,无法安全地存储包含null字符的二进制数据。而SDS则完全绕过了这一限制,可以方便地存储任意二进制数据,提高了数据存储的灵活性。

4) 空间预分配的优化

在对SDS进行扩展时,SDS会预先分配更大的内存空间,减少了频繁重新分配内存所带来的性能开销。当字符串长度小于1MB时,扩容后的空间是原长度的两倍;当长度超过1MB时,则会额外分配1MB的空间,防止过度使用内存。

SDS结构

在Redis源码中，SDS结构源码（位于sds.h文件）如下：

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

定义了sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64多种结构，sdshdr5不再使用无需关注。每一个SDS结构都包含了实际存储字符串的字符数组buf[]，记录当前字符串的长度len、记录分配的总空间alloc（不包括头部和空终止符） 和 SDS类型flags。

它们的主要区别就在于，数据结构中的字符数组现有长度 len 和分配空间长度 alloc，这两个元数据的数据类型不同。uint8_t 是 8 位无符号整型，会占用 1 字节的内存空间。当字符串类型是sdshdr8时，它表示字符数组buf[]长度（包括数组最后一位\0）不会超过 256 字节（2 的 8 次方等于 256）。uint16_t、uint32_t、uint64_t，分别表示不超过 2 的 16 次方、32 次方和 64 次方。这两个元数据各自占用的内存空间在 sdshdr16、sdshdr32、sdshdr64 类型中，则分别是 2 字节、4 字节和 8 字节。

在SDS结构的定义上还使用了__attribute__ ((__packed__))，来优化空间，它的作用就是告诉编译器，在编译结构时，不要使用字节对齐的方式，而是采用紧凑的方式分配内存。

image.png

SDS的内存分配过程

SDS的内存分配包括创建、扩展和释放三个主要过程。以下是SDS的内存管理源码分析。

1、SDS创建

SDS的创建函数是sdsnewlen。

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}
1.1 确定类型和头部大小

首先，通过sdsReqType函数确定适合的SDS类型，然后计算头部大小。sdsReqType根据字符串长度选择合适的SDS类型，而sdsHdrSize返回相应类型的头部大小。

char type = sdsReqType(initlen);
int hdrlen = sdsHdrSize(type);
1.2. 分配内存

接着，通过s_trymalloc_usable或s_malloc_usable函数分配内存，这里&usable会返回实际可用的内存大小。

sh = trymalloc?
	s_trymalloc_usable(hdrlen+initlen+1, &usable) :
	s_malloc_usable(hdrlen+initlen+1, &usable);
1.3. 初始化内存

根据init参数的不同，初始化内存。

if (init==SDS_NOINIT)
	init = NULL;
else if (!init)
	memset(sh, 0, hdrlen+initlen+1);
1.4. 设置类型和长度

最后，设置SDS的类型标志和长度，并返回字符串的指针。s表示是SDS中buf[]的起始位置，len表示使用空间，alloc表示分配的空用空间。

s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;

2、SDS扩容

SDS的扩展函数是sdsMakeRoomFor。

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }

    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}
2.1 计算可用空间

首先，计算当前字符串的可用空间和长度。

size_t avail = sdsavail(s);
size_t len = sdslen(s);
2.2 计算新长度

如果可用空间不足，则需要扩展。新长度通常是当前长度的两倍，以减少频繁的内存分配操作。SDS_MAX_PREALLOC是1M的大小，扩容后新空间的大小有两种情况：

  • 如果新长度小于1M，则新空间为扩容后字符串长度的两倍+1
  • 否则，则新空间为扩容后字符串长度+1M+1
    后面的+1是调用内存分配函数是添加的。
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;
2.3. 分配新内存

根据新长度分配内存。如果新的类型与旧的类型相同，直接使用s_realloc_usable重新分配内存，否则需要创建新的SDS，重新分配内存拷贝数据。

type = sdsReqType(newlen);
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
	newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
	if (newsh == NULL) return NULL;
	s = (char*)newsh+hdrlen;
} else {
	newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
	if (newsh == NULL) return NULL;
	memcpy((char*)newsh+hdrlen, s, len+1);
	s_free(sh);
	s = (char*)newsh+hdrlen;
	s[-1] = type;
	sdssetlen(s, len);
}
2.4. 更新长度

最后，更新分配的总空间，并返回扩展后的SDS。

sdssetalloc(s, usable);
return s;

3、SDS的释放

SDS的释放函数是sdsfree。

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}
3.1. 检查空指针

首先，检查传入的指针是否为空。

if (s == NULL) return;
3.2. 释放内存

通过s_free函数释放内存，注意需要将指针偏移到SDS头部的位置。

s_free((char*)s-sdsHdrSize(s[-1]));

总结

Redis使用简单动态字符串SDS来代替传统C字符串,解决了获取长度低效、缓冲区溢出和二进制不安全等问题。SDS在结构体中维护长度,支持二进制存储,自动扩容防止溢出,性能和灵活性均有提升。文中详细分析了SDS的内存分配、扩容和释放过程。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/743833.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【containerd】Containerd高阶命令行工具nerdctl

【containerd】Containerd高阶命令行工具nerdctl

前言 对于习惯了使用docker cli的用户来说&#xff0c;containerd的命令行工具ctr使用起来不是很顺手&#xff0c;此时别慌&#xff0c;还有另外一个命令行工具项目nerdctl可供我们选择。 nerdctl是一个与docker cli风格兼容的containerd的cli工具。 nerdctl已经作为子项目加入…
阅读更多...
数据分析必备：一步步教你如何用matplotlib做数据可视化（12）

数据分析必备：一步步教你如何用matplotlib做数据可视化（12）

1、Matplotlib 3D线框图 线框图采用值网格并将其投影到指定的三维表面上&#xff0c;并且可以使得到的三维形式非常容易可视化。plot_wireframe()函数用于此目的 import matplotlib.pyplot as plt import numpy as np import math import seaborn as sns plt.rcParams[font.s…
阅读更多...
新增题目接口开发

新增题目接口开发

文章目录 1.基本设计2.生成CRUD代码1.生成五张表的代码1.subject_info2.subject_brief3.subject_judge4.subject_multiple5.subject_radio 2.将所有的dao放到mapper文件夹3.将所有实体类使用lombok简化4.删除所有mapper的Param("pageable") Pageable pageable5.删除所…
阅读更多...
nacos 整合 openfeign实现远程调用

nacos 整合 openfeign实现远程调用

结合之前写过的案例 Springcloud Alibaba nacos简单使用 Springcloud 之 eureka注册中心加feign调用 在微服务架构中&#xff0c;服务注册与发现是一个关键组件。Nacos 是一个开源的服务注册与发现、配置管理平台&#xff0c;而 OpenFeign 是一个声明式的 Web 服务客户端&am…
阅读更多...
6.25作业

6.25作业

1.整理思维导图 2.终端输入两个数&#xff0c;判断两数是否相等&#xff0c;如果不相等&#xff0c;判断大小关系 #!/bin/bash read num1 read num2 if [ $num1 -eq $num2 ] then echo num1num2 elif [ $num1 -gt $num2 ] then echo "num1>num2" else echo &quo…
阅读更多...
优雅谈大模型13：LangChain Vs. LlamaIndex

优雅谈大模型13：LangChain Vs. LlamaIndex

实时了解业内动态&#xff0c;论文是最好的桥梁&#xff0c;专栏精选论文重点解读热点论文&#xff0c;围绕着行业实践和工程量产。若在某个环节出现卡点&#xff0c;可以回到大模型必备腔调或者LLM背后的基础模型重新阅读。而最新科技&#xff08;Mamba,xLSTM,KAN&#xff09;…
阅读更多...
09. Java ThreadLocal 的使用

09. Java ThreadLocal 的使用

1. 前言 本节内容主要是对 ThreadLocal 进行深入的讲解&#xff0c;具体内容点如下&#xff1a; 了解 ThreadLocal 的诞生&#xff0c;以及总体概括&#xff0c;是学习本节知识的基础&#xff1b;了解 ThreadLocal 的作用&#xff0c;从整体层面理解 ThreadLocal 的程序作用&…
阅读更多...
Vue3基础使用

Vue3基础使用

目录 一、创建Vue3工程 (一)、cli (二)、vite 二、常用Composition API (一)、setup函数 (二)、ref函数 (三)、reactive函数 (四)、setup注意事项 (五)、计算属性 (六)、watch (七)、watchEffect函数 (八)、生命周期 1、以配置项的形式使用生命周期钩子 2、组合式…
阅读更多...
功能测试【测试用例模板、Bug模板、手机App测试★】

功能测试【测试用例模板、Bug模板、手机App测试★】

功能测试 Day01 web项目环境与测试流程、业务流程测试一、【了解】web项目环境说明1.1 环境的定义&#xff1a;项目运行所需要的所有的软件和硬件组合1.2 环境(服务器)的组成&#xff1a;操作系统数据库web应用程序项目代码1.3 面试题&#xff1a;你们公司有几套环境&#xff1…
阅读更多...
昇思25天学习打卡营第2天|快速入门

昇思25天学习打卡营第2天|快速入门

快速入门 操作步骤1.引入依赖包2.下载Mnist数据集3.划分训练集和测试集4.数据预处理5.网络构建6.模型训练7.保存模型8.加载模型9.模型预测 今天通过昇思大模型平台AI实验室提供的在线Jupyter工具&#xff0c;快速入门MindSpore。 目标&#xff1a;通过MindSpore的API快速实现一…
阅读更多...
互联网应用主流框架整合之Spring Boot运维体系

互联网应用主流框架整合之Spring Boot运维体系

先准备个简单的系统&#xff0c;配置和代码如下 # 服务器配置 server:# 服务器端口port: 8001# Spring Boot 配置 spring:# MVC 配置mvc:# Servlet 配置servlet:# Servlet 的访问路径path: /sbd# 应用程序配置application:# 应用程序名称name: SpringBootDeployment# 配置数据…
阅读更多...
PointCloudLib NDT3D算法实现点云配准 C++版本

PointCloudLib NDT3D算法实现点云配准 C++版本

0.实现效果 效果不咋好 ，参数不好调整 1.算法原理 3D NDT（Normal Distributions Transform）算法是一种用于同时定位和地图生成（SLAM）的机器人导航算法，特别适用于三维点云数据的配准。以下是关于3D NDT算法的详细解释： 算法原理 点云划分与分布计算：3D NDT算法首先将…
阅读更多...
ElementPlus组件与图标按需自动引入

ElementPlus组件与图标按需自动引入

按需自动引入组件 1. 安装ElementPlus和自动导入ElementPlus组件的插件 pnpm install element-plus pnpm install -D unplugin-vue-components unplugin-auto-import 2. vite.config.ts进行修改 import { defineConfig } from vite import vue from vitejs/plugin-vue // …
阅读更多...
MySQL索引优化解决方案--索引失效(3)

MySQL索引优化解决方案--索引失效(3)

索引失效情况 最佳左前缀法则&#xff1a;如果索引了多列&#xff0c;要遵循最左前缀法则&#xff0c;指的是查询从索引的最左前列开始并且不跳过索引中的列。不在索引列上做任何计算、函数操作&#xff0c;会导致索引失效而转向全表扫描存储引擎不能使用索引中范围条件右边的…
阅读更多...
Windows 根据github上的环境需求，安装一个虚拟环境，安装cuda和torch

Windows 根据github上的环境需求，安装一个虚拟环境，安装cuda和torch

比如我们在github上看到一个关于运行环境的需求 Installation xxx系统Python 3.xxx CUDA 9.2PyTorch 1.9.0xxxxxx 最主要的就是cuda和torch&#xff0c;这两个会卡很多环境的安装。 我们重新走一遍环境安装。 首先创建一个虚拟环境 conda create -n 环境名字 python3.xxx…
阅读更多...
Tomcat 下载部署到 idea

Tomcat 下载部署到 idea

一、下载Tomcat Tomcat 是Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;下的一个核心项目&#xff0c;免费开源、并支持Servlet 和JSP 规范。属于轻量级应用服务器&#xff0c;在中小型系统和并发访问用户不是很多的场合下被普遍使用&#xff0c;是开发…
阅读更多...
【Text2SQL 论文】MAGIC：为 Text2SQL 任务自动生成 self-correction guideline

【Text2SQL 论文】MAGIC：为 Text2SQL 任务自动生成 self-correction guideline

论文&#xff1a;MAGIC: Generating Self-Correction Guideline for In-Context Text-to-SQL ⭐⭐⭐ 莱顿大学 & Microsoft, arXiv:2406.12692 一、论文速读 DIN-SQL 模型中使用了一个 self-correction 模块&#xff0c;他把 LLM 直接生成的 SQL 带上一些 guidelines 的 p…
阅读更多...
计算机组成原理课程设计报告

计算机组成原理课程设计报告

有关计算机组成原理课程设计报告如下题材&#xff0c;其包含报告和代码 16位ALU设计 动态LED动态显示屏设计 海明码编码设计编码流水传输 单周期MIPS控制器设计 阵列乘法器设计 Cache映射机制与逻辑实现 我们以6x6位阵列乘法器设计的报告为例为大家讲述一下我们这次的课程设计 …
阅读更多...
网络爬虫Xpath开发工具的使用

网络爬虫Xpath开发工具的使用

开发人员在编写网络爬虫程序时若遇到解析网页数据的问题&#xff0c;则需要花费大量的时间编 写与测试路径表达式&#xff0c;以确认是否可以解析出所需要的数据。为帮助开发人员在网页上直接 测试路径表达式是否正确&#xff0c;我们在这里推荐一款比较好用的 XPath 开发工…
阅读更多...
关于关闭防火墙后docker启动不了容器

关于关闭防火墙后docker启动不了容器

做项目的时候遇到个怪事&#xff0c;在Java客户端没办法操作redis集群。反复检查了是否运行&#xff0c;端口等一系列细节的操作&#xff0c;结果都不行。 根据提示可能是Linux的防火墙原因。于是去linux关闭了防火墙。 关闭后果不其然 可以操作reids了&#xff0c;可是没想到另…
阅读更多...
最新文章

Copyright @ 2022~2023