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

发表于 分类于 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 3 分钟

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

分析完 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底层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，所以可以存放图片，视频等二进制数据。

img.png

学习交流

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

drawing