基于对等网络的分布式存储系统的设计与实现

摘 要：在基于节点分级的对等网络路由定位算法SP_Route的基础上实现一个分布式存储系统。通过采用可扩展的体系结构、稳定的通信协议、通信机制，简明的文件的组织和节点构造方式，在物理网络上叠加一个P2P网络层。将各个节点贡献的物理上分布的存储资源连接成对用户透明的文件存储系统。该系统能快速地搜索文件和进行路由定位，能为用户提供较稳定的存储服务。

关键词：对等网络；文件存储；分布式存储系统；定位算法

中图分类号：TP391.9 文献标识码：B 文章编号：1004373X(2008)1611603

Design and Implementation of Distributed Storage System Based on PeertoPeer Network

GONG Xingyao,ZHANG Qiang,JIANG Zhikuan

(Center for Disease Control and Prevention of Nanjing Command,Nanjing,210002,China)

Abstract：To implement a distribute storage system based on a routing and locating model SP_Route,which are designed for peertopeer network.By adopting extensible architecture,stable communication mechanism,communication protocol,simple way of organizing file and building node to append an overlay peertopeer network on the physics network.The system integrated the distributed storage resource as a whole storage system which is apparent to users.The storage system can search file quickly,route and locate nodes efficiently and provide stable file access services to the users.

Keywords：peertopeer network；file storage；distributed storage system;location algorithm

收稿日期：20080328 近年来，以Pastry［1,2］，Chord［3］和CAN［4］为代表的结构化P2P网络得到人们的很大关注。这种网络具有一系列优点，例如分散控制、自组织以及较强的容错能力等。因此,很多人试图在结构化P2P网络上构建基于P2P（PeertoPeer，对等网络）的文件存储系统。P2P存储系统,是指存储节点以一种功能对等的方式组成的一个存储网络［5］。基于P2P的存储系统可以看作是提供存储服务的全球应用系统，它的目标在于利用P2P网络中的众多节点联合提供超大容量、高可靠、高可用的数据存储服务。系统的用户散落在世界各地，每个成员均可贡献数据和计算资源［6］，系统再将这些众多的零星资源集成为一个大的资源库，为用户所使用。与传统的客户机/服务器存储技术及其他形式的分布式存储系统相比，基于P2P技术的存储系统数据的搜索和定位以及路由效率更高［7］，能够极大地减小存储系统的总拥有开销［8］。

本文基于作者提出的SP_Route算法［9］实现了一个分布式存储系统。该系统通过在物理网络之上叠加一个SP_Route网络层，将大量分散的节点连接成一个逻辑网络，利用每个节点贡献出来的资源，组成一个对用户透明的分布式存储系统。系统采用可扩展的体系结构，将来还可以加入用户管理、副本拷贝、访问缓存等功能。

1 体系结构

系统由地理上分布的多个节点构成，每个节点都是拥有存储空间的独立计算机，节点之间以P2P叠加网络的方式组织。

从系统功能的角度可以把系统分为5层：应用层、扩展层、数据层、路由层、物理层。

应用层 系统用户通过用户界面直接与应用层交互。通过应用层提供的文件服务接口，用户看到的将是一个虚拟的海量存储空间，用户可以上传、下载、共享自己的文件，也可以访问由其他用户上传的文件。由于应用层屏蔽了下层路由、复制、传输等技术细节，用户可以像使用本地存储系统一样访问分布式存储空间。在应用层中，可以利用系统下层提供的文件存储共享功能，开发各种应用。

扩展层 扩展层旨在提供一些除了基础路由以外的其他服务，包括用户管理、副本管理、缓存，安全机制等，使得系统可以更加安全、可靠、易用。它在基本路由和数据服务的基础上，让系统中各个节点间的联合更加紧密，让用户感觉不到底层分布的网络。

数据层 数据层通过转移节点间的负载，控制节点簇的规模，以及在节点离开，失效情况下自适应的修复路由，使得系统具有负载平衡和容错处理功能，保证向用户提供稳定的服务。

路由层 路由层使用SP_Route算法，建立节点地址空间与文件地址空间以及二者之间的映射关系，将系统中松散的节点结合到一起，形成一个二层的分布式的P2P叠加网络。主干网络之间采用基于DHT（Distributed Hash Table， 分布式哈希表）的路由定位机制［10］，其他节点通过超级节点的转发，在有限跳数内能够找到目标文件。

物理层 物理层由地理上分布的具有存储空间和计算能力的计算机即系统节点以及连接它们之间的底层网络构成。各节点贡献自己的存储空间和计算资源，是构成网络的基本元素，是文件存储的实体，是路由转发的中间节点，物理层是整个系统的物理基础。

