[發(fā)明專利]一種面向云計(jì)算環(huán)境的容錯并行Skyline查詢方法

有效

• 申請?zhí)枺?/td>: 201110205925.6
• 申請日: 2011-07-22
• 公開（公告）號: CN102254016A
• 公開（公告）日: 2011-11-23
• 發(fā)明（設(shè)計(jì)）人: 王意潔;王媛;鄧瑞鵬;裴曉強(qiáng);李小勇;楊永滔;孫偉東
• 申請（專利權(quán)）人: 中國人民解放軍國防科學(xué)技術(shù)大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F11/07
• 代理公司: 國防科技大學(xué)專利服務(wù)中心 43202
• 代理人: 郭敏

1.一種面向云計(jì)算環(huán)境的容錯并行Skyline查詢方法，其特征在于包括以下步驟：

第一步，構(gòu)建一個云計(jì)算環(huán)境，它由多個節(jié)點(diǎn)構(gòu)成，每個節(jié)點(diǎn)都是一臺可獨(dú)立運(yùn)行的計(jì)算機(jī)，各節(jié)點(diǎn)通過網(wǎng)絡(luò)設(shè)備互連；云計(jì)算環(huán)境包括一個協(xié)調(diào)節(jié)點(diǎn)，負(fù)責(zé)與用戶交互，接收用戶提交的查詢請求，向各計(jì)算節(jié)點(diǎn)分發(fā)查詢處理任務(wù)和收集查詢處理結(jié)果，并向用戶返回查詢結(jié)果；云計(jì)算環(huán)境包括N個計(jì)算節(jié)點(diǎn)，N為正整數(shù)，它們負(fù)責(zé)存儲原始數(shù)據(jù)集并執(zhí)行查詢處理任務(wù)，并向協(xié)調(diào)節(jié)點(diǎn)返回查詢處理結(jié)果；每個計(jì)算節(jié)點(diǎn)配置一個備份節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)上的原始數(shù)據(jù)集的副本存儲在其備份節(jié)點(diǎn)上；協(xié)調(diào)節(jié)點(diǎn)、計(jì)算節(jié)點(diǎn)和備份節(jié)點(diǎn)上均安裝有操作系統(tǒng)、TCP/IP協(xié)議軟件，配置了網(wǎng)絡(luò)環(huán)境；協(xié)調(diào)節(jié)點(diǎn)上安裝有任務(wù)調(diào)度程序、結(jié)果分析處理程序和故障處理程序，任務(wù)調(diào)度程序接收用戶提交的Skyline查詢請求，向各計(jì)算節(jié)點(diǎn)分發(fā)Skyline查詢處理任務(wù)，結(jié)果分析處理程序負(fù)責(zé)收集計(jì)算節(jié)點(diǎn)的Skyline查詢處理結(jié)果，并對收集到的所有計(jì)算節(jié)點(diǎn)的Skyline查詢處理結(jié)果再進(jìn)行Skyline查詢處理以得到最終的Skyline查詢結(jié)果，故障處理程序負(fù)責(zé)定期對計(jì)算節(jié)點(diǎn)進(jìn)行故障檢測，并進(jìn)行故障修復(fù)；計(jì)算節(jié)點(diǎn)和備份節(jié)點(diǎn)上均安裝有查詢處理程序，查詢處理程序負(fù)責(zé)接收來自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢請求，并對計(jì)算節(jié)點(diǎn)或者備份節(jié)點(diǎn)上存儲的原始數(shù)據(jù)集進(jìn)行Skyline查詢處理；

第二步，協(xié)調(diào)節(jié)點(diǎn)執(zhí)行任務(wù)調(diào)度程序，向各計(jì)算節(jié)點(diǎn)分發(fā)Skyline查詢處理任務(wù)；協(xié)調(diào)節(jié)點(diǎn)執(zhí)行故障處理程序，定期對計(jì)算節(jié)點(diǎn)進(jìn)行故障檢測，并進(jìn)行故障修復(fù)；各計(jì)算節(jié)點(diǎn)執(zhí)行查詢處理程序，接收來自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢處理任務(wù)，并行進(jìn)行Skyline查詢處理；

2.1協(xié)調(diào)節(jié)點(diǎn)的任務(wù)調(diào)度程序接收用戶提交的Skyline查詢請求；

2.2協(xié)調(diào)節(jié)點(diǎn)的任務(wù)調(diào)度程序向所有計(jì)算節(jié)點(diǎn)轉(zhuǎn)發(fā)Skyline查詢請求；

2.3協(xié)調(diào)節(jié)點(diǎn)的故障處理程序按故障檢測的周期T定期對計(jì)算節(jié)點(diǎn)進(jìn)行故障檢測，并進(jìn)行故障修復(fù)，T取100s，具體步驟如下：

2.3.1故障處理程序按周期T定期向所有計(jì)算節(jié)點(diǎn)發(fā)送探測消息；

2.3.2故障處理程序接收協(xié)調(diào)節(jié)點(diǎn)的探測消息，并返回應(yīng)答消息；

2.3.3故障處理程序檢查t時間內(nèi)收到的計(jì)算節(jié)點(diǎn)的應(yīng)答消息，t取10s；

2.3.4故障處理程序?qū)ξ唇邮盏綉?yīng)答消息的計(jì)算節(jié)點(diǎn)進(jìn)行如下故障修復(fù)處理：

