Redis 集群功能说明
介绍
这篇文档主要是为了说明正在进展中的Redis集群功能。文档主要分为两个部分，前一部分主要介绍我在非稳定分支已完成的代码，后一部分主要介绍还有哪些功能待实现。
本文档所有的说明都有可能在将来由于设计原因而进行更改，而未实现的计划比已实现的功能更有可能会被更改。
本文档包含了所有client library所需要的细节，但是client library的作者们需要提前意识到真正实现的细节在将来很有可能会有变化。
什么是Redis集群？
Redis集群是一个实现分布式并且允许单点故障的Redis高级版本。
Redis集群没有最重要或者说中心节点，这个版本最主要的一个目标是设计一个线性可伸缩（可随意增删节点？）的功能。
Redis集群为了数据的一致性可能牺牲部分允许单点故障的功能，所以当网络故障和节点发生故障时这个系统会尽力去保证数据的一致性和有效性。（这里我们认为节点故障是网络故障的一种特殊情况）
为了解决单点故障的问题，我们同时需要masters 和 slaves。 即使主节点(master)和从节点(slave)在功能上是一致的，甚至说他们部署在同一台服务器上，从节点也仅用以替代故障的主节点。 实际上应该说 如果对从节点没有read-after-write（写并立即读取数据 以免在数据同步过程中无法获取数据）的需求，那么从节点仅接受只读操作。
已实现子集
Redis集群会把所有的单一key存储在非分布式版本的Redis中。对于复合操作比如求并集求交集之类则未实现。
在将来，有可能会增加一种为“Computation Node”的新类型节点。这种节点主要用来处理在集群中multi-key的只读操作，但是对于multi-key的只读操作不会以集群传输到Computation Node节点再进行计算的方式实现。
Redis集群版本将不再像独立版本一样支持多数据库，在集群版本中只有database 0，并且SELECT命令是不可用的。
客户端与服务端在Redis集群版中的约定
在Redis集群版本中，节点有责任/义务保存数据和自身状态，这其中包括把数据（key）映射到正确的节点。所有节点都应该自动探测集群中的其他 节点，并且在发现故障节点之后把故障节点的从节点更改为主节点（原文这里有“如果有需要” 可能是指需要设置或者说存在从节点）。
集群节点使用TCP bus和二进制协议进行互联并对任务进行分派。各节点使用gossip 协议发送ping packets给集群其他节点以确定其他节点是否正常工作。cluster bus也可以用来在节点间执行PUB/SUB命令。
当发现集群节点无应答的时候则会使用redirections errors -MOVED and -ASK命令并且会重定向至可用节点。理论上客户端可随意向集群中任意节点发送请求并获得重定向，也就是说客户端实际上并不用关心集群的状态。然而，客户 端也可以缓存数据对应的节点这样可以免去服务端进行重定向的工作，这在一定程度上可以提高效率。
Keys分配模式
一个集群可以包含最多4096个节点（但是我们建议最多设置几百个节点）。
所有的主节点会控制4096个key空间的百分比。当集群稳定之后，也就是说不会再更改集群配置（更改配置指的增删节点），那么一个节点将只为一个hash slot服务。（但是服务节点（主节点）可以拥有多个从节点用来防止单点故障）
用来计算key属于哪个hash slot的算法如下：
HASH_SLOT = CRC16(key) mod 4096 Name: XMODEM (also known as ZMODEM or 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
这里我们会取CRC16后的12个字节。在我们的测试中，对于4096个slots， CRC16算法最合适。
集群节点特性
在集群中每个节点都拥有唯一的名字。节点名为16进制的160 bit随机数，当节点获取到名字后将被立即启用。节点名将被永久保存到节点设置文件中，除非系统管理员手动删除节点配置文件。
节点名是集群中每个节点的身份证明。在不更改节点ID的情况下是允许修改节点IP和地址的。cluster bus会自动通过gossip协议获取更改后的节点设置。
每个节点可获知其他节点的信息包括：
- IP 端口
- 状态
- 管理的hash slots
- cluster bus最后发送PING的时间
- 最后接收到PONG的时间
- 从节点数量
- 节点ID
无论是主节点还是从节点都可以通过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
节点交互
所有节点总是允许接受来自cluster bus的连接请求，并且即使请求PING的节点是不可信的也会进行应答。然而，所有来自非集群节点的packets都会被忽略。
只有以下两种情况节点才会把其他节点认为是集群的一部分：
如果一个节点使用 MEET message 介绍自己。MEET message 命令是强制其他节点把自己当成是集群的一部分。只有系统管理员使用 CLUSTER MEET ip port 命令节点才会发送MEET message给其他节点。
另外一种方式就是通过集群节点间的推荐机制。例如 如果A节点知道B节点属于集群，而B知道C节点属于集群，那么B将会发送gossip信息告知A：C是属于集群的。当A获得gossip信息之后就会尝试去连接C。
这意味着，当我们以任意连接方式为集群加入一个节点，集群中所有节点都会自动对新节点建立信任连接。也就是说，集群具备自动识别所有节点的功能，但是这仅发生在当系统管理强制为新节点与集群中任意节点建立信任连接的前提下。
这个机制使得集群系统更加健壮。
当一个节点故障时，其余节点会尝试连接其他所有已知的节点已确定其他节点的健壮性。
被移动数据的重定向
Redis客户端被允许向集群中的任意节点发送命令，其中包括从节点。被访问的节点将会分析命令中所需要的数据（这里仅指请求单个key），并自己通过判断hash slot确定数据存储于哪个节点。
如果被请求节点拥有hash slot数据（这里指请求数据未被迁移过 或者 hash slot在数据迁移后被重新计算过），则会直接返回结果，否则将会返回一个 MOVED 错误。
MOVED 错误如下：
GET x -MOVED 3999 127.0.0.1:6381
这个错误包括请求的数据所处的 hash slot（3999） 和 数据目前所属的IP:端口。客户端需要通过访问返回的IP:端口获取数据。即使在客户端请求并等待数据返回的过程中，集群配置已被更改（也就是说请求的 key在配置文件中所属的节点ID已被重定向至新的IP:端口），目标节点依然会返回一个MOVED错误。
所以虽然在集群中的节点使用节点ID来确定身份，但是map依然是靠hash slot和Redis节点的IP:端口来进行配对。
客户端虽然不被要求但是应该尝试去记住hash slot 3999现在已被转移至127.0.0.1:6381。这样的话，当一个新的命令需要从hash slot 3999获取数据时就可以有更高的几率从hash slot获取到正确的目标节点。
假设集群已经足够的稳定（不增删节点），那么所有的客户端将会拥有一份hash slots对应节点的数据，这可以使整个集群更高效，因为这样每个命令都会直接定向到正确的节点，不需要通过节点寻找节点或者重新计算hash slot对应的节点。
集群不下线更新配置
Redis集群支持线上增删节点。实际上对于系统来说，增加和删除节点在本质上是一样的，因为他们都是把hash slot从一个节点迁移至另外一个节点而已。
增加节点：集群中加入一个空节点并且把hash slot从已存在的节点们移至新节点。
删除节点：集群删除一个已存在节点并且把hash slot分散到已存在的其他节点中。
所以实现这个功能的核心就是迁移slots。实际上从某种观点上来说，hash slot只不过是一堆key的合集，所以Redis集群要做的事情只是在重分片的时候把一堆key从一个实例移动到另外一个实例。
为了清楚的了解这是如何实现的，我们需要先了解一下CLUSTER用来控制slots传输的底层命令。
这些底层命令包括：
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节点上增加/删除slots。当hash slots被赋值之后他们会通过gossip协议在整个集群进行广播（例如：大喊一声 兄弟们 我现在住在X节点 有需要我的以后请到X节点来找我）。当slots被添加，ADDSLOTS 命令是用来通知集群其余所有节点最高效的方法。
SETSLOT 命令是用来给把slot注册给一个特殊的node ID（也就是说ADDSLOTS 和 DELSLOTS 对slots进行操作是不指定节点的 而SETSLOT 是会指定节点的）。另外 SETSLOT 还包含两个特殊的状态 MIGRATING 和 IMPORTING：
当一个slot是以 MIGRATING 状态进行设置，那么目标节点将在确认key存在的前提下接受这个hash slot的所有请求，否则查询会被使用 -ASK 重定向至源节点。
当一个slot是以 IMPORTING 状态进行设置，那么目标节点只接受被设置过ASKING命令的所有请求，否则查询将会通过 -MOVED错误重定向至真正的hash slot所有者。
（MIGRATING 和 IMPORTING 我自己也没太看懂 所以这里不敢保证翻译的没有问题）
当你第一次看到以上内容的时候或许会感到困惑，不过没关系，现在我们来把思路理清楚。假设我们有2个Redis节点，一个叫A，另一个叫B。现在我们希望把hash slot8 从A移动到B，那么我们执行的命令应该如下：
We send B: CLUSTER SETSLOT 8 IMPORTING A We send A: CLUSTER SETSLOT 8 MIGRATING B
所有来自客户端对hash slot8的查询每次都会被导向至节点A，实际过程如下：
所有对A节点存在的数据查询会由A节点来处理
所有对A节点不存在的数据查询会由B节点来处理
我们会发现我们将会无法在A节点创建任何新的数据，因为会被导向B节点。为了解决这个问题，我们设计了一个叫redis-trib的特殊客户端来保证把A节点所有存在的key迁移至B节点。
我们用以下命令来处理：
CLUSTER GETKEYSINSLOT slot count
上面的命令将会返回hash slot中 count keys。对每一个key，redis-trib都会给A节点发送一个 MIGRATE 命令，这个命令会以一种原子的方式把key从A迁移到B（两个节点在迁移过程中都会被锁定）。
以下展示 MIGRATE 如何工作：
MIGRATE target_host target_port key target_database id timeout
MIGRATE 命令会先连接目标节点，并把目标key序列化后进行传输，当源节点收到OK返回值后会删除源节点上的key删除。所以从这个观点上来看，一个key只能存在A或者B而不会同时存在与A和B。
ASK 重定向
在之前的章节我们说了一下ASK重定向，为什么我们不能只是简单的使用 MOVED 重定向？因为如果使用MOVED命令则有可能会为一个key轮询集群中所有的节点，而ASK命令只询问下一个节点。
ASK是必要的因为在对于hash slot8的下一次查询命令依然是发送给A节点，我们希望客户端先尝试在A节点找数据然后在获取不到的情况下再向B节点请求数据。
然后我们真正的需求是客户端在向A节点请求数据失败后仅尝试向B节点请求数据而不再轮询。节点B将只接受带ASKING命令的IMPORTING 数据查询。
简单说，ASKING 命令给IMPORTING slot添加了一个只轮询一次的标记。
Clients implementations hints
TODO Pipelining: use MULTI/EXEC for pipelining.
TODO Persistent connections to nodes.
TODO hash slot guessing algorithm.
单点故障
节点故障侦测
故障侦测使用以下方法实现：
- 如果一个节点没有在给定时间内回复PING请求，则该一个节点会被其他节点设置 PFAIL 标志(possible failure 有可能故障)
- 如果一个节点被设置 PFAIL 标志，那么对目标节点设置 PFAIL 标志的节点会在节点之间互相进行广播通知并通知其他节点发送PING请求
- 如果有一个节点被设置 PFAIL 标志，并且其他节点也认同其为 PFAIL 状态，那么该节点会被设置为 FAIL 状态（故障）
- 一旦一个节点被设置 FAIL 标志，那么对故障节点设置 FAIL 标志的节点会通知其余所有节点
所以实际只有大多数节点认同的情况下，一个节点才会被设置为故障状态
（还在努力实现）一旦一个节点被设置为故障，那么其他任何节点收到来自故障节点的PING或者连接请求则会返回“MARK AS FAIL”从而强制故障节点把自己设置为故障
集群状态侦测（目前仅实现了一部分）：每当集群配置文件发生变更，所有集群节点都会重新扫描节点列表（这可以是由更改一个hash slot 或者只是一个节点故障造成的）
每个被扫描的节点会返回以下状态中的一个：
- FAIL：节点故障
- OK：节点正常
这意味着Redis集群被设计为有能力拒绝对故障节点的查询。然而这里有一个特例，就是一个节点从被设置为 PFAIL 到被设置为 FAIL 是有时间差的，如果仅仅是被设置为 PFAIL 还是有可能对该节点尝试连接
另外，Redis集群将不再支持MULTI/EXEC批量方法
从节点推举制度（未实现）
每个主节点可以拥有0个或者多个从节点。当主节点发生故障的时候，从节点有责任/义务推举自己成为主节点。假设我们有A1，A2，A3三个节点，A1是主节点并且A2和A3为A1的从节点
如果A1发生故障并且长时间未回复PING请求，那么其他节点将会将A1标记为故障节点。当这种情况发生的时候，第一个从节点将会尝试推举自己为主节点。
定义第一个从节点非常简单。取所有从节点中节点ID最小的那个。如果第一个从节点也被标记为故障，那么就由第二个从节点推举自己，以此类推。
实际流程是：集群配置被变更（节点故障导致的），故障节点所有的从节点检测自己是否是第一个从节点。从节点在升级为主节点后会通知其他节点更改配置
保护模式（未实现）
如果部分节点由于网络原因被隔离（比如断网），则这些节点会停止判断其他节点是否正常，而会开始从节点推举或者其他操作去更改集群配置。为了防止这 种情况发生，节点间一旦发现大部分节点在一段时间内被标记为 PFAIL 或者 FAIL 状态则会立即让集群启动保护模式以阻止集群采取任何行动（更改配置）。
一旦集群状态恢复正常则保护模式会被取消
主节点多数原则（未完成）
对于发生网络故障的情况，2个或者更多的分片有能力处理所有的hash slots。而这会影响集群数据的一致性，所以网络故障应该导致0或者只有1个分区可用。
为了强制此规则生效，所有符合主节点多数原则的节点应该强制不处理任何命令。
Publish/Subscribe（已实现，但是会重定义）
在一个Redis集群中，所有节点都被允许订阅其他节点或者对其他节点进行广播。集群系统会保证所有的广播通知给所有节点。
目前的实现仅仅是简单的一一进行广播，但是在某种程度上广播应该使用bloom filters或者其他算法进行优化。
