redis集群、数据结构、底层、算法等总结_redis底层算法

Redis使用文档
一、redis集群模式说明
1、主从复制模式、哨兵模式、cluster高可用集群模式
主从复制模式

（1）工作原理
Slave从节点服务启动并连接到Master之后，它将主动发送一个SYNC命令。Master服务主节点收到同步命令后将启动后台存盘进程，同时收集所有接收到的用于修改数据集的命令，在后台进程执行完毕后，Master将传送整个数据库文件到Slave，以完成一次完全同步。而Slave从节点服务在接收到数据库文件数据之后将其存盘并加载到内存中。此后，Master主节点继续将所有已经收集到的修改命令，和新的修改命令依次传送给数据，Slave将在本次执行这些数据修改命令，从而达到最终的数据同步。
如果Master和Slave之间的链接出现断连现象，Slave可以自动重连Master，但是在连接成功之后，一次完全同步将被自动执行
（2）优点
1、同一个Master可以同步多个Slaves。
2、Slave同样可以接受其它Slaves的连接和同步请求，这样可以有效的分载Master的同步压力。
3、Master Server是以非阻塞的方式为Slaves提供服务。所以在Master-Slave同步期间，客户端仍然可以提交查询或修改请求。
4、Slave Server同样是以非阻塞的方式完成数据同步。在同步期间，如果有客户端提交查询请求，Redis则返回同步之前的数据。
5、为了分载Master的读操作压力，Slave服务器可以为客户端提供只读操作的服务，写服务仍然必须由Master来完成。即便如此，系统的伸缩性还是得到了很大的提高。
6、Master可以将数据保存操作交给Slaves完成，从而避免了在Master中要有独立的进程来完成此操作。
7、支持主从复制，主机会自动将数据同步到从机，可以进行读写分离。
（3）缺点
1、不具备自动容错和恢复功能，主机从机的宕机都会导致前端部分读写请求失败，需要等待机器重启或者手动切换前端的IP才能恢复。
2、主机宕机，宕机前有部分数据未能及时同步到从机，切换IP后还会引入数据不一致的问题，降低了系统的可用性。
3、Redis的主从复制采用全量复制，复制过程中主机会fork出一个子进程对内存做一份快照，并将子进程的内存快照保存为文件发送给从机，这一过程需要确保主机有足够多的空余内存。若快照文件较大，对集群的服务能力会产生较大的影响，而且复制过程是在从机新加入集群或者从机和主机网络断开重连时都会进行，也就是网络波动都会造成主机和从机间的一次全量的数据复制，这对实际的系统运营造成了不小的麻烦。
4、Redis较难支持在线扩容，在集群容量达到上限时在线扩容会变得很复杂。为避免这一问题，运维人员在系统上线时必须确保有足够的空间，这对资源造成了很大的浪费。
哨兵模式

（1）工作原理
1、每个Sentinel(哨兵)进程以每秒钟一次的频率向整个集群中的Master主服务器，Slave从服务器以及其他Sentinel(哨兵)进程发送一个 PING 命令。
2、如果一个实例(instance)距离最后一次有效回复 PING 命令的时间超过 down-after-milliseconds 选项所指定的值， 则这个实例会被 Sentinel(哨兵)进程标记为主观下线(SDOWN)
3、如果一个Master主服务器被标记为主观下线(SDOWN)，则正在监视这个Master主服务器的所有 Sentinel(哨兵)进程要以每秒一次的频率确认Master主服务器的确进入了主观下线状态
4、当有足够数量的 Sentinel(哨兵)进程(大于等于配置文件指定的值)在指定的时间范围内确认Master主服务器进入了主观下线状态(SDOWN)， 则Master主服务器会被标记为客观下线(ODOWN)
5、在一般情况下， 每个 Sentinel(哨兵)进程会以每 10 秒一次的频率向集群中的所有Master主服务器、Slave从服务器发送 INFO 命令。当Master主服务器被 Sentinel(哨兵)进程标记为客观下线(ODOWN)时，Sentinel(哨兵)进程向下线的 Master主服务器的所有 Slave从服务器发送 INFO 命令的频率会从 10 秒一次改为每秒一次。若没有足够数量的 Sentinel(哨兵)进程同意 Master主服务器下线， Master主服务器的客观下线状态就会被移除。若 Master主服务器重新向 Sentinel(哨兵)进程发送 PING 命令返回有效回复，Master主服务器的主观下线状态就会被移除。
6、哨兵集群中所有的节点会进行通信，但通信过程中发现有超过一般以上的哨兵认为master主观下线了，那么标记master为客观线下（ODOWN）

