高效的数据结构Redis的底层数据结构一共有6种（一）

前言

说起目前主流的NoSql数据库，莫过于Redis。由于其读写速度极快，一般用于缓存热点数据以加快查询速度。想必大家在工作中都和Redis打过交道，但至于Redis为什么快，除了八谷文的背诵，似乎还没有特别深入。学习。

今天让我们深入了解一下Redis：

高效的数据结构

Redis的底层数据结构有6种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳转表和整数数组。它们与数据类型的对应关系如下图所示：

本文暂不列出，后续将对以上所有数据结构进行源码级深入分析。

单线程 vs 多线程

多线程与单线程

在学习计算机操作系统的时候，你一定遇到过这个问题：多线程一定比单线程快吗？相信官员们不会像上面那个愚蠢的哪吒一样落入敖丙的圈套。

多线程有时比单线程快，但也有很多时候不如单线程快。首先，用一个3岁的孩子都能看懂的图来解释并发和并行的区别：

并发：是指只能同时执行一条指令，但多条进程指令依次快速执行，这样在宏中就有了多进程同时执行的效果，但不是同时执行同时在微。只需将时间分成几段，这样多个进程就可以快速交替执行。

并行：指同时在多个处理器上同时执行多条指令。所以无论从微观还是宏观上看，两者都是一起执行的。

不难发现，只有一条指令同时并发执行，但进程（线程）在CPU中快速切换，速度极快，给人的感觉是“同时运行” ”。实际上，同时只执行一条指令。但实际上，如果我们在应用程序中使用多线程，在线程和上下文切换之间进行轮换需要花费大量时间。

他

说话很便宜，给我看代码

以下代码演示了串行和并发执行和累积操作的时间：

