1. Redis Cluster

1.1 Redis集群方案的演变

大规模数据存储系统都会面临的一个问题就是如何横向拓展。当你的数据集越来越大，一主多从的模式已经无法支撑这么大量的数据存储，于是你首先考虑将多个主从模式结合在一起对外提供服务，但是这里有两个问题就是如何实现数据分片的逻辑和在哪里实现这部分逻辑？业界常见的解决方案有两种，一是引入Proxy层来向应用端屏蔽身后的集群分布，客户端可以借助Proxy层来进行请求转发和Key值的散列从而进行进行数据分片，这种方案会损失部分性能但是迁移升级等运维操作都很方便，业界Proxy方案的代表有Twitter的Twemproxy和豌豆荚的Codis；二是smart client方案，即将Proxy的逻辑放在客户端做，客户端根据维护的映射规则和路由表直接访问特定的Redis实例，但是增减Redis实例都需要重新调整分片逻辑，如何使得客户端感知到集群的变化从而调整内存中维护的路由表呢，要么定时去感知，要么引入一个第三方协调服务，常见的就是Zookeeper。

1.2 Redis Cluster 简介

Redis 3.0 版本开始官方正式支持集群模式，Redis集群模式提供了一种能将数据在多个节点上进行分区存储的方法，采取了和上述两者不同的实现方案--去中心化的集群模式，集群通过分片进行数据共享，分片内采用一主多从的形式进行副本复制，并提供复制和故障恢复功能。在官方文档 Redis Cluster Specification中，作者详细介绍了官方集群模式的设计考量，主要有如下几点：

下图是一个三主三从的 Redis Cluster，三机房部署（其中一主一从构成一个分片，之间通过异步复制同步数据，一旦某个机房掉线，则分片上位于另一个机房的 slave 会被提升为 master 从而可以继续提供服务） ；每个 master 负责一部分 slot，数目尽量均摊；客户端对于某个 Key 操作先通过公式计算（计算方法见下文）出所映射到的 slot，然后直连某个分片，写请求一律走 master，读请求根据路由规则选择连接的分片节点。

1.3 三种集群方案的优缺点

2. 哈希槽

2.1 什么是哈希槽

Redis Cluster 中，数据分片借助哈希槽 (下文均称 slot) 来实现，集群预先划分 16384 个 slot，对于每个请求集群的键值对，根据 Key 进行散列生成的值唯一匹配一个 slot。Redis Cluster 中每个分片的 master 负责 16384 个 slot 中的一部分，当且仅当每个 slot 都有对应负责的节点时，集群才进入可用状态。当动态添加或减少节点时，需要将 16384 个 slot 做个再分配，slot 中的键值也要迁移。

2.2 哈希槽计算方法

//计算公式
HASH_SLOT = CRC16(key) mod 16384

但是上述计算方法实际采用时，做了一些改变，改变的目的是为了支持哈希标签 (Hash Tag) 。哈希标签是确保两个键都在同一个 slot 里的一种方式。为了实现哈希标签，slot 是用另一种不同的方式计算的。简单来说，如果一个键包含一个 “{…}” 这样的模式，只有 { 和 } 之间的字符串会被用来做哈希以获取 slot。但是由于可能出现多个 { 或 }，计算的算法如下：

#最终的计算方法
def HASH_SLOT(key)
	#如果key中包含{...}这样的形式，则取第一次出现{...}之间的内容进行散列
	s = key.index "{"
  if s
		e = key.index "}",s+1
    if e && e != s+1
    	key = key[s+1..e-1]
    end
	end
  crc16(key) % 16384
end

2.3 哈希槽的内部实现

Redis 集群中每个节点都会维护集群中所有节点的 clusterNode 结构体，其中的 slots 属性是个二进制位数组，长度为 2048 bytes，共包含 16384 个 bit 位，节点可以根据某个 bit 的 0/1 值判断对应的 slot 是否由当前节点处理。每个节点通过 clusterStats 结构体来保存从自身视角看去的集群状态，其中 nodes 属性是一个保存节点名称和 clusterNode 指针的字典，而 slots 数组是一个记录哪个 slot 属于哪个 clusterNode 结构体的数组。

