专栏首页用户7890857的专栏1、Redis数据结构——简单动态字符串-SDS
原创

1、Redis数据结构——简单动态字符串-SDS

1、SDS简介:

redis没有使用C语言传统的字符串表示(以空字符结尾的字符数组),而是自己构建了一种名为简单动态字符串(SDS)的抽象类型,并将SDS用作redis的默认字符串表示。

除了用来保存数据库中的字符串值之外,SDS还被用作缓冲区;AOF模块中的AOF缓存区,以及客户端状态中的输入缓冲区,都是SDS实现的。

2、SDS定义:

struct sdshdr { //记录buf数组中已使用字节的数量 //等于SDS所保存字符串的长度 int len; //记录buf数组中未使用字节的数量 int free; //字节数组,用于保存字符串 char buf[]; }

图示例:

  • len = 5,说明当前存储的字符串长度为5
  • free = 0,说明这个结构体实例中,所有分配的空间长度已经被使用完毕
  • buf 属性是一个char 类型的数组,保存了实际的字符串信息

可以看到 len 属性和 buf 属性的已使用部分都和第一个示例相同,但是 free 属性为 5, 同时 buf 属性的除了保存了真实的字符串内容之外,还有 5 个空的未使用空间 ('0'结束字符不在长度中计算)

SDS遵循C字符串以空字符串结尾的惯例,保存空字符串的1字节空间不计算在SDS的len属性里面,并且为空字符串分配额外的1字节空间,以及添加空字符到字符串末尾等操作,都由SDS函数自动完成的,所以这个空字符串对于SDS的使用者来说完全是透明的。这么做的好处是可以直接重用一部分C字符串函数库里面的函数。

3、SDS与C字符串的区别

根据传统,C语言使用长度为N+1的字符数组来表示长度为N的字符串,并且字符数组的最后一个元素总是空字符'\0';

3.1、常数复杂度获取字符串长度

因为C字符串并不记录自身的长度信息,所以为了获取一个 C字符串长度,程序必须遍历整个字符串,对遇到的每个字符进行计数,直到遇到代表字符串结尾的空字符为止,复杂度O(n)。

对于SDS而言,因为数据结构中保存了len属性,就可以立即知道长度。通过使用SDS而不是C字符串,Redis将获取字符串长度所需的复杂度从O(n)降低到了O(1),这也保证了获取字符串长度不会成为Redis的性能瓶颈。

3.2、杜绝缓冲区溢出

C字符串不记录自身长度带来的另外一个问题是容易造成缓冲区溢出。举子例子,<string.h>/strcat函数可以将src字符串中的内容拼接到dest字符串的末尾:char *strcat(char *dest, const char *src)

如果用户在执行拼接函数时,已经为dest分配足够多的内存,可以容纳src字符串中的所有内容,而一旦假设不成立,就会产生缓冲区溢出;与C字符串不同,SDS的空间分配策略完全杜绝了发送缓冲区溢出的可能性:当SDS API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作。

3.3、减少修改字符串时带来的内存重分配次数

因为C字符串不记录自身的长度,对于一个N个字符的C字符串来说,这个C字符串底层实现总是一个N+1个字符长的数组。因为C字符串的长度和底层数组的长度之间存在着这种关联性,所以每次增长或者缩短一个C字符串,程序都总要对保存这个C字符串的数组进行一次内存重分配操作:

  • 如果是增长字符串,那么执行前先要通过内存重分配来扩展底层数组的大小——如果忘记就会产生缓冲区溢出。
  • 如果是缩短字符串操作,那么要通过内存重分配来释放字符串不再使用的部分空间——如果忘记就会内存泄露。

在一般程序中,如果修改字符串长度的情况不太经常出现,那么每次修改都执行一次内存重分配是可以接受的;但是Redis经常被用于速度要求严苛、数据频繁修改的场合,光是内存重分配的时间就会占去很大一部分时间,对性能造成影响。

为了避免这种缺陷,SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。通过未使用空间,SDS实现了空间预分配惰性空间释放两种优化策略。

3.3.1、空间预分配

空间预分配用于优化SDS字符串增长操作:当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展的时候,不仅会为SDS分配修改所必须的空间,还会为SDS分配额外的未使用空间。

  • 如果SDS进行修改之后,SDS的长度(即是len属性的值)小于1M,那么程序分配和len属性同样大小的未使用空间,这时SDS len属性的值将和free属性的值相同。
  • 如果SDS修改之后,长度将大于等于1M,那么程序会分配1M的未使用空间。

3.3.2、惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时,程序并不会立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

3.4、二进制安全

C字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串不能包含空字符串,否则会被认为是字符串结尾。这些限制使得C只能保存文本数据,而不能保存图片、音频。视频、压缩文件等二进制数据。

所有SDS API都会以处理二进制方式来处理SDS存放在buf数组里的数据,程序不会对其中数据做任何限制、过滤,数据写入是什么样,读取就是什么样。因为SDS使用len属性的值而不是空字符来判断字符串是否结束。。

3.5、兼容部分C字符串函数

SDS一样遵循C字符串以空字符结尾的惯例,总是在为buf数组分配空间时多分配一个字节来容纳这个空字符,这是为了可以重用一部分<string.h>库定义函数。

重点回顾

Redis 中使用字符串的大多数场景(键的字符串,字符串数据结构的实际值存储等等)下,都不使用 C 语言的字符串,而是使用 SDS. 简单动态字符串。

它的实现方式是:一个字节数组 buf, 一个当前字符串长度的记录属性 len, 一个当前未使用空间长度属性 free. 字节数组的长度不要求绝对等于字符串值的真实长度,会有一定的缓冲。

相对于 C 语言的字符串,SDS 的优势如下:

C字符串

SDS

获取字符串长度需要 O(N)

获取字符串长度需要 O(1)

容易造成缓冲区溢出

通过封装 API, 自动变化长度,避免缓冲区溢出

每次修改字符串长度,都需要内存重新分配

最坏情况下,同 C 语言字符串,其他很多情况不需要内存重分配,直接使用预留缓冲即可。

只能保存纯文本

二进制安全,可以保存任意格式的二进制数据

无缝使用所有 C 库函数

可以兼容一部分的 C 库函数

参考文章

《Redis的设计与实现(第二版)》

联系我

最后,欢迎关注我的个人公众号 CodingCode,会不定期更新学习笔记,也欢迎公众号私信,一定知无不言,言无不尽。

公众号

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis01-Redis的数据结构之简单动态字符串SDS

