Gossip算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了Gossip的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的状态都是一致的，当然这也是疫情传播的特点。
要注意到的一点是，即使有的节点因宕机而重启，有新节点加入，但经过一段时间后，这些节点的状态也会与其他节点达成一致，也就是说，Gossip天然具有分布式容错的优点。
Gossip是一个带冗余的容错算法，更进一步，Gossip是一个最终一致性算法。虽然无法保证在某个时刻所有节点状态一致，但可以保证在”最终“所有节点一致，”最终“是一个现实中存在，但理论上无法证明的时间点。
因为Gossip不要求节点知道所有其他节点，因此又具有去中心化的特点，节点之间完全对等，不需要任何的中心节点。实际上Gossip可以用于众多能接受“最终一致性”的领域：失败检测、路由同步、Pub/Sub、动态负载均衡。例如，Cassandra集群没有中心节点，各个节点的地位完全相同，它们通过gossip协议维护集群的状态。通过gossip，每个节点都能知道集群中包含哪些节点，以及这些节点的状态，这使得Cassandra集群中的任何一个节点都可以完成任意key的路由，任意一个节点不可用都不会造成灾难性的后果。
但Gossip的缺点也很明显，冗余通信会对网路带宽、CPU资源造成很大的负载，而这些负载又受限于通信频率，该频率又影响着算法收敛的速度，后面我们会讲在各种场合下的优化方法。
2.基本概念
gossip分为两种. 本文只讨论anti-entropy
■anti-entropy 只要数据不同步，就开始同步数据
■rumor mongering 每隔固定的时间同步数据
Gossip中的每个节点维护一组状态，状态可以用一个key/value对表示，还附带一个版本号，版本号大的为更新的状态。信息达到同步的时间大概是log(N)，这里N表示节点的数量。
为了保证一致性，规定数据的value及version只有宿主节点才能修改，其他节点只能间接通过Gossip协议来请求数据对应的宿主节点修改，即m (p)只能由有节点p来修改。
anti-entropy协议通过版本号大小来对数据进行更新。
两个节点（A、B）之间存在三种通信方式:
■push-gossip: A节点将数据推送给B节点，B节点更新A中比自己新的数据
■pull-gossip：A仅将摘要数据 (node,key,value,version)推送给B，B根据摘要数据来选择那些版本号比A高的数据推送给A，A更新本地。
■push-pull gossip：与pull类似，只是多了一步，A再将本地比B新的数据推送给B，B更新本地。
如果把两个节点数据同步一次定义为一个周期，则在一个周期内，push需通信1次，pull需2次，push/pull则需3次。从效果上来讲，push/pull最好，理论上一个周期内可以使两个节点完全一致。直观上也感觉，push/pull的收敛速度是最快的。
3.算法样例
Cassandra内部有一个Gossiper，每隔一秒运行一次（在Gossiper.java的start方法中），按照以下规则向其他节点发送同步消息：
1、随机取一个当前活着的节点，并向它发送同步请求
2、向随机一台不可达的机器发送同步请求
3、如果第一步中所选择的节点不是seed，或者当前活着的节点数少于seed数，则向随意一台seed发送同步请求
如果没有这个判断，考虑这样一种场景，有4台机器，{A, B, C, D}，并且配置了它们都是seed，如果它们同时启动，可能会出现这样的情形：
1、A节点起来，发现没有活着的节点，走到第三步，和任意一个种子同步，假设选择了B
2、B节点和A完成同步，则认为A活着，它将和A同步，由于A是种子，B将不再和其他种子同步
3、C节点起来，发现没有活着的节点，同样走到第三步，和任意一个种子同步，假设这次选择了D
4、C节点和D完成同步，认为D活着，则它将和D同步，由于D也是种子，所以C也不再和其他种子同步
这时就形成了两个孤岛，A和B互相同步，C和D之间互相同步，但是{A,B}和{C,D}之间将不再互相同步，它们也就不知道对方的存在了。
加入第二个判断后，A和B同步完，发现只有一个节点活着，但是seed有4个，这时会再和任意一个seed通信，从而打破这个孤岛。
参考：
http://f.dataguru.cn/thread-163038-1-1.html
http://blog.163.com/liaoxiangui@126/blog/static/795696402012121112831272/
■rumor mongering 每隔固定的时间同步数据
Gossip中的每个节点维护一组状态，状态可以用一个key/value对表示，还附带一个版本号，版本号大的为更新的状态。信息达到同步的时间大概是log(N)，这里N表示节点的数量。
为了保证一致性，规定数据的value及version只有宿主节点才能修改，其他节点只能间接通过Gossip协议来请求数据对应的宿主节点修改，即m (p)只能由有节点p来修改。
anti-entropy协议通过版本号大小来对数据进行更新。
两个节点（A、B）之间存在三种通信方式:
■push-gossip: A节点将数据推送给B节点，B节点更新A中比自己新的数据
■pull-gossip：A仅将摘要数据 (node,key,value,version)推送给B，B根据摘要数据来选择那些版本号比A高的数据推送给A，A更新本地。
■push-pull gossip：与pull类似，只是多了一步，A再将本地比B新的数据推送给B，B更新本地。
如果把两个节点数据同步一次定义为一个周期，则在一个周期内，push需通信1次，pull需2次，push/pull则需3次。从效果上来讲，push/pull最好，理论上一个周期内可以使两个节点完全一致。直观上也感觉，push/pull的收敛速度是最快的。
3.算法样例
Cassandra内部有一个Gossiper，每隔一秒运行一次（在Gossiper.java的start方法中），按照以下规则向其他节点发送同步消息：
1、随机取一个当前活着的节点，并向它发送同步请求
2、向随机一台不可达的机器发送同步请求
3、如果第一步中所选择的节点不是seed，或者当前活着的节点数少于seed数，则向随意一台seed发送同步请求
如果没有这个判断，考虑这样一种场景，有4台机器，{A, B, C, D}，并且配置了它们都是seed，如果它们同时启动，可能会出现这样的情形：
1、A节点起来，发现没有活着的节点，走到第三步，和任意一个种子同步，假设选择了B
2、B节点和A完成同步，则认为A活着，它将和A同步，由于A是种子，B将不再和其他种子同步
3、C节点起来，发现没有活着的节点，同样走到第三步，和任意一个种子同步，假设这次选择了D
4、C节点和D完成同步，认为D活着，则它将和D同步，由于D也是种子，所以C也不再和其他种子同步
这时就形成了两个孤岛，A和B互相同步，C和D之间互相同步，但是{A,B}和{C,D}之间将不再互相同步，它们也就不知道对方的存在了。
加入第二个判断后，A和B同步完，发现只有一个节点活着，但是seed有4个，这时会再和任意一个seed通信，从而打破这个孤岛。
参考：
http://f.dataguru.cn/thread-163038-1-1.html
http://blog.163.com/liaoxiangui@126/blog/static/795696402012121112831272/
没有评论:
发表评论