一種基于分層云對等網(wǎng)絡(luò)的多屬性云資源區(qū)間查找算法分析

楊 宏

（武漢鐵路職業(yè)技術(shù)學(xué)院 湖北·武漢 430205）

0 引言

在大規(guī)模云資源分布式系統(tǒng)中，其查詢處理相對復(fù)雜且困難，在分層云對等的網(wǎng)絡(luò)運(yùn)用趨勢下，在多屬性云資源區(qū)間查找上運(yùn)用分層云對等技術(shù)，既能夠支撐匹配查詢，也能夠支撐范圍查詢，從而優(yōu)化云資源的查詢形式，相對于其它的查詢算法，其能夠?qū)θ我獾牟樵償?shù)據(jù)單元進(jìn)行單一檢索后，盡可能地將數(shù)據(jù)查詢的成本限制在一個(gè)更小的范圍內(nèi)。因此，基于分層云對等網(wǎng)絡(luò)的多屬性云資源區(qū)間搜索算法的研究和分析尤為重要。

1 分層云對等網(wǎng)絡(luò)

1.1 云計(jì)算背景

云計(jì)算理念自從提出以來都受到了各個(gè)計(jì)算機(jī)領(lǐng)域的研究。云計(jì)算提出了一種有效的網(wǎng)絡(luò)資源集成的新實(shí)現(xiàn)。通過網(wǎng)絡(luò)優(yōu)化云中存儲(chǔ)的資源服務(wù)模式與計(jì)算，對應(yīng)用服務(wù)資源和數(shù)據(jù)的配置和高效利用，并充分利用數(shù)據(jù)中心強(qiáng)大的傳統(tǒng)計(jì)算能力。用戶需要向企業(yè)或個(gè)人管理資源，用戶將根據(jù)需要直接支付費(fèi)用，就可以獲得自己的資源。云計(jì)算提供的資源服務(wù)主要包括基于傳統(tǒng)網(wǎng)絡(luò)基礎(chǔ)設(shè)施的計(jì)算功能、存儲(chǔ)功能、網(wǎng)絡(luò)服務(wù)功能等基礎(chǔ)資源，即基于傳統(tǒng)網(wǎng)絡(luò)的服務(wù)基礎(chǔ)設(shè)施，以基于傳統(tǒng)軟件資源，以軟件服務(wù)示例的形式提供給用戶，要讓多個(gè)用戶共享，即軟件作為服務(wù)軟件資源，為了實(shí)現(xiàn)云計(jì)算提供的強(qiáng)大服務(wù)，將云計(jì)算與對等技術(shù)相結(jié)合，構(gòu)成云對等網(wǎng)絡(luò)是當(dāng)前的發(fā)展趨勢。云計(jì)算的結(jié)構(gòu)化網(wǎng)絡(luò)和點(diǎn)對點(diǎn)技術(shù)在易于伸縮和資源定位方面具有明顯的優(yōu)勢，使用云計(jì)算和對等技術(shù)，可以克服云節(jié)點(diǎn)集中模式下的單點(diǎn)故障缺陷，有效地實(shí)現(xiàn)分布式資源管理和快速定位。

1.2 分層云對等網(wǎng)絡(luò)

在云計(jì)算技術(shù)背景下，分層云對等網(wǎng)絡(luò)與傳統(tǒng)的云計(jì)算與對等網(wǎng)絡(luò)相比，其最大的不同在于分層云對等網(wǎng)絡(luò)有恒穩(wěn)定在縣的云服務(wù)器構(gòu)成，云對等網(wǎng)絡(luò)的拓?fù)涮卣髋c傳統(tǒng)的對等網(wǎng)絡(luò)有很大的不同云對等網(wǎng)絡(luò)由云服務(wù)器組成，提供相對穩(wěn)定的云計(jì)算，不經(jīng)常上下移動(dòng)。因此，云資源描述信息可以存儲(chǔ)在單個(gè)節(jié)點(diǎn)上。而在云點(diǎn)對點(diǎn)網(wǎng)絡(luò)中，可用的云資源正在動(dòng)態(tài)變化的情境，即每一個(gè)節(jié)點(diǎn)都存儲(chǔ)在離線資源描述信息中，存儲(chǔ)提取過程需要不斷更新，導(dǎo)致網(wǎng)絡(luò)通信開銷的增加。基于此，設(shè)計(jì)新的分布式多維信息存儲(chǔ)模式，實(shí)現(xiàn)信息的動(dòng)態(tài)更新，以及降低更新成本，是當(dāng)前分層云對等網(wǎng)絡(luò)應(yīng)用的關(guān)鍵所在。

