《Redis设计与实现》笔记3—多机数据库的实现

一、复制

在Redis中，用户可以通过执行SLAVEOF命令或设置slaveof选项，让一个服务器去复制另外一个服务器，被复制的服务器称为主服务器，进行复制的服务器被称为从服务器

1、旧版复制功能的实现

Redis的复制功能分为同步和命令传播两个操作：

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

1、同步

当客户端从服务器发送SLAVEOF命令时，从服务器首先会执行同步操作，它会向主服务器发送SYNC命令，步骤如下：

从服务器向主服务器发送SYNC命令；
收到SYNC命令后主服务器执行BGSAVE命令，在后台生成一个RDB文件，使用一个缓冲区记录从现在开始的所有写命令；
主服务器的BGSAVE执行完成后，主服务器将RDB文件发送给从服务器，从服务器接受并载入RDB文件，将自己的状态更新至RDB文件记录的状态；
主服务器将记录在缓冲区的写命令发送给从服务器，从服务器执行这些写命令，将自身状态更新至主服务器当前的状态；

2、命令传播

当同步操作执行完毕之后，主从服务器的数据库达到一致的状态，但当主服务器执行写操作后，主从服务器状态将不再一致；为了确保状态的一致，主服务器会将接受到的写命令发送给从服务器，执行完成后状态再次回到一致

2、旧版复制功能的缺陷

Redis2.8版本之前，从服务器的复制分为两种情况：

初次复制：之前没有复制过主服务器，或者复制的主服务器与上一次主服务器不同；
断线后重新复制：处于命令传播的主从服务器因网路原因中断了复制，但从服务器重新连上了主服务器，并继续复制

后一种情况虽然在功能上没有问题，但是效率却非常低，因为它会在重新连接后重新发送SYNC命令接受RDB文件，但此时的RDB文件已经包含了部分之前复制过的数据，因而服务器做了部分重复的操作

3、新版复制功能的实现

Redis从2.8版本开始，使用PSYNC命令代替SYNC命令来执行复制时的同步操作，PSYNC命令具有完整重同步和部分重同步两种模式：

完整重同步用于处理初次复制的情况，其执行步骤与SYNC命令的执行步骤基本一致；

部分重同步用于处理断线后重复制情况，从服务器断线后，如果条件允许，主服务器可以将从断线开始执行的写命令发送给从服务器，从服务器接受并执行这些命令后，就可以将数据库更新至主服务器当前所处的状态

4、部分重同步的实现

4.1、复制偏移量

执行复制的双方，会分别维护一个复制偏移量。主服务器每次向从服务器传播N个字节的数据时，就将自己的复制偏移量的值加N，从服务器每次接收到主服务器传播来的N个字节的数据，就将自己的复制偏移量的值加N

通过对比主从服务器的复制偏移量，可续可以判断主从服务器的状态是否一致

4.2、复制积压缓冲区

复制积压缓冲区是主服务器维护的一个固定长度先进先出的而队列，默认大小为1MB（固定长度是指队首元素被弹出后队尾元素被入队）；主服务器进行命令传播时，不仅会将命令发送给从服务器，还会将命令写入复制积压缓冲区内；因此主服务器的复制积压缓冲区会保存着一部分最近传播的写命令，并且复制积压缓冲区会为队列中的每个字节记录相应的复制偏移量

当从服务器重新连接上主服务器之后，会将自己的复制偏移量发送给主服务器：

如果偏移量之后的数据存在于复制积压缓冲区，那么主从服务器将执行部分重同步操作；
如果偏移量之后的数据不存在于复制积压缓冲区，那么主从服务器将执行完整重同步操作；

当然我们可以根据公式second*write_size_per_second来估算复制积压缓冲区的大小，为了安全起见也可以设置为该结果的2倍，来应对大部分的断线情况。复制积压缓冲区大小的修改方法，可以参考配置文件中关于repl_backlog_size选项

4.3、服务器运行ID

除了上述两项外，部分重同步还需要用到服务器运行ID；每个Redis服务器都会有自己的运行ID，每个运行ID在服务器启动时自动生成，由40个随机的十六进制字符组成

当从服务器对主服务器进行初次复制时，主服务器会将自己的运行ID传送给从服务器，从服务器会将这个运行ID保存起来，当从服务器断线并重新连接上一个主服务器后，会向当前连接的主服务器发送之前保存的运行ID；如果从服务器保存的运行ID和当前连线的主服务器运行ID相同，那么断线前复制的就是当前的主服务器，主服务器恶意继续尝试执行部分重同步操作；如果ID不同，将执行完整重同步操作

5、PSYNC命令的实现

1、PSYNC命令的调用方法有两种：

如果服务器以前没有复制过任何主服务器，或者之前执行过SLAVEOF no one命令(从服务器关闭复制功能)，那么从服务器将发送PSYNC ？ -1命令，主动请求服务器进行完整重同步；
如果从服务器已经复制过主服务器，那么从服务器将发送PSYNC 命令，其中runid是上一次复制的主服务器的运行Id，而offset则是从服务器当前的复制偏移量

接收到PSYNC命令的主服务器会返回以下三种回复的一种：

主服务器返回+FULLERSYNC 回复，表示主服务器将与从服务器执行完整同步操作；
主服务器返回+CONTINUE，表示主服务器将与从服务器执行部分重同步操作，从服务器等着主服务器发送自己缺少的数据即可；
主服务器返回-ERR，表示主服务器的版本低于Redis2.8，无法识别PSYNC命令，从服务器将向主服务器发送SYNC命令，并执行完整同步操作；

6、复制的实现

