第九章P2P数据管理系统

第九章P2P数据管理系统主要内容P2P系统概述P2P系统的体系结构P2P系统中的数据管理资源的定位和路由处理语义异构查询处理与优化

P2P模型(Peer-to-Peer模型，即对等计算模型)是一种新型的网络服务体系结构，是一种通过直接交换的方式来共享计算机资源和服务的互联网应用模式。P2P系统具有很多的优势： 第一，P2P系统中的每一个成员具有平等的地位，可同时充当提供者和消费者两种角色。提供者可以向消费者提供共享的数据和计算资源(存储空间或者是空闲的CPU时间)； 第二，P2P系统具有很好的扩展性。系统成员可以动态地加入和退出P2P系统，增加了系统的灵活性以及内容的丰富性； 第三，在P2P系统中，数据是分散存储的，克服了传统集中式数据存放方法所带来的性能瓶颈、单点失效等问题，提高了系统的效率，也增加了系统的可用性和可靠性。基本概念 目前，基于P2P技术的应用是互联网上最为活跃的一个部分。统计数据表明，P2P应用所产生的网络流量已经占据了约75%的互联网总通信量。基于P2P技术的搜索引擎、文件共享机制、网络视频音频分发机制为全球用户提供了更多的资源、更高的带宽以及更好的服务质量。 下面介绍几个常用的基于P2P技术的互联网服务：数据共享服务数据搜索及查询服务分布式协同计算服务数据存储服务流媒体传输服务基本概念数据共享服务 早期出现的提供此类服务的系统有Napster和Gnutella，现在比较流行的是eMule和BitTorrent。使用者通过运行提供此类服务的软件加入数据共享网络，然后就可以直接从网络中已有的其它节点上下载感兴趣文件。与此同时，自己也可以为其它节点提供下载服务。整个系统中，数据被分布地存储在所有成员节点上，服务也由全部节点共同来担当。需要特别指出的是，虽然数据不是集中存储，但数据的目录信息可能集中存储，这有利于提高资源的定位效率。数据搜索及查询服务 提供此类服务的系统有Infrasearch、Pointera等等，主要用来在P2P网络中完成信息检索。基于P2P网络的数据搜索与基于互联网中心服务器的数据搜索截然不同，必须要考虑P2P网络拓扑结构的动态性以及节点的异构性，不同节点所使用的软硬件平台以及数据语义也不一定相同。基本概念分布式协同计算服务 如寻找外星人计划SETI＠HOME。参加者把个人计算机上的空闲CPU时间贡献出来，去协同分析和计算来自于位于波多黎各的阿雷西博（Arecibo）射电望远镜观测到的数据，从而筛选出可能是地外生物发出的信号。相类似的项目还有寻找最大质数项目GIMPS和Google的共同搜索项目Folding＠home。需要强调的是，在这些分布式协同计算应用中，都采用了一个集中式事务管理器来协调节点的行为，包括任务的分派、同步和结果汇总。数据存储服务 如Microsoft公司的Farsite和加州大学的OceanStore等软件。数据在P2P网络上的分散化存放可以减轻服务器负担，增加数据的可靠性和分发速度。流媒体传输服务 主要包括PPLive、CoolStreaming等软件所提供的视频音频文件分发服务，以及OICQ软件所提供的即时通信与文件传输服务、多人参与的计算机对弈游戏等。基本概念 为了解决数据放置和检索所带来的巨大挑战，Gribble等人提出将数据库技术与P2P技术相结合，其中最重要的是在P2P系统中引入了数据模式的概念，出现了基于数据模式的P2P数据管理系统。有力地解决了不同节点之间的语义异构问题，提高了数据存储和查询的效率，并且能够支持复杂查询。 总结来看，基于模式的P2P数据管理系统与分布式数据库之间会有很多的相似或相异点：

