Redis系列(一)底层数据结构之简单动态字符串

1,189 阅读9分钟

前言

Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

我读了几本 Redis 相关的书籍,尝试去了解它的具体实现,将一些底层的数据结构及实现原理记录下来。

本文将介绍 Redis 中最基础的 字符串 的实现方法。 它是Redis的字符串键的主要实现方法.

定义

Redis 是使用 C 语言实现的,但是 Redis 中使用的字符串却不是直接用的 C 语言中字符串的定义,而是自己实现了一个数据结构,叫做 SDS(simple dynamic String), 即简单动态字符串。

Redis 中 SDS 数据结构的定义为:

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

一个保存了字符串Redis的 SDS 示例图如下:

2020-01-04-17-10-06

  • len=5, 说明当前存储的字符串长度为 5.
  • free=0, 说明这个结构体实例中,所有分配的空间长度已经被使用完毕。
  • buf 属性是一个 char 类型的数组,保存了实际的字符串信息。

带有 free 空间的 SDS 示例:

2020-01-04-17-14-29

可以看到 len 属性和 buf 属性的已使用部分都和第一个示例相同,但是 free 属性为 5, 同时 buf 属性的除了保存了真实的字符串内容之外,还有 5 个空的未使用空间 ('\0'结束字符不在长度中计算).

优劣

Redis 为什么要这么做呢,或者说使用 SDS 来作为字符串的具体实现结构,有什么好处呢?

那么就不得不提 C 语言本来的字符串了。

C 语言的字符串定义,是使用和字符串相等长度的字符数组来存储字符串,并且在后面额外加一个字符来存储空字符'\0'. 也就是下图:

2020-01-04-17-18-57

这种实现方式的优点就是,简单且直观。但是众所周知,Redis 是一个性能极强的内存数据库,这种实现方式并不能满足 Redis 的性能要求,当然,同时也有一部分的功能性要求无法满足。

后面讲述的每一条优点,都是相对于 C 语言字符串而言的,具体的特性再具体分析。

高性能获取字符串长度

从 C 语言字符串的结构图中,我们可以看到,如果我们想获取一个字符串的长度,那么唯一的办法就是遍历整个字符串。遍历操作需要 O(N) 的时间复杂度。

而 SDS 记录了字符串的长度,也就是 len属性,我们只需要直接访问该属性,就可以拿到当前 SDS 的长度。访问属性操作的时间复杂度是 O(1).

Redis 字符串数据结构的 求长度的命令 STRLEN. 内部即应用了这一特性。无论你的 string 中存储了多长的字符串,当你想求出它的长度时,可以随意的执行 STRLEN, 而不用担心对 Redis 服务器的性能造成压力。

杜绝缓冲区溢出

C 语言的的字符串拼接函数,strcat(*desc, const char *src), 会将第二个参数的值直接连接在第一个字符串后面,然而如果第一个字符串的空间本就不足,那么此时就会产生缓冲区溢出。

SDS 记录了字符串的长度,同时在 API 实现上杜绝了这一个问题,当需要对 SDS 进行拼接时,SDS 会首先检查剩余的未使用空间是否足够,如果不足,会首先扩展未使用空间,然后进行字符串拼接。

因此,SDS 通过记录使用长度及未使用空间长度,以及封装 API, 完美的杜绝了在拼接字符串时容易造成缓冲区溢出的问题。

减少修改字符串产生的内存分配次数,提高修改字符串性能

上面提到,C 语言的字符串实现,是一个长度永远等于 字符串内容长度+1 的字节数组。那么也就意味着,当字符串发生修改,它所占用的内存空间必须要发生更改。

  • 字符串变长。需要首先扩展当前字符串的字节数组,来容纳新的内容。
  • 字符串变短。在修改完字符串后,需要释放掉空余出来的内存空间。

内存分配是比较底层的实现,其中实现比较复杂,且可能执行系统调用,通常情况下比较耗时,Redis 怎么进行对应的优化呢?

  • 空间预分配

SDS 在进行修改之后,会对接下来可能需要的空间进行预分配。这也就是 free 属性存在的意义,记录当前预分配了多少空间。

分配策略:

  1. 如果当前 SDS 的长度小于 1M, 那么分配等于已占用空间的未使用空间,即让 free 等于 len.
  2. 如果当前 SDS 的长度大于 1M, 那么分配 1M 的 free 空间。

在 SDS 修改时,会先查看 free属性的值,来确定是否需要进行空间扩展,如果不需要就直接进行拼接了。

通过预分配策略,SDS 连续增长 N 次,所需要的内存分配次数从绝对 N 次,变成了最多 N 次。

  • 惰性释放内存

