[發(fā)明專利]一種基于云計算環(huán)境的分布并行Skyline查詢方法

有效

• 申請?zhí)枺?/td>: 201110327433.4
• 申請日: 2011-10-25
• 公開（公告）號: CN102314521A
• 公開（公告）日: 2012-01-11
• 發(fā)明（設(shè)計）人: 王意潔;王媛;鄧瑞鵬;裴曉強;李小勇;孫偉東;馬行空
• 申請（專利權(quán)）人: 中國人民解放軍國防科學(xué)技術(shù)大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L29/08
• 代理公司: 國防科技大學(xué)專利服務(wù)中心 43202
• 代理人: 郭敏

1.一種基于云計算環(huán)境的分布并行Skyline查詢方法，其特征在于包括以下步驟：

第一步，構(gòu)建一個云計算環(huán)境，它由多個節(jié)點構(gòu)成，每個節(jié)點都是一臺可獨立運行的計算機，各節(jié)點通過網(wǎng)絡(luò)設(shè)備互連；節(jié)點包括一個門戶節(jié)點和N個計算節(jié)點，N為正整數(shù)；門戶節(jié)點負責(zé)與用戶交互，接收用戶提交的查詢請求并轉(zhuǎn)發(fā)給計算節(jié)點，接收計算節(jié)點的查詢處理結(jié)果并返回給用戶；計算節(jié)點負責(zé)存儲原始數(shù)據(jù)集并執(zhí)行查詢處理任務(wù)，并向門戶節(jié)點返回查詢處理結(jié)果；門戶節(jié)點和計算節(jié)點上均安裝有操作系統(tǒng)、TCP/IP協(xié)議軟件，配置了網(wǎng)絡(luò)環(huán)境；門戶節(jié)點上安裝有任務(wù)管理程序和結(jié)果回收程序，任務(wù)管理程序接收用戶提交的Skyline查詢請求，向各計算節(jié)點轉(zhuǎn)發(fā)Skyline查詢請求，結(jié)果回收程序負責(zé)接收計算節(jié)點的查詢處理結(jié)果并返回給用戶；計算節(jié)點上安裝有查詢處理程序和故障處理程序，查詢處理程序負責(zé)接收來自門戶節(jié)點的Skyline查詢請求，并對計算節(jié)點上存儲的原始數(shù)據(jù)集進行Skyline查詢處理，故障處理程序負責(zé)定期對鄰居節(jié)點進行故障檢測，并進行故障修復(fù)；計算節(jié)點的編號為i，i＝1，2，…，N，當1≤i≤N-1時，計算節(jié)點i的鄰居節(jié)點為計算節(jié)點i+1；當i＝N時，計算節(jié)點i的鄰居節(jié)點為計算節(jié)點1；

第二步，門戶節(jié)點執(zhí)行任務(wù)管理程序，向各計算節(jié)點轉(zhuǎn)發(fā)Skyline查詢請求；各計算節(jié)點執(zhí)行查詢處理程序，接收來自門戶節(jié)點的Skyline查詢請求，并行進行Skyline查詢處理；計算節(jié)點執(zhí)行故障處理程序，定期對鄰居節(jié)點進行故障檢測，并進行故障修復(fù)：

2.1門戶節(jié)點的任務(wù)管理程序接收用戶提交的Skyline查詢請求；

2.2門戶節(jié)點的任務(wù)管理程序向所有計算節(jié)點轉(zhuǎn)發(fā)Skyline查詢請求；

2.3每個計算節(jié)點的查詢處理程序接收來自門戶節(jié)點的Skyline查詢請求，根據(jù)接收的Skyline查詢請求對各自存儲的原始數(shù)據(jù)集進行Skyline查詢處理，具體步驟如下：

2.3.1查詢處理程序接收來自門戶節(jié)點的Skyline查詢請求；

2.3.2查詢處理程序初始化查詢處理結(jié)果集合簡稱Skyline集合

2.3.3查詢處理程序?qū)Ρ镜卦紨?shù)據(jù)集Set中的所有數(shù)據(jù)對象逐一進行數(shù)據(jù)對象之間的控制關(guān)系判斷，將不被Set中任意一個其他數(shù)據(jù)對象所控制的數(shù)據(jù)對象放到Skyline集合LS中，即，判斷本地原始數(shù)據(jù)集Set中的每個數(shù)據(jù)對象DO與Set中的所有其他數(shù)據(jù)對象之間的控制關(guān)系，如果DO不被Set中任意一個其他數(shù)據(jù)對象所控制，則將DO放入計算節(jié)點的Skyline集合LS中，即，LS＝LS+{DO}；

2.3.4查詢處理程序?qū)kyline集合LS發(fā)送給其他所有計算節(jié)點；

2.3.5查詢處理程序接收來自其他所有計算節(jié)點的Skyline集合，并將其合并為LS’；

2.3.6查詢處理程序?qū)kyline集合LS中的所有數(shù)據(jù)對象逐一進行篩選，方法是判斷LS中的每個數(shù)據(jù)對象SDO與來自其他所有計算節(jié)點的LS’中的所有數(shù)據(jù)對象之間的控制關(guān)系，如果數(shù)據(jù)對象SDO被LS’中任意一個數(shù)據(jù)對象所控制，則將數(shù)據(jù)對象SDO從LS中刪除，即，LS＝LS-{SDO}；

2.3.7查詢處理程序?qū)S返回給門戶節(jié)點；

2.4每個計算節(jié)點的故障處理程序按故障檢測的周期T定期對鄰居節(jié)點進行故障檢測，并進行故障修復(fù)，T取100s，具體步驟如下：

2.4.1故障處理程序按周期T定期向鄰居節(jié)點發(fā)送探測消息；

2.4.2鄰居節(jié)點接收探測消息，并向計算節(jié)點返回應(yīng)答消息；

2.4.3故障處理程序檢查t時間內(nèi)是否收到鄰居節(jié)點的應(yīng)答消息，t取10s；

2.4.4故障處理程序?qū)ξ唇邮盏綉?yīng)答消息的鄰居節(jié)點進行如下故障修復(fù)處理：

2.4.4.1計算節(jié)點替代其鄰居節(jié)點進行Skyline查詢處理，并將最終的Skyline集合LS返回給門戶節(jié)點；

2.4.4.2計算節(jié)點替代其鄰居節(jié)點進行后續(xù)的定期故障檢測和故障修復(fù)；

第三步，門戶節(jié)點的結(jié)果回收程序收集所有計算節(jié)點的Skyline集合LS，并將其匯總返回給用戶。

2.如權(quán)利要求1所述的一種基于云計算環(huán)境的分布并行Skyline查詢方法，其特征在于采用互為備份方式對計算節(jié)點進行容錯處理，即每個計算節(jié)點是其他所有計算節(jié)點的備份節(jié)點，其他所有計算節(jié)點上的原始數(shù)據(jù)集的副本都存儲在該計算節(jié)點上，每個計算節(jié)點有N-1個備份節(jié)點，計算節(jié)點上的原始數(shù)據(jù)集的副本存儲在其N-1個備份節(jié)點上。