redis设计与实现

发表于 | 分类于 |

数据结构与对象

SDS

  • 数据结构

image-20220327155838151

"

  • 相较于原生c语言字符串的区别？

    ​ 常数复杂度获取字符串长度
    ​ 杜绝缓冲区溢出
    ​ 减少修改字符串时带来的内存重分配次数
    ​ 空间预分配
    ​ 惰性空间释放
    ​ 二进制安全

链表

  • 数据结构

    ​ image-20220327160246557

    "

字典

  • 数据结构

    <img src="images/image-20220327160401494.png" alt="image-20220327160401494" style="zoom: 25%;" />

    ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
    除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

  • hash算法

    MurmurHash2算法

  • 冲突解决

    链地址法，可参考java hashmap的实现

  • rehash的过程

    扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下：
    1）为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）：

    ❑如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2 n（2的n次方幂）；
❑如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2 n。

    2）将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
    3）当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

  • 什么时候触发rehash

    • 扩展

      1）服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。

      2）服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。

    • 收缩
      当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作

  • 渐进式rehash步骤

    为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1]。

    1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。

    2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。

    3）在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。

    4）随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

    渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

  • 怎么在rehash过程中的增删改查？

    因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类。

    另外，在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

跳跃表

​ 有序集合底层实现
​ java 代码实现：https://juejin.cn/post/6844903847521976327
​ 数据结构

​ image-20220327200520224

"

整数集合

​ 是集合键的实现之一
​ 数据结构

image-20220327200658260

"

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现

  • 数据结构

    image-20220327200900372

    "

对象系统

类型与编码

  • 结构体

    image-20220327203439662

    "

  • 类型

    image-20220327203538383

    "

  • 编码

    image-20220327203639653

    "

内存回收

因为C语言并不具备自动内存回收功能，所以Redis在自己的对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。

image-20220327204211701

"

对象共享

image-20220327204051657

"

在Redis中，让多个键共享同一个值对象需要执行以下两个步骤：
1）将数据库键的值指针指向一个现有的值对象；
2）将被共享的值对象的引用计数增一。
Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象
这些共享对象不单单只有字符串键可以使用，那些在数据结构中嵌套了字符串对象的对象（linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象，以及zset编码的有序集合对象)都可以使用这些共享对象。
Redis只对包含整数值的字符串对象进行共享

空转时长

redisObject结构包含的最后一个属性为lru属性，该属性记录了对象最后一次被命令程序访问的时间

单机数据库

数据库

  • 数据结构

    <img src="images/image-20220327212351861.png" alt="image-20220327212351861" style="zoom:33%;" />

  • 键空间

    redisDb结构的dict字典保存了数据库中的所有键值对，我们将这个字典称为键空间（key space）

    image-20220327212614427

    "

  • 读写键空间时的维护操作

    当使用Redis命令对数据库进行读写时，服务器不仅会对键空间执行指定的读写操作，还会执行一些额外的维护操作

    1.在读取一个键之后，服务器会更新键的LRU（最后一次使用）时间，这个值可以用于计算键的闲置时间，使用OBJECT idletime命令可以查看键key的闲置时间。

    2.如果服务器在读取一个键时发现该键已经过期，那么服务器会先删除这个过期键，然后才执行余下的其他操作，本章稍后对过期键的讨论会详细说明这一点。

    3.如果有客户端使用WATCH命令监视了某个键，那么服务器在对被监视的键进行修改之后，会将这个键标记为脏（dirty），从而让事务程序注意到这个键已经被修改过，第19章会详细说明这一点。

    4.服务器每次修改一个键之后，都会对脏（dirty）键计数器的值增1，这个计数器会触发服务器的持久化以及复制操作，第10章、第11章和第15章都会说到这一点。

键的生存时间或过期时间

过期键的保存

redisDb结构的expires字典保存了数据库中所有键的过期时间，我们称这个字典为过期字典

过期键删除策略：惰性删除+定期删除

  • 惰性删除
    过期键的惰性删除策略由db.c/expireIfNeeded函数实现，所有读写数据库的Redis命令在执行之前都会调用expireIfNeeded函数对输入键进行检查

    image-20220327232346093

    "

  • 定期删除

    每当Redis的服务器周期性操作redis.c/serverCron函数执行时，activeExpireCycle函数就会被调用，它在规定的时间内，分多次遍历服务器中的各个数据库，从数据库的expires字典中随机检查一部分键的过期时间，并删除其中的过期键。

