面试题-redis

redis底层数据结构

String

因为redis是使用C语言开发的，自然没有java的哪些字符串类库，在redis中自定义了一种字符串，叫做SDS（简单动态字符串）（Simple Dynamic String）

sds的底层是使用一个结构体实现的：

1
2
3
4
5
6
7
8
struct sdshdr {
	// 记录 buf 数组中已使用字节的数量，它等于 SDS 所保存字符串的长度
	int len;
	// 记录 buf 数组中未使用字节的数量
	int free;
	// 字节数组，用于保存字符串
	char buf[];
};

image-20230323123918257

  • free 属性的值为0， 表示这个SDS没有分配任何未使用空间
  • len属性的值为5，表示这个SDS保存了一个五字节长的字符串。
  • buf属性是一个char类型的数组，数组的前五个字节分别保存了’R’、‘e’、‘d’、‘i’、‘s’五个字符，而最后一个字节则保存了空字符’\0’。

SDS 遵循C字符串以空字符串结尾的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面，并且为空字符分配额外的 1 字节空间

image-20230323123958954

这个SDS和之前展示的SDS一样,都保存了字符串值”Redis”。这个SDS和之前展示的SDS的区别在于，这个SDS为buf数组分配了五字节未使用空间，所以它的free属性的值为5(图中使用五个空格来表示五字节的未使用空间)

SDS与C字符串的区别：

（1）常数复杂度获取字符串长度：直接访问len就可以了。

（2）杜绝缓冲区溢出，当对SDS进行修改时，会先检查空间是否满足修改所需要的要求，如果不满足，进行空间扩展，再修改。C如果不进行内存重新分配的话就会发生溢出。

（3）减少内存重新分配次数：当增加和缩短字符串的时候，C每次都需要一次内存分配，扩展内存空间或者释放内存空间。由于内存分配涉及复杂的算法，需要系统调用，很耗时，而SDS通过空间预分配和惰性空间两种优化策略。

空间预分配：

  • 对SDS修改之后，SDSlen属性的值小于1MB, 那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。例，SDS 的len将变成13字节，那么程序也会分配13字节的未使用空间，实际长度将变成 13+13+1=27 字节

  • 对SDS修改之后，SDS 的长度大于等于1MB，那么程序会分配1MB 的未使用空间。如果进行修改之后，SDS的len将变成30MB，SDS的buf数组的实际长度为 30 MB + 1 MB + 1bytes

惰性空间释放

优化SDS的字符串缩短操作:缩短字符串时，程序并不立即回收缩短多出来的字节，而是使用free属性记录起来，并等待将来使用。

（4）二进制安全：通过使用二进制安全的SDS，而不是C字符串，使得Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。

举个例子： 存入 “Redis Cluster” 这种格式就不能用C字符串来保存，因为C字符串所用的函数只会识别出其中的 “Redis” 而忽略之后的 “Cluster”。为了确保 Redis 可以使用不同的场景，SDS 的 API 都是二进制安全的，所有SDS API 都会以处理二进制的方式来处理 SDS 里的数据，数据在被写入时是什么样的，它被读取时就是什么样的。

list

ziplist

存储在连续内存上的特殊双向链表

其中各部分代表的含义如下：

  • zlbytes：4个字节（32bits），表示ziplist占用的总字节数
  • zltail：4个字节（32bits），表示ziplist中最后一个节点在ziplist中的偏移字节数
  • entries：2个字节（16bits），表示ziplist中的元素数
  • entry：长度不定，表示ziplist中的数据
  • zlend：1个字节（8bits），表示结束标记，这个值固定为ff（255）

特点：

  1. ziplist 为了节省内存，采用了紧凑的连续存储。所以在修改操作下并不能像一般的链表那么容易，需要从新分配新的内存，然后复制到新的空间。

  2. ziplist类似一个封装的数组，通过zltail可以方便地进行追加和删除尾部数据、使用entries可以方便地计算长度

  3. 新增或更新元素可能会出现连锁更新现象。

  4. 不能保存过多的元素，否则查询效率就会降低。

    通过以上的3、4点就引出了quicklist。

连锁更新现象：

image-20230323133702901

quicklist

由于ziplist不能保存过多的元素，否则查询性能大大降低，并且会发生连锁更新的情况。因此提出quicklist。

结合了原先 linkedlist 与 ziplist 各自的优势，本质还是一个链表，只不过链表的每个节点是一个 ziplist。

