redis源码分析，SDS动态字符串

2024-01-06 23:48
文章标签 分析 动态 源码 redis 字符串 sds

本文主要是介绍redis源码分析，SDS动态字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

redis源码分析，SDS动态字符串

SDS [basic redis v6.0]，源码路径: src/sds.c, src/sds.h, src/sdsalloc.h
redis中的字符串类型为SDS（C dynamic strings）是一个动态类型字符串。 可以无限增长，理论上长度最大2^64

下面是redis中 SDS的结构

struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* buf已用长度 */uint32_t alloc; /* buf逻辑上预留长度，不包括结构体头部字段所占内存长度，并且不包含buf结尾的\0字符 */unsigned char flags; /* 字符串类型, 也表示了字符串的最长长度，可以动态增长 */char buf[]; /* 实际存储字符串的空间 */
};
  • 其中 attribute ((packed)) 告诉编译器取消在编译过程中的内存对齐。关于内存对齐，网上有详细文章。
  • uint32_t len; 其中uint32_t是typedef定义的。 还有uint8_t, uint16_t, uint32_t, uint64_t。实际的定义取决于编译器，具体如下
// Visual Studio 6 and Embedded Visual C++ 4 doesn't
// realize that, e.g. char has the same size as __int8
// so we give up on __intX for them.
#if (_MSC_VER < 1300)typedef signed char       int8_t;typedef signed short      int16_t;typedef signed int        int32_t;typedef unsigned char     uint8_t;typedef unsigned short    uint16_t;typedef unsigned int      uint32_t;
#elsetypedef signed __int8     int8_t;typedef signed __int16    int16_t;typedef signed __int32    int32_t;typedef unsigned __int8   uint8_t;typedef unsigned __int16  uint16_t;typedef unsigned __int32  uint32_t;
#endif
typedef signed __int64       int64_t;
typedef unsigned __int64     uint64_t;
  • char buf[]; 属性为实际存储字符串的字符数组。具体长度取决于flags。也是sdshdr的类型
  • uint32_t len; 属性buf已经使用的字节长度，也就想到与strlen(len)。和多数stl数据结构实现一样，因为strlen(len)时间复杂度为O(n),所以存储len，可以达到O(1)的时间取长度。
  • uintew_t alloc; 为buf逻辑预留空间，不包含\0字符。其实alloc不一定等于实际的sizeof(buf)/sizeof(char)，因为buf为实际的预留空间,初始化时候len, alloc, sizeof(buf)/sizeof(char)均为字符串长度+1, 基本没有浪费内存. 而如果增长的化, buf长度一定是28,216,232,264(需要再减去结构体头部空间和\0字符)，而alloc也是预留空间长度，当字符串增长时，假设alloc小于增长后的len，那么alloc会增长，当alloc增长后的值大于2^flags时，结构体会重新构造，当然并不是真正构造结构体，只是操作内存函数重新分配了更大的一块空间，再进行内存拷贝。所以alloc值介于len和sizeof(buf)/sizeof(char)之间
  • unsigned char flags; 为字符串的类型，有如下几个值，也就是整个结构体所占内存空间，初始化后所占内存为strlen(buf)+1, 而增长的话, 近似2^flags大小.
    /** #define SDS_TYPE_5  0* #define SDS_TYPE_8  1 // 对应长度为0 ~ 2^8-1, 假设字符串增长了的话, 那么结构体所占内存总是2^8大小* #define SDS_TYPE_16 2* #define SDS_TYPE_32 3* #define SDS_TYPE_64 4*/

下面来看一下redis对sds的内存初始化，即memory allocate

// 为了节省代码空间，假设分配的是32位的字符类型

