Skip to content

Introduction to gossip

A gossip protocol is a procedure or process of computer peer-to-peer communication that is based on the way epidemics spread. Some distributed systems use peer-to-peer gossip to ensure that data is disseminated to all members of a group. Some ad-hoc networks have no central registry and the only way to spread common data is to rely on each member to pass it along to their neighbours.

The origin of GOSSIP protocol

The term gossip protocol was originally coined in 1987 by Alan Demers, a researcher at Xerox’s Palo Alto Research Center, who was studying ways to route information through unreliable networks.

Gossip protocol在1987年8月由施乐公司帕洛阿尔托研究中心研究员艾伦·德默斯（Alan Demers）发表在ACM上的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出。

Fundamental

Gossip是一种去中心化的分布式协议，数据通过节点像病毒一样逐个传播

gossip.gif

  1. Gossip 是周期性的散播消息，把周期限定为 1 秒

  2. 被感染节点随机选择 k 个邻接节点（fan-out）散播消息，这里把 fan-out 设置为 3，每次最多往 3 个节点散播。

  3. 每次散播消息都选择尚未发送过的节点进行散播

  4. 收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A。

注意：Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。

Here is how the gossiper works
  1. Once per second, the gossiper will choose a random node in the cluster and initialize a gossip session with it. Each round of gossip requires three messages.
  2. The gossip initiator sends its chosen friend a GossipDigestSyn message.
  3. When the friend receives this message, it returns a GossipDigestAck message.
  4. When the initiator receives the ack message from the friend, it sends the friend a GossipDigestAck2 message to complete the round of gossip.

Advantage

  • 可扩展性（Scalable）：允许节点的任意增加和减少，新增节点的状态最终会与其他节点一致。
  • 容错（Fault-tolerance）：网络中任何节点的重启或者宕机都不会影响 gossip 协议的运行，具有天然的分布式系统容错特性。
  • 健壮性（Robust）：gossip 协议是去中心化的协议，所以集群中的所有节点都是对等的，没有特殊的节点，所以任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量。
  • 最终一致性（Convergent consistency）：谣言传播可以是指数级的快速传播，因此新信息传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据。

Disadvantage

  • 消息延迟：节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网，不可避免的造成消息延迟。
  • 消息冗余：节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此不可避免地引起同一节点多次接收同一消息，增加消息处理的压力。一次通信会对网路带宽、CUP资源造成很大的负载，而这些负载又受限于 通信频率，该频率又影响着算法收敛的速度。
  • 拜占庭问题：如果有一个恶意传播消息的节点，Gossip协议的分布式系统就会出问题。

System with gossip

常见使用gossip协议的分布式系统有

  • redis cluster
  • elasticsearch
  • Cassandra
  • Consul
  • Bitcoin 也使用 Gossip 协议来传播交易和区块信息

Reference

  • https://en.wikipedia.org/wiki/Gossip_protocol

Disclaimer
  1. License under CC BY-NC 4.0
  2. Copyright issue feedback me#imzye.me, replace # with @
  3. Not all the commands and scripts are tested in production environment, use at your own risk
  4. No privacy information is collected here
Try iOS App