sharding
不同节点分组服务于相互无交集的分片（sharding）
Redis Cluster 不存在单独的proxy或配置服务器
所以需要将客户端路由到目标的分片
1 数据分片（slot）
Redis Cluster 将所有的数据划分为16384 [0-16383] 个分片，每个分片负责其中一部分。
每条数据（key/value）根据K值，通过数据分布算法（一致性哈希）映射到16384 个slot中的一个。
数据分布算法
slotId = crc16(key) % 16384
客户端根据 slotId 决定将请求路由到哪个Redis 节点。
Cluster 不支持跨节点的单命令，如：sinterstore，若涉及的2个K对应的slot 在不同Node，则执行失败。
通常Redis的K带有业务意义，如：
- Product:Trade:20180890310921230001
- Product:Detail:20180890310921230001
当在集群中存储时，上述同一商品的交易和详情可能会存储在不同的节点上，进而对于这2个K 不能以原子的方式操作。
为此，Redis引入HashTag，使得数据分布算法可以根据key 的某一部分进行计算，让相关的2 条记录落到同一个数据分片
商品交易记录key：Product:Trade:{20180890310921230001} 商品详情记录key：Product:Detail:{20180890310921230001}
Redis 会根据 {} 之间的字符串作为数据分布式算法的输入。
客户端的路由
Redis Cluster的客户端相比单机Redis 需要具备路由语义的识别能力，且具备一定的路由缓存能力。
当Client 访问的K不在当前Redis节点的slots中，Redis 会返回给Client一个moved命令。并告知其正确路由信息
Client接收到moved 后，再次请求新的Redis时，此时Cluster结构又可能发生了变化。此时有可能再次返回moved。
Client 会根据moved响应，更新其内部的路由缓存信息，以便后续操作直接找到正确节点，减少交互次数。
当Cluster在数据重新分布过程中时，可通过ask命令控制客户端的路由，如下所示：
上图中，slot1 需迁移到新节点，此时若客户端已完成迁移的K，节点将相应ask告知客户端想目标节点重试。
ask V.S moved
- moved 会更新Client数据路由
- ask 只是重定向新节点，但是后续相同slot仍会路由到旧节点
迁移的过程可能会持续一段时间，这段时间某个slot的数据，同时可能存在于新旧 2 个节点。
move 操作会使Client 的路由缓存变更，若新旧节点对迁移中的slot 所有key 都回应moved，客户端的路由缓存会频繁变更。因此引入ask 类型消息，将重定向和路由缓存分离。
3 分片的迁移
在一个稳定的Redis Cluster 中，每个slot 对应的节点都是确定的。在某些情况下，节点和分片需要变更：
新的节点作为master加入；
某个节点分组需要下线；
负载不均衡需要调整slot 分布。
此时需要进行分片的迁移，迁移的触发和过程控制由外部系统完成。Redis Cluster 只提供迁移过程中需要的原语，包含下面 2 种：
节点迁移状态设置：迁移前标记源/目标节点。 key迁移的原子化命令：迁移的具体步骤。
slot 1 从节点A 迁移到B的过程
1、向节点B发送状态变更命令，将B的对应slot 状态置为importing。
2、向节点A发送状态变更命令，将A对应的slot 状态置为migrating。
3、针对A上的slot 的所有key，分别向A 发送migrate 命令，告知A 将对应的key 迁移到B。
当A节点的状态置为migrating 后，表示对应的slot 正在从A迁出，为保证该slot 数据的一致性。A此时提供的写服务和通常状态下有所区别，对于某个迁移中的slot：
如果Client 访问的key 尚未迁出，则正常的处理该key； 如果key已经迁出或者key不存在，则回复Client ASK 信息让其跳转到B处理；
当节点B 状态变成importing 后，表示对应的slot 正在向B迁入。即使B 能对外提供该slot 的读写服务，但是和通常情况下有所区别：
当Client的访问不是从ask 跳转的，说明Client 还不知道迁移。有可能操作了尚未迁移完成的，处在A上面的key，如果这个key 在A上被修改了，则后续会产生冲突。 所以对于该slot 上所有非ask 跳转的操作，B不会进行操作，而是通过moved 让Client 跳转至A执行。
这样的状态控制，保证了同一个key 在迁移之前总是在源节点执行。迁移后总是在目标节点执行，从而杜绝了双写的冲突。迁移过程中，新增加的key 会在目标节点执行，源节点不会新增key。使得迁移有界限，可以在某个确定的时刻结束。
单个key 的迁移过程可以通过原子化的migrate 命令完成。对于A/B的slave 节点，是通过主备复制，从而达到增删数据。
当所有key 迁移完成后，Client 通过 cluster setslot 命令设置B的分片信息，从而包含了迁入的slot。设置过程中会让Epoch自增，并且是Cluster 中的最新值。然后通过相互感知，传播到Cluster 中的其他节点。
failover
同Sentinel 一样，Redis Cluster 也具备一套完整的故障发现、故障状态一致性保证、主备切换机制。
1、failover的状态变迁
1）故障发现：当某个master 宕机时，宕机时间如何被集群其他节点感知。
2）故障确认：多个节点就某个master 是否宕机如何达成一致。
3）slave选举：集群确认了某个master 宕机后，如何将它的slave 升级成新的master；如果有多个slave，如何选择升级。
4）集群结构变更：成功选举成为master后，如何让整个集群知道，以更新Cluster 结构信息。
2、故障发现
Redis Cluster 节点间通过Redis Cluster Bus 两两周期性的PING/PONG 交互。当某个节点宕机时，其他Node 发出的PING消息没有收到响应，并且超过一定时间（NODE_TIMEOUT）未收到，则认为该节点故障，将其置为PFAIL状态（Possible Fail）。后续通过Gossip 发出的PING/PONG消息中，这个节点的PFAIL 状态会传播到集群的其他节点。
Redis Cluster 的节点两两通过TCP 保持Redis Cluster Bus连接，当对PING 无反馈时，可能是节点故障，也可能是TCP 链接断开。如果是TCP 断开导致的误报，虽然误报消息会因为其他节点的正常连接被忽略，但是也可以通过一定的方式减少误报。Redis Cluster 通过 预重试机制 排除此类误报：当 NODE_TIMEOUT/2 过去了，但是还未收到响应，则重新连接重发PING 消息，如果对端正常，则在很短的时间内就会有响应。
3、故障确认
对于网络分隔的情况，某个节点（B）并没有故障，但是和A 无法连接，但是和C/D 等其他节点可以正常联通。此时只会有A 将 B 标记为PFAIL 状态，其他节点认为B 正常。此时A 和C/D 等其他节点信息不一致，Redis Cluster 通过故障 确认协议 达成一致。
集群中每个节点都是Gossip 的接收者，A 也会接收到来自其他节点的Gossip 消息，被告知B 是否处于PFAIL 状态。当A收到来气其他master 节点对于 B 的PFAIL 达到一定数量后，会将B的PFAIL 状态升级为 FAIL 状态。表示B 已经确认为故障态，后面会发起slave 选举流程。
A节点内部的集群信息中，对于B的状态从PFAIL 到 FAIL 的变迁，如下图所示：
4 slave选举
先看配置项，确认该从节点是否有资格能晋升主节点。
再看偏移量，越大说明数据越多，越会成为主节点。
如果相同，看 row_id，小的竞选成功。
上图中，B是A的master，并且B 已经被集群公认是FAIL态了，那么A 发起竞选，期望成为新的master。
如果B有多个slave （A/E/F）都认知到B 处于FAIL 状态了，A/E/F 可能会同时发起竞选。当B的slave 个数 >= 3 时，很有可能产生多轮竞选失败。为了减少冲突的出现，优先级高的slave 更有可能发起竞选，从而提升成功的可能性。这里的优先级是slave的数据最新的程度，数据越新的（最完整的）优先级越高。
slave 通过向其他master发送FAILVOER_AUTH_REQUEST 消息发起竞选，master 收到后回复FAILOVER_AUTH_ACK 消息告知是否同意。slave 发送FAILOVER_AUTH_REQUEST 前会将currentEpoch 自增，并将最新的Epoch 带入到FAILOVER_AUTH_REQUEST 消息中，如果自己未投过票，则回复同意，否则回复拒绝。
5、结构变更通知
当slave 收到过半的master 同意时，会替代B 成为新的master。此时会以最新的Epoch 通过PONG 消息广播自己成为master，让Cluster 的其他节点尽快的更新拓扑结构。
当B 恢复可用之后，它手续爱你仍然认为自己是master，但逐渐的通过Gossip 协议得知A 已经替代了自己，然后降级为A的slave。
可用性和性能
Redis 集群的一致性保证（guarantee）
Redis 集群不保证数据的强一致性（strong consistency）： 在特定条件下， Redis 集群可能会丢失已经被执行过的写命令。
异步复制
使用异步复制（asynchronous replication）是 Redis 集群可能会丢失写命令的其中一个原因。
- 客户端向主节点 B 发送一条写命令
- B 执行写命令，并向客户端返回命令回复
- B 将刚执行的写命令复制给它的从节点 B1 、 B2 和 B3
主节点对命令的复制工作发生在返回命令回复之后，因为若每次处理命令请求都需要等待复制操作完成， 则主节点处理命令请求速度将极大降低，必须在性能和一致性之间取舍！
如果真的有必要， Redis 集群可能会在未来版本提供同步（synchronou）执行写命令的方法。
网络分裂
Redis 集群另外一种可能会丢失命令的情况是， 集群出现网络分裂（network partition）， 并且一个客户端与至少包括一个主节点在内的少数（minority）实例被孤立。
假设集群包含 A 、 B 、 C 、 A1 、 B1 、 C1 六个节点：A 、B 、C 为主节点， A1 、B1 、C1 分别为三个主节点的从节点， 一个客户端 Z1 。
假设集群中发生网络分裂， 那么集群可能会分裂为两方， 大多数（majority）的一方包含节点 A 、C 、A1 、B1 和 C1 ， 而少数（minority）的一方则包含节点 B 和客户端 Z1 。
在网络分裂期间， 主节点 B 仍然会接受 Z1 发送的写命令：
- 若网络分裂时间很短， 则集群会继续正常运行
- 但若网络分裂出现时间长， 使得大多数一方将 B1 设置为新master， 并使用 B1 代替了原主节点 B ， 则 Z1 发送给主节点 B 的写命令将丢失。
在网络分裂出现期间， Z1 可以向主节点 B 发送写命令的最大时间是有限制的， 这一时间限制称为节点超时时间（node timeout）， 是 Redis 集群的一个重要的配置选项：
- 对于大多数一方来说， 如果一个主节点未能在节点超时时间所设定的时限内重新联系上集群， 那么集群会将这个主节点视为下线， 并使用从节点来代替这个主节点继续工作
- 对于少数一方， 如果一个主节点未能在节点超时时间所设定的时限内重新联系上集群， 那么它将停止处理写命令， 并向客户端报告错误
Redis Cluster 还提供了一些方法可以提升性能和可用性。
1、Redis Cluster的读写分离
对于读写分离的场景，应用对于某些读请求允许舍弃一定的数据一致性，以换取更高的吞吐量。此时希望将读请求交给slave处理，以分担master的压力。
通过分片映射关系，某个slot 一定对应着一个master节点。Client 通过moved 命令，也只会路由到各个master中。即使Client 将请求直接发送到slave上，也会回复moved 到master去处理。
为此，Redis Cluster 引入了readonly 命令。Client 向slave发送该命令后，不再moved 到master处理，而是自己处理，这成为slave的readonly 模式。通过readwrite命令，可以将slave的readonly模式重置。
2、master单点保护
假如Cluster 的初始状态如下所示：
上图中A、B两个master 分别有自己的slave，假设A1 发生宕机，结构变为如下所示：
此时A 成为了单点，一旦A 再次宕机，将造成不可用。此时Redis Cluster 会把B 的某个slave （如 B1 ）进行副本迁移，变成A的slave。如下所示：
这样集群中每个master 至少有一个slave，使得Cluster 具有高可用。集群中只需要保持 2*master+1 个节点，就可以保持任一节点宕机时，故障转移后继续高可用。
