一、Redis的数据结构

1.字符串String

2.列表list

3.哈希hash

4.集合set

5.有序集合sorted set

• string–>简单的key-value

• list–>有序列表(底层是双向链表)–>可做简单队列

• set–>无序列表(去重)–>提供一系列的交集、并集、差集的命令

• hash–>哈希表–>存储结构化数据

• sorted set–>有序集合映射(member-score)–>排行榜

跳表------sorted set的重要底层数据结构

跳表是一种基于有序链表的扩展
利用类似索引的思想，从链表中提取部分节点。

1.新节点插入：

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

2.节点删除：

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

跳表的优点是维持结构平衡的成本比较低，完全依靠随机；而二叉查找树在经过多次删除后，需要重新调整结构平衡。

6.Redis的一些细节

• (1：服务器在执行某些命令的时候，会先检查给定的键的类型能否执行指定的命令。

  • 比如我们的数据结构是sortset，但你使用了list的命令。这是不对的，服务器会检查一下我们的数据结构是什么才会进一步执行命令

• (2：Redis的对象系统带有引用计数实现的内存回收机制。

  • 对象不再被使用的时候，对象所占用的内存会释放掉

• (3：Redis会共享值为0到9999的字符串对象

• (4：对象会记录自己的最后一次被访问时间，这个时间可以用于计算对象的空转时间。

二、Redis服务器中的数据库

Redis的数据库就是使用字典(哈希表)来作为底层实现的，对数据库的增删改查都是构建在字典(哈希表)的操作之上的。

过期策略

删除策略有三种：

• 定时删除(对内存友好，对CPU不友好)

  到时间点上就把所有过期的键删除了。

• 惰性删除(对CPU极度友好，对内存极度不友好)

  每次从键空间取键的时候，判断一下该键是否过期了，如果过期了就删除。

• 定期删除(折中)

  每隔一段时间去删除过期键，限制删除的执行时长和频率。

Redis采用的是惰性删除+定期删除两种策略，所以说，在Redis里边如果过期键到了过期的时间了，未必被立马删除的！

内存淘汰机制

使用 Redis 缓存数据时，为了提高缓存命中率，需要保证缓存数据都是热点数据。可以将内存最大使用量设置为热点数据占用的内存量，然后启用allkeys-lru淘汰策略，将最近最少使用的数据淘汰。

三、Redis持久化

Redis有两种持久化方式：

• RDB（快照）：将某一时刻的所有数据存储到一个RDB文件里；
• AOF：当Redis服务器执行写命令的时候，将执行的写命令保存到AOF文件中。

RDB持久化

RDB持久化可以手动执行，也可以根据服务器配置定期执行。RDB持久化所生成的RDB文件是一个经过压缩的二进制文件，Redis可以通过这个文件还原数据库的数据。

有两个命令可以生成RDB文件：

• SAVE会阻塞Redis服务器进程，服务器不能接收任何请求，直到RDB文件创建完毕为止。

• BGSAVE创建出一个子进程，由子进程来负责创建RDB文件，服务器进程可以继续接收请求。

Redis服务器在启动的时候，如果发现有RDB文件，就会自动载入RDB文件(不需要人工干预)

• 服务器在载入RDB文件期间，会处于阻塞状态，直到载入工作完成。

除了手动调用SAVE或者BGSAVE命令生成RDB文件之外，我们可以使用配置的方式来定期执行：

在默认的配置下，如果以下的条件被触发，就会执行BGSAVE命令：

save 900 1              #在900秒(15分钟)之后，至少有1个key发生变化，
save 300 10            #在300秒(5分钟)之后，至少有10个key发生变化
save 60 10000        #在60秒(1分钟)之后，至少有10000个key发生变化

AOF持久化

AOF持久化功能的实现可以分为3个步骤：

• 命令追加：命令写入aof_buf缓冲区

• 文件写入：调用flushAppendOnlyFile函数，考虑是否要将aof_buf缓冲区写入AOF文件中

• 文件同步：考虑是否将内存缓冲区的数据真正写入到硬盘

AOF重写
某些写命令可以合并起来，减小文件体积。

• 要值得说明的是：AOF重写不需要对现有的AOF文件进行任何的读取、分析。AOF重写是通过读取服务器当前数据库的数据来实现的！

AOF后台重写
AOF后台重写是不会阻塞主进程接收请求的，新的写命令请求可能会导致当前数据库和重写后的AOF文件的数据不一致！

为了解决数据不一致的问题，Redis服务器设置了一个AOF重写缓冲区，这个缓存区会在服务器创建出子进程之后使用。

RDB和AOF对过期键的策略

RDB持久化对过期键的策略：

1. 执行SAVE或者BGSAVE命令创建出的RDB文件，程序会对数据库中的过期键检查，已过期的键不会保存在RDB文件中。

2. 载入RDB文件时，程序同样会对RDB文件中的键进行检查，过期的键会被忽略。

AOF持久化对过期键的策略：

1. 如果数据库的键已过期，但还没被惰性/定期删除，AOF文件不会因为这个过期键产生任何影响(也就说会保留)，当过期的键被删除了以后，会追加一条DEL命令来显示记录该键被删除了

2. 重写AOF文件时，程序会对AOF文件中的键进行检查，过期的键会被忽略。

复制模式：

• 主服务器来控制从服务器统一删除过期键(保证主从服务器数据的一致性)

RDB和AOF用哪个？

RDB和AOF并不互斥，它俩可以同时使用。

• RDB的优点：载入时恢复数据快、文件体积小。

• RDB的缺点：会一定程度上丢失数据(因为系统一旦在定时持久化之前出现宕机现象，此前没有来得及写入磁盘的数据都将丢失。)

• AOF的优点：丢失数据少(默认配置只丢失一秒的数据)。

• AOF的缺点：恢复数据相对较慢，文件体积大

如果Redis服务器同时开启了RDB和AOF持久化，服务器会优先使用AOF文件来还原数据(因为AOF更新频率比RDB更新频率要高，还原的数据更完善)

四、Redis是单线程为什么速度快？

1）纯内存操作

2）核心是基于非阻塞的IO多路复用机制

3）单线程避免了多线程的频繁上下文切换问题

五、主从复制

复制有两步：
1.同步，2.命令传播

同步包括：完整重同步，部分重同步

完整重同步：

• 从服务器向主服务器发送PSYNC命令

• 收到PSYNC命令的主服务器执行BGSAVE命令，在后台生成一个RDB文件。并用一个缓冲区来记录从现在开始执行的所有写命令。

• 当主服务器的BGSAVE命令执行完后，将生成的RDB文件发送给从服务器，从服务器接收和载入RBD文件。将自己的数据库状态更新至与主服务器执行BGSAVE命令时的状态。

• 主服务器将所有缓冲区的写命令发送给从服务器，从服务器执行这些写命令，达到数据最终一致性。

部分重同步：

部分重同步功能由以下部分组成：

• 主从服务器的复制偏移量

• 主服务器的复制积压缓冲区

• 服务器运行的ID(run ID)

首先我们来解释一下上面的名词：

• 复制偏移量：执行复制的双方都会分别维护一个复制偏移量

• 主服务器每次传播N个字节，就将自己的复制偏移量加上N

• 从服务器每次收到主服务器的N个字节，就将自己的复制偏移量加上N

通过对比主从复制的偏移量，就很容易知道主从服务器的数据是否处于一致性的状态！

那断线重连以后，从服务器向主服务器发送PSYNC命令，报告现在的偏移量是36，那么主服务器该对从服务器执行完整重同步还是部分重同步呢？？这就交由复制积压缓冲区来决定。

当主服务器进行命令传播时，不仅仅会将写命令发送给所有的从服务器，还会将写命令入队到复制积压缓冲区里面(这个大小可以调的)。如果复制积压缓冲区存在丢失的偏移量的数据，那就执行部分重同步，否则执行完整重同步。

服务器运行的ID(run ID)实际上就是用来比对ID是否相同。如果不相同，则说明从服务器断线之前复制的主服务器和当前连接的主服务器是两台服务器，这就会进行完整重同步。

六、哨兵机制

Redis提供了哨兵(Sentinel)机制供我们解决上面的情况。如果主服务器挂了，我们可以将从服务器升级为主服务器，等到旧的主服务器(挂掉的那个)重连上来，会将它(挂掉的主服务器)变成从服务器。

• 这个过程叫做主备切换(故障转移)

哨兵机制：

• Sentinel不停地监控Redis主从服务器是否正常工作
• 如果某个Redis实例有故障，那么哨兵负责发送消息通知管理员
• 如果主服务器挂掉了，会自动将从服务器提升为主服务器(包括配置都会修改)。
• Sentinel可以作为配置中心，能够提供当前主服务器的信息。

选举领头的Sentinel：
当一个主服务器被认为客观下线以后，监视这个下线的主服务器的各种Sentinel会进行协商，选举出一个领头的Sentinel，领头的Sentinel会对下线的主服务器执行故障转移操作。

选举领头Sentinel的规则也比较多，总的来说就是先到先得(哪个快，就选哪个)

选举出领头的Sentinel之后，领头的Sentinel会对已下线的主服务器执行故障转移操作，包括三个步骤：

• 在已下线主服务器属下的从服务器中，挑选一个转换为主服务器

• 让已下线主服务器属下的所有从服务器改为复制新的主服务器

• 已下线的主服务器重新连接时，让他成为新的主服务器的从服务器

挑选某一个从服务器作为主服务器也是有策略的，大概如下：

• （1）跟master断开连接的时长

• （2）slave优先级

• （3）复制offset

• （4）run id

tips:目前为止的主从+哨兵架构可以说Redis是高可用的，但要清楚的是：Redis还是会丢失数据的

丢失数据有两种情况：

• 异步复制导致的数据丢失

  • 有部分数据还没复制到从服务器，主服务器就宕机了，此时这些部分数据就丢失了

• 脑裂导致的数据丢失

  • 有时候主服务器脱离了正常网络，跟其他从服务器不能连接。此时哨兵可能就会认为主服务器下线了(然后开启选举，将某个从服务器切换成了主服务器)，但是实际上主服务器还运行着。这个时候，集群里就会有两个服务器(也就是所谓的脑裂)。

  • 虽然某个从服务器被切换成了主服务器，但是可能客户端还没来得及切换到新的主服务器，客户端还继续写向旧主服务器写数据。旧的服务器重新连接时，会作为从服务器复制新的主服务器(这意味着旧数据丢失)。

七、缓存

缓存雪崩

这就是缓存雪崩：

• Redis挂掉了，请求全部走数据库。

• 对缓存数据设置相同的过期时间，导致某段时间内缓存失效，请求全部走数据库。

如何解决缓存雪崩？

对于“对缓存数据设置相同的过期时间，导致某段时间内缓存失效，请求全部走数据库。”这种情况，非常好解决：

• 解决方法：在缓存的时候给过期时间加上一个随机值，这样就会大幅度的减少缓存在同一时间过期。

对于“Redis挂掉了，请求全部走数据库”这种情况，我们可以有以下的思路：

• 事发前：实现Redis的高可用(主从架构+Sentinel 或者Redis Cluster)，尽量避免Redis挂掉这种情况发生。

• 事发中：万一Redis真的挂了，我们可以设置本地缓存(ehcache)+限流(hystrix)，尽量避免我们的数据库被干掉(起码能保证我们的服务还是能正常工作的)

• 事发后：redis持久化，重启后自动从磁盘上加载数据，快速恢复缓存数据。

缓存穿透

缓存穿透是指查询一个一定不存在的数据。由于缓存不命中，并且出于容错考虑，如果从数据库查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到数据库去查询，失去了缓存的意义。

如何解决缓存穿透？

解决缓存穿透也有两种方案：

1. 由于请求的参数是不合法的(每次都请求不存在的参数)，于是我们可以使用布隆过滤器(BloomFilter)或者压缩filter提前拦截，不合法就不让这个请求到数据库层！

2. 当我们从数据库找不到的时候，我们也将这个空对象设置到缓存里边去。下次再请求的时候，就可以从缓存里边获取了。

3. 这种情况我们一般会将空对象设置一个较短的过期时间。

缓存与数据库双写一致

如果仅仅查询的话，缓存的数据和数据库的数据是没问题的。但是，当我们要更新时候呢？各种情况很可能就造成数据库和缓存的数据不一致了。

从理论上说，只要我们设置了键的过期时间，我们就能保证缓存和数据库的数据最终是一致的。因为只要缓存数据过期了，就会被删除。随后读的时候，因为缓存里没有，就可以查数据库的数据，然后将数据库查出来的数据写入到缓存中。

除了设置过期时间，我们还需要做更多的措施来尽量避免数据库与缓存处于不一致的情况发生。

对于更新操作：

一般来说，执行更新操作时，我们会有两种选择：

• 先操作数据库，再操作缓存

• 先操作缓存，再操作数据库

操作缓存也有两种方案：

• 更新缓存

• 删除缓存

一般我们都是采取删除缓存缓存策略的，原因如下：

• 高并发环境下，无论是先操作数据库还是后操作数据库而言，如果加上更新缓存，那就更加容易导致数据库与缓存数据不一致问题。(删除缓存直接和简单很多)

• 如果每次更新了数据库，都要更新缓存【这里指的是频繁更新的场景，这会耗费一定的性能】，倒不如直接删除掉。等再次读取时，缓存里没有，那我到数据库找，在数据库找到再写到缓存里边(体现懒加载)

基于这两点，对于缓存在更新时而言，都是建议执行删除操作！

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

如果原子性被破坏了：

• 第一步成功(操作数据库)，第二步失败(删除缓存)，会导致数据库里是新数据，而缓存里是旧数据。

• 如果第一步(操作数据库)就失败了，我们可以直接返回错误(Exception)，不会出现数据不一致。

如果在高并发的场景下，出现数据库与缓存数据不一致的概率特别低，也不是没有：

• 缓存刚好失效

• 线程A查询数据库，得一个旧值

• 线程B将新值写入数据库

• 线程B删除缓存

• 线程A将查到的旧值写入缓存

要达成上述情况，还是说一句概率特别低：

因为这个条件需要发生在读缓存时缓存失效，而且并发着有一个写操作。而实际上数据库的写操作会比读操作慢得多，而且还要锁表，而读操作必需在写操作前进入数据库操作，而又要晚于写操作更新缓存，所有的这些条件都具备的概率基本并不大。

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

如果原子性被破坏了：

• 第一步成功(删除缓存)，第二步失败(更新数据库)，数据库和缓存的数据还是一致的。

• 如果第一步(删除缓存)就失败了，我们可以直接返回错误(Exception)，数据库和缓存的数据还是一致的。

看起来是很美好，但是我们在并发场景下分析一下，就知道还是有问题的了：

• 线程A删除了缓存

• 线程B查询，发现缓存已不存在

• 线程B去数据库查询得到旧值

• 线程B将旧值写入缓存

• 线程A将新值写入数据库

并发下解决数据库与缓存不一致的思路：

• 将删除缓存、修改数据库、读取缓存等的操作积压到队列里边，实现串行化。

对比两种策略

我们可以发现，两种策略各自有优缺点：

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

  • 在高并发下表现不如意，在原子性被破坏时表现优异

• 先更新数据库，再删除缓存(Cache Aside Pattern设计模式)

  • 在高并发下表现优异，在原子性被破坏时表现不如意

秒杀

阿里面试官问我：如何设计秒杀系统？我给出接近满分的回答