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 条评论
登录 后参与评论

相关文章

来自专栏积累沉淀

JavaScript 变量 作用域 内存

知识点 1.变量及作用域 2.内存问题 JavaScript的变量与其他语言的变量有很大区别。JavaScript变量是松散型的(不强制类型)本质,决定...

2115
来自专栏IT可乐

Redis详解(四)------ redis的底层数据结构

  上一篇博客我们介绍了 redis的五大数据类型详细用法,但是在 Redis 中,这几种数据类型底层是由什么数据结构构造的呢?本篇博客我们就来详细介绍Redi...

910
来自专栏Java面试笔试题

阐述final、finally、finalize的区别

943
来自专栏java一日一条

java内存分配和String类型的深度解析

在java语言的所有数据类型中,String类型是比较特殊的一种类型,同时也是面试的时候经常被问到的一个知识点,本文结合java内存分配深度分析关于String...

451
来自专栏java一日一条

java内存分配和String类型的深度解析

在java语言的所有数据类型中,String类型是比较特殊的一种类型,同时也是面试的时候经常被问到的一个知识点,本文结合java内存分配深度分析关于String...

691
来自专栏个人分享

JVM 类型的生命周期学习

Java虚拟机通过装载、连接和初始化一个JAVA类型,使该类型可以被正在运行的JAVA程序所使用,其中,装载就是把二进制形式的JAVA类型读入JAVA虚拟机中;...

713
来自专栏Jaycekon

深入浅出Redis-redis底层数据结构(上)

1、概述 ----     相信使用过Redis 的各位同学都很清楚,Redis 是一个基于键值对(key-value)的分布式存储系统,与Memcached类...

4607
来自专栏Spark学习技巧

深入了解Redis内存模型

2355
来自专栏java一日一条

115个Java面试题和答案——终极列表(上)

本文我们将要讨论Java面试中的各种不同类型的面试题,它们可以让雇主测试应聘者的Java和通用的面向对象编程的能力。下面的章节分为上下两篇,第一篇将要讨论面向对...

482
来自专栏java技术学习之道

java50道基础面试题

1337

扫码关注云+社区