三，集群

广义上的集群，是指多个机器，构成的分布式系统，就可以称为一个集群，所以前面的主从复制和哨兵模式也可以看作是一个集群。

而侠义上的集群，是redis提供的集群模式。这个集群模式之下，主要是解决存储空间不足的问题。

在redis哨兵模式中，本质还是redis数据节点存储数据，其中就要求主节点/从节点来存储数据的全集。为了提高 数据存储的容量，这时就引入多台机器，每台机器只存储一部分数据。

假设有1TB的数据需要存储： 拿两台机器来存储 ，每台机器需要存储512GB。

拿三台机器来存储，每台机器需要存储300多GB。

拿四台机器来存储，每台机器需要存储 256GB......

但是还存在一个问题，如果使用三台机器来存储1TB的数据，如果某个机器挂了怎么办，所以我们还需要为每个机器 再分配几个从节点。

这三组机器的数据都是不同的，每个 slave都是mster的备份，当master挂了，slave就会晋升为master。

如上图所示，每个虚线框就可以看作是一个分片（Sharding）。

重点面试题：

三种主流的分片算法：哈希求余，一致性哈希算法，哈希槽分区算法。

1，哈希求余

借助hash函数，把一个key映射成为 一个数字，在对数组长度（这里就是分片的个数）进行求余，就可以得到这个key是在哪个分片中。

比如现在有3个分片，编号为0，1，2

此时就可以针对要查询的数据（或插入的数据）计算hash值（比如可以使用md5算法），再把这个值余上分片的个数，此时就会得到一个数字，这个数字就表示这个数据在哪个分片中。

但是当总体的数据增长时，就需要扩容，引入更多的分片，此时分片的个数就变了。

如果发现某个数据在扩容之后，不该待在当前的分片中，那么就需要重新分配数据（数据搬运）。这里涉及到的数据搬运不仅仅是主节点进行，从节点也需要进行。

这种方式开销极大，往往不能再生产环境上操作的，搬运成本比较大。

数据搬运成本大的原因：这种哈希求余的方式，导致数据是交替出现的，比如100出现在0号分片，101出现在1号分片，102出现在2号分片，103又是0号分片 。这就导致在扩容之后，分片个数增长，就会有 大量的数据需要进行搬运。

2，一致性哈希算法

这种方式可以降低上述的"搬运开销"。

key映射到分片序号的过程不再是简单的求余了，而是改成以下过程：

第一步：把0~2^32-1这个数据空间，映射到一个圆环上，按照顺时针方向增长。

第二步：假设分成3个分片，将分片放到对应的位置上

每个分片就会对应一个值，比如0号分片对应的值就是0

第三步：假定有一个key，计算得到的hash值为H，如何计算这个key是在哪个分区？此时H会在圆环上的某个位置，从这个位置开始，顺时针向下找，找到的第一个分片，就是这个key所属 的分片。

这就相当于，N个分片，把整个圆环分成N个区域，key的hash值落在哪个区域，它就属于哪个分片。

因此在 一致性哈希这样的设定下，把数据交替出现，改进成了连续出现。

在这种情况下，如何进行扩容，假设新增一个分片。

如下图所示，在圆环上找一个位置，设为3号分片的位置。该部分本来是0号分片上的，这样一来，只需将0号分片上的这段数据搬运到3号分片上即可，其他分片上的数据不需要搬运。

这种搬运的成本是有的，但是比之前哈希求余的方式低了不少。

这种方式，虽然搬运的成本降低了，但是也导致了各个分片上的数据量不均匀，称作数据倾斜。

3，哈希槽分区算法

这是Redis真正采用的分片算法。

哈希槽计算公式：hsah_slot=hash(key）%16384，一共有16384个槽。

假设现在有3个分片，一种分配方式如下：

0号分片：[0,5461]，共5462个槽位。

1号分片：[5462,10923]，共5462个槽位。

2号分片：[5463,16384]，共5460个槽位。

这里只是分片的一种，分片可以很灵活。每个分片持有的槽位号：可以是连续的，也可以是不连续的。

此处 ，每个分片都会使用一个位图结构，来表示该分片有多少槽位号，16384个bit位，用每一位的0/1表示是否持有这个槽位。

现在假设要新增一个分片，那么此时可以从0号分片，1号分片，2号分片上分别截取一部分出来，放到新的分片上，这样就可以解决数据倾斜的问题。

4，故障处理

如果某个主节点挂了，此时就会把该主节点旗下的某一个从节点提拔为主节点，保证我们的redis能够正常工作。

故障判定

识别某个节点是否挂了。

节点A给节点B发送ping包，B就会给A返回一个pong包。ping和pong除了携带message type属性之外，其他部分都是一样的。还会包含集群的配置信息（该节点的id，该节点属于哪个分片，该节点是主节点还是从节点，从属于哪个主节点，持有哪些slot槽位）。

每个节点，每秒钟都会给一些 随机的节点发送ping包，而不是给所有节点都发送。这样设定设为了在节点很多的时候，心跳包也会非常多。

当节点A向节点B发送ping包后，B不能如期回应的时候，此时A就会尝试重置和B的TCP连接，看能否连接成功，如果连接失败，就会认为B节点下线了，A就会把B设为PFAIL状态（相当于主观下线）。

A判定B为PFAIL后，会通过redis内置的Gossip协议，和其他节点进行沟通，向其他节点确认B的状态。（每个 节点都会维护一个自己的下线列表，由于视角不同，每个节点的下线列表也就不同）。

此时A发现很多节点也认为B为PFAIL，并且数目超过集群节点个数的一半，那么A就会把B标记为PFAIL（相当于客观下线），并且把这个消息同步给其他节点（其他节点收到后，也会把B标记为PFAI）。

以下三种情况会出现集群宕机：

某个分片，所有的主节点和从节点都挂了。

某个分片，主节点挂了，没有从节点。

整个集群超过一半的主节点挂了。

故障迁移

还是上述的例子。

如果B是从节点挂了，那么就不需要进行故障迁移，毕竟从节点挂了，还可以通过访问同一个 分片内的主节点或者其他从节点来获取数据。

如果B是主节点，就会由B的从节点（比如C和D）发生故障迁移。重新挑选一个主节点，代替之前主节点的位置。

具体过程如下：

从节点需要判断自己是否具有参选资格，如果主节点和从节点太久没有进行通信（此时认为主节点和从节点的数据差异太大了），就失去竞选资格。

具有资格的节点，比如C和D，就会先休眠一段时间，休眠时间=500ms基础时间+【0，500ms】随机事件+排名*1000ms。offset值越大，排名就越靠前（越小）。offset表示主节点和从节点数据同步的进度。

比如C的休眠时间到了，C就会给集群中其他所有节点，进行拉票操作。但是只有主节点才有投票资格。

主节点就会把自己的票投给C节点（每个主节点只有一票），当C收到的票数超过主节点数目的一半，C就会晋升为主节点（C会自己执行slaveof no one，并且让D执行slaveof D）。

同时，C还会把自己称为主节点的消息，同步给集群中的其他节点，大家也都会更新自己保存的集群信息结构。

总之，哪个节点会成为主节点，就看哪个节点先被唤醒，哪个节点的休眠时间短，大概率就是新的主节点。

如果两个节点被唤醒的时间是差不多的，那么此时就各凭本事了，取决于网络延迟，线程调度等等因素。

上述选举的过程，称为Raft算法。