Redis为什么快？基于内存就完事了？无视Redis如此完美的数据结构，设计师表示已经哭晕在了厕所里

心已赠人 2022-12-24 07:56 94阅读 0赞

**原创博文，欢迎转载，转载时请务必附上博文链接，感谢您的尊重。本文参照《Redis设计与实现》（黄健宏 著）**

# 前言 #

Redis 是面试官考察的重点，因为它的确是生产上经常使用的技术。它的优点很多，其中有一点尤为重要，也是绕不开要提的，**就是“快”！！**

我想，稍微了解一点 Redis 的都知道它常用的五种数据类型：string，list，set，sorted set，hash。

再深一点的问，Redis 为什么是单线程的？又为什么快？底层存储？持久化策略？雪崩？击穿？并发？分布式？... 一套组合拳下来，有木有稍微触及到你的知识盲区？

![2020112715252717.jpg][]

考点太多啦，但这些都不是我要解释的，O(∩\_∩)O哈哈~~。

想了解《Redis常见面试题》的同学，不要慌，请看我的另一篇博文：敬请期待

就Redis为什么快而言，绝不是一句“单线程+基于内存”就可以解释清楚的。我今天就想带大家摸一摸面试官的天花板，了解面试官究竟想要什么。

喜欢干货的同学，好好学习本篇就OK了。有兴趣研读**原著**的，我在百度云盘为大家分享了**《Redis设计与实现》**电子书（永久有效）：

