Redis

Redis简介

Redis 是完全开源免费的，使用C语言开发，遵守BSD协议，是一个高性能的key-value数据库。

Redis 与其他 key - value 缓存产品相比有以下三个特点：

Redis支持数据的持久化，可以将内存中的数据保存在磁盘中，重启的时候可以再次加载进行使用。
Redis不仅仅支持简单的key-value类型的数据，同时还提供list，set，zset，hash等数据结构的存储。并且提供对他们的原子性操作。
Redis支持数据的备份，即master-slave模式的数据备份。

Redis 和 memcached 的区别

对于 redis 和 memcached 我总结了下面四点。现在公司一般都是用 redis 来实现缓存，而且 redis 自身也越来越强大了！

redis支持更丰富的数据类型（支持更复杂的应用场景）：Redis不仅仅支持简单的k/v类型的数据，同时还提供list，set，zset，hash等数据结构的存储。memcache支持简单的数据类型，String。
Redis支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用,而Memecache把数据全部存在内存之中。
集群模式：memcached没有原生的集群模式，需要依靠客户端来实现往集群中分片写入数据；但是 redis 目前是原生支持 cluster 模式的.
Memcached是多线程，非阻塞IO复用的网络模型；Redis使用单线程的多路 IO 复用模型。
redis的速度比memcached快很多

Redis应用场景

String

缓存功能：String字符串是最常用的数据类型，不仅仅是Redis，各个语言都是最基本类型，因此，利用Redis作为缓存，配合其它数据库作为存储层，利用Redis支持高并发的特点，可以大大加快系统的读写速度、以及降低后端数据库的压力。
计数器：许多系统都会使用Redis作为系统的实时计数器，可以快速实现计数和查询的功能。而且最终的数据结果可以按照特定的时间落地到数据库或者其它存储介质当中进行永久保存。
共享用户Session：用户重新刷新一次界面，可能需要访问一下数据进行重新登录，或者访问页面缓存Cookie，但是可以利用Redis将用户的Session集中管理，在这种模式只需要保证Redis的高可用，每次用户Session的更新和获取都可以快速完成。大大提高效率。

Hash（底层是一个hashtable?）

这个是类似 Map 的一种结构，这个一般就是可以将结构化的数据，比如一个对象（前提是这个对象没嵌套其他的对象）给缓存在 Redis 里，然后每次读写缓存的时候，可以就操作 Hash 里的某个字段。

但是这个的场景其实还是多少单一了一些，因为现在很多对象都是比较复杂的，比如你的商品对象可能里面就包含了很多属性，其中也有对象。我自己使用的场景用得不是那么多。

List(底层是一个双向链表)

List 是有序列表，这个还是可以玩儿出很多花样的。

比如可以通过 List 存储一些列表型的数据结构，类似粉丝列表、文章的评论列表之类的东西。

比如可以通过 lrange 命令，读取某个闭区间内的元素，可以基于 List 实现分页查询，这个是很棒的一个功能，基于 Redis 实现简单的高性能分页，可以做类似微博那种下拉不断分页的东西，性能高，就一页一页走。

比如可以搞个简单的消息队列，从 List 头怼进去，从 List 屁股那里弄出来。

List本身就是我们在开发过程中比较常用的数据结构了，热点数据更不用说了。

消息队列：Redis的链表结构，可以轻松实现阻塞队列，可以使用左进右出的命令组成来完成队列的设计。比如：数据的生产者可以通过Lpush命令从左边插入数据，多个数据消费者，可以使用BRpop命令阻塞的“抢”列表尾部的数据。
文章列表或者数据分页展示的应用。

比如，我们常用的博客网站的文章列表，当用户量越来越多时，而且每一个用户都有自己的文章列表，而且当文章多时，都需要分页展示，这时可以考虑使用Redis的列表，列表不但有序同时还支持按照范围内获取元素，可以完美解决分页查询功能。大大提高查询效率。

Set（intset(有序，适合容量小)或者hashtable）

Set 是无序集合，会自动去重的那种。