quicklist 是综合考虑了时间效率与空间效率引入的新型数据结构。结合了原先 linkedlist 与 ziplist 各自的优势，本质还是一个链表，只不过链表的每个节点是一个 ziplist。

image-20230323135547951

可毕竟还是使用了 ziplist，本质上无法避免连锁更新的问题，于是乎在 5.0 版本设计出另一个内存紧凑型数据结构 listpack，于 7.0 版本替换掉 ziplist。

listpack

listpack 也是一种紧凑型数据结构，用一块连续的内存空间来保存数据，并且使用多种编码方式来表示不同长度的数据来节省内存空间。

image-20230323135617155

  • tot-bytes，也就是 total bytes，占用 4 字节，记录 listpack 占用的总字节数。
  • num-elements，占用 2 字节，记录 listpack elements 元素个数。
  • elements，listpack 元素，保存数据的部分。、
  • listpack-end-byte，结束标志，占用 1 字节，值固定为 255。

element 不再像 ziplist 的 entry 保存前一项的长度。

image-20230323135630954

整数集合

整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

整数集合是Redis用于保存整数值的集合抽象数据结构，它可以保存int16_t、int32_t、int64_t的整数值，且保证集合中不出现重复元素。

1
2
3
4
5
6
7
8
typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
}

整数集合的升级

当我们向一个已经存在的整数集合中添加元素时，如果加入的元素的数据类型比contents[]数组元素的数据类型长，则整数集合需要进行升级，举个例子，我要在上面那个大小5的16位整数集合中插入一个类型为int32_t的整数65535：

  1. 升级首先要做的是，根据新元素的长度，扩大空间，目前有5个元素，加入一个后有6个，且int16_t的元素要升级为int32_t类型（需要6 * 32 = 192位的空间），因此需要先动态分配内存空间如下：

img

  1. 移动元素的位置，将14632往后移动到新的位置，末尾留下一个位置存放32位的65535

img

  1. 同理移动233、18、-5、-6370，并最后将末尾的空间中存入65535

img

整数集合不支持降级

如果因为插入一个32位的整数使得原本16位的contents[]数组转变为32位，后面又删去了这个32位的整数，这个整数集合将不会降级成16位的contents[]数组

redis常用的基本类型

key

（1）keys * ：查看当前库中所有的key

image-20220607134236942

（2）exists key ：判断某个 key 是否存在

（3）type key：查看你的 key 是什么类型

（4）del key ：删除指定的 key 数据 / unlink key 根据 value 选择非阻塞删除

（5）expire key 10 ：10 秒钟：为给定的 key 设置过期时间

（6）ttl key ：查看还有多少秒过期，-1 表示永不过期，-2 表示已过期

（7）select ：命令切换数据库

（8）dbsize ：查看当前数据库的 key 的数量

（9） flushdb ：清空当前库 / flushall ：通杀全部库

String

底层数据结构：动态字符串，是可以修改的字符串，内部结构上类似于java的ArrayList。

常用命令

（1）set <key><value>：添加键值对(内容能用字符串表示的)如果设置相同的key，则前面的value被覆盖

（2）get <key>：查询对应键值

（3）append <key><value>：将给定的 追加到原值的末尾

（4）strlen <key>：获得值的长度

（5）setnx <key><value>：只有在 key 不存在时 设置 key 的值

（6）incr <key> ：将 key 中储存的数字值增 1 （只能对数字操作）

（7）decr <key> ：将 key 中储存的数字值减 1 （只能对数字操作）

（8） incrby / decrby <key><步长>：将 key 中储存的数字值增减。自定义步长。

  • 是原子性的：所谓原子操作是指不会被线程调度机制打断的操作；
  • （1）在单线程中， 能够在单条指令中完成的操作都可以认为是”原子操作”，因为中断只能发生于指令之间。
  • （2）在多线程中，不能被其它进程（线程）打断的操作就叫原子操作。
  • Redis 单命令的原子性主要得益于 Redis 的单线程。

（9）mset <key1><value1><key2><value2> .....同时设置一个或多个 key-value 对

（10）mget <key1><key2><key3> .....同时获取一个或多个 value

（11）msetnx <key1><value1><key2><value2> ..... ：同时设置一个或多个 key-value 对，当且仅当所有给定 key 都不存在

（12）getrange <key><起始位置><结束位置>： 获得值的范围

（13）setrange <key><起始位置><value> ：用 覆写所储存的字符串值，从<起始位置>开始(索引从 0 开始)。

（14）setex <key><过期时间><value>：设置键值的同时，设置过期时间，单位秒

