Redis是如何做到访问速度很快的

对于Redis这种内存数据库来说，除了访问的是内存之外，Redis访问速度飞快还取决于其他的一些因素，而这些都跟Redis的高可用性有很大关系。下面是衡量Redis的三个纬度：

1.高性能：线程模型、网络I/O模型、数据结构，合理的数据编码
2.高可用性：主从复制、哨兵模式、Cluster分片集群和持久化机制
3.高拓展性：负载均衡

本篇文章，我们主要来介绍Redis的高性能特性的几个相关因素。根据官方数据，Redis的QPS可以达到约100000/秒，横轴表示连接数，纵轴表示QPS。

参考资料：https://redis.io/topics/benchmarks

因素1: 线程模型

Redis4.0之前是单线程模型，原因是因为在此之前CPU不是瓶颈，网络I/O才是瓶颈，而单线程模型一来避免了多线程模型之间的上下文切换，二来又可以通过多路复用来实现并发，并且代码更容易维护。

不过在Redis4.0之后，redis新增了一些可以被其他线程异步处理的删除操作，例如：UNLINK、FLUSHALL ASYNC 和 FLUSHDB ASYNC。原因是有一些超大的键值对占用了很大的内容，例如几十 MB 或者几百 MB 的数据，这些数据的删除在几百毫秒内结束不了，如果是同步的就会阻塞待处理的任务，所以加入了多线程，目的就是为了异步处理这些大的数据。

参考资料为：
https://zhuanlan.zhihu.com/p/91490643
https://stackoverflow.com/questions/10489298/redis-is-single-threaded-then-how-does-it-do-concurrent-i-o
http://www.odbms.org/2018/03/the-little-known-feature-of-redis-4-0-that-will-speed-up-your-applications/

因素2:网络I/O模型

因为Redis是单线程模型的原因，实现并发操作的话，是需要采用了多路复用机制的，例如：epoll，关于epoll的介绍可以参考我的另外一篇文章4.同时管理多个socket的高效方法-epoll

参考资料：
https://draveness.me/redis-io-multiplexing/
https://www.jianshu.com/p/8f2fb61097b8
https://baijiahao.baidu.com/s?id=1676709704453688282&wfr=spider&for=pc

因素3:数据结构

首先，Redis整个数据库就是一个全局哈希表，而哈希表的时间复杂度是 O(1)，只需要计算每个键的哈希值，便知道对应的哈希桶位置，定位桶里面的 entry 找到对应数据，这个也是 Redis 快的原因之一。

其次，不同的数据类型使用不同的数据结构速度才得以提升，并且每种数据类型都有一种或者多种数据结构来支撑。

1）SDS 简单动态字符

SDS与C中的字符串区别如下所示：

sds与c字符串相比，优势如下：

1.Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ， 这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。

2.与 C 字符串不同， SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性。

3.空间预分配：SDS 被修改后，程序不仅会为 SDS 分配所需要的必须空间，还会分配额外的未使用空间。分配规则如下：如果对 SDS 修改后，len 的长度小于 1M，那么程序将分配和 len 相同长度的未使用空间。举个例子，如果 len=10，重新分配后，buf 的实际长度会变为 10(已使用空间)+10(额外空间)+1(空字符)=21。如果对 SDS 修改后 len 长度大于 1M，那么程序将分配 1M 的未使用空间。

4.惰性释放空间：当对 SDS 进行缩短操作时，程序并不会回收多余的内存空间，而是使用 free 字段将这些字节数量记录下来不释放，后面如果需要 append 操作，则直接使用 free 中未使用的空间，减少了内存的分配。

通过惰性空间释放策略， SDS 避免了缩短字符串时所需的内存重分配操作， 并为将来可能有的增长操作提供了优化。

5.二进制安全：为了确保 Redis 可以适用于各种不同的使用场景， SDS 的 API 都是二进制安全的（binary-safe）：所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的， 它被读取时就是什么样。

这也是我们将 SDS 的 buf 属性称为字节数组的原因 —— Redis 不是用这个数组来保存字符， 而是用它来保存一系列二进制数据。

比如说， 使用 SDS 来保存之前提到的特殊数据格式就没有任何问题， 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束， 如图 2-18 所示。

参考资料：
http://redisbook.com/preview/sds/different_between_sds_and_c_string.html

2）zipList 压缩列表

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

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

Ziplist 是由一系列特殊编码的内存块构成的列表， 一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组（不以 \0 结尾的 char 数组）或者整数。

字符数组
长度小于等于 63 （26−1）字节的字符数组
长度小于等于 16383 （214−1） 字节的字符数组
长度小于等于 4294967295 （232−1）字节的字符数组
整数
4 位长，介于 0 至 12 之间的无符号整数
1 字节长，有符号整数
3 字节长，有符号整数
int16_t 类型整数
int32_t 类型整数
int64_t 类型整数

ziplist 在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表占用字节数、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N)。

3)双端列表

