基于格雷碼的結(jié)構(gòu)化對等計算系統(tǒng)及其數(shù)據(jù)管理.pdf

1、對等計算(Peer-to-Peer,簡稱P2P)是一個自組織的分布式網(wǎng)絡(luò)系統(tǒng)。脫胎于文件共享,當(dāng)前P2P系統(tǒng)的研究熱點已經(jīng)逐步過渡到:系統(tǒng)資源共享、分布式數(shù)據(jù)管理等。這類研究給現(xiàn)代網(wǎng)絡(luò)應(yīng)用注入了新的活力,因為P2P系統(tǒng)打破了現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu),進而提供了一個自組織、高分散、可擴展、節(jié)點對等的分布式網(wǎng)絡(luò)。同時,這種分布式網(wǎng)絡(luò)結(jié)構(gòu)也給網(wǎng)絡(luò)應(yīng)用帶來了很多新的挑戰(zhàn),例如,如何提供有效的復(fù)雜數(shù)據(jù)查詢、如何獲取當(dāng)前網(wǎng)絡(luò)中數(shù)據(jù)的分布信息等等。
　　

2、 盡管對等計算系統(tǒng)在文件共享、簡單數(shù)據(jù)管理方面已經(jīng)取得了不少研究成果,但是許多問題(如復(fù)雜數(shù)據(jù)管理等)依舊亟待解決。本文的研究重點是在現(xiàn)有成熟的P2P覆蓋網(wǎng)絡(luò)(Chord)基礎(chǔ)上,對其改進、優(yōu)化,并提出了一個新的P2P系統(tǒng)——GChord系統(tǒng)。結(jié)合了Chord系統(tǒng)的路由特性和格雷碼(GrayCode)數(shù)據(jù)索引編碼的優(yōu)點,GChord(Gray Codebased Chord System)系統(tǒng)由此具備了支持復(fù)雜數(shù)據(jù)管理能力?，F(xiàn)有GCho

3、rd系統(tǒng)支持的復(fù)雜數(shù)據(jù)管理主要包括:當(dāng)前網(wǎng)絡(luò)中數(shù)據(jù)密度分布函數(shù)的準確估計、一維(多維)精確匹配查找、一維(多維)范圍查找、偏好查找、多屬性查找等。以后我們將對GChord系統(tǒng)不斷研究、充實,使之成為一個完備的P2P系統(tǒng)。下面給出本文的主要貢獻:
　　 ·實現(xiàn)了Gchord系統(tǒng)中節(jié)點管理和數(shù)據(jù)管理的無縫結(jié)合。GChord系統(tǒng)脫胎于Chord系統(tǒng),但是青出于藍而勝于藍。GChord系統(tǒng)將原Chord系統(tǒng)中相互獨立的節(jié)點管理和數(shù)據(jù)管理

4、緊密地結(jié)合起來,進而獲得了很多Chord系統(tǒng)不具備的特性。對于節(jié)點管理,GChord系統(tǒng)和Chord系統(tǒng)具有相同的組織、維護方式。對于數(shù)據(jù)管理,GChord系統(tǒng)結(jié)合了基于格雷碼(任意相鄰的兩個格雷碼相差一位)混洗編碼(shuffle-based)的數(shù)據(jù)索引鍵值生成技術(shù),實現(xiàn)了節(jié)點管理和數(shù)據(jù)管理的無縫結(jié)合。GChord系統(tǒng)的指表(fingertable,即路由表)不僅實現(xiàn)了節(jié)點路由的O(logn)復(fù)雜度,同時也實現(xiàn)了數(shù)據(jù)值域路由的O(lo

5、gn)復(fù)雜度,其中n為系統(tǒng)中節(jié)點數(shù)目。突破了Chord系統(tǒng)只支持精確匹配查找的限制,GChord系統(tǒng)能夠支持包括范圍查找在內(nèi)的許多復(fù)雜數(shù)據(jù)管理。
　　 ·對GChord系統(tǒng)中分布無關(guān)數(shù)據(jù)密度分布函數(shù)估計提供了支持,即讓網(wǎng)絡(luò)中的每個節(jié)點都能精確估計當(dāng)前網(wǎng)絡(luò)中數(shù)據(jù)的密度分布。P2P系統(tǒng)的許多應(yīng)用均受益于密度分布估計,例如:負載平衡分析、復(fù)雜數(shù)據(jù)查詢和數(shù)據(jù)挖掘等等。分布無關(guān)數(shù)據(jù)密度函數(shù)估計算法的主要特性是,不論底層數(shù)據(jù)按照何種模型分布

