基于對(duì)等網(wǎng)絡(luò)的分布式存儲(chǔ)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

2 路由算法

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

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

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

3.1 通信機(jī)制

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

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

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

3.2 通信協(xié)議

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

本文介紹了基于SP_Route實(shí)現(xiàn)的一個(gè)分布式存儲(chǔ)系統(tǒng)。系統(tǒng)采用可擴(kuò)展的體系結(jié)構(gòu)，通過(guò)在物理網(wǎng)絡(luò)上疊加一個(gè)P2P網(wǎng)絡(luò)層，將各個(gè)節(jié)點(diǎn)貢獻(xiàn)的物理上分布的存儲(chǔ)資源連接成對(duì)用戶(hù)透明的文件存儲(chǔ)系統(tǒng)，系統(tǒng)支持文件存儲(chǔ)、文件查詢(xún)，文件下載等功能，能為用戶(hù)提供較穩(wěn)定的存儲(chǔ)服務(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持久存儲(chǔ)研究［J］.軟件學(xué)報(bào)，2007(6):1 3791 399.

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

［7］徐非，楊廣文，鞠大鵬.基于PeertoPeer的分布式存儲(chǔ)系統(tǒng)設(shè)計(jì)［J］.軟件學(xué)報(bào)，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.

作者簡(jiǎn)介 龔星耀 男，1981年出生，湖南桃江人，助理工程師，碩士。主要從事分布式系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)方面的研究。

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

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