面试过程中经常会被问到「Redis 为什么快？」

因为它是基于内存实现和单线程模型。

很多人仅仅只是知道基于内存实现，其他核心的原因模凌两可。

Redis 为了高性能，从各方各面都进行了优化， Redis 性能为什么如此高，不仅仅只是因为单线程和内存存储。

Part1Redis常用的数据类型

常用的 5 种数据类型和应用场景如下：

• String： 缓存、计数器、分布式锁等。
• List： 链表、队列、微博关注人时间轴列表等。
• Hash： 用户信息、Hash 表等。
• Set： 去重、赞、踩、共同好友等。
• Zset： 访问量排行榜、点击量排行榜等。

Part2Redis到底有多快

Redis采用的是基于内存的采用的是单进程单线程模型的 KV 数据库，由C语言编写，官方提供的数据是可以达到100000+的QPS（每秒内查询次数）。这个数据不比采用单进程多线程的同样基于内存的 KV 数据库 Memcached 差！可以参考官方的基准程序测试《How fast is Redis》（https://redis.io/topics/benchmarks）横轴是连接数，纵轴是QPS。

Part3Redis唯快不破的秘密

主要原因如下：

1完全基于内存实现

Redis 是基于内存的数据库，跟磁盘数据库相比，完全吊打磁盘的速度，就像飞机与脚踏车的区别。对于磁盘数据库来说，首先要将数据通过 IO 操作读取到内存里。

磁盘调用栈

内存操作

内存直接由 CPU 控制，也就是 CPU 内部集成的内存控制器，所以说内存是直接与 CPU 对接，享受与 CPU 通信的最优带宽。

Redis 将数据存储在内存中，读写操作不会因为磁盘的 IO 速度限制，所以速度飞快.

2高效的数据结构

为了追求速度，不同数据类型使用不同的数据结构速度才得以提升。每种数据类型都有一种或者多种数据结构来支撑，底层数据结构有 6 种。

Redis hash 字典

Redis 使用一个哈希表来保存所有的键值对，无论数据类型是 5 种的任意一种。哈希表本质就是一个数组，每个元素被叫做哈希桶，不管什么数据类型，每个桶里面的 entry 保存着实际具体值的指针。

整个数据库就是一个全局哈希表，而哈希表的时间复杂度是 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 分散到多次请求过程中，避免耗时阻塞

SDS 简单动态字符

Redis没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组)，而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型，并将SDS用作Redis的默认字符串表示。

（1）SDS 与 C 字符串区别

C 语言字符串获取长度信息，需要遍历整个字符串时间复杂度为 O(n)，C 字符串遍历时遇到 '\0' 时结束。

SDS 中 len 保存这字符串的长度，O(1) 时间复杂度。

（2）SDS 简单动态字符结构

struct sdshdr {
	int len;  // 记录buf数组中已使用字节的数量 等于SDS所保存字符串的长度
    int free;  // 记录buf数组中未使用的字节数量
    char buf[];
};

Redis 中用一个 len 字段记录当前字符串的长度。想要获取长度只需要获取 len 字段即可。时间复杂度为  O(1) ，速度明显提升。

（3）内存重新分配

C 语言中涉及到修改字符串的时候会重新分配内存。修改地越频繁，内存分配也就越频繁，就会造成性能下降。而 Redis 中 SDS 实现了两种优化策略：

• 空间预分配

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

• 惰性空间释放

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

（4）二进制安全

Redis 可以存储各种数据类型，包括二进制数据。但二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如 '\0' 等。

前面我们提到过，C 中字符串遇到 '\0' 会结束，那 '\0' 之后的数据就读取不上了。但**在 SDS 中，是根据 len 长度来判断字符串结束的。**可以有效的规避这个问题。

双向链表

Redis List 更多是被当作队列或栈来使用的。队列和栈的特性一个先进先出，一个先进后出。双端链表很好的支持了这些特性。常常用作微博关注人时间轴列表等场景。

• 双向链表结构

  双向链表是一个list 结构，组成如下

• head： 指向了双向链表的最开始的一个节点
• tail： 指向了双向链表的最后一个节点
• len： 代表了双向链表节点的数量
• dup： 函数用于复制双向链表节点所保存的值
• free： 函数用于释放双向链表节点所保存的值
• match： 函数用于对比双向链表节点所保存的值和另外一个的输入值是否相等

/* * 双向链表结构 */
typedef struct list {    
    // 表头节点    
    listNode *head;    
    // 表尾节点   
    listNode *tail;   
    // 节点值复制函数    
    void *(*dup)(void *ptr);    
    // 节点值释放函数    
    void (*free)(void *ptr);    
    // 节点值对比函数    
    int (*match)(void *ptr, void *key);    
    // 链表所包含的节点数量    
    unsigned long len;
} list;

