Redis-0-知识点汇总.md

数据结构

基本

字符串

一个 key 对应一个 value

原理

如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 类型标识，那么字符串对象会讲整数值保存在 ptr 属性中，并将 encoding 设置为 int。

如果字符串对象保存的是一个字符串值，Redis 的字符串底层数据结构是 sds（simple dynamic string），即简单动态字符串。

具体由 embstr 编码方式和 raw 编码方式实现

embstr
raw
对比
- embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。
- 释放 embstr 编码的字符串对象只需要调用一次内存释放函数，而释放 raw 编码的字符串对象需要调用两次内存释放函数。
- 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起 raw ，编码的字符串对象能够更好地利用缓存带来的优势。

sdshdr

结构

```
struct sdshdr{

int len;//已使用保存的字符串长度
int free;//未使用字符串长度
char buf[];保存字符串的数组

}

          - 版本区别
            - Redis3.2 之前，统一使用一个版本的 sdshdr。
            - Redis3.2 开始，对数据结构做出了修改，针对不同的长度范围定义了不同的结构。
              - sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，用于存储不同的长度的字符串，分别代表 $2^5=32B$，$2^8=256B$，$2^16=64KB$，$2^32=4GB$，$2^64$ 约等于无穷大，但实际官方字符串 value 最大值为 512M。
      - 版本区别
        - Redis 的 embstr 编码方式和 raw 编码方式在 3.0 版本之前是以 39 字节为分界的
        - 在 3.2 版本之后，则变成了 44 字节为分界
          - 在 44 字节以内，使用 embstr 实现
          - 超过了 44 字节，使用 raw 存储
  - 相关问题
    - **Redis 字符串与 C 语言中的字符串区别？**
      - 复杂度问题
        - SDS 由于存储了 len 属性，所以获取字符长度的时间复杂度为 $O(1)$，而 C 字符串并不记录本身长度，故获取字符串长度需要遍历整个字符串，直到遇到空字符，时间复杂度为 $O(N)$。
      - 内存分配释放策略
        - SDS 是预分配+惰性释放
        - SDS 的内存分配策略：
          - 如果对 SDS 字符串修改后，len 的值小于 1MB，那么程序会分配和 len 同样大小的空间，此时 len 和 free 的值是相同的，例如，如果 SDS 的字符串长度修改为 15 字节，那么会分配 15 字节空间给 free，SDS 的 buf 属性长度为 15（len）+15（free）+1（空字符）= 31 字节。
          - 如果SDS字符串修改后，len 大于等于 1MB，那么程序会分配 1MB 的空间给 free，例如，SDS 字符串长度修改为 50MB 那么程序会分配 1MB 的未使用空间给 free，SDS 的 buf 属性长度为 50MB（len）+1MB（free）+1byte（空字符）。
        - SDS 的内存释放策略：
          - 当需要缩短 SDS 字符串时，程序并不立刻将内存释放，而是使用 free 属性将这些空间记录下来，以备将来使用。
      - 缓冲区溢出问题
        - SDS 的字符串的内存预分配策略能有效避免缓冲区溢出问题
        - C 字符串每次操作增加长度时，都要分配足够长度的内存空间，否则就会产生缓冲区溢出（buffer overflow）。
      - 二进制安全问题
        - SDS 字符串 API 都是以处理二进制的方式处理 buf 数组里的数据，程序不会对其中的数据进行过滤、操作等，所以 SDS 是二进制数据安全的。
        - C 字符串的字符则必须符合某种编码（ASCII），并且字符串的中间不能包含空字符，否则字符串就会被截断，所以 C 字符串智能保存文本数据，而不能保存图片、音视频等数据类型。
    - **为什么 Redis 的 embstr 与 raw 编码方式不再以 39 字节为界？**
      - embstr 是一块连续的内存区域，由 redisObject 和 sdshdr 组成。其中 redisObject 占 16 个字节，当 buf 内的字符串长度是 39 时，sdshdr 的大小为 8+39+1=48，那一个字节是'\0'。加起来刚好 64。
      - 从 2.4 版本开始，redis 开始使用 jemalloc 内存分配器。这个比 glibc 的 malloc 要好不少，还省内存。在这里可以简单理解，jemalloc 会分配 8，16，32，64 等字节的内存。embstr 最小为 16+8+8+1=33，所以最小分配 64 字节。当字符数小于 39 时，都会分配 64 字节。这个默认 39 就是这样来的。
      - 本身就是针对短字符串的 embstr 自然会使用最小的 sdshdr8，而 sdshdr8 与之前的 sdshdr 相比正好减少了 5 个字节（sdsdr8 = uint8_t * 2 + char = 1*2+1 = 3, sdshdr = unsigned int * 2 = 4 * 2 = 8）,所以其能容纳的字符串长度增加了 5 个字节变成了 44。
- list（列表）
  - Redis 链表是一个双向无环链表结构，可以通过 push 和 pop 操作从列表的头部或者尾部添加或者删除元素，这样 list 即可以作为栈，也可以作为队列。很多发布订阅、慢查询、监视器功能都是使用到了链表来实现。
  - 原理
    - 底层有 linkedList、zipList 和 quickList 这三种存储方式。
    - 数据结构
      - linkedList、zipList
        - 当列表对象中元素的长度较小或者数量较少时，通常采用 zipList 来存储；当列表中元素的长度较大或者数量比较多的时候，则会转而使用双向链表 linkedList 来存储。
        - 双向链表 linkedList 便于在表的两端进行 push 和 pop 操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还有额外保存两个指针；其次，双向链表的各个节点都是单独的内存块，地址不连续，容易形成内存碎片。
        - zipList 存储在一块连续的内存上，所以存储效率很高。但是它不利于修改操作，插入和删除操作需要频繁地申请和释放内存。特别是当 zipList 长度很长时，一次 realloc 可能会导致大量的数据拷贝。
      - quickList
        - 在 Redis3.2 版本之后，list 的底层实现方式又多了一种，quickList。qucikList 是由 zipList 和双向链表 linkedList 组成的混合体。它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。
        - ![Redis_quickList](Redis-0-知识点汇总/Redis_quickList.png)
- hash（散列）
  - hash 是一个 string 类型的 field 和 value 的映射表，hash 特别适合用于存储对象。
  - 原理
    - 哈希对象的编码有两种，分别是：ziplist、dict。
    - 数据结构
      - ziplist
        - 使用压缩列表实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的节点推入到压缩列表的表尾，然后再将保存了值的节点推入到压缩列表表尾。
        - ![Redis_ziplist_2](Redis-0-知识点汇总/Redis_ziplist_2.jpg)
      - dict
        - 使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值来保存，跟 java 中的 HashMap 类似。
        - ![Redis_hashtable](Redis-0-知识点汇总/Redis_hashtable.jpg)
    - 切换条件
      - 当哈希对象保存的键值对数量小于 512，并且所有键值对的长度都小于 64 字节时，使用压缩列表存储；否则使用 dict 存储。
  - 扩容流程（渐进式 rehash）
    1. 计算新表 size、掩码，为新表 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
    2. 将 rehash 索引计数器变量 rehashidx 的值设置为 0，表示 rehash 正式开始。
    3. rehash 进行期间，每次对字典执行添加、删除、査找、更新操作时，程序除了执行指定的操作以外，还会触发额外的 rehash 操作，在源码中的 _dictRehashStep 方法。
       - 该方法会从 ht[0] 表的 rehashidx 索引位置上开始向后查找，找到第一个不为空的索引位置，将该索引位置的所有节点 rehash 到 ht[1]，当本次 rehash 工作完成之后，将 ht[0] 索引位置为 rehashidx 的节点清空，同时将 rehashidx 属性的值加一。
    4. 将 rehash 分摊到每个操作上确实是非常妙的方式，但是万一此时服务器比较空闲，一直没有什么操作，难道 redis 要一直持有两个哈希表吗？
       - 答案当然不是的。我们知道，redis 除了文件事件外，还有时间事件，redis 会定期触发时间事件，这些时间事件用于执行一些后台操作，其中就包含 rehash 操作：当 redis 发现有字典正在进行 rehash 操作时，会花费 1 毫秒的时间，一起帮忙进行 rehash。
    5. 随着操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被 rehash 至 ht[1]，此时 rehash 流程完成，会执行最后的清理工作：释放 ht[0] 的空间、将 ht[0] 指向 ht[1]、重置 ht[1]、重置 rehashidx 的值为 -1。
- sets（集合）
  - Redis 提供的 set 数据结构，可以存储一些集合性的数据。set 中的元素是没有顺序的。
  - 原理
    - 集合对象的编码有两种，分别是：intset、dict。
    - 切换条件
      - set 的底层存储 intset 和 dict 是存在编码转换的，使用 intset 存储必须满足下面两个条件，否则使用 dict，条件如下：
        - 结合对象保存的所有元素都是整数值
        - 集合对象保存的元素数量不超过 512 个
- sorted set（有序集合）
  - sorted set 增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列
  - 原理
    - 底层数据结有序集合对象的编码有两种，分别是：ziplist、skiplist。
    - 数据结构
      - ziplist
        - 当保存的元素长度都小于 64 字节，同时数量小于 128 时，使用该编码方式，否则会使用 skiplist。
        - ![Redis_ziplist](Redis-0-知识点汇总/Redis_ziplist.jpg)
      - skiplist
        - zset 实现，一个 zset 同时包含一个字典（dict）和一个跳跃表（zskiplist）
        - ![Redis_skiplist](Redis-0-知识点汇总/Redis_skiplist.jpg)
    - 切换条件
      - 当有序集合的长度小于 128，并且所有元素的长度都小于 64 字节时，使用压缩列表存储；否则使用 skiplist 存储。
### 高级
- HyperLogLog
  - 通常用于基数统计。使用少量固定大小的内存，来统计集合中唯一元素的数量。统计结果不是精确值，而是一个带有 0.81% 标准差（standard error）的近似值。
  - HyperLogLog 适用于一些对于统计结果精确度要求不是特别高的场景，例如网站的 UV 统计。
  - 在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。
    - 基数
      - 比如数据集 `{1, 3, 5, 7, 5, 7, 8}`，那么这个数据集的基数集为 `{1, 3, 5 ,7, 8}`, 基数（不重复元素）为 5。基数估计就是在误差可接受的范围内，快速计算基数。
- Geo
  - 可以将用户给定的地理位置信息储存起来，并对这些信息进行操作：获取 2 个位置的距离、根据给定地理位置坐标获取指定范围内的地理位置集合。
- Bitmap
  - 位图。
- Stream
  - 主要用于消息队列，类似于 kafka，可以认为是 pub/sub 的改进版。提供了消息的持久化和主备复制功能，可以让任何客户端访问任何时刻的数据，并且能记住每一个客户端的访问位置，还能保证消息不丢失。
### 原理
- RedisObject
  - 为了便于操作，Redis 定义了 RedisObject 结构体来表示 string、hash、list、set、zset 五种数据类型。
  - ![Redis_RedisObject](Redis-0-知识点汇总/Redis_RedisObject.jpg)
  - 结构
    - 源码
      - ```
        /*
         * Redis 对象
         */
        typedef struct redisObject {
            // 类型
            unsigned type:4;
            // 对齐位
            unsigned notused:2;
            // 编码方式
            unsigned encoding:4;
            // LRU 时间（相对于 server.lruclock）
            unsigned lru:22;
            // 引用计数
            int refcount;
            // 指向对象的值
            void *ptr;
        } robj;

