Redis

Redis数据类型、三种模式、淘汰策略

5种数据类型

Redis 在互联网产品中使用的场景实在是太多太多，这里分别对 Redis 几种数据类型做了整理：
1）String：缓存、限流、分布式锁、计数器、分布式 Session 等。
2）Hash：用户信息、用户主页访问量、组合查询等。
3）List：简单队列、关注列表时间轴。
4）Set：赞、踩、标签等。
5）有序集合 ZSet：排行榜、好友关系链表。
zset 是 Redis 中一个非常重要的数据结构，其底层是基于跳表（skip list） 实现的。


跳表是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为 O(logN)。简单说来跳表也是链表的一种，只不过它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，跳表能够提供 O(logN) 的时间复杂度。
跳表为了避免每次插入或删除带来的额外操作，不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数（level)。而且新插入一个节点不会影响其它节点的层数。因此，插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。

zset为何不使用红黑树等平衡树？

1）跳跃表范围查询比平衡树操作简单。 因为平衡树在查询到最小值的时还需要采用中序遍历去查询最大值。 而跳表只需要在找到最小值后，对第一层的链表遍历即可。
2）平衡树的删除和插入需要对子树进行相应的调整，而跳表只需要修改相邻的节点即可。
3）跳表和平衡树的查询操作都是O（logN）的时间复杂度。
4）从整体上来看，跳表算法实现的难度要低于平衡树。

Redis主从复制

1.全量复制

发生节点: 在slave 从服务器初始化阶段，需要将master主服务器上的所有数据都复制一份，流程如下：

• 从服务器连接主服务器，并发送sycn命令
• 主服务器接收到sycn命令后，执行bgsave命令生成RDB文件，并且在缓冲区中记录之后所有的操作记录
• master执行完bgsave后，master将RDB文件发送给slave，并在此阶段内继续在缓冲区内写操作
• slave在接收到RDB文件前 ，会将自身的数据全部丢弃，载入RDB
• master发送完毕，会向slave 的缓冲区发 写入执行命令
• slave 完成对RDB的载入，开始接受命令请求，并执行缓冲区的命令

2.增量复制

其中有三个重要参数：

• 主服务器的偏移量和从服务器的复制偏移量（offset）
• 主服务器的复制积压缓冲区
• 服务器的运行ID（runID）

复制偏移量

主节点和从节点分别维护一个复制偏移量（offset），代表的是主节点向从节点传递的字节数
offset用于判断主从节点的数据库状态是否一致：如果二者offset相同，则一致；如果offset不同，则不一致，此时可以根据两个offset找出从节点缺少的那部分数据。
例如，如果主节点的offset是1000，而从节点的offset是500，那么部分复制就需要将offset为501-1000的数据传递给从节点。而offset为501-1000的数据存储的位置，就是下面要介绍的复制积压缓冲区。

复制积压缓冲区

复制积压缓冲区是由主节点维护的、固定长度的、先进先出(FIFO)队列，默认大小1MB；当主节点开始有从节点时创建，其作用是备份主节点最近发送给从节点的数据。注意，无论主节点有一个还是多个从节点，都只需要一个复制积压缓冲区。
在命令传播阶段，主节点除了将写命令发送给从节点，还会发送一份给复制积压缓冲区，作为写命令的备份；除了存储写命令，复制积压缓冲区中还存储了其中的每个字节对应的复制偏移量（offset）。由于复制积压缓冲区定长且是先进先出，所以它保存的是主节点最近执行的写命令；时间较早的写命令会被挤出缓冲区。

从节点将offset发送给主节点后，主节点根据offset和缓冲区大小决定能否执行部分复制：

• 如果offset偏移量之后的数据，仍然都在复制积压缓冲区里，则执行部分复制；
• 如果offset偏移量之后的数据已不在复制积压缓冲区中（数据已被挤出），则执行全量复制。

哨兵模式

哨兵模式下主观下线/客观下线

• 在默认情况下，Sentinel会以每秒一次的频率向所有与他创建了连接的实例（包括主服务器、从服务器、其他Sentinel）发送PING命令，通过PING的返回值判断实例是否在线

• 回复+PONG、-LOADING、-MASTERDOWN、则有效

• 除以上三个之外的回复或者规定时间内down-after-milliseconds时间内没有回复则主观下线

• 当判断主观下线后，会对其他Sentinel进行询问，当一半以上觉得主观下线的话，视为客观下线

  选出新的主服务器

• 先判断slave节点与master节点断开的时长，如果超过指定（down-after-milliseconds * 10）则会排除该节点

• 判断slave节点的slave-priority,数字越小优先级越高，0则是用不参加选举

• 如果有多个相同最高优先级的，则选出其中偏移量offset最大的从服务器

• 最后判断运行ID，选出ID最小的服务器

  故障转移

• 选中以后，sentinel会给备选的slave发送slaveof no one，让该节点变为master

• 广播其他从节点，发送slaveof 新的ip 新的端口号给其他的从节点，让这些slave成为新的master的从节点，开始从新的master上同步数据

• sentinel将故障节点标记为slave，当故障节点恢复后会自动成为新的master的slave（直接修改配置文件为slaveof 新的ip 新的端口号）

集群模式

哈希槽

Redis集群通过分片的方式保存键值对：集群被分为16384个槽（slot），数据库中每个键都属于其中的一个。每个槽都必须有节点在处理。