    Redis用了这么久,一直没有认真的去了解其内部的数据结构和实现原理。从今天开始正式系统性的学习Redis。首先,还是从工作中经常打交道的数据类型开始说起,然后...

    码农飞哥
  • Redis数据结构-简单动态字符串

    Sds (Simple Dynamic String,简单动态字符串)是 Redis 底层所使用的字符串表示, 几乎所有的 Redis 模块中都用了 sds。

    程序员酷森
  • 【Redis】一、Redis的简单动态字符串SDS

    Redis没有直接使用C语言传统的字符串表示(以空字符 \0 结尾的字符数组),而是构建了一种名为简单动态字符串SDS的抽象类型,并将SDS用作Redis的默认...

    石臻臻的杂货铺[同名公众号]
  • Redis字符串-二进制安全(sds:简单动态字符串

    比如说, hello world 在 C 语言中就可以表示为 "hello world\0" 。

    用户8639654
  • 《闲扯Redis二》String数据类型之底层解析

    疑问:embstr 是什么意思,动态字符串又是什么意思?字符串对象到底什么结构?三种实现方式有什么区别呢?

    大道七哥
  • Redis源码分析(一)——Redis数据结构-字符串SDS

    1. SDS简介 Redis中使用的字符串均为『简单动态字符串』(Simple Dynamic String),简称SDS。 SDS是在C字符串的基础上进行了...

    大闲人柴毛毛
  • redis 为什么把简单的字符串设计成 SDS?

    2021开工第一天,就有小伙伴私信我,还给我分享了一道他面阿里的redis题(这家伙绝比已经拿到年终奖了),我看了以后觉得挺有意思,题目很简单,是那种典型的似懂...

    范蠡
  • redis 为什么把简单的字符串设计成 SDS?

    面试官:redis是用C语言开发的,那为啥不直接用C的字符串,还单独设计SDS这样的结构呢?

    AlbertZhang
  • Redis 中的 “SOS”,不对,是 SDS

    大家好,我是鸭血粉丝(大家会亲切的喊我 「阿粉」),是一位喜欢吃鸭血粉丝的程序员,之前给大家总结了线上 OOM 的情况,相信大家也能从中学到一些东西,身为一名有...

    纯洁的微笑
  • 《Redis设计与实现》读书笔记(一)——简单动态字符串(SDS)

    《Redis设计与实现》读书笔记(一) ——简单动态字符串(SDS) (原创内容,转载请注明来源,谢谢) 前言:《Redis设计与实现》,是一本分析redis...

    用户1327360
  • Redis string之SDS 源码分析 1

    string是Redis中最经常使用的一种结构,与c语言中的原生字符串不太一样,Redis 使用的是一种叫做SDS的结构,simple Dynamic stri...

    邹志全
  • 阿里面试这样问:redis 为什么把简单的字符串设计成 SDS?

    2021开工第一天,就有小伙伴私信我,还给我分享了一道他面阿里的redis题(这家伙绝比已经拿到年终奖了),我看了以后觉得挺有意思,题目很简单,是那种典型的似懂...

    程序员内点事
  • 见微知著 —— Redis 字符串内部结构源码分析

    继上篇讲解了字典的内部结构 之后,本篇我们开始讲字典 key 的内部结构,也就是 sds 字符串。首先它不是普通字符串,而是 sds 字符串,这个 sds 的意...

    老钱
  • Redis系列(一)底层数据结构之简单动态字符串

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • redis学习 - sds字符串

    Redis 设计与实现:如果想要知道redis底层,这本书可以给予不少的帮助,非常推荐每一位学习redis的同学去翻一翻。

    阿东
  • 精讲Redis内存模型一、Redis内存统计二、Redis内存划分三、Redis数据存储的细节四、Redis的对象类型与内部编码五、应用举例

    Java架构
  • 可能是目前最详细的Redis内存模型及应用解读

    Redis是目前最火爆的内存数据库之一,通过在内存中读写数据,大大提高了读写速度,可以说Redis是实现网站高并发不可或缺的一部分。

    田维常
  • Redis内存模型

    Tanyboye
  • 深入学习Redis:Redis内存模型

    转载自博客园 https://www.cnblogs.com/kismetv/p/8654978.html

    beifengtz

扫码关注云+社区

领取腾讯云代金券