Redis教程

《Redis设计与实现》读书笔记

本文主要是介绍《Redis设计与实现》读书笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 《Redis设计与实现》读书笔记
    • 第一部分、数据结构与对象
      • 第二章、简单动态字符串
        • 2.1 SDS的定义
        • 2.2 SDS与C字符串的区别
          • 2.2.1 常数复杂度获取字符串长度
          • 2.2.2 杜绝缓冲区溢出
          • 2.2.3 减少修改字符串时带来的内存重分配次数
            • 2.2.3.1 空间预分配
            • 2.2.3.2 惰性空间释放
          • 2.2.4 二进制安全
          • 2.2.5 兼容部分C字符串函数
        • 总结
      • 第三章、链表

《Redis设计与实现》读书笔记

第一部分、数据结构与对象

第二章、简单动态字符串

2.1 SDS的定义

每个 sds.h/sdshdr结构表示一个SDS值:

struct sdshdr {
	// 记录buf数组中已使用字节的数量
	// 等于SDS所保存的字符串的长度
	int len;
	
	// 记录buf数组中未使用字节的数量
	int free;

	//字节数组,用于保存字符串
	char buf[];
}

在这里插入图片描述

2.2 SDS与C字符串的区别

2.2.1 常数复杂度获取字符串长度

SDS中len变量保存了当前字符串的长度,在SDS被设置和更新时,SDS的API会在执行时自动完成长度的更新。

2.2.2 杜绝缓冲区溢出

当SDSAPI需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后进行实际的修改操作,所以SDS既不需要手动修改SDS的空间大小,也不会出现前面所说的缓冲区溢出问题。

2.2.3 减少修改字符串时带来的内存重分配次数
2.2.3.1 空间预分配

空间预分配用于优化SDS的字符串增长操作: 当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必须要的空间,还会为SDS分配额外的未使用空间。

  • 如果对SDS进行修改后,SDS的长度小于1MB,那么程序分配和len属性同样大小的未使用空间,这时SDSlen属性的值将和free属性的值相同。
  • 如果对SDS进行修改后,SDS的长度大于1MB,那么程序会分配1MB的未使用空间。
2.2.3.2 惰性空间释放

惰性空间释放用于优化SDS字符串缩短操作: 当SDS的API需要缩短SDS中保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

通过惰性空间释放策略。SDS避免了缩短字符串时所需的内存重分配操作,并未将来可能有的增长操作提供了优化。

与此同时,SDS也提供了相应的API,让我们可以在有需要时,真正的释放SDS的未使用空间,所以不用担心惰性空间释放策略会造成内存浪费。

2.2.4 二进制安全

为了确保 Redis 可以适用于各种不同的使用场景, SDS 的 API 都是二进制安全的(binary-safe): 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据, 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的, 它被读取时就是什么样。

这也是我们将 SDS 的 buf 属性称为字节数组的原因 —— Redis 不是用这个数组来保存字符, 而是用它来保存一系列二进制数据。

比如说, 使用 SDS 来保存之前提到的特殊数据格式就没有任何问题, 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束

2.2.5 兼容部分C字符串函数

虽然 SDS 的 API 都是二进制安全的, 但它们一样遵循 C 字符串以空字符结尾的惯例: 这些 API 总会将 SDS 保存的数据的末尾设置为空字符, 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符, 这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数

总结

C 字符串和 SDS 之间的区别

C字符串SDS
获取字符串长度的复杂度为 O(N) 。获取字符串长度的复杂度为 O(1) 。
API 是不安全的,可能会造成缓冲区溢出。API 是安全的,不会造成缓冲区溢出
修改字符串长度 N 次必然需要执行 N 次内存重分配。修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。可以保存文本或者二进制数据。
可以使用所有 <string.h> 库中的函数。可以使用一部分 <string.h> 库中的函数。

第三章、链表

这篇关于《Redis设计与实现》读书笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!