当初在高铁上, 赶着春节回家过年, 无座站票, 电脑只能放行李架上, 面对着行李架撸键盘–看过<Redis的设计与实现>这本书, 忽然想起, 便整顿下SDS的内容, 绝对前面的章节, 算是比较简单的~
大多数状况下, Redis应用SDS(Simple Dynamic String, 简略动静字符串)作为字符串示意, 比起C字符串, SDS具备以下长处:
- 常数复杂度获取字符串长度;
- 杜绝缓冲区溢出;
- 缩小批改字符串时带来的内存重调配次数;
- 二进制平安;
- 兼容局部C字符串函数.
以上列举的长处, 也算是这篇文章的次要内容. 先从定义说起吧:
1. SDS的定义
SDS构造定义如下(sds.h/sdshdr):
struct sdshdr {
// 记录buf数组中已应用字节的数量, 等于SDS所保留字符串的长度
int len;
// 记录buf数组中未应用字节的数量
int free;
// 字节数组, 用于保留字符串
char buf[];
}- len属性记录了已应用的字节数量(字符串长度);
- free属性的值为0, 示意这个SDS没有未应用的空间;
- free属性的值为5, 示意这个SDS保留了一个5字节长的字符串;
- buf属性是一个char类型的数组, 数组的最初一个字节保留了空字符\0.
SDS遵循C字符串以空字符串结尾的常规, 空字符不计入SDS的len属性, 即额定为空字符调配了1字节的空间, 并且增加空字符到字符串开端均由SDS函数主动实现, 对使用者齐全通明. 该个性带来的益处是, SDS能够间接复用C字符串函数库的局部函数.
2. SDS与C字符串的区别
2.1 常数复杂度获取字符串长度
- 因为C字符串不记录本身长度, 所以获取长度时须要遍历整个字符串, 直到遇到空字符\0为止, 该操作的复杂度为O(N);
- 因为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调配额定的未应用空间.
额定调配的未应用空间数量, 由以下公式决定:
- 如果对SDS进行批改之后, SDS的长度(即len属性)将小于1MB, 那么程序调配和len属性同样大小的未应用空间, 这时SDS的len属性的值将和free属性的值雷同: 比方批改之后, SDS的len将变成13字节, 那么程序也会调配13字节的未应用空间, buf长度将变成 13Byte + 13Byte + 1Byte = 27Byte;
- 如果对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
| 函数 | 作用 | 复杂度 |
|---|---|---|
| sdsnew | 创立一个蕴含给定C字符串的SDS | O(N), N为给定C字符串的长度 |
| sdsempty | 创立一个不蕴含任何内容的空SDS | O(1) |
| sdsfree | 开释给定的SDS | O(N), N为被开释SDS的长度 |
| sdslen | 返回SDS的已应用空间字节数 | 这个值能够通过读取SDS的len属性来间接取得, 复杂度为O(1) |
| sdsavail | 返回SDS的未应用空间字节数 | 这个值能够通过读取SDS的free属性来间接取得, 复杂度为O(1) |
| sdsdup | 创立一个给定SDS的正本(copy) | O(N), N为给定C字符串的长度 |
| sdsclear | 清空SDS保留的字符串内容 | 因为惰性空间开释策略, 复杂度为O(1) |
| sdscat | 将给定C字符串拼接到另一个SDS字符串的开端 | O(N), N为被拼接C字符串的长度 |
| sdscatsds | 将给定SDS字符串拼接到另一个SDS字符串的开端 | O(N), N为被拼接SDS字符串的长度 |
| sdscpy | 将给定的C字符串复制到SDS外面, 笼罩SDS原有的字符串 | O(N), N为被复制SDS字符串的长度 |
| sdsgrowzero | 用空字符将SDS扩大至给定长度 | O(N), N为扩大新增的字节数 |
| sdsrange | 保留SDS给定区间内的数据, 不在区间内的数据会被笼罩或革除 | O(N), N为被保留数据的字节数 |
| sdstrim | 承受一个SDS和一个C字符串作为参数, 从SDS中移除所有在C字符串中呈现过的字符 | O(N^2), N为给定C字符串的长度 |
| sdscmp | 比照两个SDS字符串是否雷同 | O(N), N为两个SDS钟较短的那个SDS的长度 |
4. 总结
- Redis在大多数状况下应用SDS作为字符串的示意;
- 相比C字符串, SDS具备以下长处:
- 常熟复杂度获取字符串长度;
- 杜绝缓冲区溢出;
- 缩小批改字符串长度时所需的内存重调配次数;
- 二进制平安;
- 兼容局部C字符串函数.
- C字符串和SDS之间的区别:
| C字符串 | SDS |
|---|---|
| 获取字符串长度的复杂度为O(N) | 获取字符串长度的复杂度为O(1) |
| API是不平安的，可能造成缓冲区溢出 | API是平安的，不会造成缓冲区溢出 |
| 批改字符串长度N次必然须要执行N次内存重调配 | 批改字符串长度N次最多需啊哟执行N次内存重调配 |
| 能够应用所有<string.h>库中的函数 | 能够应用一部分<string.h>库中的函数 |
以上笔记都是整顿自<Redis的设计与实现>, 真的很感激作者, 也心愿本人能保持写下去^_^.
文章来源于自己博客，公布于 2018-02-15，原文链接：https://imlht.com/archives/106/
发表回复