Redis List 数据类型通常被用于队列、微博关注人时间轴列表等场景。不管是先进先出的队列，还是先进后出的栈，双端列表都很好的支持这些特性。

双端链表还是 Redis 列表类型的底层实现之一， 当对列表类型的键进行操作 —— 比如执行 RPUSH 、 LPOP 或 LLEN 等命令时， 程序在底层操作的可能就是双端链表。

双端链表及其节点的性能特性如下：

1.节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 O(1)O(1) ，
并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
2.链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 O(1)O(1) ；
3.链表带有记录节点数量的属性，所以可以在 O(1)O(1) 复杂度内返回链表的节点数量（长度）；

除此之外，Redis为双端链表还实现了一个迭代器， 这个迭代器可以从两个方向对双端链表进行迭代：

1.沿着节点的 next 指针前进，从表头向表尾迭代；
2.沿着节点的 prev 指针前进，从表尾向表头迭代；

双端链表的实现：

参考资料：
http://origin.redisbook.com/internal-datastruct/adlist.html

4）skipList 跳跃表

和字典、链表或者字符串这几种在 Redis 中大量使用的数据结构不同， 跳跃表在 Redis 的唯一作用， 就是实现有序集数据类型。

跳表简介：

跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。

从图中可以看到， 跳跃表主要由以下部分构成：

1.表头（head）：负责维护跳跃表的节点指针。
2.跳跃表节点：保存着元素值，以及多个层。
3.层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
4.表尾：全部由 NULL 组成，表示跳跃表的末尾。

参考资料：
https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html

5）整数集合（intset）

整数集合（intset）用于有序、无重复地保存多个整数值， 根据元素的值， 自动选择该用什么长度的整数类型来保存元素。

举个例子， 如果在一个 intset 里面， 最长的元素可以用 int16_t 类型来保存， 那么这个 intset 的所有元素都以 int16_t 类型来保存。

另一方面， 如果有一个新元素要加入到这个 intset ， 并且这个元素不能用 int16_t 类型来保存 —— 比如说， 新元素的长度为 int32_t ， 那么这个 intset 就会自动进行“升级”：先将集合中现有的所有元素从 int16_t 类型转换为 int32_t 类型， 接着再将新元素加入到集合中。

根据需要， intset 可以自动从 int16_t 升级到 int32_t 或 int64_t ， 或者从 int32_t 升级到 int64_t 。

Intset 只支持升级，不支持降级。

Intset 是有序的，程序使用二分查找算法来实现查找操作，复杂度为 O(lgN)O(lgN) 。

Intset 是集合键的底层实现之一，如果一个集合是下面的情况，那么 Redis 就会使用 intset 来保存集合元素。

1. 只保存着整数元素；
2. 元素的数量不多；

参考资料：
https://redisbook.readthedocs.io/en/latest/compress-datastruct/intset.html

因素4:合理的数据编码

Redis 使用对象（redisObject）来表示数据库中的键值，当我们在 Redis 中创建一个键值对时，至少创建两个对象，一个对象是用做键值对的键对象，另一个是键值对的值对象。

typedef struct redisObject{
    //类型：包含字符串对象、列表对象、哈希对象、集合对象、有序集合对象。
   unsigned type:4;
   //编码
   unsigned encoding:4;
   //指向底层数据结构的指针
   void *ptr;
    //...
 }robj;

编码介绍：

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

2）List：List 对象的编码可以是 ziplist 或 linkedlist，字符串长度 < 64 字节且元素个数 < 512 使用 ziplist 编码，否则转化为 linkedlist 编码；

备注：这两个条件是可以修改的，在 redis.conf 中：
list-max-ziplist-entries 512
list-max-ziplist-value 64

3）Hash：Hash 对象的编码可以是 ziplist 或 hashtable。

当 Hash 对象同时满足以下两个条件时，Hash 对象采用 ziplist 编码，否则就是 hashtable 编码。

1.Hash 对象保存的所有键值对的键和值的字符串长度均小于 64 字节。
2. Hash 对象保存的键值对数量小于 512 个。

4）Set：Set 对象的编码可以是 intset 或 hashtable，intset 编码的对象使用整数集合作为底层实现，把所有元素都保存在一个整数集合里面。

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

5）Zset：Zset 对象的编码可以是 ziplist 或 zkiplist，当采用 ziplist 编码存储时，每个集合元素使用两个紧挨在一起的压缩列表来存储。

Ziplist 压缩列表第一个节点存储元素的成员，第二个节点存储元素的分值，并且按分值大小从小到大有序排列。

当 Zset 对象同时满足一下两个条件时，采用 ziplist 编码，如果不满足以上条件的任意一个，ziplist 就会转化为 zkiplist 编码。

Zset 保存的元素个数小于 128。
Zset 元素的成员长度都小于 64 字节。

备注：这两个条件是可以修改的，在 redis.conf 中：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

参考资料：

http://www.redis.cn/topics/data-types.html

https://mp.weixin.qq.com/s/8HN1PqqU57Kdz9ERwDY2cw