摘 要：在基于節(jié)點分級的對等網(wǎng)絡(luò)路由定位算法SP_Route的基礎(chǔ)上實現(xiàn)一個分布式存儲系統(tǒng)。通過采用可擴展的體系結(jié)構(gòu)、穩(wěn)定的通信協(xié)議、通信機制，簡明的文件的組織和節(jié)點構(gòu)造方式，在物理網(wǎng)絡(luò)上疊加一個P2P網(wǎng)絡(luò)層。將各個節(jié)點貢獻(xiàn)的物理上分布的存儲資源連接成對用戶透明的文件存儲系統(tǒng)。該系統(tǒng)能快速地搜索文件和進(jìn)行路由定位，能為用戶提供較穩(wěn)定的存儲服務(wù)。

關(guān)鍵詞：對等網(wǎng)絡(luò)；文件存儲；分布式存儲系統(tǒng)；定位算法

中圖分類號：TP391.9 文獻(xiàn)標(biāo)識碼：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］為代表的結(jié)構(gòu)化P2P網(wǎng)絡(luò)得到人們的很大關(guān)注。這種網(wǎng)絡(luò)具有一系列優(yōu)點，例如分散控制、自組織以及較強的容錯能力等。因此，很多人試圖在結(jié)構(gòu)化P2P網(wǎng)絡(luò)上構(gòu)建基于P2P（PeertoPeer，對等網(wǎng)絡(luò)）的文件存儲系統(tǒng)。P2P存儲系統(tǒng)，是指存儲節(jié)點以一種功能對等的方式組成的一個存儲網(wǎng)絡(luò)^［5］?；赑2P的存儲系統(tǒng)可以看作是提供存儲服務(wù)的全球應(yīng)用系統(tǒng)，它的目標(biāo)在于利用P2P網(wǎng)絡(luò)中的眾多節(jié)點聯(lián)合提供超大容量、高可靠、高可用的數(shù)據(jù)存儲服務(wù)。系統(tǒng)的用戶散落在世界各地，每個成員均可貢獻(xiàn)數(shù)據(jù)和計算資源^［6］，系統(tǒng)再將這些眾多的零星資源集成為一個大的資源庫，為用戶所使用。與傳統(tǒng)的客戶機/服務(wù)器存儲技術(shù)及其他形式的分布式存儲系統(tǒng)相比，基于P2P技術(shù)的存儲系統(tǒng)數(shù)據(jù)的搜索和定位以及路由效率更高^［7］，能夠極大地減小存儲系統(tǒng)的總擁有開銷^［8］。

本文基于作者提出的SP_Route算法^［9］實現(xiàn)了一個分布式存儲系統(tǒng)。該系統(tǒng)通過在物理網(wǎng)絡(luò)之上疊加一個SP_Route網(wǎng)絡(luò)層，將大量分散的節(jié)點連接成一個邏輯網(wǎng)絡(luò)，利用每個節(jié)點貢獻(xiàn)出來的資源，組成一個對用戶透明的分布式存儲系統(tǒng)。系統(tǒng)采用可擴展的體系結(jié)構(gòu)，將來還可以加入用戶管理、副本拷貝、訪問緩存等功能。

1 體系結(jié)構(gòu)

系統(tǒng)由地理上分布的多個節(jié)點構(gòu)成，每個節(jié)點都是擁有存儲空間的獨立計算機，節(jié)點之間以P2P疊加網(wǎng)絡(luò)的方式組織。

從系統(tǒng)功能的角度可以把系統(tǒng)分為5層：應(yīng)用層、擴展層、數(shù)據(jù)層、路由層、物理層。

應(yīng)用層 系統(tǒng)用戶通過用戶界面直接與應(yīng)用層交互。通過應(yīng)用層提供的文件服務(wù)接口，用戶看到的將是一個虛擬的海量存儲空間，用戶可以上傳、下載、共享自己的文件，也可以訪問由其他用戶上傳的文件。由于應(yīng)用層屏蔽了下層路由、復(fù)制、傳輸?shù)燃夹g(shù)細(xì)節(jié)，用戶可以像使用本地存儲系統(tǒng)一樣訪問分布式存儲空間。在應(yīng)用層中，可以利用系統(tǒng)下層提供的文件存儲共享功能，開發(fā)各種應(yīng)用。

