Redis源码分析(一)——Redis数据结构-字符串SDS

1. SDS简介

  • Redis中使用的字符串均为『简单动态字符串』(Simple Dynamic String),简称SDS。
  • SDS是在C字符串的基础上进行了一些包装,使得它更符合Redis的使用场景。
  • 在Redis中,C字符串只用在一些无需修改的地方,如日志打印;其他需要使用字符串的地方基本上使用的都是SDS。

2. 数据结构

struct sdshdr{
  int len;
  int free;
  char buf[];
};
  • len:buf数组中字符串的实际使用量。
  • free:buf数组中空闲量。
  • buf:存储字符的数组。

3. SDS的优点

Redis使用C语言编写,而Redis不使用C语言字符串是有原因的,Redis中的SDS字符串与C字符串相比有如下优点。

3.1 获取字符串长度效率高

C语言字符串是不记录字符串长度的,所以每次获取字符串长度时,都要对字符数组进行一次遍历,那么时间复杂度就为O(n)。 而SDS中采用len记录当前字符串的长度,所以统计字符串长度的时间复杂度为O(1),因此效率高于C字符串。

3.2 避免了缓冲区溢出

3.2.1 什么是『缓冲区溢出』?

当使用strcat(char *dest, char *src)拼接两个字符串时,strcat是默认第一个字符数组的后面是有足够空间的,它会直接把第二个字符数组中的字符挨个复制到第一个字符数组的后面。 那么问题就来了,如果这两个字符数组的内存空间是紧挨着的,那么当执行strcat时,第二个字符数组的就会被覆盖掉。这就是缓冲区溢出。 所以在使用strcat拼接两个字符串前,一定要先判断第一个字符串后面是否有足够的内存空间;如果不够了,那就得手动扩容。那么这一系列判断+扩容操作都是需要程序员自己去完成的,有些麻烦。

3.2.2 Redis如何避免缓冲区溢出?

而SDS提供的所有修改字符串的API中,都会判断修改之后是否会内存溢出,如果会内存溢出,它会帮你进行内存扩容。 所以对于SDS而言,这一系列操作都由它来帮你完成,无需程序员手动判断。

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

3.3.1 什么是『内存重分配』?

  • 当我们使用append扩充字符串时,我们首先要扩充当前字符数组的内存,然后再将第二个字符数组中的值一一复制进来,否则就有可能出现『缓冲区溢出』。这个过程就是『内存重分配』。
  • 当我们需要截取字符串后,我们需要释放已经不被使用的内存空间,否则就可能出现『内存泄露』。这个过程也是『内存重分配』。

内存重分配过程会涉及复杂的算法和系统调用,较为耗时。如果像C字符串那样,每次修改字符串都要进行一次内存重分配,那么效率是极底的,所以SDS使用了『空间预分配』和『惰性空间释放』降低了重分配的频率,从而提升效率。

3.3.2 SDS如何减少内存重分配次数?

  1. 空间预分配 当需要扩展SDS长度的时候,Redis不仅会给它分配所需的内存空间,还会分配一段额外的空间作为备用。 备用空间大小按照如下公式计算:
    • 如果扩展之后,SDS字符数组的长度小于1M,那么就使得备用空间的大小和字符串实际长度保持一致,即:len==free;
    • 如果扩展之后,SDS字符数组的长度大于1M,那么备用空间的大小就设置成1M。 那么这样的话,当要append时,直接使用备用空间即可,无需再次扩容啦,从而减少了内存重分配的次数。SDS将连续增长N次字符串所需的内存重分配次数从『必定N次』减少到了『最多N次』。
  2. 惰性空间释放 当需要缩短字符串时,SDS不会立即释放多于的内存空间,而是将其保留,修改free值。这样的话,当下次需要扩容时,直接使用这部分内存空间即可,减少了内存重分配的次数。

3.4 二进制安全 binary-safe

3.4.1 什么是『二进制安全』?

所谓『二进制安全』就是:往SDS里面放什么数据,取出来还是什么数据。SDS不会对存储的这些数据做任何修改、限制、过滤等。

3.4.2 SDS如何保证二进制安全?

C字符串对存入的字符串是有严格要求的: 1. 必须符合某种编码(如ASKII) 2. 不能含有空格

而SDS对于存储的数据没有任何限制,因此称为『二进制安全』。

3.5 兼容C字符串

C字符串要求字符数组的末尾必须是\0,作为字符串尾的标记。而SDS中的字符数组也遵循了这一规范,所以仍然可以使用C字符串相关函数,因此避免了重复代码。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

Swift基础语法

本文来自Swift中文开发组,感谢翻译者的分享。 本文将分几部分对Swift对iOS的语法做讲解。本文为第一节,主要讲解基础语法。 常量和变量 常量和变量把一个...

1676
来自专栏vue学习

JS数据结构与算法-队列

681
来自专栏水击三千

浅谈JavaScript的函数表达式(闭包)

  前文已经简单的介绍了函数的闭包。函数的闭包就是有权访问另一个函数作用域的函数,也就是函数内部又定义了一个函数。 1 var Super=function(n...

2125
来自专栏java学习

看看你对队列的了解有多少?

1.1队列概念及基本操作 队列(Queue) 简称队,它同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。在队列中...

2625
来自专栏.Net Core 开发记录

JavaScript权威指南 - 函数

函数本身就是一段JavaScript代码,定义一次但可能被调用任意次。如果函数挂载在一个对象上,作为对象的一个属性,通常这种函数被称作对象的方法。用于初始化一个...

573
来自专栏Python

python装饰器大详解

一.作用域 在python中,作用域分为两种:全局作用域和局部作用域。 全局作用域是定义在文件级别的变量,函数名。而局部作用域,则是定义函数内部。  关于作用...

19910
来自专栏前端儿

JS中 toString() & valueOf()

toString()可以看做是把一个数据转换成了相应字符串的形式,安照这个转换规则中

741
来自专栏编程

Python 迭代器和生成器

来源:田小计划 www.cnblogs.com/wilber2013/p/4652531.html 在Python中,很多对象都是可以通过for语句来直接遍历的...

17910
来自专栏软件开发 -- 分享 互助 成长

java arrays类学习

java.util.Arrays类能方便地操作数组,它提供的所有方法都是静态的。 具有以下功能: (1)给数组赋值:通过fill方法。 (2)对数组排序:通过s...

1766
来自专栏salesforce零基础学习

salesforce 零基础学习(六十六)VF页面应善于使用变量和函数(二)常用函数的使用

上一篇介绍VF中常用的变量,此篇主要内容为VF页面可以直接使用的函数,主要包括Date相关函数,Text相关函数,Information相关函数以及logic相...

20310

扫描关注云+社区