（2）选举（Raft算法）
基本上哪个哨兵节点最先判断出这个主节点客观下线（ODOWN），就会在各个哨兵节点中发起投票机制Raft算法（选举算法），最终被投为领导者的哨兵节点完成主从自动化切换的过程。
举采用Raft算法:
2.1 发现master下线的哨兵节点（我们称他为A）向每个哨兵发送命令，要求对方选自己为领头哨兵
2.2 如果目标哨兵节点没有选过其他人，则会同意选举A为领头哨兵
2.3 如果有超过一半的哨兵同意选举A为领头，则A当选
2.4 如果有多个哨兵节点同时参选领头，此时有可能存在一轮投票无竞选者胜出，此时每个参选的节点等待一个随机时间后再次发起参选请求，进行下一轮投票精选，直至选举出领头哨兵
2.5 选出领头哨兵后，领头者开始对进行故障恢复，从出现故障的master的从数据库slave中挑选一个来当选新的master,选择规则如下：
2.5.1 所有在线的slave中选择优先级最高的，优先级可以通过slave-priority配置
2.5.2 如果有多个最高优先级的slave，则选取复制偏移量最大（即复制越完整）的当选
2.5.3 如果以上条件都一样，选取id最小的slave
2.6挑选出需要继任的slaver后，领头哨兵向该数据库发送命令使其升格为master，然后再向其他slave发送命令接受新的master，最后更新数据。将已经停止的旧的master更新为新的master的从数据库，使其恢复服务后以slave的身份继续运行。

(3)优缺点
和主从复制很类似，唯一的区别就是，哨兵模式当集群中节点出现问题时可以自动恢复，能够提升slave为master。
Cluster高可用模式

（1）工作原理
Redis Cluster 是Redis的集群实现，内置数据自动分片机制，集群内部将所有的key映射到16384个Slot中，集群中的每个Redis 每个分片负责其中的一部分的Slot的读写。集群客户端连接集群中任一Redis 分片即可发送命令，当Redis 分片收到自己不负责的Slot的请求时，会将负责请求Key所在Slot的Redis 分片地址返回给客户端，客户端收到后自动将原请求重新发往这个地址，对外部透明。一个Key到底属于哪个Slot由crc16(key) % 16384 决定。
（2）优点
1、数据按照 slot 存储分布在多个节点，节点间数据共享，可动态调整数据分布;
2、可扩展性：可线性扩展到 1000 多个节点，节点可动态添加或删除;
3、高可用性：部分节点不可用时，集群仍可用。通过增加 Slave 做 standby 数据副本，能够实现故障自动 failover，节点之间通过 gossip 协议交换状态信息，用投票机制完成 Slave 到 Master 的角色提升;
4、降低运维成本，提高系统的扩展性和可用性。
（3）缺点
1、Client 实现复杂
2、节点会因为某些原因发生阻塞(阻塞时间大于 clutser-node-timeout)，被判断下线
3、数据通过异步复制，不保证数据的强一致性。
4、Slave 在集群中充当“冷备”，不能缓解读压力
5、Key 批量操作限制，如使用 mset、mget 目前只支持具有相同 slot 值的 Key 执行批量操作
二、redis数据结构说明
1、string数据结构
(1)单值缓存
Set key value
Get key
(2)对象缓存
Set user:1 value(json格式数据)
(3)批量缓存
Mset user:1:name zhangsan user:1:age 18
Mget user:1name user:1:age user:1
(4)分布式锁
Setnx product:1 true //返回1代表获取到锁成功
Setnx product:1 false //返回0代表获取到锁失败
Del product:1 //释放锁
Set product:1 true ex 10 nx //防止程序意外终止导致死锁
(5)原子计数
Incr rank //加1
Decr rank //减 1
INCRBY rank 2 //加一个给定值
DECRBY count 2 //减一个给定值

2、hash数据结构
优点
1、同类数据进行整合存储，方便后期数据管理
2、相比string操作消耗内存与cpu小
3、相比string存储节省存储空间

缺点
1、过期功能不能使用在field上，只能用在key上
2、Redis 高可用集群模式下不适合大规模使用
Hset product name “苹果”
Hget product name
HgetAll product
Hkeys product

