节点采样技术概述(surveyofpeersampling)

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

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

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

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

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

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

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

8、if push then/ 0 is initial age buffer (myaddress, 0)/ shuffle the viewview.permute()move oldest h items to end of view buffenappend(view.head(c/2 -1) send buffer to pelse / empty view to trigger response send (null) to pif pull thenreceive buffer(p) from p view.select(c, h, s, buffer(p) view.! ncrea

9、seage()(a) active threaddo foreverreceive buffer(p) from p p view.selectpeer() if pull then/ 0 is initial age buffer (myaddress, 0)/ shuffle the viewview.permute()move oldest h items to end of view buffer.append(view.head(c/2 1) send buffer to pview.select(c, h, s, buffer(p) view.increaseage()(b) pa

10、ssive threadmethod view.select(c, h, s, buffer(p)view.append(buffer(p) view.removeduplicats() view.removeoldltemsfminfh, view.size-c) view.removeheadfminfs, view.size-c) view.removeatrandom(view.size-c)(c) method view.selectfc, h, s, buffer(p)协议包含两个线程：主动线程用于初始化与其他节点的通信；被动线程用于接受其他节点的请 求并响应。（对于view.se

11、lectfc, h, s, buffer（p）函数，其每一句代码都很重要，实质就是对view这个数据结 构进行一系列的操作达到想要的效果）我们将系统看作一个非同步的系统（即节点发起的请求应答过程无需阻塞等待），将时间看作 一系列离散的时间单元，在每个时间单元内节点只能执行一次局部视图的拓扑信息交换。关键的参 数为c, h, so其中c表示节点的局部视图大小，为常量；h表示需要从view中删除的age值偏大 的节点描述符个数（下文解释）；s表示需要从view的头部删除的节点描述符个数（其中h, s小于 c/2,下文解释）。鉴于被动线程的内容与主动线程类似，在此仅仅解释主动线程的内容。过程描述如下

12、：1）由selectpeer方法返冋一个目标节点进行gossip信息交换。selectpeer的具体实现会对最终 结果产生影响，下文将详细阐述。2）发送缓冲区buffer：首先将当前运行主动线程的节点描述符置入缓冲区内。然后在view上执 行乱序排列，以此保证从view中选出的个元素是随机的，但是选出的c/2-l个元素不包括age 值最大的h个元素（利用时间戳起到自动剔除可能已失效的节点）。但若选出的元素不足（c/2-l）个， 也可以从age值最大的h个元素中选出若干来补足。3）select© h, s, buffer）方法：当收到应答后将参数 buffer 传递给函数 view.s

13、electfc, h, s, buffer）o 这个函数根据4个参数通过一系列操作得到节点的新view （算法的核心关键所在）。首先将buffer 的内容附在view的后面，然后删除重复的节点描述符，这之后view的大小至少是其原大小。然后 执行三个删除操作将view的大小裁剪到其原始大小。4）removeoldltems（min（h, view.size-c）：首先删除age值最大的h个元素。h越大，删除的age 值偏大的元素越多，这样做的目的是因为age值偏大的元素可能已经是失效节点（根据大规模p2p 系统中节点存活时间服从pareto分布的原则），将其删除就直接避免了与失效节点保持一个无

14、效的 连接（h表示healing）o4）removehead（min（s, view.size-c）：然后再从view的头部删除s个元素。s越大，删除的view 中原有的元素越多。这样做将使得最终节点收到的节点描述符信息有更高的概率留在view中，因为 每次buffer的内容是附在view的原有内容之后，从头部删除s个元素，删除越多则可以留更多空间 来装载接收的buffer内容，使得buffer中的内容有更高的概率留在view中。实质上参数s控制了节 点局部视图中拓扑信息交换的概率，s越高，交换概率越高（s表示swapped）o s很低会导致进行 gossip交换的双方以较高的概率保持原有vi

15、ew的内容而非进行交换。这会导致网络中只存唯一存在 的节点描述符被删除（降低了鲁棒性）；如果s很高，进行gossip交换的双方会以较高的概率进行内 容交换，可以降低网络中唯一存在的节点描述符被删除的可能性。5）removeatrandom（view.size-c）:最终view的大小被随机删除若干元素裁剪到原大小c。具体设计准则组合：主要包含三种准则，冃标gossip节点选择，局部视图的推送方式，局部视 图的元素选择方式。目标gossip节点选择：有两种方式，随机或选择age值最人的节点。rand从view中随机选择一个目标gossip节点tail从view中选择一个age值最大的节点局部视图

16、的推送方式：有三种，push, pushpull, pullopush推方式，即节点主动发起连接pushpull推拉结合方式，节点主动发起连接同吋被动接受连接请求1 11 i pxttt拉古式.即节占别动捋寺诈榕诸求（效率太低衲枷乔.除非榕旳刊一个请求，节点不能主动向网络中注入自身的节点描述符信息）局部视图的元素选择方式：盲选（blind）,恢复式（healer）,交换式（swapper）oblindh=0, s=0任何吋候采取随机选择方式healerh=c/2保持最新鲜的节点描述符在view中swapperh=0, s=c/2gossip双方以更高概率交换拓扑信息注：h 的范围是0, c/2

17、, s 的范围是0, c/2-h, h+s<c/2o具体实现：init方法与getpeer方法。getpeer方法是从节点当前持有的局部视图中返回一个节点描述符。如果要增加返回的节点描述符的 随机性，采样服务必须做到在一定的时间间隔内不对同一个节点采样两次：这样做明显引入了偏好 性而破坏了采样服务的质量。所以服务将会维持一个队列，用于存储没有被采样到的节点。getpeer 方法将每次返回队列中的第一个元素并将这个元素删除。当服务接到一个局部视图更新的通知时， 不在当前队列中的所有元素将被删除，而新加入到局部视图中的元素将被添加到队列中来。如果队 列为空，那服务将返回当前view的随机采样

18、。实验证明，很多参数组合不能获取到较好的显示结果, 但是也没有一种方案可以在各种应用屮取得都比较理想的结果。需要考虑应用差异性采取均衡的参 数设置策略。节点采样全局随机性分析：节点可以很容易的从本地局部视图中进行随机的节点采样服务，但是单 个节点的局部随机采样与独立采样特性的统计特征可能隐藏了网络作为一个整体呈现出的某些结构 属性特征。为了便于进行全局的随机性分析，将网络转化为一个有向图。图的定义如下：如果节点a的view中存在节点b的描述符，则认为从a到b直接可达，在图中 存在有向边（a, b）从a指向b。问题是这个覆盖拓扑与一个随机图有多相似？使得这个覆盖拓扑中每 个view中的节点描述符

19、集合代表整个节点集合的均匀独立随机采样。在图屈性分析中最重要的特性就是度分布。节点i的度定义为：如果某个节点将i的节点描述符 存储于各自的局部视图屮，则所有这些节点的个数之和为节点i的度。每个节点的出度是个常数c, 等于其局部视图大小。度分布决定了节点通信中是否存在通信热点与瓶颈，即负载均衡由度分布决 定。同吋度分布与节点失效与可靠性有直接的关系。除开度分布还有两个参数集群系数（clustering coefficient）与平均路径长度（average path length）。但是入度则并非一个常数，存在一定的时间关联性（节点入度与时间有关）与空间关联性（节 点入度与节点初始的拓扑有关），

20、能否通过dtmc建立节点入度的概率转移矩阵？能否给岀时间关联 性与空间关联性的具体定义？并通过某个算法尽量降低这两个关联性。第一个问题：对于一个特定的协议实现，通过一系列持续的协议执行，通信图是否存在稳定的 属性？换句话说通信图是否存在收敛行为（随着协议的执行，图会演化到某个属性收敛的状态）。我 们希望覆盖网络可以收敛于某个特定状态而与网络的初始拓扑无关。这种属性称之为自组织性。我 们希望在各种场景下运行的协议实例都可以产生一致的、可预期的行为。第二个问题：如果存在收敛，什么样的通信图使得协议实例可以收敛？第三个问题：本地的动态属性与全局度分布的关系？即度分布与其全局属性如度的最大值，方 差，

21、均值等不变时单个节点的度却在变化，这种现象是否可能？如果是这样就导出了一个很重要的 现象：即通信图中如果存在瓶颈，那么瓶颈不会始终都存在于一个节点上，换句话说瓶颈会发生转 移，这样就达到了负载均衡，增强了网络的鲁棒性。a）度分布：给出了三种初始的网络拓扑：初步增加的（初始节点为一个，每个时间间隔加入500个 节点，执行20次加入）；晶格网（规则网）；随机图。一个首要的基本条件是协议的运行不能导致网 络分区现象的产生。push模式会导致网络分区，而pushpull模式不会导致这种现象发生。根据实验, 在度分布上pushpull模式明显优于push模式，pushpull nj以很好的均衡节点入度分

22、布，起到负载均 衡的作用o缺乏自适应性与鲁棒性使得纯push模式不可用。swapper模式可以取得较好的度分布（度 分布的方差较小）；healer模式次之，blind模式最差。1）静态属性：考虑度与参数h, s的关系。h 确定，s增大可以减少度分布的不均匀性；而s确定，h增大同样可以减少度分布的不均匀性。2） 动态属性：考虑节点入度的变化速度，变化的快不快。入度变化慢意味着入度高的节点在较长时间内处于热点状态，不利于负载均衡。首先，根据实验节点入度并非一成不变。对于一段连续时间间 隔中的某个给定节点，考察这个节点度的自相关性（即在不同时刻节点入度的关联性），假设节点入 度为d2, dko则在时

23、间间隔k内序列dj, d2,ck的自相关性定义为工二（©"）（分"）工:疔自相关性高说明随机性差，自相关性为0说明随机性好。实验表明，healer模式的自相关性降低最快。也就是说，healer模式有助于负载均衡（节点度变化趋 向随机，变化较快，不会出现某个节点长期处于热点状态）。b）平均路径长度：节点a与b的最短路径定义为从a到b需耍经过的最少的边，而图的最短路径定 义为所有节点z间最短路径的平均值。研究最短路径的动机在于进行消息分发的应用时，最短路径 反映了一个节点可达的时间与开销的下限。实验表明所有的h与s取值都可以获取较低的平均路径 长度，但较大的s值可以获

24、取接近随机图的效果。c）集群系数：集群系数反映节点a的邻居之间是否也是邻居的可能性。分析集群系数的动机在于消 息分发的应用与自修复时，高集群系数可能破坏消息分发（增加了冗余消息）与自修复（增加了分 区的概率）的效果。h值越大，则集群系数越高，这是因为h值偏大表示节点都仅仅保留最新鲜的 节点描述符使得各自的view重合部分较多。s值越大则可以降低集群系数，这是因为s值偏大可以 控制节点view彼此之间拓扑信息以高概率交换而不是保持一致。容错分析：主要是引入节点失效的剧变场景与网络扰动场景来评估协议的鲁棒性。a）节点失效剧变场景：如何建立收敛后的拓扑的自修复能力与节点失效个数之间的函数关系？在静

25、态场景中对随机网络图实施突然的节点删除，根据实验，最终直到删除67%的随机节点网络才出现 分区。在动态场景中我们从收敛的随机拓扑中删除50%的节点來观察其行为，发现h值偏大可以导 致很快的拓扑修复。b）网络扰动场景：关注扰动率与重启动方法（bootstrapping）o扰动率分为止常扰动率，一般为1%-2%； 和剧烈扰动率，一般为30%o假设存在两种重启动方法，中心化和随机。h值增大可以降低扰动时 view中的无效节点，加速无效节点的删除。healer模式可以容忍剧烈的扰动。结论与讨论：1）关于随机性：swapper模式的随机性最好，可以获得比随机图还小的度的方差（就是节点的入度 变化很小），

26、增加h值会增大集群系数。在所有模式下平均路径长度都接近随机图。随机性与应 用程序的需求本质相关，比如将信息洪泛到网络中每个节点只与网络半径有关，而与度分布和 集群系数无关。故如果需要计算本地的一些对全局的统计估值，如网络容量，或全局可用资源 等屈性不需耍全局随机性（这个观点好像不对，应该和全局随机性有关，全局的随机性利于更 快的 aggregation ）o2）关于负载均衡：负载均衡与度分布有关，如果一个节点的节点描述符被很多其他节点都持有在 view中，则这个节点具有更高概率作为目标节点与其他节点发生gossip通信，也具有更高概率 被采样到提供给上层应用使用，而导致这个节点产生更多的流量，

27、引发负载不均衡。达到负载 均衡最好的模式是swapper模式。如果h值固定，增大s可以减少节点入度的方差；但如果s 值固定，增加h同样可以减少节点入度的方差。3）关于容错：h值越大越好，h值越人有助于快速的删除失效链路，实现快速的修复。注：与杨朱二人讨论中，二人提到：1）当a向b发送缓存的节点描述符中，除了 a自身的age被初 始化为0,其他节点描述符的age是否也初始化为0?个人观点，如果其他节点描述符的age不初始 化为0,则在执行函数removeoldestltems（min（h, view.size-c）h寸,若buffer中的元素age都偏大,则 会直接删除很多元素，这样难以实现sw

28、apper模式。（节点描述符只有通过自己主动向网络中注入， 即除了节点会将自己的age出师化为0发送外，其他选入buffer中的描述符age维持原值不变） 2）针对函数view.removeduplicates（）,如果两个address相同的元素，到底是删除age值小的还是 age值大的（如果删除age值大的，就倾向于保留新鲜节点，如果删除age值小的，就倾向于维持 原有view不变化）。（保留较新的，剔除较老的）基于 rw 的随机采样技术 （on unbiased peer sampling for unstructured peer-to-peer networks）木文阐述真实的p2p

29、系统的动态性与异构性如何引入了节点采样时发生的偏见性。并提岀 metropolized random walk with backtracking （mrwb）作为一个重要的技术来收集无偏采样节点。背景：采样是利用轻量级的数据收集方法来了解系统的一些屈性。过去的采样倾向引入偏见，有两个原因: 1节点的动态特性可能引起偏向于那些生命周期短的节点；2.覆盖拓扑的异构性导致偏向于连接度高 的节点。本文的贡献：1对p2p系统使用了详细的检查方法检查采样在时空维度上的质量。2.深度探索mrwb 采样方法的可用性。采样偏向性产生的第一个原因来自系统的动态性，新peer到达，存在的peer在任意时间可以离开

30、, 文章表明这样容易导致釆样偏向于存活时间短的节点。第二个产生偏向的原因是p2p系统的连通结 构（采样可以用于给网络结构进行拓扑图推测），每个链路更有可能导致采样到一个高连接度节点而 非低连接度节点。相关对比技术：1图采样cooper等的方法是利用随机算法生成一系列图，这些图具有所有需求的图属性。本文目的在于：并 非从一类图中采样一个图，而是从一个未知大规模动态改变的图中进行节点采样。另一个相关的问题是通过从少量主机向大量冃标执行tracerout来采样internet路由器，冃的是发现 internet级别的拓扑。但是探测路由器拓扑和p2p拓扑在图的探测方而的基本操作各不相同。使用 trac

31、erout的目的在于“到目的地的路径是什么，而p2p网络中基本问题是：这个节点的邻居是谁？。 此外internet路由器拓扑改变很慢且相对很稳定，而p2p覆盖网络的拓扑动态性强。另一个相关问题是从一系列web pages中均匀随机选择web page。web page通过超链接相连，具有 有向性，易于发现关系。2. rw的图采样就作者了解，从一个动态图中进行均匀随机的rw釆样没有被研究过。很多论文将rw作为无结构 p2p网络中的偏好搜索。搜索只需要沿着路径定位某一个资源数据，不会全局考虑节点的采样。a wan 提到了 p2p网络中的均匀采样，使用了几种rw算法包括metroplis-hasti

32、ngs方法，但是需要假设图 结构没有动态改变，同时还需要某些p2p应用的底层支撑（使用的是power-law模型）。3. 在隐藏的populations中采样p2p网络中的隐藏节点指由于没有屮心存储结构使得可以查询所有的节点，节点必须通过查询其他 节点的邻居才能被发现。最有名的是respondent-driven sampling方法，这是-种滚雪球式的办法。 这个方法首先用采样推测底层网络结构，然后使用与网络冇关的佔值來获取不同感兴趣领域的subpopulationso这个方法同样不能适用于动态变化的网络环境。4.动态图这些模型不适合p2p系统.网络被看作是一个图g=g(v,e),网络中的节

33、点被看作顶点集合v,节点之间的连接被看作边集合e。 由于系统是一个动态变化的系统，故将时间参数整合到系统中。整个网络被看作基于时间索引的图的无限集合。g严g(vf,ej。从这个图的集合中进行采样的一个通用方法就是定义一个测量窗口，£,*)+。并且从那些在窗口时间内一直存活的节点中均匀随机的选择节点：k0,r0+a = ur=/0 ” o因此在不同时间出现的同一个节点不会被区分。当前测量方法表明，节 点的存活时间长度非常不均匀，并不符合指数分布规律。大量节点的存活时间很短(几分钟)，但少 量节点长期存在。故当增大时间窗口长度,集合匕利+将会包含更多的存活时间短的节点。本文目的不在于从集合岭山+厶采样一个节点w，而在于采样在某个特定时刻t的节点w的某个属性(一个节点的属性是随时i'可变化而变化的)。由于系统是动态变化的，所以本文认为在不同时刻将同 一个节点采样多次是合理的。只有这样才能使得在节点行为呈现动态性的条件下采样是无偏的，因 为采样已经与节点的存活时间去除了关联。每种采样算法在以下两方面多存在不同：1.下一个要探测的节点是谁？ 2.怎样从探测到的节点中提取 采样节点集合？以前的方法使用宽度优先或深度优先的方式来探测所有节点，存在问题如下：1. 发现的节点存在较强的关联性(由于他们的邻居之间存在关系)。2. 连接度高的节点