(1)从网络拓扑结构上来看，分布式数据库中的节点相对稳定，通常以受控的方式加入或退出网络；而在P2P系统中，对等节点即兴地加入或离开网络,网络拓扑结构具有很强的动态性，每个节点的逻辑位置也可能改变；基本概念

(2)从数据的分布性来看，分布式数据库和P2P系统都是将数据分布地存储到地理上分散的节点上，但是在分布式数据库系统中，全部数据首先是一个整体，有一个全部节点公认的全局模式，全局数据经过分片和分配被映射到了各个场地上存储起来，是一个全局与局部之间的映射关系，而且分布存储的数据之间依然要严格保证数据的一致性；而在P2P系统中，没有全局数据的概念，也不强制要求数据必须保持一致性；

(3)从查询处理上来看，在分布式数据库中，存在一个全局的查询处理器，负责全局查询的分解和变换，同时还负责事务在不同节点上执行的协调工作，由于网络拓扑相对稳定，因此基于分布式数据库的查询操作可以检索到所有满足查询条件的元组；在P2P系统中，不存在协调全局的超级节点，查询从发起场地沿着某一路径转发，逐步定位查询结果。由于网络结构不稳定，因此通常不能检索到全部的满足查询条件的结果。查询结果的正确性和完整性极大地依赖于瞬间网络状态和语义映射。

基本概念P2P系统的体系结构

P2P系统的体系结构分为三种：集中式、分布式和混合式。集中式P2P网络

在集中式P2P网络中，维护着一个全局的目录服务器，它负责记录节点的共享信息并回答对于这些信息的查询请求。提供者节点把共享信息发布到目录服务器上，消费者节点首先在目录服务器上查找所需资源的准确节点位置，然后连接节点完成数据交换。 集中式P2P网络与传统的client/server模式下的集中式系统虽然有相似之处（都维护着一个中心服务器）但两者有着本质的区别：传统的集中式系统的中心服务器不仅保存资源的目录信息，更为关键的是保存全部的共享资源，客户端只能连接中心服务器并下载所需要的数据；而集中式P2P网络的中心服务器只保留共享信息的目录，所有共享信息依然保存在局部节点上。消费者节点在中心服务器上查找到资源提供者节点后，完成节点之间的连接，并进行数据交换。P2P系统的体系结构P2P系统的体系结构分为三种：集中式、分布式和混合式。集中式P2P网络

第一代P2P网络均采用集中式结构，其中典型的代表是Napster。Napster是一种可以在网络中下载自己想要的MP3音乐文件的软件。安装了Napster系统的机器将成为一台服务器，可为其它用户提供音乐下载服务。Napster系统本身并不存储和提供MP3文件下载，它实际上提供的是整个网络中包含的MP3音乐文件“目录”，即MP3音乐文件的地址，这个目录存放在一个集中的服务器上，而MP3音乐文件本身则分布在网络中的每一台机器上。使用者在目录服务器上找到想要的MP3音乐文件的位置，然后到指定的位置完成下载。2002年，Napster由于违反了知识产权保护法而被迫关闭。

P2P系统的体系结构P2P系统的体系结构分为三种：集中式、分布式和混合式。(2)全分布的P2P网络

集中式P2P网络虽然有利于内容查找，但位于系统中心的目录服务器依然是整个系统的瓶颈，而且依然存在着单点失效、负载不均衡、目录更新代价大等问题。 第二代P2P网络则完全向全分布式方向发展，这也为内容的存储和查询提出了挑战。根据内容的组织方法来划分，有两种形式的全分布式P2P网络：结构化全分布式P2P网络非结构化全分布式P2P网络P2P系统的体系结构P2P系统的体系结构分为三种：集中式、分布式和混合式。(2)全分布的P2P网络

