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

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

【专栏简介】

随着数据需求的迅猛增长,持久化和数据查询技术的重要性日益凸显。关系型数据库已不再是唯一选择,数据的处理方式正变得日益多样化。在众多新兴的解决方案与工具中,Redis凭借其独特的优势脱颖而出。

【技术大纲】

为何Redis备受瞩目?原因在于其学习曲线平缓,短时间内便能对Redis有初步了解。同时,Redis在处理特定问题时展现出卓越的通用性,专注于其擅长的领域。深入了解Redis后,您将能够明确哪些任务适合由Redis承担,哪些则不适宜。这一经验对开发人员来说是一笔宝贵的财富。

在这个专栏中,我们将专注于Redis的6.2版本进行深入分析和介绍。Redis 6.2不仅是我个人特别偏爱的一个版本,而且在实际应用中也被广泛认为是稳定性和性能表现都相当出色的版本

【专栏目标】

本专栏深入浅出地传授Redis的基础知识,旨在助力读者掌握其核心概念与技能。深入剖析了Redis的大多数功能以及全部多机功能的实现原理,详细展示了这些功能的核心数据结构和关键算法思想。读者将能够快速且有效地理解Redis的内部构造和运作机制,这些知识将助力读者更好地运用Redis,提升其使用效率。

将聚焦于Redis的五大数据结构,深入剖析各种数据建模方法,并分享关键的管理细节与调试技巧。

【目标人群】

Redis技术进阶之路专栏:目标人群与受众对象,对于希望深入了解Redis实现原理底层细节的人群

1. Redis爱好者与社区成员

Redis技术有浓厚兴趣,经常参与社区讨论,希望深入研究Redis内部机制、性能优化和扩展性的读者。

2. 后端开发和系统架构师

在日常工作中经常使用Redis作为数据存储和缓存工具,他们在项目中需要利用Redis进行数据存储、缓存、消息队列等操作时,此专栏将为他们提供有力的技术支撑。

3. 计算机专业的本科生及研究生

对于学习计算机科学、软件工程、数据分析等相关专业的在校学生,以及对Redis技术感兴趣的教育工作者,此专栏可以作为他们的学习资料和教学参考。

无论是初学者还是资深专家,无论是从业者还是学生,只要对Redis技术感兴趣并希望深入了解其原理和实践,都是此专栏的目标人群和受众对象

让我们携手踏上学习Redis的旅程,探索其无尽的可能性!


SDS(简单动态字符串)

Redis没有采纳C语言传统的字符串表示方式,而是选择了一种独特而高效的方法,构建了一个名为简单动态字符串的抽象类型,并将其确立为自己的默认字符串实现。再深入分析SDS核心结构以及原理之前,我们认识一下C语言的字符串,分析一下为什么Redis不采用它?

C字符串

在C语言中,字符串的实现通常依赖于函数的形式。开发者可以使用char*字符数组来表示和操作字符串。为了简化字符串处理任务,C语言标准库提供了string.h头文件,其中定义了一系列字符串操作函数,如字符串连接、比较、查找、复制等。

C字符串存在的问题

字符串存储局限性

C语言使用长度为N+1的字符数组来存储长度为N的字符串。这种设计是为了确保字符串的最后一个元素始终是一个空字符('\0'),即ASCII码值为0的字符。它不仅是字符串结束的标记,还确保了字符串操作的安全性,防止了诸如越界访问等潜在问题,如下图所示:

由于C字符串的字符必须遵循特定的编码标准,如ASCII,并且在其内部结构中,除了字符串的自然终止点外,不允许出现空字符。这是因为C字符串的长度是通过遍历字符直至遇到空字符来确定的,如果在字符串中间出现空字符,程序会错误地将其当作字符串的结束,从而截断后续的数据。这一限制使得C字符串只能用来存储纯文本数据,而无法有效地处理二进制数据,如图片、音频、视频或压缩文件等。

不存储字符串长度信息

C语言中的字符串不直接存储其长度信息,要获取一个C字符串的长度,程序必须通过遍历整个字符串来逐一计数其中的字符。这个过程涉及从字符串的起始位置开始,逐个检查每个字符,直到遇到表示字符串终止的空字符('\0')为止。