AOF，RDB和复制功能对过期键的处理

  • RDB

    在执行SAVE命令或者BGSAVE命令创建一个新的RDB文件时，程序会对数据库中的键进行检查，已过期的键不会被保存到新创建的RDB文件中。

    • 载入rdb文件
      1. 如果服务器以主服务器模式运行，那么在载入RDB文件时，程序会对文件中保存的键进行检查，未过期的键会被载入到数据库中，而过期键则会被忽略，所以过期键对载入RDB文件的主服务器不会造成影响。
      2. 如果服务器以从服务器模式运行，那么在载入RDB文件时，文件中保存的所有键，不论是否过期，都会被载入到数据库中。不过，因为主从服务器在进行数据同步的时候，从服务器的数据库就会被清空，所以一般来讲，过期键对载入RDB文件的从服务器也不会造成影响

  • AOF
    当服务器以AOF持久化模式运行时，如果数据库中的某个键已经过期，但它还没有被惰性删除或者定期删除，那么AOF文件不会因为这个过期键而产生任何影响。当过期键被惰性删除或者定期删除之后，程序会向AOF文件追加（append）一条DEL命令，来显式地记录该键已被删除。
    和生成RDB文件时类似，在执行AOF重写的过程中，程序会对数据库中的键进行检查，已过期的键不会被保存到重写后的AOF文件中。

  • 复制

    主服务器在删除一个过期键之后，会显式地向所有从服务器发送一个DEL命令，告知从服务器删除这个过期键。❑从服务器在执行客户端发送的读命令时，即使碰到过期键也不会将过期键删除，而是继续像处理未过期的键一样来处理过期键。❑从服务器只有在接到主服务器发来的DEL命令之后，才会删除过期键。

RDB

创建与载入

  • 持久化
    RDB持久化功能所生成的RDB文件是一个经过压缩的二进制文件，通过该文件可以还原生成RDB文件时的数据库状态
  • 创建命令
    • SAVE，BGSAVE
      当执行save命令时，redis服务器会被阻塞，所有请求命令都会被拒绝
      bgsave命令由子进程执行，不阻塞服务器
      save,bgsave,bgrewriteaof不能同时执行
  • 载入流程
    载入rdb文件期间，服务器会一致处于阻塞状态
  • 自动间隔性保存
    Redis允许用户通过设置服务器配置的save选项，让服务器每隔一段时间自动执行一次BGSAVE命令。
    • 计数
      1.dirty计数器记录距离上一次成功执行SAVE命令或者BGSAVE命令之后，服务器对数据库状态（服务器中的所有数据库）进行了多少次修改（包括写入、删除、更新等操作）。
      2.lastsave属性是一个UNIX时间戳，记录了服务器上一次成功执行SAVE命令或者BGSAVE命令的时间。
    • 检查保存条件是否满足
      每次执行完save，dirty就会被清0
      Redis的服务器周期性操作函数serverCron默认每隔100毫秒就会执行一次，该函数用于对正在运行的服务器进行维护，它的其中一项工作就是检查save选项所设置的保存条件是否已经满足，如果满足的话，就执行BGSAVE命令。

AOF

  • AOF与RDB区别
    与RDB持久化通过保存数据库中的键值对来记录数据库状态不同，AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态的

持久化的实现

  • 命令追加
    当服务器执行完命令后，会把协议内容添加到aof_buf缓冲区的末尾

  • 文件写入与同步
    flushAppendOnlyFile函数的行为由服务器配置的appendfsync选项的值来决定，appendfsync选项的默认值为everysec

  • 写入与同步的区别
    写入是指写入内存缓冲区，同步是指同缓冲区写入到磁盘

  • 载入与数据还原

    image-20220328145953801

    "

AOF重写

为了解决aof文件体积膨胀的问题

创建一个新的AOF文件来替代现有的AOF文件，新旧两个AOF文件所保存的数据库状态相同，但新AOF文件不会包含任何浪费空间的冗余命令，所以新AOF文件的体积通常会比旧AOF文件的体积要小得多

实现原理