type 记录了对象所保存的值的类型, 它的值可能是以下常量的其中一个
- REDIS_STRING // 字符串
- REDIS_LIST // 列表
- REDIS_SET // 集合
- REDIS_ZSET // 有序集
- REDIS_HASH // 哈希表
encoding 记录了对象所保存的值的编码, 它的值可能是以下常量的其中一个
- REDIS_ENCODING_INT // 编码为整数
- REDIS_ENCODING_EMBSTR // embstr 编码
- REDIS_ENCODING_RAW // 编码为字符串
- REDIS_ENCODING_HT // 编码为哈希表
- REDIS_ENCODING_LINKEDLIST // 编码为双端链表
- REDIS_ENCODING_ZIPLIST // 编码为压缩列表
- REDIS_ENCODING_INTSET // 编码为整数集合
- REDIS_ENCODING_SKIPLIST // 编码为跳跃表
ptr 是一个指针, 指向实际保存值的数据结构, 这个数据结构由 type 属性和 encoding 属性决定
refcount
- refcount 表示引用计数，由于 C 语言并不具备内存回收功能，所以 Redis 在自己的对象系统中添加了这个属性，当一个对象的引用计数为 0 时，则表示该对象已经不被任何对象引用，则可以进行垃圾回收了。
lru 表示对象最后一次被命令程序访问的时间。