2.3.4.1如果協(xié)調(diào)節(jié)點(diǎn)保存的該計(jì)算節(jié)點(diǎn)的狀態(tài)標(biāo)記Status為“Complete”，則協(xié)調(diào)節(jié)點(diǎn)保存的Skyline集合即為該計(jì)算節(jié)點(diǎn)最終的Skyline集合；

2.3.4.2如果協(xié)調(diào)節(jié)點(diǎn)保存的該計(jì)算節(jié)點(diǎn)的狀態(tài)標(biāo)記Status為“Continue”，則協(xié)調(diào)節(jié)點(diǎn)將Skyline查詢請求、保存的“數(shù)據(jù)對象DO在本地原始數(shù)據(jù)集Set中的當(dāng)前位置”和“Skyline集合LS”一起發(fā)送給該計(jì)算節(jié)點(diǎn)的備份節(jié)點(diǎn)，由備份節(jié)點(diǎn)替代該計(jì)算節(jié)點(diǎn)繼續(xù)完成后續(xù)的Skyline查詢處理，并將最終的Skyline集合LS返回給協(xié)調(diào)節(jié)點(diǎn)；。

2.4每個計(jì)算節(jié)點(diǎn)的查詢處理程序接收來自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢請求，根據(jù)接收的Skyline查詢請求對各自存儲的原始數(shù)據(jù)集進(jìn)行Skyline查詢處理，具體步驟如下：

2.4.1查詢處理程序接收來自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢請求；

2.4.2查詢處理程序初始化Skyline集合計(jì)數(shù)器ε＝0；

2.4.3查詢處理程序?qū)Ρ镜卦紨?shù)據(jù)集Set中的所有數(shù)據(jù)對象逐一進(jìn)行數(shù)據(jù)對象之間的控制關(guān)系判斷，并定期將Skyline查詢處理的中間狀態(tài)信息保存到協(xié)調(diào)節(jié)點(diǎn)，具體步驟如下：

2.4.3.1判斷本地原始數(shù)據(jù)集Set中的數(shù)據(jù)對象DO與本地原始數(shù)據(jù)集Set中的所有其他數(shù)據(jù)對象之間的控制關(guān)系，如果數(shù)據(jù)對象DO不被本地原始數(shù)據(jù)集Set中任意一個其他數(shù)據(jù)對象所控制，則將數(shù)據(jù)對象DO放入計(jì)算節(jié)點(diǎn)的Skyline集合LS中，即，LS＝LS+{DO}，同時更新計(jì)數(shù)器ε，ε＝ε+1；

2.4.3.2如果計(jì)數(shù)器ε＝θ，θ的取值范圍是[100，1000]中的正整數(shù)，則將該計(jì)算節(jié)點(diǎn)的狀態(tài)標(biāo)記Status設(shè)置為“Continue”，然后將狀態(tài)標(biāo)記Status、數(shù)據(jù)對象DO在本地原始數(shù)據(jù)集Set中的當(dāng)前位置和Skyline集合LS保存到協(xié)調(diào)節(jié)點(diǎn)；

2.4.3.3如果計(jì)數(shù)器ε＜θ，且本地原始數(shù)據(jù)集Set中的所有數(shù)據(jù)對象都已進(jìn)行2.4.3.1中的處理，則將該計(jì)算節(jié)點(diǎn)的狀態(tài)標(biāo)記Status設(shè)置為“Complete”，然后將狀態(tài)標(biāo)記Status和Skyline集合LS保存到協(xié)調(diào)節(jié)點(diǎn)；

2.4.4查詢處理程序?qū)kyline集合LS返回給協(xié)調(diào)節(jié)點(diǎn)；

第三步，協(xié)調(diào)節(jié)點(diǎn)的結(jié)果分析處理程序收集計(jì)算節(jié)點(diǎn)的Skyline查詢處理結(jié)果，并對其進(jìn)行Skyline查詢處理，得到最終的Skyline查詢結(jié)果：

3.1結(jié)果分析處理程序收集所有計(jì)算節(jié)點(diǎn)的Skyline集合LS；

3.2結(jié)果分析處理程序合并所有計(jì)算節(jié)點(diǎn)的Skyline集合LS，得到新數(shù)據(jù)集NS；

3.3初始化協(xié)調(diào)節(jié)點(diǎn)的Skyline集合

3.4結(jié)果分析處理程序?qū)π聰?shù)據(jù)集NS進(jìn)行Skyline查詢處理，即，判斷新數(shù)據(jù)集NS中的每個數(shù)據(jù)對象N_DO與新數(shù)據(jù)集NS中所有其他數(shù)據(jù)對象之間的控制關(guān)系，如果數(shù)據(jù)對象N_DO不被新數(shù)據(jù)集NS中任意一個其他數(shù)據(jù)對象所控制，那么將數(shù)據(jù)對象N_DO放入?yún)f(xié)調(diào)節(jié)點(diǎn)的Skyline集合GS中；

3.5結(jié)果分析處理程序?qū)kyline集合GS返回給用戶。

2.如權(quán)利要求1所述的面向云計(jì)算環(huán)境的容錯并行Skyline查詢方法，其特征在于所述云計(jì)算環(huán)境配置兩個相同的協(xié)調(diào)節(jié)點(diǎn)，兩個協(xié)調(diào)節(jié)點(diǎn)采用雙機(jī)熱備份的工作模式。