首先从数据库中读取键现在的值，然后用一条命令去记录键值对，代替之前记录这个键值对的多条命令，这就是AOF重写功能的实现原理。（不需要分析现有的AOF文件）
在实际中，为了避免在执行命令时造成客户端输入缓冲区溢出，重写程序在处理列表、哈希表、集合、有序集合这四种可能会带有多个元素的键时，会先检查键所包含的元素数量，如果元素的数量超过了redis.h/REDIS_AOF_REWRITE_ITEMS_PER_CMD常量的值，那么重写程序将使用多条命令来记录键的值，而不单单使用一条命令。

后台重写

子进程进行AOF重写期间，服务器进程（父进程）可以继续处理命令请求

服务器进程和重写子进程同时运行，怎么保证数据一致？

image-20220328151858653

"

在子进程执行AOF重写期间，服务器进程需要执行以下三个工作：
​ 1）执行客户端发来的命令。
​ 2）将执行后的写命令追加到AOF缓冲区。
​ 3）将执行后的写命令追加到AOF重写缓冲区。
这样一来可以保证：

  1. AOF缓冲区的内容会定期被写入和同步到AOF文件，对现有AOF文件的处理工作会如常进行。

  2. 从创建子进程开始，服务器执行的所有写命令都会被记录到AOF重写缓冲区里面。

    当子进程完成AOF重写工作之后，它会向父进程发送一个信号，父进程在接到该信号之后，会调用一个信号处理函数，并执行以下工作：

    1）将AOF重写缓冲区中的所有内容写入到新AOF文件中，这时新AOF文件所保存的数据库状态将和服务器当前的数据库状态一致。
    2）对新的AOF文件进行改名，原子地（atomic）覆盖现有的AOF文件，完成新旧两个AOF文件的替换。

服务器

还原数据库状态

  1. 载入RDB文件或者AOF文件
  2. 如果启用了AOF持久化功能，使用AOF文件恢复数据库状态
  3. 如果没启用，使用RDB文件恢复

多机数据库

复制

命令：slaveof master_ip master_port

旧版功能的实现

2大步骤：同步（sync）和命令传播（command propagate）两个操作

  1. 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。
  2. 命令传播操作则用于在主服务器的数据库状态被修改， 导致主从服务器的数据库状态出现不一致时， 让主从服务器的数据库重新回到一致状态。

image-20220328181413466

"

同步

image-20220328165530576

"

  • 触发时机
    当客户端向从服务器发送 SLAVEOF 命令， 要求从服务器复制主服务器时

  • 具体步骤

    1. 从服务器向主服务器发送 SYNC 命令。
    2. 收到 SYNC 命令的主服务器执行 BGSAVE 命令， 在后台生成一个 RDB 文件， 并使用一个缓冲区记录从现在开始执行的所有写命令。
    3. 当主服务器的 BGSAVE 命令执行完毕时， 主服务器会将 BGSAVE 命令生成的 RDB 文件发送给从服务器， 从服务器接收并载入这个 RDB 文件， 将自己的数据库状态更新至主服务器执行 BGSAVE 命令时的数据库状态。
    4. 主服务器将记录在缓冲区里面的所有写命令发送给从服务器， 从服务器执行这些写命令， 将自己的数据库状态更新至主服务器数据库当前所处的状态。

命令传播

  • 为什么要命令传播
    每当主服务器执行客户端发送的写命令时， 主服务器的数据库就有可能会被修改， 并导致主从服务器状态不再一致

  • 怎么做
    主服务器会将自己执行的写命令 —— 也即是造成主从服务器不一致的那条写命令 —— 发送给从服务器执行， 当从服务器执行了相同的写命令之后， 主从服务器将再次回到一致状态。

缺陷

  • 断线后复制效率低
    断线恢复连接后：从库向主库发送SYNC命令，执行同步操作

新版功能的实现

  • 相对老版本的优化点

    使用PSYNC代替SYNC，PSYNC在断线后复制时，可以仅同步断线后主服务器执行的命令