底层数据结构
- 字符串
  - Redis 没有直接使用 C 语言传统的字符串表示，而是自己实现的叫做简单动态字符串 SDS 的抽象类型。C 语言的字符串不记录自身的长度信息，而 SDS 则保存了长度信息，这样将获取字符串长度的时间由 O(N) 降低到了 O(1)，同时可以避免缓冲区溢出和减少修改字符串长度时所需的内存重分配次数。
- linkedlist
  - Redis链表特性：
    - 双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为 $O(1)$。
    - 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问都是以 NULL 结束。
    - 带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 $O(1)$。
    - 多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。
- dict
  - 用于保存键值对的抽象数据结构。
  - Redis 使用 hash 表作为底层实现，每个字典带有两个 hash 表，供平时使用和 rehash 时使用，hash 表使用链地址法来解决键冲突，被分配到同一个索引位置的多个键值对会形成一个单向链表，在对 hash 表进行扩容或者缩容的时候，为了服务的可用性，rehash 的过程不是一次性完成的，而是渐进式的。
- ziplist
  - 压缩列表是为节约内存而开发的顺序性数据结构，他可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
- skiplist
  - 跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。
  - 结构
  - 特性
    - 由很多层结构组成；
    - 每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点；
    - 最底层的链表包含了所有的元素；
    - 如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；
    - 链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；
  - 操作方式
    - 搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。
    - 插入：首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数 k 后，则需要将新元素插入到从底层到 k 层。
    - 删除：在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。
- intset
  - 用于保存整数值的集合抽象数据结构，不会出现重复元素，底层实现为数组。

持久化

AOF
- Append-only file，将“操作 + 数据”以格式化指令的方式追加到操作日志文件的尾部，在 append 操作返回后（已经写入到文件或者即将写入），才进行实际的数据变更，“日志文件”保存了历史所有的操作过程；当 server 需要数据恢复时，可以直接 replay 此日志文件，即可还原所有的操作过程。
- 优点
  - 可以保持更高的数据完整性，如果设置追加 file 的时间是 1s，如果 Redis 发生故障，最多会丢失 1s 的数据；且如果日志写入不完整支持 redis-check-aof 来进行日志修复；AOF 文件没被 rewrite 之前（文件过大时会对命令进行合并重写），可以删除其中的某些命令（比如误操作的 flushall）。
- 缺点
  - AOF 文件比 RDB 文件大，且恢复速度慢。
- AOF 重写
  - 引入原因
    - AOF 持久化是通过保存被执行的写命令来记录数据库状态的，随着写入命令的不断增加，AOF 文件中的内容会越来越多，文件的体积也会越来越大。
    - 如果不加以控制，体积过大的 AOF 文件可能会对 Redis 服务器、甚至整个宿主机造成影响，并且 AOF 文件的体积越大，使用 AOF 文件来进行数据还原所需的时间就越多。
    - 举个例子，如果你对一个计数器调用了 100 次 INCR，那么仅仅是为了保存这个计数器的当前值，AOF 文件就需要使用 100 条记录。
    - 然而在实际上，只使用一条 SET 命令已经足以保存计数器的当前值了，其余 99 条记录实际上都是多余的。
    - 为了处理这种情况，Redis 引入了 AOF 重写：可以在不打断服务端处理请求的情况下，对 AOF 文件进行重建（rebuild）。
  - 存在的问题
    - AOF 后台重写使用子进程进行从写，解决了主进程阻塞的问题，但是仍然存在另一个问题：子进程在进行 AOF 重写期间，服务器主进程还需要继续处理命令请求，新的命令可能会对现有的数据库状态进行修改，从而使得当前的数据库状态和重写后的 AOF 文件保存的数据库状态不一致。
      - 如何解决 AOF 后台重写存在的数据不一致问题?
        
        为了解决上述问题，Redis 引入了 AOF 重写缓冲区（aof_rewrite_buf_blocks），这个缓冲区在服务器创建子进程之后开始使用，当 Redis 服务器执行完一个写命令之后，它会同时将这个写命令追加到 AOF 缓冲区和 AOF 重写缓冲区。当 aof 重写完成时，主进程在把 aof 重写缓冲区的数据写到 aof 缓冲区，最后 fsync 到 aof 文件中。
  - rewrite 流程
  - 触发时机
    - 触发 rewrite 的时机可以通过配置文件来声明，同时 redis 中可以通过 bgrewriteaof 指令人工干预。
