Redis高性能的原因分析 - 图1
根据官方数据，Redis 的 QPS 可以达到约 100000（每秒请求数），有兴趣的可以参考官方的基准程序测试《How fast is Redis？》，地址：https://redis.io/topics/benchmarks
2021-09-14-09-19-42-312974.png
横轴是连接数，纵轴是 QPS。此时，这张图反映了一个数量级，希望大家在面试的时候可以正确的描述出来，不要问的时候，回答的数量级相差甚远！

基于内存实现

Redis 是基于内存的数据库，那不可避免的就要与磁盘数据库做对比。对于磁盘数据库来说，是需要将数据读取到内存里的，这个过程会受到磁盘 I/O 的限制。
而对于内存数据库来说，本身数据就存在于内存里，也就没有了这方面的开销。

高效的数据结构

Redis 中有多种数据类型，每种数据类型的底层都由一种或多种数据结构来支持。
Redis高性能的原因分析 - 图3

Redis 整体就是一个 哈希表来保存所有的键值对，无论数据类型是 5 种的任意一种。哈希表，本质就是一个数组，每个元素被叫做哈希桶，不管什么数据类型，每个桶里面的 entry 保存着实际具体值的指针。
2021-09-14-09-19-43-197984.png
整个数据库就是一个全局哈希表，而哈希表的时间复杂度是 O(1)，只需要计算每个键的哈希值，便知道对应的哈希桶位置，定位桶里面的 entry 找到对应数据，这个也是 Redis 快的原因之一。
那 Hash 冲突怎么办？
当写入 Redis 的数据越来越多的时候，哈希冲突不可避免，会出现不同的 key 计算出一样的哈希值。
Redis 通过链式哈希解决冲突：也就是同一个 桶里面的元素使用链表保存。但是当链表过长就会导致查找性能变差可能，所以 Redis 为了追求快，使用了两个全局哈希表。用于 rehash 操作，增加现有的哈希桶数量，减少哈希冲突。
开始默认使用 hash 表 1 保存键值对数据，哈希表 2 此刻没有分配空间。当数据越来多触发 rehash 操作，则执行以下操作：

  1. 给 hash 表 2 分配更大的空间；
  2. 将 hash 表 1 的数据重新映射拷贝到 hash 表 2 中；
  3. 释放 hash 表 1 的空间。

值得注意的是，将 hash 表 1 的数据重新映射到 hash 表 2 的过程中并不是一次性的，这样会造成 Redis 阻塞，无法提供服务。
而是采用了渐进式 rehash，每次处理客户端请求的时候，先从 hash 表 1 中第一个索引开始，将这个位置的 所有数据拷贝到 hash 表 2 中，就这样将 rehash 分散到多次请求过程中，避免耗时阻塞。

1、简单动态字符串

了解 C 语言的都知道，它是有处理字符串方法的。而 Redis 就是 C 语言实现的，那为什么还要重复造轮子？

（1）字符串长度处理

2021-05-11-23-39-52-293479.png
这个图是字符串在 C 语言中的存储方式，想要获取 「Redis」的长度，需要从头开始遍历，直到遇到 ‘\0’ 为止。
Redis高性能的原因分析 - 图6
Redis 中怎么操作呢？用一个 len 字段记录当前字符串的长度。想要获取长度只需要获取 len 字段即可。差距不言自明。前者遍历的时间复杂度为 O(n)，Redis 中 O(1) 就能拿到，速度明显提升。

（2）内存重新分配

C 语言中涉及到修改字符串的时候会重新分配内存。修改地越频繁，内存分配也就越频繁。而内存分配是会消耗性能的，那么性能下降在所难免。而 Redis 中会涉及到字符串频繁的修改操作，这种内存分配方式显然就不适合了。于是 SDS 实现了两种优化策略：

  • 空间预分配

对 SDS 修改及空间扩充时，除了分配所必须的空间外，还会额外分配未使用的空间。
具体分配规则是这样的：SDS 修改后，len 长度小于 1M，那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M，那么将分配1M的使用空间。

  • 惰性空间释放

当然，有空间分配对应的就有空间释放。SDS 缩短时，并不会回收多余的内存空间，而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作，直接使用 free 中记录的空间，减少了内存的分配。

（3）二进制安全

Redis 可以存储各种数据类型，那么二进制数据肯定也不例外。但二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如 ‘\0’ 等。
前面提到过，C 中字符串遇到 ‘\0’ 会结束，那 ‘\0’ 之后的数据就读取不上了。但在 SDS 中，是根据 len 长度来判断字符串结束的。二进制安全的问题就解决了。

2、压缩列表 zipList

当一个列表只有少量数据的时候，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现。
ziplist 是由一系列特殊编码的连续内存块组成的顺序型的数据结构，ziplist 中可以包含多个 entry 节点，每个节点可以存放整数或者字符串。

  1. struct ziplist<T> {
  2.     int32 zlbytes; // 整个压缩列表占用字节数
  3.     int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
  4.     int16 zllength; // 元素个数
  5.     T[] entries; // 元素内容列表，挨个挨个紧凑存储
  6.     int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
  7. }

Redis高性能的原因分析 - 图7
如果要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N)。

3、双端链表

列表 List 更多是被当作队列或栈来使用的。队列和栈的特性一个先进先出，一个先进后出。双端链表很好的支持了这些特性。
Redis高性能的原因分析 - 图8
Redis高性能的原因分析 - 图9
Redis 的链表实现的特性可以总结如下：

  • 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1)。
  • 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为终点。
  • 带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O（1）。
  • 带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O（1）。
  • 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。
quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。
Redis高性能的原因分析 - 图10
这也是为何 Redis 快的原因，不放过任何一个可以提升性能的细节。

4、字典