（15）getset <key><value>：以新换旧，设置了新值同时获得旧值。

List

当数据量比较少的时候，使用的是ziplist，因为普通的链表需要的附加指针空间太大，会比较浪费空间。

当数据量比较大的时候，使用的是quickList（也就是将多个ziplist使用双指针串起来使用），既满足快速插入，又不会出现太大的冗余。

单键多值 按照插入顺序排序。你可以添加一个元素到列表的头部（左边）或者尾部（右边） 它的底层实际是个双向链表，

常用命令

（1）lpush/rpush <key><value1><value2><value3> ....： 从左边/右边插入一个或多个值。
（2）lpop/rpop <key>从左边/右边吐出一个值。值在键在，值光键亡。
（3）rpoplpush <key1><key2>从列表右边吐出一个值，插到列表左边。
（4）lrange <key><start><stop>按照索引下标获得元素(从左到右)
（5）lrange mylist 0 -1 0 左边第一个，-1 右边第一个，（0-1 表示获取所有）
（6）lindex <key><index>按照索引下标获得元素(从左到右)
（7）llen <key>获得列表长度
（8）linsert <key> before <value><newvalue>在的后面插入插入值
（9）lrem <key><n><value>从左边删除 n 个 value(从左到右)
（10）lset<key><index><value>将列表 key 下标为 index 的值替换成 value

Set

Set 数据结构是 dict 字典，字典是用哈希表实现的。

特殊之处在于 set 是可以自动排重的

常用命令

sadd <key><value1><value2> .....将一个或多个 member 元素加入到集合 key 中，已经存在的 member 元素将被忽略
smembers <key>取出该集合的所有值。
sismember <key><value>判断集合是否为含有该值，有 1，没有 0
scard<key>返回该集合的元素个数。

srem <key><value1><value2> .... 删除集合中的某个元素。
spop <key>随机从该集合中吐出一个值。
srandmember <key><n>随机从该集合中取出 n 个值。不会从集合中删除 。
smove <source><destination>value 把集合中一个值从一个集合移动到另一个集合
sinter <key1><key2>返回两个集合的交集元素。
sunion <key1><key2>返回两个集合的并集元素。
sdiff <key1><key2>返回两个集合的差集元素(key1 中的，不包含 key2 中的)

ZSet

zset 底层使用了两个数据结构
（1）hash，hash 的作用就是关联元素 value 和权重 score，保障元素 value 的唯一性，可以通过元素 value 找到相应的 score 值。
（2）跳跃表，跳跃表的目的在于给元素 value 排序，根据 score 的范围获取元素列表。

image-20230322124156151

Redis 有序集合 zset 与普通集合 set 非常相似，是一个没有重复元素的字符串集合。
不同之处是有序集合的每个成员都关联了一个评分（score）,这个评分（score）被用来按照从最低分到最高分的方式排序集合中的成员。集合的成员是唯一的，但是评分可以是重复了 。

常用命令

zadd <key><score1><value1><score2><value2>…将一个或多个 member 元素及其 score 值加入到有序集 key 当中。
zrange <key><start><stop> [WITHSCORES]返回有序集 key 中，下标在之间的元素带 WITHSCORES，可以让分数一起和值返回到结果集。
zrangebyscore key minmax [withscores] [limit offset count]返回有序集 key 中，所有 score 值介于 min 和 max 之间(包括等于 min 或 max )的成员。有序集成员按 score 值递增(从小到大)次序排列。
zrevrangebyscore key maxmin [withscores] [limit offset count]同上，改为从大到小排列。

zincrby <key><increment><value> 为元素的 score 加上增量
zrem <key><value>删除该集合下，指定值的元素
zcount <key><min><max>统计该集合，分数区间内的元素个数
zrank <key><value>返回该值在集合中的排名，从 0 开始。

Hash

Hash 类型对应的数据结构是两种： ziplist（压缩列表）， hashtable（哈希表）。 当field-value 长度较短且个数较少时， 使用 ziplist， 否则使用 hashtable。

常用命令

hset <key><field><value>：给集合中的 键赋值
hget <key1><field>：从集合取出 value
hmset <key1><field1><value1><field2><value2>... ：批量设置 hash 的值
hexists<key1><field>：查看哈希表 key 中， 给定域 field 是否存在。
hkeys <key>：列出该 hash 集合的所有 field
hvals <key>：列出该 hash 集合的所有 value
hincrby <key><field><increment>：为哈希表 key 中的域 field 的值加上增量 1 -1
hsetnx <key><field><value>：将哈希表 key 中的域 field 的值设置为 value ， 当且仅当域field 不存在