• 双向链表结构图

• 前后节点

  /* * 双向链表节点 */
  typedef struct listNode {    
      // 前置节点的指针   
      struct listNode *prev;    
      // 后置节点的指针
      struct listNode *next;    
      // 节点的值    
      void *value;
  } listNode;
  
  

  链表里每个节点都带有两个指针，prev 指向前节点，next 指向后节点。这样在时间复杂度为 O(1) 内就能获取到前后节点。

• 头尾节点

  头节点里有 head 和 tail 两个参数，分别指向头节点和尾节点。这样的设计能够对双端节点的处理时间复杂度降至 O(1) 。同时链表迭代时从两端都可以进行。

压缩列表zipList

• 压缩列表是 List 、hash、 sorted Set 三种数据类型底层实现之一。

如果在一个双向链表节点中存储一个小数据，比如一个字节。那么对应的就要保存头节点，前后指针等额外的数据。这样就浪费了空间，同时由于反复申请与释放也容易导致内存碎片化。这样内存的使用效率就太低了。此时就 用到了压缩列表。

• 当一个列表只有少量数据，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，Redis 就会使用压缩列表来做列表键的底层实现。

• ziplist 是由一系列特殊编码的连续内存块组成的顺序型的数据结构，专门为了提升内存使用效率设计的。所有的操作都是通过指针与解码出来的偏移量进行的。并且压缩列表的内存是连续分配的，遍历的速度很快。

压缩列表zipList 的结构

• ziplist 在表头有三个字段

• zlbytes：列表占用字节数
• zltail：列表尾的偏移量
• zllen：列表中的 entry 个数

• ziplist 中间可以包含多个 entry 节点，每个节点可以存放整数或者字符串。

• 压缩列表在表尾还有一个 zlend，表示列表结束。

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

压缩列表zipList 的结构图

skipList 跳跃表

• sorted set 类型的排序功能便是通过「跳跃表」数据结构来实现。
• 跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，达到快速访问节点的目的。
• 跳跃表支持平均 O(logN)、最坏 O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
• 跳跃表在链表的基础上，增加了多层级索引，通过索引位置的几个跳转，实现数据的快速定位，

跳跃表的简单原理

每一层都有一条有序的链表，最底层的链表包含了所有的元素。这样跳跃表就可以支持在 O(logN) 的时间复杂度里查找到对应的节点。

整数数组（intset）

一、整数集合数据结构定义

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

结构如下：

typedef struct intset{
     //编码方式
     uint32_t encoding;
     //集合包含的元素数量
     uint32_t length;
     //保存元素的数组
     int8_t contents[];
}intset;

参数说明：

• contents：数组是整数集合的底层实现，整数集合的每个元素都是contents数组的一个数组项，各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。
• length：记录了整数集合包含的元素数量，也即是contents数组的长度。
• encoding：决定了contents数组中所有整数的类型，值可为:
• INTSET_ENC_INT16
• INTSET_ENC_INT32
• INTSET_ENC_INT64

二、升级

每当将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合里面。

因为每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(N)。

• 升级并添加新元素过程：
• 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
• 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
• 将新元素添加到底层数组里面。
• 升级的好处：
• 提升灵活性：可随意将整数添加到整数集合中而不必考虑其类型，不会发生类型错误。
• 节约内存：总是使用能容纳集合所有元素的最小类型，只有在需要的时候才会进行升级。
• 升级的局限：整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

3单线程模型

Redis 的单线程指的是 Redis 的网络 IO 以及键值对指令读写是由一个线程来执行的。 对于 Redis 的持久化、集群数据同步、异步删除等都是其他线程执行。

因为 Redis 是基于内存的操作，CPU 不是 Redis 的瓶颈，Redis 的瓶颈最有可能是机器内存的大小或者网络带宽。所以Redis 采用了单线程实现。

多线程的弊端

使用多线程，通常可以增加系统吞吐量，充分利用 CPU 资源。

• 使用多线程后，若是没有良好的系统设计，增加了线程数量，前期吞吐量到达峰值后可能会下降！

• CPU 上下文

  在运行每个任务之前，CPU 需要知道任务在何处加载并开始运行。系统需要帮助它预先设置 CPU 寄存器和程序计数器，这称为 CPU 上下文。CPU 上下文存储在系统内核中，并在重新计划任务时再次加载，非常消耗资源。

• 当多线程并行修改共享数据时，为了保证数据正确，需要加锁机制，带来额外的性能开销，

