【Redis】 简单动态字符串
【Redis】 简单动态字符串
Metadata
title: 【Redis】 简单动态字符串
date: 2023-07-09 08:28
tags:
- 行动阶段/完成
- 主题场景/数据存储
- 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
- 细化主题/数据存储/Redis
categories:
- 数据存储
keywords:
- 数据存储/Redis
description: 【Redis】 简单动态字符串
概述
Redis 中，涉及可以被修改的字符串值时，都用简单动态字符串（simple dynamic string，SDS）来实现。比如包含字符串值的键值对在底层的实现。C 字符串（C 语言中传统字符串，以空字符串结尾的字符数组）则用于无须对字符串进行修改的地方，比如日志打印。
SDS 还被用作缓冲区，比如 AOF 模块中的 AOF 缓冲区，客户端状态中的输入缓冲区。
Redis只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS（Simple Dynamic String，简单动态字符串）作为字符串表示。
比起C字符串，SDS具有以下优点：
- 常数复杂度获取字符串长度。
- 杜绝缓冲区溢出。
- 减少修改字符串长度时所需的内存重分配次数。
- 二进制安全。
- 兼容部分C字符串函数。
SDS 定义
struct sdshdr{
//buf已使用的字节数
int len;
//buf未使用的字节数
int free;
//字节数组，用于保存字符串
char buf[];
}
buf 遵循 C 字符串以空字符串结尾的惯例，保存空字符串的 1 字节空间不计算在 SDS 的 len 属性里面，并为空字符分配额外 1 字节空间，对用户来说是透明的。
如中展示了 SDS 的数据结构，5 字节未使用空间，已使用 5 字节，buf 存储了字符串值，最后一个字节保存了空字符'\0'。这里要注意的是，free 和 len 的计算不涉及空字符。
SDS 与 C 字符串的区别
- SDS 有常数级的时间复杂度获取字符串长度。
由于 C 字符串不会记录自身长度，因此只能遍历，直到遇到结尾的空字符为止, 时间复杂度为 O(N)。而 SDS 对于字符串长度的记录都是在其 API 中执行的，所以时间复杂度为 **O(1)**。 - SDS 杜绝缓冲区溢出。
由于 C 字符串未记录自身长度，容易导致缓冲区溢出。在执行字符串拼接时，如果没有足够的空间，并且相邻内存地址被其他字符串占用时，字符串的数据将溢出，且容易意外修改相邻的字符串内容。相比而言，SDS 会将这种情况扼杀在摇篮之中，SDS API 先判断空间是否满足，如果不满足则将空间扩展至执行修改所需的大小。 - SDS 拥有内存分配策略，详见 1.3。
- SDS API 都是二进制安全的。
C 字符串的字符必须符合某种编码，并且中间不能有空字符，否则读取时会被误以为是字符串结尾。种种局限使得 C 字符串只能存文本，不能存图片，音频，视频，压缩文件等二进制数据。 为确保 Redis 对不同使用场景的支持，SDS API 都是二进制安全的，也就是所有 SDS API 都会以二进制的方式存取 buf 中的数据，数据的写入和读出都是一个样的。由于 SDS 读取时并不是依靠空字符来判断结束的，而是 len 属性，所以是二进制安全的。 - 兼容部分 C 字符串函数。
SDS 虽然都是二进制安全的，但也遵循以空字符结尾的习惯。SDS API 总会在 buf 数组分配空间时多分配一个字节用于容纳空字符，这是为了保存文本的 SDS 重用一部分 <string.h> 库函数，避免代码重复。
内存分配策略
由于 C 字符并不记录自身长度，并且需要一个字符空间保存空字符串，因此每次增长或缩短字符串时，就要对其进行一次内存重分配操作。增长字符串时要看空间是否够用，否则会有缓冲区溢出；缩短字符串要释放不用的空间，否则会有内存泄漏。
Redis 经常被用于速度要求严苛，数据被频繁修改的场合，每次修改字符串都要重新分配内存，就会占用很多时间。为避免这个问题，redis 采用了空间预分配和惰性空间释放两种策略。
空间预分配
空间预分配用于优化 SDS 字符串增长操作。在扩展 SDS 空间前，SDS API 会先检查未使用空间够不够，如果不够，则进行空间预分配。此时，程序不仅会为 SDS 分配修改所必须要的空间，还为其分配额外未使用的空间。
- 修改后的 SDS<1MB，程序分配和 len 属性同样大小的未使用空间，此时 SDS 的 len 与 free 大小相等。比如修改后实际存储字符串的空间变为 13 字节，那么 len=13，free=13，buf 数组整体的长度 = 13+13+1（额外 1 字节保存空字符）。
- 修改后 SDS>=1MB。程序会分配 1MB 的未使用空间。比如修改后实际存储字符串的空间变为 2MB，那么 len=2M，free=1MB，buf 数组整体的长度 = 2MB+1MB+1byte。
通过空间的预分配，将连续增长 N 次字符串需要的内存分配次数从一定需要 N 次变为最多 N 次。因而可以减少连续执行字符串增长操作所需的内存重分配的次数。
惰性空间释放
惰性空间的释放用于优化 SDS 字符串缩短操作。当 SDS API 需要缩短保存的字符串时，程序并不立即回收这部分内存，而是使用 free 属性将字节的数量记录，等待使用。与此同时，SDS 提供了相关 API，在有需要时，真正释放未使用空间，不需要担心惰性空间造成的内存浪费。
C 字符串与 SDS 的区别简单来说：
| C字符串 | SDS |
|---|---|
| 获取字符串长度的复杂度为O(N) | 获取字符串长度的复杂度为O(1) |
| “API是不安全的,可能会造成缓冲区溢出” | API是安全的,不会造成缓冲区溢出 |
| 修改字符串长度N次必然需要执行N次重分配 | 修改字符串长度N次最多需要执行N次重分配 |
| 只能保存文本数据 | 可以保存文本或二进制数据 |
| 可以使用所有<string.h>库中的函数 | 可以使用一部分<string.h>库中的函数 |
SDS 时间复杂度
SDS 相关操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| 创建/释放/拷贝一个的SDS | “O(N),N为C字符串长度” |
| 清空SDS内容 | “情性空闫释放,O(1)” |
| 给定C字符率拼接到SDS尾部 | “O(N),N为被拼接字符串长度” |
SDS API
| 函 数 | 作 用 | 时间复杂度 |
|---|---|---|
| sdsnew | 创建一个包含给定C字符串的 SDS | “O(N),N为给定C字符串的长度” |
| sdsempty | 创建一个不包含任何内容的空 SDS | O(1) |
| sdsfree | 释放给定的 SDS | “O(M),N为被释放SDS的长度” |
| sdslen | 返回SDS的已使用空间字节数 | “这个值可以通过读取 SDS 的len属性来 直接获得,复杂度为 0(1)” |
| sdsavail | 返回SDS 的未使用空间字节数 | “这个值可以通过读取 SDS 的free属性 来直接获得,复杂度为 0(1)” |
| sdsdup | 创建一个给定 SDS的副本( copy ) | “O(M),N为给定 SDS的长度” |
| sdsclear | 清空SDS保存的字符串内容 | “因为惰性空间释放策略,复杂度为O(1)” |
| sdscat | 将给定C字符串拼接到SDS字符串的末尾 | “O(M),N为被拼接C字符串的长度” |
| sdscatsds | 将给定SDS字符串拼接到另一个SDS字符串 的末尾 | “O(N),N为被拼接SDS字符串的长度” |
| sdscpy | “将给定的C字符串复制到 SDS里面,覆盖 SDS原有的字符串” | “O(M),N为被复制C字符串的长度” |
| sdsgrowzero | 用空字符将SDS扩展至给定长度 | “O(N),N为扩展新增的字节数” |
| sdsrange | “保留SDS给定区间内的数据,不在区间内的 数据会被覆盖或清除” | “O(N),N为被保留数据的字节数” |
| sdstrim | “接受一个SDS和一个C字符串作为参数,从 SDS中移除所有在C字符串中出现过的字符” | “O(N),N为给定C字符串的长度” |
| sdscmp | 对比两个SDS字符串是否相同 | “O(M),N为两个SDS 中较短的那个 SDS 的长度” |
wechat
alipay