设置主服务器的地址和端口：从服务器首先要做的通过SLAVEOF命令将客户端给定的主服务器IP地址和端口保存到服务器状态的masterhost属性和masterport属性中，完成后客户端返回OK，复制工作也将在返回OK之后进行；
建立套接字连接：在SLAVEOF命令执行之后，从服务器将根据命令设置的IP地址和端口创建连向主服务器的套接字连接，连接成功后，从服务器将为这个套接字关联一个专门用于处理复制工作的文件事件处理器，该处理器将负责执行后续的复制工作，如接受RDB文件，接受主服务器传播的写命令等。此时从服务器可以看作是一个连接到主服务器的客户端；
发送Ping命令：从服务器成为主服务器的客户端之后，第一件事将发送Ping命令：一是为了检查套接字的读写是否正常，二是为了检查主服务器能否正常处理命令请求。发送ping命令将会得到以下三种回复的一种：①主服务器返回命令回复，但从服务器不能在规定时间内读取出回复内容，表示网络连接状态不佳，从服务器将断开连接并重新创建套接字；②返回一个错误，表示主服务器暂时无法处理从服务器的命令请求，从服务器将断开连接并重新创建套接字；③从服务器读取到“PONG”回复，表示网络连接正常，从服务器将继续执行接下来的步骤
身份验证：服务器收到“PONG”回复后，将判断从服务器是否设置了masterauth选项，如果设置了该选项则需要进行身份验证，反之则不需要进行身份验证。如果需要进行身份验证，从服务器将发送一条AUTH命令，命令参数为从服务器masterauth选项的值。从服务器在身份验证阶段可能遇到以下情况：①主服务器没有设置requirepass选项，从服务器也没有设置masterauth选项，复制工作将继续进行；②从服务器通过AUTH发送的密码和主服务器requirepass选项设置的密码相同，复制工作继续进行，密码不同则返回invalid password错误；③主服务器设置了requirepass选项，但从服务器没有设置masterauth选项，主服务器将返回NOAuth错误；而如果主服务器没有设置requirepass选项，但从服务器设置了masterauth选项，那么主服务器将返回no password is set错误。一旦出现错误的情况，从服务器将中止目前的复制工作，并从创建套接字开始重复执行复制，直到身份验证通过，或从服务器放弃复制。总结如下：
发送端口信息：身份验证通过后，从服务器将执行ReplConf listening-port 命令，向主服务器发送从服务器的监听端口号，主服务器在接收到这个命令之后，会将端口号记录在从服务器所对应的客户端状态的slave_listening_port属性中
同步：从服务器将向主服务器发送PSYNC命令，执行同步操作，并将自己的数据更新至主服务器数据库当前所处的状态。执行同步操作前，从服务器是主服务器的客户端，执行同步操作之后，主服务器也将成为从服务器的客户端。在完整同步操作时，主服务器需要成为从服务器的客户端，才能将保存在缓冲区的写命令发送给从服务器；而在执行部分重同步操作时，主服务器需要成为从服务器的客户端，才能将保存在复制积压缓冲区的写命令发送给从服务器。不仅同步操作需要利用到这一点，主服务器对从服务器执行命令传播时也需要借助这一点
命令的传播：完成同步操作后，主服务器将进入命令传播阶段，从服务器只需要一直接受并执行主服务器发送的写命令即可保持状态的一致

7、心跳检测

在命令传播阶段，从服务器默认以每秒一次的频率，向主服务器发送命令：ReplConf ACK <replication_offset>，其中replication_offset是从服务器当前的复制偏移量；发送命令的目的如下：①检测主从服务器的网络连接状态；②辅助实现min-salves选项；③检测命令丢失

主从服务器可以通过发送或接受ReplConf ACK命令来检查两者之间的网络连接是否正常，服务主服务器超过1秒没有接收到从服务器发送的ReplConf ACK命令，即表示主从服务器之间的连接出现问题。
Redis的min-slaves-to-write和min-slaves-max-lag选项可以防止主服务器在不安全的情况下执行写命令；如min-slaves-to-write设置为3，min-slaves-max-lag设置为10，即表示从服务器的数量小于3或者3个从服务器的延迟值都大于等于10秒时，主服务器将拒绝执行写命令。
若因网络原因导致主服务器传播给从服务器的写命令丢失，那么当从服务器发送ReplConf ACK命令时，主服务器将发现从服务器的复制偏移量少于自己的复制偏移量，这是主服务器将会根据从服务器提交的复制偏移量，复制在积压缓冲器中从服务器缺少的数据，发送给从服务器。

主服务器补发缺失数据的操作与部分重同步操作非常相似，区别在于补发缺失数据的操作是在没有断线的情况下执行的，而部分重同步操作是在断线重连后进行的

二、Sentinel（哨兵）

Sentinel是Redis的高可用性解决方案：通过一个或多个Sentinel实例组成的Sentinel系统，可以监视任意多个主服务器，以及这些主服务属下的所有从服务器，并在被监视的主服务器进入下线状态时，自动将下线主服务属下的某个从服务器升级为主服务器，代替已下线的主服务器继续处理命令请求（故障转移操作）。如果之前下线的主服务器重新上线，它将被Sentinel系统降级为所属组的从服务器

1、启动并初始化Sentinel

启动一个Sentinel可以使用redis-sentinel /path/to/your/sentinel.conf或redis-server /path/to/your/sentinel.conf --sentinel命令，它们的效果完全一致。而当Sentinel启动时，它将执行以下步骤：①初始化服务器；②将普通Redis服务器使用的代码替换成Sentinel专用代码；③初始化Sentinel状态；④根据给定的配置文件，初始化Sentinel的监视主服务器列表；⑤创建连向主服务器的网络连接；

1、初始化服务器

