一、介绍

　　该文档是开发之中的redis集群实现细节。该文档分成两个部分，第一部分为在redis非稳定版本代码分支上已经实现的，另外一部分为还需要去实现的。在未来若集群实现设计变更这些都可能被修改，但是相对来说，未实现的部分相较于已经实现的部分被修改的可能性更大些。该文档包括了实现客户端需要的各种细节，但是客户端作者需要注意这些细节都有可能被修改。

二、什么是Redis集群

　　集群是独立服务器关于分布式与容错实现的一个子集。在集群之中没有中心节点与代理节点，设计的主要目的之一就是线性可伸缩的扩展（即随意增删节点）。集群为了保证数据的一致性而牺牲容错性，所以当网络故障和节点发生故障时这个系统会尽力去保证数据的一致性和有效性。（这里我们认为节点故障是网络故障的一种特殊情况）

为了解决单点故障的问题，我们同时需要masters 和 slaves。 即使主节点(master)和从节点(slave)在功能上是一致的，甚至说他们部署在同一台服务器上，从节点也仅用以替代故障的主节点（即备节点不会被使用除非主节点发生故障而用来代替主节点）。
实际上应该说 如果对从节点没有read-after-write（写并立即读取数据 以免在数据同步过程中无法获取数据）的需求，那么从节点仅接受只读操作。

三、已经实现的子集

　　集群实现了在非分布式版本上的所有单个命令。复杂多命令操作例如集合sets的交集并集还没有实现。通常情况下理论上对于不在同一个节点上的操作不会被实现。

将来可能增加一种叫"Computation Node"的新节点类型（计算节点），这种节点主要用来处理在集群中multi-key的只读操作。但是对于multi-key的只读操作不会以集群传输到Computation
Node节点再进行计算的方式实现。

(有点绕啊，看英文吧：In the future it is possible that using
the MIGRATE COPY command users will be able to use Computation
Nodes to perform multi-key read only operations in the cluster, but it is not likely that the Redis Cluster
itself will be able to perform complex multi key operations implementing some kind of transparent way to move keys around.)

，并且不支持select命令。

四、集群协议中的客户端与服务器角色

　　在集群中的节点，负责存储数据，了解集群的状态以及包括把数据key映射到对应的节点。集群中的任何一个节点都能够自动发现其他节点和检测到故障的节点，并且在必要是时候执行备节点提升为主节点的操作。

　　集群节点使用TCP bus（连接总线）和二进制协议进行互联并对任务进行分派。即每一个节点都使用TCP
bus连接到集群中的其他节点。各节点使用gossip 协议发送消息：

1）传播消息（propagate
information）以发现新节点，

2）发送ping packets给集群其他节点以检测其他节点是否工作正常，

3）发送集群消息需要特定的信号条件

集群连接总线也可以是在各个节点间传播PUB/SUB消息。

　  当集群中的节点不能满足客户端的请求时，可能会使用errors -MOVED and -ASK命令来告知重定向到可用节点。理论上客户端允许向集群中的任意节点发送请求并在必要时会得到重定向应答，即客户端不必关心集群的状态。然而客户端可以缓存数据keys与节点的映射关系以改免去服务器端再进行重定向，这在一定程度上可以提高性能。

五、关键字分布式模型

　　key空间被分割成个百分比的slot。当集群稳定时（即没有正在转移某个slot到另外一个节点），则某个slot必定只被某个节点处理，然后某个节点可以同时处理多个槽。

effectively setting an
upper limit for the cluster size of 16384 nodes (however the suggested max size of nodes is in the order of ~ 1000 nodes).

　　映射键值到指定槽值的算法如下：

　　HASH_SLOT = CRC16(key) mod 4096

　　在该文档的附注1之中有CRC16算法介绍。

　　使用12满分的CRC16的16位输出，在我们的测试之中CRC16能够很好的将各种类型的key映射到4096的空间之中。

六、集群节点的属性