• 面临的共享资源的并发访问控制问题。

单线程又什么好处

1. 不会因为线程创建导致的性能消耗；
2. 避免上下文切换引起的 CPU 消耗，没有多线程切换的开销；
3. 避免了线程之间的竞争问题，比如添加锁、释放锁、死锁等，不需要考虑各种锁问题。
4. 代码更清晰，处理逻辑简单。

4I/O 多路复用模型

Redis 采用 I/O 多路复用技术，并发处理连接。采用了 epoll + Redis的事件框架。epoll 中的读、写、关闭、连接都转化成了事件，利用 epoll 的多路复用特性降低 IO 的时间。

在了解 IO 多路复用之前，先了解下基本 IO 操作会经历什么。

• 基本 IO 模型

  一个基本的网络 IO 模型，当处理 get 请求，会经历以下过程：

• 和客户端建立建立 accept
  ;
• 从 socket 种读取请求 recv
  ;
• 解析客户端发送的请求 parse
  ;
• 执行 get
  指令；
• 响应客户端数据，也就是 向 socket 写回数据。

其中，bind/listen、accept、recv、parse 和 send 属于网络 IO 处理，而 get 属于Redis指令操作。既然 Redis 是单线程，那么这些操作是在一个线程中依次执行。上述过程中 accept 和 recv 会出现阻塞：，

	**1. accept阻塞：当 Redis 监听到一个客户端有连接请求，但一直未能成功建立起连接时，会阻塞在 accept() 函数这里，导致其他客户端无法和 Redis 建立连接。**

 **2. recv 阻塞：当 Redis 通过 recv() 从一个客户端读取数据时，如果数据一直没有到达，Redis 也会一直阻塞在 recv()。**

• IO 多路复用

  epoll 的基本原理是，内核不是监视应用程序本身的连接，而是监视应用程序的文件描述符。

• 多路指的是多个 socket 连接，

• 复用指的是复用一个线程。

• 多路复用主要有三种技术：select，poll，epoll。

• epoll 是最新的也是目前最好的多路复用技术。

• IO 多路复用基本原理

• 当客户端运行时，它将生成具有不同事件类型的套接字。在服务器端，I / O 多路复用程序（I / O 多路复用模块）会将消息放入队列（socket 队列），然后通过文件事件分派器将其转发到不同的事件处理器。

  即：Redis 单线程情况下，内核会一直监听 socket 上的连接请求或者数据请求，一旦有请求到达就交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个 IO 流的效果。

• select/epoll 提供了基于事件的回调机制，即针对不同事件的发生，调用相应的事件处理器。所以 Redis 一直在处理事件，提升 Redis 的响应性能。

  Redis 线程不会阻塞在某一个特定的监听或已连接套接字上，

  即不会阻塞在某一个特定的客户端请求处理上。所以Redis 可以同时和多个客户端连接并处理请求，从而提升并发性。

5合理的数据编码

每一种数据类型底层的支持可能是多种数据结构，根据字符串的长度及元素的个数适配不同的编码格式，通过编码转化确定什么时候使用哪种数据结构。

不同的数据类型是的编码转化：

• String：存储数字的话，采用int类型的编码，如果是非数字的话，采用 raw 编码；

• List：字符串长度及元素个数小于一定范围使用 ziplist 编码，任意条件不满足，则转化为 linkedlist 编码；

• Hash：hash 对象保存的键值对的键和值字符串长度小于一定值及键值对；

• Set：保存元素为整数及元素个数小于一定范围使用 intset 编码，任意条件不满足，则使用 hashtable 编码；

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

Part4Redis速度快原理总结

• 纯内存操作，避免磁盘 IO，所以读取速度快。

• 整个 Redis 就是一个全局哈希表，他的时间复杂度是 O(1)，

• 为防止哈希冲突导致链表过长，Redis 会执行 rehash 操作，扩充哈希桶数量，减少哈希冲突。
• 为防止一次性重新映射数据过大导致线程阻塞，采用渐进式 rehash。将一次性拷贝分摊到多次请求过程后，避免阻塞。

• Redis 使用的是非阻塞 IO(IO 多路复用)，使用了单线程来轮询描述符，将数据库的开、关、读、写都转换成了事件，Redis 采用自己实现的事件分派器，效率比较高。

• 采用单线程模型，保证了每个操作的原子性，也减少了线程的上下文切换和竞争。

• Redis 全程使用 hash 结构，读取速度快，还有一些特殊的数据结构，对数据存储进行了优化，

• 如压缩表，对短数据进行压缩存储，
• 如跳表，使用有序的数据结构加快读取的速度。

• 根据实际存储的数据类型选择不同编码