结构化全分布式P2P网络是一种维护节点之间在应用层上互联的组织方法。它按照一定的逻辑拓扑结构将系统中的节点互连起来，内容的存放也相对有序，通过路由消息实现系统中任意两个节点的互通。结构化的P2P网络比较适合于拓扑结构相对固定的应用环境。通常使用分布式哈希表(DHT)来实现文件到节点的映射。目前已有的结构化全分布式P2P网络有Pastry、Tapestry、Chord和CAN等。P2P系统的体系结构P2P系统的体系结构分为三种：集中式、分布式和混合式。(2)全分布的P2P网络

结构化全分布式P2P网络是一种维护节点之间在应用层上互联的组织方法。它按照一定的逻辑拓扑结构将系统中的节点互连起来，内容的存放也相对有序，通过路由消息实现系统中任意两个节点的互通。结构化的P2P网络比较适合于拓扑结构相对固定的应用环境。通常使用分布式哈希表(DHT)来实现文件到节点的映射。目前已有的结构化全分布式P2P网络有Pastry、Tapestry、Chord和CAN等。P2P系统的体系结构P2P系统的体系结构分为三种：集中式、分布式和混合式。(2)全分布的P2P网络

在非结构化全分布式P2P网络中，节点通过一些松散的规则组织在一起，文件也是随机存放的。非结构化P2P网络扩展性和容错性较好，但是它采用应用层的广播协议，消息量过大，网络负担过重，节点无法得知整个网络的拓扑结构或组成网络的其它对等节点的信息。新节点加入网络时，系统必须向这个对等节点提供一个对等节点的列表，但P2P网络的强动态性，即节点可随时加入和退出，限制了这个对等节点列表的有效性。

Gnutella是应用最为广泛的非结构化P2P网络。它没有所谓的中心索引服务器，不需要在目录服务器上注册共享信息。当对等节点进行查询的时候，查询请求通过flooding方式广播发送给直接相连的邻居，并由近及远依次转发直到收到响应，或者达到了最大的泛洪步数。P2P系统的体系结构P2P系统的体系结构分为三种：集中式、分布式和混合式。(3)混合型的P2P网络在混合型的P2P网络中，节点以簇的形式组织，某些具有较高性能(如计算能力、存储容量和通信带宽)的节点被选择担当簇头节点，簇内节点把共享信息的目录发布到簇头节点上，簇头节点负责进行搜索和查询处理。普通节点加入网络后，可以选择多个簇头节点作为它的父亲节点，得到簇头节点的允许后，该节点加入簇头节点所领导的域，并把自己共享资源的目录发布到簇头节点上。簇头节点向查询提供匹配的资源所在的地址，而不是资源本身。如果在本领域不能找到与查询匹配的资源，查询将被转发给其它的簇头节点。P2P系统中的数据管理

核心问题包括：数据的存储策略、索引的构造策略、语义异构性的调整策略和查询传播与查询处理策略。P2P数据管理的性能指标有：可扩展性：即允许节点自由地加入和离开网络，查询处理的性能不能过分依赖网络规模，不能因为网络规模扩大而显著下降；自治性：P2P节点在系统结构、软件与功能配置，通信方式上均有很强的自治性，查询处理算法应当充分尊重节点的自治性；健壮性：对故障的健壮性和对攻击的健壮性，在面临节点故障、离开、攻击时，系统应该保持可用性、保持一定的服务质量和效率；支持语义异构：peer节点各自使用自己的数据模式来表达和组织数据。为了节点之间的数据交换，需要解决语义异构问题。查询处理能力：P2P网络中的查询处理涉及到数据存储、语义异构、索引组织、查询请求分发和结果汇聚等方面。查询的准确性、查全性、响应时间和通信量是表现P2P系统查询处理能力的重要指标。资源的定位和路由

在P2P网络中进行信息检索，第一步是要进行资源定位。目前主要有两种P2P资源定位策略：面向非结构化P2P网络的资源定位方法；面向结构化P2P网络的资源定位方法；资源的定位和路由面向非结构化P2P网络的资源定位方法 在非结构化P2P网络中，节点没有相对固定的逻辑地址，采用随机的方法或者启发式的方法加入网络，网络拓扑随着节点的变迁随时发生演变。泛洪（Flooding）搜索算法