直接基于 Set 将系统里需要去重的数据扔进去，自动就给去重了，如果你需要对一些数据进行快速的全局去重，你当然也可以基于 JVM 内存里的 HashSet 进行去重，但是如果你的某个系统部署在多台机器上呢？得基于Redis进行全局的 Set 去重。

可以基于 Set 玩儿交集、并集、差集的操作，比如交集吧，我们可以把两个人的好友列表整一个交集，看看俩人的共同好友是谁？对吧。

反正这些场景比较多，因为对比很快，操作也简单，两个查询一个Set搞定。

Sorted Set：（底层是跳表）

Sorted set 是排序的 Set，去重但可以排序，写进去的时候给一个分数，自动根据分数排序。

有序集合的使用场景与集合类似，但是set集合不是自动有序的，而Sorted set可以利用分数进行成员间的排序，而且是插入时就排序好。所以当你需要一个有序且不重复的集合列表时，就可以选择Sorted set数据结构作为选择方案。

排行榜：有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜，榜单维护可能是多方面：按照时间、按照播放量、按照获得的赞数等。
用Sorted Sets来做带权重的队列，比如普通消息的score为1，重要消息的score为2，然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行。

微博热搜榜，就是有个后面的热度值，前面就是名称

**跳表：**跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。

添加元素时，索引要添加到几层呢？随机函数，选择要添加到K层！

插入新节点过程
1.新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
2.把索引插入到原链表。O（1）
3.利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。

删除节点过程
1.自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
2.删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳跃表删除操作的时间复杂度是O（logN）。

数据类型

String, Hash, List, Set, Zset, Bitmap, HyperLogLog, Geospatial

理解：redis 都是数据结构外面再套一个key, 所以String 就是我们常见的key -val普通形式

redis 过期策略

1）定时删除，每个k-v对都有一个定时器（timer)，过期就删。内存友好，CPU不友好

2）惰性删除，过期不管，获取时检查，发现过期才删。CPU友好，内存不友好

3）定期删除，字面意思。（默认100ms）

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

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

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

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

但是实际上这还是有问题的，如果定期删除漏掉了很多过期 key，然后你也没及时去查，也就没走惰性删除，此时会怎么样？如果大量过期 key 堆积在内存里，导致 redis 内存块耗尽了，咋整？
答案是：走内存淘汰机制。

内存淘汰机制

no-eviction：禁止驱逐数据，也就是说当内存不足以容纳新写入数据时，新写入操作会报错。这个应该没人使用吧

allkeys-lru (least recently used)：当内存不足以容纳新写入数据时，移除最近最少使用的数据（这个是最常用的）

volatile-lru：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰

volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰

volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰

allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰

4.0版本后增加以下两种：

volatile-lfu (least frequently used)：从已设置过期时间的数据集(server.db[i].expires)中挑选最不经常使用的数据淘汰

allkeys-lfu：当内存不足以容纳新写入数据时，在键空间中，移除最不经常使用的key

A~~A~~A~~A~~A~~A~~A~~A~~A~~A~~~|
B~~~~~B~~~~~B~~~~~B~~~~~~~~~~~B|

考虑上面的情况，如果在|处删除，那么A距离的时间最久，但实际上A的使用频率要比B频繁，所以合理的淘汰策略应该是淘汰B。LFU就是为应对这种情况而生的。

redis 持久化机制(怎么保证 redis 挂掉之后再重启数据可以进行恢复)

很多时候我们需要持久化数据也就是将内存中的数据写入到硬盘里面，大部分原因是为了之后重用数据（比如重启机器、机器故障之后恢复数据），或者是为了防止系统故障而将数据备份到一个远程位置。

Redis不同于Memcached的很重一点就是，Redis支持持久化，而且支持两种不同的持久化操作。Redis的一种持久化方式叫快照（snapshotting，RDB），另一种方式是只追加文件（append-only file,AOF）。这两种方法各有千秋，下面我会详细这两种持久化方法是什么，怎么用，如何选择适合自己的持久化方法。

快照（snapshotting）持久化（RDB）

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

有两个Redis命令可以用于生成RDB文件，一个是SAVE，另一个是BGSAVE

