Redis基础

为什么要用 Redis/为什么要用缓存？

高性能：高频数据并且不会经常改变的话，那么我们就可以很放心地将该用户访问的数据存在缓存中。读快

高并发：使用 Redis 缓存之后QPS（Query Per Second：服务器每秒可以执行的查询次数）很容易达到 10w+提升10倍以上

Redis 为什么这么快？

Redis 基于内存，内存的访问速度是磁盘的上千倍；
Redis 基于 Reactor 模式设计开发了一套高效的事件处理模型，主要是单线程事件循环和 IO 多路复用（Redis 线程模式后面会详细介绍到）；
Redis 内置了多种优化过后的数据结构实现，性能非常高

按照这张图说即可

why-redis-so-fast

Redis 应用

Redis 除了做缓存，还能做什么？

分布式锁 （重点）：通过 Redis 来做分布式锁是一种比较常见的方式。通常情况下，我们都是基于 Redisson 来实现分布式锁。关于 Redis 实现分布式锁的详细介绍，看这篇文章：分布式锁详解open in new window 。
限流：一般是通过 Redis + Lua 脚本的方式来实现限流。相关阅读：《我司用了 6 年的 Redis 分布式限流器，可以说是非常厉害了！》open in new window。
消息队列 ：Redis 自带的 list 数据结构可以作为一个简单的队列使用。Redis 5.0 中增加的 Stream 类型的数据结构更加适合用来做消息队列。它比较类似于 Kafka，有主题和消费组的概念，支持消息持久化以及 ACK 机制。
复杂业务场景 ：通过 Redis 以及 Redis 扩展（比如 Redisson）提供的数据结构，我们可以很方便地完成很多复杂的业务场景比如通过 bitmap 统计活跃用户、通过 sorted set 维护排行榜。
…..

Redis 数据结构

从上面可以看出：

String的底层是（简单动态字符串）
List的底层是（双向链表和压缩链表）
Hash的底层是（压缩链表和哈希表）
Set的底层是（整数数组和哈希表）
Sorted Set底层（压缩链表和跳表）

也就是说

String类型的底层实现只有一种数据结构，也就是简单动态字符串。
而List、Hash、Set和Sorted Set这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据
Redis总体上只有两种数据结构，一种是字符串类型简单字符串-字符串hash，第二种是集合类型hash 字符串- 集合hash

为什么要提供这么多的数据结构呢？

当然是为了追求速度，不同数据类型使用不同的数据结构速度才得以提升。每种数据类型都有一种或者多种数据结构来支撑
redis之所以采用不同的数据结构，其实是在性能和内存使用效率之间的平衡。

redis本质就是一个哈希表

键和值用什么结构组织？

redis是一个k-v数据库。为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。

一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。也就是说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。
不管是键类型还是值类型，哈希桶中的元素保存的都不是值本身，而是指向具体值的指针。

如下图中可以看到，哈希桶中的entry元素中保存了*key和*value指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过*value指针被查找到

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

但是，如果你只是了解哈希表O(1)复杂度和快速查找特性，那么，当你往redis中写入大量数据之后，就可能发现操作有时候会突然变慢了。原因是哈希表的冲突问题和rehash可能带来的操作阻塞

哈希冲突怎么办？

redis解决哈希冲突的方式，就是链式哈希。

如果链过长就会“扩容

redis对会哈希表做rehash操作
什么是rehash操作呢？rehash也就是增加现有的哈希桶数量，让逐渐增大的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

渐进式rehash

其实，为了使得rehash操作更加高效，redis默认使用了两个全局哈希表哈希表1和哈希表2.一开始，当你刚插入数据时，默认使用哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，redis开始执行rehash，这个过程分为三步：

把哈希表2分配更大的空间，比如是当前哈希表1大小的两倍
把哈希表1中的数据重新映射并拷贝到哈希表2中
释放哈希表1的空间

我们就可以从哈希表1切换到哈希表2，用增大的哈希表2保存更多的数据，而原来的哈希表1操作留作下一次rehash扩容备用。

为了避免一次性把哈希表1中的数据都迁移完，会造成redis线程阻塞，无法服务其他请求，redis采用了渐进式rehash

简单来讲就是第二部不阻塞请求，一边拷贝一边接收请求

数据结构操作效率

因为redis本质是一个哈希表：

对于String类型来说，找到哈希桶就能直接进行增删改查了，所以，哈希表的O(1)操作复杂度也就是它的复杂度了
但是，对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步操作。