公共类并发测试{

私人静态最终长计数= 1000000000；

公共静态无效主要（字符串[]参数）{

尝试 {

并发（）；

} 捕捉（InterruptedException e）{

e.printStackTrace();

}

串行（）；

}

私有静态无效并发（）抛出 InterruptedException {

长开始 = System.currentTimeMillis();

线程 thread = new Thread(new Runnable() {

@覆盖

公共无效运行（）{

整数a = 0；

for (long i = 0; 我

{

一个+= 5；

}

}

});

线程.start();

诠释 b = 0;

for (long i = 0; 我

b–;

}

线程.join();

长时间 = System.currentTimeMillis() – 开始；

System.out.println(“并发：” + time + “ms,b=” + b);

}

私人静态无效序列（）{

长开始 = System.currentTimeMillis();

整数a = 0；

for (long i = 0; 我

{

一个+= 5；

}

诠释 b = 0;

for (long i = 0; 我

b–;

}

长时间 = System.currentTimeMillis() – 开始；

System.out.println(“序列号：” + time + “ms,b=” + b);

}

}

执行时间如下表所示。不难发现，当累加操作的并发执行不超过一百万次时，速度会比累加操作的串行执行慢。

由于线程创建和上下文切换的开销，并发执行会比串行慢。

上下文切换

多个线程可以在单核或多核 CPU 上执行。单核 CPU 还支持多线程代码执行。CPU 通过为每个线程分配 CPU 时间片（机会）来实现这种机制。为了执行多个线程，CPU需要不断地切换执行线程，以保证所有线程在一段时间内都有机会被执行。

此时，CPU分配给每个线程的执行时间段称为其时间片。CPU时间片一般为几十毫秒。CPU通过时间片分配算法循环执行任务，当前任务执行一个时间片并切换到下一个任务。

但是在切换之前会保存上一个任务的状态，这样下次切换回这个任务时可以重新加载这个任务的状态。所以任务从保存到重新加载的过程就是一个上下文切换。

根据多线程的运行状态：在多线程环境中，当一个线程的状态从Runnable转换为non-Runnable（Blocked、Waiting、Timed_Waiting）时，对应线程的上下文信息（包括CPU寄存器以及程序计数器在某个时间点的内容等）需要保存，以便之后对应的线程再次进入Runnable状态时，可以在之前的执行进度的基础上继续。并且从非可运行状态进入可运行状态的线程可能涉及恢复先前保存的上下文信息。这种保存和恢复线程上下文的过程称为上下文切换。

基于记忆

以 MySQL 为例，MySQL 的数据和索引是永久存储在磁盘上的，所以当我们使用 SQL 语句执行查询命令时，如果目标数据库的索引还没有加载到内存中，我们首先要加载索引进入内存，然后通过多次寻址和磁盘I/O将数据对应的磁盘块加载到内存中，最后读取数据。

如果是机械硬盘，那么首先需要找到数据所在的位置，也就是需要读取的磁盘地址。看看这张图：

磁盘结构图

要读取硬盘上的数据，第一步是找到所需的磁道。轨道是以中心轴为中心的环形。首先，我们需要找到需要对齐的磁道，并将磁头移动到对应的磁道上。这个过程称为seek。

然后，我们需要等到磁盘旋转，让磁头指向我们需要读取的数据的起始位置。这里花费的时间称为旋转延迟。通常我们讲的硬盘的速度，主要影响这里花费的时间，而这个旋转的方向是单向的。如果错过了数据的开头，则必须等到盘片旋转到下一轮才能开始读取。

最后，磁头开始读取并记录磁盘上的数据。这个原理其实类似于光盘的读取原理。由于磁道上有一层磁介质，当磁头扫过特定位置时，磁头会感应到不同位置的磁态。磁信号被转换成电信号。

可以看出，无论是磁头的运动还是磁盘的转动，本质上都是一种机械运动，这也是为什么这种硬盘被称为机械硬盘的原因，机械运动的效率是磁盘读写的瓶颈。

有点扯远了，让我们回到redis。如果像 Redis 一样将数据存储在内存中，直接读写数据库，自然比硬盘数据库少。从磁盘读取数据的步骤，而这一步恰恰是计算机处理I/O的瓶颈。

读取内存中的数据本质上是电信号的传输，比机械运动要快得多。

硬盘数据库读取过程

内存数据库读取过程

所以，可以负责任的说Redis这么快，当然与其基于内存的操作有很大关系。然而，这远非全部原因。

Redis 常见问题

面对单线程的Redis，你可能又会有疑问了：敖丙，我的多核CPU不行了！不用担心，Redis 已经专门回答了这个问题。

CPU 成为 Redis 的性能瓶颈的情况并不少见，因为 Redis 通常受到内存或网络的限制。例如，在 Linux 系统上使用流水线 Redis 甚至每秒可以处理 100 万个请求，因此如果您的应用程序主要使用 O(N) 或 O(log(N)) 命令，它几乎不会消耗太多 CPU。

但是，为了最大限度地提高 CPU 利用率，您可以在同一个节点中启动多个 Redis 实例，并将它们视为不同的 Redis 服务。在某些情况下，单个节点可能还不够，所以如果你想使用多个 CPU，你可以开始考虑一些早期的分片方法。

您可以在分区页面上找到有关使用多个 Redis 实例的更多信息。

然而，在 Redis 4.0 中，我们开始让 Redis 更加线程化。目前这仅限于在后台删除对象，以及通过 Redis 模块实现的阻塞命令。对于未来的版本，我们的计划是让 Redis 越来越多线程。

注意：我们一直说的Redis单线程，在处理我们的网络请求时，只有一个线程处理。正式的 Redis Server 运行时，线程肯定不止一个！

比如Redis在持久化的时候，会fork一个子进程来执行持久化操作。

四种 IO 模型

当一个网络IO发生时（假设是读），它涉及到两个系统对象，一个是调用IO的进程，另一个是系统内核。

当一个读操作发生时，它会经历两个阶段：

①等待数据准备；

②将数据从内核复制到进程中。

为了解决网络IO中的问题，提出了4种网络IO模型：

阻塞 IO 模型

非阻塞IO模型

多路复用 IO 模型

异步 IO 模型

阻塞和非阻塞的概念描述了用户线程如何调用内核 IO 操作：阻塞意味着 IO 操作需要完全完成才能返回用户空间；非阻塞是指IO操作被调用后立即返回一个状态值给用户，不需要等到IO操作完全完成。

阻塞 IO 模型

在 Linux 中，默认情况下所有套接字都被阻止。典型的读操作如下图所示：

当应用进程调用recvfrom系统调用时，系统内核开始IO的第一阶段：准备数据。

对于网络IO来说，在很多情况下，当数据一开始还没有到达时（比如一个完整的TCP包还没有收到），系统内核不得不等待足够多的数据到达。在用户进程端，整个进程都会被阻塞。

当系统内核等到数据准备好时，会将数据从系统内核复制到用户内存中，然后系统内核返回结果，用户进程就会被解除阻塞，重新运行。因此，阻塞 IO 模型的特点是 IO 执行的两个阶段（等待数据和复制数据）都是阻塞的。

非阻塞IO模型

在 Linux 中，可以通过设置套接字使 IO 变为非阻塞。当对非阻塞套接字进行读操作时，读操作流程如下图所示：

从图中可以看出，当用户进程发出读操作时，如果内核中的数据没有准备好，它不会阻塞用户进程，而是立即返回错误。

从用户进程的角度来看，它发起读操作后，不需要等待，而是立即得到结果。当用户进程判断结果是错误时，就知道数据还没有准备好，所以可以再次发送读操作。

一旦内核中的数据准备好，再次接收到来自用户进程的系统调用，它立即将数据复制到用户内存中，并返回正确的返回值。

因此，在非阻塞IO中，用户进程实际上需要主动询问内核数据是否准备好。非阻塞接口和阻塞接口之间的显着区别在于它在被调用后立即返回。

多路复用 IO 模型

IO 的多路复用，有时称为事件驱动 IO（Reactor 设计模式）。它的基本原理是一个函数会不断地轮询它负责的所有套接字。当某个套接字有数据到达时，它会通知用户进程。复用IO复用模型的流程如图：

当用户进程调用select时，整个进程会被阻塞，同时内核会“监控”所有select负责的socket。当任何套接字中的数据准备好时，select 将返回。这时，用户进程再次调用读操作，将数据从内核拷贝到用户进程。

这个模型和阻塞 IO 模型没有太大区别，实际上更糟。因为这里需要用到两个系统调用（select和recvfrom），而阻塞IO只调用了一个系统调用（recvfrom）。但是，使用 select 的好处是可以同时处理多个连接。因此，如果系统中的连接数不是很高，使用select/epoll的web服务器不一定比使用多线程阻塞IO的web服务器好，延迟可能更大；select/epoll 的好处不是单个Connections可以处理得更快，而是可以处理更多的connections。

如果select()发现句柄捕获到了一个“可读事件”，服务端程序要及时执行recv()操作，根据接收到的数据准备好要发送的数据，并将对应的句柄值添加到writefds中为“可写事件”的下一次 select() 检测做准备。同样，如果 select() 发现句柄捕获到了一个“可写事件”该内存不能为read 要终止程序，程序应该及时进行 send() 操作，为下一次“可读事件”检测做准备。

下图展示了一个事件驱动的工作模型。当产生不同的事件时，处理程序会感知并执行相应的事件，就像多路复用器一样。

IO 多路复用是最常用的 IO 模型，但它的异步性并不“彻底”，因为它使用了阻塞线程的 select 系统调用。因此，IO复用只能称为异步阻塞IO，而不是真正的异步IO。

异步 IO 模型

“真”异步IO需要操作系统更强的支持。下面展示了异步IO模型（Proactor设计模式）的运行过程：

用户进程发起读操作后，可以立即开始做其他事情；另一方面，从内核的角度来看，当它接收到异步读请求操作时，会先立即返回，所以不会影响用户进程。产生任何阻塞。

然后该内存不能为read 要终止程序，内核将等待数据准备好，然后将数据复制到用户内存中。当这一切都完成后，内核会向用户进程发送一个信号，返回读操作已经完成的信息。

IO 模型总结

调用blocking IO会阻塞对应的进程，直到操作完成，而non-blocking IO会在内核还在准备数据的时候立即返回。

两者的区别在于同步IO在执行IO操作时会阻塞进程。按照这个定义，前面提到的阻塞IO、非阻塞IO、复用IO都是同步IO。其实真正的IO操作就是例子中的recvfrom系统调用。

当非阻塞IO执行recvfrom系统调用时，如果内核的数据没有准备好，此时进程不会被阻塞。但是当内核中的数据准备好时，recvfrom会将数据从内核复制到用户内存中，此时进程被阻塞。

异步 IO 不同。当进程发起IO操作时，直接返回，直到内核发出信号告诉进程IO已经完成。在整个过程中，进程完全没有被阻塞。

各IO模型对比如下图所示：

Redis 中的应用

Redis服务器是一个事件驱动的程序，服务器需要处理以下两类事件：

文件事件：Redis服务器通过socket连接到客户端（或其他Redis服务器），文件事件是服务器对socket操作的抽象。服务器与客户端（或其他服务器）的通信会产生相应的文件事件，服务器通过监听和处理这些事件来完成一系列的网络通信操作。

时间事件：Redis服务器中的一些操作（如serverCron）函数需要在给定的时间点执行，时间事件是服务器对此类定时操作的抽象。

I/O 多路复用器

Redis的I/O多路复用程序的所有功能都是通过封装了select、epoll、evport、kqueue等常用的多路复用函数库来实现的。

因为 Redis 为每个 I/O 复用库实现了相同的 API，所以 I/O 复用程序的底层实现是可以互换的。

Redis 在 I/O 多路复用程序的实现源码中用#include 宏定义了相应的规则。程序在编译时会自动选择系统中性能最高的I/O复用函数库作为Redis的I/O复用函数库。/O 多路复用器的底层实现（ae.c 文件）：

/* 包括本系统支持的最佳多路复用层。

* 以下应按表演顺序，降序排列。*/

#ifdef HAVE_EVPORT

#include “ae_evport.c”

＃别的

#ifdef HAVE_EPOLL

#include “ae_epoll.c”

＃别的

#ifdef HAVE_KQUEUE

#include “ae_kqueue.c”

＃别的

#include “ae_select.c”

＃万一

＃万一

＃万一

文件事件处理程序

Redis 基于 Reactor 模式开发了自己的网络事件处理程序：这个处理程序称为文件事件处理程序：

文件事件处理程序使用 I/O 多路复用器同时侦听多个套接字，并根据套接字当前正在执行的操作为套接字关联不同的事件处理程序。

当被监控的socket准备好执行accept、read、write、close等操作时，会产生该操作对应的文件事件。这时，文件事件处理器会调用socket之前关联的事件处理器来处理这些事件。

下图展示了一个文件事件处理器的四个组成部分：套接字、I/O多路复用器、文件事件分派器（dispatcher）和事件处理器。

文件事件是套接字操作的抽象。每当套接字准备好执行连接回复、写入、读取、关闭等操作时，都会生成文件事件。因为服务器通常连接了多个套接字，所以可能同时发生多个文件事件。I/O 多路复用器负责侦听多个套接字并将那些生成事件的套接字传递给文件事件分派器。

哪吒问的问题很好。想想看。生活中，一群人去食堂吃饭的时候，阿姨说得最多的一句话就是：排队！排队！一个都没有！

是的，一切都来自生活！Redis 的 I/O 多路复用器总是将所有产生事件的 socket 放入一个队列中，然后通过这个队列将文件事件以有序、同步、一次一个 socket 的方式发送到文件中。调度程序传输套接字。I/O 多路复用器不会继续将下一个套接字传递给文件事件分派器，直到前一个套接字生成的事件已被处理。

Redis 为文件事件处理程序编写了多个处理程序，用于实现不同的网络通信需求：

为了回复每个连接到服务器的客户端，服务器必须为监听套接字关联一个连接回复处理程序；

为了接受来自客户端的命令请求，服务器必须为客户端套接字关联命令请求处理程序；

为了将命令的执行结果返回给客户端，服务器必须为客户端套接字关联命令回复处理程序；

当主从服务器执行复制操作时，主从服务器都需要关联一个专门为复制功能编写的复制处理器。

连接响应处理程序

network.c/acceptTcpHandler 函数是 Redis 的连接响应处理器。该处理器用于响应连接到服务器侦听套接字的客户端。它被实现为 sys/socket.h/acccept 函数的包装器。

当 Redis 服务器初始化时，程序将连接响应处理器与服务器监听套接字的 AE_READABLE 时间关联起来。当客户端使用 sys/socket.h/connect 函数连接到服务器的监听套接字时，套接字会产生一个 AE_READABLE 事件，导致连接响应处理程序执行，并执行相应的套接字响应操作。

命令请求处理程序

network.c/readQueryFromClient 函数是 Redis 的命令请求处理器。这个处理器负责从socket读取客户端发送的命令请求内容。它被实现为 unistd.h/read 函数的包装器。

当客户端通过连接响应处理程序成功连接到服务器时，服务器将客户端套接字的 AE_READABLE 事件与命令请求处理程序相关联。当客户端向服务器发送命令请求时，套接字会产生 AE_READABLE 事件，导致命令请求处理器执行，并执行相应的套接字读取操作。

在客户端连接到服务器的整个过程中，服务器将始终请求客户端套接字 AE_READABLE 事件关联命令的处理程序。