Redis为什么这么快？在除了它是内存型数据库外，它的数据结构，IO模型也是它这么快速的重要原因。我们都知道Redis是单线程模型，那么Redis是如何利用单线程快速的处理高并发业务的呢？带着疑问来看下边的内容更容易理解。

Redis为什么使用单线程？

了解多线程的开销

1. 在使用多线程中，如果合理分配资源可以增加系统中处理请求操作的实体，进而能够提升同时处理的请求数，即吞吐率。但是如图所示进一步增加线程时，系统吞吐率就增长延迟了，有时甚至还会出现下降的情况。

参考文章

2. 系统中通常会存在被多线程同时访问的共享资源，比如一个共享的数据结构。当有多个线程要修改这个共享资源时，为了保证共享资源的正确性，就需要有额外的机制进行保证，而这个额外的机制，就会带来额外的开销。

   Redis 有 List 的数据类型，并提供出队（LPOP）和入队（LPUSH）操作。假设 Redis 采用多线程设计，如下图所示，现在有两个线程 A 和 B，线程 A 对一个 List 做 LPUSH 操作，并对队列长度加 1。同时，线程 B 对该 List 执行 LPOP 操作，并对队列长度减 1。为了保证队列长度的正确性，Redis 需要让线程 A 和 B 的 LPUSH 和 LPOP 串行执行，这样一来，Redis 可以无误地记录它们对 List 长度的修改。否则，我们可能就会得到错误的长度结果。这就是多线程编程模式面临的共享资源的并发访问控制问题。

3. 并发访问控制一直是多线程开发中的一个难点问题，如果没有精细的设计，比如说，只是简单地采用一个粗粒度互斥锁，就会出现不理想的结果：即使增加了线程，大部分线程也在等待获取访问共享资源的互斥锁，并行变串行，系统吞吐率并没有随着线程的增加而增加。

4. 采用多线程开发一般会引入同步原语来保护共享资源的并发访问，这也会降低系统代码的易调试性和可维护性。为了避免这些问题，Redis 直接采用了单线程模式。

单线程Redis为什么快？

1. 大部分属于内存操作
2. 高效数据库
3. IO多路复用

阻塞式I/O模型与阻塞点

阻塞式I/O处理一个GET请求流程：

1. 监听客户端请求（bind/listen）
2. 和客户端建立连接（accept）阻塞点1
3. 从socket中读取请求（recv）阻塞点2
4. 解析客户端发送请求（parse）
5. 根据请求读取键值对数据（get）
6. 向socket中写数据，最后给客户端返回结果（send）

潜在的阻塞点，分别是 accept() 和 recv()。当 Redis 监听到一个客户端有连接请求，但一直未能成功建立起连接时，会阻塞在 accept() 函数这里，导致其他客户端无法和 Redis 建立连接。类似的，当 Redis 通过 recv() 从一个客户端读取数据时，如果数据一直没有到达，Redis 也会一直阻塞在 recv()。

非阻塞式I/O

Socket 网络模型的非阻塞模式设置，主要体现在三个关键的函数调用上，如果想要使用 socket 非阻塞模式，就必须要了解这三个函数的调用返回类型和设置模式。

在 socket 模型中，不同操作调用后会返回不同的套接字类型。socket() 方法会返回主动套接字，然后调用 listen() 方法，将主动套接字转化为监听套接字，此时，可以监听来自客户端的连接请求。最后，调用 accept() 方法接收到达的客户端连接，并返回已连接套接字。

1. 针对监听套接字，我们可以设置非阻塞模式：当 Redis 调用 accept() 但一直未有连接请求到达时，Redis 线程可以返回处理其他操作，而不用一直等待。但是，你要注意的是，调用 accept() 时，已经存在监听套接字了。
2. 针对已连接套接字设置非阻塞模式：Redis 调用 recv() 后，如果已连接套接字上一直没有数据到达，Redis 线程同样可以返回处理其他操作。我们也需要有机制继续监听该已连接套接字，并在有数据达到时通知 Redis。
3. 这样才能保证 Redis 线程，既不会像基本 I/O 模型中一直在阻塞点等待，也不会导致 Redis 无法处理实际到达的连接请求或数据。

基于多路复用的高性能I/O模型

Linux中的I/O多路复用就是一个线程处理多个I/O流，就是我们经常说的select/epoll(理解IO模型)机制。