2 路由算法

SP_Route算法是以Pastry为基础，通过引入节点分级的概念形成的一种基于DHT的P2P网络路由定位算法。

它通过将节点分成超级节点和普通节点2级，在系统中形成以超级节点为中心的子网，网络中的节点以子网为单位组织路由。子网与子网之间通过类似Pastry的根据向最相近标识符前缀转移方式进行路由定位，子网内普通节点则通过超级节点转发路由信息。由于采取了“能者多劳”的策略，让超级节点承担更多的负载，避免让所有的节点直接参加主干网络的路由，使得系统能有效地避免“单点瓶颈”问题。同时，由于普通节点在加入系统时不需要构造复杂的路由表，使得节点加入时的耗费和节点加入离开对系统的影响大大降低。算法通过节点分裂和节点迁移的办法实现子网间的负载平衡，通过控制子网的规模，使得超级节点的负载基本保持平衡。同时，通过一种“ID欺骗”的策略在子网内通过自适应的副本拷贝来转移系统中的访问热点，使得算法能应对大量的访问同时集中于热点的情况。算法的详细描述见参考文献［9］。

3 底层协议与通信机制

3.1 通信机制

SP_Route是一个工作在应用层的叠加网络，其底层协议这里使用TCP/UDP协议实现。在对等网络路由和维护的过程中，节点之间需要发送大量的路由消息。这些路由消息通信量并不大，但是数量比较多，如果采用TCP协议，将引起大量的连接不断的建立和释放，通信效率不高。而UDP协议不需要预先建立连接，也不需要同时维护多个连接，适合多点之间交叉传输数据，特别适合对等网络之间的通信。所以在传递路由信息时，主要采用UDP通信，在传送大文件时为了保证文件传输的可靠性，采用TCP通信。由于UDP在通信过程中可能会丢失数据包，所以在应用层设计了通信规则，实现确认与重传，加强可靠性。

该规则参考TCP协议，采用编号实现，编号使用节点ID和节点消息序号来产生，保证整个系统惟一，因此省去了TCP建立连接时三次握手来协商编号的麻烦，另外由于在应用层发送数据是基于消息包的发送，不像TCP的流式传输，所以也不存在顺序问题；发送方发送数据报文后，等待确认报文，确认到达后认为对方已经收到发送的报文，若超时收不到确认，则认为发送的报文丢失，重传该报文，如果连续N次收不到确认报文，则停止发送，返回出错信息。对确认报文不再进行确认。

这里采用下列方法做到确认与重传：在每个节点有1个接收缓冲区和1个发送缓冲区。当发送1个数据报文时，就将该数据报文放入发送缓冲区，收到确认后，就将该数据报文从发送缓冲区中删除。接收缓冲区采用队列结构，收到一个报文时，若接收缓冲区不满，则将其加到队尾，如果接收缓冲区满了，就从队首删除一个报文，再将收到的报文加到队尾；这样做的目的是为了防止这种情况发生：接收方收到数据报文并发出确认报文，但确认报文丢失，发送方收不到确认报文，认为发送的数据报文丢失，将该数据报文重传1次，这时接收方可以根据接收缓冲来进行重复丢弃处理。由于队列长度有限，不能保证完成所有的重复丢弃处理，例如当接收的数据报文加入接收缓冲后，从队尾移动到队首，然后被删除，在这以后重发的该数据报文又到来，就不能进行重复丢弃处理。但由于队列每次都是删除其中最早收到的一个数据报文，选择一个合适的队列长度，就能将出现重复丢弃处理出错的概率降到很小。

3.2 通信协议

为了实现SP_Route的路由功能，并且保证报文的稳定传输，首先定义一套节点间的通信协议。基本的协议报文分为2种，一种为数据报报文，一种为确认报文。同时把各种命令报文以及应答报文的公共部分提取出来，作为通用协议报文的报头，而把各种具体的命令协议包含在报文的数据部分。

报文的类型由报文的第一个字节标识，若报文的第一个字节为DATA，则为数据报文，用来传递路由信息；如果报文的第一个字节为ACK，则为确认报文，用来确认给定序号的报文已经收到。

