1. 基础与理论

1.1. Redis的5种数据结构

1.1.1 String

String 是Redis 最简单的数据机构，它内部表示就一个字符数组。Redis 所有的数据结构都以唯一的Key字符串作为名称，然后通过这个唯一的key值来获取相应的value数据。不同类型的数据结构的差异就在于value值的结构不一样
Redis.jpg
Redis 的字符串是动态字符串，可以修改的字符串，内部结构类似于Java的ArrayList，采用预分配方式来减少内存的频繁分配，内部为当前字符串的实际空间capacity一般要求高于实际字符串长度len。当字符串长度小于1MB时，扩容都是加倍现有空间。如果字符串长度超过1MB，扩容时一次只会多扩1MB的空间。Redis的最大字符串长度为512MB
Redis-第 2 页.jpg

1.1.2. List

Redis 种的list列表相当于Java中的LinkedLIst，它是一个链表结构而并非数组结构。这意味着list的插入和删除操作非常块，时间复杂度为O(1)，但是索引定位很慢，时间复杂度为O(n)。列表中的每个元素都使用双向指针顺序，串起来可以同时支持前向和后向遍历
Redis-第 3 页.jpg
Redis 的列表结构常用来做异步队列使用，将需要延后处理的任务序列化成字符串，放到Redis列表中，另一个线程从这个列表中轮询获取数据进行处理

  1. 左边进右边出（队列思想）

image.png

  1. 右边进右边出（栈思想）

image.png

  1. 慢操作

lindex相当于Java链表的get(index)方法，它需要遍历链表，性能随着参数index增大而变慢

1.1.3. Hash

Redis 中的Hash相当于Java中的HashMap，它是无序的，内部存储了很多键值对。实现结构上与Java的HashMap也是一样的，都是数组+链表二维结构。如下图：第一维是数组，第二维是链表
Redis-第 4 页.jpg
Redis 的hash值只能是字符串，另外他们rehash和Java的HashMap不一样。Java的HashMap在扩容时需要一次全部对所有元素进行rehash。Redis为了追求高性能，不能堵塞服务，采用渐进式的rehash策略
渐进式rehash会在rehash的同时，保留新旧两个hash结构，查询时会同时查询两个hash结构，然后在后续的定时任务以及hash操作制定中，循序渐进的将就hash的内容一点点迁移到新的hash结构中。当搬迁完成就会使用新的hash结构取而代之
Redis-第 5 页.jpg
当hash移除了最后一个元素之后，该数据结构会被自动删除，内存被回收。
hash结构也可以用来存储用户信息，与字符串需要一次性全部序列化整个对象不同，hash可以对用户结构中的每个字段单独存储。这样当我们需要获取用户信息时可以进行部分获取。而以整个字符串的形式去保存用户信息的话，就只能一次性读取用户的整个序列化对象，这样做的缺点会浪费网络资源

1.1.4. Set

Redis 的集合相当于Java中的HashSet，它的内部键值对是无序的、唯一的。它的内部实现相当于一个特殊的字典，字典中所有的value都是一个NULL。当集合中最后一个元素被移除后，数据结构被自动删除，内存被回收
set结构可以用来存储在某活动中奖用户ID，因为有去重功能，可以保证同一个用户不会中奖两次。

  1. Redis-1:0>sadd books python
  2. "1"
  3. Redis-1:0>sadd books python   #重复，无法添加
  4. "0"
  5. Redis-1:0>
  8. Redis-1:0>sadd books java golang
  9. "2"
  10. Redis-1:0>smembers books  #注意查询顺序和插入顺序不一样，因为set是无序的
  11.  1)  "golang"
  12.  2)  "java"
  13.  3)  "python"
  15. Redis-1:0>sismember books java #查询某个value值是否存在，相当于contains(0)
  16. "1"

1.1.5. ZSet

zset可能是Redis提供的最有特色的数据结构，它也是在面试中面试官最爱问的数据结构，ZSet类似Java中的SortedSet和HashMap的组合，它是一个set保证了value的唯一性，又给value赋予一个score代表这个value的排序权重。它的内部实现是一种叫作跳跃列表的数据结构
ZSet 中最后一个value被移除后，数据结构被自动删除，内存被回收
ZSet可以用来存储粉丝列表，value值是粉丝的用户ID，score是关注时间。我们可以对粉丝列表按关注时间进行排序
ZSet还可以用来存储学生成绩，value值是学生ID，score是学生的考试成绩。我们对成绩按分数进行排序就可以得到他的名次