Redis单线程运行下该机制允许内核中，同时存在多个监听套接字和已连接套接字。内核会监听这些套接字上的连接请求或者数据请求。一旦有请求到达，就会交给redis线程处理，这样就实现了一个Redis线程处理多个I/O流的效果

下图就是基于多路复用的 Redis IO 模型。图中的多个 FD 就是刚才所说的多个套接字。Redis 网络框架调用 epoll 机制，让内核监听这些套接字。此时，Redis 线程不会阻塞在某一个特定的监听或已连接套接字上，也就是说，不会阻塞在某一个特定的客户端请求处理上。正因为此，Redis 可以同时和多个客户端连接并处理请求，从而提升并发性。

1. select/epoll 提供了基于事件的回调机制，即针对不同事件的发生，调用相应的处理函数。
2. select/epoll 一旦监测到 FD 上有请求到达时，就会触发相应的事件。
3. 这些事件会被放进一个事件队列，Redis 单线程对该事件队列不断进行处理。这样一来，Redis 无需一直轮询是否有请求实际发生，这就可以避免造成 CPU 资源浪费。同时，Redis 在对事件队列中的事件进行处理时，会调用相应的处理函数，这就实现了基于事件的回调。因为 Redis 一直在对事件队列进行处理，所以能及时响应客户端请求，提升 Redis 的响应性能。

Accept、Read处理流程

这两个请求分别对应 Accept 事件和 Read 事件，Redis 分别对这两个事件注册 accept 和 get 回调函数。当 Linux 内核监听到有连接请求或读数据请求时，就会触发 Accept 事件和 Read 事件，此时，内核就会回调 Redis 相应的 accept 和 get 函数进行处理。

Comment and share

众所周知redis作为内存数据库有个重要的特点 — 快。除了因为是在内存中读写快之外，那就是它的查找很快，能够快速的定位到存储位置。能够快速找到的原因基于Redis的数据结构。

数据类型

以下是Redis中的基本类型，也就是数据的保存形式，而数据结构则是这些数据类型在底层的实现。

1. String：简单动态字符串
2. List：双向链表，压缩列表
3. Hash：压缩列表，哈希表
4. Set：哈希表，整数数组
5. Sorted Set：压缩列表，跳表

String类型的底层结构只有一个简单动态字符串，而List，Hash，Set，Sorted Set都有两种底层实现结构。通常情况把这四种类型称为集合类型，特点是：一个键对应了一个集合的数据。

键和值用什么数据结构？

全局哈希表

为了实现快速访问Redis实现了一个全局哈希表保存所有键值对。一个哈希表就是一个数组，数组的每个元素称之为哈希桶。每个哈希桶中保存了键值对数据。哈希桶中的值不保存值本身，而是指向具体的指针。也就是说不管是String还是集合类型，哈希桶中的元素都是指向它们的指针。

优点：

时间复杂度为O(1)查找。

缺点：

往Redis写入大量数据后，哈希表的冲突问题和rehash可能带来的阻塞。

如何解决hash冲突 — 链式hash

Redis解决hash冲突的方式，就是链式hash（跟Java中的HashMap一样）。同一个哈希桶中的多个元素用一个链表保存，它们之间依使用指针连接

缺点：

针对链表上的查找只能采用O(n)时间复杂度的依次查找。

如何解决hash桶上链表只能依次查找慢的问题 — rehash操作

Redis会对哈希会对哈希表做Rehash操作，rehash也就是增加Hash桶数量，让逐渐增多的entry元素能够在更多的桶之间分散保存。Redis默认使用了两个全局hash表：

1. 哈希表I 和哈希表II

2. 一开始插入数据默认使用哈希表I 此时的哈希表II并没有分配空间。

3. 随着数据的逐步增加Redis开始执行Rehash，分为以下三步：

   1. 给哈希表II 分配更大的空间，例如是哈希表I的二倍。
   2. 把哈希表I 中的数据重新映射并拷贝到哈希表II 中
   3. 释放哈希表I 的空间。

   缺点：

   第二步涉及大量的数据拷贝，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，

如何避免Rehash过程中拷贝带来的线程阻塞 — 渐进式 rehash

Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：

压缩列表

压缩列表类似于一个数组，数组中的每一个元素都对应保存着一个数据，和数组不同的是，压缩列表在表头有三个字段zlbytes(列表长度), zltail(列表尾偏移量) 和 zllen(列表entry个数)，zlend(列表结束)

如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。

而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

跳表

有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。