typedef struct clusterState {
  ... ...
    // 保存集群节点的字典，键是节点名字，值是clusterNode结构的指针
    dict *nodes;          /* Hash table of name -> clusterNode structures */
  // 槽和负责槽节点的映射
    clusterNode *slots[CLUSTER_SLOTS];
  ... ...
} clusterState;

typedef struct clusterNode {
  ... ...
    unsigned char slots[CLUSTER_SLOTS/8]; /* slots handled by this node */
    int numslots;   /* Number of slots handled by this node */
  ... ...
} clusterNode;

完整的映射关系如图

2.4 哈希槽的迁移

线上集群因为扩容和缩容操作，经常需要迁移 slot 对数据进行重新分片，原生的 Redis Cluster 可以借助 redis-trib 工具进行迁移。

slot 在迁移过程有两个状态，在迁出节点会对该 slot 标记为 MIGRATING，在迁入节点会对该 slot 标记为 IMPORTING 。当该 slot 内的 Key 都迁移完毕之后，新的 slot 归属信息都进过消息协议进行传播，最终集群中所有节点都会知道该 slot 已经迁移到了目标节点，并更新自身保存的 slot 和节点间的映射关系。

3. MOVED & ASK

redis-cli 是官方提供的客户端脚本，我们可以通过 redis-cli -c -p port 命令连接任意一个 master，开始使用集群。

3.1 详解 MOVED

我们通过 redis-cli 可以发起对集群的读写请求，节点会计算我们请求的 Key 所属的 slot，一旦发现该 slot 并非由自己负责的话，会向客户端返回一个 MOVED 错误（需要注意的是集群模式下 redis-cli 不会打印 MOVED 错误而是会直接显示 Redirected，使用单机版 redis-cli 连接则可以看到 MOVED 错误），指引客户端重定向到正确的节点，并再次发送先前的命令，得到正确的结果。

//cluster 模式
10.72.227.3:6380> set gfdsdf sdf
-> Redirected to slot [6901] located at 10.72.227.2:6381
OK
//stand alone 模式
192.168.0.16:6379> set myKey myValue
(error) MOVED 16281 192.168.0.14:6379
192.168.0.16:6379> get myKey
(error) MOVED 16281 192.168.0.14:6379

3.2 详解 ASK

MOVED 意为这个 slot 的负责已经永久转交给另一个节点，因此可以直接把请求准发给现在负责该 slot 的节点。但是考虑在 slot 迁移过程中，会出现属于该 slot 的一部分 Key 已经迁移到目的地节点，而另一部分 Key 还在源节点，那如果这时收到了关于这个 slot 的请求，那么源节点会现在自己的数据库里查找是否有这个 Key，查到的话说明还未迁移那么直接返回结果，查询失败的话就说明 Key 已经迁移到目的地节点，那么就向客户端返回一个 ASK 错误，指引客户端转向目的地节点查询该 Key。同样该错误仅在单机版 redis-cli 连接时打印。

3.3 客户端处理

这两个错误在实际线上环境中出现频率很高，那么定制化的客户端如何处理这二者呢？如果客户端每次都随机连接一个节点然后利用 MOVED 或者 ASK 来重定向其实是很低效的，所以一般客户端会在启动时通过解析 CLUSTER NODES 或者 CLUSTER SLOTS 命令返回的结果得到 slot 和节点的映射关系缓存在本地，一旦遇到 MOVED 或者 ASK 错误时会再次调用命令刷新本地路由（因为线上集群一旦出现 MOVED 或者是 ASK 往往是因为扩容分片导致数据迁移，涉及到许多 slot 的重新分配而非单个，因此需要整体刷新一次），这样集群稳定时可以直接通过本地路由表迅速找到需要连接的节点。

4. 故障检测

跟大多数分布式系统一样，Redis Cluster 的节点间通过持续的 heart beat 来保持信息同步，不过 Redis Cluster 节点信息同步是内部实现的，并不依赖第三方组件如 Zookeeper。集群中的节点持续交换 PING、PONG 数据，消息协议使用 Gossip，这两种数据包的数据结构一样，之间通过 type 字段进行区分。

