Redis集群通信机制、主备切换原理、分布式寻址算法

1. Gossip协议

Gossip协议包含多种消息，包含ping、pong、meet、fail等等。

• meet：新增节点时，集群中的某个节点会给新节点发送meet消息，让新节点加入集群，然后新节点就会开始与其它节点进行通信。
• ping：节点之间通过互相发送ping消息交换元数据，消息中包含自身节点的状态，以及所维护的集群元数据。
• pong：对ping和meeet消息做出响应，包含自己的状态和其它信息，也用于信息广播和更新。
• fail：集群中一半以上的节点去ping某个节点的时候而没有回应，集群就认为这个节点宕机了，然后去连接它的备用节点。

RedisCluster节点之间采用的是Gossip协议进行通信

2. 主备切换原理

如果一个节点认为某个节点宕机，那么会ping给其他节点，如果超过半数的节点都认为该节点宕机了，那么该节点就会变成fail。在cluster-node-timeout内，某个节点一直没有返回pong，那么就被认为fail。

对宕机的master node，会从其所有的slave node中，选举一个切换成master node。在选举之前，首先检查每个slave node与master node断开连接的时间，如果超过了cluster-node-timeout * cluster-slave-validity-factor，那么就没有资格切换成master。

每个从节点，都根据自己对master复制数据的offset，来设置一个选举时间，offset越大（复制数据越多）的从节点，选举时间越靠前，优先进行选举。所有的master node开始slave node选举投票，给要进行选举的slave进行投票，如果大部分master node（N/2 + 1）都投票给了某个从节点，那么选举通过，那个从节点可以切换成master。

3. 分布式寻址算法

3.1 哈希算法

首先计算每个请求中key的hash值，然后对节点数进行取模运算（hash(key) % N），最后确定key所要访问的节点信息，下次访问时就能直接够判断出该key所属哪个缓存服务器节点上。

一旦集群中节点数量发生变更，比如某个节点宕机，或者需要扩容。在这种情况下，整个集群中所有缓存的位置都要发生改变，并且所有缓存在一定时间内是失效的。由于大量缓存在同一时间失效，所有请求则会指向后端服务器，后端服务器将会承受巨大的压力，整个系统很有可能被压垮。（缓存雪崩）

3.2 一致性哈希算法

一致性哈希算法是对2^32取模，将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0 - 2^32-1（即哈希值是一个32位无符号整形），整个哈希环如下：

整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到 2^32-1 ，也就是说0点左侧的第一个点代表 2^32-1， 0和2^32-1 在零点中方向重合，我们把这个由2^32 个点组成的圆环称为 Hash 环。

假设我们有4台缓存服务器，服务器A、服务器B、服务器C，服务器D，那么，在生产环境中，这4台服务器肯定有自己的IP地址或主机名，我们使用它们各自的IP地址或主机名作为关键字进行哈希计算，使用哈希后的结果对2^32取模，可以使用如下公式：hash（服务器的IP地址） % 2^32，得出一个整数代表服务器A，服务器A就可以映射到这个环上。

接下来使用如下算法定位数据访问到相应服务器： 将数据key使用相同的函数hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：

这里可能会有疑问，为什么hash一致性的数据空间范围是2^32次方？
因为，Java中int的最大值是2^31-1 最小值是-2^31，232刚好是无符号整形的最大值。

为什么Java中int的最大值是2^{31-1最小值是-2}31？
因为，int的最大值最小值范围设定是因为一个int占4个字节，一个字节占8位，二进制中刚好是32位。

现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响，如下所示：

下面考虑另外一种情况，如果在系统中增加一台服务器Node X，此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X ！一般的，在一致性hash算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

然而，一致性哈希算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜（缓存的对象大部分集中缓存在某一台服务器上）。

为了解决这种热点问题，一致性哈希算法引入了虚拟节点机制，即对每一个节点计算多个hash，每个计算结果位置都放置一个此服务节点，称为虚拟节点。这样就实现了数据的均匀分布，负载均衡。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算Node A#1、Node A#2、Node A#3、Node B#1、Node B#2、Node B#3的哈希值，于是形成六个虚拟节点：

一致性哈希算法的详细解释原文链接：https://www.cnblogs.com/study-everyday/p/8629100.html

3.3 redis cluster hash slot 算法

RedisCluster有固定的16384个哈希槽（hash slot），对每个key计算CRC16值，然后对16384取模，可以获取key对应的哈希槽。

RedisCluster中每个master都会持有部分slot，比如有3个master，每个节点负责维护一部分槽以及槽所映射的键值数据。那么可能每个master持有5000多个哈希槽。哈希槽让node的增加和移除很简单，增加一个master，就将其他master的哈希槽移动部分过去，减少一个master，就将它的哈希槽移动到其他master上去。