HyParView: 一个基于gossip的可靠成员协议
概要
gossip或者传染病协议作为一个强大的策略出现来实现高可用的弹性可靠广播原语。由于扩展性原因，gossip协议中的每个参与者都维护协议的部分视图。Gossip协议的可靠性依赖于一些视图的特定属性，比如度分布和聚类系数。
几个算法已经提出来维护gossip协议的部分视图。在这篇论文中，我们展示了在高度的错误下，这个算法能够长期修复视图属性。为了解决这个问题，我们提出了HyParView，一个新的成员关系协议来支持基于gossip的广播，它确保了高级别的可靠性，即便存在高的节点故障率。HyParView协议是基于新颖的方法，它使用俩个不同的部分视图，它通过不同的策略维护不同的目标。
1 介绍
Gossip或者传染病协议，作为一个强大的策略来实现可靠的弹性广播原语[9,3,7,1]，在gossip协议中，当一个节点想要广播一个信息，它随机从系统中选择t个节点（这个配置参数被叫做扇出），并且发送信息给他。一旦在第一时间接收到信息，每个节点重复这个过程[9]。gossip协议是一个有趣的方法，因为它的高弹性（这个协议有固有的冗余，它允许忽略一些及诶单或者网络故障）并且分布在整个系统中的负载。
如上所述，协议需要每个及诶单知道整个系统的成员，以选择目标及诶单来进行每一个gossip步。显然，这个方案是不可扩展的，不仅是因为大数量节点可能组成的视图，也是因为维护完整的成员最新的信息。为了客服这个问题，几个gossip协议依赖于部分视图[13,2,3]而不是完整的成员信息。不分视图是整个成员列表的小子集。当一个及诶单执行gossip步骤在部分视图中选择t个节点。目标的成员服务（也叫做对等采样服务[8]）来维护这些部分视图的让它满足良好的属性。直观地说，从部分视图中选择八卦节点应该提供与从整个成员中随机选择它们相同的弹性
不幸的是，如果节点只有系统的部分视图，它将会变得容易受到节点故障。事实上，如果大量的节点故障，每个节点的视图可能被损坏，网络连接可能会断开。同样成员关系服务可能会需要几个成员轮次来回复视图的部分目标属性，同时对所传播的可靠性产生负面的影响。
这篇论文提出了一个新的方法来实现基于gossip的协议和描述成员协议，它让这个方法变得成功。这篇论文的主要想法如下。
- 我们提出了gossip策略，它基于使用可靠的传输，比如使用TCP于gossip节点之间，使用这种方法，gossip不需要配置掩盖网络的遗漏。
- 每个节点维护小的堆成的活动视图，大小为扇出+1。注意在假设所属链接不省略消息的情况下选择扇出；注意，可以在假设所属链接不遗漏消息的情况下选择扇出；策略允许使用不可靠传输的协议更小的扇出来支持交换gossip。广播是通过泛洪被活动视图定义的凸来执行的。其中图随机生成（使用我们的成员关系服务），只要图保持不变gossip就是确定性的。
- TCP也被用于故障探测，因此所有视图的活动成员被gossip步进行测试，节点的故障在活动视图中很快被探测。
- 每个节点维护一个备份节点的被动视图，当活动视图中的一个节点出现故障时，该视图可以提升到活动视图（即 断开连接，崩溃或者 停机）。
- 成员关系协议负责维护被动视图，并且选择它的被动视图的成员需要被晋升到活动视图。事实上，协议维护了俩个部分视图。
我们吧我们的协议叫做HybridPartialView成员关系协议，或者简称HarParView。我们展示了我们的方法不止可以使用在小的扇出（因此它比其他方法消耗资源更少）也可以提供对于节点故障强大的可靠性，即便在系统中存在大型的节点崩溃。正如我们将展示的，我们的协议在4个成员轮次中就可以从高达90%的节点故障中恢复过来。这明显超过了之前的方法。高弹性的节点故障我对于面对事故非常重要，比如自然灾害（如地政）或者计算机蠕虫和病毒，它可能会让特定操作系统中的机器瘫痪（这可能出现在系统的一部分）。例如，在几天时间里，蠕虫可能会影响1000w个节点；同样的，蠕虫可以在第一阶段传播，并在预期的时候同时破坏节点。
这篇论文的其他部分如下。章节2提供了相关工作的总览。第三章给出了我们工作动机，即对使用部分视图协议中高百分比点的故障影响进行分析。HyParView在第四章中被提出，在第五章执行评估。最后第六章总结这篇论文。
2 相关工作
在本章开始我们更准确的定义部分视图的概念。然后我们介绍俩个主要的方法维护部分视图。之后我们列举部分视图必须要有的属性。最后我们给出正确的成员关系协议。
2.1 部分视图
部分视图是一组节点的定义在每个节点本地维护，它是系统中所有节点定义的子集（理想上，系统中处理数量的对数级别）。通常定义是一个元组(ip,port)，一个成员关系协议负责初始化，并且维护面对系统中的动态改变时的部分视图。例如，当一个新的节点加入系统，它的标识需要被添加到一些其他节点的部分视图中，它必须创建自己的局部视图，包括系统中已经存在的节点的标识符。如果节点故障或者离开系统，它的标识符需要从部分视图中移除越快越好。
部分视图建立节点之间的邻居关系。因此，部分视图定义环绕网络。另一方面，部分视图建立了有向图，它捕捉了执行协议中所有节点的邻居关系，在这个图中，节点被表示为顶点，其中邻居关系在局部视图中包含目标节点的弧线表示。
2.2 维护部分视图
有俩个策略用来维护部分视图，名字是
被动策略：在这个类型的方法中，局部视仅在影响覆盖的外部事件时更改（节点加入或者离开）。Scamp[6,5]是这个算法的例子。
循环策略：在这种类型的方法中，视图每$\Delta T$时间单位更新一次，作为一些周期性过程的结果，通常设计与一个或多个邻居交换信息。因此部分视图可能发生变化，即便集群成员关系是稳定的。Cyclon是这个算法的例子[17,16].
被动策略依赖于故障探测机制，当一个节点离开系统时，来触发部分节点的更新。如果故障探测机制快速和准确，被动机制可以提供比循环策略快速的故障响应。
2.3部分视图的特性
为了支持快速消息广播和对于节点故障高级别的容错，不分视图需要有一些重要的特性。我们列出了一些重要的属性。
连通性：通过部分视图定义的覆盖必须是连接的。如果不满足这个性质，孤立的节点奖不能接收到广播消息。
度分布：在无向图中，节点的度是节点边的数量。给定无向图定义的部分视图，我们区分入度和出度。节点的入度n是节点的数量，在部分视图中有n的标识符；它提供了覆盖层中可达节点的数量。节点n的出度是局部视图中节点的个数。它衡量了节点对于成员关系协议的贡献，因此衡量该节点对于维持覆盖的重要性。如果故障概率在节点空间中均匀分布，为了提升错误容忍，出度和入度我必须最终贯穿所有的节点。
覆盖层直径（Overlay Diameter） 指的是 覆盖网络（Overlay Network） 中所有节点对之间最短路径的最大值。换句话说，在该覆盖网络中，找出所有可能的节点对，计算它们之间的最短路径，然后选取其中最长的一条路径，其长度即为覆盖层直径。
平均路径长度：环绕中俩个节点的路径是一组边，它从一个节点到另一个节点。平均路径长度是覆盖层中对所有在覆盖层中的最短路径的平均值。这一个特性和覆盖层直径密切相关。强制使用较低的平均值是必要的，这个值域消息到达所有节点所需时间有关。
聚类系数衡量的是一个节点的朋友们彼此认识的程度。如果朋友之间关系密（互相连接多）聚类系数高，如果朋友之间的关系松散（很少相互链接）聚类系数低。
聚类系数：某个节点的聚类系数等于该节点的令居之间已经存在的边的数量，除以这些邻居之间理论上可能形成的最大边数。这指标表示一个及诶单的邻居之间的邻居关系密度。这个度量表示一个节点的邻居之间的邻居关系密度，它的值在0-1之间。图的聚类系数是所有节点聚类系数的平均值。当传播数据时，这个特征大大影响了冗余信息的数量，其中一个高的聚类系数值将会产生更多的冗余消息。它也对图的错误容忍特性有影响，图中出现高聚类值的区域更容易和图的其他部分隔离。
准确我们定义了精确的节点的邻居数量，没有失败的数，除以该节点邻居的总数。图的精度是所有正确节点的平均精度。准确性对任何使用底层成员协议选择gossip传播协议的整体可靠性有很大的影响。如果图的准确值很低，选择的gossip目标的失败节点的数量将会更高，必须使用更高的扇出来掩盖这个故障。
2.4 成员关系和gossip协议
Scamp[6,5]是一个被动成员协议，它维护俩个分离的视图，一个该节点PartialView选择它的gossip消息目标，和带有节点的InView可以从中接受gossip消息。一个协议的有趣的概念是PartialView没有固定大小，它的值分布在logn附近，其中n是执行协议的节点总数，并且不需要n知道所有节点。维护机制来更新PartialView是一个订阅协议，当新的程序加入系统时执行。然而，为了从隔离中恢复，节点单定期发送心跳信息到所有节点呈现在他们的PartialView中，如果节点很长时间没有接受到心跳，它假设它已经被隔离并重新离开覆盖层。
Cyclon[17]是一个循环成员关系协议，其中节点维护固定的partial view的长度。这个协议依赖于一个操作，它每$\Delta T$对所有节点进行名为shuffle的操作。基本上，在shuffle操作者，一个节点选择它在partial view中最老的节点，并且对这个节点执行交换。在交换中，节点提供它partial view的对等样本，并且对称地手机对等的部分视图样本。连接操作基于覆盖上固定长度的随机游走。这个加入过程确保了，如果没有消息丢失和节点故障，所有节点的入度将会不变。
NeME[12]，网络友好的流行病多播，是一个gossip协议它以来使用tcp来广播跨越环绕的信息。在NeEM中，TCP被用来消除网络拥塞而导致的相关消息丢失。作者展示了好于gossip的稳定性，可以利用TCP的流控机制来实现。在这篇论文中，我们终极TCP来掩盖网络遗漏和探测故障。因此我们的工作NeEM互补。
CREW[2]是一个快速分发的gossip协议，即通过推拉gossip的组合，通过大量的目的快速同事下载文件。它使用TCP连接来隐式估计可用带宽，从而优化gossip过程的扇出。CREW的重点是优化延迟，主要改进多个源的并发提取。一个关键的特性是维护使用随机游走协议发现的对等节点开放连接的缓存，以避免在需要新的对等节点时打开TCP连接的延迟。相同的优化可以在HyParView中被使用，通过预先打开被动视图的一些成员连接。然而CREW没有显式的管理这些缓存来提升环绕，即大量节点故障时的弹性。
2.5 gossip可靠性
原子广播：强一致性的广播方式， 要求所有活跃节点都收到消息，要么都不接收到消息。
我定义gossip可靠性为发送gossip广播活动节点的百分比。百分比的可靠性意味着gossip消息到达了所有活动的节点，换句话说，这条消息引起了一次原子广播。
3 动机
我们的动机是基于如下俩个观察：
- gossip协议的扇出被目标的可靠级别约束和需要的协议容错。当部分视图被使用，这些视图质量也会影响扇出来达到高可靠性。通过使用更号的视图（根据章节2的指标）和例如TCP的可靠传输，可以实现最小化扇出，以此更划算的gossip协议。
- 高故障率可能会大大影响部分视图的质量。即便成员协议有处理特性，出现严重的故障后可能会严重影响消息广播的可靠性。因此gossip将极大受益于有快速修复的成员特性，它也可以通过TCP的故障探测来达到。
在以下的段落，我们展示了描述这些因素的图。
3.1 扇出值
图1中的最后一个图描述了在健康节点故障之后的交换。在这一章节我们有50%的系统节点故障，并使用了Syclon和Scamp作为成员协议，测量对使用10000个节点的网络一下。这个消息在Cyclon有机会执行循环shuffle之前（Cyclon周期性的交换上千个节点的信息），或者在Scamp到期之前。（如我们看到的，可靠性丢失了85%的节点，许多信息被传递到一些小数量的节点）。这个长期不可靠行为在永曜之星高可靠需求和高吞吐量时是不可靠的。
4 HaParView协议
4.1 总览
HyParView协议维护了俩个不同的视图在每个节点上。一个小的活动视图为扇出的大小+1，因为链接是对称的，因此每个节点必须避免中继消息返回到发送者。一个更大被动视图，它确保即使有大量故障也能保持连通性，且必须大于log(n)。记住被动视图的开销是最小的，因为没有连接保持打开。
所有节点的活动视图创建覆盖，被用于消息广播。覆盖中的链路是对称的。这意味着节点q在及诶单p的活动视图中那么，节点p也在节点q的活动视图中。如我们之前所说，我们的架构假设我们使用TCP广播信息在环绕中。这意味着 每个节点保持打开的TCP连接到每一个其他节点的活动视图。这是可行的，因为活动视图非常小。当一个节点接受到消息时，它广播消息到它活动视图的所有节点（显然，除了发送消息的节点）。在覆盖中的gossip目标选择是确定性的。然而覆盖自身是随机被创建的，使用gossip的成员信息在本章进行描述。
一个被动策略被用来维护活动视图。节点可以添加到活动视图，当加入系统。同样的，当节点失败时从系统中删除。读者应该注意到，每个节点在每次转发消息时都会测试整个活动视图。因此，么次广播时都隐式测试整广播的覆盖，这允许非常快的故障探测。
除了活动视图，每个节点维护更大的被动视图。被动视图被用来消息分发。被动视图的目标是用来维护节点列表，它可以被用来替换活动视图的故障成员。被动视图用循环策略来维护。周期的，每个节点和一个随机节点执行shuffle操作，来更新被动视图。
我们shuffle机制一个有趣的方面是，shuffle操作中交换标识符不仅来自被动视图：一个节点也发送它拥有的标识符和一些从它活动视图中收集的标识符到他们的邻居。这增加了在被动视图中具有活动节点的概率，并且确保了故障节点最终会在所有被动视图中删除。
4.2 加入机制
算法1描述了加入操作的伪代码。当一个节点希望加入覆盖，他必须知道已经属于覆盖中的节点，我们把这种节点叫做联系节点。有几种方式来学习联系节点，例如覆盖成员可以通过一组已知服务来宣布。
为了加入覆盖，一个新的节点n建立一个TCP连接到联系节点c，并且发送到c加入请求。接收JOIN请求的节点将会首先将新节点添加到其活动视图中，即便它必须从中随机删除一个节点。在这个例子中DISCONNECT通知被发送到从活动视图中删除的节点。DISCONNECT的消息的效果将在之后章节描述。
联系节点c之后将会发送到所有活动视图中的其他节点FORWARDJOSIN请求包含新的节点定义。FORWARDJOIN请求。FORWARD请求将会在覆盖中使用随机游走传播。与连接过程相关的有俩个配置参数，名为活动随机游走长度（ARWL），它指定了FORWARDJOIN请求传播的次数。以及被动随机游走长度（PRWL）它指定了在遍历中的哪一个点将被插入被动视图。为了使用这个参数，FOPRWARDJOSIN请求携带存活时间字段，初始设置为ARWL，每跳一次减小。
当一个节点p接收到FORWARDJOIN，他执行以下连续步骤
- 如果存活时间等于0或者p的活动视图中的节点数等于1，它将会添加新的节点到活动视图中。这一步在即便随机节点需要移出活动视图中的节点也必须执行。在后者情况下，从活动视图弹出的节点将收到一个DISCONNECT通知。
- 如果存活时间等于PRWL，p将会插入新的节点到被动视图中
- 存活时间字段衰减
- 如果此时n还没有被插入到p的活动视图中，p将会转发请求到它活动视图中的随机节点（不同于接收到请求的那个）
4.3 活动视图管理
优先级低代表该节点是孤立的，孤立的节点能够优先被处理，同时避免优先级过渡占用资源
- 如果 q 接受了 NEIGHBOR 请求，p 会将 q 从其被动视图中移除，并将其添加到活动视图中。
- 如果 q 拒绝了 NEIGHBOR 请求，p 会保留 q 在被动视图中，并选择另一个节点重复上述过程。
收到DISCONNECT会从活动视图中将节点移出，然后将节点天添加到被动视图。
活动视图使用被动策略管理。当一个节点p怀疑活动视图中一个节点存在故障时（断开连接或者阻塞），它选择一个随机节点q，并超时与q建立tcp连接。如果建立连接失败，节点q被认为故障，并从p的被动视图中删除；另一个节点q'被随机选中，进行一次新的尝试。重复此过程，直到成功建立连接。
当连接成功被建立，p发送给q 带有自己标识符和优先级别NEIGHBOR请求。请求的优先级别可以有俩个值，根据p的活动视图存在的节点数量：如果p没有元素在活动视图中，优先级是高，其他情况相爱优先级低。
一个节点q接收到高优先级的NEIGHBOR请求将会永远接受，即便要删除它的活动视图（同样的，将会发送给被删除的成员DISCONNECT请求）。如果一个节点q接收到低优先级的NEIGHBOR请求，只会在活动视图槽空闲的时候接受，其他情况下将会拒绝请求。
如果节点q接受到NEIGHBOR请求，p将会从被动视图中删除q的定义并且添加到活动视图中。如果q拒绝了NEIGHHBOR请求，启动器将会选择被动视图中的另一个节点重复整个过程（即便需要从被动视图中删除q）。
4.4 被动视图管理
被动视图使用循环策略维护。周期性的，每个节点执行shuffle操作和一个随机的对等节点。Shuffle操作的目标是更新参与交换节点的被动视图。节点p初始化交换创建一个带有以下信息的交换列表：p自身的标识符，活动视图中的$k_a$节点和被动视图中的$k_p$节点，其中$k_a$和$k_p$是协议参数。然后他发送SHUFFLE请求到随机的活动视图中的邻居。SHUFFLE请求使用随机游走进行传播，并且有相关的存活时间，就像FORWARDJOIN请求一样。
一个节点q接受SHUFFLE请求将会首先减少存活时间。如果存活时间大于0，并且q中的活动视图的数量大于1，节点将会随机选择活动视图中的节点，和其他人接收到的shuffle信息不同，它只是转发请求，否则节点q接受SHUFFLE请求并且发回，使用临时的TCP连接，一个SHUFFLERERELY信息，其中包括从q的被动视图中随机选择的一些节点，这些节点等于在SHUFFLE请求中接收到的节点数。
然后俩个节点将它们在SHUFFLE/SHUFFLERRELY消息中接收到的元素集成到它的被动视图中（自然它它们排除了自身标识符和作为主被动视图或者被动视图的部分节点）。因为被动视图的长度是固定的，它可能会满；在这种情况下必须扇出一些标识符，以便释放空间来包含新的标识符。一个节点将会首先尝试删除发送给对等端的标识符。如果被动视图中没有这样的标识符，它将会随机删除标识符 。
4.5 视图更新过程
算法1也展示了基础的使用被动视图和活动视图的交换原语。从这些原语保留的重要方面是，节点可以从一个被动视图中移动到活动视图，以填充活动视图（即 响应节点故障）。只要从活动视图中删除一个正确的节点，就可以将活动视图的节点移动到被动视图。由于连接是对称的，通过从节点q的活动视图中删除节点p，q会在p的活动视图中会创建一个空槽。通过添加p到它的被动视图中，通过将p加入其被动视图，节点q增加了q与其他节点shuff的概率，最后P成为NEIGHBOR的请求目标，这可能有助于它重新填充视图。
5评估
6 结论和将来工作
gossip协议是吸引人的，因为它以非常小的维护成本工作在覆盖网络上。因此，它们似乎是支持那些需要对大部分节点的故障具有极高弹性的明显候选者。这种密集的故障可能是由于攻击导致的（例如，一种蠕虫会关闭特定品牌的机器）或者在自然灾害中（比如地震）。据我们所知，这是第一篇研究大量失败情况下对gossip可靠性影响的论文，当使用不同的方法维护不同的部分成员信息时。
我们定义了一个gossip策略，它定义了一种由泛洪构成的覆盖拓扑，通过概率（部分）成员关系协议。此外，我们还提出了一个新的混合成员协议。协议维护最小活动视图和更大的被动视图用来容错。我们展示 了我们的协议能够保持非常高的可靠性，小的扇出，在故障场景下，节点的故障率高达80%。
在未来的工作中，我们希望进行实验，以更好的定义被动视图大小和协议的回复级别的关系（即，支持多少次失败而不断开连接。）一个HyParView的实现将会在PlanetLab平台进行测试，以衡量由于使用TCP造成的包开销。
最后，我们也想通过考虑节点的异质性用自适应的扇出值来实验我们的方法，以最大化可用资源的利用率，如贷款。要做到这一点，还要保持我们对gossip目标的选择，节点需要自适应它们的度数（和入度），为了优化紧急叠加，这种方法可能是一种有趣的方法。