那集合类型的操作效率又是怎么样的呢？

集合数据操作效率

操作步骤

第一步是通过全局哈希表找到对应的哈希桶位置
第二步是在集合中再增删改查。
- 那么，集合的操作效率和哪些因素相关呢？
  - 首先，与集合的底层数据结构有关。比如，使用哈希表实现的集合，要比使用链表实现的集合访问效率更高
  - 其次，操作效率和这些操作本身的执行特点有关，比如读写一个元素的操作要比读写所有元素的效率高

那集合类型的底层数据结构和操作复杂度是什么样的呢？

Redis基本数据类型应用场景介绍

String 应用场景

需要存储常规数据的场景

举例：缓存 session、token、图片地址、序列化后的对象(相比较于 Hash 存储更节省内存)。
相关命令： SET、GET。

需要计数的场景

举例：用户单位时间的请求数（简单限流可以用到）、页面单位时间的访问数。
相关命令：SET、GET、 INCR、DECR 。

分布式锁

利用 SETNX key value 命令可以实现一个最简易的分布式锁（存在一些缺陷，通常不建议这样实现分布式锁）。

List 应用场景

信息流展示

举例：最新文章、最新动态。
相关命令： LPUSH、LRANGE。

消息队列

Redis List 数据结构可以用来做消息队列，只是功能过于简单且存在很多缺陷，不建议这样做。

相对来说，Redis 5.0 新增加的一个数据结构 Stream 更适合做消息队列一些，只是功能依然非常简陋。和专业的消息队列相比，还是有很多欠缺的地方比如消息丢失和堆积问题不好解决。

Hash 应用场景

对象数据存储场景

举例：用户信息、商品信息、文章信息、购物车信息。
相关命令：HSET （设置单个字段的值）、HMSET（设置多个字段的值）、HGET（获取单个字段的值）、HMGET（获取多个字段的值）。

Set 应用场景

需要存放的数据不能重复的场景

举例：网站 UV 统计（数据量巨大的场景还是 HyperLogLog更适合一些）、文章点赞、动态点赞等场景。
相关命令：SCARD（获取集合数量）。

需要获取多个数据源交集、并集和差集的场景

举例：共同好友(交集)、共同粉丝(交集)、共同关注(交集)、好友推荐（差集）、音乐推荐（差集）、订阅号推荐（差集+交集）等场景。
相关命令：SINTER（交集）、SINTERSTORE （交集）、SUNION （并集）、SUNIONSTORE（并集）、SDIFF（差集）、SDIFFSTORE （差集）。

需要随机获取数据源中的元素的场景

举例：抽奖系统、随机。
相关命令：SPOP（随机获取集合中的元素并移除，适合不允许重复中奖的场景）、SRANDMEMBER（随机获取集合中的元素，适合允许重复中奖的场景）。

Sorted Set 应用场景

需要随机获取数据源中的元素根据某个权重进行排序的场景

举例：各种排行榜比如直播间送礼物的排行榜、朋友圈的微信步数排行榜、王者荣耀中的段位排行榜、话题热度排行榜等等。
相关命令：ZRANGE (从小到大排序) 、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)。

需要存储的数据有优先级或者重要程度的场景 比如优先级任务队列。

举例：优先级任务队列。
相关命令：ZRANGE (从小到大排序) 、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)

总结：

Redis底层数据结构介绍

SDS简单动态字符串

结构

问题：redis是用C语言实现的，为啥还有搞一个SDS动态字符串呢

struct sdshdr{
  int free; // buf[]数组未使用字节的数量
  int len; // buf[]数组所保存的字符串的长度
  char buf[]; // 保存字符串的数组
}

回答：

计算长度效率高：C 语言中字符串的获取字符串的长度，要从头开始遍历，直到「\0」为止，
减少内存分配次数：首先会检查扩容后的len是否达到 buf[] 的长度没有达到可以直接扩，不能就重新分配内存空间
- 分配空间的策略：
  - 空间预分配：简单来说就是每次分配多分配（free部分）min{len,1M}
  - 惰性空间释放: 字符串缩短不会立即回收，以免后续继续增长
存储数据格式无限制，C 中字符串遇到 ‘\0’ 会结束，那 ‘\0’ 之后的数据就读取不上了，但在 SDS中全部以二进制数据格式存储，是根据 len 长度来判断字符串结束的。