跳表

https://blog.csdn.net/qq_34412579/article/details/101731935

什么是跳表

​ 跳表是可以实现二分查找的有序单链表。

image-20221126193316929

跳表查找的时间复杂度为O(logn)

​ 时间复杂度 = 索引的高度 * 每层索引遍历元素的个数。

​ 先来求跳表的索引高度。如下图所示，假设每两个结点会抽出一个结点作为上一级索引的结点，原始的链表有n个元素，则一级索引有n/2 个元素、二级索引有 n/4 个元素、k级索引就有 n/2k个元素。最高级索引一般有2个元素，即：最高级索引 h 满足 2 = n/2^h，即 h = log2n - 1，最高级索引 h 为索引层的高度加上原始数据一层，跳表的总高度 h = log2n。

image-20221126193402245

​ 图中所示，现在到达第 k 级索引，我们发现要查找的元素 x 比 y 大比 z 小，所以，我们需要从 y 处下降到 k-1 级索引继续查找，k-1级索引中比 y 大比 z 小的只有一个 w，所以在 k-1 级索引中，我们遍历的元素最多就是 y、w、z，发现 x 比 w大比 z 小之后，再下降到 k-2 级索引。所以，k-2 级索引最多遍历的元素为 w、u、z。其实每级索引都是类似的道理，每级索引中都是两个结点抽出一个结点作为上一级索引的结点。 现在我们得出结论：当每级索引都是两个结点抽出一个结点作为上一级索引的结点时，每一层最多遍历3个结点。

跳表的索引高度 h = log2n，且每层索引最多遍历 3 个元素。所以跳表中查找一个元素的时间复杂度为 O(3*logn)，省略常数即：**O(logn)**。

跳表的空间复杂度O(n)

跳表是典型的”空间换时间“的思想

假如原始链表包含 n 个元素，则一级索引元素个数为 n/2、二级索引元素个数为 n/4、三级索引元素个数为 n/8 以此类推。所以，索引节点的总和是：n/2+n/4+n/8 … 8+4+2 = n-2，**空间复杂度是 O(n)**。

跳表的插入数据

通过randomLevel()方法返回当前元素要插入的层级

image-20221126193921939

整个插入过程的路径与查找元素路径类似， 每层索引中插入元素的时间复杂度 O(1)，所以整个插入的时间复杂度是 **O(logn)**。

跳表的删除数据

​ 跳表删除数据时，要把索引中对应节点也要删掉。如下图所示，如果要删除元素 9，需要把原始链表中的 9 和第一级索引的 9 都删除掉。

image-20221126193957439

​ 删除元素的过程跟查找元素的过程类似，只不过在查找的路径上如果发现了要删除的元素 x，则执行删除操作。跳表中，每一层索引其实都是一个有序的单链表，单链表删除元素的时间复杂度为 O(1)，索引层数为 logn 表示最多需要删除 logn 个元素，所以删除元素的总时间包含 查找元素的时间 加 删除 logn个元素的时间 为 O(logn)+O(logn) = 2 O(logn)，忽略常数部分，**删除元素的时间复杂度为 O(logn)**。

缓存雪崩

缓存雪崩是指当缓存中有大量的key在同一时刻过期，或者Redis直接宕机了，导致大量的查询请求全部到达数据库，造成数据库查询压力骤增，甚至直接挂掉。

解决：只需要将每个key的过期时间打散即可，使它们的失效点尽可能均匀分布。

缓存击穿

缓存击穿是指当缓存中某个热点数据过期了，在该热点数据重新载入缓存之前，有大量的查询请求穿过缓存，直接查询数据库。
解决：设置key永不过期

缓存穿透

缓存穿透是指查询一个缓存中和数据库中都不存在的数据，导致每次查询这条数据都会透过缓存，直接查库，最后返回空。

解决：布隆过滤器

AOF重写

当 AOF 变得太大时，Redis 能够在后台自动重写 AOF 产生一个新的 AOF 文件，这个新的 AOF 文件和原有的 AOF 文件所保存的数据库状态一样，但体积更小。

AOF重写的执行流程：

image-20221007091501846

  • 触发重写，执行bgrewriteaof命令
  • 父进程fork子进程进行重写，fork子进程的同时，父进程阻塞，fork完毕父进程继续接受指令。
  • 子进程在创建新的aof的同时，子进程根据内存快照，按照命令合并规则写入到新的AOF文件。父进程继续接受指令， 存储到aof_buf和aof_rewirte_buf缓存中，所以父进程继续往旧的aof文件中备份，同时也要往新的aof文件中备份。
  • 新的aof备份完成
  • 父进程备份新的文件创建完成
  • 将aof_rewrite_buf缓存中的备份到新的aof文件中
  • 新的文件替换旧的aof文件。