1. 从第一个元素开始，每两个元素选一个出来作为索引。

2. 这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。

3. 此时，我们只需要 4 次查找就能定位到元素 33 了。

   可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时，跳表的查找复杂度就是 O(logN)。

数据结构时间复杂度

操作复杂度

1. 单元素操作

HGET、HSET 和 HDEL 是对哈希表做操作，所以它们的复杂度都是 O(1)；

Set 类型用哈希表作为底层数据结构时，它的 SADD、SREM、SRANDMEMBER 复杂度也是 O(1)。

集合类型支持同时对多个元素进行增删改查，例如 Hash 类型的 HMGET 和 HMSET，Set 类型的 SADD 也支持同时增加多个元素。此时，这些操作的复杂度，就是由单个元素操作复杂度和元素个数决定的。例如，HMSET 增加 M 个元素时，复杂度就从 O(1) 变成 O(M) 了。

2. 范围操作

是指集合类型中的遍历操作，可以返回集合中的所有数据

Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)，比较耗时，我们应该尽量避免。

Redis 从 2.8 版本开始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN），这类操作实现了渐进式遍历，每次只返回有限数量的数据。这样一来，相比于 HGETALL、SMEMBERS 这类操作来说，就避免了一次性返回所有元素而导致的 Redis 阻塞。

3. 统计操作

集合类型对集合中所有元素个数的记录

LLEN 和 SCARD。这类操作复杂度只有 O(1)，这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录了元素的个数统计，因此可以高效地完成相关操作。

4.例外

是指某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。

对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有 O(1)，可以实现快速操作。

总结

Redis 的底层数据结构，这既包括了 Redis 中用来保存每个键和值的全局哈希表结构，也包括了支持集合类型实现的双向链表、压缩列表、整数数组、哈希表和跳表这五大底层结构。

Redis 之所以能快速操作键值对，一方面是因为 O(1) 复杂度的哈希表被广泛使用，包括 String、Hash 和 Set，它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。

不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是 O(N)。这里，我的建议是：用其他命令来替代，例如可以用 SCAN 来代替，避免在 Redis 内部产生费时的全集合遍历操作。

当然，我们不能忘了复杂度较高的 List 类型，它的两种底层实现结构：双向链表和压缩列表的操作复杂度都是 O(N)。因此，我的建议是：因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。

实际开发中Redis各个数据结构的应用场景

引用

《Redis核心技术与实战》

Comment and share

一. 缓存雪崩

“雪崩来临的时候没有一片雪花是无辜的”。缓存雪崩就是大范围甚至于整个redis提供的缓存服务不可用了，进而导致所有的请求都直接到了数据库，甚至于击垮整个服务链路。造成整个服务不可用。

出现原因：

1. 给缓存设置了过期时间，且大范围的缓存数据的过期时间一致。

2. redis服务宕机。

解决方案：

提前预案:

1. 给redis过期时间加随机值预防大面积的缓存同时过期失效。
2. redis集群高可用可用，哨兵机制。

兜底方案:
3. 服务熔断，服务降级。监控到缓存服务不可用时直接返回，或者限制流量直接请求到数据库层。

二. 缓存击穿

相交于缓存雪崩大范围或整体缓存不可用缓存击穿则是指某个热点key过期，导致的缓存失效。常常是一部分热点数据，如秒杀产品的库存数据。

出现原因：
热点数据过期，或者被其他手段删除。

解决方案：

1. 对于热点数据缓存时不设置过期时间。

2. 第一个请求发现热点数据不在redis缓存中，可以先阻塞其他请求，等到第一个请求将数据库数据读出来并缓存到redis后再唤醒其他请求从缓存服务中读取热点数据。



三. 缓存穿透

缓存穿透则是另外一个层面，指的时请求所访问的数据既不在缓存中，也不在数据库中。如果应用持续有大量请求访问数据，就会同时给缓存和数据库带来巨大压力。

出现原因：

1. 业务层误操作访问到了不会存在的数据。

2. 恶意请求攻击

解决方案：

1. 第一个请求发现热点数据不在redis缓存中和数据库中，可以先阻塞其他请求，缓存一个缺省值返回。
2. 利用redis提供的布隆过滤器。
3. 前端有效值校验。

四. 总结

缓存雪崩 ，缓存击穿均属于缓存失效的一种异常缓存雪崩影响范围大于缓存击穿。缓存穿透则是数据本身就不在整个数据存储层。

Comment and share