Sentinel本质上就是一个运行在特殊模式下的Redis服务器，所以启动的第一步就是就是初始化一个普通的Redis服务器。但因Sentinel执行的工作和普通Redis服务器执行的工作不同，所以初始化过程与普通服务器有所区别，如下表在Sentinel模式下，服务器主要功能的使用情况：

2、使用Redis专用代码

该步骤会将一部分普通Redis服务器使用的代码替换成Sentinel专用代码，如普通Redis服务器使用redis.c/redisCommandTable作为服务器的命令表，而Sentinel则使用sentinel.c/sentinelcmds作为服务器的命令表，这也是部分命令无法在Sentinel模式下执行的原因

3、初始化Sentinel状态

服务器会初始化一个sentinel.c/sentinelSatae结构，该结构保存了服务器中所有和Sentinel功能有关的状态(一般状态仍由redis.c/redisServer结构保存)，如下图：

4、初始化Sentinel状态的masters属性

Sentinel状态中的masters字典记录了所有被Sentinel监视的主服务器的相关信息：键是被监视的主服务器的名字；值则是被监视的主服务器对应的sentinel.c/sentinelRedisInstance结构。

每个sentinelRedisInstance结构代表一个被Sebtinel监视的Redis服务器实例，这个实例可以是主服务器、从服务器或者是另外一个Sentinel。此结构实例包含的属性非常多，以下为其中的一部分：

sentinelRedisInstance.addr属性是一个指向sentinel.c/sentinelAddr结构的指针，这个结构保存着实例的IP地址和端口号；

对Sentinel状态的初始化将引发master字典的初始化，而master字典的初始化是根据被载入的Sentinel配置文件来进行的；

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

连接完成后，Sentinel将成为主服务器的客户端，它可以向主服务器发送命令并获取回复信息；对于每个被Sentinel监视的主服务来说，Sentinel会创建两个连向主服务器的异步网络连接(主要原因是由于目前的发布订阅功能中，被发送的信息不会保存在Redis服务器中)：

一个是命令连接，这个连接专门用于向主服务器发送命令，并接受命令回复；
另一个是订阅连接，这个连接专门用于订阅主服务器的_sentinel_:hello频道

2、获取主服务器的信息

1、Sentinel默认会以每10秒一次的频率，通过命令连接向被监视的主服务器发送INFO命令，并通过分析INFO命令的回复来获取主服务器的当前信息。通过分析主服务器返回的INFO命令回复，Sentinel可以获取以下两方面的信息：

主服务器本身的信息，包括run_id域记录的服务器运行ID，以及role域记录的服务器角色；
主服务器下所有从服务器的信息，每个从服务器都由一个"slave"字符串开头的行记录，包括从服务器的IP地址和端口号信息，通过这些信息，Sentinel无需用户提供的从服务器地址信息，就可以自动发现从服务器；

2、根据run_id域和role域记录的信息，Sentinel将对主服务器的实例结构进行更新，如主服务器重启后run_id变更，Sentinel检测到这类情况后，将会对实例结构的运行ID进行更新；从服务器信息将被用于更新主服务器实例结构的salves字典，该字典记录了主服务器下的从服务器名单：

字典的值是由Sentinel自动设置的从服务器名字，即ip:port；
字典的值是从服务器对应的实例结构

3、Sentinel在分析INFO命令中包含的从服务器信息时，会检查从服务器对应的实例结构是否已经存在于slaves字典中：

如果已存在，Sentinel将会对从服务器的实例结构进行更新；
如果不存在，则代表从服务器是新发现的服务器，Sentinel将为这个从服务器创建一个实例结构；

如上图，注意flags属性值和name属性，主服务器的name是用户使用Sentinel配置文件设置的，从服务器的name是Sentinel根据IP地址和端口号自动设置的

3、获取从服务器信息

当Sentinel发现主服务器有新的从服务器出现时，除了会为这个新的从服务器创建相应的实例结构外，Sentinel还会创建连接到从服务器的命令连接和订阅连接。

创建命令连接之后，Sentinel在默认情况下，会以每十秒一次的频率通过命令连接向从服务器发送INFO命令，并得到相关的回复，根据回复内容Sentinel会提取出以下信息：①从服务器的run_id；②从服务器的role；③主服务器的IP地址和端口号；④主从服务器的连接状态；⑤从服务器的优先级；⑥从服务器的复制偏移量。根据这些信息，Sentinel会对从服务器的实例结构进行更新

4、向主服务器和从服务器发送信息

在默认情况下，Sentinel会以每2秒一次的频率，通过命令连接向所有被监视的主服务器和从服务器发送以下命令：

该命令向服务器的_Sentinel_:hello频道发送了一条信息，s_开头的参数记录的是Sentinel本身的信息；m_开头的参数记录的是主服务器的信息，如果Sentinel正在监视的是主服务器，那么这些参数记录的就是主服务器的信息，如果Sentinel正在监视的是从服务器，那么这些参数记录的就是从服务器正在复制的主服务器的信息。详细如下：

5、接受来自主服务器和从服务器的频道信息

当Sentinel与一个主服务器或从服务器建立起订阅连接之后，Sentinel就会通过订阅连接，向服务器发送以下命令：Subscribe _sentinel_:hello，而Sentinel对_Sentinel_:hello频道的订阅会一直持续到Sentinel与服务器的连接断开为止。也就是说，每个与Sentinel连接的服务器，Sentinel既通过命令连接向服务器的_Sentinel_:hello频道发送信息，又通过订阅连接从服务器的_Sentinel_:hello频道接受信息，如下图：

对于监视同一个服务器的多个Sentinel来说，一个Sentinel发送的消息会被其他Sentinel接受到，这些信息会用于更新其他Sentinel对发送消息的Sentinel的认知，也会被用于更新其他Sentinel对被监视服务器的认知，举例说明如下：

1、更新sentinels字典

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

