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

相关文章

来自专栏Java编程

Java泛型详解

Java泛型(generics)是JDK 5中引入的一个新特性,允许在定义类和接口的时候使用类型参数(type parameter)。声明的类型参数在使用时用具...

7560
来自专栏Python爬虫实战

Python数据类型之字典(上)

之前系列文章介绍了Python简单数据类型和序列数据类型,本文来学习一种新的映射数据类型:字典。

901
来自专栏Modeng的专栏

Javascript数组系列五之增删改和强大的 splice()

今天是我们介绍数组系列文章的第五篇,也是我们数组系列的最后一篇文章,只是数据系列的结束,所以大家不用担心,我们会持续的更新干货文章。

1382
来自专栏锦小年的博客

python学习笔记4.2-python高级之迭代器

迭代是Python中最强有力的特性之一,同时对编程人员来说,也是最难理解的一种用法。其实从高层次来看,迭代就是一种处理序列中元素的方式。通过自定义迭代对象可以...

21710
来自专栏怀英的自我修炼

Java漫谈9

上次聊String的时候聊到了String为什么可以在不new的情况下创建,说实话,这个问题我也没有答案,直到看到了这篇帖子,才敢说知道了为什么。 《Java ...

3679
来自专栏信安之路

php 弱类型问题

php 是一门简单而强大的语言,提供了很多 Web 适用的语言特性,其中就包括了变量弱类型,在弱类型机制下,你能够给一个变量赋任意类型的值。

1590
来自专栏Python数据科学

Python爬虫之快速入门正则表达式

当完成了网页html的download之后,下一步当然是从网页中解析我们想要的数据了。那如何解析这些网页呢?Python中有许多种操作简单且高效的工具可以协助我...

1243
来自专栏小詹同学

Leetcode打卡 | No.21 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1151
来自专栏从零开始学 Web 前端

01 - JavaSE之基础及面向对象

byte(-128 ~ 127) short(-32768 ~ 32767) int(-2147483648 ~ 2147483647)

1734
来自专栏blackheart的专栏

[C#6] 3-null 条件运算符

0. 目录 C#6 新增特性目录 1. 老版本的代码 1 namespace csharp6 2 { 3 internal class Perso...

22110

扫码关注云+社区

领取腾讯云代金券