一. SDS 概述
Redis 没有直接使用 C 语言传统的字符串表示, 而是自己构建了一种名为简单动态字符串 (simple dynamic string, SDS) 的抽象类型, 并将 SDS 用作 Redis 的默认字符串表示. Redis 只会使用 C 字符串作为字面量. 在 Redis 里, 使用 SDS 来表示字符串值, 是一个可以被修改的字符串, 字符串 "键值对" 底层都是由 SDS 实现的.
-- 例 1: 客户端执行如下命令:
- 127.0.0.1:6379> set msg "hello world"
- OK
- 127.0.0.1:6379> get msg
- "hello world"
上面例 1 中就在数据库里创建一个新的键值对. 其中 "键" 是一个字符串对象, 对象的底层实现是一个保存着字符串 "msg" 的 SDS. "键值" 也是一个字符串对象, 对象的底层实现是一个保存着字符串 "hello world" 的 SDS.
-- 例 2: 客户端执行如下命令:
- 127.0.0.1:6379> rpush fruits "apple" "banana" "cherry"
- (integer) 3
- 127.0.0.1:6379> lrange fruits 0 -1
- 1) "apple"
- 2) "banana"
- 3) "cherry"
上面例 2 中也在数据库里创建一个新的键值对. 其中 "键" 是一个字符串对象, 对象的底层实现是一个保存着字符串 "fruits" 的 SDS."键值" 是一个列表对象, 列表包含了三个字符串对象, 分别由三个 SDS 实现.
SDS 除了用来保存数据库中的字符串值之外, 还用作缓冲区(buffer): AOF 模块中的 AOF 缓冲区, 以及客户端状态中的输入缓冲区.
二. SDS 定义
每个 SDS.h 文件下的 sdshdr 结构表示一个 SDS 值, 下面是 Redis 源码, 在 GitHub 的地址是 https://github.com/antirez/sds
- struct sdshdr{
- // 记录 buf 数组中已使用字节的数量, 也就是字符串的长度
- int len ;
- // 记录 buf 数组中未使用字节的数量
- int free;
- // 字节数组, 用于保存字符串
- char buf[];
- }
在 C 语言中使用长度为 N+1 的字符数组来表示长度为 N 的字符串, 并且字符数组最后一个元素总是空字符'\0'. 假设 SDS 的值为 "Redis", 那么 free 属性值为 0, len 属性值为 5, buf 数组为 R,e,d,i,s 五个字符, 最后一个字节则保存空字符'\0' .
三. SDS 与 C 字符串的区别
C 语言使用简单的字符串表示方式, 并不能满足 Redis 对字符串在安全性, 效率以及功能方面的要求, 从几个方面说明:
1. 常数复杂度获取字符串长度
因为 c 字符串并不记录自身的长度信息, 所以为了获取一个 c 字符串的长度, 程序必须遍历整个字符串. 与 C 字符串不同, 因为 SDS 在 len 属性中记录了 SDS 本身的长度, 对于 SDS 的值为 "Redis" 的字节长度就是 5.
2. 杜绝缓冲区溢出
在 c 中, 假设紧邻的字符串 s1 和 s2, s1 保存为 "redis", s2 保存为 "mongodb", 如果修改 s1 的值为 Redis cluster, 但修改之前没了空间, 那么 s1 的数据将溢出到 s2 所在空间中.
在 SDS 中, 会先检查给定的 SDS 空间是否足够, 会自动扩展修改所需的大小空间. 然后在执行实际的修改操作.
3. 减少修改字符串时带来的内存重分配次数
在 c 中, 字符串的底层实现总是一个 N+1 个字符长的数组, 因为字符串的长度和底层数组的长度之间存在着这种关联, 所以每次增长或者缩短一个 c 字符串, 程序都要对保存这个 C 字符串的数组进行一次内存重分配操作.
在 SDS 中通过未使用空间解除了字符串长度和底层数组长度之间的关联, buf 数组的长度不一定就是字符数量加 1, 数组里机可以包含未使用的字节, 这些由 free 属性记录.
3.1 空间预分配
当 SDS 的 API 对一个 SDS 进行操作, 并且需要对 SDS 进行空间扩展的时候, 程序不仅会为 SDS 分配修改所必须要的空间, 还会为 SDS 分配额外的未使用空间. 额外分配的未使用空间数量由以下公式决定:
如果对 SDS 进行修改之后, SDS 的长度(也即是 len 属性的值) 将小于 1MB, 那么程序分配和 len 属性同样大小的未使用空间. 这时 SDS len 属性的值将和 fee 属性的值相同, 例如: 修改之后, SDS 的 len 将变成 13 字节, 那么程序也会分配 13 字节的未使用空间, SDS 的 buf 数组的实际长度将变成 13+13+1=27 字节.
如果对 SDS 进行修改之后, SDS 的 len 大于等于 1MB, 那么程序会分配 1MB 的未使用空间, 如果对 SDS 进行修改之后, SDS 的 len 变成 30MB, 那么程序会分配 1MB 的未使用空间, SDS 的 buf 数组的实际长度为 30MB + 1MB +1byte.
通过空间预分配策略, Redis 可以减少连续执行字符串增长操作所需的内存重分配次数.
3.2 惰性空间释放
惰性空间释放用于优化 SDS 的字符串缩短操作. 当 SDS 的 API 需要缩短 SDS 保存的字符串时, 程序并不立即使用内存重分配来回收缩短多出来的字节, 而是使用 free 属性将这些字节的数据记录起来, 并等待将来使用(缩短后未使用的空间不会释放, 而是将来增长操作时, 再使用这些未使用空间).
4. 二进制安全
在 c 字符串的字符必须符合某种编码(如 ASCII), 并且除了字符串的末尾之处, 字符串里面不能包含空字符, 否则最先被程序读入的空字符将被误以为是字符串的结尾, 这使得 c 字符串只能保存文本数据, 不能保存图片, 音频, 视频, 压缩文件之类的二进制数据.
为了保证 Redis 可以适用各种不同的使用场景, SDS 的 API 都是二进制安全的, 程序不会对其中的数据做任何限制, 过滤, 数据写入是什么, 读取时就是什么.
5. 兼容部分 C 字符串函数
在 SDS 中会遵循 C 字符串以空字符结尾的惯例, 总会为 buf 数组分配空间时多分配一个字节来容纳这个空字符, 这是为了让 SDS 的字符串可以重用一部分(string.h > 库定入的函数.
四 总结
4.1 C 字符串与 SDS 之间的区别总结
C 字符串 | SDS |
获取字符串长度的复杂度为 0(N) | 获取字符串长度的复杂度为 0(1) |
API 是不安全的,可能会造成缓冲区溢出 | API 是安全的,不会造成缓冲区溢出 |
修改字符串长度 N 次必然需要执行 N 次内存重分配 | 修改字符串长度 N 次最多需要执行 N 次内存重分配 |
只能保存文本数据 | 可以保存文本或者二进制数据 |
可以使用所有 & lt;string.h> 库中函数 | 可以使用一部分 & lt;string.h> 库中函数 |
4.2 SDS API(主要的一些 API)
函数 | 作用 |
sdsnew | 创建一个 SDS 字符串 |
sdsempty | 创建一个不包含内容的空 SDS 字符串 |
sdsfree | 释放给定的 SDS 字符串未使用空间 |
sdslen | 返回 SDS 字符串已使用空间字节数 |
sdsavail | 返回 SDS 字符串未使用空间字节数 |
sdsdup | 创建一个给定 SDS 的副本 |
sdsclear | 清空 SDS 字符串内容 |
sdscat | 将给定 c 字符拼接到 SDS 字符串的末尾 |
sdscatsds | 将给定的 SDS 字符串拼接到另一个 SDS 字符串的末尾 |
sdscpy | 将给定的 c 字符拼复制到 SDS 里机,覆盖 SDS 原有字符串 |
sdsgrowzero | 用空字符将 SDS 扩展至指定长度 |
sdsrange | 保留 SDS 指定区间内的数据,不在区间内的数据会被覆盖或清除 |
sdstrim | 接受一个 SDS 和一个 C 字符串作为参数,从 SDS 中移除所有在 C 字符串中出现过的字符 |
sdscmp | 对比两个 SDS 字符串是否相同 |
来源: https://www.cnblogs.com/MrHSR/p/9881986.html