k遍历随机游走算法(k-walkerrandomwalk)

基于移动代理(MobileAgent)的搜索算法

资源的定位和路由面向非结构化P2P网络的资源定位方法 泛洪（Flooding）搜索算法

泛洪算法在搜索时向所有的邻居节点转发查询消息，因此又叫宽度优先搜索。在网络中，一个节点向所有邻居节点广播查询消息，邻居节点再向自己的邻居节点广播，这个过程不断进行下去，像洪水在网络中各个节点流动一样，所以叫做Flooding搜索。搜索的节点预先设定消息生命周期TTL(Time-to-live)并赋以初值。查询在节点间每传播一次TTL减1，如果TTL减到0，则丢弃查询。如果搜索到资源则返回目标机器的信息用来建立连接。

泛洪算法的特点：路由算法比较简单，易于实现。缺点是查询消息数量大，耗费大量通信带宽。

资源的定位和路由面向非结构化P2P网络的资源定位方法

k遍历随机游走算法(k-walkerrandomwalk)

k遍历随机游走算法是盲目搜索算法中采用漫游策略的典范。它进一步加强了对节点路由消息的扩散程度的控制。该算法中，请求者发出K个查询请求给随机挑选的K个相邻节点。然后每个查询信息在以后的漫游过程中直接与请求者保持联系，询问查询结果的有效性并判断是否还要继续漫游。如果请求者同意继续漫游，则又开始随机选择下一个转发节点，否则终止搜索。

k遍历随机游走算法的特点：提高了查询信息的传播速度，减少了路由消息量，一定意义上实现了节点的负载均衡。但是，查询结果的准确性非常依赖于随机漫步的路径，因此结果准确性不稳定。资源的定位和路由面向非结构化P2P网络的资源定位方法

基于移动代理(MobileAgent)的搜索算法

移动代理技术非常适合在网络环境中完成信息检索的任务。代理是一个能在异构网络中自主迁移的服务程序，它可与其他代理和资源进行交互。源节点发送一个包含了查询信息的代理给它的邻居节点，当这个代理到达一台新的机器上后，就在这台机器上进行资源搜索。如果这台机器上没有它想要的资源，则它自主向下一个邻居节点迁移，如果找到资源，则将结果或者包含结果的节点IP返回给源节点。 优点：具有很好的用户个性化管理能力，支持离线查询，支持更加智能的代理迁移机制，从而获得更好的查询效率； 缺点：代理的运行增加了节点的负载，而且会带来安全性、隐私保护等多方面问题。资源的定位和路由面向结构化P2P网络的资源定位方法

结构化P2P网络是指像Chord、Tapestry、CAN之类的点对点的网络。在结构化P2P网络中，每个节点都有固定的地址，整个网络具有相对稳定和规则的拓扑结构。依赖拓扑结构，可以给网络的每一个节点指定一个逻辑地址，并把地址和节点的位置对应起来。对于给定的某个地址，拓扑结构保证只需要通过跳就能路由到相应地址的节点上去(n是网络中的节点数)。P2P网络中节点的逻辑地址通常是由散列函数得到的，即每个节点都保存一张分布式散列表(DHT，DistributedHashTable)进行路由。因此，结构化P2P网络也叫作DHT网络。资源的定位和路由面向结构化P2P网络的资源定位方法