操作C字符串的时间复杂度
  • 使用char*来操作字符串时,获取字符串长度的操作通常需要遍历整个字符串,因此其时间复杂度为O(N),其中N表示字符串的长度。
  • 当需要在字符串末尾追加内容时,也需要遍历整个字符串以找到其末尾位置,这个操作的时间复杂度也是O(N)。
案例说明

我们使用一个案例分析一下计算C字符串长度时的处理过程。传统上,C字符串的长度需要通过遍历整个字符串来逐个字符计数,直到遇到空字符作为字符串结束的标记。

上图展示了C语言程序在计算字符串长度时的处理过程。传统上,C字符串的长度需要通过遍历整个字符串来逐个字符计数。

引发的性能瓶颈

由于每个字符都需要被检查一次,这个操作的复杂度为O(n),其中n是字符串的长度。这意味着,随着字符串长度的增加,计算长度所需的时间也线性增长。因此,对于较长的字符串,这种计算方式可能会成为性能瓶颈,需要开发者在算法设计和性能优化时予以考虑。

出现缓冲区溢出问题

除了其获取字符串长度的复杂度较高之外,C字符串不记录自身长度还带来了一个关键的问题,即容易导致缓冲区溢出(buffer overflow)。缓冲区溢出是一种常见的安全漏洞,它发生在当程序试图将数据写入一个固定大小的缓冲区,而该数据的大小超过了缓冲区所能容纳的界限时。

strcat拼接引发缓冲区溢出

C标准库中的strcat函数为例,该函数用于将src字符串的内容拼接到dest字符串的末尾。如果dest字符串的缓冲区没有足够的空间来容纳src字符串的内容,就会发生缓冲区溢出。这种溢出可能导致程序崩溃,更糟糕的是,它还可能被恶意利用来执行任意代码,从而构成严重的安全威胁。

c

复制代码

char *strcat (char dest,const char *src);

考虑一个场景,在程序中存在两个紧密相邻的C字符串s1和s2,分别存储了字符串"hello"和"world",如下图所示。 在这个例子中,s1和s2在内存中紧密相连,这意味着它们的结束空字符('\0')后直接跟随的是下一个字符串的开始。在这种情况下,如果没有明确的分隔标识(如空字符),程序可能会错误地将s1和s2视为一个连续的字符串,从而导致逻辑错误或意外的行为。

如果一个程序员决定通过执行以下代码:

c

复制代码

strcat(s1, "t");

来将字符串 "t" 追加到已存在的 C 字符串 s1 的末尾,那么这里存在几个潜在的问题和风险。

因为strcat 函数不会自动检查 s1 是否有足够的空间来容纳新添加的字符串 "t"。如果 s1 的缓冲区没有足够的空间来容纳原始字符串和追加的字符串,就会发生缓冲区溢出到s2的缓冲空间中,导致s2保存的内容被意外地修改,如下图所示:

SDS的优势特点

节省数据内存分配

SDS的设计,使得Redis在处理字符串时,能够更加灵活和高效。与传统的C字符串相比,SDS提供了动态调整大小的功能,省去了频繁的内存分配和复制操作,从而显著提升了性能。

解决终止符的问题

C语言中字符串是通过char*类型的字符数组来表示的,这些数组以空字符('\0')作为字符串的终止符。如果字符串中间包含空字符,它将被错误地解释为字符串的结束,从而导致字符串无法被正确表示。

c

复制代码

#include "stdio.h"
  #include "string.h"
  int main(void) {
      char *t1 = "hello\0world";
      char *t2 = "helloworld\0";
      printf("%lu\n", strlen(t1));
      printf("%lu\n", strlen(t2));
  }
  输出结果是 5 和 10。

其中底层的字符存储模式如下所示: 为了确保Redis能够灵活适应各种不同的使用场景,SDS被设计为二进制安全的。所有的SDS API在处理存储在buf数组中的数据时,都会以二进制的方式进行处理。程序不会对这些数据施加任何限制、过滤或假设,确保数据在写入时和读取时保持一致。

