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

相关文章

来自专栏机器学习从入门到成神

海量数据处理之Bti-map详解

    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以...

731
来自专栏转载gongluck的CSDN博客

野指针分析

1. 野指针的概念   所谓的野指针,就是说指针指向的那块内存,你没有合法操作的权限,也就是指针指向非法的内存空间,这样的指针就叫做野指针。 2. 野指针产...

3687
来自专栏小樱的经验随笔

队列的存储结构的实现(C/C++实现)

存档 1 #include "iostream.h" 2 #include "stdlib.h" 3 #define max 20 4 typedef ...

3296
来自专栏Youngxj

for循环-c语言学习笔记

1794
来自专栏ShaoYL

C语言基础-循环结构

3329
来自专栏Java面试笔试题

两个栈实现一个队列

由于往栈中添加元素相当于往队列头添加元素,因此我们需要在两个队列中进行元素的转移,比较简单的实现是:

823
来自专栏闪电gogogo的专栏

【数据结构(C语言版)系列四】 串

串(或字符串)是由零个或多个字符组成的有限序列,一般记为 s = 'a1a2...an',s为串名。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。

311
来自专栏coding

redis列表list类型详解

1442
来自专栏Linux Python 加油站

Python基础之set应用详解

一个{ }里面放一些元素就构成了一个集合,set里面可以是多种数据类型(但不能是列表,集合,字典,可以是元组)

1605
来自专栏Golang语言社区

golang 算法课程 正式开课--第一季 第1节

题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列...

3037

扫码关注云+社区