原文链接(on 20 Jul)  作者：antirez  译者：carlvine

Redis集群规范

主要属性和设计原理

Redis的集群目标

Redis集群是一个分布式的实现，具有以下目标，按设计的重要性排序：

• 高性能，并且多达1000个节点的线性可扩展性。没有代理，使用异步复制，并且在进行赋值时没有合并操作。
• 可接受程度的写安全：当客户端与大多数master节点建立连接后，系统努力（使用最优的方式）保持来自客户端的写操作。通常有小窗口，其中确认的写操作可能会丢失。当客户端在一个小的分区中，窗口丢失写操作会更大。
• 可用性：Redis集群支持网络分区——其中大部分主节点都可访问，并且不可访问的各master节点对应的从至少一个可访问。而且采用副本迁移，有多个从的主会提供一个从给没有从的主。

本文档中描述的在Redis >=3.0的版本中实现。

已实现的部分

Redis集群实现了所有Redis的非分布式版本中提供的单键命令。命令执行复杂的多键操作， 像set类型的合集或交集的命令，只要键是属于同一个节点就行。

Redis群集实现有一个散列标签的概念，能强制让特定的键存储在相同的节点。但是在手动重新散列期间，多键操作的可能不可用，而单键操作总是可用。

Redis集群不支持这样的Redis的单实例版本的多个数据库。只是有数据库0并且SELECT命令是不允许的。

客户端和服务器在Redis集群协议的角色

在Redis的群集节点负责保持数据，并持有群集的状态，其中包括映射键到正确的节点。集群节点也能自动发现其他节点，检测非工作节点，当发生失败，必要时把slave切换成master，以便在继续发生故障时，持续运作。

执行任务的所有群集节点使用的是TCP总线和二进制协议连接，称为Redis集群总线。每个节点被连接到使用群集总线的所有其他节点。节点使用Gossip协议传播有关群集的信息，以发现新节点，发送Ping报文，以确保所有其他节点工作正常，并发送必要信息触发特定条件。群集总线也用于以传播跨集群发布/订阅消息，并当用户请求来协调手工故障转移（手动故障转移是未由Redis集群故障检测器发起的故障转移，而是直接由系统管理员）。

因为集群节点不能代理请求，客户端可以使用重定向错误-MOVED和-ASK重定向到其他节点。客户端是在理论上自由将请求发送到集群中的所有节点，如果需要的话得到重定向，因此客户端不需要保持群集的状态。然而，客户端缓存键和节点之间的映射可以明显的改善性能。

Redis 集群协议中的客户端和服务器端

在 Redis 集群中，节点负责存储数据、记录集群的状态,包括键值到正确节点的映射。集群节点同样能自动发现其他节点，检测非正常工作节点， 并且在需要的时候升级slave成master来保证故障发生时持续运作。

为了执行这些任务，所有的集群节点都通过TCP总线和二进制协议连接，叫集群总线redis cluster bus。 每一个节点都通过集群总线与集群上的其余每个节点连接。节点们使用一个 gossip 协议来传播集群的信息，这样可以：发现新的节点、 发送ping包用来确保所有节点都在正常工作、在特定情况发生时发送集群消息来触发特定条件。集群总线也用于在集群中传播 发布/订阅 消息、用户请求协调手动故障转移（手动故障转移都并非由Redis的集群故障检测器启动的故障转移，而是直接由系统管理员）。

由于集群节点不能代理请求，所以客户端在接收到重定向错误 -MOVED 和 -ASK 的时候， 将命令重定向到其他节点。理论上来说，客户端是可以自由地向集群中的所有节点发送请求，在必要时候把请求重定向到其他节点，所以客户端是不需要保存集群状态。 不过客户端可以缓存键值和节点之间的映射关系，这样能明显提高指令执行的效率。

写安全

Redis 集群节点间使用异步副本备份，最后一个故障转移取得隐式合并功能，这意味着最后选举出的master数据最终替换其它副本.

通常存在一个时间窗口，可能在分片中丢失写入数据。 但是一个连接到绝大部分master节点的客户端的时间窗口，与一个连接到极小部分master节点的客户端的时间窗口 有很大的区别。

Redis 集群会努力尝试保存所有与大多数master节点连接的客户端执行的写操作，相比于与少数master节点连接的客户端执行的写操作，但以下两种情况除外，会导致失败期间在多数分片丢失写操作：

1) A写入操作能到达一个master节点，但当master节点要回复客户端的时候，这个写入有可能没有通过master-slave异步备份传播到slave节点那里。 如果在某个写入操作没有到达slave节点的时候master节点已经宕机了，那么该写入会永远地丢失掉(如果master长时间周期不可达而它的slave升级成master)。

这通常在所有情况中很难发现，master突然发生故障的情况下，由于master尝试回复客户端（写入的应答）和slave（传播写操作）在大致相同时间。然而，它是一个现实世界的故障模式。

2) 另一个理论上可能会丢失写入操作的模式是：

• A master因为分区不可达。
• 它故障转移, 它的一个slave升级成了master。
• 过一段时间之后这个节点再次变得可达。
• 一个持有过期路由表的客户端或许会在集群把这个master节点变成一个slave节点（新master节点的slave节点）之前对它进行写入操作。

实际上这是极小概率事件，这是因为，那些由于长时间无法被大多数master节点访问到的节点会被故障转移掉，将不再接受任何写入操作，当其分区修复好以后仍然会在一小段时间内拒绝写入操作好让其他节点有时间被告知配置信息的变更。这种失效模式也需要客户端的路由表还没有被更新。

通常所有节点都会尝试通过非阻塞连接尝试（non-blocking connection attempt）尽快去访问一个再次加入到集群里的节点，一旦跟该节点建立一个新的连接就会发送一个ping包过去（这足够升级节点配置信息）。这就使得一个节点很难在恢复可写入状态之前没被告知配置信息更改。

写入操作到达少数分片会有更大的丢失窗口。比如：

Redis 集群在拥有少数master节点和至少一个客户端的分片上容易丢失为数不少的写入操作，这是因为，如果master节点被故障转移到集群中多数节点那边， 那么所有发送到这些master节点的写入操作可能会丢失。

特别是一个master节点要被故障转移，必须是大多数master节点在至少 NODE_TIMEOUT 时长里无法访问到，所以如果分区在这段时间之前被修复，就没有写入操作会丢失。当分区故障持续超过 NODE_TIMEOUT，所有在少数节点一边到该时间点执行的写操作可能会丢失

，然而集群的少数节点这边，和大多数节点失联，会在 NODE_TIMEOUT 这个时间内开始拒绝往受损分区进行写入，所以在少数节点这边变得不再可用后，会有一个最大时间窗口. 因此在那时间之后将不会再有写入操作被接收或丢失。

可用性

Redis 集群在分区的少数节点那边不可用。在分区的多数节点这边假设至少有大多数可达的master节点，并且对于每个不可达master节点都至少有一个slave节点可达，在经过了( NODE_TIMEOUT +n秒)时间后，有个slave节点选举出来故障转移成master节点，这时集群又再恢复可用(故障转移通常在1-2秒内)。

这意味着 Redis 集群的设计是能容忍集群中少数节点的出错，但对于要求大量网络分片的可用性的应用来说，这并不是一个合适的解决方案。

在该示例，一个由 N 个master节点组成的集群，每个master节点都只有一个slave节点。只要有单个节点被分割出去，集群的多数节点这边仍然是可访问的。当有两个节点被分割出去后集群仍可用的概率是 1-(1/(N*2-1)) (在第一个节点故障出错后总共剩下 N*2-1 个节点，那么失去slave节点只剩master节点的出错的概率是 1/(N*2-1))。

比如一个拥有5个节点的集群，每个节点都只有一个slave节点，那么在两个节点从多数节点这边分割出去后集群不再可用的概率是 1/(5*2-1) = 0.1111，即有大约 11% 的概率。

感谢redis集群特性 副本迁移，集群在真实环境可用性提升，因为副本升级为孤立的master节点（master节点不再有副本），所以每次成功的故障转移，集群重新配置slave节点来更好地防止下次故障.

性能

