关于redis:Redis的设计与实现1SDS简单动态字符串

当初在高铁上, 赶着春节回家过年, 无座站票, 电脑只能放行李架上, 面对着行李架撸键盘 – 看过 <Redis 的设计与实现 > 这本书, 忽然想起, 便整顿下 SDS 的内容, 绝对前面的章节, 算是比较简单的~

大多数状况下, Redis 应用 SDS(Simple Dynamic String, 简略动静字符串)作为字符串示意, 比起 C 字符串, SDS 具备以下长处:

1. 常数复杂度获取字符串长度;
2. 杜绝缓冲区溢出;
3. 缩小批改字符串时带来的内存重调配次数;
4. 二进制平安;
5. 兼容局部 C 字符串函数.

以上列举的长处, 也算是这篇文章的次要内容. 先从定义说起吧:

1. SDS 的定义

SDS 构造定义如下(sds.h/sdshdr):

struct sdshdr {
    // 记录 buf 数组中已应用字节的数量, 等于 SDS 所保留字符串的长度
    int len;
    // 记录 buf 数组中未应用字节的数量
    int free;
    // 字节数组, 用于保留字符串
    char buf[];}

1. len 属性记录了已应用的字节数量(字符串长度);
2. free 属性的值为 0, 示意这个 SDS 没有未应用的空间;
3. free 属性的值为 5, 示意这个 SDS 保留了一个 5 字节长的字符串;
4. buf 属性是一个 char 类型的数组, 数组的最初一个字节保留了空字符 \0.

SDS 遵循 C 字符串以空字符串结尾的常规, 空字符 不计入 SDS 的 len 属性 , 即 额定为空字符调配了 1 字节的空间 , 并且 增加空字符到字符串开端均由 SDS 函数主动实现, 对使用者齐全通明. 该个性带来的益处是, SDS 能够间接复用 C 字符串函数库的局部函数.

2. SDS 与 C 字符串的区别

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

1. 因为 C 字符串不记录本身长度, 所以获取长度时须要遍历整个字符串, 直到遇到空字符 \0 为止, 该操作的复杂度为 O(N);
2. 因为 SDS 在 len 属性中记录了 SDS 自身的长度, 所以获取一个 SDS 的长度的复杂度为 O(1).

Redis 应用 SDS, 将获取字符串长度所需的复杂度从 O(N)升高到 O(1), 确保获取字符串长度的工作不会成为 Redis 的性能瓶颈.

2.2 杜绝缓冲区溢出

因为 C 字符串不记录本身长度, 以函数 strcat 来说, 当执行该函数时, 都是认为曾经为 dest 调配了足够的内存包容 src 字符串, 但如果该假如不成立, 就会产生缓冲区溢出.

然而, SDS 的字符串空间调配策略, 从根本上杜绝了缓冲区溢出的可能性: 当 SDS-API 须要对 SDS 进行批改时, API 会先查看 SDS 的空间是否满足批改所需的需要, 如果不满足的话, API 会主动扩容至所需大小, 再执行批改操作. 所以, SDS 无需手工保护 SDS 的空间大小, 也不会产生缓冲区溢出的问题.

2.3 缩小批改字符串时带来的内存重调配次数

因为 C 字符串不记录本身长度, 所以每次增长或缩减字符串, 须要对保留这个 C 字符串的数组进行一次内存重调配操作:

1. 如果程序执行的是 增长 字符串的操作, 比方拼接操作 append, 须要进行内存重调配操作, 扩大底层数组至适合大小, 否则将会产生 缓冲区溢出 ;
2. 如果程序执行的是 缩短 字符串的操作, 比方截断操作 trim, 须要进行内存开释操作, 否则将会产生 内存泄露.

Redis 作为数据库, 常常用于速度要求严苛, 数据被频繁批改的场合, 缩小内存的重调配次数能进步性能. SDS 通过未应用空间解除了 字符串长度 和底层数组 长度之间的关联: 在 SDS 中, buf 数组的长度不肯定就是字符数加一, 数组外面能够蕴含未应用的字节, 而这些字节的数量就由 SDS 的 free 属性记录.

通过未应用空间, SDS 实现了空间预调配和惰性空间开释两种优化策略.

1. 空间预调配

当 SDS-API 对 SDS 进行批改, 并且须要对 SDS 进行空间扩大的时候, 程序不仅会为 SDS 调配批改所需的空间, 还会为 SDS 调配额定的未应用空间.

额定调配的未应用空间数量, 由以下公式决定:

1. 如果对 SDS 进行批改之后, SDS 的长度 (即 len 属性) 将小于 1MB, 那么程序调配和 len 属性同样大小的未应用空间, 这时 SDS 的 len 属性的值将和 free 属性的值雷同: 比方批改之后, SDS 的 len 将变成 13 字节, 那么程序也会调配 13 字节的未应用空间, buf 长度将变成 13Byte + 13Byte + 1Byte = 27Byte;
2. 如果对 SDS 进行批改之后, SDS 的长度将大于等于 1MB, 那么程序会调配 1MB 的未应用空间: 比方批改之后, SDS 的 len 将变成 30MB, 那么程序会调配 1MB 的未应用空间, buf 长度将变成 30MB + 1MB + 1Byte.

通过空间预调配策略, Redis 能够缩小间断执行字符串增长操作所需的内存重调配次数.

2. 惰性空间开释

惰性空间开释用于优化 SDS 的字符串缩短操作: 当 SDS-API 须要缩短 SDS 字符串时, 程序并不会立刻回收内存, 而是应用 free 属性将这些字节的数量记录起来, 并期待未来应用.

当然, SDS 也提供了相应的 API 真正地开释 SDS 的未应用空间, 无需放心该策略带来的内存节约问题.

2.4 二进制平安

C 字符串除了开端, 不能蕴含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾, 所以 C 字符串只能保留文本数据, 而不能保留像图片, 音频, 视频, 压缩文件这样的二进制数据.

Redis 为了能够实用于各种不同的场景, SDS-API 都是二进制平安的(binary-safe), 所有 SDS-API 都会以二进制的形式解决 buf 数组外面的数据, 不限度, 不过滤, 不假如, 写入什么就读到什么.

2.5 兼容局部 C 字符串函数

尽管 SDS-API 是二进制平安的, 但它们一样遵循 C 字符串以空字符结尾的常规: 这些 API 总是将 SDS 保留的数据开端数组为空字符, 并且总会在为 buf 调配空间时多调配一个字节来包容这个空字符, 以复用 <string.h> 库定义的函数.

3. SDS 的 API

4. 总结

• Redis 在大多数状况下应用 SDS 作为字符串的示意;
• 相比 C 字符串, SDS 具备以下长处:

1. 常熟复杂度获取字符串长度;
2. 杜绝缓冲区溢出;
3. 缩小批改字符串长度时所需的内存重调配次数;
4. 二进制平安;
5. 兼容局部 C 字符串函数.

• C 字符串和 SDS 之间的区别:

以上笔记都是整顿自 <Redis 的设计与实现 >, 真的很感激作者, 也心愿本人能保持写下去 ^_^.

文章来源于自己博客，公布于 2018-02-15，原文链接：https://imlht.com/archives/106/