擴展層 擴展層旨在提供一些除了基礎(chǔ)路由以外的其他服務(wù)，包括用戶管理、副本管理、緩存，安全機制等，使得系統(tǒng)可以更加安全、可靠、易用。它在基本路由和數(shù)據(jù)服務(wù)的基礎(chǔ)上，讓系統(tǒng)中各個節(jié)點間的聯(lián)合更加緊密，讓用戶感覺不到底層分布的網(wǎng)絡(luò)。

數(shù)據(jù)層 數(shù)據(jù)層通過轉(zhuǎn)移節(jié)點間的負(fù)載，控制節(jié)點簇的規(guī)模，以及在節(jié)點離開，失效情況下自適應(yīng)的修復(fù)路由，使得系統(tǒng)具有負(fù)載平衡和容錯處理功能，保證向用戶提供穩(wěn)定的服務(wù)。

路由層 路由層使用SP_Route算法，建立節(jié)點地址空間與文件地址空間以及二者之間的映射關(guān)系，將系統(tǒng)中松散的節(jié)點結(jié)合到一起，形成一個二層的分布式的P2P疊加網(wǎng)絡(luò)。主干網(wǎng)絡(luò)之間采用基于DHT（Distributed Hash Table， 分布式哈希表）的路由定位機制^［10］，其他節(jié)點通過超級節(jié)點的轉(zhuǎn)發(fā)，在有限跳數(shù)內(nèi)能夠找到目標(biāo)文件。

物理層 物理層由地理上分布的具有存儲空間和計算能力的計算機即系統(tǒng)節(jié)點以及連接它們之間的底層網(wǎng)絡(luò)構(gòu)成。各節(jié)點貢獻(xiàn)自己的存儲空間和計算資源，是構(gòu)成網(wǎng)絡(luò)的基本元素，是文件存儲的實體，是路由轉(zhuǎn)發(fā)的中間節(jié)點，物理層是整個系統(tǒng)的物理基礎(chǔ)。

2 路由算法

SP_Route算法是以Pastry為基礎(chǔ)，通過引入節(jié)點分級的概念形成的一種基于DHT的P2P網(wǎng)絡(luò)路由定位算法。

它通過將節(jié)點分成超級節(jié)點和普通節(jié)點2級，在系統(tǒng)中形成以超級節(jié)點為中心的子網(wǎng)，網(wǎng)絡(luò)中的節(jié)點以子網(wǎng)為單位組織路由。子網(wǎng)與子網(wǎng)之間通過類似Pastry的根據(jù)向最相近標(biāo)識符前綴轉(zhuǎn)移方式進(jìn)行路由定位，子網(wǎng)內(nèi)普通節(jié)點則通過超級節(jié)點轉(zhuǎn)發(fā)路由信息。由于采取了“能者多勞”的策略，讓超級節(jié)點承擔(dān)更多的負(fù)載，避免讓所有的節(jié)點直接參加主干網(wǎng)絡(luò)的路由，使得系統(tǒng)能有效地避免“單點瓶頸”問題。同時，由于普通節(jié)點在加入系統(tǒng)時不需要構(gòu)造復(fù)雜的路由表，使得節(jié)點加入時的耗費和節(jié)點加入離開對系統(tǒng)的影響大大降低。算法通過節(jié)點分裂和節(jié)點遷移的辦法實現(xiàn)子網(wǎng)間的負(fù)載平衡，通過控制子網(wǎng)的規(guī)模，使得超級節(jié)點的負(fù)載基本保持平衡。同時，通過一種“ID欺騙”的策略在子網(wǎng)內(nèi)通過自適應(yīng)的副本拷貝來轉(zhuǎn)移系統(tǒng)中的訪問熱點，使得算法能應(yīng)對大量的訪問同時集中于熱點的情況。算法的詳細(xì)描述見參考文獻(xiàn)［9］。

3 底層協(xié)議與通信機制

3.1 通信機制

SP_Route是一個工作在應(yīng)用層的疊加網(wǎng)絡(luò)，其底層協(xié)議這里使用TCP/UDP協(xié)議實現(xiàn)。在對等網(wǎng)絡(luò)路由和維護(hù)的過程中，節(jié)點之間需要發(fā)送大量的路由消息。這些路由消息通信量并不大，但是數(shù)量比較多，如果采用TCP協(xié)議，將引起大量的連接不斷的建立和釋放，通信效率不高。而UDP協(xié)議不需要預(yù)先建立連接，也不需要同時維護(hù)多個連接，適合多點之間交叉?zhèn)鬏敂?shù)據(jù)，特別適合對等網(wǎng)絡(luò)之間的通信。所以在傳遞路由信息時，主要采用UDP通信，在傳送大文件時為了保證文件傳輸?shù)目煽啃?，采用TCP通信。由于UDP在通信過程中可能會丟失數(shù)據(jù)包，所以在應(yīng)用層設(shè)計了通信規(guī)則，實現(xiàn)確認(rèn)與重傳，加強可靠性。

