Redis简介

Redis是一个开源的内存中的数据结构存储系统，它被我们经常用作：数据库、缓存，当然也可以当做消息中间件使用。

它支持多种类型的数据结构，如字符串（Strings），散列（Hash），列表（List），集合（Set），有序集合（Sorted Set或者是ZSet）与范围查询，Bitmaps，Hyperloglogs 和地理空间（Geospatial）索引半径查询。

其中常见的数据结构使用场景：
1、String常用来存储简单的文本信息，或者进行统计操作
2、List可以模拟队列，栈进行操作。
3、Set常用与集合操作，求交集、并集、差集等操作
4、Hash简言之直接当做HashMap进行使用。
5、ZSet 可以制作延时队列使用。

Redis到底有多快

Redis是基于内存访问并且是单进程单线程模型的 KV 数据库，由C语言编写，官方提供的数据是可以达到100000+的QPS（每秒内查询次数）。这个数据不比采用单进程多线程的同样基于内存的 KV 数据库 Memcached 差！

image.png

横轴是连接数，纵轴是QPS。

Redis为什么这么快

1.纯内存操作

数据存储在内存中，读取的时候不需要磁盘的 IO操作。查找和操作的时间复杂度都是O(1)；

2.合理的数据结构

2.1、SDS

Redis并没有使用C语言传统字符串标识而是自己构建的一种简单动态字符串(simple dynamic String,SDS)的抽象类型，作为redis默认字符串标识。

SDS.示例

struct sdshdr {
    int len;//用于记录 buf 中已使用空间的长度
    int free;//buf 中空闲空间的长度
    char buf[]; //存储实际内容
}

SDS 与 C 字符串的区别

①常数复杂度获得字符串长度
C 字符串本身不记录长度信息，每次获取长度信息都需要遍历整个字符串，复杂度为 O(n)；C 字符串遍历时遇到 '\0' 时结束。
SDS 中 len 字段保存着字符串的长度，所以总能在常数时间内获取字符串长度，复杂度是 O(1)。
②避免缓冲区溢出
假设在内存中有两个紧挨着的两个字符串，s1=“aaaa”和 s2=“bbbb”。
由于在内存上紧紧相连，当我们对 s1 进行扩充的时候，将 s1=“aaaabbbb”后，由于没有进行相应的内存重新分配，导致 s1 把 s2 覆盖掉，导致 s2 被莫名其妙的修改。
但 SDS 的 API 对 zfc 修改时首先会检查空间是否足够，若不充足则会分配新空间，避免了缓冲区溢出问题。
③减少字符串修改时带来的内存重新分配的次数
在 C 中，当我们频繁的对一个字符串进行修改（append 或 trim）操作的时候，需要频繁的进行内存重新分配的操作，十分影响性能。
如果不小心忘记，有可能会导致内存溢出或内存泄漏，对于 Redis 来说，本身就会很频繁的修改字符串，所以使用 C 字符串并不合适。而 SDS 实现了空间预分配和惰性空间释放两种优化策略：
空间预分配：当 SDS 的 API 对一个 SDS 修改后，并且对 SDS 空间扩充时，程序不仅会为 SDS 分配所需要的必须空间，还会分配额外的未使用空间。
分配规则如下：如果对 SDS 修改后，len 的长度小于 1M，那么程序将分配和 len 相同长度的未使用空间。举个例子，如果 len=10，重新分配后，buf 的实际长度会变为 10(已使用空间)+10(额外空间)+1(空字符)=21。如果对 SDS 修改后 len 长度大于 1M，那么程序将分配 1M 的未使用空间。

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

④二进制安全
在 Redis 中不仅可以存储 String 类型的数据，也可能存储一些二进制数据。
二进制数据并不是规则的字符串格式，其中会包含一些特殊的字符如 '\0'，在 C 中遇到 '\0' 则表示字符串的结束，但在 SDS 中，标志字符串结束的是 len 属性。

2.2、字典

字典是一种保存键值对的抽象数据结构，类似于我们Java熟知的HashMap，字典中每个键都是独一无二的。字典在Redis使用相当广泛，Redis的数据库就是使用字典作为底层实现，对数据库的增删改查都是建立在字典之上。

字典的数据结构：

typedef struct dict{
      dictType *type; //类型特定函数
    void *privdata; //私有数据
    dictht ht[2];//hash表
    int trehashidx;//reshhash 索引
}

哈希表的数据结构：

typedef struct dictht{
    dectEntrt **table; //哈希表数组
    unsigned long size; //哈希表大小
    unsigned long sizemask;//哈希表大小掩码，用于计算索引值
    unsigned long used;   //哈希表已有节点数量
}

哈希表节点数据结构

 typedef struct dictEntry {
     void *key;  // 键
     union {
       void *val;
       uint64_t u64;
        int64_t s64;
   } v;     // 值
    struct dictEntry *next;   // 指向下个哈希表节点，形成链表
} dictEntry;

字典中放置哈希表，我们看到ht属性是一个包含了两个项的数组，数组中每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，而ht[1]哈希表只对ht[0]哈希表进行rehash时使用。

渐进式rehash

随着操作的不断进行，哈希表保存的键值对会逐渐增多或减少，为了让哈希表负载因子维持在一个合理范围之内，当哈希表保存的键值对太多或太少时，程序要对哈希表的大小进行相应的扩展或收缩。

Redis中的rehash动作并不是一次性、集中式完成的，而是分多次、渐进式的完成的。