PSYNC

  • PSYNC命令具有完整重同步（full resynchronization）和部分重同步（partial resynchronization）两种模式：\

    • 其中完整重同步用于处理初次复制情况：完整重同步的执行步骤和SYNC命令的执行步骤基本一样，它们都是通过让主服务器创建并发送RDB文件，以及向从服务器发送保存在缓冲区里面的写命令来进行同步。
    • 而部分重同步则用于处理断线后重复制情况：当从服务器在断线后重新连接主服务器时，如果条件允许，主服务器可以将主从服务器连接断开期间执行的写命令发送给从服务器，从服务器只要接收并执行这些写命令，就可以将数据库更新至主服务器当前所处的状态。

  • 部分重同步功能由以下三个部分构成：

    1. 主服务器的复制偏移量（replication offset）和从服务器的复制偏移量。

    2. 主服务器的复制积压缓冲区（replication backlog）。

    3. 服务器的运行ID（run ID）。

复制偏移量

  • 执行复制的双方——主服务器和从服务器会分别维护一个复制偏移量：

    1.主服务器每次向从服务器传播N个字节的数据时，就将自己的复制偏移量的值加上N。
2.从服务器每次收到主服务器传播来的N个字节的数据时，就将自己的复制偏移量的值加上N。

  • 通过对比主从服务器的复制偏移量，程序可以很容易地知道主从服务器是否处于一致状态：

    1. 如果主从服务器处于一致状态，那么主从服务器两者的偏移量总是相同的。

    2. 相反，如果主从服务器两者的偏移量并不相同，那么说明主从服务器并未处于一致状态

复制积压缓冲区

  • 主服务器维护的一个固定长度，先进先出的队列，默认大小1M

  • 同步记录时，也会记录在复制积压区

    image-20220328171446304

    "

    image-20220328171505476

    "

  • 如何利用积压区进行断线后恢复数据
    当从服务器重新连上主服务器时，从服务器会通过PSYNC命令将自己的复制偏移量offset发送给主服务器，主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作：

    1. 如果offset偏移量之后的数据（也即是偏移量offset+1开始的数据）仍然存在于复制积压缓冲区里面，那么主服务器将对从服务器执行部分重同步操作。

    2. 相反，如果offset偏移量之后的数据已经不存在于复制积压缓冲区，那么主服务器将对从服务器执行完整重同步操作。

服务器运行ID

除了复制偏移量和复制积压缓冲区之外，实现部分重同步还需要用到服务器运行ID（run ID）：

  1. 每个Redis服务器，不论主服务器还是从服务，都会有自己的运行ID。

  2. 运行ID在服务器启动时自动生成，由40个随机的十六进制字符组成，例如53b9b28df8042fdc9ab5e3fcbbbabff1d5dce2b3。

怎么用

当从服务器对主服务器进行初次复制时，主服务器会将自己的运行ID传送给从服务器，而从服务器则会将这个运行ID保存起来。
当从服务器断线并重新连上一个主服务器时，从服务器将向当前连接的主服务器发送之前保存的运行ID：
1.如果从服务器保存的运行ID和当前连接的主服务器的运行ID相同，那么说明从服务器断线之前复制的就是当前连接的这个主服务器，主服务器可以继续尝试执行部分重同步操作。
2.相反地，如果从服务器保存的运行ID和当前连接的主服务器的运行ID并不相同，那么说明从服务器断线之前复制的主服务器并不是当前连接的这个主服务器，主服务器将对从服务器执行完整重同步操作。

复制的实现流程

  1. 设置主服务器的地址和端口 slaveof <master_ip> <master_port>

  2. 建立套接字
    如果从服务器创建的套接字能成功连接（connect）到主服务器，那么从服务器将为这个套接字关联一个专门用于处理复制工作的文件事件处理器，这个处理器将负责执行后续的复制工作

  3. 发送PING命令

  4. 身份验证

  5. 发送端口信息
    主服务器把端口信息记录在从服务器对应的客户端状态的slave_listening_port属性中
    从服务器也是一种客户端
    slave_listening_port属性的唯一作用是：执行INFO replication命令时打印出从服务器的端口号

  6. 同步

  7. 命令传播

心跳检测

  • 怎么心跳检测
    命令传播阶段，从服务器默认每秒向主服务器发送命令：REPLCONF ACK <replication_offset>

  • 作用是什么

    • 辅助实现min-slaves

    • 检测命令丢失
      如果因为网络故障，主服务器传播给从服务器的写命令在半路丢失，那么当从服务器向主服务器发送REPLCONF ACK命令时，
      主服务器将发觉从服务器当前的复制偏移量少于自己的复制偏移量，然后主服务器就会根据从服务器提交的复制偏移量，
      在复制积压缓冲区里面找到从服务器缺少的数据，并将这些数据重新发送给从服务器。

