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

相关文章

来自专栏IT派

SQL Server 与 MySQL 中排序规则与字符集相关知识的一点总结

字符集是针对不同语言的字符编码的集合,比如UTF-8字符集,GBK字符集,GB2312字符集等等,不同的字符集使用不同的规则给字符进行编码。排序规则则是在特定字...

615
来自专栏大闲人柴毛毛

深入理解JVM(八)——类加载的时机

类的生命周期 一个类从加载进内存到卸载出内存为止,一共经历7个阶段: 加载——>验证——>准备——>解析——>初始化——>使用——>卸载 其中,类加载包括...

2654
来自专栏蓝天

C语言编程程序的内存如何布局

C语言程序在内存中各个段的组成   C语言程序连接过程中的特性和常见错误   C语言程序的运行方式   一:C语言程序的存储区域   由C语言代码(文本...

562
来自专栏博岩Java大讲堂

Java虚拟机--对象的建立你的对象如何创建?

2856
来自专栏IT笔记

JAVA中的值传递和引用传递

先来看一个作为程序员都熟悉的值传递的例子: ... ... //定义了一个改变参数值的函数 public static void changeValue(int...

3199
来自专栏技术博客

C#字符串(字节)的长度

顺便看一下Sql Server中char nchar varchar  nvarchar

632
来自专栏大闲人柴毛毛

String类中你不知道的知识

直接量创建对象更高效 在Java中,创建一个字符串有两种方法: //第一种方法 String str1 = "字符串1"; //第二种方法 String str...

2766
来自专栏我是业余自学C/C++的

malloc、calloc、realloc

1533
来自专栏liulun

Nim教程【十一】

引用类型和指针类型 不同的引用可以只想和修改相同的内存单元 在nim中有两种引用方式,一种是追踪引用,另一种是非追踪引用 非追踪引用也就是指针,指向手动在内存中...

1916
来自专栏移动端开发

Swift 内存管理详解

Swift内存管理: Swift 和 OC 用的都是ARC的内存管理机制,它们通过 ARC 可以很好的管理对象的回收,大部分的时候,程序猿无需关心 Swift...

1759

扫描关注云+社区