3、list数据结构
Lpush key values //将一个或多个值插入列表的表头（左）
Rpush key values //将一个或多个值插入列表的表头（右）
Lpop key //从列表取出一个元素（左）
Rpop key //从列表取出一个元素（右）
Lrange key start stop //返回列表中一段区间内元素 取全部（0，-1）
Blpop key timeot //从列表表头弹出一个元素（左），若没元素进行阻塞等待 timeot 表示阻塞等待时间 timeot=0则表示一直等待
BRpop key timeot //从列表表头弹出一个元素(右)，若没元素进行阻塞等待 timeot 表示阻塞等待时间 timeot=0则表示一直等待
4、set数据结构
（1）常用操作
Sadd key member[member…]//往集合添加元素，元素存在则忽略 若key不存在则新建
Srem key member[member…]//从集合中删除元素
Smembers key //获取集合key中所有元素
Scard key //获取集合中元素个数
Sismember key member //判断member元素是否存在于集合key中
Srandmember key [count] //从集合中选出count个元素，元素不从key中删除
Spop key [count] //从集合key中选出count个元素，元素从key中删除
（2）运算操作
Sinter key [key…] //交集
Sinterstore destination key [key…] //将交集结果存入新集合destination 中
Sunion key [key…] //并集
Sunionstore destination key [key…] //将并集结果存入新集合destination 中
Sdiff key [key…] //差集
Sdiffstore destination key [key…] //将差集结果存入新集合destination 中

5、zset数据结构
（1）常用操作
Zadd key score member [ [score member]…] //往集合中添加带分值的元素
Zrem key member [member…] //从集合key中删除元素
Zscore key member //返回有序集合key中元素member 的分值
Zincrby key increment member //为有序集合key中元素member的分值加上increment
Zcard key //返回有序集合key中元素个数
Zrange key start stop [withscores] //正序获取有序集合key从start 下标到stop下标的元素
Zrevrange key start stop [withscores] //倒序获取有序集合key从start 下标到stop下标的元素
（2）运算操作
Zunionstore destkey numkeys key [key…] //并集计算
Zinterstore destkey numkeys key [key…] //交集计算
三、redis底层数据结构
1、简单动态字符串
Redis底层自己实现了SDS 的空间分配策略
/*

• 保存字符串对象的结构
  */
  struct sdshdr {

  // buf 中已占用空间的长度
  int len;

  // buf 中剩余可用空间的长度
  int free;

  // 数据空间
  char buf[];
  };
  优点
  1、获取字符串长度（SDS O（1）/C 字符串 O(n)）
  2、避免缓冲区溢出
  3、减少修改字符串时带来的内存重分配次数
  4、惰性空间释放
  5、二进制安全
  2、链表
  链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。（其中list底层就是要链表）
  ypedef struct list{
  //表头节点
  listNode * head;
  //表尾节点
  listNode * tail;
  //链表长度
  unsigned long len;
  //节点值复制函数
  void *(*dup) (void *ptr);
  //节点值释放函数
  void (*free) (void *ptr);
  //节点值对比函数
  int (*match)(void *ptr, void key);
  }
  链表的特性
  双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）
  无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
  表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
  长度计数器：链表中存有记录链表长度的属性 len
  多态：链表节点使用 void 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。
  3、字典
  字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构（redis采用hash表实现字典、用链地址法（单项链表）解决hash冲突）
  typedef struct dictht {
  //哈希表数组
  dictEntry **table;
  //哈希表大小
  unsigned long size;

  //哈希表大小掩码，用于计算索引值
  unsigned long sizemask;
  //该哈希表已有节点的数量
  unsigned long used;
  }
  4、跳跃表
  是在链表的基础上改进而来的，虽然跳跃表的具体实现有很多种，但它的主要思想都是在有序的链表上(原始链表)，随机提取一些关键结点到上一层形成一个新的有序链表作为索引链表，当然为了提高查找效率，索引链表往往不会只是一层，而是在索引链表中再提取一些关键结点到上一层形成更高一层的有序索引链表，不断的提取以此形成多层链表(Redis底层使用的跳表最多允许32层)（在redis中用在有序集合键zset、集群节点内部数据结构在redis中用在有序集合键、集群节点内部数据结构）
  5、整数集合
  Reids对整数存储专门作了优化，intset就是redis用于保存整数值的集合数据结构。当一个结合中只包含整数元素，redis就会用这个来存储。
  typedef struct intset {

  // 编码方式
  uint32_t encoding;

  // 集合包含的元素数量
  uint32_t length;

  // 保存元素的数组
  int8_t contents[];

}
6、压缩列表
ziplist是redis为了节约内存而开发的顺序型数据结构。它被用在列表键和哈希键中。一般用于小数据存储。
7、快速列表
一个由ziplist组成的双向链表。但是一个quicklist可以有多个制品ziplist节点，它很像B树的存储方式。是在redis3.2版本中新加的数据结构，用在列表的底层实现。