　　在集群中的每个节点都有其在集群中唯一的ID，其ID为160比特随机数的十六进制表示。节点首次启动时即获取ID，节点将获取其ID并保存在其配置文件之中，并且将一直使用该ID，直到该配置文件被系统管理员删除。

　　节点的ID作为集群中的节点识别，一个节点可能修改IP或地址但是不必须修改节点名称。集群也能够检测到节点IP、PORT的变化然后通过连接总线发送变更的协议通知。

　　每个节点都有一些相关的信息，被其他节点所知道：

　　1）该节点的IP地址与端口

　　2）一些标志位

　　3）该节点服务的key-slot

　　4）最后一次通过集群连接总线发送ping的时间

　　5）最后一次收到pong的时间

　　6）该节点的备份节点数

　　7）如果其为备份节点，则其主节点的ID（若该节点为主节点则该值为0000000

　　通过CLUSTER NODES命令可以获取该集群中的所有节点信息，包括主节点与备份节点。

　　如下为一个示例：

　　$ redis-cli cluster nodes

　　d1861060fe6a534d42d8a19aeb36600e18785e04 :0 myself - 0 1318428930 connected 0-1364

　　3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 　　connected 1365-2729

　　d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931 　　connected 2730-4095

　　上述显示各项信息依次为：ID、IP：PORT、 FLAGS、最近发送PING的时间，最近接受到PONG时间、连接状态、slots

七、节点间的握手（已实现）

　　节点总是接受来自集群总线的端口连接请求，并且在收到ping请求时总是回复，即使ping的源节点非可信的。然而若发送端的节点非所在集群，则其消息将被丢弃。

　　一个节点接受另一个节点为集群的一部分有如下两种情况：

　　1）假如一个节点使用一个MEET消息介绍自己。MEET消息很像一个PING消息，但是其要求接受者将其接受为集群的一部分。节点只有在收到管理员执行的CLUSTER MEET ip port 命令之后才会发送MEET消息到其他节点

　　2）当一个节点已经被信任时，另一个节点也可以注册其为该集群的一部分，将扩展该消息到其他节点。假如：A知道B，B知道C，最后B将传播伙伴信息到A与C，这时A将注册C为该网络的一部分，并且试图连接到C。

　　这意味着，只要我们加入节点到任意连通图，他们最终将自动实现全连接。该项意味着集群可以自动发现新节点，但是信任关系需要有管理员设定。这种方式使得集群更加强大并且确保集群不会因为IP或PORT变更而导致多个集群互相混淆。

　　所有的节点将试图连接已知的所有其他节点。

八、移动重定向

　　一个redis客户端可以*地将请求发送给集群中的任意一个节点，包括哪些slave节点。节点将分析查询请求，如果不能接受将通过哈希算法计算该关键字归属的节点，如果计算出的关键字属于自己处理，则查询直接被处理，其他情况将根据该节点的持有的其他节点信息，计算出关键字哈希然后返回客户端表示MOVED错误。

　　MOVED错误，看起来如下：

　　GET x

　　-MOVED 3999 127.0.0.1:6381

　　错误信息中包括了该key哈希出来的slot，以及服务于该slot的节点地址信息，客户端需要重新请求到指定地址的节点。注意，假如客户端得到该信息后很长一段时间没有发起请求，假如集群在此时重组了各个节点服务的slot，则再次请求时有可能再次接收到MOVED错误。

　　因此根据集群节点的视图以ID为标示来说，我们试图只是简单的暴露哈希slot与节点IP，port之间的映射关系。客户端不必须但是应该试着缓存slot3999是由 127.0.0.1 6381节点提供服务。

　　这种方式当有一个新的命令需要处理时，就可以计算其slot然后请求到特定的节点能够增加成功率。

　　当集群服务稳定后，最终所有的客户端都有一张slot与节点的映射表，客户端直接请求到正确的节点而不需要重定向，有助于提高集群的效率。

　　客户端应该也能够处理本文档描述的ASK命令的重定向。

九、集群动态重构

　　集群支持在运行时动态增加与删除节点，事实上对于增加或删除节点执行的是相同操作，即将处理key的slot从一个节点移动到另一个节点。

