【算法】 gossip 协议

发表于

描述 gossip 协议

作用

主要用在分布式数据库系统中各个副本节点同步数据之用

特点

组成的网络的节点都是对等节点，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致

优点

  1. 扩展性
    网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致

  2. 容错
    网络中任何节点的宕机和重启都不会影响 gossip 消息的传播，gossip 协议具有天然的分布式系统容错特性

  3. 去中心化
    gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网

  4. 一致性收敛
    gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致，消息传播速度达到了 logN。

  5. 简单
    gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。

缺点

  1. 消息的延迟
    一次只传播一部分节点，到达最终一致需要时间

  2. 消息冗余
    可能存在同一消息发到同一节点的情况

执行过程

gossip 过程是由种子节点发起

  1. gossip 是周期性地发起
  2. 由种子节点开始，随机选择 k 个邻接的节点传播消息
  3. 每次传播都是选择尚未发送过的节点进行传播
  4. 收到消息的节点往其他节点传播消息

由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议

gossip 协议