首页 > redis > redis中字符串的底层实现-SDS
2017
05-15

redis中字符串的底层实现-SDS

概述

Redis 是用 C 语言开发完成的,但在 Redis 字符串中,并没有使用 C 语言中的字符串,而是用一种称为 SDS(Simple Dynamic String)的结构体来保存字符串

图片.png

struct sdshdr {
    int len;
    int free;
    char buf[];
}

SDS 的结构如上图:

  • len:用于记录 buf 中已使用空间的长度

  • free:buf 中空闲空间的长度

  • buf[]:存储实际内容

例如:执行命令 set key value,key 和 value 都是一个 SDS 类型的结构存储在内存中。

SDS与C字符串的区别

1、常数时间内获得字符串长度

C 字符串本身不记录长度信息,每次获取长度信息都需要遍历整个字符串,复杂度为 O(n);

C 字符串遍历时遇到 ‘\0’ 时结束。

SDS 中 len 字段保存着字符串的长度,所以总能在常数时间内获取字符串长度,复杂度是 O(1)。

2、避免缓冲区溢出

假设在内存中有两个紧挨着的两个字符串,s1=“xxxxx”和 s2=“yyyyy”。

由于在内存上紧紧相连,当我们对 s1 进行扩充的时候,将 s1=“xxxxxzzzzz”后,由于没有进行相应的内存重新分配,导致 s1 把 s2 覆盖掉,导致 s2 被莫名其妙的修改。

但 SDS 的 API 对字符串修改时首先会检查空间是否足够,若不充足则会分配新空间,避免了缓冲区溢出问题。

3、减少字符串修改时带来的内存重新分配的次数

在 C 中,当我们频繁的对一个字符串进行修改(append 或 trim)操作的时候,需要频繁的进行内存重新分配的操作,十分影响性能。

如果不小心忘记,有可能会导致内存溢出或内存泄漏,对于 Redis 来说,本身就会很频繁的修改字符串,所以使用 C 字符串并不合适。而 SDS 实现了空间预分配和惰性空间释放两种优化策略:

1)空间预分配

当 SDS 的 API 对一个 SDS 修改后,并且对 SDS 空间扩充时,程序不仅会为 SDS 分配所需要的必须空间,还会分配额外的未使用空间。

分配规则如下:如果对 SDS 修改后,len 的长度小于 1M,那么程序将分配和 len 相同长度的未使用空间。

举个例子,如果 len=10,重新分配后,buf 的实际长度会变为 10(已使用空间)+10(额外空间)+1(空字符)=21。如果对 SDS 修改后 len 长度大于 1M,那么程序将分配 1M 的未使用空间。

2)惰性空间释放

当对 SDS 进行缩短操作时,程序并不会回收多余的内存空间,而是使用 free 字段将这些字节数量记录下来不释放,后面如果需要 append 操作,则直接使用 free 中未使用的空间,减少了内存的分配。

4、二进制安全

在 Redis 中不仅可以存储 String 类型的数据,也可能存储一些二进制数据。

二进制数据并不是规则的字符串格式,其中会包含一些特殊的字符如 ‘\0’,在 C 中遇到 ‘\0’ 则表示字符串的结束,但在 SDS 中,标志字符串结束的是 len 属性。


本文》有 0 条评论

留下一个回复