Redis设计与实现第二章笔记
date
Jul 12, 2021
slug
Redis设计与实现第二章笔记
status
Published
tags
读书笔记
summary
简单动态字符串，SDS
type
Post
简单动态字符串（simple dynamic string, SDS）。
Redis将C字符串作为字符串字面量用在一些无须对字符串值进行修改的地方，比如打印日志，将SDS作为需要一个可以被修改的字符串值时使用。
SDS用的地方：
- Redis数据库里面，包含字符串的键值对
- 用作缓冲区：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区
2.1 SDS定义
- free为0，表示这个SDS没有分配任何未使用空间
- len为5，表示保存了一个五字节长的字符串
- buf是一个char类型的数组，实际存值的地方，最后一个字节保存了结束符'\0'
结束符结尾的好处时，SDS可以直接重用一部分C字符串函数库里的函数
2.2 SDS与C字符串的区别
2.2.1 常数复杂度获取字符串长度
直接获取len属性而不需要遍历数组，STRLEN命令的复杂度为O(1)
2.2.2 杜绝缓冲区溢出
举例：
添加额外字符串到S1尾部，会意外修改S2的内容
SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足需要，不满足的话，API会自动将SDS扩容至需要的大小。
2.2.3 减少修改字符串时带来的内存重分配次数
每次增长或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行一次内存重分配操作。
为了避免C字串的缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度的联系：在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。
SDS实现了空间预分配和惰性空间释放：
空间预分配
当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展时，程序不仅会为SDS分配修改所必须的空间，还会为SDS分配额外未使用的空间
公式：
- 如果修改之后，SDS的长度(len的值)将小于1MB，那么程序分配len属性同样大小的未使用空间，这是SDS的len和free属性相同
- 如果修改之后，SDS的长度将大于1MB，那么程序会分配1MB的未使用空间
惰性空间释放
当SDS的API需要缩短字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来。
举例：
2.2.4 二进制安全
二进制安全使得Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据
2.2.5 兼容部分C字符串函数
由于结尾空字符的存在，可以使用部分<string.h>定义的函数
2.2.6 总结