1.1.5.1. 跳跃列表

zset 内部的排序功能是通过“跳跃列表”数据结构来实现的，它的结构非常特殊，结构也复杂。因为zset要支持随机的插入和删除，所以它不宜用数组来表示。

跳表(skip List)是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为O(logN)。简单说来跳表也是链表的一种，只不过它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，跳表能够提供O(logN)的时间复杂度。
先来看一个有序链表，如下图（最左侧的灰色节点表示一个空的头结点）：
20210515142522687.png
在这样一个链表中，如果我们要查找某个数据，那么需要从头开始逐个进行比较，直到找到包含数据的那个节点，或者找到第一个比给定数据大的节点为止（没找到）。也就是说，时间复杂度为O(n)。同样，当我们要插入新数据的时候，也要经历同样的查找过程，从而确定插入位置。
假如我们每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：
2021051514255558.png
这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半（上图中是7, 19, 26）。现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比如，我们想查找23，查找的路径是沿着下图中标红的指针所指向的方向进行的：
2021051514255558.png

1.1.5.1.1. 插入

skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程：
20210515142704322.png

1.2. 布隆过滤器

布隆过滤器可以理解为一个不怎么精确的set结构，当你使用它的contains方法判断某个对象是否存在时，它可能会误判，但是布隆过滤器也不是特别不精确，只要参数设置得合理，它的精确度也可以控制得相对足够精确，只会有小小的误判概率。
布隆过滤器说某个值存在时，这个值可能不存在。当它说某个值不存在时，那它肯定不存在。举个例子：当它说不认识你时，那肯定就是真的不认识你。当它说认识你时，确有可能不认识你，只是因为你的脸跟它认识的某个人的脸比较像，所以误判认识你。

1.2.1. 布隆过滤器原理

每个布隆过滤器对应到Redis的数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数。无偏就是能够把元素的hash值算的比较均匀，让元素被hash映射到位数组中的位置比较随机
Redis.jpg

1.2.2. 向布隆过滤器中add

在向布隆过滤器添加Key时，会使用多个hash函数对key进行hash运算，每个hash函数都会算得一个整数索引，然后用索引和数组长度进行位运算（跟索引和数组长度去摸结果一样）。再把位数组得这几个位置都置为1，完成添加操作。

1.2.3. 布隆过滤器如何询问key是否存在

向布隆过滤器询问key是否存在时，跟add操作一样，会使用和add添加时同样得hash函数对key进行运算。然后通过位运算得出位置，看数组中这几个位置得值是否都位1，只要有一个为0，那么就说明布隆过滤器中得这个key不存在。如果这数组中这几个位置得值都为1，并不能说明这个key就一定存在，只能说明有很大概率存在，因为这些被置为1可能是因为其他key 在add时所致。

1.2.4. 布隆过滤器得应用

布隆过滤器可以应用于在爬虫系统中对URL得去重，邮箱系统垃圾过滤，数据库查询过滤等

2. 原理

2.1. Redis 持久化

Redis 有两种持久化机制，一种是快照（RDB），另一种是AOF日志。快照是一次全量备份，AOF日志是连续的增量备份，快照是内存数据的二进制序列化形式，在存储上非常紧凑。

2.1.1. 快照持久化（RDB）

  1. 优点
  • RDB是一个非常紧凑的文件
  • RDB在保存RDB文件时父进程唯一需要做的就是fork出一个子进程，接下来的工作全由子进程来做，父进程不需要在做其他IO操作，所以RDB的持久化方式可以最大化Redis的性能。
  • 与AOF相比，在恢复大的数据集的时候，RDB的方式会更快一些
  1. 缺点
  • 数据丢失风险大
  • RDB需要经常fork子进程来保存数据集到硬盘上，当数据集比较大的时候，fork的过程是非常耗时的，可能会导致Redis在一些毫秒级不能响应客户端请求
  • aof（Append Only File）
  • aof文件是一个只进行追加的日志文件
  • Redis可以在aof文件体积变得过大时，自动的在后台对AOF进行重写
  • aof文件有序的保存了对数据库执行的所有写入操作，这些写入操作以Redis协议的格式保存，因此aof文件的内容非常容易被人读懂，对文件进行分析也很轻松