sentinel

  • 是什么
    Sentinel（哨岗、哨兵）是Redis的高可用性（high availability）解决方案：由一个或多个Sentinel实例（instance）组成的Sentinel系统（system）可以监视任意多个主服务器，以及这些主服务器属下的所有从服务器，并在被监视的主服务器进入下线状态时，自动将下线主服务器属下的某个从服务器升级为新的主服务器，然后由新的主服务器代替已下线的主服务器继续处理命令请求。

故障转移的整个过程

启动并初始化sentinel

1）初始化服务器。

2）将普通Redis服务器使用的代码替换成Sentinel专用代码。

3）初始化Sentinel状态。

4）根据给定的配置文件，初始化Sentinel的监视主服务器列表。

5）创建连向主服务器的网络连接。

Sentinel本质上只是一个运行在特殊模式下的Redis服务器

  • 数据结构

    image-20220328204312385

    "

    image-20220328204341504

    "

  • 创建与主服务器的连接
    Sentinel会创建两个连向主服务器的异步网络连接：

    • 一个是命令连接，这个连接专门用于向主服务器发送命令，并接收命令回复。

    • 另一个是订阅连接，这个连接专门用于订阅主服务器的sentinel:hello频道。
      为什么是2个

      image-20220328205719679

      "

获取主服务器的信息

  • Sentinel默认会以每十秒一次的频率，通过命令连接向被监视的主服务器发送INFO命令，并通过分析INFO命令的回复来获取主服务器的当前信息。

  • 通过分析主服务器返回的INFO命令回复，Sentinel可以获取以下两方面的信息：

    • 一方面是关于主服务器本身的信息，包括run_id域记录的服务器运行ID，以及role域记录的服务器角色；
    • 另一方面是关于主服务器属下所有从服务器的信息，每个从服务器都由一个”slave”字符串开头的行记录，每行的ip=域记录了从服务器的IP地址，而port=域则记录了从服务器的端口号。根据这些IP地址和端口号
      Sentinel无须用户提供从服务器的地址信息，就可以自动发现从服务器

    image-20220328210037050

    "

获取从服务器的信息

  • sentinel发现从服务器时，会建立命令连接和订阅连接

    image-20220328210311702

    "

  • 在创建命令连接之后，Sentinel在默认情况下，会以每十秒一次的频率通过命令连接向从服务器发送INFO命令

向主服务器和从服务器发消息

Sentinel会以每两秒一次的频率，通过命令连接向所有被监视的主服务器和从服务器发送命令

image-20220328210346132

"

以s_开头的参数记录的是Sentinel本身的信息，m_开头的参数记录的则是主服务器的信息

接收来自主服务器和从服务器的频道信息

  1. 对于每个与Sentinel连接的服务器，Sentinel既通过命令连接向服务器的sentinel:hello频道发送信息，又通过订阅连接从服务器的sentinel:hello频道接收信息

  2. 对于监视同一个服务器的多个Sentinel来说，一个Sentinel发送的信息会被其他Sentinel接收到，这些信息会被用于更新其他Sentinel对发送信息Sentinel的认知，也会被用于更新其他Sentinel对被监视服务器的认知。

  3. 更新sentinels字典
    Sentinel为主服务器创建的实例结构中的sentinels字典保存了除Sentinel本身之外，所有同样监视这个主服务器的其他Sentinel的资料

    image-20220328211612900

    "

  4. 创建连向其他Sentinel的命令连接

    • 当Sentinel通过频道信息发现一个新的Sentinel时，它不仅会为新Sentinel在sentinels字典中创建相应的实例结构，还会创建一个连向新Sentinel的命令连接，而新Sentinel也同样会创建连向这个Sentinel的命令连接
    • Sentinel之间不会创建订阅连接

