劉立芳,侯力元,齊小剛
(1.西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院,西安 710071;2.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,西安 710071)
基于Chord網(wǎng)絡(luò)模型的改進(jìn)數(shù)據(jù)復(fù)制方法
劉立芳1,侯力元1,齊小剛2
(1.西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院,西安 710071;2.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,西安 710071)
根據(jù)現(xiàn)有復(fù)制策略在局部節(jié)點(diǎn)故障時(shí)數(shù)據(jù)查找失敗率高的缺點(diǎn),提出一種針對(duì)Chord網(wǎng)絡(luò)的數(shù)據(jù)復(fù)制方法——Rd-Chord(rearranged replication method based on Chord)。利用離散存儲(chǔ)的方法,將數(shù)據(jù)復(fù)制到Chord覆蓋網(wǎng)根節(jié)點(diǎn)前繼相對(duì)分散的節(jié)點(diǎn)中,即使某個(gè)甚至幾個(gè)區(qū)域節(jié)點(diǎn)全部故障,其他區(qū)域依然有數(shù)據(jù)副本可供使用。同時(shí),為了維護(hù)網(wǎng)絡(luò)結(jié)構(gòu)和key遷移,針對(duì)Rd-Chord提出基礎(chǔ)更新和定期更新2種更新策略。為了驗(yàn)證該方法的優(yōu)越性,通過計(jì)算機(jī)仿真對(duì)前繼復(fù)制、后繼復(fù)制和Rd-Chord方法進(jìn)行了大量的比較實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,Rd-Chord方法能夠解決節(jié)點(diǎn)區(qū)域性故障問題,在保證平均查找效率的前提下,查找失敗率降低了近10%,明顯優(yōu)于其他方法。
P2P網(wǎng)絡(luò);Chord模型;數(shù)據(jù)復(fù)制;區(qū)域性故障
近年來,對(duì)等(peer-to-peer,P2P)網(wǎng)絡(luò)已經(jīng)成為關(guān)注的焦點(diǎn),成為構(gòu)建大規(guī)模分布式應(yīng)用的范例[1]。P2P網(wǎng)絡(luò)是一種分布式網(wǎng)絡(luò),打破了傳統(tǒng)的C/S(client/server)模式,網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)地位都是對(duì)等的,沒有中心化的服務(wù)器,不存在系統(tǒng)瓶頸,每個(gè)節(jié)點(diǎn)既充當(dāng)客戶端又充當(dāng)服務(wù)器,因而具有很高的資源利用率。P2P網(wǎng)絡(luò)分為非結(jié)構(gòu)化和結(jié)構(gòu)化網(wǎng)絡(luò)。以Gnutella為代表的非結(jié)構(gòu)化P2P網(wǎng)絡(luò),不存在目錄服務(wù)器,解決了單點(diǎn)瓶頸問題,不存在單一故障點(diǎn)。然而其缺點(diǎn)也是明顯的:采用洪泛機(jī)制加重了網(wǎng)絡(luò)通信負(fù)擔(dān),其查詢機(jī)制在系統(tǒng)規(guī)模擴(kuò)大時(shí)不具有可擴(kuò)展性;另外,由于查詢報(bào)文被限制在特定的范圍內(nèi),所以并不能保證一定可以找到網(wǎng)絡(luò)中存在的目的數(shù)據(jù)。
結(jié)構(gòu)化P2P網(wǎng)絡(luò)實(shí)現(xiàn)了節(jié)點(diǎn)之間在應(yīng)用層的互連,然而當(dāng)節(jié)點(diǎn)故障時(shí),如何保證數(shù)據(jù)的可用性成為必須要解決的問題。在節(jié)點(diǎn)失效情況下,保證數(shù)據(jù)可用性最基本和必要的手段,就是要對(duì)存儲(chǔ)的數(shù)據(jù)做一定的冗余。沒有冗余的數(shù)據(jù),節(jié)點(diǎn)故障后,其上的數(shù)據(jù)必然無法恢復(fù)。DHT(distributed hash table)網(wǎng)絡(luò)中,需要找到一個(gè)最合適的節(jié)點(diǎn)集合來存放冗余數(shù)據(jù),以達(dá)到最好的數(shù)據(jù)持久性。不適當(dāng)?shù)墓?jié)點(diǎn)組合將可能極大地消耗系統(tǒng)帶寬,甚至威脅系統(tǒng)中數(shù)據(jù)的持久性。例如,將數(shù)據(jù)的多個(gè)副本放在一個(gè)錯(cuò)誤相關(guān)的節(jié)點(diǎn)集合上,即節(jié)點(diǎn)集合中的節(jié)點(diǎn)可能由于區(qū)域斷網(wǎng)或斷電而同時(shí)離線。這樣即便有多個(gè)數(shù)據(jù)副本,也容易出現(xiàn)數(shù)據(jù)不可用的情況。
本文的主要貢獻(xiàn):①針對(duì)現(xiàn)有復(fù)制策略在局部節(jié)點(diǎn)故障時(shí)查找失敗率高的缺點(diǎn),在Chord模型基礎(chǔ)上提出一種數(shù)據(jù)復(fù)制方法——Rd-Chord(rearranged replication method based on Chord)來保證數(shù)據(jù)可用性,并和現(xiàn)有主要數(shù)據(jù)復(fù)制方法進(jìn)行比較。仿真結(jié)果顯示,就解決節(jié)點(diǎn)區(qū)域性故障而言,Rd-Chord在保證平均查找效率的前提下,查找失敗率降低了近10%,遠(yuǎn)遠(yuǎn)優(yōu)于其他方法;②在Rd-Chord的基礎(chǔ)上,為了維護(hù)網(wǎng)絡(luò)結(jié)構(gòu)和key遷移,提出基礎(chǔ)更新和定期更新2種更新策略?;A(chǔ)更新在節(jié)點(diǎn)加入或離開網(wǎng)絡(luò)時(shí)啟用。定期更新機(jī)制被定期觸發(fā),目的在于在動(dòng)蕩環(huán)境下保持復(fù)制因子。
文獻(xiàn)[2]中對(duì)當(dāng)前分布式系統(tǒng)的數(shù)據(jù)存儲(chǔ)方式做了比較,針對(duì)目前分布式存儲(chǔ)系統(tǒng)的不足,以發(fā)展相對(duì)比較成熟的P2P技術(shù)作為存儲(chǔ)結(jié)構(gòu)體系,對(duì)數(shù)據(jù)冗余容錯(cuò)技術(shù)、副本管理機(jī)制、資源的搜索算法做了詳細(xì)的探索與研究。數(shù)據(jù)冗余存儲(chǔ)問題中,在最小化副本數(shù)目和最大化副本命中率之間存在一個(gè)權(quán)衡。副本越多,復(fù)制成本越高,副本命中率也越高,反之亦然。理想的復(fù)制方法是以低成本給用戶提供延遲較低的查詢服務(wù)?,F(xiàn)有復(fù)制方法可以被分為四類:隨機(jī)復(fù)制、ServerEnd復(fù)制、路徑復(fù)制和ClientEnd復(fù)制。隨機(jī)復(fù)制,如文獻(xiàn)[3],將文件復(fù)制到隨機(jī)選擇的節(jié)點(diǎn)中;ServerEnd復(fù)制,如文獻(xiàn)[4-6],將文件復(fù)制到P2P網(wǎng)絡(luò)中文件擁有者附近的節(jié)點(diǎn);路徑復(fù)制,如文獻(xiàn)[7-8],將文件復(fù)制到它查詢路徑路過的所有節(jié)點(diǎn)中。在隨機(jī)復(fù)制、ServerEnd復(fù)制和路徑復(fù)制中,文件查詢直到到達(dá)文件持有者或者副本節(jié)點(diǎn)才停止轉(zhuǎn)發(fā)。隨機(jī)復(fù)制和路徑復(fù)制由于副本數(shù)很多,其中一些副本沒有被很好地利用,會(huì)導(dǎo)致開銷很高。因此,文獻(xiàn)[9]中提出了有效的自適應(yīng)文件復(fù)制算法,該算法是基于路徑復(fù)制改進(jìn)的。在該算法中,某個(gè)文件的查詢流量樞紐為該文件許多查詢路徑相交的節(jié)點(diǎn)。該算法選擇某個(gè)文件查詢流量樞紐和頻繁的請(qǐng)求者為副本節(jié)點(diǎn),在限制副本數(shù)的同時(shí)增加命中率;ClientEnd復(fù)制,如文獻(xiàn)[10-11],將文件復(fù)制到頻繁請(qǐng)求的節(jié)點(diǎn)中,使它們可以不用對(duì)查詢進(jìn)行路由,直接存取文件。然而,由于其他請(qǐng)求者的查詢消息有很低的可能性通過頻繁請(qǐng)求者,ClientEnd不能保證高命中率。在以上副本放置的基礎(chǔ)上,還有數(shù)據(jù)冗余度維護(hù)方法[12]、負(fù)載均衡技術(shù)[13-16]、數(shù)據(jù)一致性維護(hù)等策略[17-21]。
本文主要以ServerEnd復(fù)制[6]的前繼復(fù)制方法為基礎(chǔ),在Chord模型中,將副本存儲(chǔ)在標(biāo)識(shí)符為(rid-2k-1)%·2m,k=1,2,…,r的節(jié)點(diǎn)中,其中,rid為根節(jié)點(diǎn)id,k為副本數(shù)目。
本文根據(jù)現(xiàn)有的數(shù)據(jù)復(fù)制方法,在Chord模型基礎(chǔ)上提出一種在局部節(jié)點(diǎn)故障時(shí)增加數(shù)據(jù)可用性的復(fù)制方法——Rd-Chord方法。
2.1 模型建立
圖1是Chord模型的一個(gè)例子,有6個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)資源集合。其中,keyk被分配給在標(biāo)識(shí)符空間中標(biāo)識(shí)符等于或者大于k的第1個(gè)節(jié)點(diǎn)。該節(jié)點(diǎn)稱為k的后繼,由successor(k)表示。例如,在圖1中,successor(1),successor(2)和successor(3)都是節(jié)點(diǎn)3,則key 1,2和3將會(huì)被存儲(chǔ)在該節(jié)點(diǎn)。Chord用一致性散列,以更高的概率保證節(jié)點(diǎn)間的負(fù)載均衡。為了完成一次lookup(k)操作,查詢沿著Chord環(huán)轉(zhuǎn)發(fā),尋找Finger table中節(jié)點(diǎn)標(biāo)識(shí)符大于或等于k的,最接近節(jié)點(diǎn)標(biāo)識(shí)符的節(jié)點(diǎn)。
圖1 Chord模型Fig.1 Chord model
2.2 改進(jìn)的數(shù)據(jù)復(fù)制方法——Rd-Chord方法
為了利用Chord的查詢路由機(jī)制,前繼復(fù)制方法將副本存儲(chǔ)在持有節(jié)點(diǎn)連續(xù)前繼節(jié)點(diǎn)中,副本存儲(chǔ)較為集中,在節(jié)點(diǎn)區(qū)域性故障時(shí)不能保證數(shù)據(jù)可用性。Rd-Chord同樣將復(fù)制數(shù)據(jù)到持有節(jié)點(diǎn)的前繼節(jié)點(diǎn)中以減少定位被請(qǐng)求數(shù)據(jù)的跳數(shù)。不同的是,為了提高數(shù)據(jù)可用性,并克服數(shù)據(jù)副本存儲(chǔ)集中的缺點(diǎn),Rd-Chord采用離散存儲(chǔ)的方式,將數(shù)據(jù)復(fù)制到Chord覆蓋網(wǎng)(rid-2k-1)%·2m,k=1,2,…,r的節(jié)點(diǎn)中。這樣,副本節(jié)點(diǎn)較為分散,并有規(guī)律可尋,當(dāng)局部副本節(jié)點(diǎn)故障時(shí),其他部分?jǐn)?shù)據(jù)依然可用。
算法1描述了本文提出的數(shù)據(jù)復(fù)制機(jī)制。每個(gè)節(jié)點(diǎn)維護(hù)r-1個(gè)通過計(jì)算得出的副本節(jié)點(diǎn)replicateList。根節(jié)點(diǎn)n將數(shù)據(jù)復(fù)制到每個(gè)屬于replicateList的節(jié)點(diǎn)中。復(fù)制程序通過旨在更新副本key值的updateReplicas過程實(shí)現(xiàn)。該算法每個(gè)節(jié)點(diǎn)在O(n)時(shí)間內(nèi)完成對(duì)副本的復(fù)制。
算法1Rd-Chord復(fù)制方法。
1: n.improvementReplication(k)
2: fori=0 tor-2 do
3:nextReplica=n.replicateList[i];
4:nextReplica.replicatedKeys.put(k);
5: end for
為了更好地理解Rd-Chord,不失一般性,以key 2的復(fù)制為例來進(jìn)一步闡述,如圖2所示。假設(shè)節(jié)點(diǎn)2為根節(jié)點(diǎn),當(dāng)m=1,rid=2,k=4時(shí),副本存儲(chǔ)在(2-21-1)%·24,(2-22-1)%·24,(2-23-1)%·24,(2-24-1)%·24,也就是標(biāo)識(shí)符為1,0,14和10的節(jié)點(diǎn)中。可以看出,副本節(jié)點(diǎn)分布較為分散,數(shù)據(jù)可用性較好。
圖2 基于Chord模型的數(shù)據(jù)復(fù)制Fig.2 Data replication based on Chord model
更新算法用來解決復(fù)制時(shí)機(jī)的問題。有2種情況:①節(jié)點(diǎn)加入或者離開網(wǎng)絡(luò)時(shí),應(yīng)用下面介紹的基礎(chǔ)更新算法對(duì)數(shù)據(jù)進(jìn)行遷移或復(fù)制。每個(gè)數(shù)據(jù)根據(jù)復(fù)制因子對(duì)副本進(jìn)行編號(hào),不能超過副本數(shù)目閾值;②為了應(yīng)對(duì)節(jié)點(diǎn)故障,周期性出發(fā)定期更新策略對(duì)網(wǎng)絡(luò)中的副本數(shù)進(jìn)行探測(cè),以保證每個(gè)數(shù)據(jù)的復(fù)制度。
為了定義一個(gè)有效的P2P數(shù)據(jù)復(fù)制方法,必須考慮到節(jié)點(diǎn)故障的情況。因此,本文會(huì)詳述此后在實(shí)現(xiàn)不同復(fù)制方法時(shí)涉及到的穩(wěn)定算法的不同策略。為了維護(hù)網(wǎng)絡(luò)結(jié)構(gòu)和key遷移,本文提出2種更新策略(算法2),基礎(chǔ)更新和定期更新。該算法同樣在O(n)時(shí)間內(nèi)完成對(duì)網(wǎng)絡(luò)的更新操作。
基礎(chǔ)更新策略在節(jié)點(diǎn)加入或離開網(wǎng)絡(luò)時(shí)啟用。比如說在節(jié)點(diǎn)n離開時(shí),數(shù)據(jù)必須已經(jīng)從節(jié)點(diǎn)n成功遷移到它的前繼n′。這個(gè)過程在改進(jìn)的復(fù)制方法中需要更新successorList。基礎(chǔ)更新算法根據(jù)復(fù)制方法自適應(yīng)的。比如說,在后繼復(fù)制方法中,當(dāng)節(jié)點(diǎn)n離開網(wǎng)絡(luò)時(shí),n的后繼存儲(chǔ)n負(fù)責(zé)的key并更新replicatedKeys列表。
算法2更新算法。
1: n.updateReplicas(k)
2: fori=0 tor-2 do
3: replicaNode = replicaList[i];
4: replicaNode.addReplica(myKeys);
5: end for
6: n.verifReplicas(k)
7: fori=0 toreplicatedKeys.lengthdo
8: root = successor(replicatedKeys[i]);
9: root.verifReplicas(n);
10: end for
11: n.addReplica(keys)
12: n.replicatedKeys.put(keys);
舉一個(gè)簡單的例子,如圖3所示。在節(jié)點(diǎn)n加入系統(tǒng)時(shí)(見圖3a),節(jié)點(diǎn)n獲取ns作為它的后繼,此外,ns將自己負(fù)責(zé)的key分成2部分:kns和kn,kn為所有小于等于節(jié)點(diǎn)nID的key。n從ns復(fù)制,并不考慮副本(見圖3b)。這時(shí),節(jié)點(diǎn)ns收到節(jié)點(diǎn)n的通知,會(huì)把n作為自己的前繼(見圖3c),然后np把n作為自己的后繼,最后,np通知n,讓n把自己作為n的前繼(見圖3d)。
圖3 節(jié)點(diǎn)加入Fig.3 Node to join
節(jié)點(diǎn)離開如圖4所示,假設(shè)節(jié)點(diǎn)n離開系統(tǒng),它的ID在節(jié)點(diǎn)np和ns之間。在離開系統(tǒng)時(shí),節(jié)點(diǎn)n先通知前繼和后繼ns自己即將離開,告訴np自己的后繼ns的地址(見圖4a);然后,前繼節(jié)點(diǎn)np斷開與節(jié)點(diǎn)n的鏈接(見圖4b),后繼節(jié)點(diǎn)ns從節(jié)點(diǎn)n復(fù)制所有節(jié)點(diǎn)n負(fù)責(zé)的數(shù)據(jù)和副本數(shù)據(jù)(見圖4c);最后,節(jié)點(diǎn)n退出系統(tǒng),前繼節(jié)點(diǎn)np將自己的后繼指針指向ns,讓ns作為自己的后繼節(jié)點(diǎn)(見圖4d)。此時(shí),節(jié)點(diǎn)n的離開過程已經(jīng)完成。
圖4 節(jié)點(diǎn)離開Fig.4 Node to leave
定期更新機(jī)制被定期觸發(fā),目的在于在動(dòng)蕩環(huán)境下保持復(fù)制因子。有2個(gè)目標(biāo):①每個(gè)根節(jié)點(diǎn)定期聯(lián)系它的所有副本節(jié)點(diǎn)來保證正確維護(hù)合適的副本(updateReplicas);②每個(gè)節(jié)點(diǎn)保證只維護(hù)自己負(fù)責(zé)的key(verifReplicas)。因此,為了確保副本是最新的,它聯(lián)系所有副本key的后繼。
2.3 已有方法的故障情形分析與改進(jìn)研究
為了更好地理解本文改進(jìn)復(fù)制方法——Rd-Chord方法的優(yōu)點(diǎn),考慮圖5中描述的lookup情景。節(jié)點(diǎn)11發(fā)起lookup(2)操作并由不同的復(fù)制策略處理,復(fù)制因子在該例中為4。根據(jù)標(biāo)識(shí)符順序,將Chord模型中的節(jié)點(diǎn)分為8個(gè)區(qū)域,假設(shè)故障區(qū)域數(shù)cn=3。
1)后繼復(fù)制方法。圖5描述了后繼復(fù)制處理過程。假設(shè)節(jié)點(diǎn)11執(zhí)行l(wèi)ookup(2)的請(qǐng)求,r=4。為了在使用后繼復(fù)制的Chord網(wǎng)絡(luò)中找到key 2,節(jié)點(diǎn)11由在Finger table中尋找2的前繼開始,也就是節(jié)點(diǎn)15。根據(jù)Chord路由算法,在節(jié)點(diǎn)15執(zhí)行相同的查找過程,在節(jié)點(diǎn)15的Finger table中查找2的前繼,也就是節(jié)點(diǎn)1。節(jié)點(diǎn)1再轉(zhuǎn)發(fā)請(qǐng)求給節(jié)點(diǎn)2,也就是存儲(chǔ)被請(qǐng)求資源的節(jié)點(diǎn)。節(jié)點(diǎn)11發(fā)起的lookup(2)通過3跳到達(dá)successor(2)。
就跳數(shù)而言,在通常情況下后繼復(fù)制并沒有減少lookup的跳數(shù),除非lookup(k)操作由復(fù)制k的后繼發(fā)起。否則,lookup查詢將會(huì)被路由到successor(k)。
就抗毀性來說,故障區(qū)域是隨機(jī)挑選的,假設(shè)剛好是區(qū)域1、區(qū)域2和區(qū)域3,則存儲(chǔ)資源2的節(jié)點(diǎn)全部故障,在該網(wǎng)絡(luò)中資源2是不可用的。
2)前繼復(fù)制方法。該方法和后繼復(fù)制相比減少了2跳,如圖6所示。這是由于節(jié)點(diǎn)2復(fù)將key 2復(fù)制到了節(jié)點(diǎn)15,lookup過程在并沒有到達(dá)successor(2)時(shí)就已經(jīng)完成。因此,節(jié)點(diǎn)11只需要一跳便能完成lookup(2)操作。就抗毀性而言,當(dāng)有3個(gè)區(qū)域故障時(shí),假設(shè)剛好是區(qū)域7、區(qū)域8和區(qū)域1,則存儲(chǔ)資源2的節(jié)點(diǎn)全部故障,在該網(wǎng)絡(luò)中資源2不可用。
圖5 后繼復(fù)制方法Fig.5 Successor replication method
圖6 前繼復(fù)制方法Fig.6 Predecessor replication method
3)Rd-Chord方法。如圖7所示,Rd-Chord方法和后繼復(fù)制相比減少了1跳,和前繼復(fù)制相比增加了1跳。前2種復(fù)制方法副本存儲(chǔ)比較集中,在同樣數(shù)目副本的情況下,該方法副本分散在4個(gè)區(qū)域內(nèi),當(dāng)任意3個(gè)區(qū)域發(fā)生故障時(shí)依然有數(shù)據(jù)可得。
為了評(píng)估改進(jìn)數(shù)據(jù)復(fù)制策略的好處和適用性,本文進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)包括2個(gè)方面:①調(diào)查在考慮一系列的性能度量時(shí)該方法的效率;②和現(xiàn)有幾個(gè)數(shù)據(jù)復(fù)制策略進(jìn)行比較,包括后繼復(fù)制和前繼復(fù)制方法。所有方法用omnet++仿真實(shí)現(xiàn)。
3.1 仿真環(huán)境設(shè)定
仿真基于omnet++,對(duì)不同副本數(shù)和故障區(qū)域數(shù)進(jìn)行仿真,比較前繼復(fù)制、后繼復(fù)制和本文改進(jìn)方法查找平均跳數(shù)和查找失敗率。
平均跳數(shù)定義為
(1)
(1)式中:hi為第i條查找成功的消息經(jīng)過的跳數(shù);Lsuc為查找成功的消息數(shù)。
查找失敗率定義為
(2)
假設(shè)系統(tǒng)初始由N個(gè)節(jié)點(diǎn)構(gòu)成。每次實(shí)驗(yàn)由初始載入階段開始。隨后,在仿真階段節(jié)點(diǎn)可以在系統(tǒng)中進(jìn)行l(wèi)ookup查詢。每個(gè)key被復(fù)制r(復(fù)制因子)次。在仿真期間,8個(gè)區(qū)域中不同區(qū)域的節(jié)點(diǎn)會(huì)隨機(jī)故障。例如,當(dāng)N=1 024個(gè),故障區(qū)域數(shù)cn=2時(shí),會(huì)有1 024×(2/8) = 256個(gè)節(jié)點(diǎn)故障。
本仿真實(shí)驗(yàn)共有5個(gè)參數(shù):標(biāo)識(shí)符長度m,表示標(biāo)識(shí)符空間中標(biāo)識(shí)符ID所占的比特?cái)?shù);節(jié)點(diǎn)數(shù)N,表示整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目,即網(wǎng)絡(luò)規(guī)模;副本數(shù)r,表示整個(gè)網(wǎng)絡(luò)中的復(fù)制度,即副本數(shù)目閾值,該值比故障區(qū)域數(shù)多1;查詢消息數(shù)L,表示網(wǎng)絡(luò)中節(jié)點(diǎn)隨機(jī)生成查詢消息的總數(shù)目,每個(gè)節(jié)點(diǎn)發(fā)送100條查詢消息,則整個(gè)網(wǎng)絡(luò)有6 400條;故障區(qū)域數(shù)cn,表示將整個(gè)網(wǎng)絡(luò)劃分成8個(gè)區(qū)域,其中故障區(qū)域的總數(shù),當(dāng)故障區(qū)域數(shù)大于5時(shí),整個(gè)網(wǎng)絡(luò)癱瘓,因此,故障區(qū)域數(shù)最多為5。仿真過程中使用的參數(shù)如表1所示。
表1 仿真參數(shù)設(shè)置
3.2 算法比較
網(wǎng)絡(luò)模型基于Chord模型,本文將模型中所有節(jié)點(diǎn)按標(biāo)識(shí)符序號(hào)分為8個(gè)區(qū)域,統(tǒng)計(jì)在不同副本數(shù)下3種復(fù)制方法查找的平均跳數(shù)和不同故障區(qū)域數(shù)狀況下查找失敗率。本文解決的問題是在節(jié)點(diǎn)區(qū)域性故障時(shí),怎樣存儲(chǔ)副本可以提高數(shù)據(jù)可用性。前繼復(fù)制和后繼復(fù)制并沒有考慮到這個(gè)問題。
本文從查找速度和查找失敗率2個(gè)維度來驗(yàn)證Rd-Chord的有效性。其中,查找速度由最后統(tǒng)計(jì)的參數(shù)平均跳數(shù)來反映,查找失敗率即由最后統(tǒng)計(jì)的失敗率來反映。平均跳數(shù)越少,失敗率越低,表明算法效率越好。下面從查找成功平均跳數(shù)和查找失敗率2個(gè)方面比較本文的Rd-Chord方法以及前繼復(fù)制和后繼復(fù)制算法。
1)平均跳數(shù)。圖8為cn=3時(shí),不同副本個(gè)數(shù)下查找平均跳數(shù)。可以看出,當(dāng)副本數(shù)增加時(shí),平均跳數(shù)減少,這是因?yàn)椴檎页晒Φ母怕屎途W(wǎng)絡(luò)中可用的副本數(shù)是成正比的。Rd-Chord復(fù)制方法平均跳數(shù)居于前繼復(fù)制和后繼復(fù)制之間。
圖8 cn=3時(shí),不同副本個(gè)數(shù)下查找成功平均跳數(shù)Fig.8 cn=3, search successful average hops of different copies
2)查找失敗率。圖9為r=6時(shí),不同個(gè)數(shù)區(qū)域節(jié)點(diǎn)失效的查找失敗率。圖9中,查找失敗率隨著失效區(qū)域數(shù)增加而增加,這是由于失效節(jié)點(diǎn)可能存儲(chǔ)所查找的數(shù)據(jù)。前繼復(fù)制和后繼復(fù)制方法查找失敗率曲線幾乎重合,而本文的方法失敗率遠(yuǎn)遠(yuǎn)低于這2種方法。仿真表明,在節(jié)點(diǎn)區(qū)域性故障的情況下,Rd-Chord數(shù)據(jù)復(fù)制方法在幾乎沒有增加查找代價(jià)的前提下,大大提高了網(wǎng)絡(luò)中的數(shù)據(jù)可用性。
本文在Chord模型基礎(chǔ)上提出一種在局部節(jié)點(diǎn)故障時(shí)增加數(shù)據(jù)可用性的復(fù)制方法——Rd-Chord。為了應(yīng)對(duì)節(jié)點(diǎn)區(qū)域性故障,此方法將數(shù)據(jù)副本存儲(chǔ)在根節(jié)點(diǎn)前繼相對(duì)分散的節(jié)點(diǎn)集合上,這樣即使某個(gè)區(qū)域節(jié)點(diǎn)全部故障,別的區(qū)域依然有數(shù)據(jù)副本可供使用。為了驗(yàn)證該方法的有用性,本文對(duì)現(xiàn)有的前繼復(fù)制、后繼復(fù)制和Rd-Chord方法進(jìn)行了大量的比較實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示,就解決節(jié)點(diǎn)區(qū)域性故障而言,本文的數(shù)據(jù)復(fù)制方法遠(yuǎn)遠(yuǎn)優(yōu)于其他方法,而且也有很好的查找效率(查找成功平均跳數(shù)和后繼復(fù)制比并沒有明顯差距)。
圖9 r=6時(shí),不同個(gè)數(shù)區(qū)域節(jié)點(diǎn)失效的查找失敗率Fig.9 r=6, failure rate when nodes in different number of areas are fail
[1] BLOND S L, LEGOUT A, DABBOUS W.Pushing bittorrent locality to the limit.[J].Computer Networks, 2010,55(3), 541-557.
[2] 張永福. 分布式數(shù)據(jù)存儲(chǔ)關(guān)鍵技術(shù)研究[D]. 南京:南京郵電大學(xué), 2016.
ZHANG Yongfu.Study on Key Technology of Distributed Data Storage[D].Nanjing:Nanjing University of Posts and Telecommunications, 2016.
[3] CHEN H, JIN H, LUO X, et al. BloomCast: Efficient and Effective Full-Text Retrieval in Unstructured P2P Networks[J].IEEE Transactions on Parallel & Distributed Systems, 2011, 23(2):232-241.
[4] LEGTCHENKO S,SENS P,MULLER G.RelaxDHT:A churn-resilient replication strategy for peer-to-peer distributed hash-tables[J]. ACM Transactions on Autonomous & Adaptive Systems,2012 , 7(2) :1-18.
[5] RAMASUBRAMANIAN V, SIRER E G.The Design and Implementation of a Next Generation Name Service for the Internet[C]//ACM. Summaries of Technical Papers of Meeting Architectural Institute of Japan. E-2, Architectural Planning and Design Ii, Dwelling Houses and Housing Sites, Rural Planning, Education. New York:ACM,Architectural Institute of Japan, 2004:331-342.
[6] GUIRAT F B, FILALI I. An efficient data replication approach for structured peer-to-peer systems[C]//IEEE.International Conference on Telecommunications. New York:IEEE Press, 2013:1-5.
[7] ROUSSOPOULOS M, BAKER M. CUP: Controlled Update Propagation in Peer-to-Peer Networks[J]. Computer Science, 2002, 21(6):1 -6.
[8] YIN L, CAO G. DUP: Dynamic-Tree Based Update Propagation in Peer-to-Peer Networks[C]//IEEE. International Conference on Data Engineering. Tokoyo:IEEE Computer Society, 2005:258-259.
[9] SHEN H. EAD: An Efficient and Adaptive Decentralized File Replication Algorithm in P2P File Sharing Systems[C]// Eighth International Conference on Peer-To-Peer Computing.[s.l.]: IEEE Computer Society, 2008:827-840.
[10] GOPALAKRISHNAN V, SILAGHI B, BHATTACHARJEE B, et al. Adaptive replication in peer-to-peer systems[C]// 2008 APS March Meeting.[s.l.]: American Physical Society, 2004:360-369.
[11] 孫新,李慶洲,趙璞,等.對(duì)等網(wǎng)絡(luò)中一種優(yōu)化的副本分布方法[J].計(jì)算機(jī)學(xué)報(bào),2014, 37(6):1424-1434.
SUN Xin, LI Qqingzhou, ZHAO Pu, et al.An Optimized Copy Distribution Method in Peer-to-Peer Networks [J].Journal of Computers,2014,37(6): 1424-1434.
[12] YANG Z, TIAN J, ZHAO B Y, et al. Protector: A Probabilistic Failure Detector for Cost-Effective Peer-to-Peer Storage.[J]. IEEE Transactions on Parallel & Distributed Systems, 2010, 22(9):1514-1527.
[13] MUTHUSAMY V, JACOBSEN H A. Infrastructure-free content-based publish/subscribe[J].IEEE/ACM Transactions on Networking, 2014, 22(5):1516-1530.
[14] TU X, JIN H, CAO J, et al. An Efficient Data Scheduling Scheme for P2P Storage-Constrained IPTV System[J].IEEE Transactions on Systems Man & Cybernetics Systems, 2013, 43(2):379-389.
[15] KAWAKAMI T, ISHI Y, YOSHIHISA T, et al. A Study of Robustness Enhancement Technique on P2P Sensor Data Stream Delivery System Using Distributed Hashing[C]//IEEE.International Conference on P2P. New York:IEEE Press, 2014:591-596.
[16] ZHANG Y, GUO Y, CHEN Y. Optimized bandwidth allocation for maximizing user’s QoE in hybrid cloud P2P content distribution[J].Journal of China Universities of Posts & Telecommunications, 2015, 22(3):84-91.
[17] LAI C C, LIU C M. A mobility-aware approach for maintaining data consistency in unstructured mobile P2P systems[C]//IEEE.International Conference on Ubiquitous and Future Networks.New York:IEEE Press, 2015:695-700.
[18] HU Y, BHUYAN L N, FENG M. Maintaining Data Consistency in Structured P2P Systems[J].IEEE Transactions on Parallel & Distributed Systems, 2012, 23(11):2125-2137.
[19] SHEN H, LIU G.A Geographically Aware Poll-Based Distributed File Consistency Maintenance Method for P2P Systems[J].IEEE Transactions on Parallel & Distributed Systems, 2013, 24(11):2148-2159.
[20] NAKASHIMA T, FUJITA S.Tree-Based Consistency Maintenance Scheme for Peer-to-Peer File Sharing Systems[J]. Ieice Transactions on Information & Systems, 2013, 97 (12):187-193.
[21] NAKASHIMA T, FUJITA S. Scalable Tree-Based Consistency Maintenance in Heterogeneous P2P File Sharing Systems[C]//IEEE.International Conference on Parallel Processing Workshops.New York: IEEE Press, 2015:250-256.
(編輯:王敏琦)
ImproveddatareplicationapproachbasedonChordnetworkmodel
LIU Lifang1, HOU Liyuan1, QI Xiaogang2
(1. School of Computer Science and Technology, Xidian University, Xi’an 710071, P.R. China;2. School of Mathematics and Statistics, Xidian University, Xi’an 710071, P.R. China)
To solve the high failure rate in data search under the local node failure of the existing replication strategy, a new data replication mechanism called Rd-Chord is proposed. Discrete storage method is employed to deal with the data copies’ storage in the relatively decentralized nodes which are Pre-relay nodes of the root node in the Chord network, and thus there are still copies of data available in other regions even if all the nodes in one region or several regions are breakdown. Simultaneously, a basic update strategy and a periodic update strategy for Rd-Chord are presented to maintain the network structure and key migration. In order to verify the superiority of this method, the extensive comparative experiments on the existing predecessor replication, successor replication, and Rd-Chord are carried out, and the experiment results show that Rd-Chord is superior to the other methods in terms of the capability of solving the regional node failure, the searching failure rate of Rd-Chord is also cut down about 10% but the average searching efficiency is ensured.
P2P network; Chord model; data replication; regional fault
s:The National Natural Science Foundation of China (61572435, 61472305); The Natural Science Foundation of Shaanxi Province (2015JZ002, 2015JM6311); The Natural Science Foundation of Zhejiang Province (LZ16F020001); The Natural Science Foundation of Ningbo Province (2016A610035) ; The Space Measurement and Communication Innovation Fund (KJCK1608)
TP393
A
1673-825X(2017)05-0688-08
劉立芳(1972-),女,甘肅蘭州人,教授,博士研究生,主要研究方向?yàn)閿?shù)據(jù)處理與智能計(jì)算。E-mail: lfliu@xidian.edu.cn。
侯力元(1990-),女,陜西咸陽人,碩士研究生在讀,主要研究方向?yàn)閷?duì)等網(wǎng)絡(luò)數(shù)據(jù)抗毀性技術(shù)。E-mail:540406686@qq.com。
齊小剛(1973-),男,陜西寶雞人,教授,博士研究生,主要研究方向?yàn)橄到y(tǒng)建模與故障診斷。E-mail: xgqi@xidian.edu.cn。
2017-04-17
2017-09-07
侯力元 540406686@qq.com
國家自然科學(xué)基金(61572435, 61472305);陜西省自然科學(xué)基金(2015JZ002, 2015JM6311);浙江省自然科學(xué)基金(LZ16F020001);寧波市自然科學(xué)基金(2016A610035);空間測(cè)控通信創(chuàng)新探索基金(KJCK1608)
10.3979/j.issn.1673-825X.2017.05.016