Redis 集群中的每个节点都会定期向集群中的其他节点发送 PING 消息，以此来检测对方是否存活，如果接收 PING 消息的节点在规定时间内（node_timeout）没有回复 PONG 消息，那么之前向其发送 PING 消息的节点就会将其标记为疑似下线状态（PFAIL）。每次当节点对其他节点发送 PING 命令的时候，它都会随机地广播三个它所知道的节点的信息，这些信息里面的其中一项就是说明节点是否已经被标记为 PFAIL 或者 FAIL。当节点接收到其他节点发来的信息时，它会记下那些被集群中其他节点标记为 PFAIL 的节点，这称为失效报告（failure report）。如果节点已经将某个节点标记为 PFAIL ，并且根据自身记录的失效报告显示，集群中的大部分 master 也认为该节点进入了 PFAIL 状态，那么它会进一步将那个失效的 master 的状态标记为 FAIL 。随后它会向集群广播 “该节点进一步被标记为 FAIL ” 的这条消息，所有收到这条消息的节点都会更新自身保存的关于该 master 节点的状态信息为 FAIL。

5. 故障转移（Failover)

5.1 纪元（epoch）

Redis Cluster 使用了类似于 Raft 算法 term（任期）的概念称为 epoch（纪元），用来给事件增加版本号。Redis 集群中的纪元主要是两种：currentEpoch 和 configEpoch。

5.1.1 currentEpoch

这是一个集群状态相关的概念，可以当做记录集群状态变更的递增版本号。每个集群节点，都会通过 server.cluster->currentEpoch 记录当前的 currentEpoch。

集群节点创建时，不管是 master 还是 slave，都置 currentEpoch 为 0。当前节点接收到来自其他节点的包时，如果发送者的 currentEpoch（消息头部会包含发送者的 currentEpoch）大于当前节点的currentEpoch，那么当前节点会更新 currentEpoch 为发送者的 currentEpoch。因此，集群中所有节点的 currentEpoch 最终会达成一致，相当于对集群状态的认知达成了一致。

5.1.2 currentEpoch 作用

currentEpoch 作用在于，当集群的状态发生改变，某个节点为了执行一些动作需要寻求其他节点的同意时，就会增加 currentEpoch 的值。目前 currentEpoch 只用于 slave 的故障转移流程，这就跟哨兵中的sentinel.current_epoch 作用是一模一样的。当 slave A 发现其所属的 master 下线时，就会试图发起故障转移流程。首先就是增加 currentEpoch 的值，这个增加后的 currentEpoch 是所有集群节点中最大的。然后slave A 向所有节点发起拉票请求，请求其他 master 投票给自己，使自己能成为新的 master。其他节点收到包后，发现发送者的 currentEpoch 比自己的 currentEpoch 大，就会更新自己的 currentEpoch，并在尚未投票的情况下，投票给 slave A，表示同意使其成为新的 master。

5.1.3 configEpoch

这是一个集群节点配置相关的概念，每个集群节点都有自己独一无二的 configepoch。所谓的节点配置，实际上是指节点所负责的槽位信息。

每一个 master 在向其他节点发送包时，都会附带其 configEpoch 信息，以及一份表示它所负责的 slots 信息。而 slave 向其他节点发送包时，其包中的 configEpoch 和负责槽位信息，是其 master 的 configEpoch 和负责的 slot 信息。节点收到包之后，就会根据包中的 configEpoch 和负责的 slots 信息，记录到相应节点属性中。

5.1.4 configEpoch 作用

configEpoch 主要用于解决不同的节点的配置发生冲突的情况。举个例子就明白了：节点A 宣称负责 slot 1，其向外发送的包中，包含了自己的 configEpoch 和负责的 slots 信息。节点 C 收到 A 发来的包后，发现自己当前没有记录 slot 1 的负责节点（也就是 server.cluster->slots[1] 为 NULL），就会将 A 置为 slot 1 的负责节点（server.cluster->slots[1] = A），并记录节点 A 的 configEpoch。后来，节点 C 又收到了 B 发来的包，它也宣称负责 slot 1，此时，如何判断 slot 1 到底由谁负责呢？

这就是 configEpoch 起作用的时候了，C 在 B 发来的包中，发现它的 configEpoch，要比 A 的大，说明 B 是更新的配置。因此，就将 slot 1 的负责节点设置为 B（server.cluster->slots[1] = B）。在 slave 发起选举，获得足够多的选票之后，成功当选时，也就是 slave 试图替代其已经下线的旧 master，成为新的 master 时，会增加它自己的 configEpoch，使其成为当前所有集群节点的 configEpoch 中的最大值。这样，该 slave 成为 master 后，就会向所有节点发送广播包，强制其他节点更新相关 slots 的负责节点为自己。

