一提到 Redis ，首先的一个印象就是快！但是之前很少研究过Redis底层的一些实现。之前接触Redis比较少，有一个项目是做限流用到了 Redis，大致原理是记录最近访问过的IP和时间，如果下次再有请求到来匹配IP查找之前是否有过访问，如果有则判断时间差是否小于一小时，小于则禁掉，大于则更新时间戳，如果没有就是第一次访问。

再回顾一下这个限流器的逻辑。

限流器本身最大的瓶颈就是查找是否该 IP 有记录。这里我们利用 Redis 这个高效的 KV数据库实现，这里申请一个 Hash 表，从实现上来看确实快，但是随着 IP 越来越多，也会到瓶颈。

那我们从本质看看为什么快，以及越到后面怎么又慢了。

知其然也要知其所以然，接下来从“数据结构” 和 “线程” 模型两个维度去学习一下Redis

数据结构

Redis 的键值对的数据类型有 String（字符串）、List（列表）、Hash（哈希）、Set（集合） 和 Sorted Set（有序集合） ，其底层数据结构有6种，分别是 简单动态字符串、双向链表、压缩列表、哈希表、跳表、整数数组。他们之间的对应关系如下：

这些数据类型除了String只有一种简单动态字符串的实现外，其余的4种数据类型都有两种底层的实现结构。通常情况下，我们会把这四种类型称为集合类型。他们的特点是一个键对应了一个集合的数据。

  sorted set 也被称为 zset

使用方式参考

哈希表

哈希表可以高效的保存键值对并快速访问。那么为什么哈希表能做到 O(1) 时间复杂度呢？

首先，哈希表基于数组实现，而数组可以根据下标随机访问任意元素。数组之所以可以随机访问，是因为它由连续内存承载，且每个数组元素的大小都相等。于是，当我们知道下标后，把下标乘以元素大小，再加上数组的首地址，就可以获得目标访问地址，直接获取数据。

当然因为 hash 表长度有限的缘故和在有限长度下一定会出现哈希冲突的缘故，哈希桶中的可能也是以链表、红黑树等方式组织的。entry元素保存了 *key 和 *value 的指针。分别指向实际的键和值。

因为这张 hash 表保存了所有的键值对，所以这张表也被称为全局哈希表。

虽然哈希表是非常快的，但是当大量的数据写入后，就不可避免的会存在性能瓶颈，这主要是两点造成的 哈希表冲突 和 rehash 。

哈希冲突

一般来说 hash 桶里的多个 entry 元素是由链表串起来的，当然也可以在hash 桶中用其他数据结构串起来，如果是链表的话，则当大量的 entry 元素落入到同一个 hash 桶中时，就会使得效率变差。这就叫 哈希冲突。

哈希冲突链上的元素只能通过指针逐一再查找再操作，链表的查找效率就不是很高了。

(不过不清楚有没有用hash再解决hash冲突的做法，理论上挺高效的)

rehash

当写入的元素过多达到一定比例，同时，Redis ⽬前没有执⾏ RDB 创建或 AOF 重写操作¹，Redis 底层会对 hash 表做 rehash 操作。rehash 就是增加现有的 hash 桶的数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存。减少单个桶之间的元素数量，从而减少单个桶中的 hash 冲突。

这里详细说一下 rehash 的过程吧，起初为了使 rehash 的操作更高效，Redis 默认使用了两个全局哈希表：hash 1 和 hash 2 。当开始 rehash 过程时，会分三步

1. 将 hash 2 扩容，hash 2 的大小是 hash1 的一倍；
2. 把 hash 1 中的数据重新映射并拷贝到 hash2 中；
3. 释放 hash 1，并将 hash 1 留作下一次 rehash 扩容备用；

但是上述方法在步骤二中涉及大量的数据拷贝，严重时会造成Redis阻塞，所以Redis为了更高效，采用了 渐进式 rehash

Redis rehash 在触发后，实际的执⾏时机有两种：⼀种是在处理请求时，会顺带进⾏数据迁移；另⼀种是，Redis 后台会启动周期性任务进⾏数据迁移。

第一种在处理请求时，进行数据迁移的过程如下，Redis 仍然正常处理客户端的请求，每处理一个请求时，从 hash 1 的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到 hash 2 中，等待处理下一个请求时，再顺带拷贝一个。

这样就将一次性的大量数据拷贝分摊到多次处理请求过程中，避免了耗时操作，保证了数据快速访问。