在 Redis 集群中节点并不是把命令转发到负责键的节点上，而是把客户端重定向到服务一定范围内的键的节点上。 最终客户端获得一份最新的集群路由表，里面有写着哪些节点服务哪些键，所以在正常操作中客户端是直接联系到对应的节点来发送指令。

由于使用了异步复制，节点不会等待其他节点对写入操作的回复。（除非显式发送WAIT指令）

同样，由于多键指令仅限于相邻的键，如果不是重新分片，那么数据是永远不会在节点间移动的。

普通操作是可以被处理得跟在Redis单机版一样的。这意味着，在一个拥有 N 个master节点的 Redis 集群中，由于线性扩展的设计，你可以认为同样的操作在集群上的性能是Redis单机版的n倍。同时，请求通常在一次来回中被执行，客户端会保持跟节点的长连接，所以延迟指标跟在Reids 单机版情况是一样的。

为什么要避免使用合并操作

Redis 集群的设计是避免在多个节点中存在同个键值对的冲突版本，在这点上 Redis 数据模型不总是满足需要，Redis 中的值通常都是比较大的，经常可以看到列表或者有序集合中有数以百万计的元素。数据类型也是语义复杂的。传输和合并这样的值将会变成一个主要的性能瓶颈， 并且/或者可能需要应用端逻辑的引入，额外的内存来存储元数据，诸如此类。

redis集群主要组件概览

键分布模型

键空间被分割为 16384 槽（slot），事实上集群的最大master节点数量是 16384 个。（然而建议最大节点数量设置在1000）所有的master节点都负责 16384 个哈希槽中的一部分。当集群处于稳定状态时，当集群中没有在执行重配置操作(即：hash槽没有从一处移到另一处)。当集群在稳定状态，每个哈希槽都只由一个节点进行支配（不过master节点可以有一个或多个slave节点，可以在网络分区或节点失效时替换掉master节点，并且这样可以用来水平扩展读操作（这些读操作不要求实时数据））。以下是用来把键映射到哈希槽的算法（下一段落，除了哈希标签以外就是按照这个规则）：

HASH_SLOT = CRC16(key) mod 16384

CRC16的定义如下：

• 名称：XMODEM（也可以称为 ZMODEM 或 CRC-16/ACORN）
• 输出宽度：16 bit
• 多项数（poly）：1021（即x¹⁶+ x¹² + x⁵ + 1 ）
• 初始化：0000
• 反射输入字节（Reflect Input byte）：False
• 反射输出CRC（Reflect Output CRC）：False
• 输出CRC的异或常量（Xor constant to output CRC）：0000
• 输入”123456789″的输出：31C3

CRC16的16位输出中的14位会被使用（这也是为什么上面的式子中有一个对 16384 取余的操作）。

在我们的测试中，CRC16能相当好地把不同的键均匀地分配到 16384 个槽中。

注意：在本文档的附录A中有CRC16算法的实现。

键哈希标签

为了实现哈希标签（hash tags），计算hash槽有一个特殊处理，哈希标签是确保两个键都在同一个哈希槽里的一种方式。用来实现集群中多键多键操作。

为了实现哈希标签，哈希槽在一定条件下是用另一种不同的方式计算的。基本来说，如果一个键包含一个 “{…}”模式，只有 { 和 } 之间的部分字符串会用做哈希计算以获取哈希槽。但是由于可能出现多个 { 或 }，计算的算法详细说明如下：