主观下线

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

  2. 回复

    • 有效回复：实例返回+PONG、-LOADING、-MASTERDOWN三种回复的其中一种。

    • 无效回复：实例返回除+PONG、-LOADING、-MASTERDOWN三种回复之外的其他回复，或者在指定时限内没有返回任何回复

    • Sentinel配置文件中的down-after-milliseconds选项指定了Sentinel判断实例进入主观下线所需的时间长度：如果一个实例在down-after-milliseconds毫秒内，连续向Sentinel返回无效回复，那么Sentinel会修改这个实例所对应的实例结构，在结构的flags属性中打开SRI_S_DOWN标识，以此来表示这个实例已经进入主观下线状态

    • 多个Sentinel设置的主观下线时长可能不同

检查客观下线状态

  1. 当Sentinel将一个主服务器判断为主观下线之后，为了确认这个主服务器是否真的下线了，它会向同样监视这一主服务器的其他Sentinel进行询问，看它们是否也认为主服务器已经进入了下线状态（可以是主观下线或者客观下线）。当Sentinel从其他Sentinel那里接收到足够数量的已下线判断之后，Sentinel就会将从服务器判定为客观下线，并对主服务器执行故障转移操作。

  2. 命令询问其他Sentinel是否同意主服务器已下线

  3. 根据其他Sentinel发回的SENTINEL is-master-down-by-addr命令回复，Sentinel将统计其他Sentinel同意主服务器已下线的数量，当这一数量达到配置指定的判断客观下线所需的数量时，Sentinel会将主服务器实例结构flags属性的SRI_O_DOWN标识打开，表示主服务器已经进入客观下线状态

选举领头Sentinel

当一个主服务器被判断为客观下线时，监视这个下线主服务器的各个Sentinel会进行协商，选举出一个领头Sentinel，并由领头Sentinel对下线主服务器执行故障转移操作。
选举算法是对Raft算法的领头选举方法的实现

故障转移

  • 3个步骤
    1）在已下线主服务器属下的所有从服务器里面，挑选出一个从服务器，并将其转换为主服务器。
    2）让已下线主服务器属下的所有从服务器改为复制新的主服务器。
    3）将已下线主服务器设置为新的主服务器的从服务器，当这个旧的主服务器重新上线时，它就会成为新的主服务器的从服务器。

  • 怎么选举新的主服务器
    挑选出一个状态良好、数据完整的从服务器，然后向这个从服务器发送SLAVEOF no one命令，将这个从服务器转换为主服务器。

    如果有多个具有相同最高优先级的从服务器，那么领头Sentinel将按照从服务器的复制偏移量，对具有相同最高优先级的所有从服务器进行排序，并选出其中偏移量最大的从服务器（复制偏移量最大的从服务器就是保存着最新数据的从服务器）。最后，如果有多个优先级最高、复制偏移量最大的从服务器，那么领头Sentinel将按照运行ID对这些从服务器进行排序，并选出其中运行ID最小的从服务器。

集群

Redis集群是Redis提供的分布式数据库方案，集群通过分片（sharding）来进行数据共享，并提供复制和故障转移功能。

节点

  • 怎么加入集群

    image-20220328222139682

    "

    向一个节点node发送CLUSTER MEET命令，可以让node节点与ip和port所指定的节点进行握手（handshake），当握手成功时，node节点就会将ip和port所指定的节点添加到node节点当前所在的集群中

  • 节点启动
    一个节点就是一个运行在集群模式下的Redis服务器，Redis服务器在启动时会根据cluster-enabled配置选项是否为yes来决定是否开启服务器的集群模式

    image-20220328222454024

    "

  • 集群数据结构

    每个节点都会使用一个clusterNode结构来记录自己的状态，并为集群中的所有其他节点（包括主节点和从节点)都创建一个相应的clusterNode结构，以此来记录其他节点的状态
    每个节点都保存着一个clusterState结构，这个结构记录了在当前节点的视角下，集群目前所处的状态
    image-20220328222804037

    "

  • CLUSTER MEET命令的实现

    image-20220328222848607

    "

