Redis， Codis与Mc

Memcache

工作原理

用的是LRU cache算法+超时过期机制

当查询数据时，客户端首先参考节点列表计算出key的哈希值（阶段一哈希），进而选中一个节点；客户端将请求发送给选中的节点，然后memcached节点通过一个内部的哈希算法（阶段二哈希），查找真正的数据（item）

优缺点

Mc特点：

MC 处理请求时使用多线程异步 IO 的方式，可以合理利用 CPU 多核的优势，性能非常优秀；
MC 功能简单，使用内存存储数据；
MC 的内存结构以及钙化问题我就不细说了，大家可以查看官网了解下；
MC 对缓存的数据可以设置失效期，过期后的数据会被清除；
失效的策略采用延迟失效，就是当再次使用数据时检查是否失效；
当容量存满时，会对缓存中的数据进行剔除，剔除时除了会对过期 key 进行清理，还会按 LRU 策略对数据进行剔除

限制：
key 不能超过 250 个字节；
value 不能超过 1M 字节；
key 的最大失效时间是 30 天；
只支持 K-V 结构，不提供持久化和主从同步功能

钙化问题

没有空余的内存分配新的slab的时候， 写入新的数据，会淘汰最新的，LRU只会淘汰同一级别的Slab数据

重启实例，采取随机过期策略

Reids

缓存

本地缓存(内存交互)，分布式缓存（远程请求，良好的扩展能力），多级缓存（两者结合）

基础类型

string

内部的实现是通过 SDS（Simple Dynamic String ）来存储的。SDS 类似于 Java 中的 ArrayList，可以通过预分配冗余空间的方式来减少内存的频繁分配

场景：缓存，计数器，session

动态字符串SDS

会存储长度信息，取出来的就是o1，还预分配了一个冗余长度，有多余的1byte空间（这1byte也是为了存空字

惰性空间释放：我们执行完一个字符串缩减的操作，redis并不会马上收回我们的空间，因为可以预防你继续添加的操作，这样可以减少分配空间带来的消耗，但是当你再次操作还是没用到多余空间的时候，Redis也还是会收回对于的空间，防止内存的浪费的

两次，第一次不会缩减回收多余空间，再次操作发现还没有使用，就会回收，删减的话也不会马上释放free空间

同时保存了长度还会处理二进制的数据，进行长度对比

hash

map结构，kv使用，扩容，渐进式rehash，新旧两个hash，扩大到原来的2倍，缩容是元素数量到达数组的1/10

list

List 存储一些列表型的数据结构，底层是链表结构

lrange 命令，读取某个闭区间内的元素，可以基于 List 实现分页查询

Redis的链表结构，可以轻松实现阻塞队列，数据的生产者可以通过Lpush命令从左边插入数据，多个数据消费者，可以使用BRpop命令阻塞的“抢”列表尾部的数据

set

无序集合，自动去重

sorted set

有序集合，根据分数自动排序

pub/sub 订阅发布

bitmap 布隆过滤器

pipeline 管道命令

事务

Redis 只保证串行执行命令，并且能保证全部执行，但是执行命令失败时并不会回滚，而是会继续执行下去

跳表

解决链表查找问题，链表的插入删除都是o1，但是查找是on，只能一个一个查找

将链表升维，多层链表，类似二分查找的思想，是查找时间复杂度可以降低到O(log n)

但是会对插入，删除造成影响，需要调整层级链表之间的对应关系

如何调整，不要求每层的对应关系，插入的节点产生随即层数，还是O1操作，比如随机 层数是3，则1到3层都有这个节点，不需要调整会优于平衡树

查找时会逐层查找，降低查找的时间复杂度

如何产生这个随机层数，会影响到跳表的查找效率

redis中的概率是p，1/4

第1层链表固定有n个节点；
第2层链表平均有np个节点；
第3层链表平均有np2个节点

从第1层到最高层，各层链表的平均节点数是一个指数递减的等比数列。容易推算出，而最高层的平均节点数为1/p

相比于平衡树，hash：

1、跳表，平衡树是有序的，hash是无序的，查找是O1，但是无法范围查找

2、范围查找时，平衡树比跳表复杂，平衡树需要中序遍历

3、平衡树插入删除会引起子树调整，保证平衡，跳表只需要修改指针

4、内存占用，平衡树每层两个指针，跳表每层1/（1-p）， redis是1/4，每层1.33个指针

5、查找都是ologn，实现跳表更简单

redis中的跳表

sorted set底层不仅仅使用了skiplist，还使用了ziplist和dict

sorted set中的每个元素主要表现出3个属性：

数据本身（在前面的例子中我们把名字存成了数据）。
每个数据对应一个分数(score)。
根据分数大小和数据本身的字典排序rank排名

zrevrank由数据查询它对应的排名，这在前面介绍的skiplist中并不支持。
zscore由数据查询它对应的分数，这也不是skiplist所支持的。
zrevrange根据一个排名范围，查询排名在这个范围内的数据。这在前面介绍的skiplist中也不支持。
zrevrangebyscore根据分数区间查询数据集合，是一个skiplist所支持的典型的范围查找（score相当于key）。

