Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?

2024年 6月 4日 80.4k 0

使用过 Redis 的小伙伴肯定对 String 这种数据对象并不陌生, 它即可以存放普通的字符串,也可以存放对象,同样可以存图片,视频等二进制数据,使用频次特别高,真可谓是一个万精油。

为什么 Redis 的 String 可以存放这么多类型的数据?Redis 底层到底是如何实现 String 的呢?今天我们就来聊一聊。

申明:本文源码基于redis-6.2。

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-1

一、String的特性 

String 的特性主要包含下面4点:

  • String 是Redis中最基本的数据类型;
  • String 是二进制安全,存入和获取的数据相同;
  • Redis 字符串存储字节序列,包括文本、序列化对象和二进制数组;
  • String 存储的 value值最大为 512MB;

二、String常用指令 

String 高频指令如下表:

指令

举例

说明

set

set key value

设置值

get

get key

获取值

getset

getset key

先获取之前的值,然后设置一个新的值

del

del key

删除key

incr

incr key

从0开始自增1

incrby

incrby key n

自增指定的步长

decr

decr key 

自减1

decrby

decrby key n

自减指定的步长

append

append key

追加内容

如下图,展示了 String常用指令:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-2

三、实现原理 

上文介绍了 String数据对象的一些基础知识,接下来进入核心内容:String 的 Redis 底层实现。

1. SDS 结构

Redis 底层是 C语言实现的,但是 Redis 的 String数据对象并没有直接使用 C语言传统的字符串,而是自创了一套 SDS,用于 Redis 默认字符串表示。SDS(simple dynamic string),简单动态字符串。

SDS 的结构定义在 sds.h 文件中,每个 sds.h/sdshdr 结构表示一个 SDS 值,在 Redis 3.2 版本之后,SDS 由一种数据结构变成了 5 种数据结构,如下源码截图:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-3

  • sdshdr5:存储大小为 32 byte = 2^ 5 ,被弃用;
  • sdshdr8:存储大小为 256 byte = 2^ 8;
  • sdshdr16:存储大小为 64KB = 2 ^16
  • sdshdr32:存储大小为 4GB = 2^ 32;
  • sdshdr64:存储大小为 2^ 64;

5 种数据结构存储不同长度的内容,Redis 会根据 SDS 存储的内容长度来选择不同的结构,源码实现对应 sds.c/sdsReqType,截图如下:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-4

为了对 SDS 有一个更好的体感,这里以 sdshdr8 为例,执行指令:SET name Redis

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-5

执行上述 set 指令后,值对象对应的 SDS 结构如下图:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-6

SDS 各个属性说明:

  • len:表示 buf 已用空间的长度,占 4 个字节,不包括 \0;
  • alloc:表示 buf 的实际分配长度,占 4 个字节,不包括 \0;
  • flags:标记当前字节数组是 sdshdr8/16/32/64 中的哪一种,占 1 个字节;
  • buf:表示字节数组,保存实际数据。为了表示字节数组的结束,Redis 会自动在数组最后加一个\0,需要额外占用 1 个字节的开销;

从上面 SDS 的结构可以看出,SDS 依然遵循了 C语言中字符串以 \0 结尾的规则, 但是,\0占用的1 个字节空间并没有计算在 SDS 的 len 属性里面。

分析完 SDS 的结构,我们会问,SDS 在 Redis 中是如何存放的呢?

因为 Redis 的数据类型有很多(String、List、Set、Hash等等),不同数据类型会包含相同的元数据,所以值对象并不是直接存储,而是被包装成 redisObject 对象(源码位于 server.h中),其定义如下图:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-7

所以,SDS 在 Redis Server 端的存储如下图:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-8

另外,为了节省内存空间,Redis 还做了如下优化:

  • 当保存 Long 类型整数,RedisObject 中的指针直接赋值为整数数据,这样就不用额外的指针指向整数。这种方式称为 int 编码方式。
  • 当保存字符串数据,且字符串小于等于 44 字节时,RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域,这样可以避免内存碎片。这种方式称为 embstr 编码方式。
  • 当保存字符串数据,且字符串大于 44 字节时,Redis 不再把 SDS 和 RedisObject 放在一起,而是给 SDS 分配独立的空间,并用指针指向 SDS 结构。这种方式称为 raw 编码模式。

下图为 int、embstr 和 raw 这三种编码模式的对比:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-9