- 触发时机
  - redis 提供了 3 中 aof 记录同步选项：
    - always：每一条 aof 记录都立即同步到文件，这是最安全的方式，也以为更多的磁盘操作和阻塞延迟，是 I/O 开支较大。
    - everysec：每秒同步一次，性能和安全都比较中庸的方式，也是 redis 推荐的方式。如果遇到物理服务器故障，有可能导致最近一秒内 aof 记录丢失（可能为部分丢失）。
    - no：redis 并不直接调用文件同步，而是交给操作系统来处理，操作系统可以根据 buffer 填充情况/通道空闲时间等择机触发同步；这是一种普通的文件操作方式。性能较好，在物理服务器故障时，数据丢失量会因 OS 配置有关。
RDB
- RDB 是在某个时间点将数据写入一个临时文件，持久化结束后，用这个临时文件替换上次持久化的文件，达到数据恢复。
- 优点
  - 使用单独子进程来进行持久化，主进程不会进行任何 I/O 操作，保证了 Redis 的高性能
- 缺点
  - RDB 是间隔一段时间进行持久化，如果持久化之间 Redis 发生故障，会发生数据丢失。所以这种方式更适合数据要求不严谨的时候
  - 每次快照持久化都是将内存数据完整写入到磁盘一次，并不是增量的只同步脏数据。如果数据量大的话，而且写操作比较多，必然会引起大量的磁盘 I/O 操作，可能会严重影响性能。
- RDB 持久化的两种方法
  - save
    - 描述
      - 同步、阻塞
    - 缺点
      - 致命的问题，持久化的时候 redis 服务阻塞（准确的说会阻塞当前执行 save 命令的线程，但是 redis 是单线程的，所以整个服务会阻塞），不能继对外提供请求
  - bgsave
    - 描述
      - 异步、非阻塞
    - 原理
      - fork() + copyonwrite
        
        fork()
        
        fork() 是什么
        
        fork() 是 unix 和 linux 这种操作系统的一个 api，而不是 Redis 的 api。
        
        fork() 有什么用
        
        fork() 用于创建一个子进程，注意是子进程，不是子线程。fork() 出来的进程共享其父类的内存数据。仅仅是共享 fork() 出子进程的那一刻的内存数据，后期主进程修改数据对子进程不可见，同理，子进程修改的数据对主进程也不可见。
        
        比如：A 进程 fork() 了一个子进程 B，那么 A 进程就称之为主进程，这时候主进程子进程所指向的内存空间是同一个，所以他们的数据一致。但是 A 修改了内存上的一条数据，这时候 B 是看不到的，A 新增一条数据，删除一条数据，B 都是看不到的。而且子进程 B 出问题了，对我主进程 A 完全没影响，我依然可以对外提供服务，但是主进程挂了，子进程也必须跟随一起挂。这一点有点像守护线程的概念。Redis 正是巧妙的运用了 fork() 这个牛逼的 api 来完成 RDB 的持久化操作。
        
        Redis 中的 fork()
        
        Redis 巧妙的运用了 fork()。当 bgsave 执行时，Redis 主进程会判断当前是否有 fork() 出来的子进程，若有则忽略，若没有则会 fork() 出一个子进程来执行 rdb 文件持久化的工作，子进程与 Redis 主进程共享同一份内存空间，所以子进程可以搞他的 rdb 文件持久化工作，主进程又能继续他的对外提供服务，二者互不影响。我们说了他们之后的修改内存数据对彼此不可见，但是明明指向的都是同一块内存空间，这是咋搞得？肯定不可能是 fork() 出来子进程后顺带复制了一份数据出来，如果是这样的话比如我有 4g 内存，那么其实最大有限空间是 2g，我要给 rdb 留出一半空间来，扯淡一样！那他咋做的？采取了 copyonwrite 技术。
        
        copyonwrite
        
        原理
        
        主进程 fork() 子进程之后，内核把主进程中所有的内存页的权限都设为 read-only，然后子进程的地址空间指向主进程。这也就是共享了主进程的内存，当其中某个进程写内存时（这里肯定是主进程写，因为子进程只负责 rdb 文件持久化工作，不参与客户端的请求），CPU 硬件检测到内存页是 read-only 的，于是触发页异常中断（page-fault），陷入内核的一个中断例程。中断例程中，内核就会把触发的异常的页复制一份（这里仅仅复制异常页，也就是所修改的那个数据页，而不是内存中的全部数据），于是主子进程各自持有独立的一份。
        
        回到原问题
        
        其实就是更改数据的之前进行 copy 一份更改数据的数据页出来，比如主进程收到了 set k 1 请求（之前 k 的值是 2），然后这同时又有子进程在 rdb 持久化，那么主进程就会把 k 这个 key 的数据页拷贝一份，并且主进程中 k 这个指针指向新拷贝出来的数据页地址上，然后进行更改值为 1 的操作，这个主进程 k 元素地址引用的新拷贝出来的地址，而子进程引用的内存数据k还是修改之前的。
    - 优点
      - 他可以一边进行持久化，一边对外提供读写服务，互不影响，新写的数据对我持久化不会造成数据影响，你持久化的过程中报错或者耗时太久都对我当前对外提供请求的服务不会产生任何影响。持久化完会将新的 rdb 文件覆盖之前的。
- 触发时机
  - 执行数据写入到临时文件的时间点是可以通过配置来自己确定的，通过配置 redis 在 n 秒内如果超过 m 个 key 被修改这执行一次 RDB 操作。这个操作就类似于在这个时间点来保存一次 Redis 的所有数据，一次快照数据。所有这个持久化方法也通常叫做 snapshots。
  - snapshot 触发的时机，是有“间隔时间”和“变更次数”共同决定，同时符合 2 个条件才会触发 snapshot，否则“变更次数”会被继续累加到下一个“间隔时间”上。snapshot 过程中并不阻塞客户端请求。snapshot 首先将数据写入临时文件，当成功结束后，将临时文件重名为 dump.rdb。