• 当键包含一个{ 字符。
• 并且当在{ 的右边有一个 }。
• 并且当第一次出现{和第一次出现 } 之间有一个或多个字符。

然后不是直接计算键的哈希，只有在第一个 { 和它右边第一个 } 之间的内容会被用来计算哈希值。

例子：

• 比如这两个键{user1000}.following 和 {user1000}.followers 会被哈希到同一个哈希槽里，因为只有 user1000 这个子串会被用来计算哈希槽。
• 对于foo{}{bar} 这个键，整个键跟普通键一样被用来计算哈希值，因为第一个出现的 { 和右边紧接着的 } 之间没有任何字符。
• 对于foo{{bar}}zap 这个键，用来计算哈希值的是 {bar 这个子串，因为是它第一个 { 及其右边第一个 } 之间的内容。
• 对于foo{bar}{zap} 这个键，用来计算哈希值的是 bar 这个子串，因为算法会在第一次有效或无效（中间没有任何字节）的匹配到 { 和 } 的时候停止。
• 按照这个算法，如果一个键是以{} 开头的话，整个键会被用来计算哈希值。当使用二进制数据做为键名的时候，这是非常有用的。

加上哈希标签的特殊处理，下面是用 Ruby 和 C 语言实现的 HASH_SLOT 函数。

Ruby example code:

def HASH_SLOT(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

C example code:

unsigned int HASH_SLOT(char *key, int keylen) {
    int s, e; /* start-end indexes of { and } */

    /* Search the first occurrence of '{'. */
    for (s = 0; s < keylen; s++)
        if (key[s] == '{') break;

    /* No '{' ? Hash the whole key. This is the base case. */
    if (s == keylen) return crc16(key,keylen) & 16383;

    /* '{' found? Check if we have the corresponding '}'. */
    for (e = s+1; e < keylen; e++)
        if (key[e] == '}') break;

    /* No '}' or nothing between {} ? Hash the whole key. */
    if (e == keylen || e == s+1) return crc16(key,keylen) & 16383;

    /* If we are here there is both a { and a } on its right. Hash
     * what is in the middle between { and }. */
    return crc16(key+s+1,e-s-1) & 16383;
}

集群节点属性

在集群中，每个节点都有一个唯一的名字。节点名字是一个十六进制表示的160 bit 随机数，这个随机数是节点第一次启动时生成的（通常是用 /dev/urandom）。 节点会把它的ID保存在配置文件里，以后永远使用这个ID，或者至少只要这个节点配置文件没有被系统管理员删除掉，或者通过指令CLUSTER RESET强制请求硬重置(hard reset)

节点ID是用于在整个集群中标识每个节点。节点改变IP地址，没有任何必要改变节点ID。集群能检测到 IP /端口的变化，然后使用在集群总线（cluster bus）上的 gossip 协议来重新配置。

节点ID不仅是关联节点的信息，也是全局始终唯一的。 每个节点也有下面的关联信息。一些信息是具体集群节点的配置详情，并且在集群中最终一致。一些其它信息，比如节点最后ping的时间，是每个节点和其它都不同的。

每个节维护了感知集群其它节点如下信息： 每个节点的节点ID,IP和端口，一系列标识，当标识为slave对应的master节点，最后节点ping包的时间和最后收到pong回复的时间，当前节点配额(后文会解释)，连接状态和最后服务的一堆哈希槽。

详细的描述在CLUSTER NODES文档中：http://redis.io/commands/cluster-nodes

在任意节点执行 CLUSTER NODES 命令可以获得上述信息。

下面的例子是在一个只有三个节点的小集群中发送 CLUSTER NODES 命令到一个master节点得到的输出。

$ redis-cli cluster nodes
d1861060fe6a534d42d8a19aeb36600e18785e04 127.0.0.1:6379 myself - 0 1318428930 1 connected 0-1364
3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 2 connected 1365-2729
d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931 3 connected 2730-4095

在上面列出来的信息中，各个字段依次表示的是：节点ID，IP地址：端口号，标识，上一次发送 ping 指令的时间，上一次收到 pong 回复的时间，配额，连接状态，节点使用的哈希槽，上述字段的详情很快会在redis集群规范部分中全部讲清楚

集群总线

每个Redis的集群节点都有一个额外的TCP端口，用于接收来自其他Redis的集群节点连接。此端口号(普通TCP端口号的的固定偏移值)用于接收来自客户端的连接。为了Redis群集端口，加了10000到普通的命令端口。例如，如果一个Redis的节点监听端口为6379，会打开集群总线端口16379(=10000+6379)。节点到节点的通信独自使用群集总线和群集总线协议：不同类型和大小的帧组成一个二进制协议。群集总线二进制协议不公开发布，因为它的设计目的不是用这个协议和外部软件的设备交互。然而，你可以通过阅读cluster.h和cluster.c文件Redis的集群源代码获取有关群集总线协议的更多细节。

集群拓扑结构

Redis 集群是一个网状结构，每个节点都通过 TCP 连接跟其他每个节点连接。

在一个有 N 个节点的集群中，每个节点都有 N-1 个对外的 TCP 连接，和 N-1 个对内的连接。

这些 TCP 连接会永久保持，并不是按需创建的。当一个节点在集群总线中预计回复一个ping，等待足够长的时间，以标识节点不可达，它会尝试从头开始连接来刷新与节点的连接。

而Redis的群集节点形成全网状，节点使用gossip协议和一个配置更新机制，以避免在正常条件下交换节点之间太多消息，因此，交换的消息的数量不是指数。

节点握手

节点总是通过集群总线端口接受连接，甚至会回复接收到的 ping 请求，即使发送 ping 请求的节点是不可信的。 然而如果某个节点不被认为是在集群中，那么所有它发出的数据包都会被丢弃掉。

只有在两种方式下，一个节点才会认为另一个节点是集群中的一部分：

• 当一个节点使用MEET 消息介绍自己。一个 meet 消息跟一个 PING 消息完全一样，但它会强制让接收者接受自己为集群中的一部分。 只有在系统管理员使用以下命令请求的时候，节点才会发送MEET 消息给其他节点：

CLUSTER MEET ip port

• 一个已被信任的节点能通过传播gossip消息让另一个节点被注册为集群中的一部分。也就是说，如果 A 知道 B，B 知道 C，最终B会发知道C 的gossip消息给A。A 收到后就会把 C 当作是网络中的一部分，并且尝试连接 C。

这意味着，只要我们往任何连接图中加入节点，它们最终会自动形成一个完全连接图。这表示集群能自动发现其他节点，但前提是有一个由系统管理员强制创建的信任关系。

这个机制能防止不同的 Redis 集群因为 IP 地址变更或者其他网络事件而意外混合起来，从而使集群更健壮。

重定向和重分片

MOVED 重定向

一个 Redis 客户端可以自由地向集群中的任意节点（包括slave节点）发送请求。接收的节点会分析请求，如果这个命令是集群可以执行的（就是查询中只涉及一个键,或者多键在同一个哈希槽），节点会找出这个键/这些键所属的哈希槽对应的节点。

如果哈希槽在这个节点上，那么这个请求就简单的执行了。否则这个节点会查看它内部的 哈希槽-节点 映射，然后给客户端返回一个 MOVED 错误,如下：

GET x
-MOVED 3999 127.0.0.1:6381

这个错误包括键的哈希槽和能处理这个查询的节点的 IP：端口。客户端需要重新发送请求到给定 ip 地址和端口号的节点。 注意，即使客户端在重发请求之前等待了很长一段时间，与此同时集群的配置信息发生改变，如果哈希槽 3999 现在是归属其它节点，那么目标节点会再向客户端回复一个 MOVED 错误。如果连接的节点没有信息变更，会重复这样。

从集群的角度看，节点是以 ID来标识的。我们尝试简化接口，所以只向客户端暴露哈希槽和用 IP:端口 来标识的 Redis 节点之间的映射。

虽然并没有要求，但是客户端应该尝试记住哈希槽 3999 归属于 127.0.0.1:6381。这样的话一旦有一个新的命令需要发送，它能计算出目标键的哈希槽，找到正确节点的机率更高。

另一种方法是使用CLUSTER NODES 或CLUSTER SLOTS命令刷新整个客户端集群布局。当遇到一个MOVED,当遇到重定向，很可能多个插槽进行重新配置，而不是只有一个，所以尽快更新客户端的配置往往是最好的策略。

注意，当集群是稳定的时候(配置没有在变更)，所有客户端最终都会得到一份 哈希槽->节点 的映射表，这样能使得集群效率非常高,客户端直接定位目标节点，不用重定向、或代理或发生其他单点故障。

一个客户端也应该能处理后文提到的 -ASK 重定向错误，否则不是一个完整的redis集群客户端

集群在线重新配置

Redis 集群支持在集群运行过程中添加或移除节点。实际上，添加或移除节点都被抽象为同一个操作，那就是把哈希槽从一个节点移到另一个节点。这意味着相同的原理能用来重新平衡集群，增/删节点，等等.

• 向集群添加一个新节点，就是把一个空节点加入到集群中并把某些哈希槽从已存在的节点移到新节点上。
• 从集群中移除一个节点，就是把该节点上的哈希槽移到其他已存在的节点上。
• 重新平衡，就是指向一堆哈希槽在节点间迁移

所以实现这个的核心是能把哈希槽移来移去。从实际角度看，哈希槽就只是一堆键，所以 Redis 集群在重组分片时做的就是把键从一个节点移到另一个节点。移动一个哈希槽就是移动属于这个槽的所有键。为了理解这是怎么工作的，我们需要介绍 CLUSTER 的子命令，这些命令是用来操作 Redis 集群节点上的哈希槽转换表。

有以下子命令（在这个案例中有的没用到）：

• CLUSTER ADDSLOTS slot1 [slot2] … [slotN]
• CLUSTER DELSLOTS slot1 [slot2] … [slotN]
• CLUSTER SETSLOT slot NODE node
• CLUSTER SETSLOT slot MIGRATING node
• CLUSTER SETSLOT slot IMPORTING node

头两个命令，ADDSLOTS 和 DELSLOTS，就是简单地用来给Redis 节点指派或移除哈希槽。指派哈希槽就是告诉一个master节点它会负责存储和服务指定的哈希槽。

在哈希槽被指派后会将这个消息通过 gossip 协议向整个集群传播（协议在后文配置传播章节说明）。

ADDSLOTS 命令通常是用于在一个集群刚建立的时候从新给所有master节点指派哈希槽，总共有16384个。

DELSLOTS主要用于群集配置的手工修改或用于调试任务：在实践中很少使用。

SETSLOT用于将哈希槽指定给特定节点的ID ，如果SETSLOT <插槽>节点的形式被使用。否则，哈希槽可以在两种特殊状态MIGRATING 和 IMPORTING。这两个特殊状态用于哈希槽从一个节点迁移到另一个。

• 当一个槽被设置为 MIGRATING，持有该哈希槽的节点仍会接受所有跟这个哈希槽有关的请求，但只有当查询的键还存在原节点时，原节点会处理该请求，否则这个查询会通过一个-ASK 重定向转发到迁移的目标节点。
• 当一个槽被设置为 IMPORTING，只有在接受到 ASKING 命令之后节点才会接受所有查询这个哈希槽的请求。如果客户端没有发送 ASKING 命令，那么查询都会通过-MOVED 重定向错误转发到真正的哈希槽归属节点那里，这通常会发生。

这我们用实例让它哈希槽迁移更清晰些。假设我们有两个 Redis master节点，称为 A 和 B。我们想要把哈希槽 8 从 节点A 移到 节点B，所以我们发送了这样的命令：

• 我们向 节点B 发送：CLUSTER SETSLOT 8 IMPORTING A
• 我们向 节点A 发送：CLUSTER SETSLOT 8 MIGRATING B

其他所有节点在每次请求的一个键是属于哈希槽 8 的时候，都会把客户端引向节点”A”。具体如下：

• 所有关于已存在的键的查询都由节点”A”处理。
• 所有关于不存在于节点 A 的键都由节点”B”处理，因为”A”将重定向客户端请求到”B”。

这种方式让我们可以不用在节点 A 中创建新的键。同时，一个叫做 redis-trib 的特殊脚本，用于重新分片和集群配置，把已存在的属于哈希槽 8的键从节点 A 移到节点 B。这通过以下命令实现：

CLUSTER GETKEYSINSLOT slot count

上面这个命令会返回指定的哈希槽中 count 个键。对于每个返回的键，redis-trib 向节点 A 发送一个MIGRATE 命令，这样会以原子性的方式从A到B迁移指定的键（在移动键的过程中两个节点都被锁住,通常时间很短，所以不会出现竞争状况）。以下是 MIGRATE 的工作原理：

MIGRATE target_host target_port key target_database id timeout

执行 MIGRATE 命令的节点会连接到目标节点，把序列化后的 key 发送过去，一旦收到 OK 回复就会从它自己的数据集中删除老的 key。所以从一个外部客户端看来，在某个时间点，一个 key 要不就存在于节点 A 中要不就存在于节点 B 中。

在 Redis 集群中，不需要指定一个除了 0 号之外的数据库，但 MIGRATE 命令能用于其他跟 Redis 集群无关的的任务，所以它是一个通用的命令。MIGRATE 命令被优化了，使得即使在移动像长列表这样的复杂键仍然能做到快速。 不过当在重配置一个拥有很多键且键的数据量都很大的集群的时候，如果使用它的应用程序来说就会有延时这个限制，这个过程就不是那么好了。

ASK 重定向

在前面的章节中，我们简短地提到了 ASK 重定向（ASK redirection），为什么我们不能单纯地使用 MOVED 重定向呢？因为收到 MOVED，意味着我们认为哈希槽永久地归属到了另一个节点，并且接下来的所有请求都尝试发到目标节点上去。而 ASK 意味着我们只要下一个请求发送到目标节点上去。

这个命令是必要的，因为下一个关于哈希槽 8 的请求需要的键或许还在节点 A 中，所以我们希望客户端尝试在节点 A 中查找，如果需要的话然后在节点 B 中查找。 由于这是发生在 16384 个槽的其中一个槽，所以对于集群的性能影响是在可接受的范围。

然而我们需要强制客户端的行为，以确保客户端会在尝试 A 中查找后去尝试在 B 中查找，如果客户端在发送查询前发送了 ASKING 命令，那么节点 B 只会接受被设为 IMPORTING 的槽的查询。

基本上ASKING 命令在客户端设置了一个一次性标识（one-time flag），强制一个节点可以执行一次关于带有 IMPORTING 状态的槽的查询。

所以从客户端看来，ASK 重定向的完整语义如下：

• 如果接受到 ASK 重定向，发送单次请求重定向到目标节点，接着发送后续的请求到老的节点。
• 先发送 ASKING 命令，再开始发送请求。
• 现在不要更新本地客户端的映射表，把哈希槽 8 映射到B。

一旦完成了哈希槽 8 的转移，节点 A 会发送一个 MOVED 消息，客户端也许会永久地把哈希槽 8 映射到新的 ip:端口号 上。 注意，即使客户端出现bug，过早地执行这个映射更新，也是没有问题的，因为它不会在查询前发送 ASKING 命令，节点 B 会用 MOVED 重定向错误把客户端重定向到节点 A 上。

客户端首次连接和处理重定向

虽然可以有一个Redis的群集客户端不在内存中记住哈希槽配置（哈希槽与节点的映射），并只能通过联系随机节点等待被重定向，这样的客户端将是效率非常低。

Redis的集群客户应尽量足够聪明，记忆哈希槽配置。然而这种配置不必是最新的。因为联系错误的节点只会导致一个重定向，应当触发客户视图的更新。

客户通常需要获取哈希槽与节点映射的完整列表：

• 启动时保存初始的哈希槽配置.
• 当收到 MOVED重定向.

请注意，客户可能根据MOVED重定向更新变动的哈希槽，但是这通常不是有效的，因为通常配置中多个哈希槽一起修改（例如，如果一个slave升为master，所有归属老master的哈希槽会重新映射） 。更简单对MOVED重定向做出回应是，重新获取哈希槽节点映射表。

为了获取哈希槽配置Redis的群集提供了另一种不需要的解析的命令CLUSTER NODES，并只仅提供客户端严格需要的信息。

新的命令被称为CLUSTER SLOTS并槽提供了一组哈希槽范围，关联了主从节点服务于指定的哈希槽范围。

下面是CLUSTER插槽输出的例子：

127.0.0.1:7000> cluster slots
1) 1) (integer) 5461
   2) (integer) 10922
   3) 1) "127.0.0.1"
      2) (integer) 7001
   4) 1) "127.0.0.1"
      2) (integer) 7004