5.2 自动 Failover

当一个 slave 发现自己正在复制的 master 进入了已下线（FAIL）状态时，slave 将开始对已下线状态的 master 进行故障转移，以下是故障转移执行的步骤：

• 该下线的 master 下所有 slave 中，会有一个 slave 被选中。具体的选举流程为：slave 自增它的 currentEpoch 值，然后向其他 masters 请求投票，每个 slave 都向集群其他节点广播一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST 消息用于拉票，集群中具有投票权的 master 收到消息后，如果在当前选举纪元中没有投过票，就会向第一个发送来消息的 slave 返回 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，表示投票给该 slave。某个 slave 如果在一段时间内收到了大部分 master 的投票，则表示选举成功。
• 被选中的 slave 会执行 SLAVEOF no one 命令，成为新的 master
• 新的 master 会撤销所有对已下线 master 的 slot 指派，并将这些 slot 全部指派给自己
• 新的 master 向集群广播一条 PONG 消息，这条 PONG 消息可以让集群中的其他节点立即知道自己已经由 slave 变成了 master ，并且这个 master 已经接管了原本由已下线节点负责处理的 slot
• 新的 master 开始接收和自己负责处理的 slot 有关的命令请求，故障转移完成

5.3 手动 Failover

Redis 集群支持手动故障转移，也就是向 slave 发送 CLUSTER FAILOVER 命令，使其在 master 未下线的情况下，发起故障转移流程，升级为新的 master ，而原来的 master 降级为 slave。

为了不丢失数据，向 slave 发送 CLUSTER FAILOVER 命令后，流程如下：

1. slave 收到命令后，向 master 发送 CLUSTERMSG_TYPE_MFSTART 命令
2. master 收到该命令后，会将其所有客户端置于阻塞状态，也就是在 10s 的时间内，不再处理客户端发来的命令，并且在其发送的心跳包中，会带有 CLUSTERMSG_FLAG0_PAUSED 标记
3. slave 收到 master 发来的，带 CLUSTERMSG_FLAG0_PAUSED 标记的心跳包后，从中获取 master 当前的复制偏移量，slave 等到自己的复制偏移量达到该值后，才会开始执行故障转移流程：发起选举、统计选票、赢得选举、升级为 master 并更新配置

CLUSTER FAILOVER 命令支持两个选项：FORCE 和 TAKEOVER。使用这两个选项，可以改变上述的流程。

如果有 FORCE 选项，则 slave 不会与 master 进行交互，master 也不会阻塞其客户端，而是 slave 立即开始故障转移流程：发起选举、统计选票、赢得选举、升级为 master 并更新配置。

如果有 TAKEOVER 选项，则更加简单直接，slave 不再发起选举，而是直接将自己升级为 master ，接手原 master 的 slot，增加自己的 configEpoch 后更新配置。

因此，使用 FORCE 和 TAKEOVER 选项，master 可以已经下线；而不使用任何选项，只发送 CLUSTER FAILOVER 命令的话，master 必须在线。

6. 写在最后

6.1 详解 Redis 集群中的消息

搭建 Redis Cluster 时，首先通过 CLUSTER MEET 命令将所有的节点加入到一个集群中，但是并没有在所有节点两两之间都执行 CLUSTER MEET 命令，因为节点之间使用 Gossip 协议进行工作。Gossip 翻译过来就是流言，类似与病毒传播一样，只要一个人感染，如果时间足够，那么和被感染的人在一起的所有人都会被感染，因此随着时间推移，集群内的所有节点都会互相知道对方的存在。

在 Redis 集群中，节点信息是如何传播的呢？答案是通过发送 PING 或 PONG 消息时，会包含节点信息，然后进行传播的。先介绍一下 Redis Cluster 中，消息是如何抽象的。一个消息对象可以是 PING、PONG、MEET，也可以是 PUBLISH、FAIL 等。他们都是 clusterMsg 类型的结构，该类型主要由消息包头部和消息数据组成。

• 消息包头部包含签名、消息总大小、版本和发送消息节点的信息。
• 消息数据则是一个联合体 union clusterMsgData，联合体中又有不同的结构体来构建不同的消息。

