参考书籍：《深入分布式缓存》《Redis设计与实现》
本文转载自: 掘金
Redis Cluster
### 介绍
Redis 3.0以后，节点之间通过**去中心化的方式**提供了完整的sharding、replication(复制机制仍复用原有机制，只是cluster具备感知主备的能力)、failover解决方案，称为Redis Cluster。即将proxy/sentinel的工作融合到了普通的Redis节点里。
### 拓扑结构
一个Redis Cluster 由多个Redis节点组构成。**不同节点组服务的数据无交集**（每一个节点组对应数据sharding的一个分片）。节点组内部为主备两类节点，两者数据准实时一致，通过异步化的主备复制机制保证。一个节点组有且仅有一个master节点（读写服务），同时有0到多个slave节点（读服务）。
Redis Cluster通过分片的方式保存键值对，整个数据库被分为**16384个槽（slot）**，数据库中的键都属于这16384个槽中的一个，每个节点可以处理0个或最多16384个槽（**每个节点处理的槽都是不相同的**）。
下面来看下Redis Cluster的节点结构示例图：
该示例图中key-value数据全集被分成了5个slot，只是举例说明，实际Redis Cluster总共有**16384个slot**。A和B节点为master，对外提供读写服务。其中A、A1作为主备关系构成一个节点组，通过主备复制方式同步数据。A1为A的slave，A持有1/2/3三个slot数据，A1作为A的slave也持有这三个节点。同理，B1和B2作为B的slave也构成一个节点组。
通过上面Redis Cluster的节点结构示例图，可以看到两两节点通过Redis Cluster Bus交互，交互信息如下：
1. 数据分片（slot）和节点的对应关系
2. 集群中每个节点可用状态
3. 集群结构（配置）发生变更时，通过一定的协议对配置信息达成一致。数据分片的迁移、主备切换、单点master的发现和其发生主备关系的变更等均会导致集群结构的变化。
4. publish/subscribe功能在cluster版的内部实现所需要交互的信息。
Redis Cluster Bus通过单独的接口连接，bus为节点间内部通信机制，交互的是**字节序列化信息**，和client到redis服务器的字符序列化相比，**交互效率更高**。**客户端可以和集群中任一节点连接**，通过交互流程，逐步获知全集群的**数据分片映射关系**。
### 配置的一致性
对于一个去中心化的实现，**集群的拓扑结构并不存在在单独的配置节点上**，后者的引入同样会带来新的一致性问题。各个节点怎么就**集群拓扑结构达成一致**，Redis CLuster配置机制是怎么解决的那？Redis Cluster **通过引入两个自增的epoch变量**来使得集群配置在各个节点间达成最终一致。
#### 配置信息数据结构
Redis Cluster中的每一个节点（Node）内部都保存了集群的配置信息，存储在ClusterState中，结构如下图所示：
上面各个变量语义如下：
* clusterState记录了从集群中某个节点视角的集群配置状态
* currentEpoch表示整个集群中的最大版本号，集群信息每变更一次，版本号都会自增
* nodes是一个列表，包含了本节点所知的集群所有节点信息(clusterNode),其中包含本节点本身
* clusterNode记录了每个节点的信息，比较关键的包括该信息的版本epoch,该版本信息的描述：该节点对应的数据分片（slot）、该节点为master时的slave节点列表、当该节点为slave时对应的master节点。
* 每个节点包含一个全局唯一的NodeId
* 当数据分片在节点组之间迁移，Redis Cluster仍保持对外服务，迁移过程中，通过“分片迁移相关状态”的一组变变量来管控迁移过程
* 当集群中某个master宕机，Redis Cluster会自动发现并触发故障转移操作，将宕机master的某个slave升级为新的master（包含一组变量来控制）
可见每个节点都保存着**自己视角的集群结构**，描述数据的**分片方式、节点主备关系**，并通过**epoch作为版本号**实现集群结构信息（配置）的一致性，同时也控制着**数据迁移和故障转移**的过程。
#### 信息交互
去中心架构不存在统一配置中心，节点对集群认知来自节点间信息交互，信息交互通过Redis Cluster Bus（端口独立）完成。交互信息结构如下图所示：
clusterMsg的**type字段指明了消息的类型**，配置信息的一致性达成主要依靠PING和PONG两种类型的msg。每个节点向其它节点频繁地周期性发送PING消息并接收PONG消息。在**交互信息的Gossip部分**，包含了发送者节点或者接收者节点所知的其它节点信息，接收者根据这些信息更新自己对集群的认识。
对于规模较大的集群，**PING/PONG频繁交互**都带有整个集群结构信息会造成极大网络负担。于是Redis Cluster每次PING/PONG包中，只包含随机选取的部分节点信息，这样短时间几次交互后，集群状态也会很快达成一致。
#### 一致性的达成
当Cluster不发生变化时，各节点通过gossip协议几轮交互之后得知Cluster的结构信息，达到一致状态。对于故障转移、分片迁移等情况会导致cluster结构发生变更，优先得知变更的节点**利用epoch变量将自己最新信息扩散到集群**，达到最终一致。
* clusterNode的epoch属性描述粒度是单个节点（某个节点的数据分片、主备信息版本）
* clusterState的currentEpoch属性的粒度是整个集群，用来辅助epoch自增地生成。由于currentEpoch信息也是维护在各个节点，Redis Cluster在结构发生变更时，通过一定时间窗口控制和更新规则，保证每个节点的currentEpoch都是最新的。
更新遵循规则如下：
* 当某个节点率先知道信息变更时，这个节点的currentEpoch自增使之成为集群中的最大值，再用自增后的currentEpoch作为新的epoch版本。
* 当某个节点收到比自己更大的currentEpoch，则更新自己的currentEpoch
* 当收到的Redis Cluster Bus消息中的某个节点的epoch值大于自身的epoch的时候，则将自身的映射信息更新为消息的内容
* 当收到的Redis Cluster Bus消息中某个节点信息未包含在自身中，则将其加入到自身配置
上述规则保证了**信息的更新始终是单向的**，**朝着epoch值更大的信息收敛**，同时epoch也随着每次配置变更时currentEpoch的自增而单向增加，确保各节点信息更新方向的稳定。
### sharding
**不同节点分组服务于相互无交集的数据子集(分片,sharding)**。因为Redis Cluster不存在单独的proxy和配置服务器，需要将客户端的请求正确的路由到对应的分片。
#### 数据分片
Redis Cluster将所有的数据划分为16384个分片(slot),每个分片负责其中一部分。**每一条数据(key-value)根据key值通过数据分布算法映射到16384个slot中的一个**。数据分布算法如下：
slotId = crc16(key)%16384
客户端根据**slotId**决定将请求路由到哪个Redis 节点。**cluster不支持跨节点的单命令**。例如SINTERSTORE，如果涉及的两个key对应的slot分布在不同的node，则操作失败。
通常key具备一定的业务含义，例如：
-A商品交易记录的key值:product\_trade\_prod123
-A商品交易明细的key值:product\_detail\_prod123
上面两个key根据数据分布算法计算出的slotId可能分布在不同的slot中，当需要一个命令中操作这两条关联比较强的数据时，则不能以原子方式操作。为了解决这个问题，Redis引入了**HashsTag（可以根据key的某一部分计算）**，使得相关记录放在同一分片。上面举例的key可以改成如下所示：
-A商品交易记录的key值:product\_trade\_{prod123}
-A商品交易明细的key值:product\_detail\_{prod123}
可以看到Redis会以{}\color{red}{\{\}}{}之间的字符串作为数据分布算法的输入。
#### 客户端的路由
Redis Cluster的客户端相比单机的Redis具备**路由语义的识别能力**和**路由缓存能力**。
当client访问的key不在对应节点(例如A)，则会收到一个**moved命令**，告知其正确的路由信息(假设是B)。如下图所示：
从client接收到moved命令后，再次向moved响应中指向的B节点发送期间，如果发生了**分片迁移**，使B节点也不是正确的节点，此时client会再次收到B响应的moved。client会根据moved响应更新内部路由缓存信息，以便下次能够直接路由到正确节点，降低交互次数。
当cluster在slot迁移过程中时，可通过ask命令控制客户端路由，如下图所示：
上图可见，客户端请求节点A的key存储在slot2上，请求A节点时，slot2已不在节点A（slot2已迁移到B节点），则节点给client一个**ask转向命令**（例如ASK 2 127.0.0.1:7003）,告诉client可以尝试到ask命令返回中的节点请求尝试。然后客户端首先会**向B节点发送asking命令**(打开发送该命令的客户端的REDIS\_ASKING标识)，之后再重新发送需要执行的命令到B节点，B节点会执行如下图所示的执行过程：
从上面流程图可以看出ASKING标识的作用，当判断节点正在导入slot2并且客户端带有ASKING标识，则会执行命令，否则会返回moved命令。另外需要注意的是客户端的REDIS\_ASKING标识是一个一次性标识(执行一次后客户端的REDIS\_ASKING标识就会被移除)。
ask命令和moved命令的区别：
* 返回的场景不一样。client访问的key不在节点slots中，返回moved命令；如果正在迁移中返回ask命令。
* moved命令会**更新client数据路由缓存**(后续相同操作会直接定位到目标节点)。ask命令**只是重定向到新节点**。(不会更新客户端路由缓存，后续相同slot操作仍路由到旧节点)
迁移过程可能持续一段时间，这段时间某个slot数据可能分布在新旧两个节点各分布一部分，由于moved操作会使客户端路由缓存变更，如果新旧节点对迁移中的slot所有的key都回应moved，client的路由缓存可能会频繁变动。因此引入ask类型消息，**将重定向和路由缓存更新分离**。
#### 分片迁移
稳定Redis Cluster下每一个slot对应的节点是确定的。但在一些情况下，节点和分片的对应关系需要发生变更：
* 新的节点作为master加入
* 某个节点分组需要下线
* 负载不均需要调整slot分布
此时的话需要分片的迁移。迁移的触发和过程控制由外部系统完成，Redis Cluster只提供迁移过程需要的原语。原语主要包含两种：
* **节点迁移状态设置，迁移前标记源/目标节点**
* **key迁移的原子化命令：迁移的具体步骤**
下面我们来举个例子，slot1从节点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提供读写服务的行为和通常状态有所区别，对于某个迁出的slot：
* **若client访问的key未迁移出，正常处理该key**
* **若key已经迁移出或者不存在该key，则回复客户端ASK信息让其跳转到B执行**
当节点B的状态设置为IMPORTING后，表示对应的slot正在向B迁入。即使B仍能对外提供该slot的读写服务，但也有所区别：
* 当client请求不是从ASK跳转过来，client还不知道迁移在进行，很可能操作了一个尚未迁移完成正处在A上的key，此时key在A上被修改了，则B和A的修改值将来会发生冲突。**所以对于该slot上的非ASK跳转而来的操作，B不会进行处理，而是通过MOVED命令让client跳转至A执行**。
这样状态控制保证同一个key在迁移前总是在源节点执行，迁移后总是在目标节点执行，杜绝了两边同时写导致值冲突的问题。并且迁移过程中新增的key总是在目标节点执行(原节点不会再新增key)，使迁移过程时间有界，可以确定在某个时刻结束。
单个key的迁移过程通过原子化的MIGRATE命令(完成数据传输到B、等待B接收完成、在A上删除该key的动作)。A和B各自slave通过主备复制同步master的的增删数据。
当所有key迁移完成，client**通过CLUSTER SETSLOT命令设置B的分片信息，让其包含迁移的slot**。设置过程**自增epoch**(当前集群最大epoch)，然后利用epoch变量将自身信息扩散到整个集群(上面所述的一致性达成)。
### failover
和sentinel一样，Redis Cluster也有一套完整节点故障发现、故障状态一致性保证、主备切换机制，我们下面来看下。
#### failover的状态变迁
1.**故障发现**：当某个master宕机时，如何被集群其它节点感知
2.**故障确认**：多个节点就某个master是否宕机如何达成一致
3.**slave选举**：集群确认某个master宕机后，如何将它的slave升级为新的master；多个slave，如何选择升级
4.**集群结构变更**：成功选举的slave升级为master后，如何让全集群知道以更新集群结构信息
#### 故障发现
Redis Cluster节点间通过Redis Cluster Bus**两两周期性地PING/PONG交互**，当某个节点宕机，其它发向它的PING消息将无法及时响应，**当PONG响应超过一定时间（NODE\_TIMEOUT）未收到，则认为该节点故障**，将其置为**PFAIL**（**POSSIBLE FAIL**）状态。后续通过Gossip发出的PING/PONG消息中，这个节点的PFAIL状态会传播到集群其它节点。
Redis Cluster节点间两两通过TCP保持Redis Cluster Bus连接，当PING无PONG回复，可能是**节点故障**，也可能是**TCP连接断开**。如果是TCP连接断开导致的响应超时将会产生误报，虽然误报消息同样会因为其它节点连接正常被忽略，但这种误报是可以通过一定方式尽可能避免的。Redis Cluster通过**预重试机制**排除此类误报,当NODE\_TIMEOUT/2时间内未收到回应，则重新连接重发PING消息，如果在短时间内就有响应，则说明对端正常。
#### 故障确认
在网络分隔的情况下,某节点并没有故障，但是和A无法连接，但是和C、D等其它节点可以正常连接，此时只会有A将B标记为**PFAIL状态**,其它节点认为B正常。此时A和C/D等其它节点信息不一致，Redis Cluster通过故障确认协议达成一致。
集群中的每个节点都是Gossip的接收者，A也会接收其它节点的Gossip消息，被告知B是否处于FFAIL状态。当A接收到其它master节点对于B的PFAIL达到一定数量以后，会将B的PFAIL状态升级为**FAIL状态**。表示B已经确认为故障状态，后面会发起slave选举流程。
A节点内部的集群信息中B的状态由PFAIl转为FAIl的的变迁流程图如下所示:
#### slave选举
上图中B是A的master,并且B已经被集群公认为FAIL状态了，那么A发起竞选期望成为新的master。
如果B有多个slave(A/E/F)都认知到B处于FAIL状态，A/E/F可能会同时发起竞选。当B的**slave个数大于等于3**的时候，很有可能发起多轮竞选失败。**为了减少冲突，优先级最高（数据越新，也就是数据最完整的优先级最高）的slave更有可能发起竞选，从而提升成功的可能性**。
slave发送FAILOVER\_AUTH\_REQUEST消息竞选之前会将currentEpoch自增并将最新的Epoch带入到FAILOVER\_AUTH\_REQUEST消息中。slave通过向其它master发送**FAILOVER\_AUTH\_REQUEST**消息发起竞选，master收到后回复**FAILOVER\_AUTH\_ACK**消息告知是否同意，如果未投过票则回复同意，否则回复拒绝。
#### 结构变更通知
当slave收到超过半数master同意回复，则替代B成为新的master，此时它会以最新的epoch通过PONG消息广播自己成为master的信息，让集群其它节点尽快更新拓扑结构。
B恢复可用后，刚开始仍然认为自己是master，但逐渐通过Gossip协议得知A替代了自己之后降级为A的slave。
### 可用性和性能
Redis Cluster还提供了一些手段提升性能和可用性。
#### Redis Cluster的读写分离
对于有读写分离需求的场景，应用对于某些读的请求允许舍弃一定的数据一致性来换取更高的吞吐量。此时希望将读的请求交由slave处理以分担master的压力。
数据分片映射关系中，**slot对应的节点一定是一个master**，客户端通过moved消息将请求路由到各个master。即便客户端将请求直接发送到slave，slave也会回复moved到master的响应。
为此，Redis Cluster引入了READONLY命令。客户端向slave发送该命令后，slave对于读操作不再moved到master而是直接处理，称为**slave的READONLY模式**。通过**READWRITE命令**可将slave的readonly模式重置。
#### master单点保护
对于master的单点保护我们来举个例子，假设集群初始结构如下图所示：
A、B两个master分别有1个和2个自己的slave。假设A1发生宕机，集群结构会变成如下所示：
此时A成为了单点，一旦A发生宕机，将会造成不可用。此时Redis Cluster会将B的某一个slave（假设是B1）进行副本迁移，让B1变成A的slave，副本迁移后的结构如下图所示：
这使集群中的每个master至少有一个slave，那么集群只需要保持**2\*master+1**个节点就可以在任一节点宕机后仍能通过迁移**自动维持高可用**。