鲁达 作者：Rick.lz
原文：
Redis 如何保证高效的查询效率
为什么 Redis 比较快
Redis 中的查询速度为什么那么快呢？
1、因为它是内存数据库；
2、归功于它的数据结构；
3、Redis 中是单线程；
4、Redis 中使用了多路复用。
Redis 中的数据结构
这里借用一张来自[Redis核心技术与实战] Redis 中数据结构和底层结构的对应图片
1、简单动态字符串
Redis 中并没有使用 C 中 char 来表示字符串，而是引入了 简单动态字符串（Simple Dynamic Strings，SDS）来存储字符串和整型数据。那么 SDS 对比传统的字符串有什么优点呢？
先来看下 SDS 的结构
struct sdshdr { // 记录 buf 数组中已使用字节的数量 // 等于 SDS 保存字符串的长度，不包含'\0' long len; // 记录buf数组中未使用字节的数量 long free; // 字节数组，用于保存字符串 char buf[]; }; 举个栗子：
使用 SDS 存储了一个字符串 hello,对应的 len 就是5，同时也申请了5个为未使用的空间，所以 free 就是5。
在 3.2 版本后，sds 会根据字符串实际的长度，选择不同的数据结构，以更好的提升内存效率。当前 sdshdr 结构分为 5 种子类型，分别为 sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。其中 sdshdr5 只有 flags 和 buf 字段，其他几种类型的 len 和 alloc 采用从 uint8_t 到 uint64_t 的不同类型，以节省内存空间。
SDS 对比 c 字符串的优势
SDS可以常数级别获取字符串的长度
因为结构里面已经记录了字符串的长度，所以获取字符串的长度复杂度为O(1)，c 中字符串没记录长度，需要遍历整个长度，复杂度为O(N)。
杜绝缓冲区溢出
如果在修改字符的时候，没有分配足够的内存大小，就很容易造成缓存溢出，内存越界。
strcat 函数常见的错误就是数组越界，即两个字符串连接后，长度超过第一个字符串数组定义的长度，导致越界。
SDS 中的空间分配策略可以杜绝这种情况，当对 SDS 进行修改时，API 会检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。空间的申请是自动完成的，所以就避免了缓存溢出。
减少修改字符串时带来的内存分配次数
对于 C 字符串来说，如果修改字符串的长度，都需要重新执行内存分配操作；但是对于 Redis 数据库来说，如果频繁执行内存分配/释放操作，必然会对性能产生一定影响。为了避免 C 字符串的缺陷，SDS 采用了空间预分配和惰性空间释放两种优化策略。
空间预分配
空间预分配用于优化 SDS 的字符串增长操作，当 SDS 的 api 对 SDS 进行修改，同时需要进行空间扩展的时候，除了会给 SDS 分配修改需要的空间，同时还会给 SDS 分配额外的未使用空间。
1、如果对 SDS 修改之后，SDS 的长度小于1MB,那么程序分配和 len 同样大小的未使用空间，也就是这时候 SDS 中的 len 和 free 长度相同；
2、如果对 SDS 修改之后，SDS 的长度大于等于1MB,那么程序分配1MB的未使用空间。
在对 SDS 空间进行扩展的时候，首先会判断未使用空间的大小是否能满足要求，如果足够，就不用在进行内存分配了，这样能够减少内存的重新分配的次数。
惰性空间释放
惰性空间释放用于优化 SDS 字符串的缩短操作，当 SDS 的 API 需要缩短 SDS 保护的字符串时，程序并不会立即使用内存重分配来回收缩短后多出来的内存，而是使用 free 属性将这些字节的数量记录起来，等待之后的重新使用。
二进制安全
对于 C 字符串来说，字符串中不能包含空字符，否则最先被程序读入的空字符串被误认为是字符串结尾，这使得 C 字符串只能保存文本数据，而不能保存图片、音视频等二进制文件。对于 SDS 来说，所有 SDS 都会以处理二进制的方式来处理 SDS 保存在 buf 数组中的内容，程序不会对里面的内容做任何限制。
兼容部分C字符串函数
SDS 末尾设置空字符的操作使得它可以和部分 C 字符串函数兼容。
2、链表
链表是一种很常见的数据结构，在很多高级语言中都能看到，Redis 中的 list 就用到了双向链表，当一个列表键包含了数量比较多的元素，或者是列表中包含的元素都是比较长的字符串的时，Redis 就会使用链表作为 list 的底层实现。
这里双向链表不展开讨论了。
3、字典
redisDb 主要包括 2 个核心 dict 字典、3 个非核心 dict 字典、dbID 和其他辅助属性。2 个核心 dict 包括一个 dict 主字典和一个 expires 过期字典。主 dict 字典用来存储当前 DB 中的所有数据，它将 key 和各种数据类型的 value 关联起来，该 dict 也称 key space。过期字典用来存储过期时间 key，存的是 key 与过期时间的映射。日常的数据存储和访问基本都会访问到 redisDb 中的这两个 dict。
所以对于任何类型的数据查询都需要经过一次 dict 的查询，也就是 hash 的过程。通过这个 dict 将 key 映射到对应的数据类型的 value 中。
3 个非核心 dict 包括一个字段名叫 blocking_keys 的阻塞 dict，一个字段名叫 ready_keys 的解除阻塞 dict，还有一个是字段名叫 watched_keys 的 watch 监控 dict。
Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希节点，每个哈希表节点就保存了字典中的一个键值对。
使用哈希表就难免遇到哈希碰撞，两个key的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。
Redis 解决哈希冲突的方式，就是链式哈希。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。
随着写入的消息越来越多，哈希冲突的几率也随之升高，这时候就需要对哈希表进行扩容，Redis 中的扩容使用的是渐进式rehash。
其实，为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表1和哈希表2。一开始，当你刚插入数据时，默认使用哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：
1、给哈希表2分配更大的空间，例如是当前哈希表1大小的两倍；
2、把哈希表1中的数据重新映射并拷贝到哈希表2中；
3、释放哈希表1的空间。
当然数据很大的话，一次迁移所有的数据，显然是不合理的，会造成Redis线程阻塞，无法服务其他请求。这里 Redis 使用的是渐进式 rehash。
在 rehash 期间，每次执行添加，删除，查找或者更新操作时，除了对命令本身的处理，还会顺带将哈希表1中的数据拷贝到哈希表2中。从索引0开始，每执行一次操作命令，拷贝一个索引位置的数据。
在进行 rehash 期间，删除，查找或者更新操作都会在两个哈希表中执行，添加操作就直接添加到哈希表2中了。查找会把两个哈希表都找一遍，直到找到或者两个都找不到。
4、跳表
其中 Redis 中的有序集合就是使用跳表来实现的
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是O(n)。
链表加多级索引的结构，就是跳表,跳表查询的时间复杂度是O(logn)。通过在每个节点中维持多个指向其他节点的指针，从而实现快速访问的节点的目的。
5、整数数组
整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。是 Redis 用户保存整数值的集合抽象数据结构，可以保存的类型是int16_t,int32_t,int64_t的整数值，并且保证集合中不会出现重复的元素。
typedef struct intset{ // 编码方法，指定当前存储的是 16 位，32 位，还是 64 位的整数 int32 encoding; // 集合中的元素数量 int32 length; // 保存元素的数组 int<T> contents; } 这样看，这个集合倒也没有什么特殊的点。这时候需要来看下整数集合的升级。
每当一个整数被添加到整数集合时，首先需要判断下 新元素的类型和集合中现有元素类型的长短，如果新元素是一个32位的数字，现有集合类型是16位的，那么就需要将整数集合进行升级，然后才能将新的元素加入进来。
这样做的优点：
1、提升整数集合的灵活性，可以随意的添加整数，而不用关心整数的类型；
2、可以尽可能的节约内存。
缺点：
不支持降级，一旦对数组进行了升级，就会一直保持升级后的状态。
6、压缩列表
压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个元素只包含少量的列表项，并且每个列表项是小整数值或者是长度比较短的字符串,redis 就会使用压缩列表来作为列表键的底层实现。
压缩列表(ziplist)的目的是为了节约内存，通过一片连续的内存空间来存储数据。这样看起来好像和数组很像，数组中每个节点的内存大小是一样的，对于压缩列表，每个节点的内存大小是不同的，每个节点可以保存字节数组或一个整数值。通过可变的节点内存大小，来节约内存的使用。
ziplist 的结构：
1、zlbytes : 是压缩列表所占用的总内存字节数;
2、Zltail : 尾节点到起始位置的字节数，（目的是为了直接定位到尾节点，方便反向查询）;
3、Zllen : 总共包含的节点/内存块数，也就是压缩列表的节点数量;
4、Entry : 是 ziplist 保存的各个数据节点，这些数据点长度随意;
5、Zlend : 是一个魔数 255，用来标记压缩列表的结束。
由于 ziplist 是连续紧凑存储，没有冗余空间，所以插入新的元素需要 realloc 扩展内存，所以如果 ziplist 占用空间太大，realloc 重新分配内存和拷贝的开销就会很大，所以 ziplist 不适合存储过多元素，也不适合存储过大的字符串。
因此只有在元素数和 value 数都不大的时候，ziplist 才作为 hash 和 zset 的内部数据结构。其中 hash 使用 ziplist 作为内部数据结构的限制时，元素数默认不超过 512 个，value 值默认不超过 64 字节。可以通过修改配置来调整 hash_max_ziplist_entries 、hash_max_ziplist_value 这两个阀值的大小。
zset 有序集合，使用 ziplist 作为内部数据结构的限制元素数默认不超过 128 个，value 值默认不超过 64 字节。可以通过修改配置来调整 zset_max_ziplist_entries 和 zset_max_ziplist_value 这两个阀值的大小。
在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是O(N)了。
连锁更新
压缩列表 ziplist 的存储节点 Entry 数据节点的结构：
1、previous_entry_length : 记录了前一个节点的长度
- 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节： 前一节点的长度就保存在这一个字节里面；
- 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE （十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。
2、encoding : 记录了节点的 content 属性所保存数据的类型以及长度
3、content : 节点的 content 属性负责保存节点的值， 节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding 属性决定。
举个栗子：
如果压缩列表中每个节点的长度都是250，因为是小于254，所以每个节点中的 previous_entry_length 长度1字节就能够保存了。
这时候，在头部节点插入了一个新的元素 entryNew，然后长度是大于254，那么后面的节点中 entry1 的 previous_entry_length 长度为1字节，就不能保存了，需要扩容成5字节，然后 entry1 节点进行扩容了，变成了254，所以后面的节点也就需要一次扩容，这就引发一连串的扩容。也就是连锁更新。
为什么单线程还能很快
Redis 是单线程，主要是指 Redis 的网络IO和键值对读写是由一个线程来完成的，这也是 Redis 对外提供键值存储服务的主要流程。
多线程必然会面临对于共享资源的访问，这时候通常的做法就是加锁，虽然是多线程，这时候就会变成串行的访问。也就是多线程编程模式会面临的共享资源的并发访问控制问题。
同时多线程也会引入同步原语来保护共享资源的并发访问，代码的可维护性和易读性将会下降。
基于多路复用的高性能I/O模型
Linux 中的IO多路复用机制是指一个线程处理多个IO流。简单来说，在 Redis 只运行单线程的情况下，该机制允许内核中，同时存在多个监听套接字和已连接套接字。内核会一直监听这些套接字上的连接请求或数据请求。一旦有请求到达，就会交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个IO流的效果。
文件事件是对连接 socket 操作的一个抽象。当端口监听 socket 准备 accept 新连接，或者连接 socket 准备好读取请求、写入响应、关闭时，就会产生一个文件事件。IO 多路复用程序负责同时监听多个 socket，当这些 socket 产生文件事件时，就会触发事件通知，文件分派器就会感知并获取到这些事件。
虽然多个文件事件可能会并发出现，但 IO 多路复用程序总会将所有产生事件的 socket 放入一个队列中，通过这个队列，有序的把这些文件事件通知给文件分派器。
文件事件分派器接收 I/O 多路复用程序传来的套接字，并根据套接字产生的事件类型，调用相应的事件处理器。
服务器会为执行不同任务的套接字关联不同的事件处理器，这些处理器是一个个的函数，他们定义了这个事件发生时，服务器应该执行的动作。
Redis 封装了 4 种多路复用程序，每种封装实现都提供了相同的 API 实现。编译时，会按照性能和系统平台，选择最佳的 IO 多路复用函数作为底层实现，选择顺序是，首先尝试选择 Solaries 中的 evport，如果没有，就尝试选择 Linux 中的 epoll，否则就选择大多 UNIX 系统都支持的 kqueue，这 3 个多路复用函数都直接使用系统内核内部的结构，可以服务数十万的文件描述符。
如果当前编译环境没有上述函数，就会选择 select 作为底层实现方案。select 方案的性能较差，事件发生时，会扫描全部监听的描述符，事件复杂度是 O(n)，并且只能同时服务有限个文件描述符，32 位机默认是 1024 个，64 位机默认是 2048 个，所以一般情况下，并不会选择 select 作为线上运行方案。
单线程处理IO请求性能瓶颈
1、后台 Redis 通过监听处理事件队列中的消息，来单线程的处理命令，如果一个命令的执行时间很久，就会影响整个 server 的性能；
耗时的操作命令有下面几种：
- 1、操作 bigkey：bigkey 在写入和删除的时候，需要的时间都会很长；
- 2、使用复杂度过高的命令；
- 3、大量 key 集中过期：Redis 的过期机制也是在主线程中执行的，大量 key 集中过期会导致处理一个请求时，耗时都在删除过期 key，耗时变长；
- 4、淘汰策略：淘汰策略也是在主线程执行的，当内存超过 Redis 内存上限后，每次写入都需要淘汰一些 key，也会造成耗时变长；
- 5、AO F刷盘开启 always 机制：每次写入都需要把这个操作刷到磁盘，写磁盘的速度远比写内存慢，会拖慢 Redis 的性能；
- 6、主从全量同步生成 RDB：虽然采用 fork 子进程生成数据快照，但 fork 这一瞬间也是会阻塞整个线程的，实例越大，阻塞时间越久；
上面的这几种问题，我们在写业务的时候需要去避免，对于 bigkey，Redis 在4.0推出了 lazy-free 机制，把 bigkey 释放内存的耗时操作放在了异步线程中执行，降低对主线程的影响。
2、并发量非常大时，单线程读写客户端 IO 数据存在性能瓶颈
使用 Redis 时，几乎不存在 CPU 成为瓶颈的情况， Redis 主要受限于内存和网络。随着硬件水平的提升，Redis 中的性能慢慢主要出现在网络 IO 的读写上。虽然采用 IO 多路复用机制，但是读写客户端数据依旧是同步IO，只能单线程依次读取客户端的数据，无法利用到CPU多核。
为了提升网络 IO 的读写性能，Redis 在6.0推出了多线程，同过多线程的 IO 来处理网络请求。不过需要注意的是这里的多线程仅仅是针对客户端的读写是并行的，Redis 处理事件队列中的命令，还是单线程处理的。
总结
Redis 使用单线程，来避免共享资源的竞争，使用多路复用实现高性能的I/O，它是内存数据库，所有操作都在内存上完成，使用哈希表，跳表等一系列高效的数据结构，这些特性保证了 Redis 的高性能。