Nosql，作为程序员在当下不了解点儿，还真不行，出去聊起来别人就会说你土。那么就聊聊其中一个比较火的redis。redis单机版没得说，但是一直没有集群版，有也是山寨的。前段时间对redis的实现进行了一些学习，明天就要发布redis集群的稳定版，作为纪念以及学习，发一下redis集群实现的细节，英文好的就看原文吧。
redis集群实现一个高性能、线性可扩展的1000节点的集群。
Redis集群没有最重要或者说中心节点，这个版本最主要的一个目标是设计一个线性可伸缩（可随意增删节点？）的功能。
Redis集群没有任何的数据合并动作。写，直接是与主节点通信，但同步到slave也有一个时间窗口。在可用性方面，除了master以及所有slave失效，不然一直可用。
Redis集群为了数据的一致性可能牺牲部分允许单点故障的功能，所以当网络故障和节点发生故障时这个系统会尽力去保证数据的一致性和有效性。（这里我们认为节点故障是网络故障的一种特殊情况）
为了解决单点故障的问题，我们同时需要masters 和 slaves。 即使主节点(master)和从节点(slave)在功能上是一致的，甚至说他们部署在同一台服务器上，从节点也仅用以替代故障的主节点。 实际上应该说 如果对从节点没有read-after-write（写并立即读取数据 以免在数据同步过程中无法获取数据）的需求，那么从节点仅接受只读操作。
已实现的子集
Redis集群实现单一key在非分布式版本的Redis中的所有功能。对于复合操作比如求并集求交集之类则只实现在单个节点的操作。
增加了hash tags的概念，主要用来强制把某些multi-key分配在一个节点。但是在resharding中，这些multi-key可能找不到。
Redis集群版本将不再像独立版本一样支持多数据库，在集群版本中只有database 0，并且SELECT命令是不可用的。
客户端与服务端在Redis集群版中的约定
在Redis集群版本中，节点有责任/义务保存数据和自身状态，这其中包括把数据（key）映射到正确的节点。所有节点都应该自动探测集群中的其他节点，并且在发现故障节点之后把故障节点的从节点更改为主节点（原文这里有“如果有需要” 可能是指需要设置或者说存在从节点）。
集群节点使用TCP bus和二进制协议进行互联并对任务进行分派。各节点使用gossip 协议发送ping packets给集群其他节点以确定其他节点是否正常工作。Cluster bus也可以用来在节点间执行PUB/SUB命令。
当发现集群节点无应答的时候则会使用redirections errors -MOVED and -ASK命令并且会重定向至可用节点。理论上客户端可随意向集群中任意节点发送请求并获得重定向，也就是说客户端实际上并不用关心集群的状态。然而，客户端也可以缓存数据对应的节点这样可以免去服务端进行重定向的工作，这在一定程度上可以提高效率。
安全写
Redis cluster节点之间通过异步复制，这样总会存在丢数据的窗口。但是client在连接master多的分区和少的分区的窗口是不一样的。
Redis cluster在连接master多的分区的时候，尽量保证不丢写操作。除了下面两种情况：
1）当一个写到达master，master已经回复client，但是master还没来的及复制到slave就宕机了，那么这个写操作就会丢失。直到其中一个slave被提拔为master。
2）另外一种理论上可能丢失写操作的情况如下，
一个master因为partition不可到达
其中一个slave获取master失败
一会儿后master可以重新到达
一个client没用更新路由表，还在向旧的master写
实际上，这是不太可能发生，因为节点无法到达其他大多数master故障切换，不再接收写操作需要足够的时间，并当分区固定后，一段时间内写操作仍然是拒绝的，让其他节点通知有关配置更改。
Redis cluster会丢失很多写操作，当一个或多个客户端连接到一个少master分区时。因为如果这些master不可以到达多master的分区，这些写操作就会丢失。
如果在NODE_TIMEOUT前不可到达，不会丢消息，如果在NODE_TIMEOUT后，会有消息丢失。（暂时不理解为啥不丢消息）。
可用性
少master分区是不开用的，假设多master分区至少有一个不开到达master的slave，那么在NODE_TIMEOUT后，slave就会被选举为相应的master。假设一个master有一个slave，那么可用性为1-(1/(2*n-1))。
性能
在Redis中不在通过代理命令来确定给定键的节点，而是它们将客户端重定向到服务密钥空间的给定部分的节点。
最终客户保存着集群和那个节点提供密钥的时间标识符，所以在正常操作期间，client直接联系合适的节点，以便发送给定的命令。
因为使用异步复制的，节点不等待写入的其他节点的确认。
此外，由于限制多个键执行操作命令的子集，如果不rsharding，数据从来不在节点之间移动。
所以在单个Redis的实例下，正常操作处理可以完成的，在N个主节点Redis的集群，可以期望以单一的Redis实例相同的性能乘以N作为设计的线性扩展。在同一时间，通常在单次往返执行查询，因为客户通常保持与节点持久连接，以便和单个独立的Redis节点延迟性也是一样的。
非常高的性能和弱（非CAP）的可扩展性，但合理的形式一致性和可用性是主要目标。
为什么避免合并操作
Redis集群设计避免了版本冲突的相同键值在多个节点，因为在Redis的数据模型下，这并不总是可取的：在Redis的值通常都非常大，这是经常可以看到的，列表或数百万元素的sorted set。另外，数据类型在语义上是复杂的。转移和合并这些类型的值，可能需要的应用程序端逻辑实现。
Keys分配模式
Key分为16384，这样最多可以有16384个节点，但是建议最多有1000个节点。
所有的主节点会控制16384个key空间的百分比。当集群稳定之后，也就是说不会再更改集群配置（hash slot不在节点之间移动），那么一个节点将只为一个hash slot服务。（但是服务节点（主节点）可以拥有多个从节点用来防止单点故障）
用来计算key属于哪个hash slot的算法如下：
HASH_SLOT = CRC16(key) mod 16384
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后的14个字节。在我们的测试中，对于16384个slots， CRC16算法最合适。
Keys散列tags
有一个计算hash slots的例外是使用hash tags。Hash tags以确保两个键被分配在相同的hash slot。这是用在为了实现多键在Redis集群中操作。
为了实现hash tags，hash时使用了不同的算法。基本上如果关键字包含“{...}”，那么在{和}之间的字符串被hash，然而可能有多个匹配的{或}该算法由以下规则规定：
如果key包含｛，在｛的右边有一个｝，并在第一次出现｛与第一次出现｝之间有一个或者多个字符串，那么就作为key进行hash。例如，{user1000}.following和{user1000}.followed就在同一个hash slot；foo{}{bar}整个字符被hash，foo{{bar}},{bar被hash；foo{bar}{zap},bar被hash。
集群节点特性
在集群中每个节点都拥有唯一的名字。节点名为16进制的160 bit随机数，当节点获取到名字后将被立即启用。节点名将被永久保存到节点配置文件中，除非系统管理员手动删除节点配置文件。
节点名是集群中每个节点的身份证明。在不更改节点ID的情况下是允许修改节点IP和地址的。cluster bus会自动通过gossip协议获取更改后的节点设置。
每个节点可获知其他节点的信息包括：
IP 端口
状态
管理的hash slots
cluster bus最后发送PING的时间
最后接收到PONG的时间
标记节点失败的时间
从节点数量
如果是slave，那么还包含master节点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
集群拓扑结构
Redis的集群是一个全网状的，通过TCP，每一个节点都与其他每个节点连接。在N个节点的集群中，每个节点有N-1个对外TCP连接，和N-1的传入连接。这些TCP连接一直保持着，不需要的时候才创建。
节点握手
节点永远接受集群总线端口的连接，即使ping命令的节点不被信任，当收到ping时也回复。但是，如果该节点不是集群中的，所有的其他数据包将被丢弃。
一个节点被另一个视为集群的一部分，只能通过下面两种方式：
1）如果一个节点的MEET消息。和ping消息相似，但强制把该节点做为集群的一部分。只有系统管理员通过以下的命令，节点才发送MEET消息给其他节点。
CLUSTER MEET ip port
2）节点也将注册另一个信任的节点作为集群的一部分。如果A知道B和B知道C，最终B就发送C相关的gossip消息到A。当发生这种情况，A将C作为网络的一部分，并会尝试连接C。
这意味着，只要我们加入的节点在连通图中，他们最终会自动形成一个完全连通图。基本上集群能够自动发现其他节点，但仅当由系统管理员确定。这种机制使得集群更加健壮，但可防止意外地混合不同的Redis集群将IP地址或其它变化后的网络相关事件。如果链接断开，所有节点积极尝试连接到所有其他已知的节点。
MOVED重定向
客户端发送查询到集群中的随便一个节点，甚至是slave，该节点分析查询，看key在那个节点hash slot中，如果hash slot在本节点，处理非常简单，否则检查hash slot和节点ID对应关系，方式MOVED error。
一个MOVED error如下：
GET x
-MOVED 3999 127.0.0.1:6381
错误包含key的hash slot和IP：port，客户端需要重新发出查询到指定的ip和port，在重新发送前，需要很长一段时间，那么在这期间，配置文件可能发生了变化，但是目的节点仍然回复MOVED error。
尽管集群节点由id来确定，但是我们只给客户端暴漏hash slot和IP：port的对应关系。客户端尽量记住，hash slot（3999）和27.0.0.1:6381对应。这样计算出目标key的hash slot，非常有机会直接找到相应的node。
当集群稳定，那么所有客户端有hash slot和node的对应关系，这样集群效率非常高，就不存在重定向代理和单节点故障。
集群实时重新配置
Redis的集群支持在群集运行时添加和删除节点。实际上添加或删除一个节点被抽象成相同的操作，即移动hash slot从一个节点到另一个节点。
若要将新节点添加到集群中的空节点，即hash slot从现有节点移动到新的节点。
从群集中删除一个节点，即分配给该节点的hash slot移动到其他现有节点。
因此，实施的核心是围绕移动hash slot。其实从实用的角度出发hash slot仅仅是一组key。因此Redis集群resharding是keys从一个实例键移动到另一个实例。
要理解这是如何工作，那么必须知道集群的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。分配后，将使用gossip协议在集群传播。该ADDSLOTS命令通常用于一个新的集群为所有节点从头配置slots的一个快速的方式。
SETSLOT子命令用于将slots指定给特定节点的ID，除了该节点的形式被使用。否则，该slot可指定两个特殊的状态MIGRATING和IMPORTING：
1）当一个slot被设置为MIGRATING时，该节点将接受的是关于这个哈希位置查询的所有请求，但前提是键存在。否则查询使用-ASK重定向目标节点。
2）当一个slot被设置为IMPORTING，该节点将接受的是关于这个哈希位置查询的所有请求，但只有请求被前面ASKING。否则，查询MOVED到真正的hash slot所有者。
起初这看起来很奇怪，但现在我们会更清楚。假设我们有两个Redis的节点，称为A和B。我们想要移动的hash slot8从A到B，所以我们发出的命令是这样的：
We send B: CLUSTER SETSLOT 8 IMPORTING A
We send A: CLUSTER SETSLOT 8 MIGRATING B
所有节点都指向A，每次都查询属于8的key，会发生：
All the queries about already existing keys are processed by "A".
All the queries about non existing keys in A are processed by "B".
在A就不再建立新的keys，集群配置管理工具redis－trib可以查看：
CLUSTER GETKEYSINSLOT slot count
上述命令将返回该slot中key的个数，从A迁移到B的每一个key（是原子的）都会显示，如：
MIGRATE target_host target_port key target_database id timeout
MIGRATE将连接到目标实例，发送键的序列化版本，一旦接收到ok，会删除key的旧数据集。因此在一定时间段，从外部客户端看来key存在于A或B。
在Redis的集群没有必要指定除0以外的数据库，但MIGRATE可用于不涉及Redis集群的其他任务。即使是复杂的key如lists，MIGRATE优化的也非常快。但如果有等待时间约束的应用，在重新配置redis集群，使用big keys是不明智的。
ASK重定向
在上一节中，我们简要地谈到了ASK重定向，为什么我们不能简单地用MOVED重定向？MOVED重定向意味着hash slot永久在那个节点，下一个查询应该尝试对指定的节点，ASK只表明到指定节点查询。
ASK表明hash slot8下的key仍然在A中，所以我们总是希望client将尝试A，如果需要然后B。由于这种情况只有hash slot超出16384时发生，性能损失是可以接受的。
然而，我们需要强制该客户端的行为，所以为了确保客户端将只尝试hash slotB，A尝试后，节点B就只能接受客户端发送ASK并被设置为IMPORTING hash slot的查询。
对于client，ASK语义如下：
1)如果收到ASK重定向，只把这次查询发向指定的节点
2）伴随ASK，开始查询
3）不更新hash slot 8 到B的映射
如果hash slot 8迁移完成，那么就会发送MOVED消息，client会永久保存hash slot 8到新IP：port的映射。如果有客户端提前映射，也是没有问题的，那么查询的时候没有ASK消息，那么会发送MOVED消息，重定向到A。
多key操作
使用hash tags操作多key，下面的操作是有有效的：
MSET {user:1000}.name Angela {user:1000}.surname White
当hash slot正在从一个节点移动到另一个节点，由于人工resharding，多健操作不可用。
更具体地讲，即使在resharding，多键操作key所有位于同一节点（源或目的节点），key仍然可用。
在resharding，源和目的分开，多健操作将产生TRYAGAIN error，client在稍后尝试操作，或汇报错误。
容错
节点心跳和gossip消息
每一秒，通常一个节点将ping几个随机节点，这样ping的数据包的总数量（和接收的pong包 ）是一个恒定的量，无论集群中节点的数量。
但是每个节点可确保ping通，ping或pong不超过一半NODE_TIMEOUT。前NODE_TIMEOUT已过，节点也尝试重新与另一个节点的TCP链接，节点不相信因为当前TCP链接，是不可达的。
信息的交换量大于O（N） ，NODE_TIMEOUT设置为一个小的数字，但节点的数量（N）是非常大的，因为每个节点将尝试ping ，如果配置信息在NODE_TIMEOUT一半的时间没有更新。
例如，NODE_TIMEOUT设置为60秒的100个节点集群，每个节点会尝试发送99 ping每30秒，那么每秒3.3个ping，即乘以100个节点是每秒330个ping。
有一些方法可以使用已经通过交换的Redis集群的gossip信息，以减少交换的消息的数量。例如，我们可以ping那些一半NODE_TIMEOUT内“可能的失败”状态的节点，然后每秒ping几个包到那些工作的节点。然而，在现实世界中，设置非常小的NODE_TIMEOUT的大型集群可靠地工作，将在未来作为大型集群实际部署测试。
ping和pong消息内容
ping和pong都包含一个通用的header和一个gossip消息节。
通用的header内容如下：
1）节点ID，在创建节点的时候分配的一个160位的伪随机数，并在集群中保持不变。
2）currentEpoch和configEpoch字段，这是为了安装Redis集群的分布式算法使用。如果节点是一个slave，那么configEpoch是master最后版本的configEpoch。
3）节点的标志，表明该节点是slave、master和其他单位节点的信息。
4）给定节点的hash slot位图，如果该节点是slave，那么是master hash slot的位图。
5）端口：发送方的TCP基本端口（也就是，使用Redis的接受客户端的命令，加10000，得到集群的端口）。
6）状态：发送者的状态（down或OK）。
7）主节点的ID，如果是slave。
ping和pong都包含一个gossip节，给接受者提供集群中其他节点的信息，只是sender知道的随机几个节点的信息。
gossip节中，每个节点的信息如下：
ID
ip和port
节点状态
receiver从sender获得其他节点信息，这在故障检测和节点发现是非常有用的。
故障检测
故障检测用于失败master或slave不可达，提一个slave为master，如果失败，那么集群阻止clients的查询。
每个节点保存已知节点的状态列表，包括两种状态PFAIL和FAIL，PFAIL意思是可能失败，不确信。FAIL的意思是，大部分master在固定的时间，确定是失败的。
PFAIL flag
如果一个节点在超过NODE_TIMEOUT时间不可到达一个节点，那么master和slave标志这个节点为PFAIL。
不可到达的意思是，ping在经过NODE_TIMEOUT还没有回复，因此NODE_TIMEOUT必须大于网络往返的时间。为了可用性，节点在超过一半NODE_TIMEOUT后，进行重连，这样一直保持着连接，不至于误报故障。
FAIL flag
PFAIL只是一个节点本地的信息，不足把slave提为master。认为一个节点down，那么必须是FAIL。
每个节点发送的gossip消息都包含一些随机节点的状态，这样每个节点都会收到其他节点的状态，可以标志其他节点已经检测到的故障。
遇到以下情况，就会由PFAIL过度到FAIL：
一些节点标识B为PFAIL，并且调用A，那么A收集其他master对B标识的状态，在NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT时间范围内，标识为PFAIL。A将会标识B为FAIL，发送B的标识FAIL到其他节点。强制其他节点标识B为FAIL。
如果要清除FAIL flag，有以下两种情况：
1）一个节点为slave并可以到达，那么FAIL flag被清除。
2）一个节点为master并可以到达，没有hash slot，可以清除FAIL flag，等待加入集群。
3）一个节点为master可以到达，但很长一段时间（NODE_TIMEOUT＊ N），没有检测到slave可以提为master。
但从PFAIL转化为FAIL过程中，使用的协议非常弱：
1）收集其他节点的意见，因为这一段时间，不可以确定状态是稳定的。
2）当一个节点检测到FAIL条件，强制其他节点使用FAIL消息，但是不可以确定是否可以到达所有节点。
然而，Redis的集群故障检测具有活跃性要求：最终所有节点即使在分区都应该同意有关给定节点的状态。一旦分区愈合，一些少数节点认为节点是在故障状态，或相信该节点是不在故障状态。在这两种情况下，最终给定节点的状态只有一个。
案例1：如果多数masters标记一个节点失败，那么其他节点最终也标志为失败。
案例2：只有少数masters标记一个节点发生故障，slave提为master失败，那么就会清除FAIL flag。
基本上FAIL flag只是为了提slave为master算法的安全执行。在理论上slave是独立运行的，当一个master不可到达时，开始提slave，但实际上，大多master是可以访问该master的，这样PFAIL转化为FAIL就太复杂，这样FAIL消息就可以强制执行，阻止写操作，其实是由于slave到达不了master引起，不需要slave提为msater。
Cluster epoch
currentEpoch是一个64位无符号整数，节点新建立时，设置currentEpoch为0。一个节点收到一个消息，currentEpoch比本地的大，那么更新本地的currentEpoch。通过这种策略，集群中节点接受比较大的currentEpoch。在slave升级为master中起重要作用。
config epoch
每一个master，在ping或pong消息中都包含他的configEpoch。当一个新的节点建立时，master的configEpoch设置为0。
slave选举时，建立一个新的configEpoch，slave增加Epoch取代失败的master，得到大部分masters的认证。若slave认证了，建立一个新的configEpoch，slave就变为master了。configEpoch有助于解决不同节点分散的配置冲突。
slave在ping或pong消息中都包含他的master的configEpoch，这使得其他实例来检测一个slave有一个旧的配置需要被更新。每次configEpoch改变都存储在nodes conf文件。
目前，当一个节点被重新启动其currentEpoch被设定为已知的节点的最大configEpoch 。这是不安全的崩溃恢复系统模型，为了持久保存currentEpoch，系统将会被修改。
slave选举和推广
一个slave在满足以下条件会进行选举：
1）master处在FAIL状态
2）master有服务的hash slot
3）slave和master断开连接没有超过给定的时间，为了保证slave上的数据有意义
开始选举前，增加currentEpoch，发送FAILOVER_AUTH_REQUEST消息，等待回包的最大时间为2倍的NODE_TIMEOUT，一个master回复了FAILOVER_AUTH_ACK，在2倍的NODE_TIMEOUT时间内，不再回复相同master的slave选举。不能保证安全，但是在同一时间可避免多个slave选举。
slave忽略currentEpoch小于发送的AUTH_ACK。
如果slave在2倍的NODE_TIMEOUT没有收到master的回复，那么另一个slave在经过4陪的NODE_TIMEOUT后，重新选举。
选举不是在master一处于FAIL状态就开始的，需要经过DELAY，
DELAY = 500 milliseconds + random delay between 0 and 500 milliseconds +SLAVE_RANK * 1000 milliseconds.
DELAY为了使masters知道该master的FAIL状态。随机时间，为了不同的选举在不同的时间。SLAVE_RANK，最新更新的slave为0，一次上涨。
如果一个slave成为master，那么在ping和pong包中包括服务的hash slot、为currentEpoch的configEpoch。为了快速传播新的配置，可以广播pong包。
如果其他节点检测到新的master在服务原来的hash slot，那么更新配置，如果旧的master或slave加入，需要从新master复制配置。
master回复slave选举请求
回复必须满足以下条件：
1）一个给定的epoch只回复一次，不回复低于lastVoteEpoch的currentEpoch。
2）master处在FAIL状态
3）小于master currentEpoch的请求被忽略。例如master currentEpoch为5，lastVoteEpoch为1，slave currentEpoch为3，那么elect currentEpoch为4，不回复。slave重试，currentEpoch为5，那么认为是有效的。
4）在两倍的NODE_TIMEOUT时间内，不回复相同master的slave选举。
5）master不尝试选择最好的slave。
6）master拒绝支持给定的slave，这个请求被简单忽略。
7）还不太理解
slave选举中的竞态条件
一个master有A、B、C三个slave，master处在FAIL状态，A选举为master，但是产生了partition，选举B为master，随后B处在FAIL状态，A也可达了，那么A和C争当master，但是C的currentEpoch大，那么C就作为master。
服务器slots信息传播规则
规则一：如果一个节点声明，没有hash slots，那么修改hash slots，关联到这个节点。
规则二：如果一个节点有hash slots，那么他广播的configEpoch大于slot拥有者的configEpoch，那么新节点重构hash slot。
UPDATE消息
例如特定的hash slot在master A和slave B，一段时间A被partition，B作为master，随后A又可以连接，但是他的配置是旧的，没有节点可复制，这样UPDATE消息就可起作用。当一个节点检测到一个广播的是旧的config，那么他给这个节点发送一个UPDATE消息，包含这个hash slot的节点ID和这个节点服务的hash slots。
副本迁移算法
触发的条件是，一个master没有slave，选择好的slave，并且ID最小。
configEpoch冲突解决算法
最小ID节点的configEpoch加1.
广播和订阅
现在这是节点广播所有订阅的消息到其他所有的节点，后面实现bloomfilter。
