【Redis】Redis Cluster集群原理_redis cluster slot算法原理

Redis Cluster是Redis官方提供的集群解决方案。由于业务的飞速增长，单机模式总会遇到内存、性能等各种瓶颈，这个时候我们总会喊，上集群啊。就跟我家热得快炸了，你总喊开空调呀一样。的确，上集群可以解决大多数问题，但是在使用集群的过程中，不可避免会遇到这样那样的问题，这个时候怎么办呢，各种百度各种群里去问吗？NO,作为开发人员，在享受第三方提供的方便前，有必要去了解其基本的工作机制，这样才能在遇到问题时快速定位，方便下手。本篇文章主要是梳理Redis集群的原理和Java客户端JedisCluster的工作流程及源码分析，虽万字长文，但原理通俗易懂，源码条理清晰。

一、RedisCluster

有关redis集群的基本介绍及搭建教程请移步：Redis 集群教程

1.1 数据如何读写

在单个的 redis节点中，我们都知道redis把数据已 k-v 结构存储在内存中，使得 redis 对数据的读写非常之快。Redis Cluster 是去中心化的，它将所有数据分区存储。也就是说当多个 Redis 节点搭建成集群后，每个节点只负责自己应该管理的那部分数据，相互之间存储的数据是不同的。

Redis Cluster 将全部的键空间划分为16384块，每一块空间称之为槽（slot），又将这些槽及槽所对应的 k-v 划分给集群中的每个主节点负责。如下图：

key -> slot 的算法选择上，Redis Cluster 选择的算法是 hash(key) mod 16383，即使用CRC16算法对key进行hash，然后再对16383取模，结果便是对应的slot。

常见的数据分区方法：

节点取余分区：对特定数据取hash值再对节点数取余来决定映射到哪一个节点。优点是简单，缺点是扩容或收缩时需重新计算映射结果，极端情况下会导致数据全量迁移。
一致性哈希分区：给每个节点分配一个0～2^32的token，使其构成一个环，数据命中规则为根据key的hash值，顺时针找到第一个token大于等于该hash的节点。优点是加减节点只影响相邻的节点，缺点是节点少的时候优点变缺点，反倒会影响环中大部分数据，同时加减节点时候会导致部分数据无法命中。
虚拟槽分区：使用分散度良好的hash函数将数据映射到一个固定范围的整数集合，这些整数便是槽位，再分给具体的节点管理。Redis Cluster使用的便是虚拟槽分区。
上面主要介绍了下集群中数据是如何分布在各节点上的，但实际上 客户端是如何读写数据 的呢？ Redis Cluster 采用了直接节点的方式 。集群模式下，客户端去操作集群是直连到一个具体的节点上操作的。当该节点接收到任何键操作命令时，会先计算键对应的slot，然后根据slot找出对应节点（这里如何找后面会提到），如果对应的节点是自身，则执行键操作命令，返回结果；如果不是自身，会返回给客户端MOVED重定向错误，告诉客户端应该请求具体哪个节点，由客户端发起二次请求到正确的节点，完成本次键操作。MOVED错误信息如下图所示：

当使用redis-cli 直连集群中节点时，使用 -c 参数，redis-cli会自动重定向连接到目标节点进行键操作。需要注意的是，这个自动重定向功能是redis-cli实现的，跟redis节点本身无关，节点本身依旧返回了MOVED错误给客户端。

在键操作命令中，除了对单个键值的操作，还有 多键值以及批量操作 。Redis 集群实现了所有在非分布式版本中出现的处理单一键值的命令，但是在使用 多个键值的操作 ，由于集群跟客户端的通信方式是直连节点，对于多键的操作却是需要遍历所有节点，因此是 不支持 的，一般由客户端在代码中实现需要的功能。 对于批量操作 ，一方面可以由客户端代码计算槽位，针对单个节点进行分档，最后批量操作，另一方面，Redis Cluster 提供了 hashtag 的功能，通过为key打上hashtag，让一类key在存储时就位于同一个slot，达到存储于同一个节点的效果。

hashtag: 是Cluster为了满足用户让特定Key绑定到特定槽位的需求而实现的一个功能。在计算key的slot时，如果key中包括花括号{}，并且花括号中内容不为空，便会计算花括号中标志对应的slot。如果不包括{}或是其中内容为空，则计算整个key对应的slot。可以利用这个功能，在特定需求中将一类key绑定到一个槽位上，但不可滥用，毕竟本身数据是分区存的，全这么搞会导致各节点内存占用不平衡，影响集群性能。

