Redis Cluster

Redis Cluster

Redis Cluster是Redis3.0版本推出的高可用及分布式解决方案，多个Redis实例组成，数据按照槽(slot)存储分布在多个Redis实例上，通过Gossip流言协议来进行节点之间通信。

Redis Cluster实现的功能：

• 将数据分片到多个实例(按照slot存储)；
• 集群节点宕掉会自动failover；
• 提供相对平滑扩容(缩容)节点。

Redis Cluster暂未有的：
• 实时同步
• 强一致性

分片实现

基于hash的分片方式，具体是虚拟槽分区。

虚拟槽分区

• 槽(slot):使用分散度良好的hash函数把所有数据映射到一个固定范围的整数集合中。
• Redis Cluster槽的范围是0 ~ 16383。槽是集群内数据管理和迁移的基本单位。

分片的具体算法
Redis Cluster使用slot = CRC16(key) %16384来计算键key属于哪个slot。

CRC算法全称循环冗余校验算法。16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以）后,再除以一个多项式,最后 所得到的余数既是CRC码。
(注: CRC16算法——循环冗余校验(Cyclic Redundancy Check/Code)，即G(x)为：x16+ x12+ x5+ 1。)

集群状态

当16384个槽都有节点在处理时，集群处于上线状态(ok)；

如果有任何一个槽没有得到处理(或者某一分片的最后一个节点挂了)，那么集群处于下线状态(fail)。

如果集群超过半数以上master挂掉，无论是否有slave集群，均进入fail状态。

节点ID

每个节点在集群中都有唯一的ID，该ID是由40位的16进制字符组成，具体是节点第一次启动由linux的/dev/urandom生成。

具体信息会保存在node.cnf配置文件中(该文件有Redis Cluster自动维护，可以通过参数cluster-config-file来指定路径和名称)，如果该文件被删除，节点ID将会重新生成。

节点ID用于标识集群中的每个节点，包括指定Replication Master。只要节点ID不改变，哪怕节点的IP和端口发生了改变，Redis Cluster可以自动识别出IP和端口的变化，并将变更的信息通过Gossip协议广播给其他节点。

clusterNode结构的slots属性记录了节点负责处理那些槽。

Slots属性是一个二进制位数组(bit
array)，这个数组的长度为16384/8=2048个字节，共包含16384个二进制位。

Master节点用bit来标识对于某个槽自己是否拥有。比如对于编号为1的槽，Master只要判断序列的第二位（索引从0开始）是不是为1即可。时间复杂度为O（1）。

将所有槽的指派信息保存在clusterState.slots数组里面，程序要检查槽i是否已经被指派，又或者取得负责处理槽i的节点，只需要访问clusterState.slots[i]的值即可，复杂度仅为O（1）。

请求重定向

由于每个节点只负责部分slot，以及slot可能从一个节点迁移到另一节点，造成客户端有可能会向错误的节点发起请求。

因此需要有一种机制来对其进行发现和修正，这就是请求重定向。有两种不同的重定向场景：

a)MOVED错误
1.请求的key对应的槽不在该节点上，节点将查看自身内部所保存的哈希槽到节点ID的映射记录，节点回复一个MOVED错误。
2.需要客户端进行再次重试。

b)ASK错误
1.请求的key对应的槽目前的状态属于MIGRATING状态，并且当前节点找不到这个key了，节点回复ASK错误。ASK会把对应槽的IMPORTING节点返回给你，告诉你去IMPORTING的节点尝试找找。
2.客户端进行重试首先发送ASKING命令，节点将为客户端设置一个一次性的标志（flag），使得客户端可以执行一次针对IMPORTING状态的槽的命令请求，然后再发送真正的命令请求。
3.不必更新客户端所记录的槽至节点的映射。

节点通信

采用P2P的Gossip协议，Gossip协议的原理就是每个节点与其他节点间不断通信交换信息，一段时间后节点信息一致，每个节点都知道集群的完整信息。

(1)集群中的每个节点都会单独开辟一个TCP通道，用于节点之间彼此通信，通信端口号在基础端口上加10000；

(2)每个节点在固定周期内通过特定规则选择几个节点发送ping消息；

(3)接收到ping消息的节点用pong消息作为响应。

集群中每个节点通过一定规则挑选要通信的节点，每个节点可能知道全部节点，也可能仅知道部分节点.只要这些节点彼此可以正常通信，最终它们会达到一致的状态。

当节点出故障、新节点加入、主从角色变化、槽信息变更等事件发生时，通过不断的ping/pong消息通信，经过一段时间后所有的节点都会知道整个集群全部节点的最新状态，从而达到集群状态同步的目的。

Gossip消息

Gossip协议的主要职责就是信息交换，信息交换的载体就是节点彼此发送的Gossip消息，常用的Gossip消息可分为：

• meet消息：用于通知新节点加入。消息发送者通知接收者加入到当前集群，meet消息通信正常完成后，接收节点会加入到集群中并进行周期性的ping、pong消息交换；

• ping消息：集群内交换最频繁的消息，集群内每个节点每秒向多个其他节点发送ping消息，用于检测节点是否在线和交换彼此状态信息。ping消息发送封装了自身节点和部分其他节点的状态数据。

• pong消息：当接收到ping、meet消息时，作为响应消息回复给发送方确认消息正常通信。pong消息内部封装了自身状态数据。节点也可以向集群内广播自身的pong消息来通知整个集群对自身状态进行更新。

• fail消息：当节点判定集群内另一个节点下线时，会向集群内广播一个fail消息，其他节点接收到fail消息之后把对应节点更新为下线状态。

通信规则

Redis集群内节点通信采用固定频率(定时任务每秒执行10次)。由于内部需要频繁地进行节点信息交换，而ping/pong消息会携带当前节点和部分其他节点的状态数据，势必会加重带宽和计算的负担。

• 通信节点选择过多可以让信息及时交换，但是成本过高；

• 通信节点选择过少会降低集群内所有节点彼此信息交换频率，从而影响故障判定、新节点发现等需求的速度。

节点选择

消息交换的成本主要体现在单位时间选择发送消息的节点数量和每个消息携带的数据量。

(1)选择发送消息的节点数量

集群内每个节点维护定时任务默认每秒执行10次，每秒会随机选择5个节点找出最久没有通信的节点发送ping消息，用于Gossip信息交换的随机性。

每100毫秒都会扫描本地节点列表，如果发现节点最后一次接受pong消息的时间大于cluster_node_timeout/2，则立刻发送ping消息,防止该节点信息太长时间未更新。

根据以上规则得出每个节点每秒需要发送ping消息的数量=1+10*num(node.pong_received> cluster_node_timeout/2)，因此cluster_node_timeout参数对消息发送的节点数量影响非常大。

当我们的带宽资源紧张时，可以适当调大此参数。但是如果cluster_node_timeout过大会影响消息交换的频率从而影响故障转移、槽信息更新、新节点发现的速度。因此需要根据业务容忍度和资源消耗进行平衡。同时整个集群消息总交换量也跟节点数成正比。

消息数据量

每个ping消息的数据量体现在消息头和消息体中，其中消息头主要占用空间的字段是myslots[CLUSTER_SLOTS/8]，占用2KB，这块空间占用相对固定。

消息体会携带一定数量的其他节点信息用于信息交换。而消息体携带数据量跟集群的节点数量相关，集群越大每次消息通信的成本也就更高。