LinkedList双端链表

在这里插入图片描述

获取头尾节点包括对头尾节点的增删查改复杂度为O(1),获取长度 O(1),其他O(n)

zipList 压缩列表

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

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

struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    
    
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

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

在这里插入图片描述

它是经过特殊编码，专门为了提升内存使用效率设计的。所有的操作都是通过指针与解码出来的偏移量进行的。
并且压缩列表的内存是连续分配的，遍历的速度很快。

后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。

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

SkipList跳表

为什么要引入跳表呢？

有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。对于有序集合的访问应当由加快机制
具体来说，跳表是在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。如下图：
- 如果我们要在链表中查找33这个元素，只能从头开始遍历链表，查找6次，直到找到33为止。为此，复杂度是O(N)，查找效率很低。
- 为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。这些索引再通过指针指向原始的链表。比如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。此时，我们只需要 4 次查找就能定位到元素 33 了。
- 如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取 1、27、100 作为二级索引，二级索引指向一级索引。这样，我们只需要 3 次查找，就能定位到元素 33 了。
- 本质上就是二分一样的查找复杂度O(logN)

IntSet 整数集合

intset 编码的对象使用整数集合作为底层实现，把所有元素都保存在一个整数集合里面。

HashTable 哈希表

没啥可讲的

合理的数据编码（什么时候使用哪种数据结构）

对于每一种数据类型来说，底层的支持可能是多种数据结构，什么时候使用哪种数据结构，这就涉及到了编码转换问题

那我们就来看看，不同的数据类型是如何进行编码转化的：

String：存储数字的话，采用 int 类型的编码，如果是非数字的话，采用 raw 编码；
List：List 对象的编码可以是 ziplist 或 linkedlist，字符串长度 < 64 字节且元素个数 < 512 使用 ziplist 编码，否则转化为 linkedlist 编码；
注意：这两个条件是可以修改的，在 redis.conf 中：

list-max-ziplist-entries 512
list-max-ziplist-value 64
12

Hash：Hash 对象的编码可以是 ziplist 或 hashtable。
- 当 Hash 对象同时满足以下两个条件时，Hash 对象采用 ziplist 编码：
  - Hash 对象保存的所有键值对的键和值的字符串长度均小于 64 字节
  - Hash 对象保存的键值对数量小于 512 个。
- 否则就是 hashtable 编码。
Set：
- Set 对象的编码可以是 intset 或 hashtable，intset 编码的对象使用整数集合作为底层实现，把所有元素都保存在一个整数集合里面。
- 保存元素为整数且元素个数小于一定范围使用 intset 编码，任意条件不满足，则使用 hashtable 编码；
Zset：
- Zset 对象的编码可以是 ziplist 或 zkiplist，当采用 ziplist 编码存储时，每个集合元素使用两个紧挨在一起的压缩列表来存储。
- Ziplist 压缩列表第一个节点存储元素的成员，第二个节点存储元素的分值，并且按分值大小从小到大有序排列。
- 当 Zset 对象同时满足一下两个条件时，采用 ziplist 编码：
  - Zset 保存的元素个数小于 128。
  - Zset 元素的成员长度都小于 64 字节。

整数数组和压缩列表在查找时间复杂度方面并没有很大的优势，那为什么 Redis 还会把它们作为底层数据结构呢？

复杂度不变前提下省空间：内存利用率，整数数组和压缩列表的设计，充分体现了 Redis“又快又省”特点中的“省”，也就是节省内存空间。整数数组和压缩列表都是在内存中分配一块地址连续的空间，然后把集合中的元素一个接一个地放在这块空间内，非常紧凑。因为元素是挨个连续放置的，我们不用再通过额外的指针把元素串接起来，这就避免了额外指针带来的空间开销。
充分利用CPU缓存，因为数组和压缩列表的内存是连续的，符合程序的局部性原理，就可以充分利用CPU高速缓存，速度会更快
另外，当数组元素超过阈值时，会自动转为hash和跳表，保证查询效率

其他特殊的数据结构

3 种特殊数据结构 ：HyperLogLogs（基数统计）、Bitmap （位存储）、Geospatial (地理位置)。

HyperLogLog

(超小内存去重)

主要用于基数统计，统计UV（UV：网站的独立访客）

如果要实现这么一个功能：

统计 APP或网页的一个页面，每天有多少用户点击进入的次数。同一个用户的反复点击进入记为 1 次。