該規(guī)則參考TCP協(xié)議，采用編號實現(xiàn)，編號使用節(jié)點ID和節(jié)點消息序號來產(chǎn)生，保證整個系統(tǒng)惟一，因此省去了TCP建立連接時三次握手來協(xié)商編號的麻煩，另外由于在應(yīng)用層發(fā)送數(shù)據(jù)是基于消息包的發(fā)送，不像TCP的流式傳輸，所以也不存在順序問題；發(fā)送方發(fā)送數(shù)據(jù)報文后，等待確認(rèn)報文，確認(rèn)到達(dá)后認(rèn)為對方已經(jīng)收到發(fā)送的報文，若超時收不到確認(rèn)，則認(rèn)為發(fā)送的報文丟失，重傳該報文，如果連續(xù)N次收不到確認(rèn)報文，則停止發(fā)送，返回出錯信息。對確認(rèn)報文不再進(jìn)行確認(rèn)。

這里采用下列方法做到確認(rèn)與重傳：在每個節(jié)點有1個接收緩沖區(qū)和1個發(fā)送緩沖區(qū)。當(dāng)發(fā)送1個數(shù)據(jù)報文時，就將該數(shù)據(jù)報文放入發(fā)送緩沖區(qū)，收到確認(rèn)后，就將該數(shù)據(jù)報文從發(fā)送緩沖區(qū)中刪除。接收緩沖區(qū)采用隊列結(jié)構(gòu)，收到一個報文時，若接收緩沖區(qū)不滿，則將其加到隊尾，如果接收緩沖區(qū)滿了，就從隊首刪除一個報文，再將收到的報文加到隊尾；這樣做的目的是為了防止這種情況發(fā)生：接收方收到數(shù)據(jù)報文并發(fā)出確認(rèn)報文，但確認(rèn)報文丟失，發(fā)送方收不到確認(rèn)報文，認(rèn)為發(fā)送的數(shù)據(jù)報文丟失，將該數(shù)據(jù)報文重傳1次，這時接收方可以根據(jù)接收緩沖來進(jìn)行重復(fù)丟棄處理。由于隊列長度有限，不能保證完成所有的重復(fù)丟棄處理，例如當(dāng)接收的數(shù)據(jù)報文加入接收緩沖后，從隊尾移動到隊首，然后被刪除，在這以后重發(fā)的該數(shù)據(jù)報文又到來，就不能進(jìn)行重復(fù)丟棄處理。但由于隊列每次都是刪除其中最早收到的一個數(shù)據(jù)報文，選擇一個合適的隊列長度，就能將出現(xiàn)重復(fù)丟棄處理出錯的概率降到很小。

3.2 通信協(xié)議

為了實現(xiàn)SP_Route的路由功能，并且保證報文的穩(wěn)定傳輸，首先定義一套節(jié)點間的通信協(xié)議?；镜膮f(xié)議報文分為2種，一種為數(shù)據(jù)報報文，一種為確認(rèn)報文。同時把各種命令報文以及應(yīng)答報文的公共部分提取出來，作為通用協(xié)議報文的報頭，而把各種具體的命令協(xié)議包含在報文的數(shù)據(jù)部分。

報文的類型由報文的第一個字節(jié)標(biāo)識，若報文的第一個字節(jié)為DATA，則為數(shù)據(jù)報文，用來傳遞路由信息；如果報文的第一個字節(jié)為ACK，則為確認(rèn)報文，用來確認(rèn)給定序號的報文已經(jīng)收到。

