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

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

(原创内容,转载请注明来源,谢谢)

前言:《Redis设计与实现》,是一本分析redis源码,讲述redis各数据类型结构与实现方式、各操作方式的具体实现等内容。本系列是我对该书学习过程中的读书笔记。

一、概述

Redis中的字符串,是在redis中最为常用的内容,除了redis的字符串数据结构,另外redis其他的数据结构中的子成份,大多也是用字符串的形式存储。

redis的字符串不是直接用c语言的字符串,而是用了一种称为简单动态字符串(SDS)的抽象类型,并将其作为默认字符串。

二、SDS定义

structsdshdr{
 int len;
 int free;
 char buf[];
}

该结构体共三个变量,包括len——sds的长度、free——buf数组中未使用的字节数量、buf——字节数组(保存字符串使用)。

例如,字符串“Redis”的存储方式如下图:

其中,free是0表示申请的内存空间已经都用上,len是5表示长度是5(不计算表示字符串结束的符号\0,这一点和c语言一样),buf里面存储了具体的字符串内容。

三、SDS与C语言字符串的比较

SDS采用结构体的方式存储字符串,而不是采用c语言的开辟一个连续的存储空间的方式。

1、字符串长度计算

C语言如果要获取字符串的长度,需要从第一个字符开始,遍历整个字符串,直到遍历到\0符号,时间复杂度是O(N),即字符串的长度。

而redis由于已经存储了字符串的长度,因此,时间复杂度是O(1)。

这样,避免了获取大字符串长度时时间的缓慢。

2、缓冲区

C语言给字符串开辟一个存储空间,如果对此存储空间的使用超过开辟的空间,会导致内存溢出。例如使用字符串拼接等方式时,就很容易出现此问题。而如果每次拼接之前都要计算每个字符串的长度,时间上又要耗费很久。

redis的SDS中内置一个sdscat函数,也是用于字符串的拼接。但是在执行操作之前,其会先检查空间是否足够,通过比较当前字符串的free与即将拼接字符串的len的大小,就知道是否可以拼接。如果free的值不够,会再申请内存空间,避免溢出。

3、修改字符串时的内存重分配

C语言的字符串长度和底层数组之间存在关联,因此字符串长度增加时需要再分配存储空间,避免溢出;字符串长度减少时,需要释放存储空间,避免内存泄漏。

由于redis中,字符串频繁修改是很经常发生的事情,redis的一个应用场景就是变量频繁修改的场景。为了避免C语言的不断重分配空间,redis进行了改进。

redis的sds,主要是通过free字段,来进行判断。通过未使用空间大小,实现了空间预分配和惰性空间释放。

1)空间预分配

空间预分配用于优化字符串的增长操作,实现方式为:当需要增长字符串时,sds不仅会分配足够的空间用于增长,还会预分配未使用空间。

分配的规则是,如果增长字符串后,新的字符串比1MB小,则额外申请字符串当前所占空间的大小作为free值;如果增长后,字符串长度超过1MB,则额外申请1MB大小。

例如,字符串增长后,大小是50kb,则额外申请50kb作为未使用空间。如果字符串增长后的大小是20mb,则额外申请1mb作为未使用空间。以上两种情况都为将\0计算在内,因此,实际上还会需要1字节作为\0存放的空间。

上述机制,避免了redis字符串增长情况下频繁申请空间的情况。每次字符串增长之前,sds会先检查空间是否足够,如果足够则直接使用预分配的空间,否则按照上述机制申请使用空间。该机制,使得字符串增长n次,需要申请空间的次数,从必定为n次的情况,降为最多n次的情况。

2)懒惰空间释放

懒惰空间释放用于优化sds字符串缩短的操作,实现方式为:当需要缩短sds的长度时,并不立即释放空间,而是使用free来保存剩余可用长度,并等待将来使用。当有剩余空间,而有有增长字符串操作时,则又会调用空间预分配机制。

当redis内存空间不足时,会自动释放sds中未使用的空间,因此也不需要担心内存泄漏问题。

4、二进制安全

C语言的字符必须符合某种编码,例如ascii,且字符串除了末尾之外,不能有空格,否则会被当作是另一个字符串。这些限制使得c语言的字符串只能保存不含空格的文本,不能保存图片、视频等二进制数据,也不能保存包含空格的文本。

