基于GOSSIP的集群成员管理-成员的加入和退出

本文是对于以下项目的算法说明。

https://github.com/xnnyygn/xgossip

首先简单介绍一下GOSSIP。

GOSSIP据说最早见于论文《Epidemic Algorithms for Replicated  Database Maintenance》,对于GOSSIP有兴趣的人建议阅读一下此论文。

GOSSIP算法如论文标题是一种epidemic algorithm,可以理解为传染病的传播。有三个人A,B,C。A是传染源,当A传染给B,B传染给C之后,所有人都被传染了。在分布式系统中,可以把传染病类比为更新,当所有参与的节点都获取到了更新之后,集群达到最终一致状态。从这个角度来说,GOSSIP是一种弱一致性,或者说最终一致性算法。

论文中主要提到了两种具体模型,一种是anti-entropy,SI模型(susceptive,infective),另一种是rumor mongering,SIR模型(susceptive infective,removed)。两者区别是后者多了一个removal状态,即节点发现自己发出去的rumor太多人知道了之后不再发送这个rumor的状态。由于这个特性,虽然rumor mongering算法会快速收敛,但是存在更新没有被发送到所有人的可能性,所以论文中建议rumor mongering加anti-entropy做备份。

模型之外还有三种传输策略,即PUSH,PULL和PUSH-PULL。PUSH更新及时但是无用功多,PULL无用功少但是更新不及时,所以一般都是用PUSH-PULL混合策略。当然混合策略具体怎么做和你如何合并数据有关。

比如说论文中的数据库同步。首先数据库相对数据量大,不可能任何时候都全量同步,对网络的压力太大,所以论文中用的是最近更新列表加一个checksum。如果两个节点checksum一致,那么就表示已同步。当有更新的时候,checksum肯定不一致,所以在checksum不一致时应用同时传过来的更新列表之后再比较checksum,一般来说checksum就会一致,同步完成。相比于直接同步所有数据,只需要传输更新和checksum,效率会高很多。

在XGOSSIP中,需要同步的数据是集群成员列表。更新主要有两类,

  • Member Join
  • Member Leave

即成员的加入和退出。仿照论文,XGOSSIP构建了增量同步策略。

  • UpdateList 最近更新列表
  • MemberList 主数据,成员列表

同时,UpdateList参照了论文,使用feedback/count策略决定更新的生命周期。具体,当其他节点回应某个更新已经被应用过之后,UpdateList会更新对应更新的无效次数,达到一定次数之后此更新无效。注意,这个策略和SIR模型中的removal有点像,但是是针对单个更新,而不是节点本身。

问题在于如何判断更新已经被应用过,和在分布式环境下安全合并MemberList。原论文中没有具体提及如何处理。个人认为是因为需要同步的是数据库,当只有一个更新源时,其他节点只需要比较自己的数据和更新的时间戳即可。

在XGOSSIP中,更新是围绕节点的状态,而加入和退出是属于节点的自发行为,相对的,通信失败等是被观测到的外部状态。通过把通信失败的观测和节点的自身状态分离,把更新来源固定到一个地方,即节点本身。考虑如下序列

  1. member A joined at 09:00
  2. member A leaved at 09:01
  3. member A joined at 09:05
  4. member A joined at 09:07

1和2是正常加入与退出,3和4是正常加入和异常退出后的加入。具体实现中只需要保存节点最后操作的时间戳和状态即可。注意,节点退出不能删除节点信息,否则无法比较数据(论文中对于数据的删除有专门的处理)。

实际实现中,MemberList参考了 CRDT 的LWW-ELement-Set,同时保存了节点的加入时间和退出时间。如果你不知道CRDT,用上面保存时间戳和状态的方式也是没问题的。

有了以上机制,如果一个更新的时间戳小于或者等于对应节点的数据的时间戳的话,那么就可以认为此更新无效,或者说已经被应用。

增量更新看起来应该完美了,但是更新本身有有效时间,一定时候会消失,所以实际的数据同步是先增量,不行再全量的方式。加上双方都有更新的话,实际的通讯次数会比纯粹的PUSH-PULL要多。

由于代码中没有明显的PUSH-PULL字样,这里简单说明一下实际的交互机制。

  1. 定时3秒向有效节点(非无效节点,即ping得通的节点)发送自己的更新列表和checksum。其他节点收到后,比较或者应用更新返回结果,通过一系列交互,两个节点最终达到一致状态。
  2. 节点收到其他节点的加入或者离开消息时,应用到自己的MemberList,加入到更新列表中,找其他节点同步更新。

机制2我个人认为是可以算作PUSH的,那么机制1可以认为是PULL。但是由于机制2的同步更新和机制1用的是同样的代码,所以并不完全可以那么归类。

不管怎么说,现在的机制,可以保证实时性(机制2),完整性(机制1的定时任务),流量的可控(增量同步和更新的消失)。

以上大致介绍了一下XGOSSIP中实现成员加入和退出管理的部分,对于其他节点观测到的状态,个人认为是属于Failure Detection的范畴,将在下回讲解。

另外如果对XGOSSIP有兴趣,欢迎直接阅读源代码。如果有任何建议和问题,也欢迎联系我,谢谢。