6、抑或是根本不存在任何分布模型,該算法均能以近似的估計精度準確估計當(dāng)前網(wǎng)絡(luò)中的數(shù)據(jù)密度分布函數(shù)。分布無關(guān)密度估計算法首先將底層數(shù)據(jù)的任意分布轉(zhuǎn)換成一中間分布——累計概率分布函數(shù)。由于累計概率分布函數(shù)的輸出在[0,1]之間均勻分布,因此接著對累計概率分布函數(shù)的輸出隨機采樣,可以準確估計當(dāng)前網(wǎng)絡(luò)中數(shù)據(jù)的密度分布。本文在GChord系統(tǒng)環(huán)境下,提出了三種計算累計概率分布函數(shù)的有效算法和兩種對累計概率分布函數(shù)的輸出隨機采樣的算法。累計概率分布函數(shù)

7、計算算法讓網(wǎng)絡(luò)中每個節(jié)點只維護累計概率分布函數(shù)中相互不重疊的一個片段,而所有這些片斷綜合起來又構(gòu)成了完整的累計概率分布函數(shù),由此降低了各個節(jié)點的維護代價。我們從理論上證明了累計概率分布函數(shù)的計算誤差和分布無關(guān)數(shù)據(jù)密度估計的估計誤差,同時給出了詳盡的算法。充分的實驗也證明了該算法在估計數(shù)據(jù)分布方面的有效性和高效性。
　　 ·對GChord系統(tǒng)中偏好查找提供了支持。所謂偏好查找是指查詢請求中包含有用戶對各個屬性項不同偏好程度并返回t

8、op-κ條數(shù)據(jù)元組的查詢。對于各個屬性項具有不同偏好程度的查詢請求,其查詢結(jié)果可能大相徑庭?，F(xiàn)有數(shù)據(jù)索引技術(shù)均無法對偏好查找提供很好的支持。本文提出了一種在GChord系統(tǒng)上支持偏好查找的新穎方法。通過估計當(dāng)前網(wǎng)絡(luò)中的數(shù)據(jù)分布,并計算包含有top-κ查詢數(shù)據(jù)元組的區(qū)域范圍,將偏好查找轉(zhuǎn)換為范圍查找并執(zhí)行有效查找。通過對數(shù)據(jù)空間多維柱狀圖信息進行離散余弦變換可有效維護當(dāng)前網(wǎng)絡(luò)中數(shù)據(jù)的分布,從而實現(xiàn)數(shù)據(jù)密度分布的準確估計。本文也提出了對偏好

9、矩陣(由查詢請求給定)作奇異值分解,有效計算對應(yīng)查找范圍的算法。在實現(xiàn)偏好查找到范圍查找的有效轉(zhuǎn)換之后,通過多播區(qū)域(mutli-castzone)的形式獲取相關(guān)節(jié)點上的top-κ條數(shù)據(jù)元組。本文給出了數(shù)據(jù)分布估計算法和范圍計算的算法及其理論分析。詳盡的實驗證明了該方法在處理偏好查找方面的有效性和高效性。
　　 ·對GChord系統(tǒng)中多屬性范圍查找提供了支持。所謂多屬性查找是指查詢請求中僅包含有用戶關(guān)心屬性項的謂詞(即查詢中包含

10、的屬性項可以是數(shù)據(jù)元組屬性項集合的子集)。因此,該類查詢請求中包含的謂詞可以針對任意數(shù)目的屬性項,也可以針對任意屬性項之間的組合?，F(xiàn)有P2P系統(tǒng)都無法高效的處理該類查詢。由于GChord系統(tǒng)實現(xiàn)了節(jié)點管理和數(shù)據(jù)管理之間的無縫結(jié)合,進而實現(xiàn)了相鄰數(shù)據(jù)之間的快速路由,由此提供了對多屬性查詢的良好支持。本文提出了使用卡諾圖(Karnaughmap)有效計算包含有查詢結(jié)果節(jié)點的算法,并且以多播樹(multi-casttree)的方式獲取這些節(jié)點

11、上數(shù)據(jù)元組的算法及其理論分析。詳盡的試驗證明了該方法在處理多屬性查詢的有效性和高效性。
　　 綜上所述,本文詳細介紹了GChord系統(tǒng),及其支持的復(fù)雜數(shù)據(jù)管理操作。GChord系統(tǒng)實現(xiàn)了節(jié)點管理和數(shù)據(jù)管理的無縫結(jié)合,并對當(dāng)前網(wǎng)絡(luò)中分布無關(guān)數(shù)據(jù)密度的精確估計、偏好查找、多屬性范圍查找、一維精確匹配查找(源于對Chord系統(tǒng)的繼承)、多維精確匹配查找和一維(多維)范圍查找(源于對多屬性范圍查找的支持)提供了支持。這些功能滿足了當(dāng)前P