Cluster 实现原理
65 哥：数据切片后，需要将数据分布在不同实例上，数据和实例之间如何对应上呢？
Redis 3.0 开始，官方提供了 Redis Cluster 方案实现了切片集群，该方案就实现了数据和实例的规则。Redis Cluster 方案采用哈希槽（Hash Slot，接下来我会直接称之为 Slot），来处理数据和实例之间的映射关系。
跟着「码哥字节」一起进入 Cluster 实现原理探索之旅…...
将数据分成多份存在不同实例上
集群的整个数据库被分为 16384 个槽（slot），数据库中的每个键都属于这 16384 个槽的其中一个，集群中的每个节点可以处理 0 个或最多 16384 个槽。
Key 与哈希槽映射过程可以分为两大步骤：
- 根据键值对的 key，使用 CRC16 算法，计算出一个 16 bit 的值；
- 将 16 bit 的值对 16384 执行取模，得到 0 ～ 16383 的数表示 key 对应的哈希槽。
Cluster 还允许用户强制某个 key 挂在特定槽位上，通过在 key 字符串里面嵌入 tag 标记，这就可以强制 key 所挂在的槽位等于 tag 所在的槽位。
哈希槽与 Redis 实例映射
65 哥：哈希槽又是如何映射到 Redis 实例上呢？
在 部署集群的样例中通过 cluster create 创建，Redis 会自动将 16384 个 哈希槽平均分布在集群实例上，比如 N 个节点，每个节点上的哈希槽数 = 16384 / N 个。
除此之外，可以通过 CLUSTER MEET 命令将 7000、7001、7002 三个节点连在一个集群，但是集群目前依然处于下线状态，因为三个实例都没有处理任何哈希槽。
可以使用 cluster addslots 命令，指定每个实例上的哈希槽个数。
65 哥：为啥要手动制定呢？
能者多劳嘛，加入集群中的 Redis 实例配置不一样，如果承担一样的压力，对于垃圾机器来说就太难了，让牛逼的机器多支持一点。
三个实例的集群，通过下面的指令为每个实例分配哈希槽：实例 1负责 0 ～ 5460 哈希槽，实例 2 负责 5461~10922 哈希槽，实例 3 负责 10923 ～ 16383 哈希槽。
redis-cli -h 172.16.19.1 –p 6379 cluster addslots 0,5460 redis-cli -h 172.16.19.2 –p 6379 cluster addslots 5461,10922 redis-cli -h 172.16.19.3 –p 6379 cluster addslots 10923,16383
键值对数据、哈希槽、Redis 实例之间的映射关系如下：
Redis 键值对的 key 「码哥字节」「牛逼」经过 CRC16 计算后再对哈希槽总个数 16394 取模，模数结果分别映射到实例 1 与实例 2 上。
切记，当 16384 个槽都分配完全，Redis 集群才能正常工作。
复制与故障转移
65 哥：Redis 集群如何实现高可用呢？Master 与 Slave 还是读写分离么？
Master 用于处理槽，Slave 节点则通过《Redis 主从架构数据同步》方式同步主节点数据。
当 Master 下线，Slave 代替主节点继续处理请求。主从节点之间并没有读写分离， Slave 只用作 Master 宕机的高可用备份。
Redis Cluster 可以为每个主节点设置若干个从节点，单主节点故障时，集群会自动将其中某个从节点提升为主节点。
如果某个主节点没有从节点，那么当它发生故障时，集群将完全处于不可用状态。
不过 Redis 也提供了一个参数cluster-require-full-coverage可以允许部分节点故障，其它节点还可以继续提供对外访问。
比如 7000 主节点宕机，作为 slave 的 7003 成为 Master 节点继续提供服务。当下线的节点 7000 重新上线，它将成为当前 70003 的从节点。
故障检测
65 哥：在《Redis 高可用篇：Sentinel 哨兵集群原理》我知道哨兵通过监控、自动切换主库、通知客户端实现故障自动切换，
Cluster又如何实现故障自动转移呢？
一个节点认为某个节点失联了并不代表所有的节点都认为它失联了。只有当大多数负责处理 slot 节点都认定了某个节点下线了，集群才认为该节点需要进行主从切换。
Redis 集群节点采用 Gossip 协议来广播自己的状态以及自己对整个集群认知的改变。
比如一个节点发现某个节点失联了 (PFail)，它会将这条信息向整个集群广播，其它节点也就可以收到这点失联信息。
关于 Gossip 协议可阅读悟空哥的一篇文章：《病毒入侵，全靠分布式》
如果一个节点收到了某个节点失联的数量 (PFail Count) 已经达到了集群的大多数，就可以标记该节点为确定下线状态 (Fail)，然后向整个集群广播，强迫其它节点也接收该节点已经下线的事实，并立即对该失联节点进行主从切换。
故障转移
当一个 Slave 发现自己的主节点进入已下线状态后，从节点将开始对下线的主节点进行故障转移。
- 从下线的 Master 及节点的 Slave 节点列表选择一个节点成为新主节点。
- 新主节点会撤销所有对已下线主节点的 slot 指派，并将这些 slots 指派给自己。
- 新的主节点向集群广播一条 PONG 消息，这条 PONG 消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。
- 新的主节点开始接收处理槽有关的命令请求，故障转移完成。
选主流程
65 哥：新的主节点如何选举产生的？
- 集群的配置纪元 +1，是一个自曾计数器，初始值 0 ，每次执行故障转移都会 +1。
- 检测到主节点下线的从节点向集群广播一条
CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息，要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票。
- 这个主节点尚未投票给其他从节点，那么主节点将向要求投票的从节点返回一条
CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，表示这个主节点支持从节点成为新的主节点。
- 参与选举的从节点都会接收
CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，如果收集到的票 >= (N/2) + 1 支持，那么这个从节点就被选举为新主节点。
- 如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止。
跟哨兵类似，两者都是基于 Raft 算法来实现的，流程如图所示：
用表保存键值对和实例的关联关系可行么
65 哥，我来考考你：“Redis Cluster 方案通过哈希槽的方式把键值对分配到不同的实例上，这个过程需要对键值对的 key 做 CRC 计算并对 哈希槽总数取模映射到实例上。如果用一个表直接把键值对和实例的对应关系记录下来（例如键值对 1 在实例 2 上，键值对 2 在实例 1 上），这样就不用计算 key 和哈希槽的对应关系了，只用查表就行了，Redis 为什么不这么做呢？”
使用一个全局表记录的话，假如键值对和实例之间的关系改变（重新分片、实例增减），需要修改表。如果是单线程操作，所有操作都要串行，性能太慢。
多线程的话，就涉及到加锁，另外，如果键值对数据量非常大，保存键值对与实例关系的表数据所需要的存储空间也会很大。
而哈希槽计算，虽然也要记录哈希槽与实例时间的关系，但是哈希槽的数量少得多，只有 16384 个，开销很小。
