Redis Cluster 实现原理
1. 简介
Redis Cluster 是 Redis 官方提供的集群模式。在Redis 3.0 版本开始支持，是在原有的 Redis 版本中增加了集群相关的实现，是同一个项目。Redis Cluster 方式各个节点其实是一样的，都是Redis节点，本身支持执行Redis的所有命令，也是数据的存储节点，只是额外支持一些 Cluster 命令。但是 Redis Sentinel 模式中，Sentinel 则是一个全新的角色，并不是数据的存储节点，不允许执行常规的 set / get / inc 等操作，主要运用于故障检测、故障发现、故障转移这些场景。
在之前的一篇文章中记录了关于 Redis Cluster 的学习笔记，其中是按照程序执行顺序编排的，也包括了一些细节方面的说明，对于研究 Redis 源码的同学可能有帮助，基本每一小节内容对应源码中的一小段程序。而这篇文章将是以一个使用者的角度去理解 Redis Cluster，所以更加宏观一些，某些细节可能就不会提到。关于细节可以参考：Redis Cluster 学习笔记
2. 通信流程
2.1 建立集群
集群配置有2种方式，一种是使用Redis安装包中的 redis-trib.rb 工具，其中对redis命令有一些封装，所以在使用上更方便一些；另一种方式是使用redis的内置命令直接与redis服务端交互。为了更加深刻的理解 Redis 内部运行原理，我们这里只介绍第二种方式。
2.1.1 先介绍一下，集群配置过程
a. 在所有节点配置中追加集群相关配置（注意是在原有单节点模式的配置文件中追加以下配置）
cluster-enabled yes // 开启集群模式 cluster-config-file nodes-7000.conf // 集群配置文件 cluster-node-timeout 15000 // 集群节点超时时间，单位毫秒
b. 启动所有节点
这时就要启动节点了，后续操作都需要与节点通信，所以我们这里就先把所有节点启动成功。
c. 连接所有节点
集群模式，所有节点需要相互通信，但是在 a. 中并没有配置集群所有节点的信息，所以在这之前他们还是相互独立的。接下来，我们就要让他们相互连接。通过其中一个节点N1向其他节点发送 MEET 命令，此时这个N1节点就会记录了其他节点（MEET 参数后对应的IP/PORT 节点）的IP/PORT清单信息。有了这个清单，N1节点就会与清单中的节点建立连接，然后向这些节点传播这个清单。其他节点收到清单后，也会执行相同的过程，最终，整个集群所有节点相互连接。
连接其中一个节点，向其他节点发送 MEET 命令。这里我们连接到端口为 7000 的节点，向 7001 7002 7003 7004 7005 节点发送 MEET 命令。如果当中只要有一个节点是部署在不同的IP下，那么这里需要把所有连接都替换为真实的IP地址，而不能再使用 127.0.0.1。
127.0.0.1:7000> CLUSTER MEET 127.0.0.1 7001 127.0.0.1:7000> CLUSTER MEET 127.0.0.1 7002 127.0.0.1:7000> CLUSTER MEET 127.0.0.1 7003 127.0.0.1:7000> CLUSTER MEET 127.0.0.1 7004 127.0.0.1:7000> CLUSTER MEET 127.0.0.1 7005
当我们在当前连接的节点N1上输入MEET命令后回车，代表我们期望当前节点N1与目标节点N2建立连接（当然这里也可以引申为第一次见面，因此称作MEET），发送完 MEET 命令后，会把这个目标节点N2的信息（包括 ip/port/cport）追加到当前节点N1的内核变量 server.cluster->nodes 列表中，并且设置这个节点的标记为 flags = CLUSTER_NODE_HANDSHAKE|CLUSTER_NODE_MEET 。然后就会返回 OK，这时并不会实际与这个节点进行连接。
注意：
1> 可以对相同的节点多次执行 MEET 命令，内部会进行兼容处理，如果连接已经建立，则并不会重复连接，依然返回 OK。但是没必要这么做，执行一次就够了。
2> 其结果返回OK, 只会验证 IP/PORT 数据类型是否正确，并不真正连接，所以并不代表连接就一定能成功，也许网络根本不通。
d. 分派槽
集群中每个节点负责处理一部分数据，以此来分摊总流量。通过对 key 进行hash取值之后取模求余，通过此种算法把不同的 key 分派到不同的节点上。取模使用的数字是 16384 ，2的14次方，也就是槽的最大数量，因此就需要为每个节点分派一些槽。节点总数不能超过槽的总数，不然必有其中一个节点分派不到槽。也就是说Redis集群模式下节点（这里只指Master节点，因为只有Master才实际分担槽数）总数最大值为 16384。
redis-cli -h 127.0.0.1 -p 7000 cluster addslots {0..5461}
redis-cli -h 127.0.0.1 -p 7001 cluster addslots {5462..10922}
redis-cli -h 127.0.0.1 -p 7002 cluster addslots {10923..16383}
上面 addslots 命令的正确写法是 0 1 2 3 这种格式，每个数字中间用空格隔开，相当于独立的一个一个的参数，而不是大括弧括起来，其中是不能有省略号。这里使用这种写法是为了更直观的描述。另外，如果使用 redis 安装包中的 redis-trib.rb 工具分派槽时，是使用{0..5461} 这种格式，其内部会转换。
首先这个分派只能对当前连接的节点分派，比如当前连接到了节点N1，然后输入命令：CLUSTER ADDSLOTS <slot> [slot] ... ，这相当于给当前节点分派槽。如果对应槽已经分派，则会返回错误。
这里会操作两个内核变量，来保存这个信息
1> myself->slots (类型：unsigned char slots[CLUSTER_SLOTS/8]; /* slots handled by this node */) 2> server.cluster->slots (类型：clusterNode *slots[CLUSTER_SLOTS])
两个都是数组，但是长度却不同，其值的含义也不同。
myself->slots 保存的是当前节点负责的槽，长度是总槽数的 1/8，按位保存，每一个位标记一个槽是否属于自己，如果属于赋值为1，否则为0。
server.cluster->slots 中则是保存的所有槽与集群所有节点的映射关系。
其作用不同，前者是方便查找当前节点负责的槽，后者是方便查找某个槽对应的节点。
注意：1> 当我们在执行 get / set 这样的命令时，其后的key必须是属于同一个槽，不然命令将执行失败，这也是集群模式与普通模式的使用上最直接的一个区别。2> hash 算法是这样的 crc16(key,keylen) & 0x3FFF 。 0x3FFF 就是槽的最大索引（最大槽数 -1），即16383 。3> 不过，我们也可以使用一种特殊技巧把key进行分组，同一种类型的key 存放到同一个槽中，这样在批量获取时就可以规避上面说的这个问题。
其规则是在key中使用{...} , 括弧不能出现在key的结尾，开始与中间都可以。如下：
{group1}key1 {group1}key2 // 相同槽
{group2}key1 {group2}key2 // 相同槽
{group3}key1 {group3}key2 // 相同槽
e. 配置Slave节点
上一步完成之后，其实集群就可以正常运行，但是为了更高的可用性，我们为每个Master配一个Slave，当Master故障时，Slave可以快速提升为Master，并且恢复服务。如果其中一个Master故障，此时又没有Slave，那么这个Master负责的这部分槽将不能继续服务，需要人工介入修复，这将大大影响可用性。
redis-cli -h 127.0.0.1 -p 7003 cluster replicate 29978c0169ecc0a9054de7f4142155c1ab70258b OK redis-cli -h 127.0.0.1 -p 7004 cluster replicate 8f285670923d4f1c599ecc93367c95a30fb8bf34 OK redis-cli -h 127.0.0.1 -p 7005 cluster replicate 66478bda726ae6ba4e8fb55034d8e5e5804223ff OK
最后一串数字是主节点ID，可以通过 CLUSTER NODES 命令获取到。
至此，集群建立完成。与 Redis Sentinel 方式相比，Redis Cluster 模式在建立阶段要复杂一些，因此在 Redis 的源码中提供了 redis-trib 这样的开箱即用的工具，更加方便我们使用，具体可以参看其对应的使用说明。
2.2 通信原理
上面建立集群的过程也相当于给集群初始化一些配置。但是 Redis 为什么不设计为直接让运维人员统一维护配置文件呢？这是因为这些信息在运行时可能会变化，一旦重启，这些新的配置可能会被统一维护的配置覆盖。即使运维人员不用维护这些配置项，但集群相关的信息还是会由集群自己维护，并会持久化到本地文件中。这个文件就是上面提到的 cluster-config-file 配置项所指定的。
执行完上面的这些命令，其实集群节点间还是孤立的，并没有真正进行通信。真正的建立连接是通过异步方式实现，也就是在周期性命令中调用。
2.2.1 主流程
a. 建立连接
clusterCron 这个函数中有大量的逻辑，其中包含与其他节点建立连接的过程
b. 发送周期性命令
clusterCron 通过这个函数也将会周期性的发送Ping命令来检测节点的状态，也将通过Ping命令来传播集群中的节点信息
clusterReadHandler 集群模式下有多种类型的消息，在这个函数中统一接收消息，然后根据消息类型去处理，部分类型的消息处理完之后，继续向相应节点进行消息的回复。
相关信息
1> 消息类型有10种
#define CLUSTERMSG_TYPE_PING 0 /* Ping */ #define CLUSTERMSG_TYPE_PONG 1 /* Pong (reply to Ping) */ #define CLUSTERMSG_TYPE_MEET 2 /* Meet "let's join" message */ #define CLUSTERMSG_TYPE_FAIL 3 /* Mark node xxx as failing */ #define CLUSTERMSG_TYPE_PUBLISH 4 /* Pub/Sub Publish propagation */ #define CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST 5 /* May I failover? */ #define CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 6 /* Yes, you have my vote */ #define CLUSTERMSG_TYPE_UPDATE 7 /* Another node slots configuration */ #define CLUSTERMSG_TYPE_MFSTART 8 /* Pause clients for manual failover */ #define CLUSTERMSG_TYPE_MODULE 9 /* Module cluster API message. */
2> 节点的角色
在集群模式下只有2种角色，Master 与 Slave, 并没有其他角色，但是这里为 Master/Slave 增加了高可用的实现，可以自行进行故障转移，不需要人工介入。
3> server.cluster->nodes 集群所有节点列表
这个列表结构会保存集群所有节点（包括 Master/Slave）的相关信息
4> server.cluster->size 集群大小
负责 slot 的 Master 节点个数，这个与上面的 nodes 的长度并不相同。投票阶段会使用这个数来计算需要的票数（needed_quorum = (server.cluster->size / 2) + 1）
2.2.2 详细流程
有几个过程我们应该需要重点关注与了解
a. 集群节点传播过程
在最开始建立集群的过程中我们在其中一个节点上向其他节点发送了MEET命令，这时这个节点就会使用MEET命令后对应的 IP/PORT 创建节点信息，然后添加到 server.cluster->nodes 中，然后根据遍历这个 nodes 列表，依次与之建立连接，最后这个节点与其他所有节点均保持通信。
但是仔细想想，既然是集群，应该所有节点间彼此都可以通信，这样才可以处理后续的一系列过程，比如投票、故障转移。因此还需要有别的机制来实现，它就是 gossip 协议。gossip：流言蜚语。这个叫法还是很贴切的，就如同在一群人当中传播明显绯闻，刚开始只有一个人知道某个消息，接着一传十，十传百，最后所有人都会听到这个消息。
b. 节点处理命令的过程
在集群模式下，正常使用方式只有 Master 对外提供服务，Slave 并不真正提供服务。每个 Master 节点只拥有部分数据，负责所有 slot 的 Master 的数据组合起来是一个集群的完整数据。比如：客户端有一个带着 key: abc 的命令，应该去哪个节点去执行呢？我想有2种方案：第一，客户端保存一份节点与slot的映射关系，然后根据命令中的 key 计算 slot，然后再根据 slot 去找到对应的节点；第二，客户端向任意一个节点发送命令，然后让 redis 服务端计算这个key在哪个节点上，如果在当前节点则处理相应逻辑，然后就返回结果，如果位于别的节点，返回相应节点信息，让客户端再去连接那个节点。
第一种方式客户端定期从服务端同步节点与 slot 的映射关系，在下次命令执行时这个映射关系可能已经在服务端发生变更，但是客户端还未及时同步更新，这将导致客户端连接的节点不正确。第二种方式倒是没有什么问题，但是客户端收到跳转命令的情况可能会比较多，会对客户端性能有影响。因此可以两种方式结合使用效果会更好。
如果客户端收到 MOVED 消息（-MOVED hashslot ip port）就说明命令中的 key 不在当前连接的节点，需要向这个新的ip/port对应的节点去发送命令。如果集群处于迁移、导入、异常状况时可能还会收到别的消息，可以参考 getNodeByQuery 函数的实现。
常用命令分为3种，有key, 无 key, pub/sub命令。
有 key ：如果一个命令中有多个key，那么所有这些key必须是要在一个slot，否则也返回错误。比如：get key1 key2
无 key：会在当前连接的节点进行处理，并不会返回 -MOVED 。比如：info / ping 等命令
pub/sub：PUBLISH / SUBSCRIBE 命令后面并没有 key 参数，而是 channel 参数，所有也就没有办法根据 key 计算 slot ，为此 redis 专门提供增加个一种消息 PUBLISH 消息，当客户端向集群其中一个节点发送PUBLISH命令时，这个节点会把这个数据再转发给集群其他节点。这样的设计，可以让我们在任意节点上执行 PUBLISH / SUBSCRIBE 命令。
c. 上面提到的10种消息执行流程与作用
#define CLUSTERMSG_TYPE_MEET 在初次建立连接时，发送MEET消息
#define CLUSTERMSG_TYPE_PING 在建立连接成功后，定期发送PING消息，传播集群节点信息，同时也检测节点的状态。
#define CLUSTERMSG_TYPE_PONG 在接收到MEET/PING消息时，回复PONG消息，表示当前节点正常。
#define CLUSTERMSG_TYPE_FAIL 如果当前节点标记了某个节点为FAIL状态时，给集群其他节点发送FAIL类型消息，通知其他节点也标记这个节点为FAIL。
#define CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST 发起投票请求。在发现集群中某个Master节点处于可能失败状态（PFAIL）时，由这个Master对应的Slave节点来发起故障转移（FAILOVER）,在多个Slave节点中要选择一个节点来执行FAILOVER操作，因此就需要发起投票，如果赢得选举，就开始执行FAILOVER。
#define CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 回复投票请求。当收到FAILOVER_AUTH_REQUEAT，如果是负责有效slot的Master节点时，则回复 ACK 消息，表示赞成票。否则不发送ACK消息。也就是说Slave并不参数与投票。
#define CLUSTERMSG_TYPE_UPDATE 用于发送节点slot更新消息。当收到PING/PONG消息时会检测消息中的slot信息是否一致，如果发送者的slot较新，则当前节点更新slot信息，如果当前节点的slot较新，则给发送者发送UPDATA消息，通知其更新对应slot。
#define CLUSTERMSG_TYPE_MFSTART 在执行了手动故障转移命令（CLUSTER FAILOVER），没有其他参数时，将会给当前节点对应的Master节点发送 MFSTART 消息，使其Master节点暂停接收客户端请求，让Slave与Master的offset保持同步之后再开始故障转移操作。
#define CLUSTERMSG_TYPE_MODULE 我们暂且不讨论，是 Module API 使用的。
#define CLUSTERMSG_TYPE_PUBLISH 用于传播客户端发送的PUBLISH命令的。当节点收到客户端发送的PUBLISH命令时，这个节点同步PUBLISH消息把这个命令传播给其他节点。
3. 高可用
高可用对于一个基础组件来说太重要了，这里不再重复，当然Redis Cluster也有自己的实现方式的，我们也将分为3部分来依次探讨。
3.1 故障检测
通过定期向其他节点发送PING消息，然后根据PONG回复的情况来验证节点是否正常。如果在指定的超时时间还未收到PONG回复，我们认为这个节点可能下线，标记为PFAIL 状态。节点超时时间可以通过配置文件进行配置（cluster-node-timeout）
ping_sent 用来记录发送时间。pong_received 用来记录接收时间
如果收到 PONG 回复则记录 pong_received 为当前时间戳，重置 ping_sent 为 0。通过ping_sent 与当前时间之差来计算响应时间。通过对几个随机节点比较 pong_received 来优先发送给更久没有发送 ping 消息的节点发送 ping 消息。
3.2 故障发现
在检测到PING请求超时后，当前节点标记目标节点为可能失败状态（CLUSTER_NODE_PFAIL）。但是这时并不能确认是当前节点（自己）本身的网络问题，还是目标节点故障，因此需要看看集群其他节点的反馈信息。相关名称：gossip 协议。PFAIL 可能失败。当前节点单方面认为某节点失败时，标记这个节点为 PFAIL 。如果集群大多数节点认为某节点失败时，标记这个节点为 FAIL。
在PING/MEET/PONG消息中，会包含有 gossip 结构的列表。gossip 就是包含一个集群节点信息的结构，gossip 列表就是多个节点信息的列表。gossip 结构列表包含部分 PING 延时较长的节点，与全部可能失败的节点。这样如果A节点发现B节点故障，如果真的发生了故障，其他节点就会定期的在PING消息中传播这个消息。经过几次的传播，很快节点就会知道其他节点把哪些节点标记为了PFAIL。
在每次携带gossip结构列表的消息时，就会检测消息中节点的可用性标记，是否是 FAIL 与 PFAIL 状态。如果是，我们将进行计算，是否大多数节点有同样的标记。如果不是，我们将清除之前的一些失败上报记录。如果大多数节点认为某节点是 PFAIL/FAIL. 则当前节点就会标记这个节点为 FAIL，确定这个节点是发生了故障。
有一个细节需要了解，只对 Master 节点发送来的失败节点进行处理。集群节点总大小（server.cluster->size）也就是Master节点的个数。在计算是否是大多数节点时，会用到 needed_quorum = (server.cluster->size / 2) + 1 。
如果最终标记为了 FAIL，则确认发生了故障。
3.3 故障转移
只有 Master 节点故障才会执行故障转移，并且由其下的 Slave 节点发起故障转移。如果有多个 Slave, 将选择其中一个来执行。这些 Slave 通过发出 选票请求，看谁先赢得半数以上节点的选票。对发起选票的时间按照 repl_offset（复制偏移量） 进行了时间差设置，主从同步延时最小的，最优先开始进行选票请求。
发送选票请求，即发送 CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST 类型消息，收到此消息的 Master 节点回复 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，选票 + 1。选票总数：server.cluster->size ，需要的选票数：needed_quorum = (server.cluster->size / 2) + 1
如果选票达到半数以上，则此节点开始进行故障转移操作。提升当前节点为Master，取消原来的主从关系，把原来 Master 负责的 slot 移到当前的节点。这时原来的Master 节点负责的 slot 数为0，接着给所有节点发送 PONG ，其他节点收到这个消息之后，各节点负责更新自己本地的 slot 与 node 的映射关系。
兄弟Slave节点收到 PING/PONG/MEET 消息之后，也会更新 slot 信息，同时也就会设置其新 Master 为上面提升的那个Slave节点（现在为Master节点）。当然如果这个故障的Master之后恢复了之后，也会跟随这个新的 Master。
如果这个故障节点对应的其他 Slave 节点收到上面的消息之后，也会更新 slot 映射关系，这时其 Master 负责的 slot 数就为 0，原来未开始的选票就不会再次执行。当然如果这时其Master 节点已经切换为了新的Master节点 ，其检测到对应的Master节点是正常的，选票也不会开始的。
3.4 手动故障转移
为了运维操作的灵活性，或者一些特殊的场景，提供了手动故障转移操作。手动故障转移分为 3 种，是使用 redis 提供的命令来（CLUSTER FAILOVER [force|takeover] -- Promote current slave node to being a master.）执行。3种行为分别是：
a. CLUSTER FAILOVER 这个就是正常的手动故障转移。会先给其 Master 发送 CLUSTERMSG_TYPE_MFSTART 类型消息，使其暂停客户端请求， 然后等 Master 发送了其最后的 offset 之后，当前 Slave 同步跟上这个 offset 时，开始故障转移，后续过程与 3.3 相同。
b. CLUSTER FAILOVER force Master 不会暂停客户端请求，当前Slave也不会进行 offset 的验证，直接开始一次故障转移，后续过程与 3.3 相同。
c. CLUSTER FAILOVER takeover 这个是最狠的。直接进行角色变更，slot 的移动，然后广播给所有节点。省去了发送选票的环节。
三种方式，可以在不同的情况下，根据需要使用。
3.4 Slave 节点迁移
集群中各个 Master 节点负责处理一部分客户端请求，如果某个 Master 故障时，其他 Master 并不会接管这个 Master 的职责，而是有这个 Master 下的 Slave 晋升为新的 Master 来接管。因此为了保证故障后，可以执行自动故障转移，我们也需要平均分配 Slave 节点到 Master 。
但是，设想在特殊情况下某个Master下多个 Slave 出现异常，甚至没有可用的 Slave 节点，因此需要一个 Slave 节点迁移机制来解决 Master 下无 Slave 节点的情形。
如果有孤立的 Master 节点（其下无可用Slave节点）时，统计拥有最多 Slave 节点的 Master，把这个 Master 下的其中一个 Slave（node ID 最小的） 迁移到孤立的 Master 节点下。
当然，我们可以设置单个 Master 节点，其下的Slave节点迁移给其他 Master 节点时自身必须保留的 Slave 节点个数（cluster-migration-barrier）, 免得自己最后成了那个孤立的节点。cluster-migration-barrier 默认值为 1 ，我们可以把它设置为一个正整数。
3.5 slot的迁移
在故障转移过程，slot 将会由原来的 Master 负责转移到新晋升的 Master 节点负责。
当我们想从原来的3个 Master 增加到5 个 Master 时，或者从5个 Master 减少到3个 Master 时，这也称为扩容、缩容。这时，我们就需要收到把 slot 对应节点映射到新的 节点，并迁移相关的数据。
这需要使用 SETSLOT 命令：CLUSTER SETSLOT <slot> (importing|migrating|stable|node <node-id>)
这个命令包含其中2种使用方式：
CLUSTER SETSLOT <slot> importing <node-id> 导入。从 node-id 节点导入 slot 数据到当前节点。
CLUSTER SETSLOT <slot> migrating <node-id> 迁移，把当前节点 slot 数据迁移到 node-id 节点。