sentinels字典中的键是一个Sentinel的名字，格式为ip:port；
sentinels字典中的值则是键所对应Sentinel的实例结构

①当一个Sentinel接收到其他Sentinel发来的消息时，它会从信息中分析并提取出以下两方面的参数：

与Sentinel有关的参数：发送消息的Sentinel的IP地址、端口号、运行ID和配置纪元；
与主服务器有关的参数：发送消息的Sentinel正在监视的主服务器的名字、IP地址、端口号和配置纪元；

②接受消息的Sentinel首先会提取出信息中的主服务器参数，并在自己的Sentinel状态的masters字典中查找对应的主服务器结构，确认主服务器实例结构的sentinel字典中，是否存在提取出的主服务器，如果存在则更新信息，如果不存在则会新增。

2、创建连向其他Sentinel的命令连接

当Sentinel通过频道信息发现一个新的Sentinel时，它不仅会为新Sentinel在sentinels字典中创建新的实例结构，还会创建一个连向新Sentinel的命令连接，而新Sentinel同样也会创建连向这个Sentinel的命令连接，最终监视同一服务器的Sentinel形成相互连接的网络。（Sentinel需要通过主服务器或从服务器发来的频道信息来发现未知的新Sentinel，所以需要和它们建立订阅连接，而Sentinel之间只需要通过命令连接进行通信）

6、监测主观下线状态

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

有效回复：实例返回+PONG、-LOADING、-MASTERDOWN三种回复的一种；
无效回复：实例返回+PONG、-LOANDING、-MASTERDOWN三种回复外的其他回复，或者在指定时间内没有返回回复

Sentinel配置文件中的down-after-milliseconds选项指定了Sentinel判断实例进入主观下线所需要的时间长度；如果在这个时间长度内连续返回无效回复，那么Sentinel会将这个实例结构flags属性标识为SRI_S_DOWN，来表示该实例已进入主观下线状态（注意这里用户配置的down-after-milliseconds同样还会用来判断master属下所有从服务器和同样监视master的Sentinel是否进入主观下线状态；另外不同的Sentinel可以设置不同的主观下线时长）

7、检查客观下线状态

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

1、发送Sentinel is-master-down-by-addr命令

Sentinel会使用Sentinel is-master-down-by-addr <IP> <Port> <current_epoch> <runid>命令来询问其他Sentinel是否同意主服务器已下线，命令中的参数说明如下:

2、接受Sentinel is-master-down-by-addr命令

当目标Sentinel接受到源Sentinel发送的上述命令时，目标Sentinel会分析并取出命令请求中包含的各个参数，并根据IP和Port来检查主服务器是否已经下线，然后向源Sentinel发送包含三个参数的Multi Bulk回复，即<down_state>，和

3、接受Sentinel is-master-down-by-addr命令的回复

根据其他Sentinel返回的命令回复，Sentinel将统计其他同意主服务器已下线的数量，当这一数量达到配置指定的判断客观下线所需的数量时，Sentinel会将主服务器实例结构的flags属性的SRI_O_Down标识打开，表示主服务器已进入客观下线状态（需要注意的是不同的Sentinel判断客观下线的条件可以不同）

8、选举领头Sentinel

当一个主服务器被判断为客观下线后，监视这个主服务器的各个Sentinel会进行协商，选举出一个领头Sentinel，并由领头Sentinel对下线服务器进行故障转移操作。选举的规则和方法如下：

9、故障转移

在选举出领头Sentinel后，领头Sentinel将对已下线的主服务器执行故障转移操作，共三个步骤：

在已下线主服务器属下的所有从服务器里面，挑选一个从服务器将其转换为主服务器；
让已下线的主服务器属下的所有从服务器改为复制新的主服务器；
将已下线的主服务器设置为新的主服务器的从服务器，当其上线时，会成为新服务器的从服务器；

1、选出新的主服务器

故障转移操作的第一步就是在已下线主服务器属下的所有从服务器中选出一个状态良好、数据完整的从服务器，然后向这个从服务器发送SLAVEOF no one命令，将这个从服务器转换为主服务器；挑选规则如下：

领头服务器向被选中的从服务器发送完SLAVEOF no one命令后，领头Sentinel会以每秒一次的频率（平时时10秒一次）向被升级的从服务器发送INFO命令，并观察命令回复中的角色信息，当被升级服务器的role从slave变为master时，领头Sentinel将知晓从服务器已成功升级为主服务器

2、修改从服务器的复制目标

当新的主服务器出现之后，领头Sentinel要做的就是让已下线主服务器的属下所有从服务器去复制新的主服务器，这一个动作可以通过向从服务器发送SLAVEOF命令来实现

3、将旧的主服务器变为从服务器

故障转移的最后一步，就是将已下线的主服务器设置为新的主服务器的从服务器，这种设置时保存在旧的主服务器对应的实例结构里面的，所以当旧的主服务器上线时，Sentinel就会向它发送SLAVEOF命令，让他成为新的主服务器的从服务器

三、集群

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

1、节点

一个Redis集群通常由多个节点组成，刚开始的时候每个节点都是相互独立的，它们处于一个只包含自己的集群当中，要组建一个真正可用的工作集群，我们必须将各个独立的节点连接起来，构成一个包含多个节点的集群。连接节点可以用命令Cluster Meet <ip> <port>

向一个节点发送Cluster meet命令，可以让节点与ip和port所指定的节点进行握手，握手成功后，发送命令的节点就会将被连接的节点添加到当前的集群中。完成后可以通过Cluster Nodes命令查看当前的集群信息

1、启动节点

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

开启集群模式的Redis服务器会继续使用所有在单机模式中使用的服务器组件，除此之外集群模式下用到的数据，节点将它们保存到三种数据结构中，即cluster.h/clusterNode结构、cluster.h/clusterLink结构和cluster.h/clusterState结构