如果想查看一个值对象是采用哪种编码模式,可以使用 OBJECT ENCODING((大小写不敏感)命令,下面给了几个示例截图:

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-10

到此,SDS 的实现原理分析完成,需要补充的是:Redis 官方为了保证 String 的性能,在 SDS 设计上采用了两个非常优秀的设计:空间预分配 和 惰性空间释放。

2. 空间预分配

在对 SDS 进行修改操作时(追加字符串,拷贝字符串等),通常会调用 sds.c/sdsMakeRoomFor 方法对 SDS 的剩余容量进行检查,如有必要会对 SDS 进行扩容,当计算修改之后字符串(用target_string表示)的目标长度之后分以下几种情况:

(1)剩余的 freespace 足够容纳 target_string 和末尾\0字符,则不作任何操作

(2)剩余的 freespace 不够容纳 target_string 和末尾的\0字符

  • 当target_string_size < 1MB,则会直接分配2 * target_string_size 的空间用于存储字符串
  • 当target_string_size >= 1MB,则会再额外多分配1MB的空间用于存储字符串(target_string_size + 1024*1024)

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-1

3. 惰性空间释放

当 SDS 字符串缩短时, 空余出来的空间并不会直接释放,而是会被保留,等待下次再次使用,字符串缩短操作需要更新 sdshdr 头中的 Len 字段以及alloced buffer中的\0字符的位置,如下源码截图,在更新字符串长度的过程中并没有涉及到内存的重分配策略,只是简单的修改sdshdr 头中的 Len 字段。

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-12

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-13

四、SDS 的缺点 

从上面 SDS 的结构可以看出,SDS 除了存储 String 的内容外,还需要额外的内存空间记录数据长度、空间使用等信息,这个就导致了 SDS 的一个比较大的缺点:占内存。那么有什么更好的数据结构呢?我们下篇文章会进行分析。

不过,计算机领域很多时候都在空间和时间上的一种权衡。而Redis String 这种浪费内存换取读写速度就是一个很好的体现。

五、SDS 与 C字符串比较 

1. 获取字符串长度复杂度

C字符串不记录长度,获取长度必须遍历整个字符串,复杂度为O(N),SDS 在 len 属性中记录了 SDS 本身的长度, 获取 SDS 长度的复杂度为 O(1) ;

2. 缓冲区溢出

C字符串不记录自身的长度,每次增长或缩短一个字符串,都要对底层的字符数组进行一次内存重分配操作。如果在 append 操作之前没有通过内存重分配来扩展底层数据的空间大小,就会产生缓存区溢出;如果进行 trim 操作之后没有通过内存重分配来释放不再使用的空间,就会产生内存泄漏;

SDS 通过未使用空间解除了字符串长度和底层数据长度的关联,3.0版本用 free属性记录未使用空间,3.2版本用 alloc属性记录总的分配字节数量。通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化的空间分配策略,解决了字符串拼接和截取的空间问题;

3. 二进制安全

C 字符串以 \0结尾(即 以 \0判断字符串结束),所以在 C字符串的内容里面不能包含 \0,否则会被认为是字符串结尾,因此,C字符串只能保存文本数据,不能保存像图片这样的二进制数据;

而 SDS 的 API 会以处理二进制的方式来处理存放在 bu f数组里的数据,不会对里面的数据做任何的限制。SDS 使用 len 属性来判断字符串是否结束,而不是空字符。

两者比较归纳如下表:

C字符串

SDS

获取字符串长度复杂度为O(N)

获取字符串长度复杂度为O(1)

API是不安全的,可能会造成缓冲区溢出

API是安全的,不会造成缓冲区溢出

修改字符串长度必然需要内存重分配

修改字符串长度 N次最多需要执行 N次内存重分配

只能保存文本数据

可以保存文本或二进制数据

可以使用所有库中的函数

可以使用一部分库中的函数

六、总结

本文从 Redis的底层 SDS 实现分析了 String 的实现原理,可以说 SDS 是一种很优秀的设计,它即遵循了C语言的部分功能,又规避了 C语言 字符串常见的一些问题,这或许就是 Redis 优秀的一个原因。

另外,SDS 为了保证读写速度,尽管做了很多节省内存的操作(比如:sdshdr8/16/32/64,int/embstr/raw),但是,还在是一定程度上采用空间换时间。

通过 SDS 的设计,我们可以看出:在程序的世界里没有“银弹”,每种数据结构似乎总有其擅长的场景以及不足之处,这也正是各种数据结构百花齐放的原因。

最后,回答文章开头的问题,为什么Redis String可以存放图片,视频?

我们把 SDS的结构抽象如下图,尽管 String也是以 \0结尾,但是,因为 SDS 有 len 属性来记录 String 值的内容长度(used space),所以在获取数据时只需要按照 len 获取内容,而无需遍历 String内容,所以也就不用担心内容中有\0 异常结束String,所以可以存放图片,视频等二进制数据。

Redis 为什么不直接使用C语言的 string,而是重新造了个 SDS ?-14

相关文章

Oracle如何使用授予和撤销权限的语法和示例
Awesome Project: 探索 MatrixOrigin 云原生分布式数据库
下载丨66页PDF,云和恩墨技术通讯(2024年7月刊)
社区版oceanbase安装
Oracle 导出CSV工具-sqluldr2
ETL数据集成丨快速将MySQL数据迁移至Doris数据库

发布评论