[發(fā)明專利]一種基于時間參數(shù)的副本等級衰減方法

有效

• 申請?zhí)枺?/td>: 200910081614.6
• 申請日: 2009-04-07
• 公開（公告）號: CN101645920A
• 公開（公告）日: 2010-02-10
• 發(fā)明（設計）人: 尤佳莉;王勁林;鄧浩江;王玲芳
• 申請（專利權(quán)）人: 中國科學院聲學研究所
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/58
• 代理公司: 北京法思騰知識產(chǎn)權(quán)代理有限公司
• 代理人: 楊小蓉

技術(shù)領域

本發(fā)明涉及信息網(wǎng)絡技術(shù)領域，特別涉及一種應用于分布式系統(tǒng)中的基于時間參數(shù)的副本等級衰減方法。?

背景技術(shù)

在分布式系統(tǒng)中，數(shù)據(jù)被存儲在系統(tǒng)中的不同節(jié)點上，為了加快用戶訪問速度和降低部分應用中，數(shù)據(jù)源服務器的負載壓力，文件常常存在許多副本，并散布在網(wǎng)絡中，便于用戶在最近的節(jié)點處獲取對應副本，降低數(shù)據(jù)傳輸延遲，避免網(wǎng)絡擁塞，提高響應速度和服務質(zhì)量。然而，在分布式系統(tǒng)中，每個節(jié)點的存儲空間有限，系統(tǒng)無法滿足數(shù)據(jù)無限制的生成副本，因此，需要對副本空間進行有效管理，通過一定規(guī)則來對不需要的數(shù)據(jù)進行優(yōu)化。?

結(jié)構(gòu)化的P2P網(wǎng)絡是指所有節(jié)點通過某種規(guī)則的、固定拓撲的方式進行組織。每個節(jié)點都有固定的節(jié)點度，表示所聯(lián)系鄰居的數(shù)目，每個鄰居都被精心挑選，可以保證節(jié)點間的可路由和可查找。結(jié)構(gòu)化P2P網(wǎng)絡的顯著特點是自組織性，在節(jié)點加入、失效等動態(tài)性的情況下，可以有效保持拓撲結(jié)構(gòu)，保證網(wǎng)絡的路由性能。該組織方式在分布式網(wǎng)絡系統(tǒng)中得到了廣泛的應用。?

圖1是結(jié)構(gòu)化P2P網(wǎng)絡中的副本放置示意圖。如圖1所示，在結(jié)構(gòu)化P2P網(wǎng)絡中，每個節(jié)點都通過某種哈希算法得到一個唯一ID值，同樣，所有應用實體(如對象，object)，也通過該哈希算法得到一個與節(jié)點Id在同一個數(shù)值空間的objectID值，同樣也有一個唯一的放置節(jié)點，該放置節(jié)點就叫做該object的主節(jié)點，叫做home?node。對object的查找即對其home?node的定位，該過程是通過查詢發(fā)起節(jié)點的鄰居節(jié)點作為中介而逐跳進行，直至找到目標或查找失敗為止。?

結(jié)構(gòu)化P2P網(wǎng)絡又稱為分布式哈希表(簡稱DHT)，以上的資源定位過程是一個普遍方法。在實際應用中，不同的拓撲結(jié)構(gòu)被提出，也對應了不同的DHT算法。常用的有CAN，Chord，Kademlia，Pastry，Tapestry等。在DHT網(wǎng)絡中，假設哈希值的ID空間為M個bit位的數(shù)值，從左到右，所有匹配大于等于l位數(shù)值的ID，稱為在一個等級，即一個level。一個object如果其level為l，表示路由l跳就可以找到該object。因此，需要在l跳覆蓋之外的所有節(jié)點上進行備份。比如，以Pastry為路由協(xié)議，object的level為l則對應了一個楔形的節(jié)點區(qū)域，表示該區(qū)域的所有節(jié)點需要對object進行備份，若網(wǎng)絡中節(jié)點總數(shù)為N，基數(shù)為b，則需要N/b^l個節(jié)點進行備份。因此，如何計算每個object所對應的level值，則是副本放置的關鍵。而對l值進行合理的變化，則可對應文件副本數(shù)目的變化。?

在分布式系統(tǒng)的存儲空間不足時，常將最不常用(at?least?recently?used)和最少用(at?least?frequetly?used)的文件刪除，為其余待分發(fā)文件騰出空間。然而，文件的副本等級和文件流行度以及所上線時間有一定的相關性，如果不考慮這些因素，很有可能將有用的文件副本刪除。?

發(fā)明內(nèi)容

為了解決上述問題，本發(fā)明的目的在于提供一種應用于分布式系統(tǒng)中的基于時間參數(shù)的副本等級衰減方法。該方法以文件上線時間作為參數(shù)，綜合文件流行度信息，使文件副本等級隨時間變化而衰減。該方法有利于分布式系統(tǒng)中的內(nèi)容更新，避免不常用數(shù)據(jù)長時間占據(jù)分布式系統(tǒng)中的存儲空間，使存儲空間得到充分利用，方便更多的文件得到服務，提高對應系統(tǒng)的服務性能，并改善系統(tǒng)性能。?

為了實現(xiàn)上述目的，本發(fā)明的一種基于時間參數(shù)的副本等級衰減方法中，假設文件f初始的副本等級為L，所有與f的ID匹配L位的節(jié)點上都有一份f的副本。每個文件的主節(jié)點，即與其ID最近的節(jié)點，都會存儲一個關于該文件的元數(shù)據(jù)，包括：當前層數(shù)、衰減周期、衰減步長以及開始時間。而每個副本都帶有一個表示生存期的數(shù)據(jù)結(jié)構(gòu)，定時自我檢測并計算剩余等級數(shù)，從而決定該節(jié)點所保持的副本是否需要刪除。則在網(wǎng)絡中，從文件加入到退出，整個衰減過程包括如下步驟，?

1)通過等級計算得到文件f的初始副本等級；?

2)通過某個管理節(jié)點計算文件f基于流行度的生存期，計算方法如下：?

a)從管理節(jié)點或某個全局信息表中讀取文件f的流行度信息pop；?

b)通過對網(wǎng)絡中所有文件流行度的統(tǒng)計，計算得到所有節(jié)點的平均流行度ave_pop；?

c)通過下式計算總在線時間值tc：?

tc＝pop/ave_pop×ut?