zscore的查询，不是由skiplist来提供的，而是由那个dict来提供的。 时间复杂度o1
为了支持排名(rank)，Redis里对skiplist做了扩展，使得根据排名能够快速查到数据，或者根据分数查到数据之后，也同时很容易获得排名。而且，根据排名的查找，时间复杂度也为O(log n)。
zrevrange的查询，是根据排名查数据，由扩展后的skiplist来提供。O(log(n)+M)
zrevrank是先在dict中由数据查到分数，再拿分数到skiplist中去查找，查到后也同时获得了排名。O(log n)

分数(score)允许重复，即skiplist的key允许重复。这在最开始介绍的经典skiplist中是不允许的。
在比较时，不仅比较分数（相当于skiplist的key），还比较数据本身。在Redis的skiplist实现中，数据本身的内容唯一标识这份数据，而不是由key来唯一标识。另外，当多个元素分数相同的时候，还需要根据数据内容来进字典排序。
第1层链表不是一个单向链表，而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。

当数据较少时，sorted set是由一个ziplist来实现的。超过128个就会转skiplist，或者单独插入长度超过了64
当数据多的时候，sorted set是由一个dict + 一个skiplist来实现的。简单来讲，dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）

ziplist双向链表

相关问题

大量的key同一时间过期

大量的key过期时间设置的过于集中，到过期的那个时间点，Redis可能会出现短暂的卡顿现象。严重的话会出现缓存雪崩

过期时间加上随机值

redis分布式锁

先拿setnx来争抢锁，抢到之后，再用expire给锁加一个过期时间防止锁忘记了释放

如果set后，设置expire之前意外crash，setnx和expire合成一条指令来用

查找指定前缀的key

keys指令可以扫出指定模式的key列表，如果这个redis正在给线上的业务提供服务，那使用keys指令会有什么问题？

Redis的单线程的。keys指令会导致线程阻塞一段时间，线上服务会停顿，直到指令执行完毕，服务才能恢复。这个时候可以使用scan指令，scan指令可以无阻塞的提取出指定模式的key列表，但是会有一定的重复概率，在客户端做一次去重就可以了，但是整体所花费的时间会比直接用keys指令长

增量式的，但是期间被更改，不能完全保证

redis做异步队列

rpush生产消息，lpop消费消息。当lpop没有消息的时候，要适当sleep一会再重试

list还有个指令叫blpop，在没有消息的时候，它会阻塞住直到消息到来

使用pub/sub主题订阅者模式，可以实现 1:N 的消息队列，但有缺点在消费者下线的情况下，生产的消息会丢失，得使用专业的消息队列如RocketMQ等

实现延时队列：使用sortedset，拿时间戳作为score，消息内容作为key调用zadd来生产消息，消费者用zrangebyscore指令获取N秒之前的数据轮询进行处理

redis持久化，主从数据交互

RDB：RDB 持久化机制，是对 Redis 中的数据执行周期性的持久化。
AOF：AOF 机制对每条写入命令作为日志，以 append-only 的模式写入一个日志文件中，因为这个模式是只追加的方式，所以没有任何磁盘寻址的开销，所以很快，有点像Mysql中的binlog。

RDB做镜像全量持久化，AOF做增量持久化。因为RDB会耗费较长时间，不够实时，在停机的时候会导致大量丢失数据，所以需要AOF来配合使用。在redis实例重启时，会使用RDB持久化文件重新构建内存，再使用AOF重放近期的操作指令来实现完整恢复重启之前的状态

AOF持久化开启且存在AOF文件时，优先加载AOF文件；AOF关闭或者AOF文件不存在时，加载RDB文件；加载AOF/RDB文件城后，Redis启动成功

RDB更适合做冷备，AOF更适合做热备

两种方式的优缺点：

1、RDB对Redis的性能影响非常小，是因为在同步数据的时候他只是fork了一个子进程去做持久化的，而且他在数据恢复的时候速度比AOF来的快

2、RDB都是快照文件，都是默认五分钟甚至更久的时间才会生成一次，这意味着你这次同步到下次同步这中间五分钟的数据都很可能全部丢失掉。AOF则最多丢一秒，数据完整性不一样

3、RDB在生成数据快照的时候，如果文件很大，客户端可能会暂停几毫秒甚至几秒

4、AOF是一秒一次去通过一个后台的线程fsync操作，那最多丢这一秒的数据，写入的方式是追加，减少磁盘开销

5、AOF开启后，Redis支持写的QPS会比RDB支持写的要低

第一时间用RDB恢复，然后AOF做数据补全

RDB快照的数据生成的时候，缓存区也必须同时开始接受新请求，不然你旧的数据过去了，你在同步期间的增量数据咋办

aof重写：原理 就是 开辟一个子进程 对内存进行 遍历 转换成一系列 Redis 的操作指令，序列化到一个新的 AOF 日志文件 中。序列化完毕后再将操作期间发生的 增量 AOF 日志 追加到这个新的 AOF 日志文件中

