节点采样技术概述(survey of peer sampling).doc

基于gossip机制的节点采样技术概述（gossip-based peer sampling） 这是什么技术，为什么需要这个技术， Gossip机制，即流言机制，作为一种简单可靠的拓扑管理与消息分发机制，在大规模的分布式系统中得到了广泛的应用，其主要应用包括信息分发，数据收集，拓扑管理等方面。其产生原因主要由于在大规模的分布式系统中，底层物理链路存在数据丢包与链路断开等现象，节点规模的可扩展性与消息分发的可靠性难以得到有效保证。 基于gossip机制的覆盖网络协议模仿流言传播的特性，系统中的每个节点定期的从邻居表中选择一个节点子集，然后与这个子集中的节点进行拓扑信息（邻居表信息）的交换，来维持一种动态的覆盖拓扑结构。如何进行子集的选择对于基于gossip机制的消息分发是至关重要的。理想的情况下希望从分布式系统的所有节点中均匀随机的选择邻居节点。基于这个假设而衍生出的gossip协议已经得到了很多良好的特性：如可扩展、可靠、有效。 在实际应用中，假设一个节点可以知道系统中的其他所有节点是不现实的。因为当前的大规模分布式系统规模可以达到10万或以上级别，同时节点可能频繁加入或离开系统（称之为churn现象），前者需要巨大的存储开销，后者需要节点维持大量的对邻居节点的同步信息开销，这导致了节点以及整个系统的性能严重下降。 所以采取一种分布式的拓扑管理策略来替代全局的拓扑管理策略进行gossip机制的协议部署显得至关重要。 节点采样服务，是一种独立于应用的服务，就是在某个时刻系统中任意一个节点通过这个服务可以获取一个系统中的随机选择节点。节点采样服务可以应用于消息分发，数据收集，负载均衡以及网络管理。采样服务提供了任何节点与其他节点进行通信连接的可能性。 节点采样服务的基本原理本身基于gossip机制的特征，每个节点都维持一个本地的有限数目的邻居表，邻居表中包含若干个系统中的其他节点信息（称之为节点描述符），每隔一段时间节点使用gossip机制与某个或某几个邻居进行各自邻居表信息的交换来刷新自己的邻居表。 （但是很明显存在若干问题有待解决： 单个节点从本地邻居表中选择的节点的随机性，即本地的有限数目邻居表如何映射系统中的所有节点来保证节点选择的随机性？ 当系统中存在节点失效、消息丢包以及网络扰动时如何保证此时节点的选择依然保持良好的随机性？ 由于系统中的节点分布不同，如何避免某个节点被采样的次数过多，即避免出现网络热点，保证负载均衡。） 事实已经证明：采用push-pull模式要优于纯push或是纯pull模式。同时事实已证明，在进行成员策略管理时要兼顾负载均衡与抗网络扰动与节点失效。 （这引出了本文认为很重要的可能的一个研究点：基于gossip的节点采样服务存在负载均衡与抗网络扰动与节点失效这两个需求，如何通过环境的变化来动态调整若干关键参数来同时部分满足这两个需求？即某个时刻根据网络环境偏向于满足某个需求） 下面给出基于gossip机制的节点采样服务的基本实现框架： 基于gossip的节点采样服务就是为某个节点提供一个获取系统中随机节点的方法。其主要的方法只有两个，如下： init()：init方法用于对刚加入覆盖网络中的节点进行初始化的一系列操作，这个操作是应用相关的（比如针对消息分发，数据收集等等）。 getPeer()：getPeer方法返回一个系统中随机选择的节点。理想情况下这个采样是独立的无偏采样，被采样节点的特性是与实验有关的（被采样节点的随机性在时间上和空间上可能存在关联）。重点就在研究getPeer方法的不同实现版本，找出每种版本最适合于什么应用，然后针对总体环境在优化均衡考虑或直接针对某个场景做优化。 协议的总体描述：考虑网络中一系列连通的节点，每个节点都有一个地址用于消息的发送，每个节点都有一个本地邻居表用来代表节点对全局成员关系的部分感知。理想情况下本地邻居表包含网络中所有其他节点，但实际中本地邻居表不可能包含所有的节点。如果本地邻居表包含所有其他节点信息，称之为节点持有网络的全局视图；如果本地邻居表仅仅包含所有节点的一个子集，则称之为节点持有网络的局部视图。局部视图是c（c为常数）个节点描述符的列表。每个节点都持有相同大小的局部视图。 一个节点描述符表示一个网络地址（例如一个IP地址）和一个时间戳。时间戳用于表示这个节点描述符的存活时间，时间戳的值越大则表明这个描述符存在于节点的局部视图中的时间越长。可以认为节点的局部视图是一个数据结构，在这之上定义了一组操作集合。这意味着除非某个特殊的操作施加于局部视图，否则局部视图中的元素顺序不会显式变化。同时规定局部视图中不允许存在相同网络地址的两个描述符。 节点定期持续进行gossip的交换过程来保证局部视图中的描述符是系统全局拓扑信息的一个随机集合，使得局部