用 HashMap 这种数据结构就可以，假设 APP 中日活用户达到百万或千万以上级别的话，我们采用 HashMap 的做法，就会导致程序中占用大量的内存。

HyperLogLog 提供不精确的去重计数方案，标准误差为 0.81%，这个精确度已经可以满足 UV 的统计需求了，而且占用的内存不超过12k。
HyperLogLog与伯努利试验有关
用法，pfadd一直添加元素，pfcount返回给定 HyperLogLog 的基数估算值 pfmerge 将多个 HyperLogLog 合并为一个 HyperLogLog，只能存不能取

统计各种计数。比如注册IP数、每日访问IP数、页面实时UV、在线用户数、共同好友数等

Bitmap （位图）

可以用于布尔型数据的存取，比如用户一年的签到记录（DAU：日活跃用户），签到了是1，没签到是0，记录365天，通过 bitcount 指令来统计用户一共签到了多少天，每个签到记录只占用一位，365位大约是46个字节大小，用户上亿时，大大节约了内存空间

Geospatial （地理位置）

存储经纬度，计算两地距离，范围等

geo本质是zset类型 type

Redis 线程模型

对于读写命令来说，Redis 一直是单线程模型。不过，在 Redis 4.0 版本之后引入了多线程来执行一些大键值对的异步删除操作， Redis 6.0 版本之后引入了多线程来处理网络请求（提高网络 IO 读写性能）

Redis 基于 Reactor 模式设计开发了一套高效的事件处理模型 （Netty 的线程模型也基于 Reactor 模式，Reactor 模式不愧是高性能 IO 的基石），这套事件处理模型对应的是 Redis 中的文件事件处理器（file event handler）。由于文件事件处理器（file event handler）是单线程方式运行的，所以我们一般都说 Redis 是单线程模型。

《Redis 设计与实现》有一段话是如是介绍文件事件处理器的，我觉得写得挺不错。

Redis 基于 Reactor 模式开发了自己的网络事件处理器：这个处理器被称为文件事件处理器（file event handler）。

文件事件处理器使用 I/O 多路复用（multiplexing）程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器。

当被监听的套接字准备好执行连接应答（accept）、读取（read）、写入（write）、关闭（close）等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

虽然文件事件处理器以单线程方式运行，但通过使用 I/O 多路复用程序来监听多个套接字，文件事件处理器既实现了高性能的网络通信模型，又可以很好地与 Redis 服务器中其他同样以单线程方式运行的模块进行对接，这保持了 Redis 内部单线程设计的简单性

既然是单线程，那怎么监听大量的客户端连接呢？

Redis 通过 IO 多路复用程序 来监听来自客户端的大量连接（或者说是监听多个 socket），它会将感兴趣的事件及类型（读、写）注册到内核中并监听每个事件是否发生。

大体上来说，Redis 6.0 之前主要还是单线程处理。

那 Redis6.0 之前为什么不使用多线程？ 我觉得主要原因有 3 点：

单线程编程容易并且更容易维护；
Redis 的性能瓶颈不在 CPU ，主要在内存和网络；
多线程就会存在死锁、线程上下文切换等问题，甚至会影响性能。

Redis 内存管理

Redis 给缓存数据设置过期时间有啥用？

因为内存是有限的，如果缓存中的所有数据都是一直保存的话，容易内存溢出。

127.0.0.1:6379> expire key 60 # 数据在 60s 后过期
(integer) 1
127.0.0.1:6379> setex key 60 value # 数据在 60s 后过期 (setex:[set] + [ex]pire)
OK
127.0.0.1:6379> ttl key # 查看数据还有多久过期
(integer) 56

Redis 是如何判断数据是否过期的呢？

Redis 通过一个叫做过期字典（可以看作是 hash 表）来保存数据过期的时间。过期字典的键指向 Redis 数据库中的某个 key(键)，过期字典的值是一个 long long 类型的整数，这个整数保存了 key 所指向的数据库键的过期时间（毫秒精度的 UNIX 时间戳）。

redis过期字典

过期的数据的删除策略

惰性删除 ：只会在取出 key 的时候才对数据进行过期检查。这样对 CPU 最友好，但是可能会造成太多过期 key 没有被删除。

定期删除 ：每隔一段时间抽取一批 key 执行删除过期 key 操作。并且，Redis 底层会通过限制删除操作执行的时长和频率来减少删除操作对 CPU 时间的影响。

