[發明專利]一種面向云計算環境的容錯并行Skyline查詢方法

有效

• 申請號: 201110205925.6
• 申請日: 2011-07-22
• 公開（公告）號: CN102254016A
• 公開（公告）日: 2011-11-23
• 發明（設計）人: 王意潔;王媛;鄧瑞鵬;裴曉強;李小勇;楊永滔;孫偉東
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F11/07
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

技術領域

本發明涉及Skyline查詢的分布并行處理方法，尤其是面向云計算環境的容錯并行Skyline查詢方法。

背景技術

Skyline查詢是海量數據管理領域亟待解決的核心問題之一。Skyline查詢是指從給定的一個D維的數據對象集合S中選擇一個子集，該子集中的任意一個數據對象都不能被S中的任意一個其他數據對象所控制。所謂控制關系是指在D維的數據對象集合S中，如果數據對象p至少在某一維度上優于另一個數據對象q，而且數據對象p在其他維度上都不比數據對象q差(p優于或等于q)，那么數據對象p能夠控制數據對象q。Skyline查詢是目前解決多目標優化問題的典型方法之一，Skyline查詢已經成為數據分析和信息提取的重要技術手段，在城市導航、市場分析、環境監控等諸多領域都有著重要應用。

近年來，隨著計算機技術、網絡技術和通信技術的快速發展，人們獲取、存儲和傳遞數據的能力日益增強，數據的規模急劇膨脹，“大數據”作為信息爆炸的產物應運而生。隨著數據集規模的不斷增大，Skyline查詢的數據處理變得更加復雜，對存儲資源和計算資源的需求也急劇增長，Skyline查詢的處理效率逐漸成為影響數據分析和信息提取效果的關鍵因素。

隨著集群計算、網格計算、P2P計算等網絡計算模式的不斷發展，分布式并行計算技術已經日趨成熟，并逐漸成為提高海量數據處理效率的有效技術途徑之一。云計算是分布計算、并行計算和網格計算的發展，是一種新的分布式并行計算模式。它將計算任務分布在大量計算機構成的資源池上，使各種應用系統能夠根據需要獲取計算力、存儲空間和各種軟件服務。將云計算技術與海量數據的Skyline查詢相結合，可以通過開發查詢計算的并行性來提高查詢處理效率。

盡管隨著技術的進步，各種軟硬件資源的可靠性得到了顯著提高，但是，隨著云計算的資源規模的不斷擴大，資源的失效概率明顯上升。此外，為了有效降低維護成本，失效資源不是及時更新，而是成批維護的。在云計算環境下，資源失效是一種常態行為。

現有的Skyline查詢方法主要關注查詢處理過程及其查詢結果的正確性，無法及時處理節點失效情況。因此，如何針對海量數據及其Skyline查詢的本質特點，結合云計算環境的資源特點，設計高效率低成本的容錯并行Skyline查詢方法，保證Skyline查詢處理的效率和查詢結果的正確性，已經成為并行與分布處理領域的熱點研究問題。

發明內容

本發明要解決的技術問題是：針對現有的Skyline查詢方法無法有效處理查詢處理過程中的節點失效的問題，提出一種面向云計算環境的容錯并行Skyline查詢方法，有效控制故障對分布并行Skyline查詢處理過程的影響，有效保證Skyline查詢處理的效率和查詢結果的正確性。

本發明技術方案包括以下步驟：

第一步，構建一個云計算環境，它由多個節點構成，每個節點都是一臺可獨立運行的計算機，各節點通過網絡設備互連。

云計算環境中的節點分為三類：協調節點、計算節點和備份節點。云計算環境包括一個協調節點，負責與用戶交互，接收用戶提交的查詢請求，向各計算節點分發查詢處理任務和收集查詢處理結果，并向用戶返回查詢結果。云計算環境包括N個計算節點(N為正整數)，它們負責存儲原始數據集并執行查詢處理任務，并向協調節點返回查詢處理結果。為了降低容錯成本，采用冷備份方式對計算節點進行容錯處理，以避免計算節點故障對Skyline查詢處理的影響。每個計算節點配置一個備份節點，計算節點上的原始數據集的副本存儲在其備份節點上。協調節點、計算節點和備份節點上均安裝有操作系統、TCP/IP協議軟件，配置了網絡環境。

協調節點上安裝有任務調度程序、結果分析處理程序和故障處理程序。任務調度程序接收用戶提交的Skyline查詢請求，向各計算節點分發Skyline查詢處理任務。結果分析處理程序負責收集計算節點的Skyline查詢處理結果，并對收集到的所有計算節點的Skyline查詢處理結果再進行Skyline查詢處理以得到最終的Skyline查詢結果。故障處理程序負責定期對計算節點進行故障檢測，并進行故障修復。計算節點和備份節點上均安裝有查詢處理程序。查詢處理程序負責接收來自協調節點的Skyline查詢請求，并對計算節點或者備份節點上存儲的原始數據集進行Skyline查詢處理。