注意：lua脚本执行、事务中key操作，前提都是所涉及的key在一个节点上，如果在使用集群时无法避免这些操作，可以考虑使用hashtag，然后客户端通过这台节点的连接去操作。

1.2 节点间的信息共享

集群中会有多个节点，每个节点负责一部分slot以及对应的k-v数据，并且通过直连具体节点的方式与客户端通信。那么问题来了，你向我这里请求一个key的value，这个key对应的slot并不归我负责，但我又要需要告诉你MOVED到目标节点，我如何知道这个目标节点是谁呢？

Redis Cluster使用Gossip协议维护节点的元数据信息，这种协议是P2P模式的，主要指责就是信息交换。节点间不停地去交换彼此的元数据信息，那么总会在一段时间后，大家都知道彼此是谁，负责哪些数据，是否正常工作等等。节点间信息交换是依赖于彼此发出的Gossip消息的。常用的一般是以下四种消息：

meet消息 会通知接收该消息的节点，发送节点要加入当前集群，接收者进行响应。
ping消息 是集群中的节点定期向集群中其他节点（部分或全部）发送的连接检测以及信息交换请求，消息包含发送节点信息以及发送节点知道的其他节点信息。
pong消息 是在节点接收到meet、ping消息后回复给发送节点的响应消息，告诉发送方本次通信正常，消息包含当前节点状态。
fail消息 是在节点认为集群内另外某一节点下线后向集群内所有节点广播的消息。
在集群启动的过程中，有一个重要的步骤是 节点握手 ，其本质就是在一个节点上向其他所有节点发送meet消息，消息中包含当前节点的信息（节点id，负责槽位，节点标识等等），接收方会将发送节点信息存储至本地的节点列表中。消息体中还会包含与发送节点通信的其他节点信息（节点标识、节点id、节点ip、port等）,接收方也会解析这部分内容，如果本地节点列表中不存在，则会主动向新节点发送meet消息。接收方处理完消息后，也会回复pong消息给发送者节点，发送者也会解析pong消息更新本地存储节点信息。因此，虽然只是在一个节点向其他所有节点发送meet消息，最后所有节点都会有其他所有节点的信息。

集群启动后，集群中各节点也会定时往 其他部分节点 发送ping消息，用来检测目标节点是否正常以及发送自己最新的节点负槽位信息。接收方同样响应pong消息，由发送方更新本地节点信息。当在与某一节点通信失败（故障发现策略后面会说）时，则会主动向集群内节点广播fail消息。考虑到频繁地交换信息会加重带宽（集群节点越多越明显）和计算的负担，Redis Cluster内部的定时任务每秒执行10次，每次遍历本地节点列表，对最近一次接受到pong消息时间大于cluster_node_timeout/2的节点立马发送ping消息，此外每秒随机找5个节点，选里面最久没有通信的节点发送ping消息。同时 ping 消息的消息投携带自身节点信息，消息体只会携带1/10的其他节点信息，避免消息过大导致通信成本过高。

cluster_node_timeout 参数影响发送消息的节点数量，调整要综合考虑故障转移、槽信息更新、新节点发现速度等方面。一般带宽资源特别紧张时，可以适当调大一点这个参数，降低通信成本。

1.3 槽位迁移与集群伸缩

Redis Cluster 支持在集群正常服务过程中，下线或是新增集群节点。但无论是集群扩容还是收缩，本质上都是槽及其对应数据在不同节点上的迁移。一般情况下，槽迁移完成后，每个节点负责的槽数量基本上差不多，保证数据分布满足理论上的均匀。

常用的有关槽的命令如下：

CLUSTER ADDSLOTS slot1 [slot2]…[slotN] —— 为当前节点分配要负责的槽，一般用于集群创建过程。
CLUSTER DELSLOTS slot1 [slot2]…[slotN] —— 将特定槽从当前节点的责任区移除，和ADDSLOTS命令一样，执行成功后会通过节点间通信将最新的槽位信息向集群内其他节点传播。
CLUSTER SETSLOT slotNum NODE nodeId —— 给指定ID的节点指派槽，一般迁移完成后在各主节点上执行，告知各主节点迁移完成。
CLUSTER SETSLOT slotNum IMPORTING sourceNodeId —— 在槽迁移的目标节点上执行该命令，意思是这个槽将由原节点迁移至当前节点，迁移过程中，当前节点（即目标节点）只会接收asking命令连接后的被设为IMPORTING状态的slot的命令。
CLUSTER SETSLOT slotNum MIGRATING targetNodeId —— 在槽迁移的原节点上执行该命令，意思是这个槽将由当前节点迁移至目标节点，迁移过程中，当前节点（即原节点）依旧会接受设为MIGRATING的slot相关的请求，若具体的key依旧存在于当前节点，则处理返回结果，若不在，则返回一个带有目标节点信息的ASK重定向错误。 其他节点在接受到该槽的相关请求时，依旧会返回到原节点的MOVED重定向异常。
实际上迁移槽的核心是将槽对应的k-v数据迁移到目标节点。所以在完成slot在原节点和目标节点上状态设置（即上面最后两条命令）后，就要开始进行具体key的迁移。