混合持久化
- 混合持久化只发生于 AOF 重写过程。使用了混合持久化，重写后的新 AOF 文件前半段是 RDB 格式的全量数据，后半段是 AOF 格式的增量数据。
- 优点：结合 RDB 和 AOF 的优点, 更快的重写和恢复。
- 缺点：AOF 文件里面的 RDB 部分不再是 AOF 格式，可读性差。

内存淘汰策略

删除过期键的策略（Redis 使用惰性删除和定期删除。）
- 清除策略
  - 定时删除
    - 在设置键的过期时间的同时，创建一个定时器，让定时器在键的过期时间来临时，立即执行对键的删除操作。对内存最友好，对 CPU 时间最不友好。
  - 惰性删除
    - 放任键过期不管，但是每次获取键时，都检査键是否过期，如果过期的话，就删除该键；如果没有过期，就返回该键。对 CPU 时间最优化，对内存最不友好。
  - 定期删除
    - 每隔一段时间，默认 100ms，程序就对数据库进行一次检査，删除里面的过期键。至于要删除多少过期键，以及要检査多少个数据库，则由算法决定。前两种策略的折中，对 CPU 时间和内存的友好程度较平衡。
- Redis 具体实现
  - 比如 Redis-3.0.0 中的 hz 默认值是 10，代表每秒钟调用 10 次后台任务。
    - 典型的方式为，Redis 每秒做 10 次如下的步骤：
      1. 随机测试 100 个设置了过期时间的 key
      2. 删除所有发现的已过期的 key
      3. 若删除的 key 超过 25 个则重复步骤 1
    - 这是一个基于概率的简单算法，基本的假设是抽出的样本能够代表整个 key 空间，redis 持续清理过期的数据直至将要过期的 key 的百分比降到了 25% 以下。这也意味着在任何给定的时刻已经过期但仍占据着内存空间的 key 的量最多为每秒的写操作量除以 4。
不管是定期采样删除还是惰性删除都不是一种完全精准的删除，就还是会存在 key 没有被删除掉的场景，所以就需要内存淘汰策略进行补充。
- 内存淘汰（驱逐）策略
  - noeviction：默认策略，不淘汰任何 key，直接返回错误
  - allkeys-lru：在所有的 key 中，使用 LRU 算法淘汰部分 key
  - allkeys-lfu：在所有的 key 中，使用 LFU 算法淘汰部分 key，该算法于 Redis 4.0 新增
  - allkeys-random：在所有的 key 中，随机淘汰部分 key
  - volatile-lru：在设置了过期时间的 key 中，使用 LRU 算法淘汰部分 key
  - volatile-lfu：在设置了过期时间的 key 中，使用 LFU 算法淘汰部分 key，该算法于 Redis 4.0 新增
  - volatile-random：在设置了过期时间的 key 中，随机淘汰部分 key
  - volatile-ttl：在设置了过期时间的 key 中，挑选 TTL（time to live，剩余时间）短的 key 淘汰

主从、哨兵、集群

主从复制
- 复制的流程（Redis6.0）
  1. 开启主从复制。通常有以下三种方式：
    - 在 slave 直接执行命令：slaveof <masterip> <masterport>
    - 在 slave 配置文件中加入：slaveof <masterip> <masterport>
    - 使用启动命令：--slaveof <masterip> <masterport>
  2. 建立套接字（socket）连接
    - slave 将根据指定的 IP 地址和端口，向 master 发起套接字（socket）连接，master 在接受（accept） slave 的套接字连接之后，为该套接字创建相应的客户端状态，此时连接建立完成。
  3. 发送 PING 命令
    - slave 向 master 发送一个 PING 命令，以检査套接字的读写状态是否正常、 master 能否正常处理命令请求。
  4. 身份验证
    - slave 向 master 发送 AUTH password 命令来进行身份验证。
  5. 发送端口信息
    - 在身份验证通过后后，slave 将向 master 发送自己的监听端口号， master 收到后记录在 slave 所对应的客户端状态的 slave_listening_port 属性中。
  6. 发送 IP 地址
    - 如果配置了 slave_announce_ip，则 slave 向 master 发送 slave_announce_ip 配置的 IP 地址， master 收到后记录在 slave 所对应的客户端状态的 slave_ip 属性。
      - 该配置是用于解决服务器返回内网 IP 时，其他服务器无法访问的情况。可以通过该配置直接指定公网 IP。
  7. 发送 CAPA
    - CAPA 全称是 capabilities，这边表示的是同步复制的能力。slave 会在这一阶段发送 capa 告诉 master 自己具备的（同步）复制能力， master 收到后记录在 slave 所对应的客户端状态的 slave_capa 属性。
  8. 数据同步
    - slave 将向 master 发送 PSYNC 命令， master 收到该命令后判断是进行部分重同步还是完整重同步，然后根据策略进行数据的同步。
  9. 命令传播
    - 当完成了同步之后，就会进入命令传播阶段，这时 master 只要一直将自己执行的写命令发送给 slave ，而 slave 只要一直接收并执行 master 发来的写命令，就可以保证 master 和 slave 一直保持一致了。
- 相关问题
  - Redis 主从复制延迟问题
    - 将主从模式更换为哨兵模式则无需自己去做监控
  - 脑裂导致数据丢失
    - Redis 已经提供了两个配置项来限制主库的请求处理，分别是 min-slaves-to-write 和 min-slaves-max-lag。
      - min-slaves-to-write：这个配置项设置了主库能进行数据同步的最少从库数量；
      - min-slaves-max-lag：这个配置项设置了主从库间进行数据复制时，从库给主库发送 ACK 消息的最大延迟（以秒为单位）。
    - 我们可以把 min-slaves-to-write 和 min-slaves-max-lag 这两个配置项搭配起来使用，分别给它们设置一定的阈值，假设为 N 和 T。这两个配置项组合后的要求是，主库连接的从库中至少有 N 个从库，和主库进行数据复制时的 ACK 消息延迟不能超过 T 秒，否则，主库就不会再接收客户端的请求了。