2) 1) (integer) 0
   2) (integer) 5460
   3) 1) "127.0.0.1"
      2) (integer) 7000
   4) 1) "127.0.0.1"
      2) (integer) 7003
3) 1) (integer) 10923
   2) (integer) 16383
   3) 1) "127.0.0.1"
      2) (integer) 7002
   4) 1) "127.0.0.1"
      2) (integer) 7005

返回的数组中的每个元素的前两个子元素是该范围的始未哈希槽。附加元素表示地址端口对。第一个地址端口对是服务于哈希槽的master，和附加的地址端口对服务于相同槽slave，它不存在错误条件（即故障标志没有被设置）。

例如，输出的第一个元素表示，槽从5461至10922（开始和结束包括）由127.0.0.1:7001服务，并且可以通过127.0.0.1:7004水平扩展读负载。

CLUSTER SLOTS是不能保证返回覆盖整个16384插槽，如果群集配置不正确范围，所以客户初始化哈希槽配置时应当用NULL填充空节点，并报告一个错误，如果用户试图执行有关键的命令属于未分配的插槽。

当一个哈希槽被发现是未分配之前，返回一个错误给调用者之前,客户应该再次尝试读取哈希槽配置，检查群集现在配置是否正确。

多键操作

使用哈希标签，用户可以自由地使用多键操作。例如下面的操作是有效的：

MSET {user:1000}.name Angela {user:1000}.surname White

多键操作可能变得不可用,当键所属的哈希槽在进行重新分片。

更具体地，即使重新分片期间，多键操作目标键都存在并且处于相同节点（源或目的地节点）仍然可用。

在重新分片时，操作的键不存在或键在源节点和目的节点之间，将产生 -TRYAGAIN 错误。客户端可以一段时间后再尝试操作，或报错。

只要指定的哈希槽的迁移已经终止，所有多键操作可再次用于该散列槽。

通过slave节点水平扩展读

通常情况下从节点将客户端重定向到给定的命令哈希槽对应的master，但是客户端可以使用READONLY命令读来水平扩展读。

READONLY告诉客户端是允许读失效的数据并且不关心写请求。

当连接处于只读模式，当操作涉及到不是slave的主节点提供服务的键，集群将发送一个重定向到客户端。这可能发生的原因是：

1.客户端发送一个命令对应的哈希槽不是由这个slave的master服务。

2.集群重新配置（例如重新分片 ）并且slave不再能够服务于给定的哈希槽命令。

当发生这种情况如前面部分中说明的，客户端应该更新其哈希槽映射表。

连接的只读状态可以使用READWRITE命令清除。

容错性（Fault Tolerance）

节点心跳和 gossip 消息

集群里的节点不断地交换 ping / pong 数据包。这两种数据包有相同的数据结构，都传输重要的配置信息 。唯一不同是消息类型字段，我们将提到心跳ping/pong包的总数。

通常节点发送ping包，将触发接收节点回复pong包。然而，这未必都是这样的。可能节点只是发送pong包的配置信息给其他节点，而不会触发应答。这样有用处，例如，为了尽快广播新配置。

通常一个节点每秒会随机 ping 几个节点，这样发送的 ping 包（和接收到的 pong 包）的总数会是一个跟集群节点数量无关的常数。

在过去的一半 NODE_TIMEOUT 时间里都没有发送 ping 包过去或接收从那节点发来的 pong 包的节点，会保证去 ping每一个其他节点：。 在 NODE_TIMEOUT 这么长的时间过去之前，若当前的 TCP 连接有问题，节点会尝试去重连接，以确保不会被当作不可达的节点。

如果 NODE_TIMEOUT 被设为一个很小的数而节点数量（N）非常大，那么全局交互的消息会非常多，因为每个节点都会尝试去 ping 每一个在过去一半 NODE_TIMEOUT 时间里都没更新信息的节点。

例如在一个拥有 100 个节点的集群里，节点超时时限设为 60 秒，每个节点在每 30 秒中会尝试发送 99 个 ping 包，也就是每秒发送的 ping 包数量是 3.3 个，乘以 100 个节点就是整个集群每秒有 330 个 ping 包。

有一些方法可以降低的消息的数量，但已经出现了与当前使用的Redis集群故障检测的带宽没有报告的问题，所以现在明显的和直接的设计被使用。注意，即使在上例中，每秒交换被均匀地划分在100个不同的节点330的数据包，因此每个节点收到的通信量是可接受的。

心跳数据包内容

Ping 和 Pong 数据包都包含着一个头部（header），这在这类数据包（比如请求投票的数据包）中是很常见的。一个特殊的 报文片段就是 Ping 包和 Pong 包里一个特殊部分。