SAVE命令会阻塞Redis服务器进程，直到RDB文件创建完毕。期间服务器不能处理任何命令请求

BGSAVE命令会派生出一个子进程，然后由子进程负责创建RDB文件，服务器进程(父进程)继续处理命令请求

快照持久化是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命令创建快照。

AOF（append-only file）持久化

以日志的形式记录写操作。

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

appendonly yes

开启AOF持久化后每执行一条会更改Redis中的数据的命令，Redis就会将该命令写入硬盘中的AOF文件。AOF文件的保存位置和RDB文件的位置相同，都是通过dir参数设置的，默认的文件名是appendonly.aof。

AOF持久化功能的实现分为命令追加，文件写入，文件同步三个步骤。

文件追加：服务器执行完一个写命令，会将执行的命令以协议格式追加到AOF缓冲区。

AOF文件写入和同步：将AOF缓冲区中的所有内容写入并同步到 AOF 文件中。

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

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

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

开启了RDB时，也可以同时开启AOF，但是恢复的时候会从AOF恢复。

优缺点对比：

1.对于同一份数据来说，AOF日志文件通常比RDB数据快照文件更大，恢复速度慢；

2.RDB与AOF相比，在恢复大的数据集时会更快。

3.AOF可以更好的保护数据不丢失。RDB可能会丢失崩溃到上一次快照的数据。

4.RDB在保存的时候需要复制一个副本。如果比较大的话，占内存。

Redis 4.0 对于持久化机制的优化

Redis 4.0 开始支持 RDB 和 AOF 的混合持久化（默认关闭，可以通过配置项 aof-use-rdb-preamble 开启）。

如果把混合持久化打开，AOF 重写的时候就直接把 RDB 的内容写到 AOF 文件开头。这样做的好处是可以结合 RDB 和 AOF 的优点, 快速加载同时避免丢失过多的数据。当然缺点也是有的， AOF 里面的 RDB 部分是压缩格式不再是 AOF 格式，可读性较差。

补充内容：AOF 重写

显然，.aof文件会越来越大，文件大小当达到某个值的时候，触发AOF重写。从Redis数据库遍历数据，得到set命令。重写得到新的aof文件。

AOF重写可以产生一个新的AOF文件，这个新的AOF文件和原有的AOF文件所保存的数据库状态一样，但体积更小。

AOF重写是一个有歧义的名字，该功能是通过读取数据库中的键值对来实现的，程序无须对现有AOF文件进行任何读入、分析或者写入操作。

AOF后台重写

执行命令BGREWRITEAOF时，除了创建一个子进程（带有服务器进程的数据副本）来重写AOF文件，还会维护一个AOF重写缓冲区，记录子进程运行期间服务器执行的所有写命令。当子进程完成创建AOF文件后，服务器会将重写缓冲区的内容追加到新AOF文件末尾。完成AOF文件后台重写。

Redis事务

DISCARD 取消事务，放弃执行事务块内的所有命令。
EXEC 执行所有事务块内的命令。
MULTI 标记一个事务块的开始。
UNWATCH 取消 WATCH 命令对所有 key 的监视。
WATCH key [key …]
监视一个(或多个) key ，如果在事务执行之前这个(或这些) key 被其他命令所改动，那么事务将被打断。

在redis中，对于一个存在问题的命令，如果在入队的时候就已经出错，整个事务内的命令将都不会被执行（其后续的命令依然可以入队），如果这个错误命令在入队的时候并没有报错，而是在执行的时候出错了，那么redis默认跳过这个命令执行后续命令，不会回滚（没有原子性）。

Redis的集群模式

主从模式（复制）

所有的写请求都被发送到主数据库。在由主数据库将数据同步到从数据库上。从数据库主要用于执行读操作缓解系统的读压力。

SYNC命令非常消耗资源。为了解决旧版复制功能在断线重复制的低效问题，Redis从2.8开始使用PSYNC命令代替SYNC命令。

PSYNC分为完整重同步和部分重同步，完整重同步时PSYNC和SYNC一样，部分重同步则用于处理断线后重复制情况。（如果丢失的命令不是太多，不需要生成RDB文件，更高效，免得复制还存在从数据库的数据）