哨兵
- 哨兵（Sentinel）是 Redis 的高可用性解决方案：由一个或多个 Sentinel 实例组成的 Sentinel 系统可以监视任意多个主服务器，以及这些主服务器属下的所有从服务器。
- Sentinel 可以在被监视的主服务器进入下线状态时，自动将下线主服务器的某个从服务器升级为新的主服务器，然后由新的主服务器代替已下线的主服务器继续处理命令请求。
- 主要功能
  - 客户端可以通过哨兵节点 + masterName 获取主节点信息，在这里哨兵起到的作用就是配置提供者。
  - 哨兵故障检测
    - 检查主观下线状态
      - 在默认情况下，Sentinel 会以每秒一次的频率向所有与它创建了命令连接的实例（包括主服务器、从服务器、其他 Sentinel 在内）发送 PING 命令，并通过实例返回的 PING 命令回复来判断实例是否在线。
      - 如果一个实例在 down-after-miliseconds 毫秒内，连续向 Sentinel 返回无效回复，那么 Sentinel 会修改这个实例所对应的实例结构，在结构的 flags 属性中设置 SRI_S_DOWN 标识，以此来表示这个实例已经进入主观下线状态。
    - 检查客观下线状态
      - 当 Sentinel 将一个主服务器判断为主观下线之后，为了确定这个主服务器是否真的下线了，它会向同样监视这一服务器的其他 Sentinel 进行询问，看它们是否也认为主服务器已经进入了下线状态（可以是主观下线或者客观下线）。
      - 当 Sentinel 从其他 Sentinel 那里接收到足够数量（quorum，可配置）的已下线判断之后，Sentinel 就会将服务器置为客观下线，在 flags 上打上 SRI_O_DOWN 标识，并对主服务器执行故障转移操作。
  - 哨兵故障转移流程
    1. 发起一次选举，选举出领头 Sentinel
    2. 领头 Sentinel 在已下线主服务器的所有从服务器里面，挑选出一个从服务器，并将其升级为新的主服务器。
    3. 领头 Sentinel 将剩余的所有从服务器改为复制新的主服务器。
    4. 领头 Sentinel 更新相关配置信息，当这个旧的主服务器重新上线时，将其设置为新的主服务器的从服务器。
- 架构
集群模式（Cluster）
- 哨兵模式最大的缺点就是所有的数据都放在一台服务器上，无法较好的进行水平扩展。
- 为了解决哨兵模式存在的问题，集群模式应运而生。在高可用上，集群基本是直接复用的哨兵模式的逻辑，并且针对水平扩展进行了优化。
- 集群模式具备的特点
  - 采取去中心化的集群模式，将数据按槽存储分布在多个 Redis 节点上。集群共有 16384 个槽，每个节点负责处理部分槽。
  - 使用 CRC16 算法来计算 key 所属的槽：crc16(key,keylen) & 16383。
  - 所有的 Redis 节点彼此互联，通过 PING-PONG 机制来进行节点间的心跳检测。
    - 交换的数据信息，由消息体和消息头组成。消息体无外乎是一些节点标识啊，IP 啊，端口号啊，发送时间啊。这与本文关系不是太大。我们来看消息头，结构如下
      - 注意看红框的内容，type 表示消息类型。另外，消息头里面有个 myslots 的 char 数组，长度为 16383/8，这其实是一个 bitmap，每一个位代表一个槽，如果该位为 1，表示这个槽是属于这个节点的。
        
        在消息头中，最占空间的是 myslots[CLUSTER_SLOTS/8]。这块的大小是: 16384÷8÷1024=2kb。
        
        那在消息体中，会携带一定数量的其他节点信息用于交换。那这个其他节点的信息，到底是几个节点的信息呢？
        
        约为集群总节点数量的 1/10，至少携带 3 个节点的信息。这里的重点是：节点数量越多，消息体内容越大。
    - 发送规律
      1. 每秒会随机选取 5 个节点，找出最久没有通信的节点发送 ping 消息
      2. 每 100 毫秒（1 秒 10 次）都会扫描本地节点列表，如果发现节点最近一次接受 pong 消息的时间大于 cluster-node-timeout/2 则立刻发送 ping 消息
      - 每秒单节点发出 ping 消息数量为数量=1+10*num，num=（node.pong_received>cluster_node_timeout/2）的数量
  - 分片内采用一主多从保证高可用，并提供复制和故障恢复功能。在实际使用中，通常会将主从分布在不同机房，避免机房出现故障导致整个分片出问题。
  - 客户端与 Redis 节点直连，不需要中间代理层（proxy）。客户端不需要连接集群所有节点，连接集群中任何一个可用节点即可。
