现在在高铁上, 赶着春节回家过年, 无座站票, 电脑只能放行李架上, 面对着行李架撸键盘--看过<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类型的数组, 数组的最后一个字节保存了空字符 .
SDS遵循C字符串以空字符串结尾的惯例, 空字符不计入SDS的len属性, 即额外为空字符分配了1字节的空间, 并且添加空字符到字符串末尾均由SDS函数自动完成, 对使用者完全透明. 该特性带来的好处是, SDS可以直接复用C字符串函数库的部分函数.
2. SDS与C字符串的区别
2.1 常数复杂度获取字符串长度
- 由于C字符串不记录自身长度, 所以获取长度时需要遍历整个字符串, 直到遇到空字符 为止, 该操作的复杂度为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/
