Gossip 协议解析
原文发布于 systemdesign.one 网站。翻译自 Gossip Protocol Explained 。
什么是Gossip协议？
分布式系统中典型的问题包括以下几点[1]，[11]：
维护系统状态（节点的存活性）
节点之间的通信
解决这些问题的潜在方案如下[1]：
集中式状态管理服务
点对点状态管理服务
集中式状态管理服务
集中式状态管理服务（如 Apache Zookeeper ）可以配置为服务发现，以跟踪系统中每个节点的状态。尽管这种方法提供了强一致性保证，但其主要缺点是状态管理服务成为单点故障，并且在大规模分布式系统中会遇到可伸缩性问题[1]，[11]。
点对点状态管理服务
点对点状态管理方法倾向于高可用性和最终一致性。Gossip 协议算法可用于实现具有高可伸缩性和改进的韧性的点对点状态管理服务[1]。
Gossip 协议也被称为流言协议，因为信息传递方式类似于疾病传播的方式。Gossip 协议中的通信概念类似于办公室员工之间传播谣言或社交媒体网站上信息传播的方式[4]，[8]。
广播协议
分布式系统中流行的消息广播技术如下：
点对点广播
急切可靠广播
Gossip协议
点对点广播
生产者直接将消息发送给消费者的方式是点对点广播。生产者上的重试机制和消费者上的去重机制使得点对点广播是可靠的。当生产者和消费者同时发生故障时，消息将会丢失[3]。
急切可靠广播
每个节点通过可靠的网络链接将消息重新广播给其他每个节点。这种方法提供了更好的容错能力，因为在生产者和消费者同时发生故障时，消息不会丢失。剩余的节点将重新广播消息。急切可靠广播的注意事项如下[3]，[8]：
由于广播 n 个节点的 O(n²) 条消息，导致显著的网络带宽使用
由于 O(n) 线性广播，发送节点可能成为瓶颈
每个节点都存储系统中所有节点的列表，导致存储成本增加
Gossip 协议
Gossip 协议是一种用于在庞大的分布式系统中传输消息的去中心化点对点通信技术[1]，[8]。Gossip 协议的关键概念是每个节点定期向其他随机节点的子集发送消息[8]，[2]。整个系统最终将以很高的概率接收到特定的消息[11]，[3]。通俗地说，Gossip 协议是一种通过有限的本地交互来使节点构建全局地图的技术[1]。
Gossip 协议构建在稳健、可伸缩和最终一致的算法之上。Gossip 协议通常用于在分布式系统中维护节点成员列表、实现共识和故障检测[2]。此外，额外的信息，如应用层数据，可以附加在 Gossip 消息中[1]。
Gossip 协议是可靠的，因为节点故障可以通过另一个节点的消息重新传输来克服。FIFO 广播、因果广播和全序广播可以通过 Gossip 协议实现[3]。
Gossip 协议的参数，如周期和广播数，可以调整以提高 Gossip 协议的概率保证。以下工具提供 Gossip 协议的高端模拟和可视化[8]，[5]：
serf 收敛模拟器
Gossip 模拟器
Gossip 协议的以下特性使其成为大规模分布式系统中通信协议的最佳选择[12]：
限制每个节点传输的消息数量
限制带宽消耗，以防止应用性能降低
容忍网络和节点故障
只有当执行的操作是可交换的且不需要序列化时，才能使用 Gossip 协议来保持节点一致。 tombstone 是一种特殊的条目，用于使具有匹配键的数据条目无效，而无需实际删除数据。Gossip 协议使用 tombstone 来从节点中删除数据。
Gossip 协议的类型
在选择特定用例的 Gossip 协议类型时，必须考虑 Gossip 协议传播消息所需的时间以及在传播消息中产生的网络流量。Gossip 协议可以大致分为以下几种类型[8]，[10]：
抗熵模型
谣言传播模型
聚合模型
抗熵 Gossip 协议
抗熵算法是为了减少类似数据库的有状态服务的副本之间的熵。比较复制的数据并修复副本之间的差异[10]。具有最新消息的节点会在每个 Gossip 循环中与其他节点共享它[8]。
抗熵模型通常传输整个数据集，导致不必要的带宽使用。可以使用校验和、最近更新列表和 Merkle 树等技术来识别节点之间的差异，以避免传输整个数据集并降低网络带宽使用。抗熵 Gossip 协议将发送无限数量的消息而不终止[8]。
谣言传播 Gossip 协议
谣言传播协议也称为传播协议。谣言传播循环相对于抗熵循环发生得更频繁，并以最坏情况的负载淹没网络[10]。谣言传播模型仅使用最新的更新传输到节点，因此使用的资源较少，如网络带宽[8]。
在几轮通信后，消息将被标记为已删除，以限制消息数量。通常有很高的概率使消息传递到所有节点[8]。
聚合 Gossip 协议
聚合 Gossip 协议通过对每个节点的信息进行抽样并将值组合起来生成系统范围的聚合值[10]。
进一步的系统设计学习资源
订阅系统设计通讯，以便不再错过新的博客文章。您还将在通讯注册时收到接近系统设计面试的终极指南。
通过 Gossip 协议传播消息的策略
Gossip 协议是构建高可用性服务的最佳框架。选择通过 Gossip 协议传播消息的策略应该基于服务需求和可用的网络条件。每种通过 Gossip 协议传播消息的策略都涉及带宽、延迟和可靠性方面的权衡。这些传播消息的策略适用于抗熵和谣言传播模型。通过 Gossip 协议传播消息的不同策略如下[8]，[5]，[2]：
推送模型
拉取模型
推拉模型
推送模型
当只有少量更新消息时，推送模型是高效的，因为它会产生流量开销。推送模型中，具有最新消息的节点将消息发送给其他节点的随机子集[8]。
拉取模型
每个节点在拉取模型中主动轮询随机节点的子集，以查找任何更新消息。当存在许多更新消息时，此方法是高效的，因为很有可能找到具有最新更新消息的节点[8]。
推拉模型
推拉模型是快速可靠地传播更新消息的最佳策略[2]。节点可以推送新的更新消息，也可以拉取新的更新消息。在初始阶段使用推送方法是高效的，因为只有很少的节点具有更新消息。在最后阶段，由于有很多具有许多更新消息的节点，使用拉取方法是高效的[8]。
Gossip 协议性能
从特定节点传播消息的节点数量称为 fanout 。传播消息跨越整个群集所需的 Gossip 循环数量称为 cycle [8]，[5]。
传播消息跨越群集所需的 cycle 数 = 以 fanout 为基数的 O(log n) ，其中 n = 节点总数
例如，对于传播消息到 25000 个节点，大约需要 15 个 Gossip cycle 。可以将 Gossip 间隔设置为 10 毫秒，以在大型数据中心内大约 3 秒内传播消息。为了减少不必要的负载，Gossip 协议中的消息传播应该自动过期[4]。Gossip 协议实现的性能可以用以下指标来衡量[8]：
残余：尚未接收到消息的剩余节点数量应该最小化
流量：节点之间平均发送的消息数应该最小化
收敛：每个节点应尽快接收到消息
时间平均：将消息发送到每个节点所花费的平均时间应该较低
时间最后：最后一个节点接收到消息所花费的时间应该较低
一项案例研究显示，拥有 128 个节点的系统在运行 Gossip 协议时，CPU 消耗不到 2％ ，带宽消耗不到 60 KBps[11] 。
Gossip协议特性
没有正式定义 Gossip 协议的方式。一般来说，Gossip 协议应满足以下特性[8]：
节点选择必须是随机的，以执行广播
每个节点只能获得本地信息，对集群状态不了解
节点之间的通信涉及周期性的两两进程交互
每个 Gossip cycle 的传输容量有限
每个节点都采用相同的 Gossip 协议
假设节点之间的网络路径是不可靠的
节点交互频率较低
节点交互会导致状态交换
Gossip 算法
Gossip算法的高级概述如下[6]，[1]：
每个节点维护一组子集节点及其元数据的列表
定期向随机的活动对等节点的端点发出 Gossip
每个节点检查接收到的 Gossip 消息，将最高版本号合并到本地数据集中
节点的心跳计数器在特定节点参与 Gossip 交换时递增。只要心跳计数器保持增长，节点就会被标记为健康。另一方面，如果心跳计数器在长时间内没有改变，说明发生了网络分区或节点故障，该节点被视为不健康[1]。Gossip 协议中的对等节点选择具有不同的标准[12]：
利用由编程语言提供的库，如 java.util.random
与最少接触的节点交互
实施网络拓扑感知的交互
Gossip协议实现
Gossip 协议通过 User Datagram Protocol (UDP) 或 Transmission Control Protocol (TCP) 传输消息，并具有可配置但固定的广播数和间隔[12]。Gossip 协议使用节点的对等抽样服务来识别用于 Gossip 消息交换的对等节点。对等抽样服务使用随机算法选择对等节点。对等抽样服务的应用程序编程接口(API)应提供以下端点[8]：
/gossip/init：返回特定节点在启动时所知的节点列表
/gossip/get-peer：返回独立对等节点的地址（IP地址和端口号）
对等抽样服务执行的工作流程如下[8]：
将每个节点初始化为系统的部分视图（带有子集节点列表）
将节点视图与对等节点的视图在 Gossip 交换中合并
换句话说，每个节点维护一个小的本地成员表，其中包含系统的部分视图，并通过 Gossip 消息定期刷新该表。Gossip 协议可以利用概率分布来选择对等节点，以减少向相同节点的重复消息传输[4]。
应用程序状态可以作为键值对通过 Gossip 协议传输。当节点对同一键执行多个更改时，必须传输最新的值。Gossip 协议提供的 API 来组织应用程序状态交换如下[6]：
/gossip/on-join
/gossip/on-alive
/gossip/on-dead
/gossip/on-change
种子节点是基于静态配置的完全功能节点。系统中的每个节点都必须知道种子节点。Gossip 系统与种子节点交互，以防止逻辑分区[4]，[12]。当一个节点接收到具有对等节点的节点元数据的 Gossip 消息时，以下是高级工作流程[12]：
比较传入的Gossip消息，以识别本地节点数据集中的缺失值
比较传入的Gossip消息，以识别对等节点数据集中的缺失值
当节点已经包含传入Gossip消息中存在的值时，选择更高版本值
在本地节点数据集中添加缺失值
在响应中返回对等节点数据集中的缺失值
使用接收到的响应更新对等节点数据集
通常，在节点启动时将整个节点元数据传输通过 Gossip 协议。每个节点可以维护一个内存中的版本号，通过 Gossip 协议只发送节点元数据的增量更新[6]。
生成时钟是一个递增的表示服务器生成的数字。每当节点重新启动时，生成时钟都会增加。版本号保证应用程序状态的排序和版本控制。版本号只能递增[6]。在节点重新启动时，可以使用生成时钟和版本号来正确检测节点元数据的更改[12]。
Gossip 定时器是 Gossip 协议的一个组件，它确保每个节点最终包含有关对等节点的关键元数据，包括网络分区后的节点。每个节点都包含一个与之关联的心跳。心跳状态包含生成和版本号。应用程序状态包含表示节点状态的键值对和版本号[6]。
发起 Gossip 交换的节点发送一个 Gossip 摘要同步消息，其中包含 Gossip 摘要列表。Gossip 摘要包含端点地址、生成号和版本号。Gossip 摘要确认消息包含 Gossip 摘要列表和端点状态列表。Gossip 摘要的示例模式如下[6]：
Gossip 协议的使用案例
Gossip 协议用于多种应用，其中偏向于最终一致性。Gossip 协议的流行应用如下[8]，[5]，[4]，[7]，[12]：
数据库复制
信息传播
维护集群成员资格
故障检测
生成聚合（计算平均值、最大值、总和）
生成覆盖网络
领导者选举
Gossip 协议可以用于在分布式系统中高概率地检测节点的故障。节点故障的检测可以节省 CPU、带宽和队列空间等资源。在分布式系统中，如果一个单独的客户端无法与特定节点进行交互，仅仅凭此无法断定该节点发生了故障，因为可能发生了网络分区或客户端故障[1]。只有在多个节点（客户端）通过 Gossip 协议确认特定节点的活动时，才能确定特定节点的故障[4]，[11]。
Gossip 协议比通过 TCP 连接更加可靠，用于数据交换和命令与控制。Gossip 协议使得应用程序逻辑中的节点和子系统属性的通信抽象出来[11]。例如，节点统计信息（如平均负载和可用内存）可以通过 Gossip 消息传输，以改进本地决策过程。
子系统信息（如队列深度、配置更改等的关键元数据）甚至请求-响应等信息也可以通过Gossip协议传输。通过 Gossip 协议对节点更新消息的聚合允许以单个块而不是多个小消息的形式发送数据，从而减少通信开销[11]。
消息可以通过识别节点的活动状态在群集中进行最优路由[9]。在不涉及集中式服务的情况下进行本地节点级别的决策是 Gossip 协议可扩展的关键[4]，[11]。消息可以使用向量时钟进行版本化，节点可以忽略较旧的消息版本[9]，[2]。Gossip 协议的现实世界应用案例包括以下几种[12]，[8]，[4]，[9]，[11]：
Apache Cassandra 使用 Gossip 协议来维护集群成员资格、传输节点元数据（标记分配）、使用 Merkle 树修复未读数据和检测节点故障
Consul 利用 swim-gossip 协议变体进行组成员资格、领导者选举和 consul 代理的故障检测
CockroachDB 使用 Gossip 协议来传播节点元数据
Hyperledger Fabric 区块链使用 Gossip 协议进行组成员资格和分类账元数据传输
Riak 利用 Gossip 协议来传输一致性哈希环状态和群集节点元数据
Amazon S3 使用 Gossip 协议在系统中传播服务器状态
Amazon Dynamo 使用 Gossip 协议进行故障检测和跟踪节点成员资格
Redis 集群使用 Gossip 协议传播节点元数据
比特币使用 Gossip 协议在挖矿节点间传播随机数值
Gossip 协议的优点
Gossip 协议的优点包括以下几点[8]，[2]，[7]，[4]，[5]：
可扩展性
容错性
健壮性
最终一致性
去中心化
简单性
集成和互操作性
有界负载
可扩展性
可扩展性是系统处理不断增加的负载而无需降低性能的能力[2]。Gossip 协议的周期要求对数时间达到收敛。此外，每个节点仅与固定数量的节点进行交互，并且独立于系统中节点数量，只发送固定数量的消息。节点不需要等待确认以提高延迟[8]，[4]，[5]。
容错性
容错性是系统在发生故障（如节点崩溃、网络分区或消息丢失）时保持功能的能力。采用 Gossip 协议的分布式系统由于对不可靠网络的容忍而具有容错性。Gossip 协议提供的冗余性、并行性和随机性增强了系统的容错性[2]。
此外，节点参与 Gossip 协议的对称和去中心化特性增强了 Gossip 协议的容错性[5]。通常会将相同的消息多次传输到多个节点。换句话说，源和目标之间的消息流有许多路径。因此，通过其他节点的消息传输可以克服节点故障[8]，[4]。
健壮性
节点参与 Gossip 协议的对称特性提高了系统的健壮性[5]，[4]。节点故障不会破坏系统的质量。然而， Gossip 协议对于临时网络分区并不具备健壮性。然而，除非数据经过自验证，否则 Gossip 协议对于存在故障节点或恶意 Gossip 消息的情况并不具备健壮性[8]，[7]。
通过基于分数的声誉系统可以防止恶意节点损坏 Gossip 系统。必须实施适当的机制和策略（如加密、身份验证和授权），以确保 Gossip 系统的隐私和安全性[2]。
最终一致性
一致性是确保系统中的每个节点具有相同的状态视图的技术。不同的一致性级别（如强一致性、最终一致性、因果一致性和概率一致性）对系统的性能、可用性和正确性有不同的影响[2]。Gossip 协议通过数据的指数传播在对数时间复杂度下收敛到一致状态[8]，[5]。
去中心化
Gossip 协议通过点对点通信提供了一种极度去中心化的信息发现模型[8]，[4]，[5]。
简单性
大多数 Gossip 协议的变体都可以使用很少的代码和低复杂性来实现[8]，[5]。节点的对称性使得执行Gossip协议变得非常简单[7]。
集成和互操作性
Gossip 协议可以与数据库、缓存和队列等分布式系统组件进行集成和互操作。必须定义通用接口、数据格式和协议，以在不同的分布式系统组件上实现 Gossip 协议[2]。
有界负载
传统的分布式系统协议通常会产生高峰负载，可能会使单个分布式系统组件超负荷。Gossip 协议只会对单个分布式系统组件产生严格有界的最坏负载，以避免服务质量的中断。Gossip 协议中的对等节点选择可以调整以减少网络链接的负载。在实践中，Gossip 协议产生的负载不仅是有界的，而且与可用带宽相比也是可忽略的[7]。
Gossip 协议的缺点
Gossip 协议的缺点包括以下几点[1]，[5]，[8]，[2]，[7]：
最终一致性
不知道网络分区
相对较高的带宽消耗
增加的延迟
调试和测试困难
成员资格协议不可扩展
容易出现计算错误
最终一致性
Gossip 协议本质上是最终一致性的[1]。与组播相比，Gossip 协议相对较慢。Gossip 消息存在开销，并且 Gossip 行为取决于网络拓扑和节点异构性[2]。因此，群集对于识别新节点或节点故障可能会有一些延迟[12]。
不知道网络分区
当发生网络分区时，子分区中的节点仍会相互传播 Gossip 。因此，Gossip 协议对于网络分区没有意识，可能会严重延迟消息传播[1]，[7]。
带宽
Gossip 协议并不以效率著称，因为相同的消息可能会被多次重传给同一个节点，从而消耗不必要的带宽[5]，[8]。尽管由于有界消息大小和周期性消息交换，Gossip 协议的带宽使用是有限的，但当节点应该传播的信息量超过有界消息大小时，通过 Gossip 交换实际上有效的 fanout 可能会降低[7]。
Gossip 协议的饱和点取决于不同的参数，例如消息生成速率、消息大小、 fanout 和 Gossip 协议类型[7]，[8]。
延迟
使用 Gossip 协议会导致增加的延迟，因为节点必须等待下一个 Gossip 周期（间隔）才能传输消息[5]。消息并不会触发 Gossip 交换，而是由 Gossip 协议的间隔计时器触发。在系统中传播消息所需的时间复杂度是对数级别的[8]，[4]。
调试和测试
调试是识别并修复导致 Gossip 协议偏离预期行为的故障的过程。测试是验证 Gossip 协议是否满足性能、可靠性和安全性等功能和非功能要求的能力[2]。
Gossip 协议的固有非确定性和分布式特性使得调试和重现故障变得困难[8]，[5]，[2]。可以使用模拟、仿真、日志记录、跟踪、监视和可视化等工具和技术来测试和调试 Gossip 系统[2]。
可扩展性
大多数 Gossip 协议的变体依赖于不可扩展的成员资格协议[5]。
计算错误
Gossip 协议易于受到恶意节点的计算错误影响。节点应该实现自校正机制，因为 Gossip 协议的健壮性仅限于某些类别的故障[7]。尽管如此，Gossip 协议非常可靠，概率为1的结果是典型的[8]。
总结
在分布式系统中进行 Gossip 是一种福音，而在现实世界中进行闲言碎语则是一种诅咒。Gossip 协议被用于 Amazon Dynamo 和分布式计数器等分布式系统中。
进一步的系统设计学习资源
订阅系统设计通讯，再也不会错过新的博客文章。您还将在订阅时收到关于如何应对系统设计面试的终极指南。
参考
[1]: Prateek Gupta, Gossip Protocol in distributed systems (2022), medium.com
[2]: How do you integrate a gossip system with other distributed components and services?, Distributed Systems (LinkedIn.com)
[3]: Martin Kleppmann, Distributed Systems 4.3: Broadcast algorithms (2021), YouTube.com
[4]: Bhumika Dutta, A Gentle Introduction to Gossip Protocol (2022), analyticssteps.com
[5]: Gabriel Acuna, Parallel & Distributed Computing — Gossip Protocol (2020), YouTube.com
[6]: Architecture Gossip, Cassandra
[7]: Ken Birman, The Promise, and Limitations, of Gossip Protocols (2007), cornell.edu
[8]: Felix Lopez, Introduction to Gossip (2016), managementfromscratch.wordpress.com
[9]: Kumar Chandrakant, Fundamentals of Distributed Systems (2023), baeldung.com
[10]: Alan Demers et al., Epidemic Algorithms for Replicated Database Maintainance (1987), berkeley.edu
[11]: Todd Hoff, Using Gossip Protocols For Failure Detection, Monitoring, Messaging And Other Good Things (2011), highscalability.com
[12]: Unmesh Joshi, Gossip Dissemination (2021), martinfowler.com