常见头部会包含以下这些信息：

• 节点 ID，在节点第一次创建的时候赋值的一个 160 bit 的伪随机字符串，在Redis 集群节点永远都保持不变。
• currentEpoch和 configEpoch 两个字段，用来挂载 Redis 集群使用的分布式算法（这会在下一节中详细解释）。如果节点是slave，configEpoch是上一个已知master的configEpoch。
• 节点标识，标识一个节点是slave/slave，还有其他只占用一个 bit 的节点信息。
• 给定节点负责的哈希槽的位图（bitmap），如果该节点是slave，就是一个其master节点负责的哈希槽位图。
• 发送端的 TCP 基本端口号（也就是，这个端口号是 Redis 用来接收客户端命令的，加上 10000 就是集群总线端口）。
• 从发送者的角度看来的集群状态（down还是ok）。
• 如果这是个slave节点，那么会有master节点 ID。

ping 包和 pong 包都包含着一个 gossip 字段。这个字段是用来让接收者知道发送者是怎么看待集群中的其他节点。gossip 报文片段只包含在发送者已知节点集合里随机取的一些节点的信息。

提到的gossip报文片段的节点数据与集群大小成比例。

每个添加到gossip 报文片段的节点有如下几个字段

• 节点 ID。
• 节点的 IP 和端口号。
• 节点标识。

从发送者的角度看来，gossip 报文片段是让接收的节点能获得其他节点的状态信息。这对于失效检测或者发现集群中的其他节点都是非常有用的。

失效检测

Redis 集群失效检测是用来识别出大多数节点何时无法访问某一个master节点或slave节点。然后，就提升级一个slave成master。若如果无法升级slave成master，那么整个集群就置为错误状态并停止接收客户端的请求。

正如已经提到的，每个节点都有一份跟其他已知节点相关的标识列表。其中有两个标识是用于失效检测，分别是 PFAIL 和FAIL。PFAIL 表示可能失效（Possible failure），这是一个非承认失效类型。FAIL 表示一个节点已经失效，而且这个情况已经被大多数master节点在固定时间内确认过。

PFAIL 标识:

当一个节点在超过 NODE_TIMEOUT 时间后仍无法访问另一个节点，那么它会用 PFAIL 来标识另一个节点。master节点和slave节点都能标识其他的节点为 PFAIL，不论节点类型。

Redis 集群节点的不可达性是指，发送给某个节点的一个活跃的 ping 包 (一个我们发送后要等待其回复)已经等待了超过 NODE_TIMEOUT 时间迟迟不回复。为了让这个机制能正常工作，NODE_TIMEOUT 必须比网络往返时间大。节点为了在普通操作中增加可靠性，当在经过一半 NODE_TIMEOUT时间还没收到目标节点对于 ping 包的回复，就会马上尝试重连接该节点。这个机制能保证连接都保持有效，所以节点间的失效连接通常都不会导致错误的失效报告。

FAIL 标识:

单独一个 PFAIL 标识仅仅是每个节点的一些关于其他节点的本地信息，但是不足够触发slave节点的升级。要让一个节点真正被认为down需要让 PFAIL 状态上升为 FAIL 状态。

在本文的节点心跳章节有提到的，每个节点向其他每个节点发送的 gossip 消息中有包含一些随机的已知节点的状态。最终每个节点都能收到一份其他每个节点的节点标识。通过这种方法，每个节点都有一套机制去标记检测到的其他节点的失效状态。

当下面的条件满足的时候，会使用这个机制来让 PFAIL 状态升级为 FAIL 状态：

• 某个节点，我们称为节点 A，标记另一个节点 B 为PFAIL。
• 节点 A 通过 gossip 报文片段收集到集群中大部分master节点标识的节点 B 的状态信息。
• 大部分master节点标记节点 B 为PFAIL 状态，或者在 NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT 这个时间内是处于 PFAIL 状态(在当前的代码，有效因子FAIL_REPORT_VALIDITY_MULT值为2，所以这个时间是2倍的NODE_TIMEOUT时间)。

如果以上所有条件都满足了，那么节点 A 会：

• 标记节点 B 为FAIL。
• 向所有可达节点发送一个FAIL 消息。

FAIL 消息会强制每个接收到这消息的节点把节点 B 标记为 FAIL 状态，不论是否标记过节点PFAIL。

注意，FAIL 标识基本都是单向的，也就是说，一个节点能从 PFAIL 状态升级到 FAIL 状态，但要清除FAIL 标识只有以下两种可能方法：

• 节点已经恢复可达的，并且它是一个slave节点。在这种情况下，FAIL标识可以清除掉，当slave节点并没有被故障转移。
• 节点已经恢复可达的，并且它是不负责任何哈希槽，在这种情况下FAIL可以清除，因为master没有任何哈希槽处在集群中，就等待配置加入到集群中.
• 节点已经恢复可达的，而且它是一个master节点，但经过了很长时间（N *NODE_TIMEOUT）后也没有检测到任何slave节点被提升了,最好重新加入到集群，并继续这个方法。

值得注意，PFAIL -> FAIL 的转变使用了一种弱协议：

1) 节点是在一段时间内收集其他节点的信息，所以即使大多数master节点要去”同意”标记某节点为 FAIL，实际上这只是表明说我们在不同时间里从不同节点收集了信息，并且我们不确定或不需要，给定的时刻大多数master同意，然后我们舍弃旧的失效报告，所以失效的通知是大多数master在时间窗口内的。

2) 当每个节点检测到 FAIL 节点的时候会强迫集群里的其他节点把各自对该节点的记录更新为 FAIL，但没有一种方式能保证这个消息能到达所有节点。比如有个节点可能检测到了 FAIL 的节点，但是因为网络分区，这个节点无法到达其他任何一个节点。

然而 Redis 集群的失效检测有一个实时要求：最终所有节点都应该同意给定节点的状态。有两种情况是来源于脑裂情况，或者是小部分节点相信该节点处于 FAIL 状态，或者少数节点相信节点不处于 FAIL 状态。在这两种情况中，最后集群都会给节点一个状态：

第 1 种情况: 如果大多数节点都标记了某个节点为 FAIL，由于失效检测和产生的链条反应，这个master节点最终会被标记为FAIL,因为在指定时间窗口内失效将被报告。

第 2 种情况: 当只有小部分的master节点标记某个节点为 FAIL 的时候，slave节点的提升并不会发生（它是使用一个更正式的算法来保证每个节点最终都会知道节点的提升）并且每个节点都会根据上面的清除规则来清除 FAIL 状态（即：在经过了一段时间 > N * NODE_TIMEOUT 后仍没有slave节点升级操作）。

FAIL 标识只是用来触发slave节点升级算法的安全部分。理论上一个slave节点会在它的master节点不可达的时候独立起作用并且启动slave节点提升程序，如果master节点对大部分节点恢复连接，然后等待master节点来拒绝认可该提升。然后增加复杂性的PFAIL -> FAIL 状态变化、弱协议、强制在集群的可达部分用最短的时间传播状态变更的 FAIL 消息，这些东西增加的复杂性有实际的好处。由于这种机制，如果集群处于错误状态的时候，所有节点都会在同一时间停止接收写入操作，这从使用 Redis 集群的应用的角度来看是个很好的特性。还错误的选举，是slave节点本地原因无法访问master节点（该master节点能被其他大多数master节点访问的话），这个选举会被拒绝掉。

配置处理，传播，和失效转移

集群当前epoch

Redis 集群使用一个类似于木筏算法”术语”的概念。在 Redis 集群中这个术语叫做 epoch，它是用来记录事件的递增版本号，所以当有多个节点提供了冲突的信息的时候，另外的节点就可以通过这个状态来了解哪个是最新的。

currentEpoch 是一个 64bit 的 unsigned 数。

Redis 集群中的每个节点，包括master节点和slave节点，都在创建的时候设置了 currentEpoch 为0。

每次当节点接收到来自其他节点的 ping 包或 pong 包的时候，如果发送者的 epoch（集群总线消息头部的一部分）大于该节点的 epoch，那么更新currentEpoch成发送者的 epoch 。