说一下redis和Memcached的区别和共同点

共同点：

  • 都基于内存数据库，一般都用来当作缓存使用
  • 都有过期策略
  • 两者的性能都非常高

区别：

  • redis支持更丰富的数据类型，（list，set，zset，hash）
  • redis支持持久化操作
  • redis有灾难恢复机制，因为有持久化功能
  • redis在服务器内存使用完之后，将不用的数据放到磁盘上，而Memcached在服务器中内存使用后，直接报异常
  • memcached是多线程，非阻塞IO复用模型，redis是单线程，多路IO复用模型
  • Memcached 过期数据的删除策略只用了惰性删除，而 Redis 同时使用了惰性删除与定期删除。

应用场景

  • Redis：数据量较小的高性能操作和运算上。
  • memcache：用于在动态系统中减少数据库负载，提升性能; 做缓存，提高性能（适合读多写少，对于数据量比较大，可以采用 sharding）。
  • MongoDB: 主要解决海量数据的访问效率问题。

redis如何使用事务

Redis 可以通过 MULTI，EXEC，DISCARD 和 WATCH 等命令来实现事务(transaction)功能。

MULTI 命令后可以输入多个命令，Redis 不会立即执行这些命令，而是将它们放到队列，当调用了exec 命令后，再执行所有的命令。

1
2
3
4
5
6
7
8
9
> MULTI
OK
> SET PROJECT "JavaGuide"
QUEUED
> GET PROJECT
QUEUED
> EXEC
1) OK
2) "JavaGuide"

DISCARD：取消一个事务，它会清空事务队列中保存的所有命令。

1
2
3
4
5
6
7
8
> MULTI
OK
> SET PROJECT "JavaGuide"
QUEUED
> GET PROJECT
QUEUED
> DISCARD
OK

