# Redis
# 1.Redis是什么？
答案
Redis是基于内存的数据库，读写操作都在内存中完成,因此读写速度特别快。常用于缓存，消息队列
# 2.Redis和MemCached的区别
答案
1.Redis支持的数据类型跟丰富，如Hash,List,Set,ZSet等，而MemCached只支持字符串
2.Redis支持数据的持久化，可以将内存中的数据存储在磁盘中，重启的时候可以再次加载使用，而MemCached不支持持久化，数据全部存储在内存中，一旦重启或挂掉后，数据就丢失了。
3.Redis支持原生的集群模式，MemCached没有原生的集群模式，需要依靠客户端来实现往集群中分片写入数据
4.Redis支持订阅，Lua脚本，事务等功能，而MemCached不支持
# 3.Redis常用数据类型及其应用场景
答案
1.String 用于缓存对象，计数器，分布式锁，共享Session
2.List 用于消息队列(但是需要自己实现全局唯一ID,不能以消费组的形式消费数据)
3.Set 用于共同好友，点赞等场景
4.ZSet 用于排行榜
5.BitMap 常用于签到，用户登陆状态判断
6.HyperLogLog 常用于大量数据的基数统计，例如网页浏览量统计
7.GEO 用于地理位置信息存储，例如滴滴叫车，附近的人
8.Stream 用于消息队列，支持消费组和自动生成全局唯一ID
9.hash 用于缓存对象，缓存购物车
# 4.Redis是单线程的吗?
答案
我们常说的Redis是单线程的是指接收客户端请求，解析请求，进行数据读写操作，发送数据给客户端这个过程是由一个线程完成。但Redis并不是单线程的，它还为关闭文件，AOF刷盘，释放内存任务创建了后台线程
# 5.Redis6.0之前为什么使用单线程
答案
单线程是无法利用多核CPU的，但是Redis仍然采用单线程模型，因为Redis是基于内存的，读写速度很快，所以性能瓶颈不在CPU，而在于内存和网络IO，并且使用单线程可以提高可维护性，多线程模型虽然在某些方面表现优秀，但是也导致了一些并发读写带来的问题，增加了系统的复杂度。
# 6.为什么Redis6.0后引入了多线程
答案
因为随着网络硬件的提升，Redis的性能瓶颈有时会出现在网络IO处理上，所以使用了多个IO线程来处理网络请求，但是对于命令的执行，仍然采用单线程来处理
# 7.AOF日志的原理
答案
先执行写操作，再将日志写入AOF缓冲区（因为这样可以避免额外的检查开销，还不会阻塞当前的写操作），通过系统调用write时再写入内核缓冲区，刷盘时机由系统参数决定
# 8.AOF日志重写的原理
答案
当AOF日志过大时，会触发AOF重写，Redis会开启一个子进程, 读取数据库中的所有键值对，然后每一个键值对用一条命令记录到新的AOF文件(AOF重写期间，主进程可以继续处理命令请求，主进程产生的AOF日志先写入AOF缓冲区，再写入AOF重写缓冲区)，完成重写工作后，会向主进程发送一条命令，然后主进程会将AOF重写缓冲区的所有内容追加到新的AOF文件中，然后将新的AOF文件改名，覆盖旧的AOF文件
# 9.为什么AOF日志重写要用子进程而不是线程
答案
因为如果使用线程，多线程之间会共享内存，修改共享内存数据时需要加锁，从而会降低性能。而使用子进程，父子进程共享数据，当内存发生修改时，会发生写时复制，而不需要加锁
# 10.RDB快照原理
答案
Redis生成RDB快照有两种方式
一种是save，在主线程生成RDB文件，如果生成RDB文件时间过长就会阻塞主线程
一种是bgsave，会创建一个子进程来生成RDB文件，可以避免阻塞主线程。Redis的RDB快照是全量快照，每次执行快照会把内存中的所有数据都记录到磁盘中，所以频率不能太频繁
# 11.混合持久化
答案
开启混合持久化后，AOF重写时，子进程会将共享的AOF日志以RDB的形式写入到新的AOF文件中，重写完成后通知主进程，主进程将AOF重写缓冲区以AOF的形式追加到新的AOF文件，然后将新的AOF文件改名，覆盖旧的AOF文件
# 12.AOF，RDB，混合持久化优缺点
答案
AOF的文件体积更大，性能较差，恢复速度较慢，但是AOF丢失的数据更少
RDB的文件体积更小，性能较高，恢复速度较快，但是RDB丢失的数据更多
混合持久化有RDB的优点恢复速度快，也有AOF的优点丢失的数据少，同时也有其缺点，可读性更差，兼容性更差
# 13.Redis主从复制原理
答案
一开始，从节点向主节点建立连接，然后主节点生成RDB快照，将其发送给从节点，从节点清空自己的数据，然后载入RDB快照，在生成RDB快照的过程中，不会阻塞的主进程，期间的写操作命令记录在replication buffer内(如果replication buff 满了会删除缓存，重新和从节点建立连接)。在从节点加载RDB快照完成后，主节点将replication buffer中的数据发送给从节点
当从节点掉线重连后，主节点会采用增量复制的方式发送数据，首先会检查要发送的数据是否存在repl_backlog_buffer（在发送给从节点之前会先将命令写入这里）中，如果在则进行增量复制，否则进行全量复制
# 14.Redis哨兵模式原理
答案
哨兵一开始会监控主节点的状态，如果Ping不通主节点，则判定为主观下线，然后向其他哨兵发送命令，其他哨兵节点根据自身与主节点的网络状态，投出赞成或反对，如果赞成票数达到quorum值，则判定主节点为客观下线。然后通知其他哨兵，希望成为leader来进行主从切换，每个哨兵只有一次投票机会，如果得到半数以上的赞成票并且大于等于quorum值，则当选leader。
开始主从切换，在从节点中选出一个节点将其转化为主节点（选取规则：先过滤掉网络不好的，然后优先级，复制下标，节点ID排序），然后通知其他从节点更换复制目标，将新主节点的信息发送给客户端，继续监视旧主节点，当他上线后设置为新节点的从节点。
# 15.Redis集群原理
答案
Redis集群将所有数据自动分成16384个哈希槽，将数据分散在不同的节点上。节点之间基于Gossip协议进行通信，通过主从复制和故障转移保证高可用
# 16.Redis过期删除策略
答案
Redis的过期删除策略由惰性删除和定期删除组成
惰性删除是指当访问到某个key时，判断是否过期，如果过期了就将其删除，否则不做处理。
定期删除是指每隔一段随机抽取20个key，将过期的key删除，如果定期删除执行时间超过了25ms，那么直接结束，否则判断过期key是否超过25%，超过则继续抽取
# 17.Redis内存淘汰策略
答案
1.随机淘汰设置了过期时间的key
2.优先淘汰更早过期的key
3.淘汰设置了过期时间中的，最久未使用的key
4.淘汰设置了过期时间中的，最少使用的key
5,随机淘汰key
6.淘汰最久未使用的key
7.淘汰最少使用的key
# 18.Redis的LRU和LFU
答案
Redis的LRU算法和传统的LRU算法不同，Redis通过添加最后访问时间的字段，然后需要淘汰数据时，通过随机采样，然后淘汰最久没用使用的那个
Redis的LFU算法记录和该key上次访问的时间戳和访问频次，每次访问时，首先会根据当前与上次访问时间的距离对访问频次进行衰减，然后按照一定概率增加访问频次的值。当需要淘汰数据时，随机抽取一些key，然后删除掉访问频次最低的key
# 19.缓存雪崩、缓存击穿、缓存穿透
答案
缓存雪崩是指大量缓存在同一时间过期，此时大量的请求直接访问数据库，从而导致数据库宕机。避免的方法是随机生成过期时间或者设置为不过期
缓存击穿是指热点数据过期，此时有大量的请求访问该热点数据，从而导致大量请求直接访问数据库，导致数据库宕机。避免的方法是将热点数据设置为不过期，由后台异步更新缓存或者在热点数据快过期时，提前通知后台线程更新缓存以及重新设置过期时间。或者在加互斥锁，保证同一时间只有一个线程请求缓存，其他线程等待或返回空值
缓存穿透是指大量请求即不在缓存又不在数据库中的数据，从而使得数据库宕机。避免的办法是对于在数据库中没查到的数据回种空值或默认值。或者使用布隆过滤器快速判断数据是否存在，来减少对数据库的查询。
# 20.常见的缓存更新策略
答案
1.旁路缓存。在更新数据时，先修改数据库，再删除缓存。在查询数据时，先查询缓存，再查询数据库，再将数据写回缓存
2.写穿/读穿。在更新数据时，如果存在缓存，则修改缓存，由缓存组件将数据同步更新到数据库，否则直接修改数据库。在查询数据时，如果存在缓存则直接返回，否则由缓存组件从数据库查询数据，并写入缓存，然后返回
3.写回。在更新数据时，只更新缓存，同时将缓存数据设置为脏，然后返回。异步的将缓存中的数据更新到数据库
# 21.Redis 的大 key 如何处理
答案
1.分批次删除，对于一个大key，每次只删除key对应的部分数据
2.异步删除，使用unlink命令异步删除
# 22.如何用 Redis 实现分布式锁的？
答案
通过Redis的SetNX实现，如果不存在则插入成功，如果存在，则插入失败，很适合分布式锁的加锁和解锁
# 23.惰性删除和定期删除的优缺点
答案
惰性删除不会占用太多的系统资源对CPU友好，但是会导致过期key长期占用内存得不到释放，造成一定的空间浪费。
定期删除的优点是能够减少对系统资源的占用的同时还能够减少对内存空间的无效占用,但是效果不如定时删除好
# 24.Redis实现的分布式锁，如果获取到锁的线程挂了，一直占用该锁怎么办?
答案
给锁设置超时时间即可
# 25.Redis分布式锁容灾问题，如果一个Redis挂了会不会重复拿到这个锁
答案
存在这种可能，如果采用的是主从或者哨兵模式的话，在主节点申请到锁后，主节点挂了，加锁信息还没来得及同步到从节点，是可以重复加锁的
# 26.Redis如何解决集群情况下分布式锁的可靠性？
答案
使用Redlock，客户端向多个独立的Redis加锁，如果能够和半数以上的节点成功的完成操作，则认为加锁成功
# 27.主从模式下，如何处理过期键
答案
从节点不会让key过期，主节点发现key过期后，会发送删除命令给从节点
# 28.为什么Redis集群采用哈希槽而不是一致性哈希
答案
1.一致性哈希增删节点时，会导致部分数据无法命中，并且导致下一个节点的压力增大，造成缓存雪崩
2.哈希槽的数据分布比一致性哈希更加均匀
3.哈希槽增删节点更加便捷，只需要将原有的数据移动到其他节点即可
# 29.为什么Redis的哈希槽是16384个？
答案
因为如何有更多的槽位会导致心跳包更大，浪费带宽。主节点的配置信息的哈希槽是通过bitmap记录的，如果哈希槽越少，压缩率更高
# 30.Redis常见数据结构的实现
答案
1.String redis的字符串是通过int和sds实现的，sds不仅可以保存文本数据，还可以保存二进制数据。并且获取字符串长度的复杂度是O（1），因为sds存储了字符串的长度，并且sds是安全的，拼接字符串不会造成缓冲区溢出
2.List 因为压缩列表是连续存储的，发生修改时，导致联动更新，而双向链表的空间开销太大。所以将二者相结合 redis的list通过quicklist实现，quick本质上是个双向链表，里面存储的是压缩列表，结合了压缩列表和双向链表的优点，有效节省存储空间的同时有较高的效率。
3.hash redis的hash在元素个数少于512并且所有值小于64字节时，基于listpack实现，listpack沿用了ziplist的紧凑布局，通过不存在上一个元素的长度避免了连锁更新的问题，通过encoding记录了元素的数据类型和长度，通过element-tot-len记录encoding和data的长度，从而支持方向遍历，否则会采用哈希表，哈希表底层存储了两个字典，一个用于扩容,会在必要的时候进行扩容和缩容，rehash
4.set redis的set，在元素类型都是int并且元素个数不超过512的时候，会采用整数集合，整数集合的底层是一个有序数组。否则采用哈希表
5.zset zset在元素个数小于128并且每个元素的值都小于64字节时，采用listpack，否则采用跳表。跳表是一个有序数据结构，它通过在每个节点维护多个指向其他节点指针，从而达到快速访问节点的目的
# 31.Redis 采用单线程为什么还这么快？
答案
1.Redis的大部分操作都在内存中完成，并且采用了高效的数据结构，因此 Redis 瓶颈可能是机器的内存或者网络带宽，而并非 CPU，既然 CPU 不是瓶颈，那么自然就采用单线程的解决方案了。
2.Redis 采用单线程模型可以避免了多线程之间的竞争，省去了多线程切换带来的时间和性能上的开销，而且也不会导致死锁问题。
3.Redis 采用了 I/O 多路复用机制处理大量的客户端 Socket 请求
# 32.Redis分布式锁，过期时间不够怎么办?
答案
可以使用看门狗机制，监控锁的过期时间，定期给锁续期
# 33.redis惊群效应
答案
在高并发场景下，某个缓存过期，然后大量请求打到数据库，导致数据库压力突增，然后另一段时间又有大量的缓存失效
通过加分布式锁,限流，本地缓存来解决
# 34.redis的哈希表的底层原理
答案
哈希表包括了两个哈希桶数组，一个用于存储普通数据，一个用于存储扩容时的数据。是数组+链表的结构，当发生哈希冲突时，会在链表后追加元素。当哈希冲突过于频繁，会进行扩容。
扩容条件为：
1.负载因子(实际的元素数量/哈希桶的数量)>1并且没在进行AOF日志重写或RDB快照生成(AOF日志重写和RDB快照生成都是由子进程完成的， ，如果进行扩容会增加不必要的内存写入操作)
2.负载因子>5
缩容条件为：负载因子<0.1
当插入操作时会判断是否满足扩容条件，如果满足则开始扩容。当删除操作时会判断是否满足缩容条件，如果满足则开始缩容。扩容和缩容都是一个渐进式的过程，每次进行操作时，都会移动一个哈希桶到另一个数组
# 35.AOF日志缓冲区刷盘策略
答案
1.Always 每次执行写操作后都将AOF日志刷盘
2.Everysec 每次执行写操作后都将AOF日志写入内核缓冲区，然后每秒刷盘
3.No 每次执行写操作后都将AOF日志写入内核缓冲区，具体刷盘时机由操作系统决定
# 36.布隆过滤器如何实现删除操作
答案
1.通过计数布隆过滤器实现，但是占用的空间会大很多
2.布谷鸟过滤器
布谷鸟过滤器的底层是哈希桶数组，每个元素记录的是key对应的指纹。
插入：首先计算出当前key对应的hash，如果已经存在，则将当前位置的key(这里的key实际存储的是key对应的指纹)剔除，然后计算出当前key的hash值与当前的下标进行异或，如果存在，则将当前位置的key进行剔除，直到达到最大剔除次数或没有冲突，则插入
查找：首先计算出当前key对应的hash1(对应首选桶的下标)，和hash1和key对应的指纹的哈希值的异或值hash2(对应候选桶的下标)，如果hash1或hash2存在对应的指纹，则直接返回true，否则返回false(如果发生桶溢出则会导致假阴性)
删除：首先计算出当前key对应的hash1(对应首选桶的下标)和和hash1和key对应的指纹的哈希值的异或值hash2(对应候选桶的下标)，如果hash1或hash2存在对应的指纹，则删除掉一个(因此不能重复删除，必须保证删除的key是存在的key)
优点：
1.基于布谷鸟过滤器的布谷鸟过滤器，更加紧凑，因此可以更加节省空间
2.布隆过滤器在查询时需要多次哈希，而布谷鸟过滤器只需要一次哈希，因此效率更高
3.布谷鸟过滤器支持删除，而布隆过滤器不支持删除
缺点：
1.布隆过滤器采用的是备用桶的方案，首选桶和候选桶可以通过相互异或得出，因此桶的大小必须是2的指数倍
2.布谷鸟不能重复插入元素，因为重复插入会将原有元素剔除，然后导致首选桶和候选桶被占满，因此一个元素最多被插入2b
3.频繁的剔除元素可能导致哈希冲突加剧，从而导致性能下降
4.如果在元素没有被插入的时候删除，会导致误删除
# 37.redis跳表的底层实现
答案
跳表本质上是一个多层链表，平均复杂度为log(n)
插入操作：每个插入前会随机生成一个层数，如果超过当前跳表的层数则需要扩大跳表的层数，然后从最高层开始，找到第一个大于等于目标值的节点，插入在它的前面，直到所有层都添加完毕
查询操作：从最高层开始，当目标值大于当前节点的后一个节点的值时，继续往后走，当目标值小于当前节点的后一个节点的值，大于当前节点的值时，往下移动一层，直到目标值等于当前节点值，搜索结束
删除操作：从最高层开始，先进行搜索操作，找到目标值后，将当前节点及其下层节点删除
# 38.跳表的无锁实现
# 39.ZSet的原理和底层实现
答案
简单剖析下zset的原理，大抵上就是skiplist是由两个元素构成的，哈希表和跳表。哈希表主要是用来 保证元素的唯一性，去重，并且能够通过元素寻找对应的score值，而跳表主要是用来给元素value 进行排序并且通过score的范围来获取元素列表(就是找到最小符合的进行遍历得到的一连串)。
实现原理:跳表在创建节点的时候会生成一个0-1的随机数，如果随机数小于0.25那层数就增加1，一 直进行这个操作直到随机数大于0.25。因此这样会有个疑问。如果想要平均时间复杂度log(n)，为什么这个因 子不是0.5呢？原因是因为要为了节约一半内存而牺牲一小部分性能来做权衡。而跳表节点中存在 有元素，元素的权重值，后向指针，level数组，level数组内有前向指针和跨度，后向指针是为了 能倒序遍历，跨度的话是为了计算排位，因为你如果只是一直遍历的话没有其他的元素告诉你到底 离开始遍历时的节点有多远。而查询时跳表会先从最高层开始遍历(我猜测时因为高层节点少，跨度 大，能更快遍历到)，遍历时候会对权重和元素进行判断，如果当前节点的权重比较小，会访问该层 的下一个节点，如果权重相等的话会按元素的值来判断，如果当前节点的值比较小，就会访问下一 个节点，如果两个都不满足或者下一个节点是空，跳表就会把高度下降一层。
# 40.ZSet用跳表不用平衡树的原因
答案
从内存占用上看，跳表更灵活。平衡树每个节点包含两个指针指向左右子树，但是跳表的指针数 平均为1/(1-p),取决p大小。
做范围遍历更简单，平衡树找到指定范围的小值还要用中序遍历去寻找其他不大于大值的值。而 跳表找到小值对第一层链表进行遍历判断即可。
平衡树实现逻辑复杂，而跳表实现逻辑简单，操作快速。
# 41.Redis GEO底层实现
答案
要实现附近的人功能，本质上就是对于坐标(x,y)需要找到附近的点对。对于二维点对很难找到相邻点对，因此要将二维映射到一维。
我们通过 GEO HASH算法。对坐标的范围进行二分。假设l <= x <= r， 那么用二进制的0表示x位于[l,mid]之间，1表示x位于[mid,r]之间，然后将l,r的区间不断缩小，从而使得坐标更加精确，因此可以将坐标通过logn的复杂度得到若干个比特位，然后将x,y坐标的比特位交替放置。然后按其值排序，当需要查找附近的人时，计算出自己的比特值然后通过二分找到自己附近的值。
本质上 GEO HASH 就是将坐标映射到了多个区域，然后每次找到自己的区域后，查找附近的几个区域进行比较即可。
# 42.Redis HyperLogLog底层实现
答案
hyperloglog是算法原理是通过对key计算哈希值，然后转换为二进制64位，取出后14位作为桶的编号，然后剩余50位，找到第一次出现1的位置，范围是0~49，因此通过6个比特位就可以存下。每次写入时，更新桶对于的最大的1出现的位置。在查询时每次读取所有的桶的比特位，然后对所有的桶取调和级数并乘上一个系数即可
核心原理是基于伯努利实现，在实验次数足够多的条件下，可以近似估计结果。例如抛硬币，正面和反面概率是0.5，1表示正面，0表示反面，假设进行了N轮实验，最多maxv次才出现正面，则他最少进行了2^maxv次实现，maxv即1出现的位置。然后为了减少误差使用了调和级数和分桶,通过hash保证10分布均匀。