Pipelibne

可以将多次IO往返的时间缩减为一次，前提是pipeline执行的指令之间没有因果相关性

redis同步机制

第一次同步时，主节点做一次bgsave，并同时将后续修改操作记录到内存buffer，待完成后将RDB文件全量同步到复制节点，复制节点接受完成后将RDB镜像加载到内存。加载完成后，再通知主节点将期间修改的操作记录同步到复制节点进行重放就完成了同步过程。后续的增量数据通过AOF日志同步即可

传输过程中有什么网络问题啥的，会自动重连的，并且连接之后会把缺少的数据补上的

为啥redis快

Redis采用的是基于内存的采用的是单进程单线程模型的 KV 数据库，由C语言编写，官方提供的数据是可以达到100000+的QPS

1、完全基于内存，绝大部分请求是纯粹的内存操作，非常快速

2、数据结构简单，数据操作简单

3、采用了单线程，避免了上下文切换，和竞争，也不存在多线程多进程的cpu消耗

4、多路io复用模型，非阻塞io

5、底层实现，Redis直接自己构建了VM 机制 ，因为一般的系统调用系统函数的话，会浪费一定的时间去移动和请求

单线程多核

开多个实例

哨兵集群sentinel监控

集群监控：负责监控 Redis master 和 slave 进程是否正常工作。
消息通知：如果某个 Redis 实例有故障，那么哨兵负责发送消息作为报警通知给管理员。
故障转移：如果 master node 挂掉了，会自动转移到 slave node 上。
配置中心：如果故障转移发生了，通知 client 客户端新的 master 地址

过期策略

Redis的过期策略，是有定期删除+惰性删除两种

从设置过期时间的key里随机选取 检查，达到过期时间的就删除，全扫描量太大

惰性删除：定期没删的，查询的时候来检查是否过期

既没定期删，也没访问，lru解决

缓存击穿，穿透，雪崩

击穿：热点数据不过期设置

穿透：加校验，布隆过滤器反向校验

雪崩：重启，过期随机时间

主从之间数据同步

单机QPS是有上限的，而且Redis的特性就是必须支撑读高并发的，master机器去写，数据同步给别的slave机器

redis线程模型

文件事件处理器是单线程的，采用 IO 多路复用机制同时监听多个 Socket，根据 Socket 上的事件来选择对应的事件处理器进行处理

多个socket，io多路复用，文件事件分派器，文件处理器

多个 Socket 可能会并发产生不同的操作，每个操作对应不同的文件事件，但是 IO 多路复用程序会监听多个 Socket，会将 Socket 产生的事件放入队列中排队，事件分派器每次从队列中取出一个事件，把该事件交给对应的事件处理器进行处理

redis慢的原因

1、实例内存达到上限：max值，达到max值会踢出一些数据，内存维持在max下，lru淘汰，扩充内存

2、大key问题，操作大key，就会消耗比较多的时间与内存，业务分解

3、复杂的操作：CONFIG SET slowlog-log-slower-than 5000，On操作，N比较大，或者组装数据，网络问题

4、集中过期：redis定时任务检查主动过期时，大量的key都过期

5、fork子进程，持久化，拷贝数据量大，在这个时间段内操作就会耗时比较严重

6、申请内存大页，内存页4kb，linux2.6。38支持2mb内存申请，Redis 在申请内存时也会以 2MB 为单位向操作系统申请，申请内存的耗时变长，进而导致每个写请求的延迟增加，影响到 Redis 性能

7、AOF阻塞：刷磁盘的时候，磁盘负载过高，导致子进程阻塞，不能返回，再次aofwrite的时候就会影响redis性能

Codis

Codis就是起着一个中间代理的作用，能够把所有的Redis实例当成一个来使用，在客户端操作着SDK的时候和操作Redis的时候是一样的，没有差别。

因为Codis是一个无状态的，所以可以增加多个Codis来提升QPS,同时也可以起着容灾的作用。

codis分片

Codis会把所有的key分成1024个槽，这1024个槽对应着的就是Redis的集群，这个在Codis中是会在内存中维护着这1024个槽与Redis实例的映射关系

槽位同步

ZooKeeper监听槽位变化，会及时同步

codis扩容

在迁移的时候，会在原来的Redis节点和新的Redis里都保存着迁移的槽位信息，在迁移的过程中，如果有key打进将要迁移或者正在迁移的旧槽位的时候，这个时候Codis的处理机制是，先是将这个key强制迁移到新的Redis节点中，然后再告诉Codis,下次如果有新的key的打在这个槽位中的话，那么转发到新的节点。

最后自动均衡

codis不支持事务，不支持MSETNX

因为key可能存在在多个Redis的实例中，如果某个实例的设值成功，而另一个实例的设值不成功，从本质上讲这是不成功的，但是分布在多个实例中的Redis是没有回滚机制的，所以会产生脏数据