2、集群数据结构

①clusterNode结构保存了一个节点当前的状态，如节点的创建时间，节点的名字，节点当前的配置纪元、节点的IP地址和端口号等。每个节点都会使用一个clusterNode结构来记录自己当前的状态，并为集群中的其他节点都创建一个相应的clusterNode结构，来记录节点的状态，如下：

②其中Link属性是一个clusterLink结构，该结构保存了连接节点所需的所有信息，如套接字描述符、输入缓冲区和输出缓冲区，如下：

③每个节点都保存着一个clusterState结构，这个结构记录了当前节点的视角下，集群目前所处的状态，比如集群是在线还是下线，集群所包含的节点数、集群当前的配置纪元等，如下：

如下是一个ClusterState结构示意图：

3、Cluster meet命令

通过向节点A发送Cluster Meet命令，客户端可以让接受到命令的节点A将接节点B添加至节点A所在的集群中。接受到命令的节点A会和节点B进行握手操作，来确认彼此的存在，为进一步的通信打好基础：

节点A会为节点B创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典中；
节点A根据Cluster meet命令给定的IP和端口号，向节点B发送一条Meet消息；
正常情况下，节点B会接收到节点A发送的meet消息，节点B会为节点A创建一个clusterNode结构，并将该结构添加到自己的clusterState.Node字典中；
节点B向节点A返回一条PONG消息；
正常情况下，节点A将接收到节点B返回的PONG消息，通过PONG消息节点A可以知道节点B已经成功接受到自己发送的meet消息；
之后节点A会向节点B返回一条PING消息；
正常情况下，节点B将接受到节点A返回的PING消息，通过这条PING消息，节点B可以知道节点A已经成功接收到了自己返回的PONG消息，此时握手完成

握手完成后，节点A会将节点B的信息通过Gossip协议传播给集群中的其他节点，让其他节点也与节点B进行握手，最后节点B会被集群中的所有节点所认识

2、槽指派

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

当数据库中的16384个槽都有节点在处理时，集群处于上线模式；相反，只要有一个槽没有得到处理，那么集群将处于下线模式。

可以使用Cluster Info命令来查看集群的状态；通过向节点发送Cluster AddSlots <slot> [slot......]命令，我们可以将一个或多个槽指派给节点负责；

1、记录节点的槽指派信息

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

slots属性是一个二进制位数组，数组的长度为16284/8=2048个字节，共16384个二进制位。Redis从索引0开始到索引16384，对slots数组中的16384个二进制位进行编号，并根据索引上二进制位的值判断是否负责处理槽，二进制为1代表负责，为0代表不负责；
numslots属性记录节点负责处理的槽的数量

2、传播节点的槽指派信息

一个节点除了会将自己负责处理的槽记录在clusterNode结构的slots属性和numslots属性外，它还会将自己的slots数组通过消息发送给集群中的其他节点，来告知其他节点自己目前负责处理哪些槽。

当节点A通过消息从节点B中接收到节点B的slots数组时，节点A会在自己的clusterState.nodes字典中查找节点B对应的clusterNode结构，并对结构中的slots数组进行保存或更新。真是由于这种机制，集群中的每个节点都会知道数据库中的16384个槽被指派给了哪个节点

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

clusterState结构中的slots数组记录了集群中所有16384个槽的指派信息；slots数组包含16384个项，每个数组都是一个指向clusterNode结构的指针。如果指针指向为null则代表槽未指派给任何节点，如果指向一个clusterNode结构则表示槽已经指派给了clusterNode结构所代表的节点。

如果节点只使用clusterNode.slots数组来记录槽的指派信息，那么为了知道槽位i是否被指派或槽位i被指派给了哪些节点，程序需要遍历clusterStata.nodes字典中所有的clusterNode结构，检查这些结构的slots数组直到找到负责处理槽i的节点，整个过程的复杂度位O(n)。而通过将所有槽的指派信息保存在clusterState.slots数组中，程序要检查槽位i是否被指派，又或者取得负责处理槽i的节点，只需要访问clusterState.slots[i]的值即可，而这个复杂度仅为O(1)

虽然clusterState.slots数组记录了集群中所有槽的指派信息，但使用clusterNode结构的slots数组来记录单个节点的槽指派信息仍是有必要的。因为当程序需要将某个节点的槽指派信息通过消息发送给其他节点时，程序只需要将相应节点的clusterNode.slots数组发送出去就可以了；另一方面，如果Redis不使用clusterNode.slots数组，而单独使用clusterState.slots数组的话，每次将节点A的槽指派信息传播给其他节点时，程序都要先遍历整个clusterState.slots数组，记录节点A负责处理哪些槽，才能发送节点A的槽指派信息。

两者的主要区别：clusterState.slots数组记录了集群中所有槽的指派信息，而clusterNode.slots数组只记录了clusterNode结构所代表的节点的槽指派信息

4、Cluster AddSlots命令的实现

Cluster AddSlots命令接受一个或多个槽作为参数，并将所有输入的槽指派给接受该命令的节点负责，如下：

3、在集群中执行命令

在对数据库中的16384个槽都进行了指派之后，集群就会进入上线状态。当客户端向节点发送与数据库键有关的命令时，接受命令的节点会计算出处理命令的数据库键属于哪个槽，并检查这个槽是否指派给了自己。如果键所在的槽指派给了当前节点，那么节点将直接执行这个命令；如果键所在的槽没有指派当前节点，当前节点会向客户端返回一个MOVED错误，指引客户端转向至正确的节点，并再次发送之前要执行的命令。

1、计算键属于哪个槽