CLUSTER GETKEYSINSLOT slot total —— 该命令返回指定槽指定个数的key集合
MIGRATE targetNodeIp targetNodePort key dbId timeout [auth password] —— 该命令在原节点执行，会连接到目标节点，将key及其value序列化后发送过去，在收到目标节点返回的ok后，删除当前节点上存储的key。整个操作是原子性的。由于集群模式下使用各节点的0号db，所以迁移时dbId这个参数只能是0。
MIGRATE targetNodeIp targetNodePort “” 0 timeout [auth password] keys key1 key2… —— 该命令是上面迁移命令基于pipeline的批量版本。
在整个slot的key迁移完成后，需要在各主节点分别执行CLUSTER SETSLOT slotNum NODE nodeId来通知整个slot迁移完成。redis-trib.rb 提供的reshard功能便是基于官方提供的上述命令实现的。

集群的扩展过程实际上就是启动一个新节点，加入集群（通过gossip协议进行节点握手、通信），最后从之前各节点上迁移部分slot到新节点上。

集群的收缩过程除了除了将待下线节点的槽均匀迁移到其他主节点之外，还有对节点的下线操作。官方提供了CLUSTER FORGET downNodeId命令，用于在其他节点上执行以忘记下线节点，不与其交换信息，需要注意的是该命令有效期为60s，超过时间后会恢复通信。一般建议使用redis-trib.rb 提供的del-node功能。

1.4 高可用

Redis集群牺牲了数据强一致性原则，追求最大的性能。上文中一直未提到从节点，主要都是从主节点出发去梳理数据存储、集群伸缩的一些原理。要保证高可用的前提是离不开从节点的，一旦某个主节点因为某种原因不可用后，就需要一个一直默默当备胎的从节点顶上来了。一般在集群搭建时最少都需要6个实例，其中3个实例做主节点，各自负责一部分槽位，另外3个实例各自对应一个主节点做其从节点，对主节点的操作进行复制（本文对于主从复制的细节不进行详细说明）。Redis Cluster在给主节点添加从节点时，不支持slaveof命令，而是通过在从节点上执行命令cluster replicate masterNodeId 。完整的redis集群架构图如下：

Cluster的故障发现也是基于节点通信的。每个节点在本地存储有一个节点列表（其他节点信息），列表中每个 节点元素除了存储其ID、ip、port、状态标识（主从角色、是否下线等等）外，还有最后一次向该节点发送ping消息的时间、最后一次接收到该节点的pong消息的时间以及一个保存其他节点对该节点下线传播的报告链表 。节点与节点间会定时发送ping消息，彼此响应pong消息，成功后都会更新这个时间。同时每个节点都有定时任务扫描本地节点列表里这两个消息时间，若发现pong响应时间减去ping发送时间超过cluster-node-timeout配置时间（默认15秒,该参数用来设置节点间通信的超时时间）后，便会将本地列表中对应节点的状态标识为PFAIL，认为其有可能下线。

节点间通信（ping）时会携带本地节点列表中部分节点信息，如果其中包括标记为PFAIL的节点，那么在消息接收方解析到该节点时，会找自己本地的节点列表中该节点元素的下线报告链表，看是否已经存在发送节点对于该故障节点的报告，如果有，就更新接收到发送ping消息节点对于故障节点的报告的时间，如果没有，则将本次报告添加进链表。 下线报告链表的每个元素结构只有两部分内容，一个是报告本地这个故障节点的发送节点信息，一个是本地接收到该报告的时间 （存储该时间是因为故障报告是有有效期的，避免误报） 。由于每个节点的下线报告链表都存在于各自的信息结构中，所以在浏览本地节点列表中每个节点元素时，可以清晰地知道，有其他哪些节点跟我说，兄弟，你正在看的这个节点我觉的凉凉了。

故障报告的有效期是 cluster-node-timeout * 2

