1 背景

分布式系统绕不开的核心之一的就是数据缓存，有了缓存的支撑，系统的整体吞吐量会有很大的提升。通过使用缓存，我们把频繁查询的数据由磁盘调度到缓存中，保证数据的高效率读写。 当然，除了在内存内运行还远远不够，我们今天就以具有代表性的缓存中间件Redis为例子，分析下，它是如何达到飞起的效率。

2 Redis高效性能分析

Redis之所以能够提供超高的执行效率，主要从以下几个维度来实现的：

• 存储模式：基于内存实现，而非磁盘
• 数据结构：基于不同业务场景的高效数据结构
  • 动态字符串(REDIS_STRING)：整数(REDIS_ENCODING_INT)、字符串(REDIS_ENCODING_RAW)
  • 双端列表(REDIS_ENCODING_LINKEDLIST)
  • 压缩列表(REDIS_ENCODING_ZIPLIST)
  • 跳跃表(REDIS_ENCODING_SKIPLIST)
  • 哈希表(REDIS_HASH)
  • 整数集合(REDIS_ENCODING_INTSET)
• 线程模型： Redis 的网络 IO 以及键值对指令读写是由单个线程来执行的，避免了不必要的contextswitch和竞选
• I/O 模型： 基于I/O多路复用模型，非阻塞的I/O模型
• 恰单的数据编码： 根据实际数据类型，选择合理的数据编码

2.1 官网的性能报告

Redis官方站点中，有对Redis性能做了比较详细的压测，可以参考官方这一篇 How fast is Redis?， 在较高的配置基准下（比如 8C 16G +），在连接数为0~10000的时候，最高QPS可达到120000。Redis以超过60000个连接为基准，仍然能够在这些条件下维持50000个q/s，体现了超高的性能。下图中横轴是连接数，纵轴是QPS。 下面这张图为data size 与整体吞吐量之间的趋向关系：

这个大概可以得出一个容量预估，比如你的服务用户量是多少，预估峰值QPS是多少，集群需要配置多少个实例（虽然实例的多少不能线性计算），可以大致推算出去。

2.2 基于内存实现

Redis的读写操作都是在内存中实现了，相对其他的持久化存储（如MySQL、File等，数据持久化在磁盘上），性能会高很多。因为在们在操作数据的时候，需要通过 IO 操作先将数据读取到内存里，增加工作成本。

上面那张图来源于网络，可以看看他的金字塔模型，越往上执行效率越高，价格也就越贵。下面给出每一层的执行耗时对比：

• 寄存器：0.3 ns
• L1高速缓存：0.9 ns
• L2高速缓存：2.8 ns
• L3高速缓存：12.9 ns
• 主存：120 ns
• 本地二级存储（SSD）：50~150 us
• 远程二级存储：30 ms 这样可能不直观，我们举个L1和SSD的对比，如果L1耗时1s的话，SSD中差不多要15~45小时。 因为 CPU 内部集成了内存控制器，所以CPU直接控制了内存，给予通信上的最优带宽。上面的部分数据引用自《性能之巅：洞悉系统、企业与云计算》。

2.3 适配多元场景的高效数据结构

在 Redis 缓存中，常用的主要数据类型有五种，如下：

• 字符串/REDIS_STRING：适用于 缓存、计数、共享Session、IP统计、分布式锁等。
• 列表/REDIS_LIST： 链表、消息队列、栈、有序的对象列表（如朋友圈的点赞顺序列表、评论顺序列表）。
• 哈希表/REDIS_HASH： 购物车信息、用户信息、Hash类型的(key, field, value)存储对象等。
• 集合/REDIS_SET：无序的唯一的键值结构： 好友、关注、粉丝、感兴趣的人集合等。
• 有序集合/REDIS_ZSET：访问排行榜、点赞排行、粉丝数排行等。

上面这5种Redis 支持的数据类型，能够满足不同业务场景下的数据结构需求。而对于这几类数据类型的区分和支持，目的无非也是为了效率，具体的业务中使用恰当的数据结构才能保证得到应有的效率。

这5种数据类型都有一种或者多种数据结构来支撑，底层数据结构有 7 种。关系如下： 限免我们对这些数据结构一个个的分析。

2.3.1 SDS 简单动态字符串

Redis使用简单动态字符串（simple dynamic string，SDS）来表示字符串，Redis中字符串类型包含的数据结构有：整数（R_INT） 、 字符串（R_RAW）。我们以字符串为例子，常规的字符串，如 "Brand"，如果要获取他的长度，需要从头开始遍历，直至遇到 \0 空字符代表结尾,如 C字符串。