节点使用以下算法来判断给定的key属于哪个槽：def slot_number(key) : return CRC16(key) & 16384；其中CRC16(key)语句用于计算键的CRC-16校验和，而 & 16384语句则用于计算介于0~16384之间的整数作为键的槽号

Cluster keySlot命令就是基于上述的分配算法，可以用来查看一个给定的键属于哪个槽

2、判断槽是否由当前节点负责处理

当节点计算出键所属的槽后，节点就会检查自己在clusterState.slots数组中的项i，判断键所在的槽是否由自己负责。如果clusterState.Slots[i]等于clusterState.myself，即说明槽i由当前节点负责，节点可以执行客户端发送的命令；如果不相等，节点会根据clusterState.Slots[i]指向的clusterNode结构，并根据结构中所记录的节点IP和端口号，向客户端返回MOVED错误，指引客户端转向至正在处理槽i的节点

3、MOVED错误

当节点发现键所在的槽不由自己负责时，节点就会向客户端返回一个MOVED错误。MOVED错误的格式为MOVED <slot> <ip>:<port>，其中slot为键所在的槽，而IP和Port则是负责处理槽slot的节点的IP地址和端口号。如错误Moved 10086 127.0.0.1:7002表示槽10086正在由IP为127.0.0.1端口为7002的节点负责。

当客户端接收到节点返回的MOVED错误时，客户端会根据MOVED错误中提供的IP地址和端口号，转向至负责处理槽Slot的节点，并向该节点重新发送之前想要执行的命令。一个集群客户端通常会与集群中的多个节点创建套接字连接，而所谓的节点转向实际上就是换一个套接字来发送命令。如果客户端尚未与想要转向的节点创建套接字连接，那么客户端先根据MOVED错误提供的IP地址和端口号来连接节点，然后再进行转向。

需要注意的是，集群模式的redis-cli客户端在接收到MOVED错误时，并不会打印出MOVED错误，而是根据MOVED错误自动进行节点的转向，并自动打印出转向信息。而单机模式下的redis-cli客户端则会将MOVED错误打印出来

4、节点数据库的实现

集群节点保存键值对以及键值对过期时间的方式，与单机Redis服务器的机制完全相同，唯一的区别是节点只能使用0号数据库，而单机Redis服务器则没有这一限制。除了将键值对保存在数据库之外，节点还会用clusterState结构中的slots_to_keys跳跃表来保存槽和键之间的关系。slots_to_keys跳跃表每个节点的分值(score)都是一个槽号，而每个节点的成员(number)都是一个数据库键：

每当节点往数据库中添加一个新的键值对时，节点就会将这个键以及键的槽号关联到slots_to_keys跳跃表；
当节点删除数据库中的某个键值对时，节点就会在slots_to_keys跳跃表解除被删除键与槽号的关联；

通过在slots_to_keys跳跃表中记录各个数据库键所属的槽，节点可以很方便地对属于某个或某些槽的所有数据库进行批量操作，例如命令Cluster GetKeySinSlot <slot> <count>命令可以返回最多count个属于槽slot的数据库键，而这个命令就是通过遍历跳跃表实现的。

4、重新分片

Redis集群的重新分片操作可以将任意数量已经分配给某个节点的槽改为指派给另一个节点，并且槽所属的键值对也会移动到新节点。重新分片操作可以在线进行，在重新分片的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求。

Redis集群的重新分片操作是由Redis的集群管理软件redis_trib负责执行的，Redis提供进行重新分片所需的所有命令，而redis-trib则通过向源节点和目标节点发送命令来进行重新分片操作。redis-trib对集群的单个槽slot进行重新分片的步骤如下：

redis-trib对目标节点发送Cluster SetsLot <slot> Importing <source_id>命令，让目标节点准备好从源节点导入属于槽的键值对；
redis-trib对源节点发送Cluster SetsLot <slot> Migrating <target_id>命令，让源节点准备好将属于槽的键值对迁移到目标节点；
redis-trib向源节点发送Cluster GetKeysSinslot <slot> <count>命令获得最多count个属于槽的键值对的键名；
对于上一步获得的每个键名，redis-trib都向源节点发送一个Migrate <target_ip> <target_port> <key_name> 0 <timeout>命令，将被选中的键原子地从源节点迁移至目标节点
重复执行第三第四步骤，直到源节点保存的所有属于槽Slot的键值对都被迁移至目标节点为至；
redis-trib向集群中的任意一个节点发送Cluster SetSlot <slot> Node <target_id>命令，将槽slot指派给目标节点，指派信息会通过消息发送至整个集群，最终集群中的所有节点都会知道槽已经指派给了目标节点

5、ASK错误

在进行重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现属于被迁移槽的一部分键值对被保存在源节点，而另一部分键值对则保存在目标节点里面。当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据又恰好属于正在被迁移的槽时：

源节点会先在自己的数据库中查找指定的键，如果找到的话，就直接执行客户端发送的命令；
如果源节点没有在自己的数据库中找到指定的键，那么这个键可能已经被转移到目标节点，源节点将向客户端返回一个ASK错误，指引客户端转向正在导入槽的目标节点，并再次发送需要执行的命令

1、Cluster SetSlot Importing命令的实现

clusterState结构的import_slots_from数组记录了当前节点正在从其他节点导入的槽，如果import_slots_from[i]的值不为null，而是指向一个clusterNode结构，则表示当前节点正在从clusterNode所代表的节点导入槽i.

在对集群进行重新分片时，向目标节点发送Cluster SetLots <i> Importing <source_id>可以将目标节点clusterState,importing_slots_from[i]的值设置为source_id所代表节点的ClusterNode结构

2、Cluster SetSlot Migraing命令的实现