　　1）增加一个新节点时，有一个空的节点添加到集群之中，同时会有一些哈希slot从现存的节点移动到新的节点上

　　2）删除一个节点，同样的将其处理的哈希slot移动到其他节点之上

　　因此实现的核心是能够移动哈希slot，实际上，哈希slot对应的就是一组关键字key，因此集群在重新哈希时其实就是将一些key从一个节点移动到另一个节点。

　　要理解该内容，可以通过CLUSTER子命令来手动移动节点的哈希slot，有如下命令：

　　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只是简单的从某个节点上增加删除其处理的slot，当哈希slot分配完成后他们将通过集群协议将信息广播到所有节点。ADDSLOTS通常用于从零配置一个集群的快速方法。SETSLOTS用于将某个哈希slot分配给指定的已存在的节点。其他情况哈希slot可以通过另外两种方法设置：MIGRATING、INPORTING

　　1）当一个哈希slot被设置成MIGRATING，该节点会接受所有对该哈希slot的查询，但是必须是该key已经存在。其他情况，将指引一个ASK重定向到MIGRATING的目标节点

　　2）当一个哈希slot被设置成IMPORTTING，该节点会接受所有对该哈希slot的查询，但是前提是必须执行一个ASKING命令。其他情况若客户端没有提供ASKING命令，则请求会被重定向到真实的服务该slot的节点上，产生一个MOVED错误。

　　如此操作可能会奇怪，接下来会详细说明。假定现在又两个节点A、B，现在希望将slot 8从节点A移动到节点B，我们使用如下命令：

　　We send B: CLUSTER SETSLOT 8 IMPORTING A

　　We send A: CLUSTER SETSLOT 8 MIGRATING B

　　此时，所有其他节点都会将查询slot 8的请求定向到A，因此发生如下情况：

　　1）所有已经存在的key查询请求都在A中处理

　　2）而所有未存在的key查询请求都在B中处理

　　这种方式我们不会在A中创建新的key，一个特殊的客户端redis_trib作为集群的重配置将已经存在A中的key迁移到B之中，有如下命令执行：

　　CLUSTER GETKEYSINSLOT slot count

　　该命令返回某个slot中的key数量，对于每一个返回的key都会执行一个MIGRATE命令，该命令自动的将key从A迁移到B，这两种情况下都将锁定key因此没有竞争条件。

　　MIGRATE target_host target_port key target_database id timeout

　　MIGRATE命令连接到目标实例，然后发送key的数据，当返回OK就从原有的数据库中删除该key，因此从外部客户端看来同一时间key只存在于A或者B。

　　在redis集群中不需要指定而外的数据库除了0，但是迁移MIGRATE命令可以用于非集群环境中，是一个通用的命令。迁移MIGRATE命令最优化执行迁移复杂的key例如lists。但是重新配置集群不是一个明智的操作特别是在应用程序有时间限制的时候。

十、ASK重定向

　　在上一节我们简单谈及ASK重定向，为什么我们能够简单的使用MOVED重定向？因为MOVED意味着我们想要某个哈希slot永远的由另一个节点提供服务，并且后续的查询应该和试图到特定的节点上。ASK只要求后续的查询到特定的节点上。之所以需要如此是由于下次查询slot 8的可能依然在A上，因此我们希望客户端尝试A之后如果需要再查询B。由于只发生于4096分之一因此执行性能是可以接受的。

　　然而我们需要确保客户端在试图查询A之后才查询B，因此B对于设置为IMPORTING的slot的查询只接受预先发送ASKING命令的查询。简单地ASKING命令用于设置一个标志位使得节点能够为设置为IMPORTING的slot提供服务。

　　因此对于ASK重定向，客户端语义如下：

　　1）若在发送查询特定节点时收到ASK重定向信息

　　2）使用ASKING请求作为命令的开始

　　3）当前不需要修改本地的缓存将slot 8指向B