由于这个语义，最终所有节点都会支持集群中最大的 epoch。

这个信息在此处是用于，当一个节点的状态发生改变的时候为了执行一些动作寻求其他节点的同意（agreement）。

目前这个只发生在slave节点的升级期间，随后在下一节中详述。本质上说，epoch 是一个集群里的逻辑时钟，并决定一个给定的消息覆盖另一个带着更小 epoch 的消息。

epoch配置

每一个master节点总是通过发送 ping 包和 pong 包向别人宣传它的 configEpoch 和一份表示它负责的哈希槽的位图。

当一个新节点被创建的时候，master节点中的 configEpoch 设为零。

slave升级的时候创建一个新的configEpoch. slave试图取代失败的主人增加他们的epoch，并尝试从大多数主人获得授权。当slave被授权，新的唯一configEpoch创建并且alave变成master使用新的configEpoch。

将在下一节解释，configEpoch 用于在不同节点提出不同的配置信息的时候解决冲突（这种情况或许会在网络分区和节点失效）。

slave节点也会在 ping 包和 pong 包中向别人宣传它的 configEpoch 字段，不过slave节点的这字段表示的是上一次跟它的master节点交换数据的时候master节点的 configEpoch 值。这能让其他节点检测出slave节点的配置信息是不是需要更新了（master节点不会给一个配置信息过期的slave节点投票）。

所有节点收到信息，每次由于一些已知节点的值比自己的值大而更新 configEpoch 值，都会永久性地存储在 nodes.conf 文件中。currentEpoch也一样。这两人个变量更新时，节点在继续动作前，保证同步保存到磁盘

configEpoch值使用简单算法, 在失效转移生成保证是最新/自增/唯一。

slave节点的选举和升级

slave节点的选举和提升都是由slave节点处理的，master节点会投票要提升哪个slave节点。一个slave节点的选举发生条件：master处理FAIL状态（至少一个slave有条件成为master）。

要让一个slave升级成master,需要发起一次选举并取胜。当master处于FAIL状态，所有给定master的slave都能发起一次选举。然后只有一个slave能赢得选举升级成为master。一个slave发起选举，并要满足如下条件：

• 该slave节点的master节点处于FAIL 状态。
• 这个master节点负责的哈希槽数目不为零。
• slave节点和master节点之间的连接断线不超过一段给定的时间，这是为了确保slave节点的数据是可靠的。

一个slave节点想要被推选出来，那么第一步应该是提高它的 currentEpoch 计数，并且向master节点们请求投票。

slave节点通过广播一个 FAILOVER_AUTH_REQUEST 数据包给集群里的每个master节点来请求选票。然后等待回复,最多等 NODE_TIMEOUT 这么长时间(通常至少2秒)。

一旦一个master节点给这个slave节点投票，会回复一个FAILOVER_AUTH_ACK，并且在 NODE_TIMEOUT * 2 这段时间内不能再给同个master节点的其他slave节点投票。在这段时间内它完全不能回复其他授权请求。这不必保证安全，但用于同时在一轮防止多slave选举（使用不同的configEpoch），多选举是不需要的。

slave节点会忽视所有带有的epoch参数比 currentEpoch 小的回应（ACKs），这样能避免把之前的投票的算为当前的合理投票。

一旦某个slave节点收到了大多数master节点的回应，那么它就赢得了选举。否则，如果无法在 NODE_TIMEOUT 时间内访问到大多数master节点(通常至少2s)，那么当前选举会被放弃并在 NODE_TIMEOUT * 4 这段时间后由另一个slave节点尝试发起选举（通常至少4s）。

slave排名

DELAY = 500 milliseconds + 0-500随机数 milliseconds +

SLAVE_RANK * 1000 milliseconds.

固定延时确保我们会等到 FAIL 状态在集群内广播后，否则若slave节点尝试发起选举，master节点们仍然不知道那个master节点已经 FAIL，就会拒绝投票。

随机延迟用于破坏同步slave,所以他们不太可能在同一时间开始选举。

该SLAVE_RANK是slave从master复制过来的数据处理数量的排名。slave交换消息时，当master失败，以（尽力而为）建立一个排名：最新的复制数据偏移量slave排名0，第二最新排名1 ，依此类推。如果靠前排名的slave选举失败，其它很快会接着做。

排名顺序没有严格执行;如果排名较高的奴隶落选，其他人会尝试很快。

一旦有slave节点赢得选举，它就会有一个比其它存在的master更大的 唯一自增的configEpoch 。 它开始通过ping 和 pong 数据包向其他节点宣布自己已经是master节点，并提供它负责的哈希槽覆盖老的，这个数据包带有configEpoch。

为了加速其他节点的重新配置，该节点会广播一个 pong 包 给集群里的所有节点. 那些现在访问不到的节点,如果它们通过心跳包发布的信息已经过期，最终也会收到一个 ping 包或 pong 包，并且进行重新配置。

其他节点会检测到有一个更大configEpoch的新master节点在负责处理之前一个旧的master节点负责的哈希槽，然后就升级自己的配置信息。 旧master节点的slave节点(或者是经过故障转移后重新加入集群的该旧master节点)不仅会升级配置信息，还会配置新master节点的备份。节点怎么重新加入集群的配置会在下一节解释。

master节点回复slave节点的投票请求

在上一节中我们讨论了slave节点是如何被选举上的，这一节我们将从master节点的角度解释在为给定slave节点投票的时候发生了什么。

master节点接收到来自于slave节点、要求以 FAILOVER_AUTH_REQUEST 请求的格式投票的请求。

要授予一个投票，必须要满足以下条件：

• 1)一个master节点只能投一次票给指定的epoch，并且拒绝更早的epoch：每个master节点都有一个 lastVoteEpoch 域，一旦认证请求数据包里的currentEpoch小于 lastVoteEpoch，那么master节点就会拒绝再次投票。当一个master节点积极响应一个投票请求，那么 lastVoteEpoch 会相应地进行更新，同时安全地存储到磁盘。
• 2) 一个master节点投票给某个slave节点只有当该slave节点的master节点被标记为FAIL。
• 3) 如果认证请求里的currentEpoch 小于master节点里的 currentEpoch 的话，那么该请求会被忽视掉。因此，master节点的回应总是带着和认证请求一致的 currentEpoch。如果同一个slave节点在增加currentEpoch 后再次请求投票，那么保证一个来自于master节点的、旧的延迟回复不会被新一轮选举接受。

下面的例子是没有依据规则3引发的问题：

master节点的 currentEpoch 是 5， lastVoteEpoch 是 1（在几次失败的选举后这也许会发生的）

• slave节点的currentEpoch 是 3。
• slave节点尝试用 epoch 值为 4（3+1）来赢得选票，master节点回复 ok，里面的currentEpoch 是 5，可是这个回复延迟了。
• slave节点尝试用 epoch 值为 5（4+1）来再次赢得选票，收到的是带着currentEpoch 值为 5 的延迟回复，这个回复会被当作有效的来接收。

1. master节点若已经为某个失效master节点的一个slave节点投票后，在经过NODE_TIMEOUT * 2 时间之前不会为同个失效master节点的另一个slave节点投票。这并不是严格要求的，因为两个slave节点用同个 epoch 来赢得选举的可能性很低，不过在实际中，系统确保正常情况当一个slave节点被选举上，那么它有足够的时间来通知其他slave节点，以避免另一个slave节点发起另一个新的选举。
2. master节点不会用任何方式来尝试选出最好的slave节点，只要slave节点的master节点处于FAIL 状态并且投票master节点在这一轮中还没投票，master节点就能积极投票。

最佳的slave最可能在其它slave前发起一次选举并赢得它 ，因为它通常能更早发起选举过程，因为它更高排名(前面章节提到的slave排名)。

1. 当master拒绝投票给没有积极回应的slave，请求简单的被忽略.
2. master节点不会投票给那些configEpoch 值比master节点哈希槽表里的 configEpoch 更小的slave节点。记住，slave节点发送了它的master节点的 configEpoch 值，还有它的master节点负责的哈希槽对应的位图。这意味着，请求投票的slave节点必须拥有它想要进行故障转移的哈希槽的配置信息，而且信息应该比它请求投票的master节点的配置信息更新或者一致。

