文章目录

• 《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 之间的区别

第三章、链表