压缩列表

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes （列表长度）、zltail（列表尾的偏移量） 和 zlen（列表中的entry个数）, 压缩列表为还有一个 zlend（列表结束）

在压缩列表中，如果我们查找定位的第一个元素和最后一个元素，可以通过表头的三个字段的长度直接定位，复杂度是 O(1) ，但是查找其他元素就是逐个查找的模式了，此时的复杂度是 O(N) 。

跳表

由于有序链表只能逐一查找元素，很低效，于是就出现了跳表。我们在查字典的时候，比如想要查 Yes 这个单词，往往是先查 y 位于第几页，在 y 组里查 e 再往后翻几页，再查 s 。这就是和跳表有异曲同工之妙。

具体来说，跳表在链表的基础之上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。

双向链表

双向链表是我们最常见的一个数据结构，一个节点 “ListNode” 包含头指针 prev，尾指针，当前值的value，每个节点都有两个指针，既能从表头根据尾指针找到表尾，又能从表尾根据头指针的prev找到表头，如果将他们串联起来就是双向链表。

其余还有两个，分别是 “整形数组” 和 “动态字符串”，由于这两个数据结构太普通了，就不再这里介绍了。

底层数据结构对应的查找时间复杂度如下：

命令复杂度

• 单元素操作

指的是对单个数据实现的增删改查操作。例如 Hash 类型的 HGET、HSET、HDEL 。Set 类型的 SADD 、SREM、SRANDMEMBER 等，这类操作的复杂度都是 O(1) 。

• 范围操作

指的是集合类型中的遍历操作，可以返回集合中的所有数据，比如 Hash 类型的 HGETALL 和 SET 类型的 SMEMBERS , 或者是返回一个范围内的部分数据，比如 List 类型的 LRANGE 和 ZSet 类型的 ZRANGE 。 这类操作的复杂度一般是 O(N) ，比较耗时，应当尽可能避免。

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

• 统计操作

指的是对集合所有元素个数的记录，例如 LLEN 和 SCARD 。上述两个命令分别是获取列表的长度和获取集合的成员数。这类操作复杂度只有 O(1) ，这时因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录过此类数据。

• 其他

记录数据结构的特殊记录，如压缩列表和双向链表都会记录表头和偏移。这样一来，对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，由于表头、偏移都记录过，所以操作的复杂度都是 O(1)

单线程

这里的单线程通常指的是 Redis 的网络 IO 和键值对读写是由一个线程来完成的，这即是Redis 对外提供键值存储服务的主要流程，但是 Redis 的其他功能，比如持久化、异步删除、集群同步都是额外的线程执行。

所以 Redis 并不是严格意义上的单线程。

为什么 Redis 是一个单线程模型的呢？

因为系统中通常会存在被多个线程访问的共享资源，当多个线程同时访问时就需要加锁，加锁就会带来额外的开销。

而 Redis 采用了 I/O 多路复用技术，使其可以采用单线程进行 I/O、但是如果线程一个操作阻塞了，就全完蛋了。基于多路复用的 高性能 I/O 模型，就是常常听到的 epoll ，采用 epoll 可以允许在内核中同时存在多个监听套接字和已连接的套接字。²

epoll 基于事件的回调机制，针对不同场景的发生调用相应的处理函数。一旦 epoll 监听到 FD 上有请求到达时，就会触发相应的事件。这些事件会被发到一个事件队列中，等待 Redis 去处理，这样，Redis 就不再需要一直轮询是否有实际请求发生。

Redis 为什么会变慢

Redis的单线程处理 I/O 请求的性能瓶颈主要包括2个方面：

1. Redis 本身的操作阻塞，因为Redis 的值的读写是单线程，任意一个请求阻塞会导致整个 Redis 处理请求速度变慢。

如 1. 操作大key，写入删除一个大Key会消耗更多的时间；2. 使用复杂度过高的命令，如 HGETALL 等 O(N) 操作；3. 大量的Key集中过期；4. 淘汰策略，如内存占用过高，每次写入数据都需要淘汰一些 key ；5. AOF 的 always机制，主从全量同步生成 RDB等

2. 并发量非常大时，单线程读写客户端I/O数据存在瓶颈，虽然采用I/O多路复用技术处理网络请求I/O，但是客户端读写数据依旧是同步I/O，只能单线程依次读取客户端的数据，无法利用多核CPU。

针对问题1，除了需要开发人员从代码角度尽量避免大key，另一方面 Redis 在 4.0 推出 lazy-free 机制，将 大key 的释放内存的耗时操作都放到了异步线程中执行，避免对主线程的影响。³