作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现(SDS)(二)

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现(SDS)

作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现(SDS)(一)https://developer.aliyun.com/article/1471143


原理剖析

简单动态字符串(SDS)Simple Dynamic String的缩写,它是Redis中用于表示字符串的核心数据结构。在Redis中,几乎所有的键(key)都是通过SDS来实现的,体现了其高效和灵活性。

从源码层面分析,SDS的实现细节主要集中在sds.hsds.c文件中。其中,sds.h定义了SDS的数据结构和相关操作接口,而sds.c则提供了这些接口的具体实现。此外,sdsalloc.h文件也扮演着重要角色,它负责SDS内存分配和释放的管理,确保SDS在动态扩展和收缩时能够高效、安全地使用内存。

通过深入分析sds.h头文件,我们可以发现Redis源码为char*类型定义了一个别名,如下所示:

c

复制代码

#ifndef __SDS_H
#define __SDS_H
#define SDS_MAX_PREALLOC (1024*1024)
extern const char *SDS_NOINIT;
#include <sys/types.h>
#include <stdarg.h>
#include <stdint.h>
typedef char *sds;

这种别名的使用在Redis的源代码中非常普遍,尤其是在处理字符串时。通过将char*重命名为sds,Redis不仅使代码更具可读性,还强调了这些指针实际上是指向动态字符串(SDS)的,而不仅仅是普通的C字符串。

数据结构

SDS是Redis用来表示字符串的核心数据结构,它提供了一种动态调整字符串长度的方式,同时还包含了一些额外的元数据,如字符串的长度和已分配的内存大小,还有一个名为flags的元数据字段,该字段的最低3位用于标识SDS的类型。

在SDS的设计中,为了节省内存并适应不同大小的字符串,Redis定义了五种不同大小的SDS头结构,分别是sdshdr5sdshdr8sdshdr16sdshdr32sdshdr64

这五种类型的主要区别在于它们如何存储和管理字符数组的两个关键元数据:现有长度(len)和分配空间长度(alloc)。这些元数据的数据类型因SDS类型的不同而有所区别。

以下是sds.h中定义的五种sdshdr结构,它们分别代表了五种不同的SDS数据结构模型:

sdshdr8sdshdr16sdshdr32sdshdr64这些头结构的大小分别为5字节、8字节、16字节、32字节和64字节。选择哪种头结构取决于字符串的实际长度和已分配的内存大小。

__attribute__((__packed__))是一个GCC编译器指令,用于确保结构体在内存中的布局是紧凑的,即没有额外的填充字节。这对于嵌入式系统或需要精确控制内存布局的场景非常有用。

分析结构体

接下来,我们将逐一深入剖析这些结构体。在结构模型的设计中,我们主要将其划分为两大类别:sdshdr5与其他类型。那么,为何要进行这样的分类呢?让我们来一探究竟。

sdshdr5(没有使用)

Redis的源码中并没有使用,因为它只包含一个flags字段和一个Buf字段,没有足够的空间来存储字符串的长度信息。

  • Flags字段的低3位用于表示SDS的类型(在这个情况下是5),而高5位被浪费了,没有使用。
  • Buf字段是字符数组,用于存储实际的字符串数据。
sdshdr8sdshdr16sdshdr32sdshdr64

sdshdr8sdshdr16sdshdr32sdshdr64这些结构体都包含LenAllocFlagsBuf字段。

  • Len字段表示当前字符串使用的长度(不包括末尾的空字符'\0')。
  • Alloc字段表示已分配的内存大小(不包括头信息和末尾的空字符'\0')。
  • Flags字段的低3位用于表示SDS的类型(8、16、32或64),而高5位没有被使用。
  • Buf字段是字符数组,用于存储实际的字符串数据。

注意,LenAlloc字段的大小会根据SDS头结构的大小而变化。在sdshdr8中,这两个字段都是uint8_t类型,而在sdshdr64中,这两个字段都是uint64_t类型。这种设计允许Redis根据字符串的实际大小动态地选择最合适的头结构,从而节省内存。

下面是一个底层存储案例,大家应该可以看到对应的存储模型是什么样子的。

特点分析
  • 空字符结尾:SDS遵循C字符串的传统做法,即在字符串末尾添加一个空字符(null terminator),以确保字符串的正确终止。这个空字符所占用的1字节空间并不计算在SDS的len属性中,这意味着对于SDS的使用者来说,这个空字符是完全不可见的。
  • 额外的分配:为了确保空字符的存在,SDS会自动为其分配额外的1字节空间,并在需要时在字符串末尾添加空字符。这些操作都是由SDS函数自动完成的,因此用户无需关心。
  • 兼容C方法:SDS可以直接使用C标准库中的头文件所提供的printf函数来展示其内部保存的字符串内容。录例如,通过执行printf("%s", s->buf);语句,可以方便地打印出SDS结构体中buf指针所指向的字符数组。
空字符结尾优点
  1. SDS能够直接重用C标准库中的一部分字符串函数,从而提高了代码的复用性和可维护性。
  2. 空字符的存在也有助于确保字符串的正确性和安全性,防止了越界访问等潜在问题。

特性对比