clusterState结构的migrating_slots_to数组记录了当前节点正在迁移至其他节点的槽，如果migrating_slots_to[i]的值不为null，而是指向一个clusterNode结构，则表示当前节点正在将槽i迁移至clusterNode所代表的节点

在对集群进行重新分片时，向源节点发送命令Cluster SetLots <i> Migrating <target_id>可以将源节点clusterState.migrating_slots_to[i]的值设置为target_id所代表节点的clusterNode结构

3、ASK错误

如果节点收到一个键的命令请求，并且键所属槽正好分配给了该节点，节点就会直接执行该命令，否则节点会检查自己的ClusterState.migrating_slots_to[i]，看键所属的槽是否正在进行迁移，如果正在执行迁移，节点会像客户端发送ASK错误，引导客户端到正在导入槽的节点去查找key（会在向目标节点转发命令前发送一条ASKING命令）

4、ASKING命令

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

当客户端接收到ASK错误并转向正在执行导入槽命令的节点时，客户端会先向节点发送一个ASKING命令，然后再发送想要执行的命令，这时命令将会被源节点执行。需要注意的是，客户端的Redis_Asking标识是一个一次性标识，当节点执行了一个带有Redis_Asking标识的客户端发送的命令后，客户端的Redis_Asking标识就会被移除

5、ASK错误和MOVED错误的区别

MOVES错误代表槽的负责权已经从一个节点转移到了另一个节点，客户端收到槽i的命令请求都会将请求发送给MOVED错误所指向的节点；
ASK错误是两个节点在迁移槽的过程中使用的一种临时措施，客户端在接收到槽i的ASK错误之后，客户端只会在接下来的一次命令请求中将关于槽i的命令请求发送至ASK错误所指示的节点，后续槽i的命令请求仍然会发送至目前负责处理槽i的节点

6、复制和故障转移

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

1、设置从节点

向一个节点发送命令Cluster RePlicate <node_id>可以让接受命令的节点成为node_id所指定节点的从节点，并开始对主节点复制：

接收到该命令的节点首先会在自己的clusterState.nodes字典中找到node_id所对应节点的clusterNode结构，并将自己的clusterState.myself.slavedof指针指向这个结构，来记录这个节点正在复制的主节点；
然后节点会修改自己在clusterState.myself.flags中的属性，关闭原本的Redis_Node_Master标识，打开Redis_Node_Slave标识，表示这个节点已经从主节点变为从节点；
最后，节点会调用复制代码，并根据clusterState.myself.slaveof指向的clusterNode结构所保存的IP地址和端口号，对主节点进行复制。复制功能和单机Redis服务器使用相同的功能，因而命令相同，相当于从节点发送命令Slaveof <master_ip> <master_port>

节点成为从节点并开始复制某个主节点的消息会通过消息发送给集群中的其他节点，最终集群中的所有节点都会从知晓这一消息。而集群中的所有节点都会在代表主节点的clusterNode结构的slaves属性和numslaves属性中记录正在复制这个主节点的从节点名单

2、故障检测

集群中的每个节点都会定期地向集群中的其他节点发送PING消息，来检测对方是否在线，如果接受PING消息的节点没有在规定时间内向发送PING消息的节点返回PONG消息，那么发送PING消息的节点会将接受PING消息的节点标记为疑似下线，即在clusterState.nodes字典中找到节点对应的clusterNode结构，并在结构的flags属性中打开Redis_NODE_PFail标识

集群中的各个节点会通过互相发送消息的方式来交换集群中各个节点的状态信息，如主节点A通过主节点B得知主节点C进入了疑似下线状态，主节点A会在自己的clusterState.nodes字典中找到节点C对应的clusterNode结构，并将主节点B下线报告添加到clusterNode结构的fail_reports链表中，而每个下线报告由一个clusterNodeFailReport结构表示

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

3、故障转移

当一个从节点发现自己正在复制的节点进入已下线状态时，从节点将开始对下线主节点进行故障转移，步骤如下：

复制下线主节点的所有从节点中，会有一个从节点被选中，并执行SLAVEOF no one命令，成为新的主节点；
新的主节点会撤销所有对已知下线主节点的槽指派，并将这些槽全部指派给自己；
新的主节点会向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点知道这个节点已经由从节点变为了主节点，并且接管了原本由已下线节点负责处理的槽；
新的主节点开始接受和自己负责处理的槽有关的命令请求，故障转移完成

4、选举新的主节点

以下是新的主节点选举方法的步骤，和领头Sentinel的方法非常相似，因为都是基于Raft算法的领头选举方法实现的：

集群的配置纪元是一个自增计数器，初始值为0；
当集群中的某个节点开始一次故障转移操作时，集群配置纪元的值会变为加一；
对于每个配置纪元，集群中每个负责处理槽的主节点都只有1次投票机会，而第一个向主节点要求投票的从节点将获得主节点的投票；
当从节点发现自己复制的主节点下线时，从节点会像集群广播以一条ClusterMsg_Type_FailOver_Auth_Request消息，要求所有接收到这条消息并且具有投票权的主节点向这个从节点投票；
如果一个主节点具有投票权，并且这个主节点尚未投票给其他从节点，那么这个主节点将向要求投票的从节点返回一条ClusterMsg_Type_FailOver_Auth_Ack消息，表示这个主节点支持从节点成为新的主节点；
每个参与选举的从节点都会接受ClusterMsg_Type_FailOver_Auth_Ack消息，并根据接收到的条数来统计自己获得了多少主节点的支持；
如果集群中有N个具有投票权的主节点，那么当一个从节点收集到大于等于N/2+1张投票时，从几点就会当选成为新的主节点；
因为在一个配置纪元中，每个具有投票权的主节点只能投一次票，所以获得大于等于N/2+1张投票的从节点只会有一个；
如果在一个配置纪元中没有从节点能后收集到足够多的票，那么集群将进入一个新的纪元，并再次进行选举直到新的主节点选出；