槽指派

  • Redis集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为16384个槽（slot），数据库中的每个键都属于这16384个槽的其中一个，集群中的每个节点可以处理0个或最多16384个槽。

  • cluster addslots
    通过向节点发送CLUSTER ADDSLOTS命令，我们可以将一个或多个槽指派（assign）给节点负责

  • 记录节点的槽指派信息

    1. clusterNode结构的slots属性和numslot属性记录了节点负责处理哪些槽

    image-20220328223145203

    "

    1. image-20220328223236704

      "

      1表示负责处理

  • 传播节点的槽指派信息
    节点也会将自己的slots数组通过消息发送给集群中的其他节点，以此来告知其他节点自己目前负责处理哪些槽。
    因为集群中的每个节点都会将自己的slots数组通过消息发送给集群中的其他节点，并且每个接收到slots数组的节点都会将数组保存到相应节点的clusterNode结构里面，因此，集群中的每个节点都会知道数据库中的16384个槽分别被指派给了集群中的哪些节点。

  • 记录集群所有槽的指派信息

    clusterState结构中的slots数组记录了集群中所有16384个槽的指派信息

    image-20220328223529391

    "

在集群中执行命令

image-20220328223919377

"

  1. 计算键属于哪个槽

    image-20220328224004552

    "

  2. 判断槽是否由当前节点负责处理
    当节点计算出键所属的槽i之后，节点就会检查自己在clusterState.slots数组中的项i，判断键所在的槽是否由自己负责

  3. MOVED错误
    当节点发现键所在的槽并非由自己负责处理的时候，节点就会向客户端返回一个MOVED错误，指引客户端转向至正在负责槽的节点。

重新分片

  1. 重新分片操作可以在线（online）进行，在重新分片的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求。

  2. 槽迁移的过程

    image-20220328230826290

    "

ASK错误

  • 属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点里面。

    image-20220330222326638

    "

  • CLUSTER SETSLOT IMPORTING命令的实现

    clusterState结构的importing_slots_from数组记录了当前节点正在从其他节点导入的槽

<img src="images/image-20220330222610460.png" alt="image-20220330222610460" style="zoom:33%;" />
  • CLUSTER SETSLOT MIGRATING命令的实现
    clusterState结构的migrating_slots_to数组记录了当前节点正在迁移至其他节点的槽

<img src="images/image-20220330222636281.png" alt="image-20220330222636281" style="zoom:33%;" />

  • ASK错误

    如果节点没有在自己的数据库里找到键key，那么节点会检查自己的clusterState.migrating_slots_to[i]，看键key所属的槽i是否正在进行迁移，如果槽i的确在进行迁移的话，那么节点会向客户端发送一个ASK错误，引导客户端到正在导入槽i的节点去查找键key

  • ASKING命令

    在一般情况下，如果客户端向节点发送一个关于槽i的命令，而槽i又没有指派给这个节点的话，那么节点将向客户端返回一个MOVED错误；但是，如果节点的clusterState.importing_slots_from[i]显示节点正在导入槽i，并且发送命令的客户端带有REDIS_ASKING标识，那么节点将破例执行这个关于槽i的命令一次

    image-20220330222810822

    "

复制与故障转移

Redis集群中的节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点继续处理命令请求。

  • 设置从节点

    image-20220330223354761
    image-20220330223410477
    image-20220330223753669

    "

故障检测

  1. 集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此来检测对方是否在线，如果接收PING消息的节点没有在规定的时间内，向发送PING消息的节点返回PONG消息，那么发送PING消息的节点就会将接收PING消息的节点标记为疑似下线（probable fail，PFAIL）

  2. 当一个主节点A通过消息得知主节点B认为主节点C进入了疑似下线状态时，主节点A会在自己的clusterState.nodes字典中找到主节点C所对应的clusterNode结构，并将主节点B的下线报告（failure report）添加到clusterNode结构的fail_reports链表里面

    image-20220330223915432

    "

  3. 如果在一个集群里面，半数以上负责处理槽的主节点都将某个主节点x报告为疑似下线，那么这个主节点x将被标记为已下线（FAIL），将主节点x标记为已下线的节点会向集群广播一条关于主节点x的FAIL消息，所有收到这条FAIL消息的节点都会立即将主节点x标记为已下线。

故障转移

当一个从节点发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移，以下是故障转移的执行步骤：
1）复制下线主节点的所有从节点里面，会有一个从节点被选中。
2）被选中的从节点会执行SLAVEOF no one命令，成为新的主节点。
3）新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己。
4）新的主节点向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。
5）新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成。

选举新的主节点

image-20220415164437638

"

  1. 其他集群节点给从节点投票

  2. 基于Raft算法的领头选举（leader election)方法来实现的

消息

image-20220330224909157

"