Redis设计与实现读书笔记——第二章SDS
Redis设计与实现读书笔记——第二章
为了做Redis相关实验，在网上粗略看了Redis设计与实现的电子版，感觉收获很多，但是因为是旧版，所以买了第二版，重读第二次。
第二章 简单动态字符串
简介
- 字符串值的键值对在底层都是由SDS实现的。
- sds的功能：
- 存储字符串值
- 用作缓冲区
- AOF模块缓冲区
- 客户端状态的输入缓冲区
2.1 SDS的定义
文件：sds.h/sdshdr 结构体
书中的为3.0版本，4.0版本有较大改动。
version: redis-4.02
参考：https://www.cnblogs.com/chenpingzhao/p/7292182.html
1 | typedef char *sds; //注意，sds其实不是一个结构体类型，而是被typedef的char* |
除了结构体字段对len和alloc的数据类型的不同(unit8, unit16， unit32, unit64)， 其字段含义相差无几。其中header记录len, alloc, flags 信息。不同的header的目的是节省内存。header与buf数组在内存地址上前后相邻。
1 | +--------+-------------------------------+-----------+ |
1 | len: 记录buf数组中已使用的字节数量 等于保存的字符串的长度 （不算结尾的\0 标识符） |
buf的大小=alloc+1；
header类型定义中，注意的地方：
在各个header的定义中使用了attribute ((packed))，是为了让编译器以紧凑模式来分配内存，取消字节对齐。
- 结构体的成员内存是’”连续”的，但是这个连续是以对齐的单位而言的。比如说A成员的内存是3个字节，假设对齐单位是4个字节，会给A成员多分配一个字节。A成员后面才又紧接B成员的内存。
- 如果没有这个属性，编译器可能会为struct的字段做优化对齐，在其中填充空字节。那样的话，就不能保证header和sds的数据部分紧紧前后相邻，也不能按照固定向低地址方向偏移1个字节的方式来获取flags字段了。
在各个header的定义中最后有一个char buf[]。我们注意到这是一个没有指明长度的字符数组，这是C语言中定义字符数组的一种特殊写法，称为柔性数组（flexible array member），只能定义在一个结构体的最后一个字段上。它在这里只是起到一个标记的作用，表示在flags字段后面就是一个字符数组，或者说，它指明了紧跟在flags字段后面的这个字符数组在结构体中的偏移位置。而程序在为header分配的内存的时候，它并不占用内存空间。如果计算sizeof(struct sdshdr16)的值，那么结果是5个字节，其中没有buf字段。
sdshdr5与其它几个header结构不同，它不包含alloc字段，而长度使用flags的高5位来存储。因此，它不能为字符串分配空余空间。如果字符串需要动态增长，那么它就必然要重新分配内存才行。所以说，这种类型的sds字符串更适合存储静态的短字符串（长度小于32）。 因为长度的范围是5个bit来存储的
sds字符串的header，其实隐藏在真正的字符串数据的前面（低地址方向）。这样的一个定义，有如下几个好处
- header和数据相邻，而不用分成两块内存空间来单独分配。这有利于减少内存碎片，提高存储效率（memory efficiency）。
- 虽然header有多个类型，但sds可以用统一的char *来表达。且它与传统的C语言字符串保持类型兼容。如果一个sds里面存储的是可打印字符串，那么我们可以直接把它传给C函数，比如使用strcmp比较字符串大小，或者使用printf进行打印。
2.2 SDS与C字符串的区别
c语言使用N+1长度的字符数组来表示长度为N的字符串，因为需要增加一个\0 字符终止
2.2.1 常数复杂度获取字符串长度
因为c语言要知道字符串的长度只能遍历数组，所以复杂度为O(N)。
而获取sds的字符串长度，只需要返回len的值就可以了复杂度为O(1)。这样对一个非常长的字符串键反复执行STRLEN命令，也不会对系统性能造成任何影响。
2.2.2 杜绝缓冲区溢出
C字符串不记录自身长度会带来易造成缓冲区溢出的问题。 比如使用strcat函数拼接两个字符串，被拼接的字符串要是没有提前分配空间，就会造成缓冲区溢出。（溢出的字节会导致这个字符串内存紧邻的其他字符串的内容被修改）
而SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能，SDS的API需要修改SDS时，会先检查空间alloc是否满足修改所需的要求。不满足的话会先将空间扩展至修改所需的大小，再执行修改。
2.2.3 减少修改字符串时带来的内存重分配次数
C语言字符串用N+1个字节长的数组来保存N个字节的字符串，因为这个关联性所以每次每次增长或者缩短一个C字符串，都要对这个字符串进行一次内存重分配操作。
- 执行增长操作 比如append，需要首先通过内存重分配来扩展底层数组的空间大小，否则产生缓冲区溢出
- 执行所动操作比如截断操作trime，需要首先通过内存重分配来释放字符串不再使用的空间，否则造成内存泄漏。
内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以通常是一个比较耗时的操作。这对Redis经常用于速度要求严苛，数据被频繁修改的场合来说，是不可接受的。
因此SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联：buf的长度可以大于len的长度。 （4.0版本的源码还未找到对应的函数，所以可能和书上说的有变化了）
空间预分配 ——减少连续执行字符串增长操作所需的内存重分配次数。
用于优化字符串增长操作。
当需要对SDS的空间进行空间扩展时，不仅会对SDS分配修改所必需的空间，还会额外分配未使用空间。
当len < 1Mb时 alloc = 2*len; 当len >= 1 mb时 alloc= len +1Mb。
源码分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/* Enlarge the free space at the end of the sds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen); // 预分配
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);
return s;
}
惰性空间释放
用于优化SDS的字符串缩短操作
缩短SDS保存的字符串时，并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性，将这些字节的数量记录起来，并等待将来使用。
2.2.4 二进制安全
C字符串中的字符必须符合某种编码（如ASCII），除了末尾字符串中间不能有\0 这个空字符，否则最先被程序读取的空字符将被认为是结尾，导致C字符串只能保存文本数据，而不能保存图片、音频、视频、压缩文件这样的二进制数据。
所谓二进制安全：以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，被读取是就是什么样的。因为SDS使用len来判断字符串是否结束。
所以buf是字节数组，而不是字符数组。
2.2.5 兼容部分C字符串函数
因为遵循C字符串以\0结尾的惯例，所以可以兼容<string.h>/strcasecmp ,<stdio.h>/printf 这些函数。但是是否是书上的使用结构体指针还是博客说的可以直接使用sds来调用？还需验证。
书：printf("%s", sds->buf) sds是指向结构体的指针。
博客：https://blog.csdn.net/yangbodong22011/article/details/78419966 :printf(%s, sds)
源码中是直接使用sds
2.2.6 总结
| C字符串 | SDS |
|---|---|
| 获取字符串长度复杂度为O(N) | 获取字符串长度复杂度为O(1) |
| API不安全，可能造成缓冲区溢出 | API安全，不会造成缓冲区溢出 |
| 修改字符串长度N次必然执行N次内存重分配 | 最多执行N次内存重分配 |
| 只能保存文本数据 | 二进制安全文本与二进制数据皆可 |
可使用<string.h>库中所有函数 |
部分使用<string.h>库中函数 |
2.3 SDSAPI
| 函数 | 作用 |
|---|---|
| sdslen(const sds s) | 获取sds字符串长度 O（1） |
| sdssetlen(sds s, size_t newlen) | 设置sds字符串长度 |
| sdsinclen(sds s, size_t inc) | 增加sds字符串长度 |
| sdsalloc(const sds s) | 获取sds字符串容量 |
| sdssetalloc(sds s, size_t newlen) | 设置sds字符串容量。 |
| sdsavail(const sds s) | 获取sds字符串空余空间（即alloc - len） |
| sdsHdrSize(char type) | 根据header类型得到header大小 |
| sdsReqType(size_t string_size) | 根据字符串数据长度计算所需要的header类型。 |
sdsReqType函数源码分析
1 | static inline char sdsReqType(size_t string_size) { |
采用左移来计算对应多少位的范围，而不是用2^5 这样的乘法。直接移位比使用幂来计算快很多。
1<<5 计算出来就是2^5 次方。1是int型，4byte32位。最低8bit位的二进制为：00000001 左移5位后变成了：00100000 对应的十进制既是32。
计算n个bit位的最大值：(1<<n) -1
但是需要注意位数不够的情况。因为1是int型，只有32个bit。所以在左移32个bit时，需要使用long long int型。用1ll来表示，此时1ll为64个bit。
还得考虑机器是否为64位机器，在32位机器上LONG_MAX = 2147483647L，64位机器上LONG_MAX = 9223372036854775807L 。不论32位机器还是64位机器上 LLONG_MAX 都是9223372036854775807L 。所以当LONG_MAX == LLONG_MAX 说明字长为64bit。加上条件编译，说明在32位机器上不使用sdshdr32而直接跳到了sdshdr64，仅仅在64位机器上使用sdshdr32。原因是什么？还没想通
问题
- 为什么Redis需要自己实现字符串功能，而不直接使用c语言的传统字符串？
- 见第二节。
- 执行SET 与GET命令的过程。
char buf[]为什么没有指定大小？一个数组占用的内存大小- 在各个header的定义中最后有一个char buf[]。我们注意到这是一个没有指明长度的字符数组，这是C语言中定义字符数组的一种特殊写法，称为柔性数组（flexible array member），只能定义在一个结构体的最后一个字段上。它在这里只是起到一个标记的作用，表示在flags字段后面就是一个字符数组，或者说，它指明了紧跟在flags字段后面的这个字符数组在结构体中的偏移位置。而程序在为header分配的内存的时候，它并不占用内存空间。如果计算sizeof(struct sdshdr16)的值，那么结果是5个字节，其中没有buf字段。
- 数组内存大小为分配的的长度*数组类型的内存大小
- 为什么redis 在32位机器上不使用sdshdr32？