而保存图片、大段文本等内容,也是redis的常用场景。因此,redis也对此进行优化。因此,sds是二进制安全的,写入的是什么内容,返回的也是什么内容,并没有限制。

redis的sds,用buf保存字符串,保存的就是一系列的二进制数据。因为,sds考虑字符串长度,是通过len属性,而不是通过\0来判断。

5、C语言字符串函数

redis兼容c语言对于字符串末尾采用\0进行处理,这样使得其可以复用部分c语言字符串函数的代码,实现代码的精简性。

6、总结——C语言字符串和SDS字符串比较

C字符串

Redis SDS

获取字符串长度时间复杂的O(n)

获取字符串长度时间复杂的O(1)

字符串长度增加可能造成缓冲区溢出

字符串长度增加不会造成缓冲区溢出

修改字符串长度n次,必然n次内存重分配

修改字符串长度n次,最多n次内存重分配

只保存不含空格文本

保存任意二进制数据和文本数据

可以使用<string.h>库所有函数

可以使用部分<string.h>库的函数

四、总结

redis只有部分情况下使用c语言的字符串形式用作字符串,如给用户返回的信息、报错信息、提示信息等,只有不会被改动的字符串,才会直接使用c语言的字符串形式。否则,大部分情况下,redis都是使用sds作为字符串的存储方式。

——written by linhxx 2017.08.28

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-28

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逆向技术

逆向知识第十二讲,识别全局变量,静态全局变量,局部静态变量,以及变量.

         逆向知识第十二讲,识别全局变量,静态全局变量,局部静态变量,以及变量. 一丶认识全局的 (静态变量 全局变量) 高级代码: int RetIn...

18510
来自专栏Spark学习技巧

Java泛型详解——绝对是对泛型方法讲解最详细的,没有之一!

ArrayList可以存放任意类型,例子中添加了一个String类型,添加了一个Integer类型,再使用时都以String的方式使用,因此程序崩溃了。为了解决...

1392
来自专栏Python爬虫与数据挖掘

Python正则表达式初识(六)

续分享Python正则表达式基础,今天给大家分享的正则表达式特殊符号是“[]”。中括号十分实用,其有特殊含义,其代表的意思是中括号中的字符只要满足其中任意一个就...

653
来自专栏微信公众号:Java团长

Java泛型详解——绝对是对泛型方法讲解最详细的,没有之一!

ArrayList可以存放任意类型,例子中添加了一个String类型,添加了一个Integer类型,再使用时都以String的方式使用,因此程序崩溃了。为了解决...

771
来自专栏乐百川的学习频道

Java 8 新特性(一)lambda表达式

Java 9 好像也快出了,不过我连Java 8的新特性都还没认真研究过,所以这几篇文章就是来介绍Java 8的新特性的。首先,第一个重要的特性就是传说中的la...

2108
来自专栏用户2442861的专栏

c++面试题

delete会调用对象的析构函数,和new对应free只会释放内存,new调用构造函数。malloc与free是C++/C语言的标准库函数,new/delet...

731
来自专栏用户2442861的专栏

Java finally语句到底是在return之前还是之后执行?

网上有很多人探讨Java中异常捕获机制try...catch...finally块中的finally语句是不是一定会被执行?很多人都说不是,当然他们的回答是正...

902
来自专栏陈树义

Java集合常见面试题集锦

1、介绍Collection框架的结构 集合是Java中的一个非常重要的一个知识点,主要分为List、Set、Map、Queue三大数据结构。它们在Java中的...

3875
来自专栏程序员互动联盟

【专业技术】C++虚函数的缺省参数

编者按:缺省参数,缺省函数,缺省构造函数,如果你有些迷糊,本文可以让你把它看个清楚。呵呵。 前些日子,有个同学问我一个关于虚函数的缺省参数问题。他是从某个论坛上...

2596
来自专栏开发与安全

从零开始学C++之从C到C++(一):const与#define、结构体对齐、函数重载name mangling、new/delete 等

一、bool 类型 逻辑型也称布尔型,其取值为true(逻辑真)和false(逻辑假),存储字节数在不同编译系统中可能有所不同,VC++中为1个字节。 声明方式...

1750

扫码关注云+社区