报文序号由发送报文的节点ID加上每个节点的序号产生器产生，序号产生器在0~4 000的范围内按序产生序号，由于一般来说，系统中不可能同时有属于一个节点的4 000个报文，所以采用这种方法可以保证系统中报文序号的惟一性。每个报文在系统中都有一个惟一的标识符称为Key值，报文Key值是节点转发报文的依据，节点总是在自己的路由表中找与Key值在ID空间中最接近的节点作为报文的下一跳节点。报文的Key值依据报文功能的不同而有不同的产生方法，当节点加入时，待加入节点的节点ID即为报文的key值，当查询文件时，报文把文件名的经过哈希变换得出的值作为报文的key值。报文还记录一些其他的信息，包括上一跳地址，源地址和报文长度等。

4 文件组织与节点结构

系统将文件看作对象，每个文件拥有1个全局标识符称为FID（文件标识符），文件的FID是通过对文件名进行哈希变换得到

在节点中，文件存放在指定的目录中，每个节点保留一个它所存储的文件的索引。索引以链表的方式组织，记录文件的FID、名称、存放路径、大小、关键字、描述信息等。

当每个节点加入系统时，指定一个或多个文件目录，并标明存储空间的大小，作为这个节点向系统贡献的资源。一个节点的路由信息由节点基础信息、路由信息、存储空间信息和文件索引信息4部分组成。超级节点和普通节点除路由信息不同外，其他部分具有相同的结构。节点基础信息包含了文件的各项基本信息，包括节点在系统中的节点ID，节点在网络中的IP地址，节点加入系统的时间，以及节点的一些硬件信息包括主频、存储空间、网络带宽等。节点每一项路由信息都由若干个对组成，例如组成路由信息中的一项。存储空间信息是一个列表，它包含节点向系统所共享的所有空间的信息。其中每一项都指明空间路径、空间大小、剩余的存储空间、存储文件的数目。系统中的文件只能存储在这些指定的空间中，并且不能超过允许的大小。文件索引信息包含了所有系统存储在节点上的文件信息，包括文件的ID、文件名称，文件大小、存储目录、文件描述等。不包含在索引中的文件将被认为是本地的文件。当查询文件请求到达节点时，节点直接从索引中查找是否包含被检索的文件信息。

5 结 语

本文介绍了基于SP_Route实现的一个分布式存储系统。系统采用可扩展的体系结构，通过在物理网络上叠加一个P2P网络层，将各个节点贡献的物理上分布的存储资源连接成对用户透明的文件存储系统，系统支持文件存储、文件查询，文件下载等功能，能为用户提供较稳定的存储服务。

参 考 文 献

［1］Rowstron A,Druschel P.Pastry:Scalable,Distributed Object Location and Routing for Large Scale PeertoPeer Systems［C］.Proc.of the IFIP/ACM Int′l Middleware Conf.London:SpringerVerlag,2001:329350.

［2］Rowstron A,Druschel P.PAST:A Largescale,Persistent P2P Storage Utility［C］.In:Proc.of the 8th Workshop on Hot Topics in Operating Systems.New York:ACM Press,2001:7580.

［3］Stoica I,Morris R,Karger D,et al.Chord:A Scalable PeertoPeer Lookup Service for Internet Applications［C］.In:Proc.of the 2001 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications (SigComm).New York:ACM Press,2001:149160.

［4］Ratnasamy S,Francis P,Handley M,et al.A Scalable Contentaddressable Network［C］.In:Proc.of the 2001 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications (SigComm).New York:ACM Press,2001:161172.

［5］田敬，代亚非.P2P持久存储研究［J］.软件学报,2007(6):1 3791 399.

［6］余敏,李战怀,张龙波.P2P数据管理［J］.软件学报,2006(8):1 7171 730.

［7］徐非,杨广文,鞠大鹏.基于PeertoPeer的分布式存储系统设计［J］.软件学报,2004(2):268277.

［8］Zhang Z,Lin S,Jin C.RepStore:A Selfmanaging and Selftuning Storage Backend with Smart Bricks.In:Proc.of the Int′l Conf.on Autonomic Computing.New York:IEEE Computer Society:2004:122129.

［9］龚星耀.基于P2P网络的路由与定位模型研究［D］.南京:理工大学,2006.

［10］Ratnasamy S,Shenker S,Stoica I.Routing Algorithms for DHTs:Some Open Questions［C］.Proc.of the 1st Int′l Workshop on PeertoPeer Systems(IPTPS 2002).Berlin:SpringerVerlag,2002:174179.

作者简介 龚星耀 男，1981年出生，湖南桃江人，助理工程师，硕士。主要从事分布式系统、计算机网络方面的研究。

张 强 男，1974年出生，江苏南京人，工程师，本科。主要从事计算机网络方面的研究。

姜志宽 男，1952年出生，江苏南通人，研究员，本科。主要从事情报信息方面的研究。