7、消息

集群中的各个节点通过发送和收集消息来进行通信，发送消息的为发送者，接受消息的为接收者。节点发送的消息主要有以下5种：

Meet消息：当发送者接收到客户端发送的Cluster Meet命令时，发送者会向接收者发送Meet消息，请求接收者加入到发送者的集群中；
PING消息：集群中的每个节点默认每隔一秒就会从已知节点列表中随机选出5个节点，然后对5个节点中最长时间没有发送PING消息的节点发送PING消息，来检测是否在线。另外如果节点A最后一次收到节点B发送的PONG消息超过了cluster-node-timeout属性的一半，节点A也会向节点B发送PING消息，防止对节点B的信息更新滞后；
PONG消息：当接收者收到发送者发来的Meet消息或ping消息时，为了向发送者确认这条Meet消息或者PING消息已经到达，接收者会向发送者返回一条PONG消息。另外，节点也可以通过向集群广播自己的PONG消息让集群中的其他节点立即刷新关于这个节点的认知（如从节点成为了新的主节点）；
FAIL消息：当一个主节点A判断另一个主节点B已经进入FAIL状态时，节点A会像集群广播一条关于节点B的FAIL消息，所有接收到这条消息的节点都会立即将节点B标记为已下线；
PUBLISH消息：当节点接收到一个PUBLISH消息时，节点会执行这个命令，并向集群广播一条PUBLISJ消息，所有接受到这条消息的节点都会立即执行相同的PUBLISH消息；

一个消息由消息头和消息正文组成，接下来将介绍消息头和5类消息正文

1、消息头

节点发送的所有消息都由一个消息头包裹，消息头除了包含消息正文之外，还记录了消息发送者自身的一些信息，这些信息也会被接收者用到，因而严格来讲，消息头本身也是消息的一部分。每个消息头由一个cluster.h/clusterMsg结构表示，如下：

clusterMsg结构的currentEpoch、Sender、mySlots等属性记录了发送者自身的节点信息，接收者会根据这些信息，在自己的clusterState.nodes字典中找到发送者对应的clusterNode结构，并对结构进行更新。如通过接收者为发送者记录的槽指派信息，以及发送者在消息头的myslots属性记录的槽指派信息，接收者就可以判断槽指派信息是否发生了变化。

而sclusterMsg.data属性指向联合cluster.h/clusterMsgData，这个联合就是消息的正文：

2、MEET、PING、PONG消息的实现

Redis集群中的各个节点通过Gossip协议来交换各自关于不同节点的状态信息，其中Gossip协议由MEET、PING、PONG三种消息实现，这三种消息的正文都由两个cluster.h/clusterMsgDataGossip结构组成。由于这三种消息都使用相同的消息正文，所以节点通过消息头的type属性来判读消息的类别。

每次发送MEET、PING、PONG消息时，发送者都从自己已知节点列表中随机选出两个节点，并将这两个节点的信息分别保存到两个clusterMsgDataGossip结构中。该结构记录了被选中节点的名字，发送者与被选中节点最后一次发送和接受PING消息和PONG消息的时间戳，被选中节点的IP地址和端口号，以及被选中节点的标识值：

当接收者收到MEET、PING、PONG消息时，接收者会访问消息正文中的两个clusterMsgDataGossIp结构，并根据自己是否认识该结构中记录的被选中节点来判断进行哪种操作：

如果被选中节点不存在于接收者的已知节点列表，即代表接收者是第一次接触到被选中节点，接收者将根据结构中记录的IP地址和端口号信息，与被选中节点进行握手；
如果被选中节点存在于接收者的已知节点列表，即代表接收者之前与被选中节点接触过，接收者将根据结构记录的信息对被选中节点所对应的clusterNode结构进行更新

3、FAIL消息的实现

当集群中的主节点A将主节点B标注为已下线(FAIL)时，主节点A将向集群广播一条关于主节点B的FAIL消息，所有接受到这条FAIL消息的节点都会将主节点B标记为已下线

在集群节点数量较大的情况下，使用Gossip协议来传播节点的已下线信息会给节点的信息带来一定的延迟，因为Gossip协议消息需要一段时间才能传播至整个集群，因而使用FAIL消息来实现。FAIL消息的正文由cluster.h/clusterMsgDataFail结构表示，这个结构只包含一个nodeName属性，该属性记录了已下线节点的名字。因为集群中所有节点的名字都是唯一的，因而FAIL消息只需要保存下线节点的名字，接收到消息的节点就可以根据这个名字来判断哪个节点下线了

4、PUBLISH消息的实现

当客户端向集群中的某个节点发送命令：PUBLISH <channel> <message>时，接收到PUBLISH命令的节点不仅会向channel频道发送消息message，还会像集群广播一条PUBLISH消息，所有接收到这条PUBLISH消息的节点都会像channel频道发送message消息。换句话说，向集群中的某个节点发送命令PUBLISH <channel> <message>，将导致集群中的所有节点都向channel频道发送message消息

PUBLISH消息的正文由cluster.h/clusterMsgDataPublish结构表示：

bulk_data属性是一个字节数组，保存了客户端通过PUBLISH命令发送给节点的channel参数和message参数；
channel_len和message_len分别保存了channel参数的长度和message参数的长度，bulk_data的0字节~channel_len-1字节保存的是channel参数；而channel_len字节~channel_len+message_len-1字节保存的则是message参数

注意：实际上直接向所有节点广播PUBLISH命令是最简单的执行相同PUBLISH命令的方法，这也是Redis在复制PUBLISH命令时所用到的方法，但这不符合Redis集群通过发送和接受消息进行通信的规则，因而没有采用