这也是为什么SDS的buf属性称为字节数组的原因,因为Redis并不是使用这个数组来保存字符,而是用它来保存一系列原始的二进制数据。这种设计使得SDS能够轻松应对各种复杂的数据格式,包括那些使用特殊字符或编码的数据。

内存溢出控制

C语言的字符串是静态分配的,当追加的内容导致字符串长度超过原分配的空间时,就可能发生溢出错误或无法追加的情况。这是因为SDS在内部维护了字符串的长度信息,并且使用了动态内存分配来管理字符串空间。

sdscat拼接案例分析

SDS的sdscat函数为例,该函数旨在将一个C字符串追加到给定SDS所存储的字符串的末尾。然而,与C标准库中的strcat函数不同,sdscat在执行拼接操作之前,会先对给定SDS的可用空间进行详尽的检查。如果SDS的当前空间不足以容纳即将追加的C字符串,sdscat会智能地扩展SDS的空间,确保有足够的容量来容纳拼接后的新字符串。只有当空间扩展完成后,sdscat才会执行实际的拼接操作。

空间分配策略进行了优化,从而彻底消除了缓冲区溢出的风险。当使用SDS API对SDS进行修改时,该API会预先检查SDS当前的空间是否满足修改所需的条件。如果SDS的空间不足以支持所需的修改,API会自动执行空间扩展操作,将SDS的大小调整至足以执行修改所需的大小。只有在确保空间足够后,API才会执行实际的修改操作。

提升操作效率

Redis所采用的简单动态字符串(SDS)则在这些方面进行了优化,SDS不仅能够在O(1)的时间复杂度内获取字符串长度,还能在O(1)的时间复杂度内完成字符串的追加操作。

SDS通过在其内部结构中包含一个len属性来直接记录字符串的长度信息。因此,在SDS中,获取字符串长度的操作不再需要遍历整个字符串,而是直接读取len属性的值,这使得获取SDS长度的复杂度降低到了O(1),即无论SDS的长度如何,获取其长度所需的时间都是恒定的。

因此,可以说SDS是Redis在处理字符串数据时的一项创新举措,它使得Redis能够以更加高效和灵活的方式处理字符串,从而为用户提供了更加稳定和高效的数据存储和访问体验。


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

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
2天前
|
消息中间件 存储 Java
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
11 4
|
2天前
|
搜索推荐 C++
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(一)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
2天前
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(二)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
26天前
|
设计模式 安全 Java
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
假如有T1、T2两个线程同时对某链表扩容,他们都标记头结点和第二个结点,此时T2阻塞,T1执行完扩容后链表结点顺序反过来,此时T2恢复运行再进行翻转就会产生环形链表,即B.next=A;采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率。JDK8中,HashMap采用尾插法,扩容时链表节点位置不会翻转,解决了扩容死循环问题,但是性能差了一点,因为要遍历链表再查到尾部。例如15(即2^4-1)的二进制为1111,31的二进制为11111,63的二进制为111111,127的二进制为1111111。
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
|
10天前
|
存储 缓存 NoSQL
解决Redis缓存击穿问题的技术方法
解决Redis缓存击穿问题的技术方法
30 2
|
13天前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
23天前
|
存储 NoSQL Redis
Redis 管道技术
【9月更文挑战第16天】Redis 管道技术通过批量发送命令并一次性读取响应,显著提升了与 Redis 服务器交互的性能。其工作原理包括命令缓冲、批量发送、响应接收与处理。管道技术减少了网络往返次数,提高了资源利用效率,并使代码更简洁。适用于批量操作、高并发环境及复杂业务逻辑等场景,是优化 Redis 应用性能的强大工具。
|
2天前
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(三)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
27天前
|
缓存 NoSQL PHP
使用PHP-redis实现键空间通知监听key失效事件的技术与代码示例
通过上述方法,你可以有效地在PHP中使用Redis来监听键空间通知,特别是针对键失效事件。这可以帮助你更好地管理缓存策略,及时响应键的变化。
65 3
|
10天前
|
存储 NoSQL Redis
10)Redis 的管道技术
10)Redis 的管道技术
20 0