消息接收方解析到PFAIL节点，并且更新本地列表中对应节点的故障报告链表后，会去查看该节点的故障报告链表中有效的报告节点是否超过所有主节点数的一半。如果没超过，便继续解析ping消息；如果超过，代表 超过半数的节点认为这个节点可能下线了，当前节点就会将PFAIL节点本地的节点信息中的状态标识标记为FAIL ,然后向集群内广播一条fail消息，集群内的所有节点接收到该fail消息后，会把各自本地节点列表中该节点的状态标识修改为FAIL。在所有节点对其标记未FAIL后，该FAIL节点对应的从节点就会发起转正流程。在转正流程完成后，这个节点就会正式下线，等到其恢复后，发现自己的槽已经被分给某个节点，便会将自己转换成这个节点的从节点并且ping集群内其他节点，其他节点接到恢复节点的ping消息后，便会更新其状态标识。此外，恢复的节点若发现自己的槽还是由自己负责，就会跟其他节点通信，其他主节点发现该节点恢复后，就会拒绝其从节点的选举，最终清除自己的FAIL状态。

1.5 从节点坎坷晋升路

在集群中若是某个主节点发生故障，被其他主节点标价为FAIL状态，为了集群的正常使用，这时会由其对应的从节点中晋升一个为新的主节点，负责原主节点的一切工作。

并不是所有从节点都有被提名的资格，这个跟普通职员的晋升一样。只有从节点与主节点的连接断线不超过一定时间，才会初步具备被提名的资格。该时间一般为cluster-node-timeout *10，10是从节点的默认有效因子。

一般来说，故障主节点会有多个符合晋升要求的从节点，那么怎么从这些从节点中选出一个最合适的来晋升为主节点恢复工作呢？从节点的作用是作为主节点的备份，每个对于主节点的操作都会异步在多个从节点上备份，但受具体的主从节点结构决定，一般每个从节点对于主节点的通不程度是不同的。 为了能更好的替代原主节点工作，就必须从这些从节点中选举一个最接近甚至完全同步主节点数据的从节点来完成最终晋升 。

从节点晋升的发起点是从节点。从节点在定时任务中与其他节点通信，当发现主节点FAIL后，会判断资深是否有晋升提名资格。如果有的话，则会根据相关规则设置一个选举自己的时间。在到达那个设置的时间点后，再发起针对自己晋升的选举流程，选票则由集群中其他正常主节点选投。若自己获得的选票超过正常主节点数的一半时，则会执行替换原主节点工作，完成本次选举晋升。

设置选举时间规则：发现主节点FAIL后并不会立马发起选举。而是经过 固定延时（500ms）+ 随机延时（0-500ms）+ 从节点复制偏移量排名 1000ms 后发起针对自己的选举流程。其中 固定延时 是保证主节点的FAIL状态被所有主节点获知，随机延时是为了尽量避免发生多个从节点同时发起选举的情况，最后的排名 1000ms是为了保证复制偏移量最大也就是最接近于原主节点数据的从节点最先发起选举。因此一般来说，从节点晋升选举一次就会成功。 主节点是没有区分哪个从节点是最适合晋升的规则的，主要靠这里的选举发起时间来让最合适的一次成功。

从节点发起选举主要分为两步：

自增集群的全局配置纪元，并更新为当前节点的epoch（配置纪元这里不详细介绍，不懂的可以先简单理解为版本号，每个节点都有自己的epoch并且集群有一个全局的epoch）;
向集群内广播选举消息FAILOVER_AUTH_REQUEST，消息内会包含当前节点的epoch。
从节点广播选举消息后，在NODE_TIMEOUT*2时间内等待主节点的响应FAILOVER_AUTH_ACK。若收到大多数主节点的响应，代表选举成功，则会通过ping\pong消息来宣誓主权。若未收到足够响应则会中断本次选举，由其他节点重新发起选举。

主节点在每个全局配置纪元中有且只有一张选票，一旦投给某个从节点便会忽视其他节点的选举消息。一般同一个配置纪元多个从节点竞争的情况只有极小概率会发生，这是由从节点的选举时间以及选举步骤决定的。主节点的投票响应FAILOVER_AUTH_ACK消息中会返回接收到的选举消息一样的epoch，从节点也只会认可跟节点当前epoch一致的投票响应，这样可以避免因为网络延迟等因素导致认可迟来的历史认可消息。

从节点成功晋升后，在替换原主节点时，还需要进行最后三步：

取消当前节点的复制工作，变身为主节点；
撤销原主节点负责的槽，并把这些槽委派给自己；
广播pong消息，通知所有节点自己已经完成转正以及转正后负责的槽信息。