原创代码,Java

Redis底层数据结构--简单动态字符串

本文阅读 7 分钟
首页 代码,Java 正文

1.简介

Redis没有适用传统农的C语言的字符串表示(以空字符结尾的字符数组),而是自己设计了一个名为简单动态字符串(SDS)的的抽象类型。

在Redis中,C字符串只会作为字符串字面量,用在一些无须对字符串值进行修改的地方,比如打印日志。

在Redis中,包含字符串的键值对在底层都是由SDS实现的。

2.SDS的定义

结构定义如下:

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

如下图展示了一个SDS的示例:
01.png

  • free属性值为0,表示这个SDS没有未分配的空间;
  • len属性值为5,表示该SDS存储了一个5字节的字符串;
  • buf属性是一个char类型的数组,前5个字节分别存了上图的5个字符,最后一个字节存了 '0'

SDS遵循C字符串以空字符结尾的习惯,保存空字符的1个字节空间不计算在len的属性中。为空字符分配额外的一个字节空间,以及添加空字符到字符串末尾,都是由SDS函数自动完成。遵循这一习惯的好处是SDS可以重用一部分C字符串函数库的函数。

下图展示了还有5个字节可使用的SDS:
02.png

3.Redis中为什么要使用SDS

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

如果使用C字符串要获取字符串长度的话,需要遍历,时间复杂度O(n);但是使用SDS的话直接获取 len属性的指,时间复杂度O(1)

3.2 杜绝缓冲区溢出

使用C字符串如果小心,很容易造成缓冲区溢出,如:字符串拼接函数 strcat

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

在执行这个函数的时候,需要保证dest已经分配了足够的空间,用来容纳src的字符串的所有内容,但是这个保证是由开发者来保证的,开发者一不小心就很容易造成缓冲区溢出,让新的字符串溢出到其他内存空空间,如果其他内存空间存的正是正在用的其他值,就会出现大问题。

而SDS完全没有这个问题,当SDS需要进行修改时,会先检查SDS的空间是否满足修改所需的要求,如果不满足的话,会自动将空间扩容至修改后所需的大小,然后才执行修改操作。

3.3 减少修改字符串时带来的内存重分配操作

因为C字符串不记录自身的长度,每次对增长或者缩短一个C字符串时,程序总要对这个保存C字符串的数组进行一次内存重分配操作

  • 如果是增长字符串的操作,比如拼接操作,在执行这个操作之前,程序需要先通过内存重分配来扩展底层数组的的大小---如果忘了这一步就会产生缓冲区溢出;
  • 如果是缩短字符串,比如截断操作,在执行这个操作之后,需要通过内存重分配来释放不再使用的那部分内存空间---如果忘了这一步就会产生内存泄漏。

因为内存分配涉及复杂的算法,并且可能需要执行系统调用,所以通常是一个耗时的操作:

  • 在一般的程序中,如果修改字符串的情况不是很多,那么每次修改字符串都进行一次内存重分配是可以接受的;
  • 但是Redis作为一个内存数据库,经常被用于速度要求严苛、数据被频繁修改的场景,如果每次修改都进行一次内存重分配,是会严重影响性能的。

SDS使用未使用空间来解决这个问题,SDS实现了空间预分配和惰性空间释放两种优化策略。

1) 空间预分配

空间预分配用于优化SDS的增长操作,当对一个SDS进行修改并且需要进行空间扩展时,程序不仅会为SDS分配修改所必须的空间,还会分配额外的未使用的空间。其额外未使用的空间数量由以下公式决定:

  • 如果SDS进行修改后,len属性的指小于1MB,那么会分配和len属性同样大小的未使用空间。
  • 如果SDS进行修改后,len属性的指大于等于1MB,那么将会分配1MB的未使用空间。

通过空间预分配策略,Redis可以减少连续字符串的增长操作所需的内存重分配次数。

2) 惰性空间释放

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

3.4 二进制安全

C字符串除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这使得字符串只能保存文本数据,不能保存图片、视屏等这样的二进制数据。

参考书籍:Redis设计与实现

原创文章,作者:纸飞机-JAVA追梦,如若转载,请注明出处:https://www.zfjsec.com/1909.html
-- 展开阅读全文 --
Web安全—逻辑越权漏洞(BAC)
« 上一篇 03-13
Redis底层数据结构--链表
下一篇 » 04-12

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复