PING、PONG、MEET 属于一类，是 clusterMsgDataGossip 类型的数组，可以存放多个节点的信息，该结构如下：

/* Initially we don't know our "name", but we'll find it once we connect
 * to the first node, using the getsockname() function. Then we'll use this
 * address for all the next messages. */
typedef struct {
    // 节点名字
    char nodename[CLUSTER_NAMELEN];
    // 最近一次发送PING的时间戳
    uint32_t ping_sent;
    // 最近一次接收PONG的时间戳
    uint32_t pong_received;
    // 节点的IP地址
    char ip[NET_IP_STR_LEN];  /* IP address last time it was seen */
    // 节点的端口号
    uint16_t port;              /* port last time it was seen */
    // 节点的标识
    uint16_t flags;             /* node->flags copy */
    // 未使用
    uint16_t notused1;          /* Some room for future improvements. */
    uint32_t notused2;
} clusterMsgDataGossip;

每次发送 MEET、PING、PONG 消息时，发送者都从自己的已知节点列表中随机选出两个节点（可以是主节点或者从节点），并将这两个被选中节点的信息分别保存到两个结构中。当接收者收到消息时，接收者会访问消息正文中的两个结构，并根据自己是否认识 clusterMsgDataGossip 结构中记录的被选中节点进行操作：

1. 如果被选中节点不存在于接收者的已知节点列表，那么说明接收者是第一次接触到被选中节点，接收者将根据结构中记录的IP地址和端口号等信息，与被选择节点进行握手。
2. 如果被选中节点已经存在于接收者的已知节点列表，那么说明接收者之前已经与被选中节点进行过接触，接收者将根据 clusterMsgDataGossip 结构记录的信息，对被选中节点对应的 clusterNode 结构进行更新。

有了消息之后，如何选择发送消息的目标节点呢？虽然 PING PONG 发送的频率越高就可以越实时得到其它节点的状态数据，但 Gossip 消息体积较大，高频发送接收会加重网络带宽和消耗 CPU 的计算能力，因此每次 Redis 集群都会有目的性地选择一些节点；但节点选择过少又会影响故障判断的速度，Redis 集群的 Gossip 协议选择这样的解决方案：

集群内每个节点维护定时任务默认为每秒执行10次，每秒会随机选取 5 个节点，找出最久没有通信的节点发送 PING 消息，用来保证信息交换的随机性。每 100 毫秒都会扫描本地节点列表，如果发现节点最近一次接受 PONG 消息的时间大于 cluster-node-timeout/2则立刻发送 PING 消息，这样做目的是防止该节点信息太长时间没更新，当我们宽带资源紧张时，可在 redis.conf 将 cluster-node-timeout 15000 改成 30 秒，但不能过度加大。

6.2 集群数据一致性

Redis 集群尽可能保证数据的一致性，但在特定条件下会丢失数据，原因有两点：异步复制机制以及可能出现的网络分区造成脑裂问题。

6.2.1 异步复制

master 以及对应的 slaves 之间使用异步复制机制，考虑如下场景：

写命令提交到 master，master 执行完毕后向客户端返回 OK，但由于复制的延迟此时数据还没传播给 slave；如果此时 master 不可达的时间超过阀值，此时集群将触发 failover，将对应的 slave 选举为新的master，此时由于该 slave 没有收到复制流，因此没有同步到 slave 的数据将丢失。

6.2.2 脑裂(split-brain)

在发生网络分区时，有可能出现新旧 master 同时存在的情况，考虑如下场景：

由于网络分区，此时 master 不可达，且客户端与 master 处于一个分区，并且由于网络不可达，此时客户端仍会向 master 写入。由于 failover 机制，将其中一个 slave 提升为新的 master，等待网络分区消除后，老的 master 再次可达，但此时该节点会被降为 slave 清空自身数据然后复制新的 master ，而在这段网络分区期间，客户端仍然将写命令提交到老的 master，但由于被降为 slave 角色这些数据将永远丢失。

7. 参考资料

1. Redis Cluster Specification
2. Redis cluster tutorial
3. Life in a Redis Cluster: Meet and Gossip with your neighbors
4. Redis系列九：redis集群高可用
5. Redis源码解析：27集群(三)主从复制、故障转移
6. 《Redis 设计与实现》黄建宏著