2.1.2. AOF 持久化

  1. 优点
  • 每修改同步：appendfsync always 同步持久化，每次发生数据变化会被立即同步到磁盘，性能较差但数据完整性比较好。
  • 每秒同步：appendsync everysec 异步操作，每秒记录，如果一秒内宕机，有数据丢失
  • 不同步：appendsync no 从不同步
  1. 缺点
  • 相同数据集的数据而言aof文件要远大于rdb文件，恢复速度慢于rdb
  • aof运行效率要慢于rdb，每秒的同步策略效率较好，不同步效率和rdb相同

2.1.3. 混合持久化

在Redis4.0之后，重启Redis时，我们很少使用RDB来恢复内存状态，因为会丢失大量数据。我们通常使用AOF日志重放，但是重放AOF日志相对于使用RDB来说要慢很多，这样在Redis实例很大的时候，启动需要花费很长时间。
为了解决这个问题Redis4.0 带来了一个新的持久化选项—混合持久化。将RDB文件的内容和增量的AOF日志文件存在一起，这里的AOF日志不在是全量的日志，而是自持久化开始到持久化结束的这段时间发生的增量AOF日志，通常这部分AOF日志很小
Redis-第 2 页.jpg
在Redis重启的时候，先加载rdb的内容，然后再重放增量AOF日志，替代AOF全量文件重放，重启效率因此得到大幅提升。

3. 集群

3.1. 主从同步

有了主从，当主节点挂掉的时候，从节点可以顶替主节点。使应用可以继续对外提供服务。如果没有主从那么当主节点宕机时，重启时恢复数据是一个很耗时的过程，从而影响线上业务的持续提供服务。

3.1.1. 增量同步

Redis同步的是指令流，主节点会将那些对自己的状态产生修改性影响的指令记录再本地的内存buffer中，然后异步将buffer中的指令同步到从节点，从节点一边执行同步的指令流来达到和主节点一样的状态，一边向主节点反馈自己同步到哪里了（通过偏移量）

因为内存的buffer是有限的，所以Redis 主节点不能将所有的指令都记录在内存buffer中。Redis 的复制内存buffer是一个定长的环形数组。如果数组满了，就会从头开始覆盖前面的内容

如果因为网络状况不好，从节点在短时间内无法和主节点同步，那么当网络状况恢复时，Redis 的主节点中那些没有同步的指令在buffer中有可能意见被后续的指令覆盖掉。从节点将无法直接通过指令流来进行同步，这个时候就需要用到快照同步

3.1.2. 快照同步

快照同步是一个非常耗时的操作，它首先需要在主节点上进行一次bgsave，将当前内存的数据全部快照到磁盘中，然后再将快照文件的内容全部传送到从节点。从节点将快照文件接受完毕后，立即执行一次全量加载，加载之前要将当前内存数据清空，加载完毕后通知主节点继续进行增量同步

在整个快照同步进行的过程中，主节点的复制buffer还在不停地往前移动，如果快照同步地时间过长或者复制buffer太小，都会导致同步期间增量指令在复制buffer中被覆盖，这样就会导致快照同步完成后无法进行增量复制，然后再发起快照同步，如此既有可能陷入快照同步的死循环。

3.2.3. 无盘复制

主节点在进行快照同步时，会进行很耗时的文件IO操作，在非SSD磁盘存储时，快照同步会对系统的负载产生很大的影响。特别是当系统正在进行AOF的fsync操作时，如果发生快照同步，fsync将会被推迟执行，这就会严重影响主节点的服务效率。
从Redis2.8.18版本开始，Redis支持无盘复制。所谓无盘复制是指主服务器直接通过套接字将快照内容发送到从节点，生成快照是一个遍历的过程，主节点会遍历内存，一边将序列化的内容发送到从节点，从节点还是跟之前一样，先将接收到的内容存储到磁盘文件中，在进行一次性加载。