在网络分区下epoch配置的可用性实例

这一节解释如何使用 epoch 概念来使得slave节点提升过程对网络分区更有抵抗力。

• master节点不是无限期地可达。它拥有三个slave节点 A，B，C。
• slave节点 A 赢得了选举并且被推选为master节点。
• 一个网络分区操作使得集群中的大多数节点无法访问节点 A。
• 节点 B 赢得了选举并且被推选为master节点。
• 一个网络分区操作使得集群中大多数节点无法访问节点 B。
• 之前分区操作的问题被修复了，节点 A 又恢复可访问状态。

此刻，节点 B 已经down，节点 A 当上master又可访问了(事实上UPDATE消息可以快速重新配置它，介此处我们假设所有UPDATE消息已经丢失)，同时slave C 竞选对节点 B 进行故障转移。

这两个有同样的哈希槽的slave节点最终都会请求被提升，然而由于它们发布的 configEpoch 是不一样的，而且节点 C 的 epoch 比较大，所以所有的节点都会把它们的配置更新为节点 C 的。

过程如下。

1， B就尽量当选而且一定会成功，因为对于大多数master它的master已经down。它会得到一个自增的configEpoch 。

1. A将无法声称自己是master负责它的哈希槽，因为相比A,其他的节点已经具有更高的epoch,关联了相同的哈希插槽

3。因此，所有的节点都将升级他们的哈希槽分配给C，集群将继续运作。

正如你下面章节看到的，一个失联的节点重新加入集群将尽快通知到配置变更，因为一量它ping任何其它节点，接收者会检测它已经失效的上并发送UPDATE消息.

哈希槽信息的传播

Redis 集群很重要的一个部分是用来传播关于集群节点负责哪些哈希槽的信息的机制。这对于新集群的启动和提升配置（slave升级前master处理的槽）的能力来说是必不可少的。

同样的机制让节点划分，因无限长的时间通过合理的方式来加入集群。

哈希槽配置传播有两种方法：

1.心跳消息。 ping或pong包的发送者总是带有负责的哈希槽信息（如果是slave，就是对应master的哈希槽信息）。

2.UPDATE消息。因为每一次心跳数据包中有一个关于发送者configEpoch信息和负责的哈希槽，如果心跳包的接收方发现发送者信息是过时的，它会发送新信息的数据包，迫使过时的节点更新其信息。

心跳或UPDATE消息的接收方使用某些简单的规则，以更新其映射的哈希插槽节点。当创建一个新的Redis集群，其本地哈希槽映射表只是初始化为NULL的条目，使每个哈希位置没有绑定或链接到任何节点。这看起来类似于以下内容：

0 -> NULL
1 -> NULL
2 -> NULL
...
16383 -> NULL

第一个规则允许节点来更新它的哈希槽映射表如下：

规则一：如果一个哈希槽没有赋值，（设置为NULL）,并且一个已经节点申明它，我们修改哈希槽映射表并关联申明的哈希槽，因此如果我们收到节点A的心跳包申明负责槽1和2，配置epoch是3,映射表修改如下：

0 -> NULL
1 -> A [3]
2 -> A [3]
...
16383 -> NULL

当创建一个新的集群，一个系统管理员需要手动分配（使用CLUSTER ADDSLOTS命令，通过redis – trib命令行工具，或通过任何其他方式）各主节点对节点本身负责的槽，这些信息将迅速在群集中传播。

但是这条规则是不够的。我们知道，哈希槽映射可以因两个事件改变：

1. 一个slave在故障转移中替换它的master
2. 一个槽从一个节点重新分片到不同节点

到此为止，我们专注在故障转移。当一个slave故障转移掉它的master, 它获得被保证是大于它的主人的配置epoch（更通常大于任何其他先前生成的配置epoch）。例如节点B，是一个A的slave，可以用配置epoch4故障转移B，它将开始发送心跳数据包（第一次大规模广播集群范围内），也因为以下第二个规则，接收者将更新他们的哈希槽映射表：规则2: 如果一个哈希槽已经分配，和已知的节点首播它使用的configEpoch大于目前master关联槽的configEpoch，我会重新绑定哈希槽到新节点。所以从B接收消息，用配置epoch申明负责槽1和2,接收者将用如下方式更新它们的映射表：

0 -> NULL
1 -> B [4]
2 -> B [4]
...
16383 -> NULL

实时属性：因为第二个规则，最终所有集群中的节点同意槽的归属节点在节点首播时拥有最大configEpoch

这个原理在redis集群中叫做 最后故障转移取胜

这同样发生在重新分片。当一个节点导入哈希槽完成导入操作，它的配置epoch会增加来保证这个改变会在集群中传播。

细看UPDATE 消息

带着上一节，是比较容易看到更新消息是如何工作的。节点A可能一段时间后重新加入集群。它用配置epoch 3申明负责哈希槽1和2，所有的更新信息接收者将转而看到相同的哈希插槽关联着具有较高配置epoch的节点B，将发送心跳包。正因为如此，他们会发送带有最新哈希槽配置的UPDATE信息到A。 A将更新其配置，因为上面的规则2。

节点怎么重新加入集群

当一个节点重新加入的集群,应用了相同的原理。继续上面的例子，节点A将通知哈希槽1和2现在由B负责.假设这两个哈希槽以前都由A负责。假设A负责的槽数量只有两人个，A负责的槽数降为0！因此A将重新配置成为新master的slave。

事实上后面的规则比这复杂一点。通常可能A会过很长时间再加入集群，与此同时可能开始由A负责的槽由多个节点负责，比如B负责槽1，C负责槽2.

所以真实的redis集群节点角色切换规则是：master节点会改变配置来变成slave, 它的master是拿走它最后一个槽的master.

在重新配置期间，最终负责的槽数会变成0, 节点会相应的重新配置。注意，在这基本条件下意味着老master会成为它slave失效转移后的slave. 然而通用规则会覆盖所有可能情况。

slave 做完全一样的事：它们重新配置来做slave , 它们的master是拿走老master最后一个槽的master.

备份迁移

Redis 集群实现了一个叫做备份迁移（replica migration）的概念，以提高系统的可用性。在集群中有master-slave的设定，如果主slave节点间的映射关系是固定的，master/slave一定的可用性受限于故障时间，这个时间发生多个单一节点独立故障。

例如在一个集群中，每个master节点都只有一个slave节点，任何一对master-slave的一个出故障的时候集群能让操作继续执行下去，一对同都出故障就不行。然而这样长期会积累很多由硬件或软件问题引起的单一节点独立故障。例如：

• master A只有一个slave A1。
• master A 失效了。A1 升级成新master。
• 三个小时后，A1 因为一个独立事件（跟节点 A 的失效无关）失效了。由于没有其他slave节点可以升级为master节点，因为节点 A 仍然down着，集群没法继续进行正常操作。

如果master-slave的映射关系是固定的，那要让集群对上述情况更具容灾能力 , 唯一方法就是为每个master多加slave。然而这要付出的代价也更昂贵，因为要求 Redis 部署更多的实例、更多的内存等等。

一个候选方案就是在集群中创建不对称性，然后让集群布局时随着时间自动变化。例如，假设集群有三个master A，B，C。节点 A 和 B 都各有一个slave节点，A1 和 B1。节点 C 有两个slave：C1 和 C2。

备份迁移是slave节点自动重新配置的过程，为了迁移到一个没有可工作slave节点的master节点上。按上面提到的方案，备份迁移过程如下：

• master A 失效。A1 升级成master。
• 节点 C2 迁移成为节点 A1 的slave，要不然 A1 就没有任何slave备份。
• 三个小时后节点 A1 也失效了。
• C2 被提升为取代 A1 的新master。
• 集群仍然能继续正常工作。

备份迁移算法

迁移算法不用任何形式的协议，因为 Redis 集群中的slave节点布局不是集群配置信息的一部分，配置信息要求前后一致并且者用 config epochs 来标记版本号。 当一个master没有备份时，它使用一个算法避免slave节点大批迁移。这个算法保证，一旦集群配置信息稳定下来，最终每个master节点都至少会有一个slave节点作为备份。

这个算法是如何工作的。在开始之前我们需要定义清楚在这个上下文中什么才算是一个好的slave节点：一个健康的slave节点是指节点不处于 FAIL 状态。