在DHT网络中，主机称为节点，共享资源称为对象。节点拥有名字，并且一个节点可以在多个兴趣维度下拥有多个名字。对于一个节点来说，最为典型的名字就是它的IP地址。系统拥有一个标识符空间，它是一个整数域，每个标识符就是一个来自该整数域的唯一整数。散列函数将节点的名字转换为节点的标识符，节点的标识符相当于节点的虚拟地址(VID)，例如VID=hash(IP)。同时，共享资源也有自己的对象名。散列函数将对象名转换为对象的关键字(KEY)，即kEY=hash(ObjectName)。在DHTP2P网络中，散列值相邻的节点定义为邻居节点。系统中的每个节点都拥有一部分散列空间，它负责保存某个范围的对象关键字。共享资源被发布到具有和KEY相近虚拟地址的节点上去。资源定位的时候，就可以快速根据KEY到相近的节点上获取二元组（KEY,VID），从而获得文档的实际存储位置。目前典型的DHT网络有Chord、Tapestry、CAN等，它们的主要区别在于采用了不同的DHT路由算法，因此它们具有不同的逻辑拓扑结构。资源的定位和路由面向结构化P2P网络的资源定位方法(1)chord协议

Chord是一个环形拓扑结构，Chord协议使用的散列函数是SHA-1。在Chord中，每个节点Ni有2个邻居：以顺时针为正方向排列在Ni之前的第1个节点称为Ni的前继(predecessor)，在Ni之后的第1个节点称为Ni的后继(successor)。资源存放于其关键字为KEY的后继节点上。为了路由的需要，节点保存前继和后继信息，并维护一张最多m项的路由表，称为查询表，m称为查询表级数。其中，第k项(k为查询表数组的下标)保存键值(Node_VID+2k-1)mod2m的后继节点VID。由此可见，表中节点之间的间距以2k-1的关系排列，这实际上是折半查找算法需要的排列关系。网络的最大容量为n=2m个节点。资源的定位和路由面向结构化P2P网络的资源定位方法(1)chord协议

Node7Node15Node22Node33Node39Node48Node42Node51Node63+1+2+4+8+16+32例：m=6，具有9个节点的Chord网络中的资源存储定位Node33节点的查询表(FigureTable)kNode_VID+2k-1(Node_VID+2k-1)mod2m的后继节点VID133+1Node39233+2Node39333+4Node39433+8Node42533+16Node51633+32Node7资源的定位和路由面向结构化P2P网络的资源定位方法(1)chord协议Node15Node7Node15Node22Node33Node39Node48Node42Node51Node63①：由Node_VID+2k-1=33+16=48最接近54，得第一跳找到Node51节点；②：在Node51节点上，由于Node_VID+2k-1=51+2=53，可找到Node63节点；③：在Node63上找到Key=54的共享资源，Node63给Node33发出回馈；从node33节点发起的查询键值为54的共享资源的搜索过程：资源的定位和路由面向结构化P2P网络的资源定位方法(2)PastryPastry从逻辑上是一个网状的拓扑。Pastry中没有规定具体应该采用的散列函数，但是定义了一个128bit的整数空间作为键值的域。每个节点拥有一个128bit的逻辑地址(Node_VID)。为了保证Node_VID的唯一性，一般由节点的IP地址通过散列计算获得。Node_VID在域内均匀分布，因此逻辑地址相邻的节点地理位置不同的概率很大。节点的逻辑地址和关键字均表示为一串以2b为基的数。Pastry把消息路由到节点逻辑地址最接近关键字的节点上。每个节点都维护一个路由表(RoutingTable)、一个邻居节点集合(NeighborSet)和一个叶子节点集合(LeafSet)，三者共同构成了节点的状态表。资源的定位和路由面向结构化P2P网络的资源定位方法(2)Pastry