• 数据key不与节点绑定，而是与插槽绑定。
• key中包含{}且至少有一个字符，则{}中为有效部分
• 不包含{}则 key 都是有效部分
  • key是{itcast}num，根据itcast计算，计算方式是CRC16算法得到一个hash值，然后%16384得到最后slot

删除机制

惰性删除

在读写key时才判断是否过期，如果过期就删除掉，属于将删除环节后置了，这样避免了轮询但是要增加了内存的占用。极端情况下如果某些体积非常大的key一直没有被访问，那么将占用内存很久，无疑在内存紧张的情况下对性能产生影响

定期删除

在主节点执行ServerCron任务定时扫描需要被删掉的key，节约了空间，但是使用了轮询消耗一定的CPU，因此在需要被删除键很多且CPU资源不富裕的情况下，对Redis服务的性能会产生影响。

定时删除

在设置键的过期时间的同时，创建一个定时器（timer），让定时器在键的过期时间来临时，立即执行对键的删除操作。不现实。浪费cpu

在实际中Redis将惰性删除作为默认开启，定期删除可以通过配置来进行设定删除频率和内存阈值触发等，算是个折中的选择

• **单线程删除阻塞问题**

Redis作为一个单线程模型的服务，当执行一些耗时的命令时，比如使用DEL删除一个value特别大的key时，或使用FLUSHDB 和 FLUSHALL 进行清库操作，都会造成redis阻塞，从而降低性能甚至发生故障转移

• **异步删除命令**

UNLINK是DEL的异步删除版本，UNLINK命令与DEL阻塞删除不同，UNLINK在删除集合类键时，如果集合键的元素个数大于64个，会把真正的内存释放操作，给单独的BackgroundIO线程来操作，有实验表明使用UNLINK命令删除一个大键mylist, 它包含200万个元素，但用时只有数毫秒。

通过对FLUSHALL/FLUSHDB添加ASYNC异步清理选项，redis在清理整个实例或DB时，操作也都是异步的，有实验数据表明异步清理200w数据耗时也只有数毫秒。

综上可知，采用UNLINK、FLUSHALL、FLUSHDB代替之前的阻塞删除命令可以使处理相同数据的耗时从传统秒级、甚至分钟级降低到目前的微妙，毫秒级，确实是个巨大的飞跃，或许这也是Redis直接从3.x飞跃到4.0的原因。

布隆过滤器

假如现在有三个哈希函数分别为**h1,h2,h3,**同时有三个输入x,y,z。三个输入分别通过h1-h3进行哈希计算出对应整数之后，对bitarray的长度进行取模运算，获取对应下标再进行置1，这样运算三次就形成了如图的bitmap结构：

布隆过滤器检索时，使用相同的哈希函数进行计算出对应的bit位置，只要看这些位置的值，如果这些位置有任何一个0，则被检元素一定不在；如果都是1，则被检元素可能存在。

一句话概率就是有0一定不存在、全1不一定存在。
不支持删除值，可以通过业务逻辑排除

误算率是其中之一，随着存入的元素数量增加，误算率随之增加，但是如果元素数量太少，则使用散列表足够。另外一般情况下不能从布隆过滤器中删除元素。

Redis淘汰策略

Redis为什么采用跳表而不是红黑树

在做范围查找的时候，平衡树比skiplist操作要复杂。
在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。
如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用上来说，skiplist比平衡树更灵活一些。

一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
从算法实现难度上来比较，skiplist比平衡树要简单得多。

Redis为什么这么快

Redis基于Reactor模式开发了自己的网络事件处理器：这个处理器被称为文件事件处理器（file event handler）：

• 文件事件处理器使用I/O多路复用（multiplexing）程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
• 当被监听的套接字准备好执行连接应答（accept）、读取（read）、写入（write）、关闭（close）等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

1、完全基于内存，绝大部分请求是纯粹的内存操作，非常快速。数据存在内存中，类似于HashMap，HashMap的优势就是查找和操作的时间复杂度都是O(1)；
2、数据结构简单，对数据操作也简单，Redis中的数据结构是专门进行设计的；
3、采用单线程，避免了不必要的上下文切换和竞争条件，也不存在多进程或者多线程导致的切换而消耗 CPU，不用去考虑各种锁的问题，不存在加锁释放锁操作，没有因为可能出现死锁而导致的性能消耗；
4、使用多路I/O复用模型，非阻塞IO；
多路I/O复用模型是利用 select、poll、epoll 可以同时监察多个流的 I/O 事件的能力，在空闲的时候，会把当前线程阻塞掉，当有一个或多个流有 I/O 事件时，就从阻塞态中唤醒，于是程序就会轮询一遍所有的流（epoll 是只轮询那些真正发出了事件的流），并且只依次顺序的处理就绪的流，这种做法就避免了大量的无用操作。
这里“多路”指的是多个网络连接，“复用”指的是复用同一个线程。采用多路 I/O 复用技术可以让单个线程高效的处理多个连接请求（尽量减少网络 IO 的时间消耗），且 Redis 在内存中操作数据的速度非常快，也就是说内存内的操作不会成为影响Redis性能的瓶颈，主要由以上几点造就了 Redis 具有很高的吞吐量。
5、使用底层模型不同，它们之间底层实现方式以及与客户端之间通信的应用协议不一样，Redis直接自己构建了VM 机制 ，因为一般的系统调用系统函数的话，会浪费一定的时间去移动和请求；

动态字符串SDS（保存单个字符串）

IntSet（整数集合）