当 SDS 进行了缩短操作,那么多余的空间不着急进行释放,暂时留着以备下次进行增长时使用。

听起来预分配和惰性释放是不是很简单的道理?本质上也是使用空间换取时间的操作。而且可能发现了其中的一个问题,那就是在内存紧张的机器上,这样浪费真的好吗?

这个问题,Redis 当然考虑到了,SDS 也提供了对应的 API, 在需要的时候,会自己释放掉多余的未使用空间。

二进制安全

Redis 的字符串是二进制安全的这个特性,我们应该在很多的文章中都看到了。但是它为什么可以做到二进制安全呢?

C 语言的字符串不是二进制安全的,因为它使用空间符'\0'来判断一个字符串的结尾。也就是说,假如你的字符串是 abc\0aa\0 哈哈哈、0, 那么你就不能使用 C 语言的字符串,因为它识别到第一个空字符'\0'的时候就结束识别了,它认为这次的字符串值是'abc\0'.

而二进制中的数据,我们谁也说不好,如果我们存储一段音频序列化后的数据,中间肯定会有无数个空字符,这时候怎么 C 语言的字符串就无能为力了。

而 SDS 可以,虽然 SDS 中也会在字符串的末尾储存一个空字符,但是它并不以这个空字符为判断条件,SDS 判断字符串的长度时使用 len属性的,截取 字节数组 buf 中的前 len 个字符即可。

因此,在 SDS 中,可以存储任意格式的二进制数据,也就是我们常说的,Redis 的字符串是二进制安全的。

兼容部分 C 语言的库函数

上面提到,SDS 使用 len 属性的长度来判断字符串的结尾,但是,却依然遵循了 C 语言的惯例,在字符串结尾的地方填充了一个空字符'\0'.

这样做可以在处理一些纯文本的字符串时,可以方便的沿用一些 C 语言的库函数,而不是自己重新为 SDS 进行开发库函数。

总结

Redis 中使用字符串的大多数场景(键的字符串,字符串数据结构的实际值存储等等)下,都不使用 C 语言的字符串,而是使用 SDS. 简单动态字符串。

它的实现方式是:一个字节数组 buf, 一个当前字符串长度的记录属性 len, 一个当前未使用空间长度属性 free. 字节数组的长度不要求绝对等于字符串值的真实长度,会有一定的缓冲。

相对于 C 语言的字符串,SDS 的优势如下:

C 字符串 SDS
获取字符串长度需要 O(N) 获取字符串长度需要 O(1)
容易造成缓冲区溢出 通过封装 API, 自动变化长度,避免缓冲区溢出
每次修改字符串长度,都需要内存重新分配 最坏情况下,同 C 语言字符串,其他很多情况不需要内存重分配,直接使用预留缓冲即可。
只能保存纯文本 二进制安全,可以保存任意格式的二进制数据
无缝使用所有 C 库函数 可以兼容一部分的 C 库函数

SDS 限制为512M问题

从官网上我们可以得知, Redis的key以及字符串数据结构的值, 最大的大小为 512M.这是官网信息,基本上毋庸置疑.

2020-01-04-19-50-11

让我们试一下:

    public static void main(String[] args) {
        Jedis jedis = new Jedis("localhost");
        jedis.set("test", "test");
        byte[] bytes = new byte[1024 * 1024];
        String str = new String(bytes);
        // 每次加1MB
        for (int i = 0; i < 512; i++) {
            jedis.append("test", str);
        }
    }

Redis会报错, 报错信息为:

Exception in thread "main" redis.clients.jedis.exceptions.JedisDataException: ERR string exceeds maximum allowed size (512MB)
	at redis.clients.jedis.Protocol.processError(Protocol.java:132)
	at redis.clients.jedis.Protocol.process(Protocol.java:166)
	at redis.clients.jedis.Protocol.read(Protocol.java:220)
	at redis.clients.jedis.Connection.readProtocolWithCheckingBroken(Connection.java:309)
	at redis.clients.jedis.Connection.getIntegerReply(Connection.java:260)
	at redis.clients.jedis.Jedis.append(Jedis.java:689)
	at daily.JedisTest.main(JedisTest.java:50)

好的, 坐实了~.

参考文章

《Redis 的设计与实现(第二版)》


完。

联系我

最后,欢迎关注我的个人公众号【 呼延十 】,会不定期更新很多后端工程师的学习笔记。 也欢迎直接公众号私信或者邮箱联系我,一定知无不言,言无不尽。

2020-01-07-11-03-49


以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

**更多学习笔记见个人博客或关注微信公众号 < 呼延十 >------>呼延十**x