Pastry路由的具体过程是：当收到一条搜索请求时，节点首先检查共享资源的关键字是否落在叶子节点集合中。如果是，则直接把消息转发给对应的节点，也就是叶子节点集合中逻辑地址和关键字最接近的节点。如果关键字没有落在叶子节点集合中，那么就将使用路由表进行路由。当前节点会把消息发送给节点号和关键字直接的共同前缀至少比现在节点长一个数位的节点。当然，会出现路由表对应表项为空或路由表表项对应的节点不可达的情况。此时，路由消息将会被转发给共同前缀一样长的节点，但是该节点和当前节点相比，其节点逻辑地址在数值上将更接近关键字。这样的节点一定位于叶子结点集合中。因此，只要叶子节点集合中不会出现一半以上的节点同时失效，路由过程就可以继续。从上述过程中可以看出，路由的每一步和上一步相比都向目标节点前进了一步，因此这个过程是收敛的。资源的定位和路由逻辑地址值<10233200逻辑地址值>1023320010233133102331211023320310233213102331101023310310233221102332300-221210212-23012033-120320301-1-3012331-2-2302031-3-02102210-0-3120310-1-32102210-3-23302102-0-0230102-1-1302102-2-230231023-0-3221023-1-0001023-2-121310233-0-0110233-1-0020102332-2-00面向结构化P2P网络的资源定位方法(2)Pastry1302102210200230113012333130123302232120223012033120320333213321Node_VID:10233200Key:10233102LeafSetRoutingTableNeighborSet例：在Pastry网络中节点10233102的路由表信息。b取值为2，即所有的数均是4进制数。其中路由表的最上面一行是第0行。路由表中每行的阴影项表示当前节点逻辑地址对应的位。路由表中每项表示为“和10233102的共同前缀--下一数位--节点逻辑地址的剩余位”。资源的定位和路由面向结构化P2P网络的资源定位方法(3)CAN(内容寻址网络，Content-AddressableNetwork)CAN基于虚拟的d维笛卡儿坐标空间来实现其数据组织和查找，因此CAN中的散列函数的结果是一个d维笛卡儿空间，其中d是根据系统规模大小而确定的常量。整个P2P网络被映射成为一个d维的笛卡儿空间，节点的逻辑地址是由散列函数计算出的一个d维的向量。因此，每个节点都对应于d维笛卡儿空间中的一点。整个坐标空间动态地分配给系统中的所有节点，每个节点都拥有独立的互不相交的一块区域。共享资源也经散列函数对应于d维笛卡儿空间中的一点，这样共享资源就找到了它相应的存储位置。每一个CAN网络中的节点都维护着一个相邻节点表。相邻节点的定义是，在d维笛卡儿坐标空间中，如果两个节点的坐标在其中的d-1维上均相等，在剩余的1维上坐标值相邻，则这样的两个节点成为相邻节点。因此，d维空间中的节点共有2d个邻居节点。资源的定位和路由面向结构化P2P网络的资源定位方法(3)CAN(内容寻址网络，Content-AddressableNetwork)B5N1B4N4N2N5B3N6N3B2N9N8N7B1例：在2维CAN网络中进行资源查找的过程：查询从N2节点发起，资源的关键字是(a,b)，假设0≤a≤A1，0≤b≤B1。N2节点负责存储的关键字区间是(A3~A4,B3~B4)。N2首先判断(a,b)是否属于(A3~A4,B3~B4)：如果属于，说明待查找的资源在本地；否则，则可沿着A维或者B维向包含(a,b)的关键字区间转发查询请求，直到找到N9节点，查找完成。处理语义异构性 在P2P网络中，peer节点之间是松散耦合的，每个节点都具有充分的自治性，具体体现在：每个节点可以自由地加入和退出网络；加入网络的节点可以具有不同的组件结构，可以使用不同的操作系统和数据管理系统。peer节点的自治性使得不同的数据源具有多层次的语义异构性：模式级异构：数据在关系名、属性名、属性的值域、属性之间的依赖关系、以及属性到值域的映射方面不同。数据级异构：现实世界的相同实体使用不同的表示形式。处理语义异构性 当前，解决语义异构的主要方法是在peer间建立模式或者数据映射，其中存在着巨大的局限性：多数映射就是简单的相等或者包含关系，某些研究提出使用更为复杂的映射，如合取、析取等，但这些映射关系尚不能处理大数据源的情况；无论是查询发生前预先确定语义映射关系，还是在查询提出后根据关键字匹配确定映射关系，都不能依据查询来解释语义冲突