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

Hi,你好,我是猿java。

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

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

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

String的特性

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

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

String常用指令

String 高频指令如下表:

img.png

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

img.png

实现原理

Redis 底层是C语言实现的,但是 Redis的String数据对象并没有直接使用C语言传统的字符串,而是自创了一套SDS,接下来分析它的底层实现。

SDS 结构

SDS,simple dynamic string,简单动态字符串。

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

img.png

  • 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,截图如下:

img.png

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

img.png

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

img.png

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个字节空间并没有计算在SDSlen属性里面。

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

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

img.png

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

img.png

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

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

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

img.png

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

img.png

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

空间预分配

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

  • 剩余的 freespace 足够容纳 target_string 和末尾\0字符,则不作任何操作
  • 剩余的 freespace 不够容纳 target_string 和末尾的\0字符
  • 当target_string_size < 1MB,则会直接分配2 * target_string_size 的空间用于存储字符串
  • 当target_string_size >= 1MB,则会再额外多分配1MB的空间用于存储字符串(target_string_size + 1024*1024)

img.png

惰性空间释放

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

img.png

img.png

SDS 的缺点

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

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

SDS 与 C字符串比较

获取字符串长度复杂度

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

缓冲区溢出

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

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

二进制安全

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

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

两者比较归纳如下表:

img.png

总结

本文从 Redis底层SDSString进行了原理分析,可以说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,所以可以存放图片,视频等二进制数据。

img.png

学习交流

如果你觉得文章有帮助,请帮忙转发给更多的好友,或关注公众号:猿java,持续输出硬核文章。

drawing