sds sdsnewlen(const void *init, size_t initlen) {void *sh;sds s;char type = sdsReqType(initlen);    // if (initlen < 1<<32) {return SDS_TYPE_32}, 返回能满足所需的最小长度/* 不使用type 5，最少使用type8 */if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;int hdrlen = sdsHdrSize(type);      // return sizeof(struct sdshdr32)， 即结构体头部字段所占用内存（buf为空数组的时候）unsigned char *fp;                  /* 指向flags字段 */assert(initlen + hdrlen + 1 > initlen); /* 判断整数溢出 */sh = s_malloc(hdrlen+initlen+1);    // 分配了结构体头部字段所占长度 + buf长度 + 空字符长度if (sh == NULL) return NULL; if (init==SDS_NOINIT)init = NULL;else if (!init)memset(sh, 0, hdrlen+initlen+1);s = (char*)sh+hdrlen;           // buf字段 内存开始位置fp = ((unsigned char*)s)-1;     // flags字段 内存所在位置switch(type) {case SDS_TYPE_5: {*fp = type | (initlen << SDS_TYPE_BITS);break;}case SDS_TYPE_8:  // { 和SDS_TYPE_32一样;  break;}case SDS_TYPE_16: // { 和SDS_TYPE_32一样;  break;}case SDS_TYPE_32: {SDS_HDR_VAR(32,s); // #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); 即将指向buf的s指针 反序列化为结构体指针，同时赋值到shsh->len = initlen; // 因为空字符串, 所以len == alloc，若buf = ['a', 'b', 0, 0 ,0 ,0, ... ]sh->alloc = initlen;*fp = type;break;}case SDS_TYPE_64: // { 和SDS_TYPE_32一样;  break;}}if (initlen && init)memcpy(s, init, initlen);// 返回的是char*指针， typedef char* sdss[initlen] = '\0';return s;
}
  • 可以看到，redis是直接把整个结构体的内存申请出来，然后操作指针，访问结构体的每一个变量，因为指定了编译器不会对内存进行优化，所以指针的前后移动可以直接访问到每一个属性，而直接返回buf位置的指针，可以让使用者达到和char []同样的使用效果，其实在物理上还是实现上也确实没太大区别
  • s_malloc()的空间基本等于字符数组长度, 所以初始化时几乎没有内存浪费
  • 关于指针的移动访问变量，我写了一个示例代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>struct __attribute__ ((__packed__)) Test {char a;int b;long long c;int* d;
};int main () {void* tp = malloc(sizeof(struct Test));// 初始化内存值均为0memset(tp, 0, sizeof(struct Test));// 将内存序列化为结构struct Test* t = (struct Test*)(tp);// 赋值属性t->a = 'a';t->b = 1;t->c = 2;t->d = &(t->b);// 通过指针移动访问属性printf("a:%c\n", *(char*)tp);tp += sizeof(char);printf("b:%d\n", *(int*)tp);tp += sizeof(int);printf("b:%lld\n", *(long long*)tp);tp += sizeof(long long);printf("b:%d\n", *(*(int**)tp));return 0;
}

实现更新len属性的函数

void sdsupdatelen(sds s) {size_t reallen = strlen(s);sdssetlen(s, reallen);
}

为什么会有这个函数？
因为当s = [‘a’, ‘b’, ‘c’, ‘\0’, 0, …]时
操作 s[2] = ‘\0’;
现在sdslen(s)时，结果是3， 因为sdslen(s)是调用SDS_HDR(32, s) > ->len,但是len字段没有被更新。
但是实际的长度是strlen(s) ==> 2， 所以需要调用sdsupdatelen() > 函数更新len值。
那为什么要用sdslen(s)而不直接用strlen(s)测字符串长度呢？
因为sdslen因为直接取len值，所以时间复杂度为O(1)，而strlen需要 > 遍历字符串数组，直到找到\0字符，所以时间复杂度为O(n)

动态增长实现

// 预留空间
sds sdsMakeRoomFor(sds s, size_t addlen) {void *sh, *newsh;size_t avail = sdsavail(s); // return alloc - lensize_t len, newlen;char type, oldtype = s[-1] & SDS_TYPE_MASK;int hdrlen;if (avail >= addlen) return s; // (alloc - len) > addlen，可用空间大于所需要空间len = sdslen(s);sh = (char*)s-sdsHdrSize(oldtype);newlen = (len+addlen);assert(newlen > len);   /* Catch size_t overflow */if (newlen < SDS_MAX_PREALLOC)newlen *= 2;elsenewlen += SDS_MAX_PREALLOC;type = sdsReqType(newlen); // 增长后的类型。假设原来是SDS_TYPE_8, 增长后长度大于2^8，所以type变为SDS_TYPE_16，若仍然小于2^8,则type 仍为SDS_TYPE_8if (type == SDS_TYPE_5) type = SDS_TYPE_8;hdrlen = sdsHdrSize(type);assert(hdrlen + newlen + 1 > len);  /* Catch size_t overflow */if (oldtype==type) {//因为结构体头部字段除了buf外长度并未改变,所以直接realloc即可newsh = s_realloc(sh, hdrlen+newlen+1);if (newsh == NULL) return NULL;s = (char*)newsh+hdrlen;} else {/* 上面的realloc实际也是进行空间判断，如果后面可用内存空间可以满足需求，则直接增长，返回空间，如果已被利用，则进行malloc在memcpy， 那么这里为什么不直接调用realloc呢？ 因为结构体头部len和alloc所占的空间变了， 即hdrlen变了，所以需要memcpy在拷贝过程中同时移动buf位置*/newsh = s_malloc(hdrlen+newlen+1);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);}sdssetalloc(s, newlen);return s;
}
  • 可以看到当oldtype==type时, 调用了realloc, 因为除了位于结构体内存末尾的buf, 其他字段长度并未改变.
  • 而oldtype!=type时, 执行了malloc和memcpy, 基本等同于cpp 的new struct的内存构造过程
