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具有以下优点：
度获取字符串长度时间复杂度为O(1) 。
C字符串不记录自身长度，获取C字符串长度时必须遍历整个字符串计数得到，复杂度是O(N)
SDS字符串自身记录维护len长度属性，获得SDS字符串长度的复杂度是O(1)杜绝缓冲区溢出。
C字符串不记录长度，由于两个C字符串在内存存储上紧邻，在执行字符串拼接strcat时，如果不提前分配足够空间，很可能发生修改s1的数据溢出到s2所在的空间中（缓冲区溢出）。
SDS杜绝了缓冲区溢出问题，它记录了长度，当修改SDS字符串之前，API都会检查SDS的空间是否满足修改的要求，不满足API会自动进行空间扩展。空间预分配，减少修改时的内存重分配次数
SDS 被修改后，程序不仅会为 SDS 分配所需要的空间，还会分配额外的未使用空间。这样，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。
具体分配未使用空间如下2种方式：
- 如修改后长度len小于1MB，就分配和len属性相同大小的未使用空间：free=len。
- 如修改后长度len大于等于1MB，就分配1M的未使用空间：free=1MB。
惰性空间释放
惰性空间释放，缩短操作时：SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。当SDS做缩短操作，不会立刻使用内存重分配来收回缩短后多出来的字节，而是保持在free属性里。将来如果需要 append 操作，则直接使用 free 中未使用的空间，减少了内存的分配步骤。
另外，SDS也提供了API手动进行释放SDS未使用空间，避免惰性释放策略会造成内存浪费。二进制安全
C字符串的字符必须符合某种编码，除结尾空字符以外，字符串内部不允许有空字符串，存储有局限性。而在 Redis 中，不仅可以存储 String 类型的数据，也可能存储一些二进制数据。
二进制数据并不是规则的字符串格式，其中会包含一些特殊的字符如 '\0'。在 C 中遇到 '\0' 则表示字符串的结束，但SDS不是，它是以len长度标识结尾。兼容部分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 单线程的好处
- 避免线程创建过多导致的性能消耗，反而降低整体吞吐能力。
- 避免上下文切换引起的 CPU 额外的开销。
- 避免了线程之间的竞争问题，如加锁、解锁、死锁等，都会造成性能损耗。
- 无需额外考虑多线程带来的程序复杂度，代码更清晰，处理逻辑简单。
2.4.3 单线程是否有效利用CPU
官方这么说
It’s not very frequent that CPU becomes your bottleneck with Redis, as usually Redis is either memory or network bound. For instance, using pipelining Redis running on an average Linux system can deliver even 1 million requests per second, so if your application mainly uses O(N) or O(log(N)) commands, it is hardly going to use too much 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 操作进行扩充，减少哈希冲突。