C 字符串结构与 SDS 字符串结构 对比图 参照如下：

• free属性的值为0，表示这个SDS没有分配任何未使用空间。
• len属性的值为5，表示这个SDS保存了一个5字节长度的字符串。
• buf是一个char类型的数组，存储真实的字符串，数组的前五个字节分别保存了'B'、'r'、'a'、'n'、'd'五个字符，而最后一个字节则保存了空字符'\0'，代表结尾。 注意：SDS遵循C字符串的惯例以空字符结尾，保存空字符的1字节不计算在SDS的len属性中。

比起C字符串，SDS具有以下优点：

1. 度获取字符串长度时间复杂度为O(1) 。 C字符串不记录自身长度，获取C字符串长度时必须遍历整个字符串计数得到，复杂度是O(N) SDS字符串自身记录维护len长度属性，获得SDS字符串长度的复杂度是O(1)

2. 杜绝缓冲区溢出。 C字符串不记录长度，由于两个C字符串在内存存储上紧邻，在执行字符串拼接strcat时，如果不提前分配足够空间，很可能发生修改s1的数据溢出到s2所在的空间中（缓冲区溢出）。 SDS杜绝了缓冲区溢出问题，它记录了长度，当修改SDS字符串之前，API都会检查SDS的空间是否满足修改的要求，不满足API会自动进行空间扩展。

3. 空间预分配，减少修改时的内存重分配次数 SDS 被修改后，程序不仅会为 SDS 分配所需要的空间，还会分配额外的未使用空间。这样，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。 具体分配未使用空间如下2种方式：

• 如修改后长度len小于1MB，就分配和len属性相同大小的未使用空间：free=len。
• 如修改后长度len大于等于1MB，就分配1M的未使用空间：free=1MB。

4. 惰性空间释放 惰性空间释放，缩短操作时：SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。当SDS做缩短操作，不会立刻使用内存重分配来收回缩短后多出来的字节，而是保持在free属性里。将来如果需要 append 操作，则直接使用 free 中未使用的空间，减少了内存的分配步骤。 另外，SDS也提供了API手动进行释放SDS未使用空间，避免惰性释放策略会造成内存浪费。

5. 二进制安全 C字符串的字符必须符合某种编码，除结尾空字符以外，字符串内部不允许有空字符串，存储有局限性。而在 Redis 中，不仅可以存储 String 类型的数据，也可能存储一些二进制数据。 二进制数据并不是规则的字符串格式，其中会包含一些特殊的字符如 '\0'。在 C 中遇到 '\0' 则表示字符串的结束，但SDS不是，它是以len长度标识结尾。

6. 兼容部分C字符串函数。 SDS虽然是二进制安全的，但还是秉承C字符串以空字符结尾的特性，很多函数与C字符串一致不需要重写。

2.3.2 zipList 压缩列表

通过上面的数据结构关系图，可以看出，压缩列表是 List 、Hash、 Set 三种数据类型底层实现之一。 当我们的list列表数据量比较少的时候，且存储的数据轻量的（如小整数值、短字符串）时候， Redis 就会通过压缩列表来进行底层实现。ziplist 是由一系列特殊编码的连续内存块组成的顺序型的数据结构，在列表头有三个字段 zlbytes、zltail 和 zllen，列表中有多个entry，表尾还有一个 zlend，我们来具体拆解下：

• zlbytes：表示列表占用字节数
• zltail：列表尾的偏移量
• zllen：列表尾的偏移量：列表中的 entry 个数
• entry：存储区，可以包含多个节点，每个节点可以存放整数或者字符串。
• zlend：表示列表结束。

参考代码如下：

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

如果查找定位首个元素或最后1个元素，可以通过表头zlbytes、zltail_offset元素快速获取，复杂度是 O(1)。但是查找其他元素时，就没有这么高效了，只能逐个查找下去，比如 entry n 的复杂度就是 O(N)。

2.3.3 linklist 双端列表

Redis List 数据类型经常使用在链表、消息队列、栈、有序的对象列表（如朋友圈的点赞顺序列表、评论顺序列表、关注时间线）等场景，无论是队列（先进先出），还是栈（先进后出），双端列表都能很好的支持。 参考代码如下：

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

Redis 的链表实现的特性可以总结如下：