复制的实现

从服务器发送SLAVEOF命令，就可以让一个从服务器复制一个主服务器

SLAVEOF <master_ip> <master_port>

主从模式的优点：

1.读写分离，分担master的读压力

2.master和slave之间的同步是非阻塞的，客户端在这期间可以提交查询或更新请求

缺点：

1.不具备自动容错与恢复功能，master或slave宕机都可能导致客户端请求失败，需要等待机器重启或手动切换客户端IP才能恢复

2.难以支持在线扩容，Redis的容量受限于单机配置

哨兵模式

哨兵模式基于主从复制模式，只是引入了哨兵来监控与自动处理故障。

其原理是哨兵通过发送命令，等待Redis服务器响应，从而监控运行的多个Redis服务器。

这里的哨兵有两个作用

通过发送命令，让Redis服务器返回监控其运行状态，包括主服务器和从服务器。
当哨兵监测到master宕机，会自动将slave切换成master，然后通过发布订阅模式通知其他的从服务器，修改配置文件，让它们切换主机。（master宕机后重新上线会变成从服务器）

然而一个哨兵进程对Redis服务器进行监控，可能会出现问题，为此，我们可以使用多个哨兵进行监控。各个哨兵之间还会进行监控，这样就形成了多哨兵模式。

哨兵模式优点：

1.主从的优点都有

2.master宕机时，可以切换master主机，系统可用性更高

缺点：

集群模式

哨兵模式基本可以满足一般生产的需求，具备高可用性。但是当数据量过大到一台服务器存放不下的情况时，主从模式或哨兵模式就不能满足需求了，这个时候需要对存储的数据进行分片，将数据存储到多个Redis实例中。cluster模式的出现就是为了解决单机Redis容量有限的问题，将Redis的数据根据一定的规则分配到多台机器。

cluster可以说是sentinel和主从模式的结合体，通过cluster可以实现主从和master重选功能，所以如果配置两个副本三个分片的话，就需要六个Redis实例。因为Redis的数据是根据一定规则分配到cluster的不同机器的，当数据量过大时，可以新增机器进行扩容。

集群模式特点：

无中心架构，所有的节点都是一主一从（也可以是一主多从），其中从不提供服务，仅作为备用（备份）
不支持同时处理多个key（如MSET/MGET），因为redis需要把key均匀分布在各个节点上，
并发量很高的情况下同时创建key-value会降低性能并导致不可预测的行为
支持在线增加、删除节点
客户端可以连接任何一个主节点进行读写执行之前这个(或这些) key 被其他命令所改动，那么事务将被打断。

集群模式优点：

1.无中心架构，每个节点都是平等的关系，存储的数据各不相同

2.可以动态拓展或删除节点

缺点：

不支持同时处理多个key

一致性Hash

对于分布式缓存，不同机器上存储不同对象的数据。为了实现这些缓存机器的负载均衡，可以使用m=hash(o) mod n 来定位对象缓存的存储机器：o为对象的名称，n为机器的数量，m为机器的编号。

普通hash在大部分时候都可以工作得很好，然而，当机器需要扩容或者机器出现宕机的情况下，事情就比较棘手了。
当机器扩容，需要增加一台缓存机器时，负载均衡器使用的式子变成：

m = hash(o) mod (n + 1) ——式子2

当机器宕机，机器数量减少一台时，负载均衡器使用的式子变成：

m = hash(o) mod (n - 1) ——式子3

这样的话，大部分的图片计算出来的缓存位置都会改变，造成大面积的缓存失效。可能导致缓存雪崩。

一致性hash算法正是为了解决此类问题的方法，它可以保证当机器增加或者减少时，对缓存访问命中的概率影响减至很小。

一致性hash算法通过一个叫作一致性hash环的数据结构实现。这个环的起点是0，终点是2^32 - 1，并且起点与终点连接，环的中间的整数按逆时针分布，故这个环的整数分布范围是[0, 2^32-1]

一致性hash算法解决了分布式环境下机器增加或者减少时，简单的取模运算无法获取较高命中率的问题。通过虚拟节点的使用，一致性hash算法可以均匀分担机器的负载，使得这一算法更具现实的意义。正因如此，一致性hash算法被广泛应用于分布式系统中。

