P2P持久存储研究综述

P2P持久存储研究综述∗田敬1+,代亚非11(北京大学计算机科学技术系,北京100871)ASurveyofDurablePeer-to-PeerStorageTechniques*JingTian1+,YafeiDai11(DepartmentofComputerScienceandTechnology,BeijingUniversity,Beijing100871,China)+Correspondingauthor:Phn:[phone]-8010,E-mail:[e-mail],(P2P)hasbeenoneofthemostimportantarchitecturesforInternetapplicationsforitsinherentscalability,faulttoleranceandhighperformance.TheresearchofP2Pstoragesystemsisoneofthehotissues,andP2PstoragesystemisregardedasoneofthemostpromisingP2Papplications.However,toprovidedurabledatastorageisnottrivialworkandsetsgreatbarriertorealdeployedsystems.ThissurveypapersurveystheP2Pstoragesystemsandtechniquesfordurablestorage.WefirstintroducethebasiccomponentsofadurableP2PstoragesystemandtheadvantagesbyusingP2Parchitecture.Afterpresentingtheresearchframework,weintroducesometypicalP2Pstoragesystemsandthetechniquestheyadopted.Byadetailedcomparing,wediscusstheprosandconsofthetechniquesfordifferentenvironments,theproblemsincurrentresearchandsomefutureresearchissues.Keywords:survey;Peer-to-Peer;storage;durability;redundancy;placement;failuredetection;maintenance摘要:P2P(Peer-to-Peer)的组织模式已经成为新一代互联网应用的重要形式,它为应用带来了更好的扩展性,容错性和高性能等特点.P2P存储系统一直是研究界所关注的热点,被认为是P2P最具前途的应用之一.数据的持久存储是制约P2P存储系统发展的关键问题,也是其研究的难点.本文综述了P2P存储系统及数据持久存储相关技术的研究现状.首先概述了P2P存储系统的基本概念及其在不同应用环境中的优势,并介绍了数据冗余,数据分发,错误检测和冗余数据维护等多种持久存储的基本技术.在一个P2P存储系统研究框架下,介绍了目前知名的P2P存储系统及其使用的持久存储技术.对于各种技术进行了详细综述和对比讨论,分析各种技术的适应环境及优劣,指出了存在的问题和未来研究的方向.关键词:综述;对等网络;存储系统;持久性;冗余;数据分发;错误检测;数据维护中图法分类号:TP393文献标识码:A近年来，P2P(Peer-to-Peer)技术在即时通讯、文件共享及流媒体传输等应用领域均显示出了极大的优势，∗SupportedbytheNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.2004CB318204(国家重点基础研究发展规划(973))作者简介:田敬(1979－),男,北京顺义,博士生,主要研究领域为P2P存储系统;代亚非(1958－),女,博士,教授,博士生导师,主要研究领域为P2P计算,分布式存储.田敬等:P2P持久存储研究综述961成为构建新型大规模互联网应用的主要结构和技术之一。由于巨大的技术挑战，P2P存储应用并没有获得相应的商业成功，然而P2P存储系统一直被P2P科研社区认为是极富前景的一种应用，并一直是学术界研究的热点。本文将综述P2P存储系统发展现状，指出面向持久存储的技术挑战和目前研究的主要成果。P2P存储系统，也即对等存储系统，是指存储节点以一种功能对等的方式组成的一个存储网络。这种结构是与传统的客户/服务器的集中控制模式相对应的。本文中的P2P专指“功能对等的节点组织方式”，而非专指一般用户桌面机所组成的系统。P2P文件共享系统一般指由用户桌面机组成的P2P网络，利用用户桌面机之间的带宽来解决服务器性能瓶颈问题。然而，P2P存储系统既可以是完全由服务器节点以对等方式组成，又可以是完全由用户桌面机组成，也可以是服务器与桌面机共同以对等的方式组成的存储系统。可以说，P2P技术既可用来组织专业的大型存储服务，也可以用来组织闲散的桌面机资源形成互助存储网络。综上所述，只要以功能对等的方式组织起来的存储系统均属于P2P存储系统。由于采用对等互连的技术，P2P存储系统相比传统的存储系统有如下优点：不依赖中央控制，系统自然具有高扩展性，且不存在单点性能瓶颈问题；各个节点功能对等，使得整个系统在缺失任意节点后仍能正常工作，也即有高容错性；高扩展性和高容错性进而使得利用廉价机群搭建大规模高性能存储服务成为可能；由于没有也没法进行中央控制，P2P存储系统能够极大减小存储系统总的拥有开销（TCO,TotalCostofOwnership）[1]；由桌面机组成的P2P存储系统，每个节点将可以利用互联网的边界带宽资源存储数据，极大的提高传输速度。虽然P2P系统有与生俱来的高容错潜力，但P2P系统中每个节点都可能随时暂时或永久的离开系统，这使得构建P2P存储系统极富挑战。系统中的节点均负责存储数据，一旦某节点暂时离开，存在其上的数据就将暂时不可访问，而节点的永久离开更会造成数据的丢失。因此，如何提供数据的持久存储，屏蔽这些系统错误成为近年来P2P存储领域的研究热点。本文第1节介绍构建P2P存储系统及提供数据持久存储的基本技术，并将系统按动态性进行分类；第2节给出整个P2P存储系统的研究框架，并介绍系统及相关研究的发展历史；第3节分别介绍各重要的存储系统，讨论它们的技术特点；第4节介绍和讨论目前前沿的研究结果；第5节总结全文。1P2P持久存储的基本技术及系统分类本节将以构建一个简单的抽象P2P存储系统为目标，简要而直观的介绍组成系统所需要的结构化覆盖网络及保证数据持久存储的相关技术，昀后本节按系统所适应的目标环境将系统分类。这里要强调的是，本文中所指的P2P文件存储系统均指“基于结构化P2P覆盖网络”的存储系统。这也是目前学术界的默认观点。因此，本节将首先介绍一个简单的结构化覆盖网络，并在其基础之上介绍存储相关的基本技术。1.1结构化P2P覆盖网络基本概念结构化P2P覆盖网络是一种维护节点之间在应用层上互联的组织方法。它按照一定的逻辑拓扑结构将系统中的节点互连起来，并通过路由消息使得系统中任意两个节点可以互相通信。在有节点动态加入和退出的情况下，结构化P2P覆盖网络要能够保证节点之间的互连性。为了让节点互相认识，首先需要为每个节点命名。结构化P2P网络中节点的名字一般是一个名字空间内的一个数值，例如Chord路由算法[2]的名字空间是一个环形，如图1所示。当有节点加入系统时，节点随机选择一个环上的位置作为自己的标识符（ID），如图1左边一个节点加入并以0作为自己的ID，而右图中则有更多的节点加入了这个系统。每个节点获得了一个唯一标识后，就可以定义节点之间的互连关系，例如图1的网络中可以定义每个节点认识与其在环上左右相邻的两个节点，也即知道它们的IP地址。这样，图1中的节点0就认识节点13和节点3，而节点3就认识节点0和节点6，进而每个节点都可以通过自己的邻居间接的认识网络中所有其它的节点。当有新节点加入时，也需要继续保持这一规则。例如，一个节点要以2这个ID加入系统，那么它可962能先联系到了节点13，而节点13就会介绍它认识节点0和节点3；节点0和节点3得知有节点2要加入后，会更新自己的路由表，让节点2成为自己的新邻居，以使得这个环形拓扑继续保持。同样，覆盖网络也要处理节点离开的情况。离开处理相对复杂，这里不做介绍，可以参考Chord[2]、Tapestry[3]、CAN[4]、Pastry[5]和Kademlia[6]等路由算法。Fig.1NamespaceofstructuredoverlaynetworkFig.2Storeoperationonastructuredoverlaynetwork图1结构化覆盖网络的名字空间图2结构化覆盖网络上的存储操作要在这样的一个覆盖网路上存储数据，我们需要为数据命名，以便可以用名字取回存储的数据。数据的名字一般也是该网络名字空间里面的一个值，例如图2中3号节点将文件A命名为7。存储时，我们希望数据存在以7为ID的节点上，以便读取时用文件名字定位。但不幸的是，7号位置并没有物理节点。因此，我们需要定义一个区域负责制，也即谁负责那些还没有物理节点位置。我们可以简单定义为，排在这个位置之后的昀近的一个节点负责这个位置。这样，图2中负责位置7的就是9号节点。节点3可以通过自己的邻居认识到节点9，并将数据昀终存储在9号节点上。当然，如果后来有8号节点加入网络，根据前面负责制的定义，A文件就应该移动到8号节点上。这将造成不小的带宽消耗，下一小节会讨论这个问题的解决方案。结构化P2P覆盖网络是一个独立的研究领域，近年来发展出了不少优秀的路由算法。它们虽然都是以分割ID空间和空间分区管理为核心思想，但其拓扑结构却多种多样。有代表性的包括，分割矩形空间的CAN[4]，超立方体结构的HyperCup[7]和基于抑或距离关系的Kademlia[6]等。本小节给出的只是一个简化版本的覆盖网络，其中一个节点只认识其左右两个邻居。这样势必造成节点查找任意ID位置的负责节点时，需要通过过多的邻接关系才能查到，效率非常低。为了解决这个问题，我们当然可以定义每个节点可以认识网络中所有其它的节点。这样，节点的任意查找都可以根据本地信息一次定位。但这种方案也增加了节点维护应用层路由表的负担。因此，一般的P2P覆盖网络都采用一种折衷的方案，让每个节点认识网络中O(logN)个节点，这样可以使查找效率达到O(logN)，其中N为网络中节点总数。优化的具体方法，请参考具体路由算法文章。P2P覆盖网络的另一个主要研究点是如何让网络在高抖动情况下（节点频繁加入和退出）保持正确的连通性。此研究方向，本文不展开讨论。在后续讨论中，我们简单假设覆盖网络能够保证节点之间的正确互连。1.2面向数据持久存储的相关技术介绍在一个P2P覆盖网络中，我们一般假设系统中有海量的节点且每个节点可以自由加入和退出系统。因此，临时和永久的节点失效相比于传统系统将多很多。这样，一个P2P存储系统必须要用一定的策略屏蔽这些节点失效，保证数据的持久存储。本小节，我们将介绍其基本的方法。1.2.1数据冗余方案：副本与纠删码对要存储的数据做一定的冗余，是在有节点失效情况下保证数据持久性的昀基本和必要的手段。没有冗余的数据，节点退出后，其上的数据将必然无法恢复。在P2P存储系统中，目前研究主要讨论两种冗余方法，完全副本冗余和纠删码冗余。完全副本冗余，顾名思义就是保存多个要存储的数据的完整副本。纠删码是指将要存储的数据先切分为m个部分，然后通过编田敬等:P2P持久存储研究综述963码算法变换为n（nm）个部分，其中任意t（t=m