2 多屬性云資源區(qū)間查詢研究現(xiàn)狀

2.1 云資源區(qū)間查詢方法

云計(jì)算基于有效定位云資源的能力，提供了功能強(qiáng)大的服務(wù)。傳統(tǒng)的哈希算法是一種云計(jì)算和點(diǎn)對點(diǎn)網(wǎng)絡(luò)資源本地化算法，其只支持將給定鍵映射到節(jié)點(diǎn)的操作，使用一致性算法的變體來解決負(fù)載平衡，并確保在節(jié)點(diǎn)連接和離開時(shí)遷移的最小數(shù)據(jù)量。因此，哈希算法很簡單，可擴(kuò)展良好，非常適合于對等網(wǎng)絡(luò)的大型云計(jì)算。然而，它是基于哈希值精確匹配的，它不支持多關(guān)鍵字搜索和間隔搜索。它具有上述一些優(yōu)點(diǎn)，可作為該兩層模型的基本算法。HTC的哈希算法是一個(gè)包含哈希函數(shù)的分層網(wǎng)絡(luò)，所有哈希節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)的興趣劃分為多個(gè)簇，同一簇內(nèi)的節(jié)點(diǎn)根據(jù)哈希模型形成對等網(wǎng)絡(luò)，將大型嘻哈網(wǎng)絡(luò)劃分為多個(gè)小型嘻哈網(wǎng)絡(luò)。在資源搜索時(shí)，可以減少路由數(shù)量，提高搜索效率，同時(shí)也可以實(shí)現(xiàn)基于DHT的關(guān)鍵字精確匹配，不支持多維屬性和區(qū)間查找。

2.2 多屬性云資源區(qū)間查找方法

在多屬性云資源的區(qū)間查找方法中，當(dāng)前主要運(yùn)用以下三種方法。其一，將一維屬性查詢復(fù)用以實(shí)現(xiàn)多維查找方法。查找方法的最終查詢結(jié)果通過每個(gè)單個(gè)屬性查詢結(jié)果進(jìn)行交流。即使算法經(jīng)過優(yōu)化，搜索性能也會(huì)隨著維數(shù)的增加而迅速下降；其二，建立多維索引，將數(shù)據(jù)索引樹嵌入DHT網(wǎng)絡(luò)的底部，支持多屬性區(qū)間查找索引框架，以多播樹形式的多屬性查找。同樣，本文提出了一種基于分層云對等網(wǎng)絡(luò)的區(qū)間查找算法，基于分層云對等網(wǎng)絡(luò)，通過對云空間的實(shí)時(shí)數(shù)據(jù)屬性進(jìn)行分類，建立了多維索引，并將區(qū)間劃分為多個(gè)部分，以滿足復(fù)雜的查詢需求。同時(shí)，該查找方法能夠建立云資源區(qū)間的資源簇，以使得區(qū)間查找具備效應(yīng)性與拓展性。

3 多屬性云資源區(qū)間查找算法

3.1 雙層哈希函數(shù)模型

在具有N個(gè)屬性的云資源的數(shù)據(jù)類型中，通過對屬性范圍進(jìn)行向量定義，從而保障以屬性值進(jìn)行區(qū)間劃分。同時(shí)根據(jù)云資源的類型，相關(guān)資源存儲(chǔ)在本地網(wǎng)絡(luò)中，通過設(shè)置每個(gè)資源集群的入口節(jié)點(diǎn)來子構(gòu)建資源集群，從而優(yōu)化云資源的實(shí)時(shí)存儲(chǔ)與查找。同樣，為了加快云資源的快速準(zhǔn)確定位，采用了兩層哈希函數(shù)模型，第一層將相關(guān)資源類型組合成一個(gè)個(gè)資源集群。模型的第二層直接平靜地存儲(chǔ)資源集群，并通過匹配資源類型來提供資源。資源集群的大小相對于整個(gè)集群網(wǎng)絡(luò)的大小很小，從而提高了查找效率。由于第一層主要功能為索引，也被稱為索引層；第二層主要功能為特定資源的地址信息的提高，也被稱為資源層。其實(shí)際的模型結(jié)構(gòu)如圖一所示：