• 双端：链表节点带有 prev 和 next 指针，获取某个节点的前一节点和后一节点的复杂度都是 O(1)。
• 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为终点。
• 表头指针/表尾指针：通过 list 结构的 head 指针和 tail 指针，获取链表的表头节点和表尾节点的复杂度为 O(1)。
• 链表长度计数器：通过 list 结构的 len 属性来对 list 的链表节点进行计数，获取节点数量的复杂度为O(1)。
• 多态：链表节点使用 void* 指针来保存节点值，并通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。 使用链表的附加空间相对太高，因为64bit系统中指针是8个字节，所以prev和next指针需要占据16个字节，且链表节点在内存中单独分配，会加剧内存的碎片化，影响内存管理效率。 考虑到链表的以上缺点，Redis后续版本对列表数据结构进行改造，使用quicklist代替了ziplist和linkedlist。 作为ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。 这样，性能就的得到了更大的提升。

2.3.4 Hhash 字典

无论何种类型（string、list、hash、set、zset），Redis都是以一个Hash结构的形式来保存键值对的。整体是一个数组，数组中的每个元素都是一个独立的对象，被称为哈系桶，比如图中1 ~ n, 对应的entry保存着实际具体值的指针。 上图中的全局哈希表，它的时间复杂度是 O(1)，只需要计算每个键的哈希值，便知道对应的哈希桶位置，定位桶中的 entry ，并找到对应数据。这个执行效率就很高了。 为了解决可能存在的冲突，采用了链式哈希的做法，也就是同一个桶里面的元素使用链表保存。

2.3.5 intset 整数集合

如果你的集合只有整数值元素，并且数量是轻量的，这时候Redis会使用使用整数集合作为Redis集合的底层数据结构。参考如下代码：

typedef struct intset{
     // 编码格式
     uint32_t encoding;
     // 集合中的元素个数
     uint32_t length;
     // 保存元素数据
     int8_t contents[];
} intset;

我们拆解下：

• encoding： 编码方式
• length： 数组中元素个数，也就是数组的整体长度
• contents[]： 整数集合，集合的每个元素都是数组的一个数组项（item）。具有以下特点：
  • 按值的大小增序排列
  • 不包含任何重复项

2.3.6 skipList 跳跃表

skiplist（即跳跃表）是一种有序数据结构，所以它也是ZSet数据类型中的一种，通过在每个节点中维持多个指向其他节点的指针，达到快速定位的目标。 跳跃表的平均的节点搜索，平均时间复杂度是 O(logN)、最差时间复杂度是 O(N)，还可以通过顺序性操作来批量处理节点。 跳跃表是基于链表的改良，在它基础上，增加了多层级索引，通过索引不断跳转，最终定好位到真实的数据项。这个方式是不是让大家想到b+tree，理念上有点接近，如下图所示： 可以看出，需要获取 68 这个元素需要经历3次查找，需要获取 97则需要经历4次查找。

2.4 单线程模型

Redis 的单线程主要是指Redis的网络IO和键值对读写是由一个线程来完成的，Redis在处理客户端的请求时包括获取 (socket 读)、解析、执行、内容返回 (socket 写) 等都由一个顺序串行的主线程处理，这就是所谓的“单线程”。这也是Redis对外提供键值存储服务的主要流程。 但Redis的其他功能， 比如持久化、异步删除、集群数据同步等等，其实是由额外的线程执行的。 可以这么说，Redis工作线程是单线程的。但是，整个Redis来说，是多线程的。

2.4.1 为何是单线程？

那在主流程中使用单线程，主要是出于什么原因呢？

• 整体吞吐量降低 适当的扩增线程，是为了有效的利用cpu的性能，让它跟内存达到一个利用的最优值。但频繁的Redis读写，如果没有对线程进行有效管理，不但对系统的吞吐量没有提升，反而可能导致下降。

• CPU上下文切换 在运行任务的时候，CPU需要把任务加载到CPU寄存器中进行计算，当切换到其他thread时，需要将当前上下文存储在系统内核中，以便后续重新执行计算时再次加载。 就像你做专心做一件事时，频繁切换，频繁被打断，这个代价是非常高的。 如图中，切换上下文时，我们需要完成一系列工作，save context、switch、restore context等，这种操作越频繁越是耗费资源。

• 共享资源的并发控制问题 引入了程序执行顺序的不确定性，带来了并发读写的一系列问题，增加了系统复杂度。同时可能存在线程切换、甚至加锁解锁、死锁造成的性能损耗。

