基于gossip的节点采样技术介绍(gossip-based peer sampling)

1、基于gossip机制的节点采样技术概述（gossip-based peer sampling）一、这是什么技术，为什么需要这个技术Gossip机制，即流言机制，作为一种简单可靠的拓扑管理与消息分发机制，在大规模的分布式系统中得到了广泛的应用，其主要应用包括信息分发，数据收集，拓扑管理等方面。其产生原因主要由于在大规模的分布式系统中，底层物理链路存在数据丢包与链路断开等现象，节点规模的可扩展性与消息分发的可靠性难以得到有效保证。基于gossip机制的覆盖网络协议模仿流言传播的特性，系统中的每个节点定期的从邻居表中选择一个节点子集，然后与这个子集中的节点进行拓扑信息（邻居表信息）的交换，来维持一种

2、动态的覆盖拓扑结构。如何进行子集的选择对于基于gossip机制的消息分发是至关重要的。理想的情况下希望从分布式系统的所有节点中均匀随机的选择邻居节点。基于这个假设而衍生出的gossip协议已经得到了很多良好的特性：如可扩展、可靠、有效。在实际应用中，假设一个节点可以知道系统中的其他所有节点是不现实的。因为当前的大规模分布式系统规模可以达到10万或以上级别，同时节点可能频繁加入或离开系统（称之为churn现象），前者需要巨大的存储开销，后者需要节点维持大量的对邻居节点的同步信息开销，这导致了节点以及整个系统的性能严重下降。所以采取一种分布式的拓扑管理策略来替代全局的拓扑管理策略进行gossip机

3、制的协议部署显得至关重要。节点采样服务，是一种独立于应用的服务，就是在某个时刻系统中任意一个节点通过这个服务可以获取一个系统中的随机选择节点。节点采样服务可以应用于消息分发，数据收集，负载均衡以及网络管理。采样服务提供了任何节点与其他节点进行通信连接的可能性。节点采样服务的基本原理本身基于gossip机制的特征，每个节点都维持一个本地的有限数目的邻居表，邻居表中包含若干个系统中的其他节点信息（称之为节点描述符），每隔一段时间节点使用gossip机制与某个或某几个邻居进行各自邻居表信息的交换来刷新自己的邻居表。（但是很明显存在若干问题有待解决：1. 单个节点从本地邻居表中选择的节点的随机性，即本

4、地的有限数目邻居表如何映射系统中的所有节点来保证节点选择的随机性？2. 当系统中存在节点失效、消息丢包以及网络扰动时如何保证此时节点的选择依然保持良好的随机性？3. 由于系统中的节点分布不同，如何避免某个节点被采样的次数过多，即避免出现网络热点，保证负载均衡。）事实已经证明：采用push-pull模式要优于纯push或是纯pull模式。同时事实已证明，在进行成员策略管理时要兼顾负载均衡与抗网络扰动与节点失效。（这引出了本文认为很重要的可能的一个研究点：基于gossip的节点采样服务存在负载均衡与抗网络扰动与节点失效这两个需求，如何通过环境的变化来动态调整若干关键参数来同时部分满足这两个需求？即

5、某个时刻根据网络环境偏向于满足某个需求）二、基于gossip机制的节点采样服务的基本实现框架基于gossip的节点采样服务就是为某个节点提供一个获取系统中随机节点的方法。其主要的方法只有两个，如下：1. init()：init方法用于对刚加入覆盖网络中的节点进行初始化的一系列操作，这个操作是应用相关的（比如针对消息分发，数据收集等等）。2. getPeer()：getPeer方法返回一个系统中随机选择的节点。理想情况下这个采样是独立的无偏采样，被采样节点的特性是与实验有关的（被采样节点的随机性在时间上和空间上可能存在关联）。重点就在研究getPeer方法的不同实现版本，找出每种版本最适合于什么

6、应用，然后针对总体环境在优化均衡考虑或直接针对某个场景做优化。三、协议的总体描述考虑网络中一系列连通的节点，每个节点都有一个地址用于消息的发送，每个节点都有一个本地邻居表用来代表节点对全局成员关系的部分感知。理想情况下本地邻居表包含网络中所有其他节点，但实际中本地邻居表不可能包含所有的节点。如果本地邻居表包含所有其他节点信息，称之为节点持有网络的全局视图；如果本地邻居表仅仅包含所有节点的一个子集，则称之为节点持有网络的局部视图。局部视图是c（c为常数）个节点描述符的列表。每个节点都持有相同大小的局部视图。一个节点描述符表示一个网络地址（例如一个IP地址）和一个时间戳。时间戳用于表示这个节点描述