四、redis持久化aof&rdb
由于Redis是基于内存的数据库，为了保证数据的可用性，Redis提供了两种数据持久化机制：RDB和AOP，下面对这两种持久化方式加以分析
1、Aof
（1）配置
aof机制默认关闭，可以通过appendonly = yes参数开启aof机制，通过appendfilename = myaoffile.aof指定aof文件名称。
对于触发aof重写机制也可以通过配置文件来进行设置：第一个参数是配置较前一个aof文件大小增长的百分比，第二个参数是配置触发aof重写的aof的最小的大小。
auto-aof-rewrite-percenttage = 100
auto-aof-rewrite-min-size 64mb
修改aof的fsync策略：
appendfsync=always 同步持久化每一次修改操作
appendfsync=everysec 每秒向aof文件同步一次
appendfsync=no 关闭向aof文件写入修改
（2）aof的优点
1.支持不同的fsync策略：no/always/everysec
2.能够记录所有写操作，不会造成数据丢失
3.aof重写机制确保aof文件不会过大
4.aof文件可以很容易的读懂
（3）缺点
1.虽然有aof重写机制，单aof文件通常比rdb文件大
2.在不同的fsync策略写，redis性能会受到一定影响
2、Rdb
（1）运行原理

1、RDB模式可以在指定的时间间隔内生成内存中整个数据集的持久化快照。快照文件默认被存储在当前文件夹中，名称为dump.rdb，可以通过dir和dbfilename参数来修改默认值。2、在执行fork函数的时候，操作系统会使用写时复制（copy-on-write）策略，也就是说在调用fork的一刻，父子进行有相同的内存模型，当父进程要修改其中的某片数据时，操作系统会将该片数据复制一份，从而保证不影响子进程。
3、rdb文件是经过压缩的文件，占用的空间比较小，更有利于传输，并且数据恢复速度也比较快。
（2）优点
1.rdb持久化文件很紧凑，占用空间更小。（占空间小）
2.rdb保存的是基于时间点的数据快照，更适合数据的备份和容灾（生成快照）
3.利用rdb文件进行数据恢复时，速度更快（恢复数据快）
（3）缺点
1.会造成部分数据的丢失（丢数据）
2.当数据集非常大时，fork操作会占用很多系统资源，造成主服务进程假死（假死）
五、redis三大问题解决
1、缓存丢失
（1）造成原因
缓存丢失即由于缓存策略淘汰，或者缓存没有进行持久化或者集群没有数据备份等造成查询时没有找到对应的数据，最终可能造成缓存穿透
（2）解决方案
1、选择合适的缓存淘汰策略
2、进行缓存数据持久化
3、搭建高可用集群，进行savle数据高可用备份
2、缓存穿透
（1）造成原因
缓存穿透即由于客户端在进行数据查询时没有命中缓存数据，或者缓存数据不存在而穿透缓存进行数据库查询，最终可能导致数据库压力比较大，当有大量的请求压倒数据库可能造成数据库服务死掉
（2）解决方案
1、对null进行缓存
2、布隆过滤器拦截
3、缓存雪崩
（1）造成原因
由于缓存层承载着大量请求，有效地保护了存储层，但是如果缓存层由于某些原因不可用（宕机）或者大量缓存由于超时时间相同在同一时间段失效（大批key失效/热点数据失效），大量请求直接到达存储层，存储层压力过大导致系统雪崩。

（2）解决方案
1、设置缓存过期时间不相同
2、数据提前预热
3、数据备份和恢复

六、redis缓存淘汰
1、常用的淘汰算法
1、FIFO：First In First Out，先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。（先进先淘汰）
2、LRU：Least Recently Used，最近最少使用。判断最近被使用的时间，目前最远的数据优先被淘汰。（长时间没被使用）
3、LFU：Least Frequently Used，最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。（一段时间使用次数最少的）
2、Redis淘汰策略算法（6种）
1、noeviction：（不淘汰-达到内存限制直接报错）
达到内存限额后返回错误，客户尝试可以导致更多内存使用的命令（大部分写命令，但DEL和一些例外）
2、allkeys-lru：（最近很少使用）
为了给新增加的数据腾出空间，驱逐键先试图移除一部分最近使用较少的（LRC）。
3、volatile-lru：（最近很少使用-已过期）
为了给新增加的数据腾出空间，驱逐键先试图移除一部分最近使用较少的（LRC），但只限于过期设置键。
4、allkeys-random:（随机）
为了给新增加的数据腾出空间，驱逐任意键
5、volatile-random（随机-已过期）

为了给新增加的数据腾出空间，驱逐任意键，但只限于有过期设置的驱逐键。
6、volatile-ttl: （即将过期）
为了给新增加的数据腾出空间，驱逐键只有秘钥过期设置，并且首先尝试缩短存活时间的驱逐键