　　当哈希slot 8迁移完成时，A将发送一个MOVED错误，此时客户端可以将slot 8查询缓存定向到B。即使客户端过早的将slot 8缓存指向B，当想B查询时没有发送ASKING开头，则B将会返回一个MOVED错误指向A。

十一、客户端需要实现

　　TODO Pipelining: use MULTI/EXEC for pipelining.

　　TODO Persistent connections to nodes.

　　TODO hash slot guessing algorithm.

_{^容错机制}

十二、节点的错误检测

　　错误检查使用如下机制：

　　1）在一段时间内节点未响应发出的PING消息，则将其设置为PFAIL（可能错误）状态。

　　2）当ping其他节点时随机带上其他三个节点的信息，在信息的gossip节部分带上其他节点的flag

　　3）假如有一个节点设置为PFAIL，并且在收到的PING回复中其他节点也将其设置为PFAIL则将其设置为FAIL状态

　　4）当一个节点确认某个另外节点为FAIL时则发送消息到所有其他节点，强制收到该消息的节点将其设置为FAIL状态

　　因此一个节点在没有获取外面消息时无法独立地将某个另外节点设置为FAIl

　　仍然需要实现：当一个节点被标记为FAIL，当其他节点收到该节点的请求或连接时，将回复其“MARK AS FAIL”，当收到该消息时需要强制将自身设置为FAIL状态。

十三、集群状态检查（部分实现）

　　当集群发生变更时（更新slot或者一个节点被设置为fail等）每个节点都将检查其保持的节点列表。

　　一旦配置节点进入如下的阶段：

　　1）FAIL：集群不能工作，当一个节点进入该状态，所有的请求将被拒绝并且返回一个错误。当节点检查到集群不能同时为4096个slot提供服务时进入该状态

　　2）OK：集群工作正常：所有的4096个slot都能够被节点服务到并且没有FAIL节点

　　这意味着集群在不能为所有的4096个slot提供服务时停止工作。然而有一部分时间一个slot不能被访问因为相关联的节点有问题，但是该节点还未被设置为FAIL。在此时集群只能为其中的部分slot提供访问服务。

　　由于集群不支持MULTI、EXEC执行命令，因此程序员需要确保应用程序能够从只有一部分查询被集群接受的状态中恢复。

十四、备节点选择（未实现）

　　每一个主节点都能够有任意数量的从节点。从节点负责在主节点fail时设置自己为主节点。举例：我们有节点A1，A2，A3其中A1为主节点，A2，A3为从节点。假如A在某个阶段FAIL并且没有响应ping请求，最终其他节点通过gossip协议会将其设置为fail，当发生这种情况时，它的第一个从节点需要尝试执行选择。第一个从节点的概念非常简单。所有的从节点根据node id进行排序，最小的就为第一个从节点，依次类推，当第一从节点也被标记为fail，在后续节点执行该选择未主节点，以此类推。

　　当一个配置变更时，错有从节点检查自身主节点是否为fail，若是则变更自身状态为主节点并发送到所有的其他节点以变更配置。

十五、保护模式（未实现）

　　当网络不连通导致有孤立节点时，该节点会认为所有其他节点都为fail。这种时候他可能试图选择从节点或者更改集群配置。为了避免这种情况，节点认定其他主要节点为pfail或fail要足够长的时间以避免其采取其他动作。

　　保护模式被清除之后，集群状态就恢复正常了。

十六、主要的主节点规则

　　作为网络分离的结果之一，两个或多个分割的部分可能为所有的哈希slot提供服务。由于集群努力保持一致性，这种情况不是我们想要的，而且网络分割总是产生零个或单个可供操作的部分。如果他们有大部分原来的主节点，当这些规则节点被放到一个部分之中他们应该只提供查询服务。

 十七、分发与订阅（未实现需要重定义）

　　在一个集群中的客户端能够订阅任何一个节点，也能够发布到任何一个节点。集群将确保若需要能够得到转发。当前实现只是简单地广播订阅消息到所有节点，在某些时候这些将通过过滤或其他算法。