一致性hash

缓存雪崩和缓存穿透问题解决方案

什么是缓存雪崩？

简介：缓存同一时间大面积的失效，所以，后面的请求都会落到数据库上，造成数据库短时间内承受大量请求而崩掉。

eg:对于系统 A，假设每天高峰期每秒 5000 个请求，本来缓存在高峰期可以扛住每秒 4000 个请求，但是缓存机器意外发生了全盘宕机。缓存挂了，此时 1 秒 5000 个请求全部落数据库，数据库必然扛不住，它会报一下警，然后就挂了。此时，如果没有采用什么特别的方案来处理这个故障，DBA 很着急，重启数据库，但是数据库立马又被新的流量给打死了。这就是缓存雪崩。

有哪些解决办法？

事前：尽量保证整个 redis 集群的高可用性，发现机器宕机尽快补上。选择合适的内存淘汰策略。
事中：本地ehcache缓存 + hystrix限流&降级，避免MySQL崩掉
事后：利用 redis 持久化机制保存的数据尽快恢复缓存

什么是缓存穿透？

缓存穿透说简单点就是大量请求的 key 根本不存在于缓存中，导致请求直接到了数据库上，根本没有经过缓存这一层。举个例子：某个黑客故意制造我们缓存中不存在的 key 发起大量请求，导致大量请求落到数据库。

对于系统A，假设一秒 5000 个请求，结果其中 4000 个请求是黑客发出的恶意攻击。

黑客发出的那 4000 个攻击，缓存中查不到，每次你去数据库里查，也查不到。

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

有哪些解决办法？

最基本的就是首先做好参数校验，一些不合法的参数请求直接抛出异常信息返回给客户端。比如查询的数据库 id 不能小于 0、传入的邮箱格式不对的时候直接返回错误消息给客户端等等。

缓存无效 key :

如果缓存和数据库都查不到某个 key 的数据就写一个到 redis 中(可设置为空值)去并设置过期时间，具体命令如下：SET key value EX 10086。这种方式可以解决请求的 key 变化不频繁的情况，如果黑客恶意攻击，每次构建不同的请求key，会导致 redis 中缓存大量无效的 key 。很明显，这种方案并不能从根本上解决此问题。如果非要用这种方式来解决穿透问题的话，尽量将无效的 key 的过期时间设置短一点比如 1 分钟。

布隆过滤器

布隆过滤器是一个非常神奇的数据结构，类似于一个hash set，用于**快速判某个元素是否存在于集合中。**通过它我们可以非常方便地判断一个给定数据是否存在与海量数据中。我们需要的就是判断 key 是否合法，有没有感觉布隆过滤器就是我们想要找的那个“人”。具体是这样做的：把所有可能存在的请求的值都存放在布隆过滤器中，当用户请求过来，我会先判断用户发来的请求的值是否存在于布隆过滤器中。不存在的话，直接返回请求参数错误信息给客户端，存在的话才会走redis流程。

缓存击穿

缓存击穿，就是说某个 key 非常热点，访问非常频繁，处于集中式高并发访问的情况，当这个 key 在失效的瞬间，大量的请求就击穿了缓存，直接请求数据库，就像是在一道屏障上凿开了一个洞。

解决方式也很简单，可以将热点数据设置为永远不过期；或者基于 redis or zookeeper 实现互斥锁，等待第一个请求构建完缓存之后，再释放锁，进而其它请求才能通过该 key 访问数据（走redis）。

如何解决 Redis 的并发竞争 Key 问题：分布式锁

所谓 Redis 的并发竞争 Key 的问题也就是多个系统同时对一个 key 进行写操作，但是最后执行的顺序和我们期望的顺序不同，这样也就导致了结果的不同！

推荐一种方案：分布式锁（zookeeper 和 redis 都可以实现分布式锁）。（如果不存在 Redis 的并发竞争 Key 问题，不要使用分布式锁，这样会影响性能）

Redis实现（setnx）见分布式锁

第二种方案：

