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

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

首先简单介绍一下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中，更新是围绕节点的状态，而加入和退出是属于节点的自发行为，相对的，通信失败等是被观测到的外部状态。通过把通信失败的观测和节点的自身状态分离，把更新来源固定到一个地方，即节点本身。考虑如下序列

member A joined at 09:00
member A leaved at 09:01
member A joined at 09:05
member A joined at 09:07

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

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

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

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

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

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

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

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

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

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