若检测出有一个master没有健康slave，那么就会触发这个算法的执行。然而在所有检测出这种情况的slave节点中，只有一部分slave节点会采取行动。 通常这部分slave只有一个，除非有不同的slave在给定时刻对其他节点的失效状态有稍微不同的视角。

采取行动的slave节点是属于那些绑定了最多slave的master节点，并且不处于 FAIL 状态及拥有最小的节点 ID。

例如，如果有 10 个master节点，它们各有 1 个slave节点，另外还有 2 个master节点，它们各有 5 个slave节点。会发生迁移的slave是-那 2 个拥有 5 个slave的master中的所有slave里-节点 ID 最小的那个。鉴于没用到任何协议，在集群配置信息不稳定的情况下，有可能发生一种竞争情况，多个slave节点都认为自己是不处于 FAIL 状态并且拥有较小节点 ID（实际上这是一种比较难出现的状况）。如果这种情况发生的话，结果是多个slave节点都会迁移到同个master节点下，不过这种结局是无害的。这种竞争发生的话，有时候会使得割让出slave的master变成没有任何备份节点，当集群再次达到稳定状态的时候，本算法会再次执行，然后把slave节点迁移回它原来的master节点。

最终每个master节点都会至少有一个slave备份。通常表现象是，一个slave从一个拥有多slave的master节点迁移到一个孤立的master节点。

这个算法能通过一个用户可配置的参数控制 cluster-migration-barrier : 一个master节点在拥有多少个健康slave节点的时候就要割让一个slave节点出来。例如这个参数设为 2，那么只有当一个master节点拥有 2 个可工作的slave节点时，它的一个slave节点会尝试迁移。

configEpoch冲突解决算法

当slave通过故障转移中升级，会生成新的configEpoch值，它可以保证是唯一的。

但也有两个不同的事件, 新configEpoch值以不安全的方式创建，只是递增本地节点的本地currentEpoch ，希望同一时间不存在冲突。这两个事件是系统管理员触发：

1. 当在多数master不可达，CLUSTER FAILOVER 和TAKEOVER选项是用来手工升级slave成master 。 这很管用，比如，多数据中心的设置 .
2. 当没有协议性能问题，集群重新平衡迁移哈希槽时在本地节点也产生新的配置epoch

具体来说，在手工重新分片中，当一个槽从A迁移到B,重新分片的程序会迫使B升级它的配置epoch，它是集群中最大的加1(除非节点已经是配置epoch中最大),节点相互之没有必需的协议。通常实际的重新分片涉及几百个哈希槽(特别是在小集群中)。 每个哈希槽迁移, 需要一个协议在重新分片过程中来产生新的配置epoch，这是低效的. 另外，它需要集群节点实时同步来存储最新的配置，因为它的这种运行方式，当第一个槽移动只需要一个新的配置epoch,使得在生产环境更加高效.

然而，因为上述两种情况的，它是可能的（虽然不太可能） ，最终多个节点有相同的配置epoch。一个重新分片操作由系统管理员执行，并在故障转移发生在同一时间（加了很多的坏运气），如果他们不传播速度不够快可能会导致currentEpoch碰撞。此外，软件错误和文件系统损坏也可能导致多节点有相同的配置epoch。

当负责不同的槽的master有相同的configEpoch, 这没有问题. 可能slave故障转移成master有一个唯一的配置epoch. 也就是说，手工干预或重新分片可能用不同的方式改变集群配置。redis集群主要的活越性要求槽配置经常汇总，所以在每种环境下，我们想要所有master有不同的configEpoch.

为了增强这个，使用一个冲突解决算法，来保证两个节点最终有相同configEpoch.

• 如果一个master发现其它master正在宣传跟它相同的configEpoch.
• 并且如果节点有按字典顺序比其它节点有更小的节点ID,申明相同的configEpoch.
• 然后它把currentEpoch加1作为新的configEpoch.

如果有一些节点有相同的configEpoch,除了最大节点 ID的节点都将前进，保无论发生什么证最终有唯一configEpoch。

这个原理也保证在新集群创建后，节点开始有不同的configEpoch(即使这没有使用)因为redis-trib保证使用CONFIG SET-CONFIG-EPOCH来起动。然而，如果节点由于某些原因误配置了，它会自动更新配置成另外一个。

节点重置

节点可以软重置（不重启的情况下）来来重新使用不同的角色或加入到不同的集群。 这在普通操作、测试、云环境（给定的节点可以另行配置加入到一堆集群来扩大或创建新集群）中非常有用。

在集群节点中使用CLUSTER RESET 来重置，命令提供两个选项：

• CLUSTER RESET SOFT
• CLUSTER RESET HARD

命令必需直接发送到节点重置。如果没有加上重置类型，默认是软重置.

下面是reset执行的一系列操作：

1. 软重置和硬重置：如果节点是slave,变成了master,数据集被丢弃。如果节点是master，包含了键会放弃执行重置
2. 软重置和硬重置：所有槽释放，手工故障转移也重置
3. 软重置和硬重置：节点列表会移除其它节点，节点不再知道其它节点
4. 单独硬重置：currentEpoch,configEpoch, 和lastVoteEpoch 设置成 0.
5. 单独硬重置：节点ID变成新的随机ID.

非空数据集的master不能重置（因为通常你想重新分布数据到其它节点）。然后，在特殊条件下，这是合适的（比如当一个集群完全销毁来创建一个新的），FLUSHALL必需在重置前执行.

集群删除节点

实际中可能从一个集群中删除一个节点，把数据重新分布到其它节点（如果它是master），然后关掉它。然而，其它节点仍然记录了它的节点ID和地址，并且尝试重连.

因为这个原因，当删除一个节点，我们想把条目从所有其它节点列表中删除。这可以使用CLUSTER FORGET <node-id> 命令来实现，这个命令做两件事：

1.从节点列表中删除指定的节点ID.

2.在60s间隔内，阻止相同节点ID的节点重新加入.

第二项有必要是因为redis集群使用gossip来自动发现节点，因为从节点A移除节点X,会导致B 把节点X又告诉A。 因为这60s间隔，redis集群管理工具有60s在所有节点移除节点，阻止由于重新发现重新加入节点。

CLUSTER FORGET 文档中可以得到更多信息.

发布/订阅（Publish/Subscribe）

在一个 Redis 集群中，客户端能订阅任何一个节点，也能发布消息给任何一个节点。集群会确保发布的消息都会按需进行转发。

目前的实现方式是单纯地向所有节点广播所有的发布消息，在某些点，将来会用 bloom filters 或其他算法来优化。

附录 A：CRC16算法的 ANSI C 版本的参考实现

/*
 * Copyright 2001-2010 Georges Menie (www.menie.org)
 * Copyright 2010 Salvatore Sanfilippo (adapted to Redis coding style)
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the University of California, Berkeley nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/* CRC16 implementation according to CCITT standards.
 *
 * Note by @antirez: this is actually the XMODEM CRC 16 algorithm, using the
 * following parameters:
 *
 * Name                       : "XMODEM", also known as "ZMODEM", "CRC-16/ACORN"
 * Width                      : 16 bit
 * Poly                       : 1021 (That is actually x^16 + x^12 + x^5 + 1)
 * Initialization             : 0000
 * Reflect Input byte         : False
 * Reflect Output CRC         : False
 * Xor constant to output CRC : 0000
 * Output for "123456789"     : 31C3
 */

static const uint16_t crc16tab[256]= {
    0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
    0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
    0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,
    0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,
    0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,
    0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,
    0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4,
    0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc,
    0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823,
    0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b,
    0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12,
    0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a,
    0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41,
    0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49,
    0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70,
    0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78,
    0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f,
    0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067,
    0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e,
    0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256,
    0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d,
    0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405,
    0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c,
    0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,
    0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab,
    0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3,
    0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a,
    0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92,
    0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9,
    0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1,
    0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,
    0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0
};

uint16_t crc16(const char *buf, int len) {
    int counter;
    uint16_t crc = 0;
    for (counter = 0; counter < len; counter++)
            crc = (crc<<8) ^ crc16tab[((crc>>8) ^ *buf++)&0x00FF];
    return crc;
}