在并发量过大的情况下,可以通过消息中间件进行处理,把并行读写进行串行化。

把Redis.set操作放在队列中使其串行化,必须的一个一个执行。这种方式在一些高并发的场景中算是一种通用的解决方案。

第三种方案：乐观锁

利用watch命令使用CAS。redis中可以使用watch命令会监视给定的key，当exec时候如果监视的key从调用watch后发生过变化，则整个事务会失败。也可以调用watch多次监视多个key。这样就可以对指定的key加乐观锁了。注意watch的key是对整个连接有效的，事务也一样。如果连接断开，监视和事务都会被自动清除。当然了exec，discard，unwatch命令都会清除连接中的所有监视。

缓存淘汰策略

在缓存数据过多时需要使用某种淘汰算法决定淘汰哪些数据。常用的有以下几种。

FIFO(First In First Out) : 判断被存储的时间，离目前最远的数据优先被淘汰。

LRU(Least Recently Used) : 判断缓存最近被使用的时间，距离当前时间最远的数据优先被淘汰。

LFU(Least Frequently Used) : 在一段时间内，被使用次数最少的缓存优先被淘汰。

常见面试题

redis为啥比mysql快？

1）.Redis是基于内存存储的，MySQL是基于磁盘存储的

2）.Redis存储的是k-v格式的数据。时间复杂度是O(1),常数阶，而MySQL引擎的底层实现是B+Tree，时间复杂度是O(logn)，对数阶。Redis会比MySQL快一点点。

3）.MySQL数据存储是存储在表中，查找数据时要先对表进行全局扫描或者根据索引查找，这涉及到磁盘的查找，磁盘查找如果是按条点查找可能会快点，但是顺序查找就比较慢；而Redis不用这么麻烦，本身就是存储在内存中，会根据数据在内存的位置直接取出。

4）.Redis是单线程的多路复用IO，单线程避免了线程切换的开销，而多路复用IO避免了IO等待的开销，在多核处理器下提高处理器的使用效率可以对数据进行分区，然后每个处理器处理不同的数据。

Redis没有直接使用C字符串

没有使用C字符串(即以空字符’\0’结尾的字符数组)作为默认的字符串表示，而是使用了SDS。SDS是简单动态字符串(Simple Dynamic String)的缩写。Reidis的SDS在C字符串的基础上加入了free和len字段

RDB和AOF的优缺点

RDB持久化

优点：RDB文件紧凑，体积小，网络传输快，适合全量复制；恢复速度比AOF快很多。当然，与AOF相比，RDB最重要的优点之一是对性能的影响相对较小。

缺点：RDB文件的致命缺点在于其数据快照的持久化方式决定了必然做不到实时持久化，而在数据越来越重要的今天，数据的大量丢失很多时候是无法接受的，因此AOF持久化成为主流。此外，RDB文件需要满足特定格式，兼容性差（如老版本的Redis不兼容新版本的RDB文件）。

AOF持久化

与RDB持久化相对应，AOF的优点在于支持秒级持久化、兼容性好，缺点是文件大、恢复速度慢、对性能影响大。

判断key是否存在删除key

exists key +key名字 del key

手撸一个LRU算法

class LRUcache<K,V> extends LinkedHashMap<K,V> {
    private final int CACHE_SIZE;
    /**
    传递进来最多能缓存多少数据
    @param cacheSize 缓存大小
    **/
    public LREcache(int cacheSize) {
        //true 表示让linkedHashMap按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部。
        super((int)Math.ceil(cacheSize / 0.75) + 1, 0.75f, true)
        //Math.ceil()向上取整，加载因子
        CACHE_SIZE = cacheSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.entry<K,V> eldest) {
        //当map中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
        return size() > CACHE_SIZE;
    }
}

如果有大量的key需要设置同一时间过期，一般需要注意什么？

如果大量的key过期时间设置的过于集中，到过期的那个时间点，redis可能会出现短暂的卡顿现象。严重的话会出现缓存雪崩，我们一般需要在时间上加一个随机值，使得过期时间分散一些。

布隆过滤器

