Redis 字符串用起来简单,但是原理可是真不简单

本贴最后更新于 1200 天前,其中的信息可能已经天翻地覆

Hello,大家好,我是楼下小黑哥~

无论你现在使用什么编程语言,每天最高频使用的应该就是字符串。可以说字符串对象很基础,也很重要。

那么今天想跟大家聊聊 Redis 字符串相关实现,来看下这个看起来简单的字符串,为什么实现起来确实不简单?

看完这篇文章你可以学到:

  • Redis 字符串对象多种数据结构
  • 底层数据结构转换关系
  • SDS 动态字符串
  • Redis 采用 C 语言实现,那么字符串为什么不直接使用 C 语言的字符串?

Redis 对象

每当我们在 Redis 中保存一对新的键值对时,Redis 至少会创建两个对象,一个对象用作保存键,而另一个对象用作保存值。

Redis 中每个对象都是一个 redisObject 结构,这个结构中有三个属性:

  • type,表示对象的类型
  • encoding,表示编码
  • pstr,指向底层数据结构的指针

type 代表对象类型,目前可以使用类型为:

  • 字符串对象
  • 列表对象
  • 哈希对象
  • 集合对象
  • 有序集合对象

我们可以使用 Redis 的 TYPE 指令,查看当前键对应值对象类型。

Redis 键对象说起来很简单,它总是是一个字符串对象,而值对象就相对复杂了,它可以是字符串,也可以是集合,也可以是字典等对象。

每个对象类型底层实现的时候将会采用了多种数据结构,而 encoding 代表底层数据结构类型:

我们可以使用 Redis 的 OBJECT ENCODING 指令查看一个当前键值对象底层的编码:

每个对象类型,可能支持多种数据结构,关系如下:

Redis 字符串对象

Redis 字符串对象底层支持三种数据结构,分别是(下面使用 OBJECT ENCODING 输出):

  • int
  • embstr
  • raw

int 代表 long 类型的整数,只要字符串对象中保存的是一个整数值,就将会使用 int

这里需要注意,只有整数才会使用 int,如果是浮点数, Redis 内部其实先将浮点数转化为字符串值,然后再保存。

embstrraw 类型底层的数据结构其实都是 SDS (简单动态字符串),Redis 内部定义 sdshdr 一种结构。

那这两者的区别其实在于,embstr 类型将会调用内存分配函数,分配一块连续的内存空间,空间中依次包含 redisObjectsdshdr 两个数据结构。

raw 类型将会调用两次内存分配函数,分配两块内存空间,一块用于包含 redisObject 结构,而另一块用于包含 sdshdr 结构。

SDS 简单动态字符串

接下来我们来看下简单动态字符串。

sdshdr

sds 底层的结构包含三个属性:

  • len,用于记录下面 buf[] 数组已使用的长度,即等于 SDS 所保存的字符串长度
  • free,用于记录下面 buf[] 数组未使用长度
  • buf[],用户保存字符串

这里我们需要注意了,buf[] 数组中最后一个字节将会保存一个空字符 \0,代表字符串结束。sdshdr 结构中的 len 长度是没有包含这个这一个空字符。

这一点设计上与 C 语言的字符串相同。

SDS 扩容

当我们对 SDS 字符串进行增长操作,如果 SDS 空间不足,SDS 将会先进行扩容,然后再执行修改操作。

假设当前 SDS 值如下所示:

现在执行一次字符串拼接指令,

APPEND sds " Cluster"

由于拼接完成之后字符串总长度为 13,SDS 剩余空间不足,所以 SDS 将进行扩容,重新执行一次内存重分配。

由于我们上面的例子,SDS 修改之后的长度(即 len 属性值)小于 1MB,那么程序将会分配和 len 属性同样大小的未使用空间,此时 SDS 中 len 属性与 free 属性值相同。

此时 SDS buf 数组的实际长度为:

13+13+1=27

如果 SDS 修改之后长度大于 1MB,那么 Redis 将会分配 1MB 的未使用空间。

假设进行修改之后,SDS len 属性变为 20MB,那么程序将会分配 1 MB 的未使用空间,此时 SDS buf 数组的实际长度为:

20MB+1MB+1byte

