`
QING____
  • 浏览: 2228370 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Redis Cluster实现原理

 
阅读更多

一、Redis Cluster主要特性和设计

    集群目标

    1)高性能和线性扩展,最大可以支撑到1000个节点;Cluster架构中无Proxy层,Master与slave之间使用异步replication,且不存在操作的merge。(即操作不能跨多个nodes,不存在merge层)

    2)一定程度上保证writes的安全性,需要客户端容忍一定程度的数据丢失:集群将会尽可能(best-effort)保存客户端write操作的数据;通常在failover期间,会有短暂时间内的数据丢失(因为异步replication引起);当客户端与少数派的节点处于网络分区时(network partition),丢失数据的可能性会更高。(因为节点有效性检测、failover需要更长的时间)

    3)可用性:只要集群中大多数master可达、且失效的master至少有一个slave可达时,集群都可以继续提供服务;同时“replicas migration”可以将那些拥有多个slaves的master的某个slave,迁移到没有slave的master下,即将slaves的分布在整个集群相对平衡,尽力确保每个master都有一定数量的slave备份。

 

    (Redis Cluster集群有多个shard组成,每个shard可以有一个master和多个slaves构成,数据根据hash slots配额分布在多个shard节点上,节点之间建立双向TCP链接用于有效性检测、Failover等,Client直接与shard节点进行通讯;Cluster集群没有Proxy层,也没有中央式的Master用于协调集群状态或者state存储;集群暂不提供动态reblance策略)

    备注:下文中提到的query、查询等语义,泛指redis的读写操作。

 

    Mutli-key操作

    Redis单实例支持的命令,Cluster也都支持,但是对于“multi-key”操作(即一次RPC调用中需要进行多个key的操作)比如Set类型的交集、并集等,则要求这些key必须属于同一个node。Cluster不能进行跨Nodes操作,也没有nodes提供merge层代理。

    Cluster中实现了一个称为“hash tags”的概念,每个key都可以包含一个自定义的“tags”,那么在存储时将根据tags计算此key应该分布在哪个nodes上(而不是使用key计算,但是存储层面仍然是key);此特性,可以强制某些keys被保存在同一个节点上,以便于进行“multikey”操作,比如“foo”和“{foo}.student”将会被保存在同一个node上。不过在人工对slots进行resharding期间,multikey操作可能不可用。

 

    我们在Redis单例中,偶尔会用到“SELECT”指令,即可以将key保存在特定的database中(默认database索引号为0);但是在Cluster环境下,将不支持SELECT命令,所有的key都将保存在默认的database中。

 

    客户端与Server角色

    集群中nodes负责存储数据,保持集群的状态,包括keys与nodes的对应关系(内部其实为slots与nodes对应关系)。nodes也能够自动发现其他的nodes,检测失效的节点,当某个master失效时还应该能将合适的slave提升为master。

    

    为了达成这些行为,集群中的每个节点都通过TCP与其他所有nodes建立连接,它们之间的通信协议和方式称为“Redis Cluster Bus”。Nodes之间使用gossip协议(参见下文备注)向其他nodes传播集群信息,以达到自动发现的特性,通过发送ping来确认其他nodes工作正常,也会在合适的时机发送集群的信息。当然在Failover时(包括人为failover)也会使用Bus来传播消息。

     (gossip:最终一致性,分布式服务数据同步算法,node首选需要知道(可以读取配置)集群中至少一个seed node,此node向seed发送ping请求,此时seed节点pong返回自己已知的所有nodes列表,然后node解析nodes列表并与它们都建立tcp连接,同时也会向每个nodes发送ping,并从它们的pong结果中merge出全局nodes列表,并逐步与所有的nodes建立连接.......数据传输的方式也是类似,网络拓扑结构为full mesh)

    因为Node并不提供Proxy机制,当Client将请求发给错误的nodes时(此node上不存在此key所属的slot),node将会反馈“MOVED”或者“ASK”错误信息,以便Client重新定向到合适的node。理论上,Client可以将请求发送给任意一个nodes,然后根据在根据错误信息转发给合适的node,客户端可以不用保存集群的状态信息,当然这种情况下性能比较低效,因为Client可能需要2次TCP调用才能获取key的结果,通常客户端会缓存集群中nodes与slots的映射关系,并在遇到“Redirected”错误反馈时,才会更新本地的缓存。

 

    安全写入(write safety)

    在Master-slaves之间使用异步replication机制,在failover之后,新的Master将会最终替代其他的replicas(即slave)。在出现网络分区时(network partition),总会有一个窗口期(node timeout)可能会导致数据丢失;不过,Client与多数派的Master、少数派Master处于一个分区(网络分区,因为网络阻断问题,导致Clients与Nodes被隔离成2部分)时,这两种情况下影响并不相同。

    1)write提交到master,master执行完毕后向Client反馈“OK”,不过此时可能数据还没有传播给slaves(异步replication);如果此时master不可达的时间超过阀值(node timeout,参见配置参数),那么将触发slave被选举为新的Master(即Failover),这意味着那些没有replication到slaves的writes将永远丢失了!

    2)还有一种情况导致数据丢失:

        A)因为网络分区,此时master不可达,且Master与Client处于一个分区,且是少数派分区。

        B)Failover机制,将其中一个slave提升为新Master。

        C)此后网络分区消除,旧的Master再次可达,此时它将被切换成slave。

        D)那么在网络分区期间,处于少数派分区的Client仍然将write提交到旧的Master,因为它们觉得Master仍然有效;当旧的Master再次加入集群,切换成slave之后,这些数据将永远丢失。



 

    在第二种情况下,如果Master无法与其他大多数Masters通讯的时间超过阀值后,此Master也将不再接收Writes,自动切换为readonly状态。当网络分区消除后,仍然会有一小段时间,客户端的write请求被拒绝,因为此时旧的Master需要更新本地的集群状态、与其他节点建立连接、角色切换为slave等等,同时Client端的路由信息也需要更新。

    只有当此master被大多数其他master不可达的时间达到阀值时,才会触发Failover,这个时间称为NODE_TIMEOUT,可以通过配置设定。所以当网络分区在此时间被消除的话,writes不会有任何丢失。反之,如果网络分区持续时间超过此值,处于“小分区”(minority)端的Master将会切换为readonly状态,拒绝客户端继续提交writes请求,那么“大分区”端将会进行failover,这意味着NODE_TIMEOUT期间发生在“小分区”端的writes操作将丢失(因为新的Master上没有同步到那些数据)。 

 

    可用性

    处于“小分区”的集群节点是不可用的;“大分区”端必须持有大多数Masters,同时每个不可达的Master至少有一个slave也在“大分区”端,当NODE_TIMEOUT时,触发failover,此后集群才是可用的。Redis Cluster在小部分nodes失效后仍然可以恢复有效性,如果application希望大面积节点失效仍然有效,那么Cluster不适合这种情况。

 

    比如集群有N个Master,且每个Master都有一个slave,那么集群的有效性只能容忍一个节点(master)被分区隔离(即一个master处于小分区端,其他处于大分区端),当第二个节点被分区隔离之前仍保持可用性的概率为1 - (1/(N * 2 - 1))(解释:当第一个节点失效后,剩余N * 2 -1个节点,此时没有slave的Master失效的概率为1/(N * 2 -1))。比如有5个Master,每个Master有一个slave,当2个nodes被隔离出去(或者失效)后,集群可用性的概率只有1/(5 * 2 - 1) = 11.11%,因此集群不再可用。

    幸好Redis Cluster提供了“replicas migration”机制,在实际应用方面,可以有效的提高集群的可用性,当每次failover发生后,集群都会重新配置、平衡slaves的分布,以更好的抵御下一次失效情况的发生。(具体参见下文)

 

    性能

    Redis Cluster并没有提供Proxy层,而是告知客户端将key的请求转发给合适的nodes。Client保存集群中nodes与keys的映射关系(slots),并保持此数据的更新,所以通常Client总能够将请求直接发送到正确的nodes上。因为采用异步replication,所以master不会等待slaves也保存成功后才向客户端反馈结果,除非显式的指定了WAIT指令。multi-key指令仅限于单个节点内,除了resharding操作外,节点的数据不会在节点间迁移。每个操作只会在特定的一个节点上执行,所以集群的性能为master节点的线性扩展。同时,Clients与每个nodes保持链接,所以请求的延迟等同于单个节点,即请求的延迟并不会因为Cluster的规模增大而受到影响。高性能和扩展性,同时保持合理的数据安全性,是Redis Cluster的设计目标。

 

    Redis Cluster没有Proxy层,Client请求的数据也无法在nodes间merge;因为Redis核心就是K-V数据存储,没有scan类型(sort,limit,group by)的操作,因此merge操作并不被Redis Cluster所接受,而且这种特性会极大增加了Cluster的设计复杂度。(类比于mongodb)

 

二、Cluster主要组件

    keys分布模型

    集群将key分成16384个slots(hash 槽),slot是数据映射的单位,言外之意,Redis Cluster最多支持16384个nodes(每个nodes持有一个slot)。集群中的每个master持有16384个slots中的一部分,处于“stable”状态时,集群中没有任何slots在节点间迁移,即任意一个hash slot只会被单个node所服务(master,当然可以有多个slave用于replicas,slave也可以用来扩展read请求)。keys与slot的映射关系,是按照如下算法计算的:HASH_SLOT = CRC16(key) mod 16384。其中CRC16是一种冗余码校验和,可以将字符串转换成16位的数字。

 

    hash tags

    在计算hash slots时有一个意外的情况,用于支持“hash tags”;hash tags用于确保多个keys能够被分配在同一个hash slot中,用于支持multi-key操作。hash tags的实现比较简单,key中“{}”之间的字符串就是当前key的hash tags,如果存在多个“{}”,首个符合规则的字符串作为hash tags,如果“{}”存在多级嵌套,那么最内层首个完整的字符串作为hash tags,比如“{foo}.student”,那么“foo”是hash tags。如果key中存在合法的hash tags,那么在计算hash slots时,将使用hash tags,而不再使用原始的key。即“foo”与“{foo}.student”将得到相同的slot值,不过“{foo}.student”仍作为key来保存数据,即redis中数据的key仍为“{foo}.student”。

 

    集群节点的属性

    集群中每个节点都有唯一的名字,称之为node ID,一个160位随机数字的16进制表示,在每个节点首次启动时创建。每个节点都将各自的ID保存在实例的配置文件中,此后将一直使用此ID,或者说只要配置文件不被删除,或者没有使用“CLUSTER RESET”指令重置集群,那么此ID将永不会修改。

    集群通过node ID来标识节点,而不是使用IP + port,因为node可以修改它的IP和port,不过如果ID不变,我们仍然认定它是集群中合法一员。集群可以在cluster Bus中通过gossip协议来探测IP、port的变更,并重新配置。

    node ID并不是与node相关的唯一信息,不过是唯一一个全局一致的。每个node还持有如下相关的信息,有些信息是关系集群配置的,其他的信息比如最后ping时间等。每个node也保存其他节点的IP、Port、flags(比如flags表示它是master还是slave)、最近ping的时间、最近pong接收时间、当前配置的epoch、链接的状态,最重要的是还包含此node上持有的hash slots。这些信息均可通过“CLUSTER NODES”指令开查看。

 

    Cluster Bus

    每个Node都有一个特定的TCP端口,用来接收其他nodes的链接;此端口号为面向Client的端口号 + 10000,比如果客户端端口号为6379,那么次node的BUS端口号为16379,客户端端口号可以在配置文件中声明。由此可见,nodes之间的交互通讯是通过Bus端口进行,使用了特定的二进制协议,此端口通常应该只对nodes可用,可以借助防火墙技术来屏蔽其他非法访问。

 

    集群拓扑

    Redis Cluster中每个node都与其他nodes的Bus端口建立TCP链接(full mesh,全网)。比如在由N各节点的集群中,每个node有N-1个向外发出的TCP链接,以及N-1个其他nodes发过来的TCP链接;这些TCP链接总是keepalive,不是按需创建的。如果ping发出之后,node在足够长的时间内仍然没有pong响应,那么次node将会被标记为“不可达”,那么与此node的链接将会被刷新或者重建。Nodes之间通过gossip协议和配置更新的机制,来避免每次都交互大量的消息,最终确保在nodes之间的信息传送量是可控的。

 

    节点间handshake

    Nodes通过Bus端口发送ping、pong;如果一个节点不属于集群,那么它的消息将会被其他nodes全部丢弃。一个节点被认为是集群成员的方式有2种:

    1)如果此node在“Cluster meet”指令中引入,此命令的主要意义就是将指定node加入集群。那么对于当前节点,将认为指定的node为“可信任的”。(此后将会通过gossip协议传播给其他nodes)

    2)当其他nodes通过gossip引入了新的nodes,这些nodes也是被认为是“可信任的”。

 

    只要我们将一个节点加入集群,最终此节点将会与其他节点建立链接,即cluster可以通过信息交换来自动发现新的节点,链接拓扑仍然是full mesh。

 

三、重定向与resharding

    MOVED重定向

    理论上,Client可以将请求随意发给任何一个node,包括slaves,此node解析query,如果可以执行(比如语法正确,multiple keys都应该在一个node slots上),它会查看key应该属于哪个slot、以及此slot所在的nodes,如果当前node持有此slot,那么query直接执行即可,否则当前node将会向Client反馈“MOVED”错误:

GET X
-MOVED 3999 127.0.0.1:6381

 

    错误信息中包括此key对应的slot(3999),以及此slot所在node的ip和port,对于Client 而言,收到MOVED信息后,它需要将请求重新发给指定的node。不过,当node向Client返回MOVED之前,集群的配置也在变更(节点调整、resharding、failover等,可能会导致slot的位置发生变更),此时Client可能需要等待更长的时间,不过最终node会反馈MOVED信息,且信息中包含指定的新的node位置。虽然Cluster使用ID标识node,但是在MOVED信息中尽可能的暴露给客户端便于使用的ip + port。

 

    当Client遇到“MOVED”错误时,将会使用“CLUSTER NODES”或者“CLUSTER SLOTS”指令获取集群的最新信息,主要是nodes与slots的映射关系;因为遇到MOVED,一般也不会仅仅一个slot发生的变更,通常是一个或者多个节点的slots发生了变化,所以进行一次全局刷新是有必要的;我们还应该明白,Client将会把集群的这些信息在被缓存,以便提高query的性能。

    还有一个错误信息:“ASK”,它与“MOVED”都属于重定向错误,客户端的处理机制基本相同,只是ASK不会触发Client刷新本地的集群信息。

 

    集群运行时重新配置(live reconfiguration)

    我们可以在Cluster运行时增加、删除nodes,这两种操作都会导致:slots在nodes的迁移;当然这种机制也可用来集群数据的rebalance等等。

    1)集群中新增一个node,我们需要将其他nodes上的部分slots迁移到此新nodes上,以实现数据负载的均衡分配。

    2)集群中移除一个node,那么在移除节点之前,必须将此节点上(如果此节点没有任何slaves)的slots迁移到其他nodes。

    3)如果数据负载不均衡,比如某些slots数据集较大、负载较大时,我们需要它们迁移到负载较小的nodes上(即手动resharding),以实现集群的负载平衡。

 

    Cluster支持slots在nodes间移动;从实际的角度来看,一个slot只是一序列keys的逻辑标识,所以Cluster中slot的迁移,其实就是一序列keys的迁移,不过resharding操作只能以slot为单位(而不能仅仅迁移某些keys)。Redis提供了如下几个操作:

    1)CLUSTER ADDSLOTS [slot] ....

    2)CLUSTER DELSLOTS [slot] ...

    3)CLUSTER SETSLOT [slot] NODE [node]

    4)CLUSTER SETSLOT [slot] MIGRATING [destination-node]

    5)CLUSTER SETSLOT [slot] IMPORTING [source-node]

 

    前两个指令:ADDSLOTS和DELSLOTS,用于向当前node分配或者移除slots,指令可以接受多个slot值。分配slots的意思是告知指定的master(即此指令需要在某个master节点执行)此后由它接管相应slots的服务;slots分配后,这些信息将会通过gossip发给集群的其他nodes。

    ADDSLOTS指令通常在创建一个新的Cluster时使用,一个新的Cluster有多个空的Masters构成,此后管理员需要手动为每个master分配slots,并将16384个slots分配完毕,集群才能正常服务。简而言之,ADDSLOTS只能操作那些尚未分配的(即不被任何nodes持有)slots,我们通常在创建新的集群或者修复一个broken的集群(集群中某些slots因为nodes的永久失效而丢失)时使用。为了避免出错,Redis Cluster提供了一个redis-trib辅助工具,方便我们做这些事情。

 

    DELSLOTS就是将指定的slots删除,前提是这些slots必须在当前node上,被删除的slots处于“未分配”状态(当然其对应的keys数据也被clear),即尚未被任何nodes覆盖,这种情况可能导致集群处于不可用状态,此指令通常用于debug,在实际环境中很少使用。那些被删除的slots,可以通过ADDSLOTS重新分配。

 

    SETSLOT是个很重要的指令,对集群slots进行reshard的最重要手段;它用来将单个slot在两个nodes间迁移。根据slot的操作方式,它有两种状态“MIGRATING”、“IMPORTING”(或者说迁移的方式)

    1)MIGRATING:将slot的状态设置为“MIGRATING”,并迁移到destination-node上,需要注意当前node必须是slot的持有者。在迁移期间,Client的查询操作仍在当前node上执行,如果key不存在,则会向Client反馈“-ASK”重定向信息,此后Client将会把请求重新提交给迁移的目标node。

    2)IMPORTING:将slot的状态设置为“IMPORTING”,并将其从source-node迁移到当前node上,前提是source-node必须是slot的持有者。Client交互机制同上。

 

    假如我们有两个节点A、B,其中slot 8在A上,我们希望将8从A迁移到B,可以使用如下方式:

    1)在B上:CLUSTER SETSLOT 8 IMPORTING A

    2)在A上:CLUSTER SETSLOT 8 MIGRATING B

    在迁移期间,集群中其他的nodes的集群信息不会改变,即slot 8仍对应A,即此期间,Client查询仍在A上:

    1)如果key在A上存在,则有A执行。

    2)否则,将向客户端返回ASK,客户端将请求重定向到B。

    这种方式下,新key的创建就不会在A上执行,而是在B上执行,这也就是ASK重定向的原因(迁移之前的keys在A,迁移期间created的keys在B上);当上述SETSLOT执行完毕后,slot的状态也会被自动清除,同时将slot迁移信息传播给其他nodes,至此集群中slot的映射关系将会变更,此后slot 8的数据请求将会直接提交到B上。

 

    ASK重定向

    在上文中,我们已经介绍了MOVED重定向,ASK与其非常相似。在resharding期间,为什么不能用MOVED?MOVED意思为hash slots已经永久被另一个node接管、接下来的相应的查询应该与它交互,ASK的意思是当前query暂时与指定的node交互;在迁移期间,slot 8的keys有可能仍在A上,所以Client的请求仍然需要首先经由A,对于A上不存在的,我们才需要到B上进行尝试。迁移期间,Redis Cluster并没有粗暴的将slot 8的请求全部阻塞、直到迁移结束,这种方式尽管不再需要ASK,但是会影响集群的可用性。

    1)当Client接收到ASK重定向,它仅仅将当前query重定向到指定的node;此后的请求仍然交付给旧的节点。

    2)客户端并不会更新本地的slots映射,仍然保持slot 8与A的映射;直到集群迁移完毕,且遇到MOVED重定向。

 

    一旦slot 8迁移完毕之后(集群的映射信息也已更新),如果Client再次在A上访问slot 8时,将会得到MOVED重定向信息,此后客户端也更新本地的集群映射信息。

 

    客户端首次链接以及重定向处理

    可能有些Cluster客户端的实现,不会在内存中保存slots映射关系(即nodes与slots的关系),每次请求都从声明的、已知的nodes中,随机访问一个node,并根据重定向(MOVED)信息来寻找合适的node,这种访问模式,通常是非常低效的。

    当然,Client应该尽可能的将slots配置信息缓存在本地,不过配置信息也不需要绝对的实时更新,因为在请求时偶尔出现“重定向”,Client也能兼容此次请求的正确转发,此时再更新slots配置。(所以Client通常不需要间歇性的检测Cluster中配置信息是否已经更新)客户端通常是全量更新slots配置:

    1)首次链接到集群的某个节点

    2)当遇到MOVED重定向消息时

    遇到MOVED时,客户端仅仅更新特定的slot是不够的,因为集群中的reshard通常会影响到多个slots。客户端通过向任意一个nodes发送“CLUSTER NODES”或者“CLUSTER SLOTS”指令均可以获得当前集群最新的slots映射信息;“CLUSTER SLOTS”指令返回的信息更易于Client解析。如果集群处于broken状态,即某些slots尚未被任何nodes覆盖,指令返回的结果可能是不完整的。

 

    Multikeys操作

    前文已经介绍,基于hash tags机制,我们可以在集群中使用Multikeys操作。不过,在resharding期间,Multikeys操作将可能不可用,比如这些keys不存在于同一个slot(迁移会导致keys被分离);比如Multikeys逻辑上属于同一个slot,但是因为resharding,它们可能暂时不处于同一个nodes,有些可能在迁移的目标节点上(比如Multikeys包含a、b、c三个keys,逻辑上它们都属于slot 8,但是其中c在迁移期间创建,它被存储在节点B上,a、b仍然在节点A),此时将会向客户端返回“-TRYAGAIN”错误,那么客户端此后将需要重试一次,或者直接返回错误(如果迁移操作被中断),无论如何最终Multikeys的访问逻辑是一致的,slots的状态也是最终确定的。

 

    slaves扩展reads请求

    通常情况下,read、write请求都将有持有slots的master节点处理;因为redis的slaves可以支持read操作(前提是application能够容忍stale数据),所以客户端可以使用“READONLY”指令来扩展read请求。

    “READONLY”表明其可以访问集群的slaves节点,能够容忍stale数据,而且此次链接不会执行writes操作。当链接设定为readonly模式后,Cluster只有当keys不被slave的master节点持有时才会发送重定向消息(即Client的read请求总是发给slave,只有当此slave的master不持有slots时才会重定向,很好理解):

    1)此slave的master节点不持有相应的slots

    2)集群重新配置,比如reshard或者slave迁移到了其他master上,此slave本身也不持有此slot。

 

    此时Client更新本地的slot配置信息,同上文所述。(目前很多Client实现均基于连接池,所以不能非常便捷的设置READLONLY选项,非常遗憾)

 

四、容错(Fault Tolerance)

    心跳与gossip消息

    集群中的nodes持续的交换ping、pong数据,这两种数据包的结构一样,同样都能携带集群的配置信息,唯一不同的就是message中的type字段。

    通常,一个node发送ping消息,那么接收者将会反馈pong消息;不过有时候并非如此,或许接收者将pong信息发给其他的nodes,而不是直接反馈给发送者,比如当集群中添加新的node时。

    通常一个node每秒都会随机向几个nodes发送ping,所以无论集群规模多大,每个nodes发送的ping数据包的总量是恒定的。每个node都确保尽可能的向那些在半个NODE_TIMEOUT时间内,尚未发送过ping或者接收到它们的pong消息的nodes发送ping。在NODE_TIMEOUT逾期之前,nodes也会尝试与那些通讯异常的nodes重新建立TCP链接,确保不能仅仅因为当前链接异常而认为它们就是不可达的。

 

    当NODE_TIMEOUT值较小、集群中nodes规模较大时,那么全局交换的信息量也会非常庞大,因为每个node都尽力在半个NODE_TIMEOUT时间内,向其他nodes发送ping。比如有100个nodes,NODE_TIMEOUT为60秒,那么每个node在30秒内向其他99各nodes发送ping,平均每秒3.3个消息,那么整个集群全局就是每秒330个消息。这些消息量,并不会对集群的带宽带来不良问题。

 

    心跳数据包的内容

    1)node ID

    2)currentEpoch和configEpoch

    3)node flags:比如表示此node是maste、slave等

    4)hash slots:发送者持有的slots

    5)如果发送者是slave,那么其master的ID

    6)其他..

 

    ping和pong数据包中也包含gossip部分,这部分信息包含sender持有的集群视图,不过它只包含sender已知的随机几个nodes,nodes的数量根据集群规模的大小按比例计算。gossip部分包含了nodes的ID、ip+port、flags,那么接收者将根据sender的视图,来判定节点的状态,这对故障检测、节点自动发现非常有用。

 

    失效检测

    集群失效检测就是,当某个master或者slave不能被大多数nodes可达时,用于故障迁移并将合适的slave提升为master。当slave提升未能有效实施时,集群将处于error状态且停止接收Client端查询。

    如上所述,每个node有持有其已知nodes的列表包括flags,有2个flag状态:PFAIL和FAIL;PFAIL表示“可能失效”,是一种尚未完全确认的失效状态(即某个节点或者少数masters认为其不可达)。FAIL表示此node已经被集群大多数masters判定为失效(大多数master已认定为不可达,且不可达时间已达到设定值,需要failover)。

 

    PFAIL:

    一个被标记为PFAIL的节点,表示此node不可达的时间超过NODE_TIMEOUT,master和slave有可以被标记为PFAIL。所谓不可达,就是当“active ping”(发送ping且能受到pong)尚未成功的时间超过NODE_TIMEOUT,因此我们设定的NODE_TIMEOUT的值应该比网络交互往返的时间延迟要大一些(通常要大的多,以至于交互往返时间可以忽略)。为了避免误判,当一个node在半个NODE_TIMEOUT时间内仍未能pong,那么当前node将会尽力尝试重新建立连接进行重试,以排除pong未能接收是因为当前链接故障的问题。

 

    FAIL:

    PFAIL只是当前node有关于其他nodes的本地视图,可能每个node对其他nodes的本地视图都不一样,所以PFAIL还不足以触发Failover。处于PFAIL状态下的node可以被提升到FAIL状态。如上所述,每个node在向其他nodes发送gossip消息时,都会包含本地视图中几个随机nodes的状态信息;每个node最终都会从其他nodes发送的消息中获得一组nodes的flags。因此,每个node都可以通过这种机制来通知其他nodes,它检测到的故障情况。

    PFAIL被上升为FAIL的集中情况:

    1)比如A节点,认为B为PFAIL

    2)那么A通过gossip信息,收集集群中大多数masters关于B的状态视图。

    3)多数master都认为B为PFAIL,或者PFAIL情况持续时间为NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT(此值当前为2)

 

    如果上述条件成立,那么A将会:

    1)将B节点设定为FAIL

    2)将FAIL信息发送给其所有能到达的所有节点。

 

    每个接收到FAIL消息的节点都会强制将此node标记为FAIL状态,不管此节点在本地视图中是否为PFAIL。FAIL状态是单向的,即PFAIL可以转换为FAIL,但是FAIL状态只能清除,不能回转为PFAIL:

    1)当此node已经变的可达,且为slave,这种情况下FAIL状态将会被清除,因为没有发生failover。

    2)此node已经可达,且是一个没有服务任何slots的master(空的master);这种情况下,FAIL将会被清除,因为master没有持有slots,所以它并没有真正参与到集群中,需要等到重新配置以便它加入集群。

    3)此node已经可达,且是master,且在较长时间内(N倍的NODE_TIMEOUT)没有检测到slave的提升,即没有slave发生failover(比如此master下没有slave),那么它只能重新加入集群且仍为master。

 

    需要注意的是PFAIL->FAIL的转变,使用了“协议”(agreement)的形式:

    1)nodes会间歇性的收集其他nodes的视图,即使大多数masters都“agree”,事实上这个状态,仅仅是我们从不同的nodes、不同的时间收集到的,我们无法确认(也不需要)在特定时刻大多数masters是否“agree”。我们丢弃较旧的故障报告,所以此故障(FAIL)是有大多数masters在一段时间内的信号。

    2)虽然每个node在检测到FAIL情况时,都会通过FAIL消息发送给其他nodes,但是无法保证消息一定会到达所有的nodes,比如可能当前节点(发送消息的node)因为网络分区与其他部分nodes隔离了。

 

    如果只有少数master认为某个node为FAIL,并不会触发相应的slave提升,即failover,因为可能是因为网络分区导致。FAIL标记只是用来触发slave 提升;在原理上,当master不可达时将会触发slave提升,不过当master仍然被大多数可达时,它会拒绝提供相应的确认。

 

五、Failover相关的配置

    集群currentEpoch

    Redis Cluster使用了类似于Raft算法“term”(任期)的概念,那么在redis Cluster中term称为epoch,用来给events增量版本号。当多个nodes提供了信息有冲突时,它可以作为node来知道哪个状态是最新的。currentEpoch为一个64位无签名数字。

    在集群node创建时,master和slave都会将各自的currentEpoch设置为0,每次从其他node接收到数据包时,如果发现发送者的epoch值比自己的大,那么当前node将自己的currentEpoch设置为发送者的epoch。由此,最终所有的nodes都会认同集群中最大的epoch值;当集群的状态变更,或者node为了执行某个行为需求agreement时,都将需要epoch(传递或者比较)。

 

    当前来说,只有在slave提升期间发生;currentEpoch为集群的逻辑时钟(logical clock),指使持有较大值的获胜。(currentEpoch,当前集群已达成认同的epoch值,通常所有的nodes应该一样)

 

    configEpoch

    每个master总会在ping、pong数据包中携带自己的configEpoch以及它持有的slots列表。新创建的node,其configEpoch为0,slaves通过递增它们的configEpoch来替代失效的master,并尝试获得其他大多数master的授权(认同)。当slave被授权,一个新的configEpoch被生成,slave提升为master且使用此configEpoch。

    接下来介绍configEpoch帮助解决冲突,当不同的nodes宣称有分歧的配置时。

    slaves在ping、pong数据包中也会携带自己的configEpoch信息,不过这个epoch为它与master在最近一次数据交换时,master的configEpoch。

    每当节点发现configEpoch值变更时,都会将新值写入nodes.conf文件,当然currentEpoch也也是如此。这两个变量在写入文件后会伴随磁盘的fsync,持久写入。严格来说,集群中所有的master都持有唯一的configEpoch值。同一组master-slaves持有相同的configEpoch。

 

    slave选举与提升

    在slaves节点中进行选举,在其他masters的帮助下进行投票,选举出一个slave并提升为master。当master处于FAIL状态时,将会触发slave的选举。slaves都希望将自己提升为master,此master的所有slaves都可以开启选举,不过最终只有一个slave获胜。当如下情况满足时,slave将会开始选举:

    1)当此slave的master处于FAIL状态

    2)此master持有非零个slots

    3)此slave的replication链接与master断开时间没有超过设定值,为了确保此被提升的slave的数据是新鲜的,这个时间用户可以配置。

 

    为了选举,第一步,就是slave自增它的currentEpoch值,然后向其他masters请求投票(需求支持,votes)。slave通过向其他masters传播“FAILOVER_AUTH_REQUEST”数据包,然后最长等待2倍的NODE_TIMEOUT时间,来接收反馈。一旦一个master向此slave投票,将会响应“FAILOVER_AUTH_ACK”,此后在2 * NODE_TIMOUT时间内,它将不会向同一个master的slaves投票;虽然这对保证安全上没有必要,但是对避免多个slaves同时选举时有帮助的。slave将会丢弃那些epoch值小于自己的currentEpoch的AUTH_ACK反馈,即不会对上一次选举的投票计数(只对当前轮次的投票计数)。一旦此slave获取了大多数master的ACKs,它将在此次选举中获胜;否则如果大多数master不可达(在2 * NODE_TIMEOUT)或者投票额不足,那么它的选举将会被中断,那么其他的slave将会继续尝试。

    

    slave rank(次序)

    当master处于FAIL状态时,slave将会随机等待一段时间,然后才尝试选举,等待的时间:

    DELAY = 500ms + random(0 ~ 500ms) + SLAVE_RANK * 1000ms

    一定的延迟确保我们等待FAIL状态在集群中传播,否则slave立即尝试选举(不进行等待的话),不过此时其他masters或许尚未意识到FAIL状态,可能会拒绝投票。

 

    延迟的时间是随机的,这用来“去同步”(desynchronize),避免slaves同时开始选举。SLAVE_RANK表示此slave已经从master复制数据的总量的rank。当master失效时,slaves之间交换消息以尽可能的构建rank,持有replication offset最新的rank为0,第二最新的为1,依次轮推。这种方式下,持有最新数据的slave将会首先发起选举(理论上)。当然rank顺序也不是严格执行的,如果一个持有较小rank的slave选举失败,其他slaves将会稍后继续。

 

    一旦,slave选举成功,它将获取一个新的、唯一的、自增的configEpoch值,此值比集群中任何masters持有的都要大,它开始宣称自己是master,并通过ping、pong数据包传播,并提供自己的新的configEpoch以及持有的slots列表。为了加快其他nodes的重新配置,pong数据包将会在集群中广播。当前node不可达的那些节点,它们可以从其他节点的ping或者pong中获知信息(gossip),并重新配置。

 

    其他节点也会检测到这个新的master和旧master持有相同的slots,且持有更高的configEpoch,此时也会更新自己的配置(epoch,以及master);旧master的slaves不仅仅更新配置信息,也会重新配置并与新的master跟进(slave of)。

 

    Masters响应slave的投票请求

    当Master接收到slave的“FAILOVER_AUTH_REQUEST”请求后,开始投票,不过需要满足如下条件:

    1)此master只会对指定的epoch投票一次,并且拒绝对旧的epoch投票:每个master都持有一个lastVoteEpoch,将会拒绝AUTH_REQUEST中currentEpoch比lastVoteEpoch小的请求。当master响应投票时,将会把lastVoteEpoch保存在磁盘中。

    2)此slave的master处于FAIL状态时,master才会投票。

    3)如果slave的currentEpoch比此master的currentEpoch小,那么AUTH_REQUEST将会被忽略。因为master只会响应那些与自己的currentEpoch相等的请求。如果同一个slave再此请求投票,持有已经增加的currentEpoch,它(slave)将保证旧的投票响应不能参与计票。

 

    比如master的currentEpoch为5,lastVoteEpoch为1:

    1)slave的currentEpoch为3

    2)slave在选举开始时,使用epoch为4(先自增),因为小于master的epoch,所以投票响应被延缓。

    3)slave在一段时间后将重新选举,使用epoch为5(4 + 1,再次自增),此时master上延缓的响应发给slave,接收后视为有效。

 

    1)master在2 * NODE_TIMEOUT超时之前,不会对同一个master的slave再次投票。这并不是严格需要,因为也不太可能两个slave在相同的epoch下同时赢得选举。不过,它确保当一个slave选举成功后,它(slave)有一段缓冲时间来通知其他的slaves,避免另一个slave赢得了新的一轮的选择,避免不必要的二次failover。

    2)master并不会尽力选举最合适的slave。当slave的master处于FAIL状态,此master在当前任期(term)内并不投票,只是批准主动投票者(即master不发起选举,只批准别人的投票)。最合适的slave应该在其他slaves之前,首先发起选举。

    3)当master拒绝一个slave投票,并不会发出一个“否决”响应,而是简单的忽略。

    4)slave发送的configEpoch是其master的,还包括其master持有的slots;master不会向持有相同slots、但configEpoch只较低的slave投票。

 

    Hash Slots配置传播

    Redis Cluster中重要的一部分就是传播集群中哪些节点上持有的哪些hash slots信息;无论是启动一个新的集群,还是当master失效其slave提升后更新配置,这对它们都至关重要。有2种方式用于hash slot配置的传播:

    1)heartbeat 消息:发送者的ping、pong消息中,总是携带自己目前持有的slots信息,不管自己是master还是slave。

    2)UPDATE 消息:因为每个心跳消息中会包含发送者的configEpoch和其持有的slots,如果接收者发现发送者的信息已经stale(比如发送者的configEpoch值小于持有相同slots的master的值),它会向发送者反馈新的配置信息(UPDATE),强制stale节点更新它。

 

    当一个新的节点加入集群,其本地的hash slots映射表将初始为NULL,即每个hash slot都没有与任何节点绑定。

    Rule 1:如果此node本地视图中一个hash slot尚未分配(设置为NULL),并且有一个已知的node声明持有它,那么此node将会修改本地hash slot的映射表,将此slot与那个node关联。slave的failover操作、reshard操作都会导致hash slots映射的变更,新的配置信息将会通过心跳在集群中传播。

    Rule 2:如果此node的本地视图中一个hash slot已经分配,并且一个已知的node也声明持有它,且此node的configEpoch比当前slot关联的master的configEpoch值更大,那么此node将会把slot重新绑定到新的node上。根据此规则,最终集群中所有的nodes都赞同那个持有声明持有slot、且configEpoch最大值的nodes为slot的持有者。

 

    nodes如何重新加入集群

    node A被告知slot 1、2现在有node B接管,假如这两个slots目前有A持有,且A只持有这两个slots,那么此后A将放弃这2个slots,成为空的节点;此后A将会被重新配置,成为其他新master的slave。这个规则可能有些复杂,A离群一段时间后重新加入集群,此时A发现此前自己持有的slots已经被其他多个nodes接管,比如slot 1被B接管,slot 2被C接管。

    在重新配置时,最终此节点上的slots将会被清空,那个窃取自己最后一个slot的node,将成为它的新master。

    节点重新加入集群,通常发生在failover之后,旧的master(也可以为slave)离群,然后重新加入集群。

 

    Replica迁移

    Redis Cluster实现了一个成为“Replica migration”的概念,用来提升集群的可用性。比如集群中每个master都有一个slave,当集群中有一个master或者slave失效时,而不是master与它的slave同时失效,集群仍然可以继续提供服务。

    1)master A,有一个slave A1

    2)master A失效,A1被提升为master

    3)一段时间后,A1也失效了,那么此时集群中没有其他的slave可以接管服务,集群将不能继续服务。

 

    如果masters与slaves之间的映射关系是固定的(fixed),提高集群抗灾能力的唯一方式,就是给每个master增加更多的slaves,不过这种方式开支很大,需要更多的redis实例。

    解决这个问题的方案,我们可以将集群非对称,且在运行时可以动态调整master-slaves的布局(而不是固定master-slaves的映射),比如集群中有三个master A、B、C,它们对应的slave为A1、B1、C1、C2,即C节点有2个slaves。“Replica迁移”可以自动的重新配置slave,将其迁移到某个没有slave的master下。

    1)A失效,A1被提升为master

    2)此时A1没有任何slave,但是C仍然有2个slave,此时C2被迁移到A1下,成为A1的slave

    3)此后某刻,A1失效,那么C2将被提升为master。集群可以继续提供服务。

 

    Replica迁移算法

    迁移算法并没有使用“agree”形式,而是使用一种算法来避免大规模迁移,这个算法确保最终每个master至少有一个slave即可。起初,我们先定义哪个slave是良好的:一个良好的slave不能处于FAIL状态。触发时机为,任何一个slave检测到某个master没有一个良好slave时。参与迁移的slave必须为,持有最多slaves的master的其中一个slave,且不处于FAIL状态,且持有最小的node ID。

    比如有10个masters都持有一个slave,有2个masters各持有5个slaves,那么迁移将会发生在持有5个slaves的masters中,且node ID最小的slave node上。我们不再使用“agreement”,不过也有可能当集群的配置不够稳定时,有一种竞争情况的发生,即多个slaves都认为它们自己的ID最小;如果这种情况发生,结果就是可能多个slaves会迁移到同一个master下,不过这并没有什么害处,但是最坏的结果是导致原来的master迁出了所有的slaves,让自己变得单一。但是迁移算法(进程)会在迁移完毕之后重新判断,如果尚未平衡,那么将会重新迁移。

    最终,每个master最少持有一个slave;这个算法由用户配置的“cluster-migration-barrier”,此配置参数表示一个master至少保留多少个slaves,其他多余的slaves可以被迁出。此值通常为1,如果设置为2,表示一个master持有的slaves个数大于2时,多余的slaves才可以迁移到持有更少slaves的master下。

 

    configEpoch冲突解决算法

    在slave failover期间,会生成新的configEpoch值,需要保证唯一性。不过有2种不同的event会导致configEpoch的创建是不安全的:仅仅自增本地的currentEpoch并希望它不会发生冲突。这两个事件有系统管理员触发:

    1)CLUSTER FAILOVER:这个指令,就是人为的将某个slave提升为master,而不需要要求大多数masters的投票参与。

    2)slots的迁移,用于平衡集群的数据分布(reshard);此时本地的configEpoch也会修改,因为性能的考虑,这个过程也不需要“agreement”。

 

    在手动reshard期间,当一个hash slot从A迁移到B,resharding程序将强制B更新自己的配置信息、epoch值也修改为集群的最大值 + 1(除非B的configEpoch已经是最大值),这种变更则不需要其他nodes的agreement(注意与failover的原理不同)。通常每次resharding都会迁移多个slots,且有多个nodes参与,如果每个slots迁移都需要agreement,才能生成新的epoch,这种性能是很差的,也不可取。我们在首个slots迁移开始时,只会生成一个新的configEpoch,在迁移完毕后,将新的配置传播给集群即可,这种方式在生产环境中更加高效。

 

    因为上述两个情况,有可能(虽然概率极小)最终多个nodes产生了相同的configEpoch;比如管理员正在进行resharding,但是此时failover发生了...无论是failover还是resharding都是将currentEpoch自增,而且resharding不使用agreement形式(即其他nodes或许不知道,而且网络传播可能延迟),这就会发生epoch值的冲突问题。

 

    当持有不同slots的masters持有相同的configEpoch,这并不会有什么问题。比较遗憾的是,人工干预或者resharding会以不同的方式修改了集群的配置,Cluster要求所有的slots都应该被nodes覆盖,所以在任何情况下,我们都希望所有的master都持有不同的configEpoch。避免冲突的算法,就是用来解决当2个nodes持有相同的configEpoch:

    1)如果一个master节点发现其他master持有相同的configEpoch。

    2)并且此master逻辑上持有较小的node ID(字典顺序)

    3)然后此master将自己的currentEpoch加1,并作为自己新的configEpoch。

 

    如果有多个nodes持有相同的congfigEpoch,那么除了持有最大ID的节点外,其他的nodes都将往前推进(+1,直到冲突解决),最终保证每个master都持有唯一的configEpoch(slave的configEpoch与master一样)。对于新创建的cluster也是同理,所有的nodes都初始为不同的configEpoch。

 

    Node resets

    所有的nodes都可以进行软件级的reset(不需要重启、重新部署它们),reset为了重用集群(重新设定集群),必须需要将某个(些)节点重置后添加到其他集群。我们可以使用“CLUSTER RESET”指令:

    1)CLUSTER RESET SOFT

    2)CLUSTER RESET HARD

 

    指令必须直接发给需要reset的节点,如果没有指定reset类型,默认为SOFT。

    1)soft和hard:如果节点为slave,那么节点将会转换为master,并清空其持有的数据,成为一个空的master。如果此节点为master,且持有slots数据,那么reset操作将被中断。

    2)soft和hard:其上持有的slots将会被释放

    3)soft和hard:此节点上的nodes映射表将会被清除,此后此node将不会知道其他节点的存在与状态。

    4)hard:currentEpoch、configEpoch、lastVoteEpoch值将被重置为0。

    5)hard:此nodeID将会重新生成。

 

    持有数据的(slot映射不为空的)master不能被reset(除非现将此master上的slot手动迁移到其他nodes上,或者手动failover,将其切换成slave);在某些特定的场景下,在执行reset之前,或许需要执行FLUSHALL来清空原有的数据。

 

    集群中移除节点

    我们已经知道,将node移除集群之前,首先将其上的slots迁移到其他nodes上(reshard),然后关闭它。不过这似乎还并未结束,因为其他nodes仍然记住了它的ID,仍然不会尝试与它建立连接。因此,当我们确定将节点移除集群时,可以使用“CLUSTER FORGET <node-ID>”指令:

    1)将此node从nodes映射表中移除。

    2)然后设定一个60秒的隔离时间,阻止持有相同ID的node再次加入集群。

 

    之所以2)规则,因为FORGET指令将会通过gossip协议传播给其他nodes,集群中所有的节点都收到消息是需要一定的时间延迟。

 

参考文档:

http://redis.io/topics/cluster-spec

  • 大小: 43.1 KB
分享到:
评论
2 楼 Aceslup 2016-10-29  
好多生生的东西。不很理解。
1 楼 恋上你的味道 2016-06-13  
略长,没看完

相关推荐

    Redis Cluster的实现机制和原理

    Redis Cluster主要特性和设计,Redis Cluster主要特性和设计

    RedisCluster分区实现原理

    这篇文章通过了解这些问题来认识RedisCluster分区实现原理。RedisCluster是由多个同时服务于一个数据集合的Redis实例组成的整体,对于用户来说,用户只关注这个数据集合,而整个数据集合的某个数据子集存储在哪个...

    Redis Cluster Guide

    介绍了redis集群的原理和内部实现的流程,有助于进行redis集群的部署

    redisStudy.zip

    基本回答:Rediscluster是一个高可用集群,它基于分片(对key进行crc16,然后对16384取余)的原理,可以把他理解为是由多组哨兵集群组成,但是它不依赖哨兵 6.缓存穿透 缓存穿透指的是使用不存在的key进行大量的...

    研究各种Java技术(Springboot+Redis+Dubbo+Rocketmq)

    研究各种Java技术(Springboot+Redis+Dubbo+...whatsmars-redis Cache Service & Redis Cluster whatsmars-motan weibo分布式RPC框架 demo server whatsmars-motan-demo weibo分布式RPC框架 demo server&client;

    研究各种Java技术(Springboot+Redis+Dubbo+Rocketmq) 京东技术 www.toutiao.im

    研究各种Java技术(Springboot+Redis+Dubbo+...whatsmars-redis Cache Service & Redis Cluster whatsmars-motan weibo分布式RPC框架 demo server whatsmars-motan-demo weibo分布式RPC框架 demo server&client

    2019年 Redis从入门到高可用 分布式实战教程

    8-11 实现原理-3.故障演练(日志分析).mp4 8-10 实现原理-2.故障转移演练(客户端).mp4 8-1 sentinel-目录.mp4 7-9 主从复制常见问题.mp4 7-8 故障处理.mp4 7-7 全量复制开销 + 部分复制.mp4 7-6 全量复制.mp4 ...

    java7源码-distributed-lock:分布式锁

    今天就来聊聊分布式锁这块的知识,先具体的来看看Redis分布式锁的实现原理。 如果在公司里落地生产环境用分布式锁的时候,一定是会用开源类库的,比如Redis分布式锁,一般就是用Redisson框架就好了,非常的简便易用...

    Java思维导图xmind文件+导出图片

    redis Cluster数据分布算法之Hash slot redis使用常见问题及性能优化思路 redis高可用及高并发实战 缓存击穿、缓存雪崩预防策略 Redis批量查询优化 Redis高性能集群之Twemproxy of Redis 数据存储 MongoDB ...

    memento:在epoll TCP服务器之上的基本类似redis的hashmap实现

    我对这个主题着迷的一个仅用于学习目的的玩具项目,我决定尝试制作一个更简单的redis / memcached版本,以更好地了解它的工作原理。 该项目是具有基于文本协议的最小Redis类实现,并且与Redis一样,可以用作键值...

    flycache:一致性哈希的redis分片存储 (Redis sharding by consistent-hashing)

    功能弹性伸缩,提供控制面板,管理员可以增加和删除Redis节点Redis运行状态监控,报警Redis故障或者网络故障的灾难应对原理consistent-hashing一致性hashzookeeper保持一致性和监听文章测试如果您愿意捐助一下项目,...

    Java面试 Java分布式知识点 Java微服务知识点 面试知识点

    服务提供者能实现失效踢出是什么原理? 10 服务上线怎么不影响旧版本 10 如何解决服务调用链过长的问题? 10 dubbo核心配置 10 同一个服务多个注册的情况下可以直连某一个服务吗? 11 服务注册与发现的流程图 12 ...

Global site tag (gtag.js) - Google Analytics