- 架构
- 集群选举
  1. 当从节点发现自己正在复制的主节点进入已下线状态时，会发起一次选举：将 currentEpoch（配置纪元）加 1，然后向集群广播一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST 消息，要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票。
  2. 其他节点收到消息后，会判断是否要给发送消息的节点投票，判断流程如下：
    1. 当前节点是 slave，或者当前节点是 master，但是不负责处理槽，则当前节点没有投票权，直接返回。
    2. 请求节点的 currentEpoch 小于当前节点的 currentEpoch，校验失败返回。因为发送者的状态与当前集群状态不一致，可能是长时间下线的节点刚刚上线，这种情况下，直接返回即可。
    3. 当前节点在该 currentEpoch 已经投过票，校验失败返回。
    4. 请求节点是 master，校验失败返回。
    5. 请求节点的 master 为空，校验失败返回。
    6. 请求节点的 master 没有故障，并且不是手动故障转移，校验失败返回。因为手动故障转移是可以在 master 正常的情况下直接发起的。
    7. 上一次为该 master 的投票时间，在 cluster_node_timeout 的 2 倍范围内，校验失败返回。这个用于使获胜从节点有时间将其成为新主节点的消息通知给其他从节点，从而避免另一个从节点发起新一轮选举又进行一次没必要的故障转移
    8. 请求节点宣称要负责的槽位，是否比之前负责这些槽位的节点，具有相等或更大的 configEpoch，如果不是，校验失败返回。
    9. 如果通过以上所有校验，那么主节点将向要求投票的从节点返回一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，表示这个主节点支持从节点成为新的主节点。
  3. 每个参与选举的从节点都会接收 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，并根据自己收到了多少条这种消息来统计自己获得了多少个主节点的支持。
  4. 如果集群里有 N 个具有投票权的主节点，那么当一个从节点收集到大于等于 N/2+1 张支持票时，这个从节点就会当选为新的主节点。因为在每一个配置纪元里面，每个具有投票权的主节点只能投一次票，所以如果有 N个主节点进行投票，那么具有大于等于 N/2+1 张支持票的从节点只会有一个，这确保了新的主节点只会有一个。
  5. 如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止。
  - 这个选举新主节点的方法和选举领头 Sentinel 的方法非常相似，因为两者都是基于 Raft 算法的领头选举（leader election）方法来实现的。
- 相关问题
  - 如何保证集群在线扩容的安全性？（Redis 集群要增加分片，槽的迁移怎么保证无损）
    - Redis 使用了 ASK 错误来保证在线扩容的安全性。
    - 在槽的迁移过程中若有客户端访问，依旧先访问源节点，源节点会先在自己的数据库里面査找指定的键，如果找到的话，就直接执行客户端发送的命令。
    - 如果没找到，说明该键可能已经被迁移到目标节点了，源节点将向客户端返回一个 ASK 错误，该错误会指引客户端转向正在导入槽的目标节点，并再次发送之前想要执行的命令，从而获取到结果。
      - ASK 错误
        
        在进行重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现这样一种情况：属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点里面。
        
        当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据库键恰好就属于正在被迁移的槽时。源节点会先在自己的数据库里面査找指定的键，如果找到的话，就直接执行客户端发送的命令。
        
        否则，这个键有可能已经被迁移到了目标节点，源节点将向客户端返回一个 ASK 错误，指引客户端转向正在导入槽的目标节点，并再次发送之前想要执行的命令，从而获取到结果。
  - 为什么 Redis 集群有 16384 个槽？
    1. 如果槽位为 65536，发送心跳信息的消息头达 8k，发送的心跳包过于庞大。
      - 在消息头中，最占空间的是 myslots[CLUSTER_SLOTS/8]。当槽位为 65536 时，这块的大小是: 65536÷8÷1024=8kb 因为每秒钟，redis 节点需要发送一定数量的 ping 消息作为心跳包，如果槽位为 65536，这个 ping 消息的消息头太大了，浪费带宽。
    2. Redis 的集群主节点数量基本不可能超过 1000 个。
      - 集群节点越多，心跳包的消息体内携带的数据越多。如果节点过 1000 个，也会导致网络拥堵。因此 Redis 作者，不建议 redis cluster 节点数量超过 1000 个。那么，对于节点数在 1000 以内的 redis cluster 集群，16384 个槽位够用了。没有必要拓展到 65536 个。
    3. 槽位越小，节点少的情况下，压缩比高
      - Redis 主节点的配置信息中，它所负责的哈希槽是通过一张 bitmap 的形式来保存的，在传输过程中，会对 bitmap 进行压缩，但是如果 bitmap 的填充率slots / N很高的话（N 表示节点数），bitmap 的压缩率就很低。如果节点数很少，而哈希槽数量很多的话，bitmap 的压缩率就很低。
        事务
Redis 的事务并不推荐在实际中使用，如果要使用事务，推荐使用 Lua 脚本，Redis 会保证一个 Lua 脚本里的所有命令的原子性。

常用方式

缓存
- 可能遇到的问题：
  - 缓存雪崩
    - 同一时刻大量缓存失效
    - 处理方法
      - 缓存数据增加过期标记
      - 设置不同的缓存失效时间
      - 双层缓存策略 C1 为短期，C2 为⻓期
      - 定时更新策略
  - 缓存穿透
    - 频繁请求查询系统中不存在的数据导致
    - 处理方法
      - 对请求参数进行校验，不合理直接返回
      - 查询不到的数据也放到缓存，value 为空，如 set -999 “”
      - 使用布隆过滤器，快速判断 key 是否在数据库中存在，不存在直接返回
        
        布隆过滤器
        
        布隆过滤器的特点是判断不存在的，则一定不存在；判断存在的，大概率存在，但也有小概率不存在。并且这个概率是可控的，我们可以让这个概率变小或者变高，取决于用户本身的需求。
  - 缓存击穿
    - 设置了过期时间的 key，承载着高并发，是一种热点数据。从这个 key 过期到重新从 MySQL 加载数据放到缓存的一段时间，大量的请求有可能把数据库打死。缓存雪崩是指大量缓存失效，缓存击穿是指热点数据的缓存失效
    - 处理方法
      - 设置 key 永远不过期，或者快过期时，通过另一个异步线程重新设置 key
      - 当从缓存拿到的数据为 null，重新从数据库加载数据的过程上锁
分布式锁
- 涉及操作
  - set + lua 脚本
