gossip共识
Gossip consensus | Proceedings of the 22nd International Middleware Conference
概要
基于gossip的一致性协议，最近被提出来面对在大地理分布的状态机复制。然而，目前尚不清楚共识和gossip协议在多大程度上契合。另一方面，gossip沟通已经被站名可以被扩展到更大的环境并且邮箱的处理参加者的故障和信息丢失。另一方面，gossip可能会减慢共识的速度。然而gossip固有的冗余可能是不需要的，因为共识自然解释了参与者的失败和信息丢失。这篇论文探讨了gossip作为共识沟通搭建块的适用性。我们回答三个问题：在共识中gossip会带来多少开销？我们是否可以设计一个共识友好的gossip协议？更有效的gossip协议是否仍然保持经典gossip协议的可靠熟悉。
1 介绍
在状态机复制的核心中一致性是一个基本的抽象。虽然共识和状态机复制已经在各种条件下（同步假设，故障模型，分配给流程的角色）进行了广泛的研究，大部分的研究假设进程之间可以直接通信。具体来说，网络图中的顶点代表了进程，它执行共识，边代表了俩个进程可以直接通信的可能性，是完全全连接的。在同一个管理域运行的系统中完全链接是一个合理的假设。
然而一种新的去中心化系统，特别是区块链洗头工，它与完全链接的网络图完全不一致。在去中心化系统中，没有单个试图拥有基础设施，相反，不同的管理的多个实体进行协作。在这样的环境中，期望每一个领域的每个进程都能和另一个领域的所有进程直接通信是不合理的。例如，一些在领域中的进程可能隐藏在防火墙后，而不是直接连接到域中的其他进程。
在缺乏全连接的情况下达成共识一个挑战。一些区块链共识协议依赖于gossip通信，面对部分连接网络图的挑战。在gossip中进程使用消息交换轮进行通讯。在每一轮中，一个进程可以发送消息和接受消息给他的邻居（即 在图中被连接的进程）。进程域没有连接的进程进行通讯，可能需要几轮消息交换。因此gossip算法提供了高通讯可靠性，并且一些共识算法可以处理消息丢失（即paxos），人们自然可以在gossip通讯协议之上进行交换。（见图1）。基于gossip的共识方法表明，人们不需要为链接的网络图从头开始设计共识协议。
基于gossip共识方法的核心是一个基本的问题，本文研究学术报告的主要驱动：gossip协议和基于gossip的连接能结合在一起吗？这个问题并不明显：在一方面，在部分链接的网络中，gossip提供了高度可靠的共识。此外gossip的消息冗余可能是不必要的，因为共识解释了流程失败和消息丢失。
本文从系统的角度对gossip协议进行了研究。我们考虑一个特殊的共识协议paxos，并且实验学习它在gossip沟通下的行为。我们选择paxos的正当性如下：
- paxos是在分布式系统社区中广为人知，不需要冗长的解释
- paxos不简单，它类似于很多其他的共识算法
- paxos的交互流程包括所有感兴趣的通信模式（一对一，一对多，多对以，多对多），这让我们的研究有普遍的下去
- paxos在去中心化系统中是一个可行的操作，只容忍良性失败。
我们首先考虑gossip对共识表现的影响（吞吐量和延迟）。不出所料paxos在gossip上表现不佳（吞吐量和延迟方面），与基线goosip部署相比，在基线paxos部署中进程可以直接与paxos协调器通信。使用gossip导致的延迟退化在我们的协议中高达52%，根据系统大小的不同最多可以减少74%。虽然这种比较不公平，因为paxos可以在部分链接的网络上运行，但基线paoxs假设了一个全连接的网络，但它提供了一定参考。
然后我们考虑共识友好的gossip沟通基础。这个想法是通过共识语义来减少gossip开销。我们介绍语义gossip，通过语义过滤和语义聚合对经典的gossip来进行优化。语义过滤允许gossip层丢弃不必要的消息。在决策消息中使用投票变得无关紧要。因此一旦开始传播决策消息，它会停止导致决策的投票消息传播。语义聚合允许流程将多个消息分组为具有与共识相同含义的单个消息。在paxos中，多个投票消息可以分组为单个多进程投票消息。注意gossip共识使用了paxos的知识，它不需要改变任何paxos的实现。
语义的过滤大大减少了进程之间为达成共识而交换的消息数量。当俩个技术结合使用，对比经典的gossip消息，减少的幅度可以达到58%。此外，语义gossip提高了paxos的性能。采用这俩中语义技术可以将基于gossip的paxos延迟从7%提升到24%，同时它也能够比经典的paxos实现承受更高的工作负载。为了考虑这方面的特性，我们在基于经典paxos的和语义paxos中注入故障（消息丢失）。我们发现语义gossip相对于基于gossip的paxos高达20%的注入消息丢失。
这篇论文的其他部分组织如下。章节2定义和介绍了gossip和paxos的背景信息。章节3提出和实现了语义gossip。章节4描述了使用点对点paxos，经典gossip，和语义gossip交流的评估。章节5提出了相关工作章节6是论文的结论。
2 背景
在这一章节，我们刻画我们分布式系统假设并且提供一些在gossip交流上基础的假设，以及采用的共识算法。
2.1 系统模型
我们考虑一个分布式系统，由一组固定的进程组成，它通过信息交换进行沟通。然而我们假设，没有一对进程可以直接与彼此通信。进程可以通过双向每个连接进行沟通。没有直接连接到彼此的进程需要中间进程的合作以中继信息直到达到目标。
系统是半同步的：进程和沟通通道通常是异步的，具有同步周期，在此期间，消息在有限但是位置的延迟内进行处理和传递。这是避免纯异步系统中不可能性的需求。我们适配了蹦会恢复故障模型。进程可以因为崩溃而故障，当他们没有在实现通知的情况下参与分布式算法，之后可能会回复。在崩溃之后和恢复之前，进程的行为严格遵循分布式算法（即我们不考虑拜占庭问题）。通讯渠道不可靠：消息可能会被丢弃，重新排序，或任意延迟，但是我们假设它们不会被破坏。
进程分布式的跨越在几个世界地理区域的数据中心。一个区域内的进程通过本地局域网连接，具有低延迟；不同区域的进程通过广域网进行连接，这具有更高和更多变的延迟。我们假设共识协议客户端从延迟的角度知道最接近自己的区域，并于该进程进行交互。
2.2 goosip沟通
gossip传播方法起源于流行病策略用来广播分布式系统中的信息。最初的提议是在复制数据库中传播的最新情况，流行病算法已被证明是实现多播和广播原语的有效弹性的方法。流行病工作包括定期交换信息，其中每个进程随机选择与其他的进程进行交互。
一般的八卦传播策略有三种。在推送策略中，每个有更新（即新消息）要传播的进程将它们发送到选定的对等节点。在拉取策略中，进程向所选的对等节点请求更新，如果有更新，对等节点将更新发送给请求进程。这俩个策略可以结合为push-pull策略，在议论中进程可以发送更新到对等节点，以及接受来自他们的更新。push，pull和push-lpull策略表现不同，交换的消息的数量，以及以高概率联系进程的给定部分的轮数。最好的策略依赖于应用的行为，大小和更新的频率，以及控制传播的方法。在这个工作中我们适配了push方法，但是我们的共线可以扩展到其他方法。
一个算法使用gossip层进行广播原语，它向所有进程发送消息。这是一个非阻塞原语，传递原语返回进程广播的消息。这是一个阻塞原语，返回本地的消息和从其他进程接受的消息。不能保证飞故障进程广播的消息是由非故障进程所传递。由于进程故障一个消息可能永远无法达到目标。此外，随机选择的对等节点，一放松信息可能不能提供完整的连通性。然而，正确的选择参数提供了非常高的可用性，特别是采用推送策略时。
2.3 paxos
paxos是一个分布式的共识算法用来实现状态机复制。简单的说，paxos允许一组进程其中的一些可以失败，在一个完全有序的值序列上达成一致。这是通过运行多个独自的共识实例来实现的，由一个正整数表示其中每个序列决定一个值。在随后协商一致的情况下，算法的输出由确定的值组成，遵循实例标识符建立总序，没有间隔。
paxos区分了进程在执行过程中扮演的角色：提出者，接受者和学习者。我们假设每个paxos进程扮演所有的角色。因此一个paxos提议值，确保在每个共识实例中都接受单个值，并且学习到裁决的值。paxos已经被用很多种方法优化了。在这篇论文中我们使用经典的算法版本。
每个共识实例都已轮运行，用正整数标识。每一轮都是由一个进程，即协调器安排的。一个协调器可以在多个共识实例中启用同一轮。一轮由俩个阶段 阶段1和阶段2。在每个阶段中，协调器发送小希，可以是阶段1a或者阶段2a小希到所有的进程（一对多进程模式）并且等待阶段1b或者阶段2b从他们的大多数中中继消息。（多对一的沟通模式）。消息被标记为所属实例的标识符。在该共识实例中，一个进程回复给某一轮次的协调者，前提是该进程没有回复过来自更高轮次的消息。在阶段1中，一轮的协调器尝试找出一个值是否可能在编号较低的轮中被选中。在阶段2中，协调器告诉进程接受值，要么从阶段1的消息中学习，要么从客户端提出的任何值中学习。
当大多数进程在议论的第二阶段接受一个值时，共识实例的值被决定了。paxos确保在该共识实例的更高轮号中不能选择其他值，因为只少有一个进程将报告阶段1中的可接受值。当协调器学习到了来自阶段2的信息，当某个值被确定后，它会使用Decision消息通知所有进程（一对多的沟通方式）。如果阶段2b消息被所有非故障进程接受，而不仅仅是被协调器接受，那么这个通信步骤就变得多余了。
paxos在并发协调器的存在下是安全的，但是为了取得进场，希望一次有一个进程充当协调者。一旦被选为协调者，一个进程就会在多个达成共识的实力中开始一轮在一组有限的实例中，流程可能已经接受了值，这迫使在阶段2中重新提出它。但是大多数情况下，在前几轮中没有进程报告接收值；在这个例子中，协调器可以在阶段2中自由提出任何值。因此，在常规（无故障）操作中，值的决定需要执行第一轮的第2阶段。
3 Semantic gossip
在这一章节我们激发了对gossip协议的需求以达成一致，描述gossip协议的设计，描述使用公式语义设计gossip协议的好处，并且详细说明他的实现。
3.1 动机
在goosip交流上实现共识是简单的。基本上，原来的沟通层，假设完全连接的凸和提供（一对一）发送和接受原语，这被gossip通信层锁取代，他提供了（多对多）广播，以及交付原语（见图2）。
在paxos中，阶段1a和阶段2a小希，被协调者发送到所有进程（一对多沟通模式）自然受益于gossip沟通。而不是将阶段1a和阶段2a小希发送到协调器直接连接的所有进程，它可以通过gossip来广播信息。最终，以相当高的概率，消息被传递给所有paxos参与者，它们的传播停止。注意，paxos允许消息丢失，因此概率传递就够了。
如果不出现故障的情况下，为了避免提案冲突，可以选出单个协调者进行paxos的prepare阶段和accept阶段。因此如果这个协调者不崩溃的化，那么提案都会通过。
1.Prepare阶段
- 发起提议：首先，想要提出新值的节点（称为Proposer）选择一个新的提案编号N，并向网络中的大多数Acceptor发送Prepare请求，包含这个编号N。这里的提案编号必须是全局唯一且递增的，以确保不同时间点的提案可以被区分。
- 承诺响应：接收到Prepare请求的Acceptor会做出回应，如果该提案编号N大于它们已经响应过的任何Prepare请求的编号，则Acceptor承诺不会接受任何编号小于N的提案，并返回自己已经接受的编号最大的提案（如果有）。否则，Acceptor可以忽略此请求。
2. Accept阶段
- 发送提案：如果Proposer从大多数的Acceptor那里收到了对于其Prepare请求的响应，那么它可以发送一个Accept请求给这些Acceptor，这次请求包含了提案编号N以及想要确定的值V。这里需要注意的是，如果Proposer在Prepare阶段收到了任何关于已接受提案的信息，那么它必须使用这些提案中编号最高的那个提案的值作为自己的值V；如果没有收到这样的信息，它可以自由选择值V。
- 确认提案：Acceptor收到Accept请求后，如果它没有对更大编号的Prepare请求做出过承诺，则可以接受该提案，并持久化保存提案的编号和值。然后，Acceptor将向Proposer发送一个接受成功的消息。一旦某个值被多数Acceptor接受，它就被认为是选定的值。
gossip不适合传递1b消息，从所有的进程到协调者（多对一交流模式），因为只有协调者关心消息，但是会被所有参与者接受。幸运的是，在正常、无故障的操作中，阶段1b的消息很少被发送；因此通过gossip传播它们的开销不应该对整体性能产生影响。事实上，如果流程从大多数接收到相同的阶段2b的消息，则它们不需要等待来自协调器的Decision消息。作为结果阶段2b消息的传播通过2b可能会实际上加速决策。
Paxos与更广泛的容错共识协议和 gossip 通信之间的不匹配源于这样一个事实：Paxos被设计成能够容忍进程崩溃和消息丢失，而 gossip 协议致力于提供概率性的可靠通信。共识和gossip都是通过冗余来保证的。结果是不必要的大量消息交换，这会降低性能。当使用gossip协议是，冗余程度会增加，因为进程可能会接收到相同的消息。
然而，使用gossip作为底层通信对paxos是有益的，因为gossip不需要在每对进程之间进行直接通信。次特性自然扩展到进程仅连接进程子集的环境，并平衡进程之间的通信负载。
3.2 设计
在这一章节中，我们讨论简单的技术来解决容错共识协议的不匹配，使用paxos作为参考，以及底层的gossip通信根基。目标是在gossip层减少消息荣誉。利用共识协议提供的关于消息语义的知识。挑战是减少消息冗余并且减少明显的延迟（无需修改原始的gossip协议）以及为gossip协议提供的最初的可靠性保证。
语义过滤 第一种技术为共识协议提供了是否将消息发送给对等体的能力。这意味着干扰gossip的操作，默认情况下gossip将会转发消息给所有对等节点。共识协议可以限制信息传播，不再对对等有消息，因此该对等节点连接到所有进程。主要目标是节省网络和处理资源，这些资源将用于转发对等节点可能忽略掉的消息。
语义过滤是通过一组规则实现的，根据公式的语义已经变得过时或者冗余。举个例子，来自给定轮的消息通常会让之前（较小）的消息变得过时。或者对于某些轮的步骤，来自大多数进程的确认会使进一步的确认变得多余。当消息准备好发送给对等体时，将评估语义过滤规则。如果消息被过滤掉，那么它被认为是过时的或者多余的，gossip层丢弃它，否则它像往常一样发送。
语义过滤的评估可以看做是对等体的共识协议的轻量级运行。事实上，为了识别可以被过滤掉的消息，有必要存储一些关于先前发送到该对等体的消息的信息。规则越全面，每个对等存储的信息就越多，评估的成本也就越高。因此一组语义的过滤规则需要平衡评估他们的成本和有效过滤可以提供的好处之间取得平衡。
在paxos的例子中，所提出的过滤语义影响decision和阶段2b的消息传播。当协调者接收到大部分在某轮中实例的回复时，一个Decision消息被通过协调者广播。因此，来自给定实例的Decision消息会使来自同一实例的任何阶段2b消息失效。（常规）进程也可以通过大多数进程接受相同2b阶段消息来学习公式实例中确定的值。从这一点开始，来自同一实例的任何进一步的Phase 2b消息都是多余的。在这两种情况下，当阶段消息引用一个实例时，当期望对等体已经从先前发送给它的消息中知道决策时，它们不会转发给对等体。
语义聚合 第二个技术为共识协议提供替换许多类似或相关消息的可能性，这个消息可能会被发送给对等节点，并且包含原始消息所携带的信息。这个技术探索了gossip层由多个待处理消息要发送给对等节点，因此，根据共识语义，其中一些很可能是聚集的。这是一个机会机制，来减少进程通过goossip交换的消息数量，特别是当它们在中等到高负载下运行时。
- 找出那些容易聚类的
- 定义从原始消息中构建出聚合消息。
当发现易于聚合的消息时，列表中的第一个消息被替换为聚合消息，根据各自的构建规则，而其余的将从列表里删除。另一方面，聚合消息可以替换并过滤掉它的原始消息。不倾向于聚合的消息，或者公式协议认为聚合不有利的消息将不受此技术影响。它们被保持在带处理消息列表中，并且向平时一样转发给对等体。
语义聚合规则可以是可逆的或者不可逆的。当一个进程接收到使用可逆聚合规则的消息时，它将重建原始消息，并将其视为常规消息。也就是说，第一次接收到的消息被传递给共识协议，并转发给其他对等节点-特别是这个过程中，它们可以在语义上再次聚合。当聚合消息是由不可逆规则构建时，它被聚合进程视为新的广播。在这个例子中，共识协议必须能够处理语义聚合消息。
请注意，尽管由相似之处，语义聚合和批处理不相同。当在真实网络实现时，批处理本质上是将消息作为原始字节数组进行连接，以优化网络使用。在应用级别，某些消息类型将被批处理，直到批处理大小达到阈值或超时过期。作为结果辟出里在系统处于低负载时，会对性能产生负面影响，因为发送的消息将会被延迟。而这不会发行在语义聚合上，尽管语义聚合在低负载下是无效的，但它不会延迟任何消息的发送 。此外，这个技术比批处理更灵活，因为消息不仅可以连接，也可以按照语义聚合规定的方式进行转换合并。因此，虽然一批消息的大小与该批消息中的消息数量成正比，但列入，聚合的投票消息具有相同的大小，而不管它所替换的单个投票消息的数量如何。
对于语义过滤，最好的候选者是阶段2b的消息。当多个相同的阶段2b消息等待发送到某个流程时，可以很容易地将它们替换为单个消息。为此采用单一的语义聚合规则。它考虑了引用同一事例和议论公式的2b阶段消息的聚合；所以它们的区别在于发送者。聚合消息由任何原始的Phase 2b消息加上一个用于存储多个发送者的字段组成。作为重建原始阶段2b是简单的，聚合规则是可逆的，并且不需要更改Paxos协议。
3.3 实现
我们实现基于gossip的通信层来交流程序。在系统步骤，每个过程打开一个链接以到随机选择的k个进程，其中k是一个系统参数。连接是双向的，所以进程的对等体集合包括它打开连接的k个对等体。以及它从接受请求的对等节点。事实上，每个进程与之对等节点交互的数量是2k
经典gossip 图2展示了gossip层的架构。一个进程通过俩个队列和公式协议交互。广播队列由本地消息提供，传递队列想公式协议提供信息。添加到广播队列的消息在本地传递并发送给所有对等体：它被添加到交付队列和所有活动发送队列中。添加到接收队列的消息被发送并转发给除了消息来源的对等节点之外的对等节点：它被添加到传递队列和除消息源之外的所有发送队列中。消息转发模块从goosip主线程中选择发送到的对等体。
消息使用push传播策略进行广播。这意味着相同的信息可以被一个进程多次接受，从不同的对等节点。我们使用一种基于最近看到的消息缓存的简单方法来控制消息泛滥，由每个进程维护。在消息传递给共识协议并发送给进程的对等节点之前，消息被注册到最近的缓存中。如果相同的信息在短周期时间内被接受，那么信息还存在最近的缓存中即，它也不下发给对等体。这是复制检查模块的作用如图2：在一定程度上组织了一个信息被转发超过1次。但是不是真正的保证交付并转发一次的行为，但是合理的减少缓存大小可以减少消息重复的可能性。值得注意的是，最近看到的缓存存储消息唯一标识符，可以通过共识协议来定义，防止哈希冲突，而不是完整的消息，因此它的大小是恒定的。采用布隆过滤器也能获得相同的功能。
语义扩展 gossip层提供了俩个方式来控制行为，技术在3.2章中被提出：语义过滤和语义聚合。共识协议可以通过实现八卦层提供的接口方法来采用一种或两种技术。语义过滤通过共识协议实现一个验证风阀来提供，它接收消息和 目标对等节点，并返回boolean值。
Bool validate(Message, Peer)当它准备好发送一个消息到目标对等时，验证方法通过发送线程进行执行。如果方法返回false那么消息被移除，因为决定是过滤消息。否则消息被发送到对等节点，验证方法的实现需要快速非阻塞，因为它可能被多个发送进程并发调用。实现应该保留关于每个对等节点状态的信息，本质上是先处理过切未过滤掉的相关消息的摘要，因此发送给对等体。应该考虑存储此类信息的成本与通过过滤将被发送给对等体的消息而节省资源的好处。
语义聚合是通过实现一对方法来实现的，聚合和反聚合。
Message[] aggregate(Message[], Peer)
Message[] disaggregate(Message)聚合方法接收消息数组和目标对等体，并返回消息数组。当有多个待发送的消息要发送到各自的对等端时，发送实例进行调用。消息通过聚合方法返回，包括原始消息和聚合消息，按返回的顺序发送给对等节点。disaggregate方法接收举个消息并且返回重构数组（对于可逆的语义聚合消息），或者以其他的方式接收到相同消息。当从对等端接收到标记为聚合的消息时，进程的主八卦例程调用它。该方法返回的消息按照返回的顺序作为常规消息处理：它们将根据最近看到的缓存进行检查，如果没有复制，则交付并转发给对等节点。
6 结论
这篇论论文介绍了在基于goosip通讯的部分沟通的网络。我们介绍了语义goosip，一个基于goosip沟通的子集，它考虑了共识语义来优化性能。语义gossip依赖于俩个技术，语义过滤和语义聚合。通过语义过滤，gossip协议可以停止传播共识协议角度来看变得冗余的信息。俩中技术减少了由八卦传播的消息数量，而不会损坏gossip传播的弹性。我们已经演示了Semantic的有用性，gossip使用Paxos，一个著名的共识协议。我们打算在未来考虑其他形式的共识，特别是可以容忍拜占庭失败的共识协议。