7、符的存活时间，时间戳的值越大则表明这个描述符存在于节点的局部视图中的时间越长。可以认为节点的局部视图是一个数据结构，在这之上定义了一组操作集合。这意味着除非某个特殊的操作施加于局部视图，否则局部视图中的元素顺序不会显式变化。同时规定局部视图中不允许存在相同网络地址的两个描述符。节点定期持续进行gossip的交换过程来保证局部视图中的描述符是系统全局拓扑信息的一个随机集合，使得局部视图可以反映系统的动态变化。下面给出具体实现：method view.select(c, H, S, buffer(p)view.append(buffer(p)view.removeDuplicats()view.r

8、emoveOldItems(min(H, view.size-c)view.removeHead(min(S, view.size-c)view.removeAtRandom(view.size-c)(a) method view.select(c, H, S, buffer(p)do foreverreceive buffer(p) from pP view.selectPeer()if pull then/ 0 is initial agebuffer (MyAddress, 0)/ shuffle the viewview.permute()move oldest H items to

9、end of viewbuffer.append(view.head(c/2 - 1)send buffer to pview.select(c, H, S, buffer(p)view.increaseAge()(b) passive threaddo foreverwait(T time units)P view.selectPeer()if push then/ 0 is initial agebuffer (MyAddress, 0)/ shuffle the viewview.permute()move oldest H items to end of viewbuffer.appe

10、nd(view.head(c/2 - 1)send buffer to pelse / empty view to trigger responsesend (null) to pif pull thenreceive buffer(p) from pview.select(c, H, S, buffer(p)view.increaseAge()(c) active thread协议包含两个线程：主动线程用于初始化与其他节点的通信；被动线程用于接受其他节点的请求并响应。（对于view.select(c, H, S, buffer(p)函数，其每一句代码都很重要，实质就是对view这个数据结构进

11、行一系列的操作达到想要的效果）我们将系统看作一个非同步的系统（即节点发起的请求-应答过程无需阻塞等待），将时间看作一系列离散的时间单元，在每个时间单元内节点只能执行一次局部视图的拓扑信息交换。关键的参数为c，H，S。其中c表示节点的局部视图大小，为常量；H表示需要从view中删除的age值偏大的节点描述符个数（下文解释）；S表示需要从view的头部删除的节点描述符个数（其中H，S小于c/2，下文解释）。鉴于被动线程的内容与主动线程类似，在此仅仅解释主动线程的内容。过程描述如下：1）由selectPeer方法返回一个目标节点进行gossip信息交换。selectPeer的具体实现会对最终结果产生

12、影响，下文将详细阐述。2）发送缓冲区buffer：首先将当前运行主动线程的节点描述符置入缓冲区内。然后在view上执行乱序排列，以此保证从view中选出的c/2-1个元素是随机的，但是选出的c/2-1个元素不包括age值最大的H个元素（利用时间戳起到自动剔除可能已失效的节点）。但若选出的元素不足(c/2-1)个，也可以从age值最大的H个元素中选出若干来补足。3）select(c, H, S, buffer)方法：当收到应答后将参数buffer传递给函数view.select(c, H, S, buffer)。这个函数根据4个参数通过一系列操作得到节点的新view（算法的核心关键所在）。首先将

13、buffer的内容附在view的后面，然后删除重复的节点描述符，这之后view的大小至少是其原大小。然后执行三个删除操作将view的大小裁剪到其原始大小。4）removeOldItems(min(H, view.size-c)：首先删除age值最大的H个元素。H越大，删除的age值偏大的元素越多，这样做的目的是因为age值偏大的元素可能已经是失效节点（根据大规模P2P系统中节点存活时间服从Pareto分布的原则），将其删除就直接避免了与失效节点保持一个无效的连接（H表示Healing）。4）removeHead(min(S, view.size-c)：然后再从view的头部删除S个元素。S越大

14、，删除的view中原有的元素越多。这样做将使得最终节点收到的节点描述符信息有更高的概率留在view中，因为每次buffer的内容是附在view的原有内容之后，从头部删除S个元素，删除越多则可以留更多空间来装载接收的buffer内容，使得buffer中的内容有更高的概率留在view中。实质上参数S控制了节点局部视图中拓扑信息交换的概率，S越高，交换概率越高（S表示Swapped）。S很低会导致进行gossip交换的双方以较高的概率保持原有view的内容而非进行交换。这会导致网络中只存唯一存在的节点描述符被删除（降低了鲁棒性）；如果S很高，进行gossip交换的双方会以较高的概率进行内容交换，可以

15、降低网络中唯一存在的节点描述符被删除的可能性。5）removeAtRandom(view.size-c)：最终view的大小被随机删除若干元素裁剪到原大小c。具体设计准则组合：主要包含三种准则，目标gossip节点选择，局部视图的推送方式，局部视图的元素选择方式。目标gossip节点选择：有两种方式，随机或选择age值最大的节点。rand从view中随机选择一个目标gossip节点tail从view中选择一个age值最大的节点局部视图的推送方式：有三种，push，pushpull，pull。push推方式，即节点主动发起连接pushpull推拉结合方式，节点主动发起连接同时被动接受连接请求pu

16、ll拉方式，即节点别动接受连接请求（效率太低被抛弃，除非接收到一个请求，节点不能主动向网络中注入自身的节点描述符信息）局部视图的元素选择方式：盲选（blind），恢复式（healer），交换式（swapper）。blindH=0, S=0任何时候采取随机选择方式healerH=c/2保持最新鲜的节点描述符在view中swapperH=0, S=c/2Gossip双方以更高概率交换拓扑信息注：H的范围是0, c/2，S的范围是0, c/2-H，H+S<c/2。四、具体实现init方法与getPeer方法。getPeer方法是从节点当前持有的局部视图中返回一个节点描述符。如果要增加返回的节点

17、描述符的随机性，采样服务必须做到在一定的时间间隔内不对同一个节点采样两次：这样做明显引入了偏好性而破坏了采样服务的质量。所以服务将会维持一个队列，用于存储没有被采样到的节点。getPeer方法将每次返回队列中的第一个元素并将这个元素删除。当服务接到一个局部视图更新的通知时，不在当前队列中的所有元素将被删除，而新加入到局部视图中的元素将被添加到队列中来。如果队列为空，那服务将返回当前view的随机采样。实验证明，很多参数组合不能获取到较好的显示结果，但是也没有一种方案可以在各种应用中取得都比较理想的结果。需要考虑应用差异性采取均衡的参数设置策略。五、节点采样全局随机性分析节点可以很容易的从本地局

18、部视图中进行随机的节点采样服务，但是单个节点的局部随机采样与独立采样特性的统计特征可能隐藏了网络作为一个整体呈现出的某些结构属性特征。为了便于进行全局的随机性分析，将网络转化为一个有向图。图的定义如下：如果节点a的view中存在节点b的描述符，则认为从a到b直接可达，在图中存在有向边(a, b)从a指向b。问题是这个覆盖拓扑与一个随机图有多相似？使得这个覆盖拓扑中每个view中的节点描述符集合代表整个节点集合的均匀独立随机采样。在图属性分析中最重要的特性就是度分布。节点i的度定义为：如果某个节点将i的节点描述符存储于各自的局部视图中，则所有这些节点的个数之和为节点i的度。每个节点的出度是个常数

19、c，等于其局部视图大小。度分布决定了节点通信中是否存在通信热点与瓶颈，即负载均衡由度分布决定。同时度分布与节点失效与可靠性有直接的关系。除开度分布还有两个参数集群系数（Clustering Coefficient）与平均路径长度（Average Path Length）。注：但是入度则并非一个常数，存在一定的时间关联性（节点入度与时间有关）与空间关联性（节点入度与节点初始的拓扑有关），能否通过DTMC建立节点入度的概率转移矩阵？能否给出时间关联性与空间关联性的具体定义？并通过某个算法尽量降低这两个关联性。第一个问题：对于一个特定的协议实现，通过一系列持续的协议执行，通信图是否存在稳定的属性？换

20、句话说通信图是否存在收敛行为（随着协议的执行，图会演化到某个属性收敛的状态）。我们希望覆盖网络可以收敛于某个特定状态而与网络的初始拓扑无关。这种属性称之为自组织性。我们希望在各种场景下运行的协议实例都可以产生一致的、可预期的行为。第二个问题：如果存在收敛，什么样的通信图使得协议实例可以收敛？第三个问题：本地的动态属性与全局度分布的关系？即度分布与其全局属性如度的最大值，方差，均值等不变时单个节点的度却在变化，这种现象是否可能？如果是这样就导出了一个很重要的现象：即通信图中如果存在瓶颈，那么瓶颈不会始终都存在于一个节点上，换句话说瓶颈会发生转移，这样就达到了负载均衡，增强了网络的鲁棒性。a）度分

21、布：给出了三种初始的网络拓扑：初步增加的（初始节点为一个，每个时间间隔加入500个节点，执行20次加入）；晶格网（规则网）；随机图。一个首要的基本条件是协议的运行不能导致网络分区现象的产生。push模式会导致网络分区，而pushpull模式不会导致这种现象发生。根据实验，在度分布上pushpull模式明显优于push模式，pushpull可以很好的均衡节点入度分布，起到负载均衡的作用。缺乏自适应性与鲁棒性使得纯push模式不可用。swapper模式可以取得较好的度分布（度分布的方差较小）；healer模式次之，blind模式最差。1）静态属性：考虑度与参数H，S的关系。H确定，S增大可以减少度

22、分布的不均匀性；而S确定，H增大同样可以减少度分布的不均匀性。2）动态属性：考虑节点入度的变化速度，变化的快不快。入度变化慢意味着入度高的节点在较长时间内处于热点状态，不利于负载均衡。首先，根据实验节点入度并非一成不变。对于一段连续时间间隔中的某个给定节点，考察这个节点度的自相关性（即在不同时刻节点入度的关联性），假设节点入度为d1，d2，dk。则在时间间隔k内序列d1，d2，dk的自相关性定义为rk。，自相关性高说明随机性差，自相关性为0说明随机性好。实验表明，healer模式的自相关性降低最快。也就是说，healer模式有助于负载均衡（节点度变化趋向随机，变化较快，不会出现某个节点长期处于

23、热点状态）。b）平均路径长度：节点a与b的最短路径定义为从a到b需要经过的最少的边，而图的最短路径定义为所有节点之间最短路径的平均值。研究最短路径的动机在于进行消息分发的应用时，最短路径反映了一个节点可达的时间与开销的下限。实验表明所有的H与S取值都可以获取较低的平均路径长度，但较大的S值可以获取接近随机图的效果。c）集群系数：集群系数反映节点a的邻居之间是否也是邻居的可能性。分析集群系数的动机在于消息分发的应用与自修复时，高集群系数可能破坏消息分发（增加了冗余消息）与自修复（增加了分区的概率）的效果。H值越大，则集群系数越高，这是因为H值偏大表示节点都仅仅保留最新鲜的节点描述符使得各自的vi

24、ew重合部分较多。S值越大则可以降低集群系数，这是因为S值偏大可以控制节点view彼此之间拓扑信息以高概率交换而不是保持一致。六、容错分析主要是引入节点失效的剧变场景与网络扰动场景来评估协议的鲁棒性。a）节点失效剧变场景：如何建立收敛后的拓扑的自修复能力与节点失效个数之间的函数关系？在静态场景中对随机网络图实施突然的节点删除，根据实验，最终直到删除67%的随机节点网络才出现分区。在动态场景中我们从收敛的随机拓扑中删除50%的节点来观察其行为，发现H值偏大可以导致很快的拓扑修复。b）网络扰动场景：关注扰动率与重启动方法（bootstrapping）。扰动率分为正常扰动率，一般为1%-2%；和剧烈

25、扰动率，一般为30%。假设存在两种重启动方法，中心化和随机。H值增大可以降低扰动时view中的无效节点，加速无效节点的删除。healer模式可以容忍剧烈的扰动。七、结论与讨论1） 关于随机性：swapper模式的随机性最好，可以获得比随机图还小的度的方差（就是节点的入度变化很小），增加H值会增大集群系数。在所有模式下平均路径长度都接近随机图。随机性与应用程序的需求本质相关，比如将信息洪泛到网络中每个节点只与网络半径有关，而与度分布和集群系数无关。故如果需要计算本地的一些对全局的统计估值，如网络容量，或全局可用资源等属性不需要全局随机性（这个观点好像不对，应该和全局随机性有关，全局的随机性利于更

26、快的aggregation）。2） 关于负载均衡：负载均衡与度分布有关，如果一个节点的节点描述符被很多其他节点都持有在view中，则这个节点具有更高概率作为目标节点与其他节点发生gossip通信，也具有更高概率被采样到提供给上层应用使用，而导致这个节点产生更多的流量，引发负载不均衡。达到负载均衡最好的模式是swapper模式。如果H值固定，增大S可以减少节点入度的方差；但如果S值固定，增加H同样可以减少节点入度的方差。3） 关于容错：H值越大越好，H值越大有助于快速的删除失效链路，实现快速的修复。注：与杨朱二人讨论中，二人提到：1）当a向b发送缓存的节点描述符中，除了a自身的age被初始化为0

27、，其他节点描述符的age是否也初始化为0？个人观点，如果其他节点描述符的age不初始化为0，则在执行函数removeOldestItems(min(H, view.size-c)时，若buffer中的元素age都偏大，则会直接删除很多元素，这样难以实现swapper模式。（节点描述符只有通过自己主动向网络中注入，即除了节点会将自己的age出师化为0发送外，其他选入buffer中的描述符age维持原值不变）2）针对函数view.removeDuplicates()，如果两个address相同的元素，到底是删除age值小的还是age值大的（如果删除age值大的，就倾向于保留新鲜节点，如果删除age

28、值小的，就倾向于维持原有view不变化）。（保留较新的，剔除较老的）附：基于RW的随机采样技术（on unbiased peer sampling for unstructured peer-to-peer networks）本文阐述真实的p2p系统的动态性与异构性如何引入了节点采样时发生的偏见性。并提出Metropolized Random Walk with Backtracking（MRWB）作为一个重要的技术来收集无偏采样节点。背景：采样是利用轻量级的数据收集方法来了解系统的一些属性。过去的采样倾向引入偏见，有两个原因：1.节点的动态特性可能引起偏向于那些生命周期短的节点；2.覆盖拓扑

29、的异构性导致偏向于连接度高的节点。本文的贡献：1.对p2p系统使用了详细的检查方法检查采样在时空维度上的质量。2.深度探索MRWB采样方法的可用性。采样偏向性产生的第一个原因来自系统的动态性，新peer到达，存在的peer在任意时间可以离开，文章表明这样容易导致采样偏向于存活时间短的节点。第二个产生偏向的原因是P2P系统的连通结构（采样可以用于给网络结构进行拓扑图推测），每个链路更有可能导致采样到一个高连接度节点而非低连接度节点。相关对比技术：1.图采样Cooper等的方法是利用随机算法生成一系列图，这些图具有所有需求的图属性。本文目的在于：并非从一类图中采样一个图，而是从一个未知大规模动态改

30、变的图中进行节点采样。另一个相关的问题是通过从少量主机向大量目标执行tracerout来采样internet路由器，目的是发现internet级别的拓扑。但是探测路由器拓扑和P2P拓扑在图的探测方面的基本操作各不相同。使用tracerout的目的在于“到目的地的路径是什么”，而P2P网络中基本问题是：这个节点的邻居是谁？。此外，internet路由器拓扑改变很慢且相对很稳定，而P2P覆盖网络的拓扑动态性强。另一个相关问题是从一系列web pages中均匀随机选择web page。web page通过超链接相连，具有有向性，易于发现关系。2.RW的图采样就作者了解，从一个动态图中进行均匀随机的R

31、W采样没有被研究过。很多论文将RW作为无结构P2P网络中的偏好搜索。搜索只需要沿着路径定位某一个资源数据，不会全局考虑节点的采样。Awan提到了P2P网络中的均匀采样，使用了几种RW算法包括Metroplis-Hastings方法，但是需要假设图结构没有动态改变，同时还需要某些P2P应用的底层支撑（使用的是power-law模型）。3.在隐藏的Populations中采样P2P网络中的隐藏节点指由于没有中心存储结构使得可以查询所有的节点，节点必须通过查询其他节点的邻居才能被发现。最有名的是respondent-driven sampling方法，这是一种滚雪球式的办法。这个方法首先用采样推测底

32、层网络结构，然后使用与网络有关的估值来获取不同感兴趣领域的subpopulations。这个方法同样不能适用于动态变化的网络环境。4.动态图这些模型不适合P2P系统.网络被看作是一个图G=G(V, E)，网络中的节点被看作顶点集合V，节点之间的连接被看作边集合E。由于系统是一个动态变化的系统，故将时间参数整合到系统中。整个网络被看作基于时间索引的图的无限集合。从这个图的集合中进行采样的一个通用方法就是定义一个测量窗口，。并且从那些在窗口时间内一直存活的节点中均匀随机的选择节点：。因此在不同时间出现的同一个节点不会被区分。当前测量方法表明，节点的存活时间长度非常不均匀，并不符合指数分布规律。大量节点的存活时间很短（几分钟），但少量节点长期存在。故当增大时间窗口长度，集合将会包含更多的存活时间短的节点。本文目的不在于从集合采样一个节点vi，而在于采样在某个特定时刻t的节点vi的某个属性（一个节点的