- 看门狗策略
- 存在的问题
  - 步骤
    1. 线程 1 首先获取锁成功，将键值对写入 redis 的 master 节点
    2. 在 redis 将该键值对同步到 slave 节点之前，master 发生了故障
    3. redis 触发故障转移，其中一个 slave 升级为新的 master
    4. 此时新的 master 并不包含线程 1 写入的键值对，因此线程2尝试获取锁也可以成功拿到锁
    5. 此时相当于有两个线程获取到了锁，可能会导致各种预期之外的情况发生，例如最常见的脏数据
  - 解决方法和思路
    - Zookeeper 实现的分布式锁
    - Redlock
      - 方案思路
        
        假设我们有 N 个 Redis 主节点，例如 N = 5，这些节点是完全独立的，我们不使用复制或任何其他隐式协调系统，为了取到锁，客户端应该执行以下操作：
        
        获取当前时间，以毫秒为单位。
        
        依次尝试从 5 个实例，使用相同的 key 和随机值（例如UUID）获取锁。当向 Redis 请求获取锁时，客户端应该设置一个超时时间，这个超时时间应该小于锁的失效时间。例如你的锁自动失效时间为10秒，则超时时间应该在 5-50 毫秒之间。这样可以防止客户端在试图与一个宕机的 Redis 节点对话时长时间处于阻塞状态。如果一个实例不可用，客户端应该尽快尝试去另外一个 Redis 实例请求获取锁。
        
        客户端通过当前时间减去步骤 1 记录的时间来计算获取锁使用的时间。当且仅当从大多数（N/2+1，这里是3个节点）的 Redis 节点都取到锁，并且获取锁使用的时间小于锁失效时间时，锁才算获取成功。
        
        如果取到了锁，其真正有效时间等于初始有效时间减去获取锁所使用的时间（步骤3计算的结果）。
        
        如果由于某些原因未能获得锁（无法在至少 N/2+1 个 Redis 实例获取锁、或获取锁的时间超过了有效时间），客户端应该在所有的 Redis 实例上进行解锁（即便某些 Redis 实例根本就没有加锁成功，防止某些节点获取到锁但是客户端没有得到响应而导致接下来的一段时间不能被重新获取锁）。
      - 存在的问题
        
        该方案的成本似乎有点高，需要使用5个实例；
        
        严重依赖系统时钟。如果线程 1 从 3 个实例获取到了锁，但是这 3 个实例中的某个实例的系统时间走的稍微快一点，则它持有的锁会提前过期被释放，当他释放后，此时又有 3 个实例是空闲的，则线程 2 也可以获取到锁，则可能出现两个线程同时持有锁了。
        
        如果线程 1 从 3 个实例获取到了锁，但是万一其中有 1 台重启了，则此时又有 3 个实例是空闲的，则线程 2 也可以获取到锁，此时又出现两个线程同时持有锁了。
排行榜
- 涉及操作
  - zset
计数
- 涉及操作
  - incrby
消息队列
- 涉及操作
  - stream
地理位置
- 涉及操作
  - geo
访客统计
- 涉及操作
  - hyperloglog

性能优化

缩短键值对的存储长度
- 键值对的长度是和性能成反比
使用 lazy free 特性
设置键值的过期时间
禁用长耗时的查询命令
- Redis 绝大多数读写命令的时间复杂度都在 $O(1)$ 到 $O(N)$ 之间
- 要避免 $O(N)$ 命令对 Redis造成影响，可以从以下几个方面入手改造：
  - 禁止使用 keys 命令；
  - 避免一次查询所有的成员，要使用 scan 命令进行分批的、游标式的遍历；
  - 通过机制严格控制 Hash、Set、Sorted Set 等结构的数据大小；
  - 将排序、并集、交集等操作放在客户端执行，以减少 Redis 服务器运行压力；
  - 删除一个大数据的时候，可能会需要很长时间，所以建议用异步删除的方式 unlink，它会启动一个新的线程来删除目标数据，而不阻塞 Redis 的主线程。
- 使用 slowlog 优化耗时命令
- 使用 Pipeline 批量操作数据
  - Pipeline（管道技术）是客户端提供的一种批处理技术，用于一次处理多个 Redis 命令，从而提高整个交互的性能。
- 避免大量数据同时失效
  - 如果在大型系统中有大量缓存在同一时间同时过期，那么会导致 Redis 循环多次持续扫描过期字典，直到过期字典中过期键值被删除的比较稀疏为止，而在整个执行过程中会导致 Redis 的读写出现明显的卡顿，卡顿的另一种原因是内存管理器需要频繁回收内存页，因此也会消耗一定的 CPU。
  - 为了避免这种卡顿现象的产生，我们需要预防大量的缓存在同一时刻一起过期，最简单的解决方案就是在过期时间的基础上添加一个指定范围的随机数。
- 客户端使用优化
  - 在客户端的使用上我们除了要尽量使用 Pipeline 的技术外，还需要注意尽量使用 Redis 连接池，而不是频繁创建销毁 Redis 连接，这样就可以减少网络传输次数和减少了非必要调用指令。
- 限制 Redis 内存大小
- 使用物理机而非虚拟机
- 检查数据持久化策略
- 禁用 THP 特性
  - Linux kernel 在 2.6.38 内核增加了 Transparent Huge Pages（THP）特性，支持大内存页 2MB 分配，默认开启。
  - 当开启了 THP 时，fork 的速度会变慢，fork 之后每个内存页从原来 4KB 变为 2MB，会大幅增加重写期间父进程内存消耗。同时每次写命令引起的复制内存页单位放大了 512 倍，会拖慢写操作的执行时间，导致大量写操作慢查询。
- 使用分布式架构来增加读写速度
  - 主从同步
  - 哨兵模式
  - Redis Cluster 集群

数据结构

基本

持久化

内存淘汰策略

主从、哨兵、集群

事务

常用方式

性能优化

相关问题