你可以通过[WATCH命令监听指定的 Key，当调用 EXEC 命令执行事务时，如果一个被 WATCH 命令监视的 Key 被 其他客户端/Session 修改的话，整个事务都不会被执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 客户端 1
> SET PROJECT "RustGuide"
OK
> WATCH PROJECT
OK
> MULTI
OK
> SET PROJECT "JavaGuide"
QUEUED

# 客户端 2
# 在客户端 1 执行 EXEC 命令提交事务之前修改 PROJECT 的值
> SET PROJECT "GoGuide"

# 客户端 1
# 修改失败，因为 PROJECT 的值被客户端2修改了
> EXEC
(nil)
> GET PROJECT
"GoGuide"

redis不支持原子性

Redis 官网也解释了自己为啥不支持回滚。简单来说就是 Redis 开发者们觉得没必要支持回滚，这样更简单便捷并且性能更好。Redis 开发者觉得即使命令执行错误也应该在开发过程中就被发现而不是生产过程中。

你可以将 Redis 中的事务就理解为 ：Redis 事务提供了一种将多个命令请求打包的功能。然后，再按顺序执行打包的所有命令，并且不会被中途打断。

Redis单线程为什么这么快？

1.redis是基于内存的，内存的读写速度非常快；

2.redis是单线程的，省去了很多上下文切换线程的时间；

3.采用IO多路复用机制

IO多路复用

https://www.cnblogs.com/crazymakercircle/p/10225159.html#autoid-h2-5-0-0

IO多路复用的基本原理就是，单个线程不断的轮询select/epoll系统调用所负责的成百上千的scoket连接，当某个或者某些连接有数据到达的时候，就返回这些可读写的连接，因此好处就是通过一次select/epoll的系统调用，就可以读写一个甚至成百上千的连接。

在这里插入图片描述

发起一个多路复用IO的的read读操作系统调用，流程是这个样子：

（1）不断的进行select/epoll系统调度，查询可以读的连接，只要有连接数据到达，就返回该连接（当用户线程调用select时，整个线程被block）

（2）建立连接后，发起read系统调用，将内核缓冲区的数据复制到用户缓冲区，然后返回结果。

（3）用户线程读取了数据。接触block。

IO多路复用，用到两个系统调用，一个是select/epoll调用，另一个是IO读取调用。

优点：使用select/epoll就可以同属处理成千上万的连接，与一条线程维护一条连接相比，系统不必创建线程，不必维护线程，减少了系统的开销。

缺点：读写过程是阻塞的。

redis中基本数据类型的zset底层是什么

（1）hash，hash 的作用就是关联元素 value 和权重 score，保障元素 value 的唯一性，可以通过元素 value 找到相应的 score 值。

（2）跳跃表，跳跃表的目的在于给元素 value 排序，根据 score 的范围获取元素列表。

image-20221028180718550

redis是多线程还是单线程，什么时候引入的多线程，为什么之前使用单线程

单线程，可以设置为多线程，。

在redis6.0之后引入的多线程，。

为什么之前不使用多线程？

（1）单线程编程容易并且更容易维护；

（2）多线程就会存在死锁、线程上下文切换等问题，甚至会影响性能。

如果需要开启多线程，则需要修改redis的配置文件：

io-threads-do-reads yes

redis的文件处理器通过IO多路复用来监听大量的客户端连接。

image-20221028183529128

为什么redis6.0之后使用多线程

因为对redis有更高的要求。

redis对于小数据包来说，对于80%的公司已经足够使用了。

但随着越来越复杂的业务场景，有些公司达到上亿的交易量，因此需要更大的查询效率。

为了提升查询效率，很多公司的做法是部署Redis集群，尽可能的提升redis机器数，但这种做法的资源消耗是巨大的。

经过分析限制redis的性能主要瓶颈出现在网络IO处理上，虽然采用了IO多路复用技术，但在处理网络请求时，调用select的过程时阻塞的，也就是这个过程会阻塞线程，如果并发量很高，就会成为瓶颈。

如果能采用多线程，使得网路处理的请求并发进行，就可以大大提升性能。还可以充分利用CPU的多核优势

因此采用多个IO线程处理网络的请求，网络的请求和解析由其他线程完成，主线程进行内存的读写。

注意：只是网络的请求使用多IO线程，对于读写命令，redis仍然采用单线程来处理

redis怎么更新缓存

为什么要更新缓存？

使用缓存后，数据要同时保存到数据库和缓存中，如果数据库中的数据发生变化，而缓存中的数据没有改变，会导致数据不一致的问题，因此要更新缓存。

常见的更新缓存的策略：

（1）内存淘汰：

redis自带内存淘汰机制，当内存不足时自动淘汰部分数据。

redis提供了6种淘汰策略：

  • volatile-lru（least recently used）：从已经设置时间的数据集种挑选最近最少使用的数据进行淘汰。
  • volatile-ttl：从已设置过期时间的数据集，中挑选将要过期的数据淘汰
  • allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的 key
  • allkeys-random：从数据集中任意选择数据淘汰

4.0版本后增加了以下两种：

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

（2）超时剔除

手动给缓存的数据添加ttl，到期后自动删除。

（3）主动更新

编写业务逻辑，更新数据库数据后同步更新缓存

三种实现方法：

  • 由缓存的调用者，在更新数据库时同时更新缓存
  • 将缓存与数据库整合为一个服务，由服务来维护一致性，调用者无需关心缓存一致性。
  • crud在缓存中进行，由其他线程异步的将缓存数据持久化到数据库，

这三种方法最好的就是：第一个（由缓存的调用者，在更新数据库时同时更新缓存）

总结以上缓存更新策略的最佳方案方法：

（1）低一致性需求：使用redis自带的内存淘汰机制（就是数据不会长久发生变化的情况下，例如：查询店铺类型缓存）

（2）高一致性需求：主动更新，并以超时剔除作为兜底方案（查询店铺详情）

  • 读操作：

    • 缓存命中则直接返回
    • 缓存未命中，则查询数据库，并写入缓存，设定超时时间

  • 写操作：

    • 先写数据库，然后再删除缓存
    • 确保数据库与缓存操作的原子性

redis单线程模型

redis的过期策略

redis 过期策略是：定期删除+惰性删除。

所谓定期删除，指的是 redis 默认是每隔 100ms 就随机抽取一些设置了过期时间的 key，检查其是否过期，如果过期就删除。

假设 redis 里放了 10w 个 key，都设置了过期时间，你每隔几百毫秒，就检查 10w 个 key，那 redis 基本上就死了，cpu 负载会很高的，消耗在你的检查过期 key 上了。注意，这里可不是每隔 100ms 就遍历所有的设置过期时间的 key，那样就是一场性能上的灾难。实际上 redis 是每隔 100ms 随机抽取一些key 来检查和删除的。

但是问题是，定期删除可能会导致很多过期 key 到了时间并没有被删除掉，那咋整呢？所以就是惰性删除了。这就是说，在你获取某个 key 的时候，redis 会检查一下 ，这个 key 如果设置了过期时间那么是否过期了？如果过期了此时就会删除，不会给你返回任何东西。

获取 key 的时候，如果此时 key 已经过期，就删除，不会返回任何东西。

答案是：走内存淘汰机制。

如何保证缓存与数据库的双写一致性？

最经典的缓存+数据库读写的模式，就是 Cache Aside Pattern。- 读的时候，先读缓存，缓存没有的话，就读数据库，然后取出数据后放入缓存，同时返回响应。- 更新的时候，先更新数据库，然后再删除缓存。

为什么是删除缓存，而不是更新缓存？

举个栗子，一个缓存涉及的表的字段，在 1 分钟内就修改了 20 次，或者是 100 次，那么缓存更新 20 次、100 次；但是这个缓存在 1 分钟内只被读取了 1 次，有大量的冷数据。实际上，如果你只是删除缓存的话，那么在 1 分钟内，这个缓存不过就重新计算一次而已，开销大幅度降低。用到缓存才去算缓存

明确了是删除缓存后，目前存在两种选择:

  • 先更新数据库，再删除缓存
  • 先删除缓存，再更新数据库

（1）先更新数据库，再删除缓存

问题：更新数据库成功，线程出现问题，缓存删除失败，缓存中的是旧数据，数据不一致，有两种解决方式；失败重试和异步更新

失败重试：把删除的key放入到消息队中，从消息队列中进行删除，（有个缺点，首先会对业务代码造成入侵，其次引入了消息队列，增加了系统的不确定性。）

MySQL和Redis的数据一致性问题_一致性问题_04

异步更新：因为更新数据库时会往 binlog 中写入日志，所以我们可以启动一个监听 binlog变化的服务（比如使用阿里的 canal开源组件），然后在客户端完成删除 key 的操作。如果删除失败的话，再发送到消息队列。

（2）先删除缓存，再更新数据库

问题：如果先删除Redis缓存数据，然而还没有来得及写入MySQL，另一个线程就来读取。这个时候发现缓存为空，则去Mysql数据库中读取旧数据写入缓存，此时缓存中为脏数据。出现了数据不一致的问题。可以采用延时双删的策略解决。

MySQL和Redis的数据一致性问题_缓存_05

延时双删：就是更新数据库之后，再删除一次缓存。

MySQL和Redis的数据一致性问题_缓存_06

redis 的并发竞争问题是什么？如何解决这个问题？了解redis 事务的 CAS 方案吗？

乐观锁介绍：

watch指令在redis事物中提供了CAS的行为。为了检测被watch的keys在是否有多个clients同时改变引起冲突，这些keys将会被监控。如果至少有一个被监控的key在执行exec命令前被修改，整个事物将会回滚，不执行任何动作，从而保证原子性操作，并且执行exec会得到null的回复。

乐观锁工作机制：

watch 命令会监视给定的每一个key，当exec时如果监视的任一个key自从调用watch后发生过变化，则整个事务会回滚，不执行任何动作。注意watch的key是对整个连接有效的，事务也一样。如果连接断开，监视和事务都会被自动清除。当然exec，discard，unwatch命令，及客户端连接关闭都会清除连接中的所有监视。还有，如果watch一个不稳定(有生命周期)的key并且此key自然过期，exec仍然会执行事务队列的指令。

在这里插入图片描述

redis的Watch机制是什么？

Redis Watch 命令用于监视一个(或多个) key ，如果在事务执行之前这个(或这些) key 被其他命令所改动，那么事务将被打断。注意使用multi 开始事务，exec 提交事务。

缓存雪崩

缓存雪崩是指缓存同一时间大面积的失效（由于对缓存数据设置了相同的过期时间），所以，后面的请求都会落到数据库上，造成数据库短时间内承受大量请求而崩掉。（多个key）

解决方案：

  1. 构建多级缓存架构：nginx缓存+redis缓存+其他缓存（ehcache等）

  2. 使用锁或队列：使用锁或在队列的方式来保证不会有大量的线程对数据库进行读写，从而避免失效时大量的并发请求到底层存储系统上，不适用高并发情况

  3. 将缓存失效时间分散开：设置缓存过期时间时加上一个随机值，避免缓存在同一时间过期

  4. 限流

redis-caching-avalanche-solution

限流组件，可以设置每秒的请求，有多少能通过组件，剩余的未通过的请求，怎么办？走降级！可以返回一些默认的值，或者友情提示，或者空值

好处：

  • 数据库绝对不会死，限流组件确保了每秒只有多少个请求能通过。
  • 只要数据库不死，就是说，对用户来说，2/5 的请求都是可以被处理的。
  • 只要有 2/5 的请求可以被处理，就意味着你的系统没死，对用户来说，可能就是点击几次刷不出来页面，但是多点几次，就可以刷出来了。

缓存穿透

缓存穿透是指查询一个根本不存在的数据，缓存层和持久层都不会命中，请求都会压到数据库，从而压垮数据库。

举个栗子。数据库 id 是从 1 开始的，结果黑客发过来的请求 id 全部都是负数。这样的话，缓存中不会有，请求每次都“绕过缓存”，直接查询数据库。这种恶意攻击场景的缓存穿透就会直接把数据库给打死。

redis-caching-penetration

解决方式很简单：

每次系统 A 从数据库中只要没查到，就写一个空值到缓存里去，比如 set -999 UNKNOWN 。然后设置一个过期时间，这样的话，下次有相同的 key 来访问的时候，在缓存失效之前，都可以直接从缓存中取数据。

这种方式虽然是简单，在某些场景（如数据量大的博客）下不优雅，还可能会缓存过多的空值，更加优雅的方式就是：使用 bitmap 布隆过滤（将数据库中所有的查询条件，放入布隆过滤器中，当一个查询请求过来时，先经过布隆过滤器进行查，如果判断请求查询值存在，则继续查；如果判断请求查询不存在，直接丢弃。）

缓存击穿

缓存击穿是指缓存中没有但数据库中有的某一个数据（一般是缓存时间到期），这时由于并发用户特别多，同时读缓存没读到数据，又同时去数据库去取数据，引起数据库压力瞬间增大，造成过大压力（有点像一把尖刀瞬间击穿到数据库）

某一个数key失效，但同时有许多用户并发的访问数据库，导致数据库压力过大

不同场景下的解决方式可如下：

  • 若缓存的数据是基本不会发生更新的，则可尝试将该热点数据设置为永不过期。
  • 若缓存的数据更新频繁或者在缓存刷新的流程耗时较长的情况下，可以利用定时线程在缓存过期前主动地重新构建缓存或者延后缓存的过期时间，以保证所有的请求能一直访问到对应的缓存。
  • 预先设置热门数据：在redis高峰访问前，把一些热门数据提前存入redis中，加大这些热门数据key的时长实时调整 现场监控哪些数据是热门数据，实时调整key的过期时长

布隆过滤器

是由一个很长的二进制(0或1)向量和一系列随机映射函数组成。

布隆过滤器可以用于检索一个元素是否在一个集合中。它可以告诉你某种东西一定不存在或者可能存在。当布隆过滤器说，某种东西存在时，这种东西可能不存在；当布隆过滤器说，某种东西不存在时，那么这种东西一定不存在。

布隆过滤器 优点：A. 空间效率高，占用空间少 B. 查询时间短

　　　　　　　 缺点：A. 有一定的误判率 B. 元素不能删除

原理

　当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点（使用多个哈希函数对元素key (bloom中不存value) 进行哈希，算出一个整数索引值，然后对位数组长度进行取模运算得到一个位置，每个无偏哈希函数都会得到一个不同的位置），把它们置为1。

　检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：① 如果这些点有任何一个为0（如下图的e），则被检元素一定不在；如果都是1（如下图的d），并不能完全说明这个元素就一定存在其中，有可能这些位置为1是因为其他元素的存在，这就是布隆过滤器会出现误判的原因。

img

使用布隆过滤器的场景：

黑名单校验

　识别垃圾邮件，只要发送者在黑名单中的，就识别为垃圾邮件。假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。

原本有10亿个号码，现在又来了10万个号码，要快速准确判断这10万个号码是否在10亿个号码库中？

解决办法一：将10亿个号码存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。

解决办法二：将10亿号码放入内存中，比如Redis缓存中，这里我们算一下占用内存大小：10亿*8字节=8GB，通过内存查询，准确性和速度都有了，但是大约8gb的内存空间，挺浪费内存空间的。

那么对于类似这种，大数据量集合，如何准确快速的判断某个数据是否在大数据量集合中，并且不占用内存，布隆过滤器应运而生了。

校招 > 开发
面试题-redis
http://example.com/2022/10/06/面试题-redis/
作者
zlw
发布于
2022年10月6日
许可协议