圖1：雙層哈希函數(shù)模型

3.2 多屬性云資源簇定位算法

在云計(jì)算多屬性資源族的隨機(jī)生成上，其實(shí)際的規(guī)模存在隨機(jī)性，但是在模型下的資源簇的類型定義上一定的限制，平衡系統(tǒng)資源和采集量。當(dāng)集群過熱或訪問的節(jié)點(diǎn)太少時(shí)，可以將其他具有空閑和低通信延遲的主機(jī)添加到資源集群中。資源集群內(nèi)的節(jié)點(diǎn)可以在物理上相對聚合，集群內(nèi)的通信效率。當(dāng)查詢關(guān)鍵字不等于資源群集的類型組合時(shí)，直接哈希查詢關(guān)鍵字無法找到資源群集，但可以使用哈希函數(shù)方法進(jìn)行定位，但效率較低，網(wǎng)絡(luò)流量較大。由于存儲(chǔ)容量不再是主要的限制因素，因此可以適當(dāng)?shù)卦黾淤Y源群集索引，以提高資源發(fā)現(xiàn)速度。同樣，在資源集群的擴(kuò)展和擴(kuò)展中，采用相同的索引設(shè)計(jì)來減輕系統(tǒng)的存儲(chǔ)負(fù)擔(dān)，實(shí)現(xiàn)容錯(cuò)性能的提高。在資源群集代理節(jié)點(diǎn)的變化中，需要及時(shí)更新查找索引節(jié)點(diǎn)，以減少資源數(shù)據(jù)的查詢等待時(shí)間。

3.3 編碼與查找

在實(shí)際的編碼與查早上，通過劃分每種類型的屬性值，從邏輯上形成多維資源空間，然后使用維填充曲線將多維資源縮減為一維資源循環(huán)。由于希爾伯特曲線在空間曲線族中具有最好的數(shù)據(jù)聚合特性，本文采用希爾伯特空間填充曲線編碼來繪制多維希爾伯特環(huán)，這不僅降低了數(shù)據(jù)的維數(shù)，而且更好地保持了原始資源的相對位置。為方便起見，對原始的希爾伯特曲線填充方法進(jìn)行了編碼。

同樣，在資源集群內(nèi)搜索時(shí)，該表需要確定查詢資源的坐標(biāo)，并將其轉(zhuǎn)換為空間填充曲線編碼，然后根據(jù)哈希規(guī)則找到提供資源的節(jié)點(diǎn)，最后將資源的IP和節(jié)點(diǎn)發(fā)送給用戶，用戶可以直接與節(jié)點(diǎn)通信。如果資源節(jié)點(diǎn)提供的資源有或沒有資源，則資源節(jié)點(diǎn)將間隔鄰居節(jié)點(diǎn)返回給用戶。如果間隔鄰居節(jié)點(diǎn)也沒有資源，則可以提供鄰居間隔鄰居節(jié)點(diǎn)，否則用戶的查找將失敗。用戶收集資源節(jié)點(diǎn)提供的資源信息。當(dāng)資源來自多個(gè)資源集群時(shí)，它們將按匹配的權(quán)重進(jìn)行排序，并提供給用戶。同時(shí)保持時(shí)間間隔的鄰居節(jié)點(diǎn)信息增加了節(jié)點(diǎn)的存儲(chǔ)成本，但該系統(tǒng)是建立在云服務(wù)器上的，但存儲(chǔ)容量不再是主要的限制因素，但它可以簡化查詢，提高效率、搜索效率等方便性。

4 結(jié)束語

由此可見，基于分層云對等網(wǎng)絡(luò)的使用，對云資源的類型和屬性進(jìn)行了存儲(chǔ)和索引，有助于構(gòu)建云資源的動(dòng)態(tài)資源簇，通過在資源層合理運(yùn)用哈希曲線來進(jìn)行降維，同時(shí)增加相鄰區(qū)間的索引存儲(chǔ)，以此提升實(shí)際的查找效率，提升查找的實(shí)用性。