接着上面的例子,如果我们再次执行字符串拼接指令:

APPEND sds " Guide"

这次 SDS 未使用空间足够保存拼接字符串,所以这次不需要重新分配内存。

SDS 惰性空间释放

当我们对字符串进行缩减操作, SDS 字符串值将会被缩短,这样 SDS 剩余空间将会变多。

此时程序不会立即就使用内存分配函数回收多余空间,而是使用 free 属性记录多余空间,等待后面使用。

通过这种惰性空间释放策略,SDS 避免字符串缩短所需内存重分配操作,后续 SDS 字符串增长,可以直接使用多余的空间。

当然 SDS 也有相应的 API,可以真正释放 SDS 未使用的空间,所以不用担心惰性释放策略带来的内存浪费。

为什么 Redis 不直接使用 C 语言字符串?

Redis 底层使用 C 语言编程,那么其实 C 语言也有字符串,Redis 完全可以复用 C 语言字符串~

那么为什么 Redis 还要闭门造车,重新设计一个 SDS 数据结构呢?

这是因为 C 原因这种简单的字符串形式,在安全性,效率以及功能方面不满足 Redis 需求。

首先如果我们需要获取 C 语言字符串的长度,我们可以使用以下函数:

strlen(str)

strlen 函数实际上使用遍历的方式,对每个字符计数,直到遇到代表字符串结束的空字符。

这个操作时间复杂度 O(N)

而 SDS 由于 len 记录当前字符串的长度,所以直接读取即可,时间复杂度仅为 O(1)

这就确保获取字符串长度的操作不会成为 Redis 性能瓶颈。

第二点每次增长或缩短 C 语言的字符串将会进行内存的重分配,否则可能导致缓冲区溢出,也有可能导致内存泄漏。

而 SDS 由于使用空间预分配的策略,如果 SDS 连续增长 N 次,内存重分配的次数从必定 N 次降低为最多 N 次。

第三点,C 语言字符串不能包含空字符,否则第一个空字符将会被误认为字符串结尾,这就大大限制使用的场景。

而 SDS 中由于可以使用 len 属性的值判断字符串是否结束,所以没有这种困扰。

所以 SDS 字符串是二进制安全的。

字符串对象底层数据结构转换

SDS 结构由于需要额外的属性记录长度以及未使用长度,虽然这样减少系统的复杂度,提高了性能,但是还是付出相应的代价,即存在一定内存空间浪费。

所以 Redis 字符串对象底层结构并不都是采用了 SDS。

如果字符串对象保存的是整数值,那么这个整数值将会直接保存在字符串对象结构的 ptr 属性。

如果保存不是整数,但是字符串长度小于等于 39 字节,那么字符串将会使用 embstr 编码方式。
最后上述两个都不满足才会使用 raw 编码方式。

另外,int 编码与 embstr,在一定条件也将会转换为 raw 编码格式。

如果对底层整数执行追加操作,使其不再是一个整数,则字符串对象的编码就会从 int 变为 raw

对于 embstr 编码,实际其实只读的,这是因为 Redis 底层并没有提供任何程序修改 embstr 编码对象。

所以一旦我们对 embstr 编码字符串进行修改,字符串对象的编码就会从 embstr 变为 raw

总结

Redis 字符串是我们平常操作最频繁的数据结构,了解底层字符串对象,对于我们了解 Redis 非常重要的。

Redis 字符串对象底层结构可以分为整数与 SDS,当我们在操作 set 命令保存整数时,就将会直接使用整数。

而 SDS 是 Redis 内部定义另一种结构,相比于 C 语言字符串,它可以快速计算字符串长度,不需要频繁的分配的内存,最终要一点 SDS 是一种二进制安全的字符串。

SDS 设计虽然带来的很多优势,但是这种结构相比于 C 语言,至少多占用 4(len)+4(free)=8 字节内存,如果 buf [] 数组还存在没有使用的空间,空间浪费更加严重。

所以 Redis 字符串不是万金油,某些场景下可能会占用大量内存。但是如果换一种数据结构,可能内存占用就会变少。

所以我们一定要基于合适场景使用合适的数据机构。

站在巨人的肩膀

  1. Redis 设计与实现
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 247 回帖 • 210 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...