• 内存才是核心关注点 对于 Redis 框架来说， 主要的性能瓶颈是内存或者网络带宽，而非 CPU。

2.4.2 单线程的好处

1. 避免线程创建过多导致的性能消耗，反而降低整体吞吐能力。
2. 避免上下文切换引起的 CPU 额外的开销。
3. 避免了线程之间的竞争问题，如加锁、解锁、死锁等，都会造成性能损耗。
4. 无需额外考虑多线程带来的程序复杂度，代码更清晰，处理逻辑简单。

2.4.3 单线程是否有效利用CPU

官方这么说

大概意思是，Redis是完全的纯内存操作，执行速度是非常快的，CPU通常不会是瓶颈，因为大多数请求不会是CPU密集型的。参考 Redis真正的性能瓶颈在网络IO，也就是客户端和服务端之间的网络传输延迟，因此Redis选择了单线程的IO多路复用来实现它的核心网络模型。

2.5 I/O 多路复用模型

服务端网络编程常见的 I/O 模型有四种：同步阻塞IO（Blocking IO）、同步非阻塞IO（Non-blocking IO）、IO多路复用（IO Multiplexing）、异步IO（Asynchronous IO）。 Redis 采用的是 I/O 多路复用技术，并发的去处理连接，它的多路复用程序函数有 select、poll、epoll、kqueue。以 epoll （目前最新的也是最好的多路复用技术）函数为例，当客服端执行 read、write、accept、close 等操作命令时，它会将命令封装成一个个事件，然后利用 epoll 多路复用的特性来避免 I/O 阻塞。 下面我们看看普通 I/O 模型 和 Redis的 I/O 多路复模型的的区别，来分析Redis高频请求下如何保持高效执行。

2.5.1 普通 I/O 模型

先来看一下传统的阻塞 I/O 模型到底是如何工作的：当使用 read 或者 write 对某一个文件描述符（File Descriptor：FD)进行读写时，如果当前 FD 不可读或不可写，整个 Redis 服务就不会对其它的操作作出响应，导致整个服务不可用。 这也就是传统意义上的，也就是我们在编程中使用最多的阻塞模型： 阻塞模型虽然开发中非常常见也非常易于理解，但是由于它会影响其他 FD 对应的服务，所以在需要处理多个客户端任务的时候，往往都不会使用阻塞模型。

2.5.2 I/O 多路复用

多路 复用指的是：多个socket连接复用一个线程。这种模式下，内核不会去监视应用程序的连接，而是监视文件描述符。 当客户端发起请求的时候，会生成不同事件类型的套接字。而在服务端，因为使用了 I/O 多路复用技术，所以不是阻塞式的同步执行，而是将消息放入 socket 队列（参考下图的 I/O Multiplexing module），然后通过 File event Dispatcher 将其转发到不同的事件处理器上，如accept、read、send。 综上，我们得出如下特性：

• 单线程模式，内核持续监听 socket 上的连接及数据请求，一监听就交予Redis线程处理，达到单个线程处理多个I/O 流的效果。
• epoll 提供了基于事件的回调机制。不同事件调用对应的事件处理器。Redis可以持续性的高效处理事件，性能同步提升。
• Redis 不阻塞任一客户端发起的请求，所以可以同时和多个客户端连接并处理请求，聚币并发执行的能力。

3 高性能Redis总结

• 基于内存实现，而非磁盘，大都是简单的存取操作，资源主要消耗在 IO 上，所以读取速度快。
• 数据结构：基于不同业务场景的高效数据结构
  • 动态字符串(REDIS_STRING)：整数(REDIS_ENCODING_INT)、字符串(REDIS_ENCODING_RAW)
  • 双端列表(REDIS_ENCODING_LINKEDLIST)
  • 压缩列表(REDIS_ENCODING_ZIPLIST)
  • 跳跃表(REDIS_ENCODING_SKIPLIST)
  • 哈希表(REDIS_HASH)
  • 整数集合(REDIS_ENCODING_INTSET)
• 线程模型：Redis 的网络 IO 以及键值对指令读写是由单个线程来执行的，避免了不必要的contextswitch和竞选
• I/O 模型：基于I/O多路复用模型，非阻塞的I/O模型
• 恰单的数据编码：根据实际数据类型，选择合理的数据编码
• Redis 本身是一个全局 哈希表，他的时间复杂度是 O(1)，另外为了防止哈希冲突导致链表过长，执行 rehash 操作进行扩充，减少哈希冲突。