特征 C字符串 SDS
获取字符串长度的复杂度 O(n) O(1)
API安全性 不安全,可能会造成缓冲区溢出 安全,不会造成缓冲区溢出
内存重分配 修改字符串长度N次必然需要执行N次内存重分配 修改字符串长度N次最多需要执行N次内存重分配
数据类型 只能保存文本数据 可以保存文本或者二进制数据
使用的库函数 可以使用所有<string.h>库中的函数 可以使用一部分<string.h>库中的函数

数据长度分析

sdslen 函数通过解析 SDS 字符串的标志位和头结构来获取字符串的长度,并根据字符串的类型选择相应的计算方式。这种设计允许 Redis 使用不同大小的头结构来存储不同长度的字符串,从而节省内存空间。

c

复制代码

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

这段代码是 Redis 中用于获取 SDS(Simple Dynamic String,简单动态字符串)长度的函数 sdslen 的实现。SDS 是 Redis 用于表示字符串的内部数据结构,它包含了一个长度字段和一个预分配的空间字段,以便在需要时能够快速地扩展或收缩字符串。

分析代码

  1. 方法参数以及返回值
  • size_t:这是函数的返回类型,表示字符串的长度。
  • const sds s:这是函数的参数,s 是一个指向 SDS 字符串的指针。
  1. 获取标志位unsigned char flags = s[-1];* 这行代码从 SDS 字符串的末尾获取标志位。因为 SDS 字符串的实际数据存储在头结构之后,所以通过 s[-1] 可以访问到存储标志位的字节。
  2. 判断 SDS 类型并返回长度switch(flags&SDS_TYPE_MASK)*使用了一个位掩码 SDS_TYPE_MASK来提取标志位中的 SDS 类型信息。SDS_TYPE_MASK 的值通常是一个只有低三位设置为 1 的值(例如 0x07),这样可以将标志位中的类型字段提取出来。
  • switch 语句根据提取出来的类型字段的值来选择相应的代码分支,每个分支都返回相应类型 SDS 字符串的长度。
  • case SDS_TYPE_5:如果 SDS 类型是 5,则使用 SDS_TYPE_5_LEN(Flags) 来计算字符串的长度。这个宏通常会从标志位中提取出长度信息。
  • case SDS_TYPE_8case SDS_TYPE_16case SDS_TYPE_32case SDS_TYPE_64:对于其他类型的 SDS 字符串,通过调用 SDS_HDR(size, s) 宏来获取头结构的指针,然后返回头结构中的 len 字段的值,即字符串的实际长度。
  1. 默认返回值return 0;* 如果 switch 语句中没有匹配到任何类型,函数将返回 0。这通常表示输入的 s 不是一个有效的 SDS 字符串,或者它的类型字段的值不正确。

计算剩余容量

sdsavail 函数用于快速获取 SDS 字符串的剩余容量。该函数的实现基于 SDS 字符串的 alloc(总容量)和 len(已使用长度)字段。通过简单的数学运算 alloc - len,即可得到剩余容量。这种计算方式的时间复杂度为 O(1),意味着无论 SDS 字符串的长度如何,获取剩余容量的操作都是常数时间复杂度的,因此非常高效。

c

复制代码

static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

简而言之,sdsavail 函数提供了一种快速、简便的方法来查询 SDS 字符串当前剩余的可用空间,这对于需要动态调整字符串大小的应用来说非常有用。

至此,还有还有很多关于SDS源码的其他内容,由于篇幅过长,再次就不过多介绍,本次我们主要是将核心SDS的核心特细和原理以及结构,以及基本的核心方法进行介绍和说明,特别是针对于SDS和C字符串的区别和选择的问题,做了较为深入的介绍和分析。


作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现(SDS)(三)https://developer.aliyun.com/article/1471145

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
16天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
21天前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
54 8
|
21天前
|
存储 NoSQL 定位技术
Redis geo原理
Redis的GEO功能基于Earth Mapper(http://earth-api.org/)库,它允许存储地理位置信息并执行一些基于该信息的操作。
25 3
|
20天前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
1月前
|
消息中间件 存储 缓存
redis支持的数据结构
redis支持的数据结构
29 2
|
16天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
16天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
1月前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
70 6
|
4天前
|
缓存 NoSQL 关系型数据库
大厂面试高频:如何解决Redis缓存雪崩、缓存穿透、缓存并发等5大难题
本文详解缓存雪崩、缓存穿透、缓存并发及缓存预热等问题,提供高可用解决方案,帮助你在大厂面试和实际工作中应对这些常见并发场景。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:如何解决Redis缓存雪崩、缓存穿透、缓存并发等5大难题
|
5天前
|
存储 缓存 NoSQL
【赵渝强老师】基于Redis的旁路缓存架构
本文介绍了引入缓存后的系统架构,通过缓存可以提升访问性能、降低网络拥堵、减轻服务负载和增强可扩展性。文中提供了相关图片和视频讲解,并讨论了数据库读写分离、分库分表等方法来减轻数据库压力。同时,文章也指出了缓存可能带来的复杂度增加、成本提高和数据一致性问题。
【赵渝强老师】基于Redis的旁路缓存架构