// append实现
sds sdscatlen(sds s, const void *t, size_t len) {size_t curlen = sdslen(s);s = sdsMakeRoomFor(s,len);  // 预留空间if (s == NULL) return NULL;memcpy(s+curlen, t, len);   // append到预留的空间sdssetlen(s, curlen+len);   // 重新设置lens[curlen+len] = '\0';       // 增加\0return s;
}sds sdscat(sds s, const char *t) {return sdscatlen(s, t, strlen(t));
}

这篇关于redis源码分析，SDS动态字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/578029。

相关文章

详谈redis跟数据库的数据同步问题

详谈redis跟数据库的数据同步问题

《详谈redis跟数据库的数据同步问题》文章讨论了在Redis和数据库数据一致性问题上的解决方案,主要比较了先更新Redis缓存再更新数据库和先更新数据库再更新Redis缓存两种方案,文章指出,删除R... 目录一、Redis 数据库数据一致性的解决方案1.1、更新Redis缓存、删除Redis缓存的区别二
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
Redis与缓存解读

Redis与缓存解读

《Redis与缓存解读》文章介绍了Redis作为缓存层的优势和缺点,并分析了六种缓存更新策略,包括超时剔除、先删缓存再更新数据库、旁路缓存、先更新数据库再删缓存、先更新数据库再更新缓存、读写穿透和异步... 目录缓存缓存优缺点缓存更新策略超时剔除先删缓存再更新数据库旁路缓存(先更新数据库，再删缓存）先更新数
阅读更多...
Redis事务与数据持久化方式

Redis事务与数据持久化方式

《Redis事务与数据持久化方式》该文档主要介绍了Redis事务和持久化机制,事务通过将多个命令打包执行,而持久化则通过快照（RDB）和追加式文件（AOF）两种方式将内存数据保存到磁盘,以防止数据丢失... 目录一、Redis 事务1.1 事务本质1.2 数据库事务与redis事务1.2.1 数据库事务1.
阅读更多...
mac安装redis全过程

mac安装redis全过程

《mac安装redis全过程》文章内容主要介绍了如何从官网下载指定版本的Redis,以及如何在自定义目录下安装和启动Redis,还提到了如何修改Redis的密码和配置文件,以及使用RedisInsig... 目录MAC安装Redis安装启动redis 配置redis 常用命令总结mac安装redis官网下
阅读更多...
Java汇编源码如何查看环境搭建

Java汇编源码如何查看环境搭建

《Java汇编源码如何查看环境搭建》：本文主要介绍如何在IntelliJIDEA开发环境中搭建字节码和汇编环境,以便更好地进行代码调优和JVM学习,首先,介绍了如何配置IntelliJIDEA以方... 目录一、简介二、在IDEA开发环境中搭建汇编环境2.1 在IDEA中搭建字节码查看环境2.1.1 搭建步
阅读更多...
Redis主从复制实现原理分析

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实
阅读更多...
SpringBoot使用注解集成Redis缓存的示例代码

SpringBoot使用注解集成Redis缓存的示例代码

《SpringBoot使用注解集成Redis缓存的示例代码》：本文主要介绍在SpringBoot中使用注解集成Redis缓存的步骤,包括添加依赖、创建相关配置类、需要缓存数据的类（Tes... 目录一、创建 Caching 配置类二、创建需要缓存数据的类三、测试方法Spring Boot 熟悉后，集成一个外
阅读更多...
Redis分布式锁使用及说明

Redis分布式锁使用及说明

《Redis分布式锁使用及说明》本文总结了Redis和Zookeeper在高可用性和高一致性场景下的应用,并详细介绍了Redis的分布式锁实现方式,包括使用Lua脚本和续期机制,最后,提到了RedLo... 目录Redis分布式锁加锁方式怎么会解错锁？举个小案例吧解锁方式续期总结Redis分布式锁如果追求
阅读更多...
Redis的Hash类型及相关命令小结

Redis的Hash类型及相关命令小结

《Redis的Hash类型及相关命令小结》edisHash是一种数据结构,用于存储字段和值的映射关系,本文就来介绍一下Redis的Hash类型及相关命令小结,具有一定的参考价值,感兴趣的可以了解一下... 目录HSETHGETHEXISTSHDELHKEYSHVALSHGETALLHMGETHLENHSET
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2