Redis 作为 K-V 型数据库，所有的键值都是用字典来存储的。
日常学习中使用的字典应该不会陌生，想查找某个词通过某个字就可以直接定位到，速度非常快。这里所说的字典原理上是一样的，通过某个 key 可以直接获取到对应的value。
字典又称为哈希表，这点没什么可说的。哈希表的特性大家都很清楚，能够在 O(1) 时间复杂度内取出和插入关联的值。

5、跳跃表 skipList

作为 Redis 中特有的数据结构—跳跃表，其在链表的基础上增加了多级索引来提升查找效率。
Redis高性能的原因分析 - 图11
这是跳跃表的简单原理图，每一层都有一条有序的链表，最底层的链表包含了所有的元素。这样跳跃表就可以支持在 O(logN) 的时间复杂度里查找到对应的节点。
下面这张是跳表真实的存储结构，和其它数据结构一样，都在头节点里记录了相应的信息，减少了一些不必要的系统开销。
Redis高性能的原因分析 - 图12

6、整数数组（intset）

当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。结构如下：

  1. typedef struct intset{
  2.     //编码方式
  3.     uint32_t encoding;
  4.     //集合包含的元素数量
  5.     uint32_t length;
  6.     //保存元素的数组
  7.     int8_t contents[];
  8. }intset;

contents 数组是整数集合的底层实现：整数集合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。length 属性记录了整数集合包含的元素数量，也即是 contents 数组的长度。

合理的数据编码

对于每一种数据类型来说，底层的支持可能是多种数据结构，什么时候使用哪种数据结构，这就涉及到了编码转化的问题。

  • 待补充

    那就来看看，不同的数据类型是如何进行编码转化的：

    • String：存储数字的话，采用int类型的编码，如果是非数字的话，采用 raw 编码；
    • List：字符串长度及元素个数小于一定范围使用 ziplist 编码，任意条件不满足，则转化为 linkedlist 编码；
    • Hash：Hash 对象的编码可以是 ziplist 或 hashtable。

    当 Hash 对象同时满足以下两个条件时，Hash 对象采用 ziplist 编码：

    • Hash 对象保存的所有键值对的键和值的字符串长度均小于 64 字节。
    • Hash 对象保存的键值对数量小于 512 个。

    否则就是 hashtable 编码。

    • Set：保存元素为整数及元素个数小于一定范围使用 intset 编码，任意条件不满足，则使用 hashtable 编码；
    • Zset：zset 对象中保存的元素个数小于及成员长度小于一定值使用 ziplist 编码，任意条件不满足，则使用 skiplist 编码。

合适的线程模型

Redis 快的原因还有一个是因为使用了合适的线程模型：
Redis高性能的原因分析 - 图13

1、I/O多路复用模型

  • I/O ：网络 I/O
  • 多路：多个 TCP 连接
  • 复用：共用一个线程或进程

生产环境中的使用，通常是多个客户端连接 Redis，然后各自发送命令至 Redis 服务器，最后服务端处理这些请求返回结果。
Redis高性能的原因分析 - 图14
应对大量的请求，Redis 中使用 I/O 多路复用程序同时监听多个套接字，并将这些事件推送到一个队列里，然后逐个被执行。最终将结果返回给客户端。

2、避免上下文切换

一定听说过，Redis 是单线程的。那么单线程的 Redis 为什么会快呢？
因为多线程在执行过程中需要进行 CPU 的上下文切换，这个操作比较耗时。Redis 又是基于内存实现的，对于内存来说，没有上下文切换效率就是最高的。多次读写都在一个CPU 上，对于内存来说就是最佳方案。

3、单线程模型

顺便提一下，为什么 Redis 是单线程的。Redis 中使用了 Reactor 单线程模型，可能对它并不熟悉。没关系，只需要大概了解一下即可。
2021-05-11-23-39-53-603712.png
这张图里，接收到用户的请求后，全部推送到一个队列里，然后交给文件事件分派器，而它是单线程的工作方式。Redis 又是基于它工作的，所以说 Redis 是单线程的。

总结

基于内存实现

  • 数据都存储在内存里，减少了一些不必要的 I/O 操作，操作速率很快。

    高效的数据结构

  • 底层多种数据结构支持不同的数据类型，支持 Redis 存储不同的数据；

  • 不同数据结构的设计，使得数据存储时间复杂度降到最低。

    合理的数据编码

  • 根据字符串的长度及元素的个数适配不同的编码格式。

    合适的线程模型

  • I/O 多路复用模型同时监听客户端连接；

  • 单线程在执行过程中不需要进行上下文切换，减少了耗时。
  1. 纯内存操作，一般都是简单的存取操作，线程占用的时间很多，时间的花费主要集中在 IO 上，所以读取速度快。
  2. 整个 Redis 就是一个全局 哈希表，他的时间复杂度是 O(1)，而且为了防止哈希冲突导致链表过长，Redis 会执行 rehash 操作，扩充 哈希桶数量，减少哈希冲突。并且防止一次性 重新映射数据过大导致线程阻塞，采用 渐进式 rehash。巧妙的将一次性拷贝分摊到多次请求过程后总，避免阻塞。
  3. Redis 使用的是非阻塞 IO：IO 多路复用，使用了单线程来轮询描述符，将数据库的开、关、读、写都转换成了事件，Redis 采用自己实现的事件分离器，效率比较高。
  4. 采用单线程模型，保证了每个操作的原子性，也减少了线程的上下文切换和竞争。
  5. Redis 全程使用 hash 结构，读取速度快，还有一些特殊的数据结构，对数据存储进行了优化，如压缩表，对短数据进行压缩存储，再如，跳表，使用有序的数据结构加快读取的速度。
  6. 根据实际存储的数据类型选择不同编码

    引用

    Redis高性能的原因分析
    Redis 核心