链接：[https://pan.baidu.com/s/1GCSTZDVd4vpcyqbEMlpttQ ][https_pan.baidu.com_s_1GCSTZDVd4vpcyqbEMlpttQ]  
提取码：omcc

--------------------

# 一、Redis为什么快？ #

单线程+基于内存？可以，没毛病，下面重点补充一些你可能不知道的。

Redis 是由 C 语言编写的，C 语言如此完善一定是有自己传统的字符串，但是 Redis 却弃之不用（并非完全不用，下面有解释），而是自己构建了一种名为简单动态字符串（simple dynamicstring,SDS）的抽象类型，并将 SDS 用作 Redis 的默认字符串使用。

*  当 Redis 需要的不仅仅是一个字符串字面量（string literal），而是一个可以被修改的字符串时，就会使用 SDS 来表示字符串的值；
 *  而原本的 C 语言字符串只会作为字符串字面量，用在一些无须对字符串值进行修改的地方，比如，打印日志：redisLog(REDIS\_WARNING,"Redis is so fast...")。

举个例子，如果客户端执行命令：

redis> set msg "hello world"
    OK

那么，Redis将在数据库中创建一个新的键值对，包含2个SDS，其中：

*  键：是一个可修改的字符串对象，对象的底层实现是一个保存着字符串"msg"的SDS；
 *  值：也是一个可修改的字符串对象，对象的底层实现是一个保存着字符串"hello world"的SDS；

基本同理：如果值的类型是List，也就是列表对象包含多个字符串对象，每个对象分别由SDS保存value。

除此之外，SDS还被用作缓冲区（buffer）：AOF模块中的AOF缓冲区，客户端状态中的输入缓冲区。

静下来来捋一捋，Redis在存储上使用SDS而弃用C的字符串，说明SDS和C的字符串肯定有不同之处，而这个不同决定了Redis更快。所以，解释“Redis为什么快”，已经变成解释“SDS为什么比C的字符串快”，没错吧。带着这样的疑问，接着往下看。

--------------------

# 二、SDS的定义 #

**借助源码**，我们先分析下 SDS（sds .h/sdshdr）的结构：

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

**参数解释：**

*  len：记录 buf\[\] 数组中已经使用字节的数量（等于 SDS 所保存字符串的长度）；
 *  free：记录 buf\[\] 数组中未使用字节的数量；
 *  buf\[\]：字符数组，用于保存字符串；

举个例子，展示下 SDS 的结构（"Hello为例"）：

![20201130154956446.png][] 图 2-1

**上图模型的含义：**

该 SDS 内保存了字符长度（len）为5，未使用空间长度（free）也为0的 char 数组（ buf），数组的前五个字节分别保存了'H'，'e'，'l'，'l'，'o'五个字符，而最后一个字节保存了空字符'\\0'。

保存空字符'\\0'的1个字节空间不计算在 SDS的 len 属性中，而是为空字符分配额外的1字节空间，此操作由 SDS 函数自动完成。

**解释下：为什么 SDS 最后一个字节保存了空字符 '\\0'**

Redis 是基于 C 语言写的，SDS 遵循 C 字符串以空字符结尾的惯例，是为了直接重用一部分 C 字符串函数库里的函数，而无需单独开发一套。这是一个非常用心，且十分讨巧的设计。

--------------------

# 三、SDS 之于 C 字符串的优势 #

Redis 是由 C 语言编写的，例如它们一样遵循空字符结尾的惯例，所以 SDS 兼容了很多很多 C 字符串的函数，避免了不必要的代码浪费。

鉴于我们讨论的是“Redis为什么快？”的问题，所以接下来只论证下SDS 之于 C 字符串的优势：

**1.降低计数复杂度**

这个事情比较好解释，我们还是以上面的 **图 2-1 为例**：

C语言使用长度 N+1 的字符数组来表示长度为 N 的字符串，但是C语言又并不会记录自身的长度信息，所以，当需要获取一个 C 字符串长度时，程序就必须遍历整个字符串，这个操作的时间复杂度为O(N)。

而对于 SDS 来说，程序只需要访问 len 属性就可以了，因为 SDS 在 len 属性中记录了字符串的长度，而设置和更新 SDS 长度的工作是由 SDS 的 API 自动完成的，无需进行任何手动修改长度的工作，所以获取一个 SDS 长度的时间复杂度为O(1)。

通过使用 SDS 而不是 C 字符串，Redis将获取字符串长度的时间复杂度从 O(N) 降低到了 O(1)，这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。

## 2.杜绝缓冲区溢出 ##

在3.1 中已经提到：C语言又并不会记录自身的长度信息。这就会带来一个问题——缓冲区（buffer overflow）溢出。

举个例子，假设程序中有两个在内存中紧挨着的 C 字符串空间 s1 和 s2，其中 s1 保存了字符串 "Redis"， s1 保存了字符串 "MySql"，如图 3-1 所示。

![20201130160230528.png][] 图 3-1

如果一个程序员想要获取“Redis NoSQL”，而执行命令：

>>> strcat(s1, "NoSql");

可是，他忘记了在执行 strcat 命令之前为 s1分配足够的空间，那么在执行 strcat 函数之后，s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改，如图3-2 所示。

![20201130160253731.png][] 图 3-2

与 C 字符串不同，SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：

当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行所需的大小。

例如，我们对 **图 2-1** 的“Redis”执行拼接操作：

>>> sdscat(s, "Mysql");

![20201130164013594.png][] 图 3-3

注意，SDS 的 sdscat 命令不仅对“Redis”进行了拼接操作，拼接之后的字符串长度是10，它还为 SDS 分配了额外的未使用空间（free），并且该空间大小也正好是10字节。这种结果并不是BUG，更不是巧合，它和 SDS 的空间分配策略有关，这就引出了下面 SDS 的另一个优势——减少字符串修改时内存重分配的次数。

## 3.减少字符串修改时内存重分配的次数 ##

同样是因为 C 字符串不记录自身长度，它的长度和底层数组之间存在着关联性，所以每次增长或者缩短一个 C 字符串，程序都会对保存这个 C 字符串的数组进行一次内存的重新分配：

*  如果程序执行的是拼接（append）操作，那么在执行该操作之前，程序需要先通过内存的重分配来【扩展】底层数组的空间大小——如果忘了这一步，就会产生缓存区溢出；
 *  如果程序执行的是截断（trim）操作，那么在执行该操作之前，程序需要先通过内存的重分配来【释放】底层数组的空间大小——如果忘了这一步，就会产生内存泄漏；

为了避免这种缺陷，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关系：

在 SDS 中，buf 数组的长度不一定就是所含的字符数量加一，数组里面也可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录。

通过未使用空间，SDS 实现了“空间与分配”和“惰性空间释放”两种优化策略：

*  **空间预分配：**用于优化 SDS 的字符串增长操作（图 3-3所示），当 SDS 的 API 对一个 SDS 进行修改时，并且需要空间扩展时，程序不仅会为 SDS 分配必须的空间，还会分配额外的未使用空间（具体分配公式：见书P13），以此来减少Redis连续执行增长操作所需的内存重分配次数；
 *  **惰性空间释放：**用于优化 SDS 的字符串缩短操作（图 3-4所示），当 SDS 的 API 需要缩短保存的字符串时，程序并不会立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，以备不时之需；

与此同时，SDS 也提供了相应的 API，让我们可以在需要的时候，真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放侧罗会造成内存浪费。

![20201130171130451.png][] 图 3-4

## 4.二进制安全 ##

C 字符串中的字符必须符合某种编码比如（ASCII），并且除了字符串的末尾意外，里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串的结尾。这些限制使得 C 字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

例如，图 3-5 中所示的字符串就不能用 C字符串来保存，因为 C 字符串只能识别其中的“Redis”，而忽略之后的所有内容。

![20201130172624284.png][] 图 3-5

通过二进制安全的 SDS，而不是 C 字符串，使得 Redis 不仅仅可以保存文本数据，还可以保存任意格式的二进制数据。

--------------------

# 总结 #

对 Redis SDS 和 C 字符串之间的区别进行了总结：

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;vertical-align:middle;">C字符串</th> 
   <th style="text-align:center;vertical-align:middle;">SDS</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>获取字符串长度的复杂度<span style="color:#f33b45;">O(N)</span></td> 
   <td>获取字符串长度的复杂度<span style="color:#f33b45;">O(1)</span></td> 
  </tr> 
  <tr> 
   <td>API是不安全的，<span style="color:#f33b45;">可能</span>会造成缓冲区溢出</td> 
   <td>API是安全的，<span style="color:#f33b45;">不会</span>造成缓冲区溢出</td> 
  </tr> 
  <tr> 
   <td>修改字符串长度N次，<span style="color:#f33b45;">必须</span>要执行N次内存重分配</td> 
   <td>修改字符串长度N次，<span style="color:#f33b45;">最多</span>要执行N次内存重分配</td> 
  </tr> 
  <tr> 
   <td>只能保存<span style="color:#f33b45;">文本</span>数据</td> 
   <td>可以保存<span style="color:#f33b45;">文本</span>或者<span style="color:#f33b45;">二进制</span>数据</td> 
  </tr> 
  <tr> 
   <td>可以使用<span style="color:#f33b45;">所有</span>&lt;string.h&gt;库中的函数</td> 
   <td>可以使用<span style="color:#f33b45;">一部分</span>&lt;string.h&gt;库中的函数</td> 
  </tr> 
 </tbody> 
</table>

--------------------

**我是IT无知君，您的点赞、评论和关注，才是我不懈创作的动力！！  
学无止境，气有浩然，让我们一起加油，乘风破浪，江湖有缘再见。**

[2020112715252717.jpg]: /images/20221120/76a469871d7f482aaf85f3d6b4d0f27d.png
[https_pan.baidu.com_s_1GCSTZDVd4vpcyqbEMlpttQ]: https://pan.baidu.com/s/1GCSTZDVd4vpcyqbEMlpttQ%C2%A0
[20201130154956446.png]: /images/20221120/81d0e83b03784a20a1cdc5348e06bd30.png
[20201130160230528.png]: https://img-blog.csdnimg.cn/20201130160230528.png
[20201130160253731.png]: https://img-blog.csdnimg.cn/20201130160253731.png
[20201130164013594.png]: https://img-blog.csdnimg.cn/20201130164013594.png
[20201130171130451.png]: https://img-blog.csdnimg.cn/20201130171130451.png
[20201130172624284.png]: https://img-blog.csdnimg.cn/20201130172624284.png