它 实际上 是一个很长的二进制向量和一系列随机映射函数 (哈希函数)，实际上你也可以把它 简单理解 为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。

当布隆过滤器说某个值存在时，这个值 可能不存在；当它说不存在时，那么 一定不存在。

无法删除某个元素，可以考虑带计数器的布隆过滤器。

常用的五种数据结构及其底层结构

Redis过期时间是如何实现的？

底层有两个dict 一个dict对应key value ，一个dict对应key expireTime，在查询的时候回去看有无expireTime，过期则删除。

Redis rehash操作

以下是哈希表渐进式 rehash 的详细步骤：

为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
在字典中维持一个索引计数器变量 rehashidx ，并将它的值设置为 0 ，表示 rehash 工作正式开始。
在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ，当 rehash 工作完成之后，程序将 rehashidx 属性的值增一。
随着字典操作的不断执行，最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ，这时程序将 rehashidx 属性的值设为 -1 ，表示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。

因为在进行渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行：比如说，要在字典里面查找一个键的话，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找，诸如此类。

另外，在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到 ht[1] 里面，而 ht[0] 则不再进行任何添加操作：这一措施保证了 ht[0] 包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。

写时复制技术（COW copy on write）

fork()会产生一个和父进程完全相同的子进程(除了pid)
如果按传统的做法，会直接将父进程的数据拷贝到子进程中，拷贝完之后，父进程和子进程之间的数据段和堆栈是相互独立的。

但是，以我们的使用经验来说：往往子进程都会执行exec()来做自己想要实现的功能。

所以，如果按照上面的做法的话，创建子进程时复制过去的数据是没用的(因为子进程执行exec()，原有的数据会被清空)

既然很多时候复制给子进程的数据是无效的，于是就有了Copy On Write这项技术了，原理也很简单：

fork创建出的子进程，与父进程共享内存空间。也就是说，如果子进程不对内存空间进行写入操作的话，内存空间中的数据并不会复制给子进程，这样创建子进程的速度就很快了！(不用复制，直接引用父进程的物理空间)。
并且如果在fork函数返回之后，子进程第一时间exec一个新的可执行映像，那么也不会浪费时间和内存空间了。

另外的表达方式：

在fork之后exec之前两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。

当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间。

Copy On Write技术实现原理：

fork()之后，kernel把父进程中所有的内存页的权限都设为read-only，然后子进程的地址空间指向父进程。当父子进程都只读内存时，相安无事。当其中某个进程写内存时，CPU硬件检测到内存页是read-only的，于是触发页异常中断（page-fault），陷入kernel的一个中断例程。中断例程中，kernel就会把触发的异常的页复制一份，于是父子进程各自持有独立的一份。

Copy On Write技术好处是什么？

COW技术可减少分配和复制大量资源时带来的瞬间延时。
COW技术可减少不必要的资源分配。比如fork进程时，并不是所有的页面都需要复制，父进程的代码段和只读数据段都不被允许修改，所以无需复制。

Copy On Write技术缺点是什么？

如果在fork()之后，父子进程都还需要继续进行写操作，那么会产生大量的分页错误(页异常中断page-fault)，这样就得不偿失。

Raft算法

Redis集群和Raft协议都采用了主从节点的结构，只有主节点才能响应客户端的请求，从节点的唯一任务就是备份主节点的数据。当我们有多个节点的时候，什么时候选择主节点，选择谁当主节点就是两个重要的问题。前者就是Fault Detection问题，后者才是Leader Election问题。

在Raft中有两个参数比较重要，一个是HeartbeatTimeout，一个是ElectionTimeout
leader节点至多隔HeartbeatTimeout就要给所有的follower节点发送心跳信息，来告知所有的follower节点自己还活着，那么每个follower如果发现在上次与leader节点交互过了ElectionTimeout之后还未收到来自leader的新的信息，就会直接认为leader节点故障了，从而开始发起竞选。论文中用如下的状态变化图进行描述

leader选举

follower在ElectionTimeout内未收到来自leader的消息，则认为leader故障，从而发起竞选。变成Candidate状态
设置新任期，向所有节点拉票，如果得到大多数节点的Vote，则称为新的master
更新所有节点任期