報文序號由發(fā)送報文的節(jié)點ID加上每個節(jié)點的序號產(chǎn)生器產(chǎn)生，序號產(chǎn)生器在0~4 000的范圍內(nèi)按序產(chǎn)生序號，由于一般來說，系統(tǒng)中不可能同時有屬于一個節(jié)點的4 000個報文，所以采用這種方法可以保證系統(tǒng)中報文序號的惟一性。每個報文在系統(tǒng)中都有一個惟一的標(biāo)識符稱為Key值，報文Key值是節(jié)點轉(zhuǎn)發(fā)報文的依據(jù)，節(jié)點總是在自己的路由表中找與Key值在ID空間中最接近的節(jié)點作為報文的下一跳節(jié)點。報文的Key值依據(jù)報文功能的不同而有不同的產(chǎn)生方法，當(dāng)節(jié)點加入時，待加入節(jié)點的節(jié)點ID即為報文的key值，當(dāng)查詢文件時，報文把文件名的經(jīng)過哈希變換得出的值作為報文的key值。報文還記錄一些其他的信息，包括上一跳地址，源地址和報文長度等。

4 文件組織與節(jié)點結(jié)構(gòu)

系統(tǒng)將文件看作對象，每個文件擁有1個全局標(biāo)識符稱為FID（文件標(biāo)識符），文件的FID是通過對文件名進(jìn)行哈希變換得到

在節(jié)點中，文件存放在指定的目錄中，每個節(jié)點保留一個它所存儲的文件的索引。索引以鏈表的方式組織，記錄文件的FID、名稱、存放路徑、大小、關(guān)鍵字、描述信息等。

當(dāng)每個節(jié)點加入系統(tǒng)時，指定一個或多個文件目錄，并標(biāo)明存儲空間的大小，作為這個節(jié)點向系統(tǒng)貢獻(xiàn)的資源。一個節(jié)點的路由信息由節(jié)點基礎(chǔ)信息、路由信息、存儲空間信息和文件索引信息4部分組成。超級節(jié)點和普通節(jié)點除路由信息不同外，其他部分具有相同的結(jié)構(gòu)。節(jié)點基礎(chǔ)信息包含了文件的各項基本信息，包括節(jié)點在系統(tǒng)中的節(jié)點ID，節(jié)點在網(wǎng)絡(luò)中的IP地址，節(jié)點加入系統(tǒng)的時間，以及節(jié)點的一些硬件信息包括主頻、存儲空間、網(wǎng)絡(luò)帶寬等。節(jié)點每一項路由信息都由若干個<節(jié)點ID，IP地址>對組成，例如組成路由信息中的一項。存儲空間信息是一個列表，它包含節(jié)點向系統(tǒng)所共享的所有空間的信息。其中每一項都指明空間路徑、空間大小、剩余的存儲空間、存儲文件的數(shù)目。系統(tǒng)中的文件只能存儲在這些指定的空間中，并且不能超過允許的大小。文件索引信息包含了所有系統(tǒng)存儲在節(jié)點上的文件信息，包括文件的ID、文件名稱，文件大小、存儲目錄、文件描述等。不包含在索引中的文件將被認(rèn)為是本地的文件。當(dāng)查詢文件請求到達(dá)節(jié)點時，節(jié)點直接從索引中查找是否包含被檢索的文件信息。

5 結(jié) 語

本文介紹了基于SP_Route實現(xiàn)的一個分布式存儲系統(tǒng)。系統(tǒng)采用可擴展的體系結(jié)構(gòu)，通過在物理網(wǎng)絡(luò)上疊加一個P2P網(wǎng)絡(luò)層，將各個節(jié)點貢獻(xiàn)的物理上分布的存儲資源連接成對用戶透明的文件存儲系統(tǒng)，系統(tǒng)支持文件存儲、文件查詢，文件下載等功能，能為用戶提供較穩(wěn)定的存儲服務(wù)。

參 考 文 獻(xiàn)

［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，F(xiàn)rancis 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］.軟件學(xué)報，2007(6):1 3791 399.

［6］余敏，李戰(zhàn)懷，張龍波.P2P數(shù)據(jù)管理［J］.軟件學(xué)報，2006(8):1 7171 730.

［7］徐非，楊廣文，鞠大鵬.基于PeertoPeer的分布式存儲系統(tǒng)設(shè)計［J］.軟件學(xué)報，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網(wǎng)絡(luò)的路由與定位模型研究［D］.南京:解放軍理工大學(xué)，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年出生，湖南桃江人，助理工程師，碩士。主要從事分布式系統(tǒng)、計算機網(wǎng)絡(luò)方面的研究。

張 強 男，1974年出生，江蘇南京人，工程師，本科。主要從事計算機網(wǎng)絡(luò)方面的研究。

姜志寬 男，1952年出生，江蘇南通人，研究員，本科。主要從事情報信息方面的研究。