这样做的目的是，如果服务器中包含很多键值对，要一次性的将这些键值对全部rehash到ht[1]的话，庞大的计算量可能导致服务器在一段时间内停止服务于。

为了避免这种影响，Redis采用了渐进式，Redis：为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
在字典中维持一个索引计数器变量rehashidx，并将它置为0，表示rehash工作开始。
在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]中，当rehash工作完成之后，程序将rehashidx属性的值+1。
随着字典操作的不断进行，最终在某个时间点上，ht[0]的所有键值对都被rehash到ht[1]上，这时将rehashidx属性设为-1，表示rehash完成。
渐进式rehash的好处在于其采取分而治之的方式，将rehash键值对所需要的计算工作均摊到字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

2.3、跳跃表

跳跃表是一种有序的数据结构，它通过每个节点维护指向多个其他节点的指针，达到快速访问节点的目的。大部分情况下调表的查询效率可以与平衡树相媲美，并且跳跃表实现比平衡树简单，所以很多程序都是用调表代替了平衡树。
Redis中Zset使用了跳跃表，跳跃表的基本结构如图所示：

跳跃表

跳表具有如下性质：
(1) 由很多层结构组成
(2) 每一层都是一个有序的链表
(3) 最底层(Level 1)的链表包含所有元素
(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

2.4、压缩列表

压缩列表是列表键和哈希键的底层实现之一，当一个列表键只含有少量的列表项，并且每个列表项要么就是最小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来作为列表的底层原理实现。
当元素个数较少时，Redis 用 ziplist 来存储数据，当元素个数超过某个值时，链表键中会把 ziplist 转化为 linkedlist，字典键中会把 ziplist 转化为 hashtable。

3、线程

首先我们这里强调的线程，只是在处理我们的网络请求的时候的线程。

Redis线程模型

讲到线程首先我们要明白CPU不是Redis的瓶颈，Redis的瓶颈最有可能是机器内存的大小或者网络带宽。例如在一个普通的Linux系统上，Redis通过使用pipelining每秒可以处理100万个请求，所以如果应用程序主要使用O(N)或O(log(N))的命令，它几乎不会占用太多CPU。

在Redis6.0版本之前，我们使用单线程模型， 单线程指的是网络请求模块使用了一个线程，即一个线程处理所有网络请求，其他模块该使用多线程，仍会使用了多个线程，使用了单线程后，可维护性高。多线程模型虽然在某些方面表现优异，但是它却引入了程序执行顺序的不确定性，带来了并发读写的一系列问题，增加了系统复杂度、同时可能存在线程切换、甚至加锁解锁、死锁造成的性能损耗。Redis通过IO多路复用等技术，处理性能非常高，因此没有必要使用多线程。单线程机制使得 Redis 内部实现的复杂度大大降低，Hash 的惰性 Rehash、Lpush 等等 “线程不安全” 的命令都可以无锁进行.

Redis6.0开始使用多线程模型

从Redis自身角度来说，因为读写网络的read/write系统调用占用了Redis执行期间大部分CPU时间，瓶颈主要在于网络的 IO 消耗, 优化主要有两个方向:

1、 提高网络 IO 性能，典型的实现比如使用 DPDK 来替代内核网络栈的方式。
2、使用多线程充分利用多核，典型的实现比如 Memcached。

协议栈优化的这种方式跟 Redis 关系不大，支持多线程是一种最有效最便捷的操作方式。所以总结起来，redis支持多线程主要就是两个原因：

1、可以充分利用服务器 CPU 资源，目前主线程只能利用一个核
2、多线程任务可以分摊 Redis 同步 IO 读写负荷

单线程与多线程性能对比：

性能对比

4、多路I/O复用模型

在我们的IO模型中，大概IO分为五种IO模型分别是：BIO、NIO、IO多路复用、信号驱动IO、异步IO。如果不懂可以看下 https://www.cnblogs.com/reecelin/p/13537734.html

IO

多路复用I/O（Multiplexing I/O）
select：能打开的文件描述符个数有限（最多1024个），如果有1K个请求，用户进程每次都要把1K个文件描述符发送给内核，内核在内部轮询后将可读描述符返回，用户进程再依次读取。因为文件描述符（fd）相关数据需要在用户态和内核态之间拷来拷去，所以性能还是比较低
poll：可打开的文件描述符数量提高，因为用链表存储，但性能仍然不够，和selector一样数据需要在用户态和内核态之间拷来拷去
epoll：用户态和内核态之间不用文件描述符（fd）的拷贝，所有fd用红黑树存储，有返回结果的fd放在链表中，用户进程通过链表读取返回结果，伪异步I/O，性能较高。epoll分为水平触发和边缘出发两种模式，ET是边缘触发，LT是水平触发，一个表示只有在变化的边际触发，一个表示在某个阶段都会触发。
epoll核心：
执行epoll_create()时，创建了红黑树和就绪链表；
执行epoll_ctl()时，如果增加socket句柄，则检查在红黑树中是否存在，存在立即返回，不存在则添加到树干上，然后向内核注册回调函数，用于当中断事件来临时向准备就绪链表中插入数据；
执行epoll_wait()时立刻返回准备就绪链表里的数据即可。

Redis采用epoll作为I/O多路复用技术的实现，再加上Redis自身的事件处理模型将epoll中的连接，读写，关闭都转换为了时间，不在I/O上浪费过多的时间。

总结

1.采用了纯内存的操作。
2.采用了合理的数据结构。
3.线程模型采用尽量少的线程处理，避免了多线程的频繁上下文切换问题。
4.基于非阻塞的IO多路复用机制。