Redis的设计与实现(1)-SDS简单动态字符串

现在在高铁上, 赶着春节回家过年, 无座站票, 电脑只能放行李架上, 面对着行李架撸键盘--看过这本书, 突然想起, 便整理下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分配空间时多分配一个字节来容纳这个空字符, 以复用库定义的函数.

3. SDS的API

4. 总结

• Redis在大多数情况下使用SDS作为字符串的表示;

• 相比C字符串, SDS具有以下优点:

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

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

以上笔记都是整理自, 真的很感谢作者, 也希望自己能坚持写下去^_^.

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