定期删除对内存更加友好，惰性删除对 CPU 更加友好。两者各有千秋，所以 Redis 采用的是 定期删除+惰性/懒汉式删除 。

但是，仅仅通过给 key 设置过期时间还是有问题的。可能还是由很多key漏删或者没用到。这样就导致大量过期 key 堆积在内存里，然后就 Out of memory 了。

怎么解决这个问题呢？答案就是：Redis 内存淘汰机制。

Redis 内存淘汰机制

相关问题：MySQL 里有 2000w 数据，Redis 中只存 20w 的数据，如何保证 Redis 中的数据都是热点数据?

Redis 提供 6 种数据淘汰策略：

volatile-lru（least recently used）：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰
volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰
volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰
allkeys-lru（least recently used）：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的 key（这个是最常用的）
allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
no-eviction：禁止驱逐数据，也就是说当内存不足以容纳新写入数据时，新写入操作会报错。这个应该没人使用吧！

4.0 版本后增加以下两种：

volatile-lfu（least frequently used）：从已设置过期时间的数据集（server.db[i].expires）中挑选最不经常使用的数据淘汰
allkeys-lfu（least frequently used）：当内存不足以容纳新写入数据时，在键空间中，移除最不经常使用的 key

Redis 持久化机制

怎么保证 Redis 挂掉之后再重启数据可以进行恢复？

Redis 不同于 Memcached 的很重要一点就是，Redis 支持持久化，而且支持两种不同的持久化操作。Redis 的一种持久化方式叫快照（snapshotting，RDB），另一种方式是只追加文件（append-only file, AOF）。

什么是 RDB 持久化？

Redis 可以通过创建快照来获得存储在内存里面的数据在某个时间点上的副本。Redis 创建快照之后，可以对快照进行备份，可以将快照复制到其他服务器从而创建具有相同数据的服务器副本（Redis 主从结构，主要用来提高 Redis 性能），还可以将快照留在原地以便重启服务器的时候使用。

快照持久化是 Redis 默认采用的持久化方式，在 redis.conf 配置文件中默认有此下配置：

save 900 1           #在900秒(15分钟)之后，如果至少有1个key发生变化，Redis就会自动触发bgsave命令创建快照。

save 300 10          #在300秒(5分钟)之后，如果至少有10个key发生变化，Redis就会自动触发bgsave命令创建快照。

save 60 10000        #在60秒(1分钟)之后，如果至少有10000个key发生变化，Redis就会自动触发bgsave命令创建快照。

RDB 创建快照时会阻塞主线程吗？

Redis 提供了两个命令来生成 RDB 快照文件：

save : 同步保存操作，会阻塞 Redis 主线程；
bgsave : fork 出一个子进程，子进程执行，不会阻塞 Redis 主线程，默认选项。

这里说 Redis 主线程而不是主进程的主要是因为 Redis 启动之后主要是通过单线程的方式完成主要的工作。如果你想将其描述为 Redis 主进程，也没毛病。

什么是 AOF 持久化？

与快照持久化相比，AOF 持久化的实时性更好，因此已成为主流的持久化方案。默认情况下 Redis 没有开启 AOF（append only file）方式的持久化，可以通过 appendonly 参数开启：

appendonly yes

开启 AOF 持久化后每执行一条会更改 Redis 中的数据的命令，Redis 就会将该命令写入到内存缓存 server.aof_buf 中，然后再根据 appendfsync 配置来决定何时将其同步到硬盘中的 AOF 文件。

AOF 文件的保存位置和 RDB 文件的位置相同，都是通过 dir 参数设置的，默认的文件名是 appendonly.aof。

在 Redis 的配置文件中存在三种不同的 AOF 持久化方式，它们分别是：

appendfsync always    #每次有数据修改发生时都会写入AOF文件,这样会严重降低Redis的速度
appendfsync everysec  #每秒钟同步一次，显式地将多个写命令同步到硬盘
appendfsync no        #让操作系统决定何时进行同步

为了兼顾数据和写入性能，用户可以考虑 appendfsync everysec 选项，让 Redis 每秒同步一次 AOF 文件，Redis 性能几乎没受到任何影响。而且这样即使出现系统崩溃，用户最多只会丢失一秒之内产生的数据。当硬盘忙于执行写入操作的时候，Redis 还会优雅的放慢自己的速度以便适应硬盘的最大写入速度。