針對大規模數據集交叉比較的分布式計算系統和方法
2023-05-12 23:41:56
針對大規模數據集交叉比較的分布式計算系統和方法
【專利摘要】本發明涉及一種針對大規模數據集交叉比較的分布式計算系統，包括交叉比較編程模型、主結點、編程接口和基於異構分布式機群的後端分布式處理框架。該分布式計算系統旨在應用分布式計算環境高效處理滿足數據集交叉比較模式的計算問題。本發明通過提供用戶直觀的交叉比較編程模型，幫助用戶將待處理計算過程進行抽象簡化，實現了對各種不同交叉比較計算問題的統一支持；提供用戶簡潔的編程接口，幫助用戶開發串行交叉比較程序，用戶無需掌握並行編程知識；系統隱藏了並行計算的實現細節，用戶無需掌握系統內部結構，降低了系統的使用難度。此外，本發明提出的交叉比較編程模型及接口與硬體無關，可以方便的在不同分布式機群環境中實現。
【專利說明】針對大規模數據集交叉比較的分布式計算系統和方法
【技術領域】
[0001]本發明涉及一種針對大規模數據集交叉比較的分布式計算系統和方法，屬於分布式計算【技術領域】。
技術背景
[0002]交叉比較問題又稱為數據集交叉連接或笛卡爾乘積問題，計算空間包括兩個數據集所有元素的可能組合。針對數據集中所有元素進行交叉比較的計算問題廣泛存在於生物計算，數據挖掘和模式識別等領域。比如生物計量學中，為處理人臉識別問題需要對資料庫中海量人臉樣本進行逐一對比得到相似度；生物信息學中，為深入分析物種進化特徵需要對海量DNA，RNA等基因序列進行逐條比對從而得到基因序列關係矩陣；數據挖掘學中，知識挖掘過程中處理噪聲的重要步驟就是對數據集逐項與噪聲進行分析。因此，高效處理此類計算問題具有很重要的科研及商業價值。
[0003]隨著待處理數據規模的不斷增大，數據結構差異化增加，傳統解決方案在應對此類問題時顯出越來越大的局限性。目前的解決方案主要分為兩種，一種設計針對小規模數據集，採用單機處理或在分布式計算平臺中的每個計算結點統一部署全部數據的方法，無法解決海量大數據集交叉比較的問題；另一種方案採用傳統批處理方式將數據集分割打包成任務集由不同的計算結點並行處理完成，此種方案存在計算資源利用率低，總處理能力及擴展能力受限於批處理任務系統，同樣無法高效解決海量大數據集交叉比較的問題。
[0004]對於大規模數據集交叉比較問題，整個計算問題可以被劃分成不同的計算任務被不同的計算結點並行處理，但不同的計算任務可能使用同一子數據集，整個計算問題的描述如圖1所示:
[0005]圖1所示的大規模數據集交叉比較計算問題主要包含兩個計算過程:
[0006]I)數據集中的每一項子數據作為輸入進行預處理計算，得到預處理後的中間結果;
[0007]2)任意兩個不同子數據的預處理後的中間結果作為比較計算的輸入，得到最終比較計算結果。
[0008]在典型的兩數據集交叉比較問題中，整個計算空間如圖2所示，每個星號代表兩個數據集中的元素進行了一次交叉比較運算，對集合和集合，整個過程需要進行次交叉比較運算。
[0009]數據集在進行比較計算之前需要對其中的元素進行預處理計算。相對於比較計算，預處理計算同樣需要大量的計算資源與計算時間。因此數據集元素預處理與元素比較運算構成了交叉比較運算中的主要計算過程。同樣對於集合和集合，整個計算過程可以用以下的偽代碼描述:
[0010]For each item i in data set A
[0011]For each item j in data set B
[0012]其中M表示計算結果矩陣，F表示交叉比較運算，P表示預處理運算。[0013]此外，目前解決方案在使用過程中存在著並行程序開發困難，用戶需要掌握計算平臺內部實現方式，系統只針對解決某一特殊計算問題等缺點。因此，迫切需要研究一種針對海量數據集進行交叉比較的分布式計算系統，既滿足高效處理大規模數據集的需要，又可以為用戶提供簡潔易用的使用接口，同時面向一般性的數據集交叉比較計算問題。
【發明內容】
[0014] 針對現有技術的局限與不足，本發明提供一種針對大規模數據集交叉比較的分布式計算系統。
[0015]本發明還提供一種利用上述分布式計算系統處理數據的方法。
[0016]本發明的技術方案在於:
[0017]一種針對大規模數據集交叉比較的分布式計算系統，包括交叉比較編程模型、主結點、編程接口和基於異構分布式機群的後端分布式處理框架。該分布式計算系統旨在應用分布式計算環境高效處理滿足數據集交叉比較模式的計算問題。本發明通過提供用戶直觀的交叉比較編程模型，幫助用戶將待處理計算過程進行抽象簡化，實現了對各種不同交叉比較計算問題的統一支持；提供用戶簡潔的編程接口，幫助用戶開發串行交叉比較程序，用戶無需掌握並行編程知識；系統隱藏了並行計算的實現細節，用戶無需掌握系統內部結構，降低了系統的使用難度。
[0018]根據本發明優選的，所述的交叉比較編程模型包括四個獨立的計算模塊:數據讀取模塊、數據預處理模塊、數據比較模塊和數據輸出模塊；所述數據讀取模塊為根據計算任務的需要讀取不同的輸入數據；所述數據預處理模塊為預處理輸入數據，生成預處理後的中間計算結果，其中預處理是用戶自定義的處理方法；所述數據比較模塊對兩個不同的預處理後中間計算結果進行比較計算，得到最終計算結果，其中比較計算處理是用戶自定義的比較計算處理方法；所述數據輸出模塊收集生成的最終計算結果，以用戶定義的方式將最終計算結果生成輸出文件。在本發明所述分布式計算系統中的主結點調度下，四個獨立計算模塊在不同子結點協同運行，構成了一個具體的交叉比較計算任務。
[0019]為指導用戶編程，本發明所述分布式系統還提供了 4個編程接口，所述的4個編程接口的使用方法包括步驟(i)-(iv):
[0020](i)用戶創建自定義類並實現此編程接口 ；
[0021](ii)用戶根據具體計算問題定義INDEX(索引)，CRUDEDATA(初始內容)，INTERMEDIATEDATA(預處理後內容)及RESULTDATA(比較結果)的數據類型；
[0022]其中索引值一般為原始輸入數據文件名；初始內容為原始輸入數據；預處理後內容為輸入數據在預處理過程後得到的計算結果；比較結果為輸入數據在進行比較運算後得到的最終計算結果。
[0023](iii)用戶根據具體計算問題編寫算法；
[0024](iv)用戶將編寫完成的類文件提交後端分布式計算處理框架，執行計算任務；
[0025]編程接口如下所示(以JAVA語言示例):
[0026]
public interface ComputingSystem
{[0027]
【權利要求】
1.一種針對大規模數據集交叉比較的分布式計算系統，其特徵在於，該分布式計算系統包括交叉比較編程模型、主結點、編程接口和基於異構分布式機群的後端分布式處理框架。該分布式計算系統旨在應用分布式計算環境高效處理滿足數據集交叉比較模式的計算問題。本發明通過提供用戶直觀的交叉比較編程模型，幫助用戶將待處理計算過程進行抽象簡化，實現了對各種不同交叉比較計算問題的統一支持；提供用戶簡潔的編程接口，幫助用戶開發串行交叉比較程序，用戶無需掌握並行編程知識；系統隱藏了並行計算的實現細節，用戶無需掌握系統內部結構，降低了系統的使用難度。
2.根據權利要求1所述的一種針對大規模數據集交叉比較的分布式計算系統，其特徵在於，所述的交叉比較編程模型包括四個獨立的計算模塊:數據讀取模塊、數據預處理模塊、數據比較模塊和數據輸出模塊；所述數據讀取模塊為根據計算任務的需要讀取不同的輸入數據；所述數據預處理模塊為預處理輸入數據，生成預處理後的中間計算結果，其中預處理是用戶自定義的處理方法；所述數據比較模塊對兩個不同的預處理後中間計算結果進行比較計算，得到最終計算結果，其中比較計算處理是用戶自定義的比較計算處理方法；所述數據輸出模塊收集生成的最終計算結果，以用戶定義的方式將最終計算結果生成輸出文件。
3.根據權利要求1所述的一種針對大規模數據集交叉比較的分布式計算系統，其特徵在於，所述的編程接口分別為Reader編程接口、Preprocess編程接口、Compare編程接口和Writer編程接口: 其中所述Reader編程接口對應數據讀取模塊，用戶自定義讀入數據的INDEX(索引)及CRUDEDATA(初始內容)類型，並且自定義讀入數據的讀入方式及數據類型； 所述PrepiOcess編程接口對應數據預處理模塊，用戶只需關注讀入數據內容的預處理過程，定義INTERMEDIATEDATA(預處理後內容)類型； 所述Compare編程接口對應數據比較模塊，用戶只需關注兩個不同預處理後數據的比較過程，定義RESULTDATA(比較結果)； 所述Writer編程接口對應數據輸出模塊，用戶自定義輸出數據的格式及形式。
4.根據權利要求1所述的一種針對大規模數據集交叉比較的分布式計算系統，其特徵在於，所述基於異構分布式機群的後端分布式處理框架，包括作業調度器、任務執行器、分布式機群資源管理系統和分布式文件系統: 其中作業調度器運行於分布式機群主結點(Master結點)，用戶在提交計算作業後，作業調試器根據整個分布式機群中空閒資源情況，作業對資源的需求及待處理數據集的存儲情況生成計算任務隊列，依據任務分配策略將不同任務發布到各個從結點中； 其中任務執行器運行於分布式機群從結點(Slaves結點)，任務執行器在接收到相應任務之後啟動子任務處理過程，依照用戶編寫的方法進行數據的讀入，預處理，比較和輸出操作； 其中分布式機群資源管理系統運行於分布式機群所有結點，起到管理分布式機群中所有結點計算機，監控資源利用情況，控制結點之間通信及數據傳輸，及處理結點故障的作用； 其中分布式文件系統運行於分布式機群所有結點，用於存儲輸入數據集及最終輸出結果O
5.一種利用如權利要求1所述分布式計算系統處理數據的方法，其特徵該方法包括步驟如下: (1)用戶分析具體計算問題； (2)用戶應用本發明所述分布式計算系統所提供的編程接口，分別實現四個獨立的計算模塊:數據讀取模塊、數據預處理模塊、數據比較模塊和數據輸出模塊的具體處理方法，包括步驟(a)-(d): (a)數據讀入階段:在此階段，子任務執行所需要的子數據集從分布式文件系統中被讀入，數據集中的每一項輸入文件在本發明所述的分布式計算系統中以索引A、初始內容的方式存儲； (b)數據預處理階段:在此階段，步驟(1)中讀入的數據按照用戶自定義的處理方法進行預處理，得中間計算結果在本發明所述的分布式計算系統中以索引A、預處理後內容的方式存儲； (C)數據比較階段:在此階段，用戶自定義的比較計算處理方法從步驟(2)的中間計算結果中取出兩個不同數據進行比較計算，得最終計算結果在本發明所述的分布式計算系統中以索引A、索引B和比較結果的方式存儲；其中索引A，B分別對應兩個不同的輸入文件的索引； (d)數據輸出階段:在此階段，所述數據輸出模塊收集生成的最終計算結果，以用戶定義的方式將最終計算 結果生成輸出文件； (3)用戶編寫包括以上四個獨立的計算模塊的類文件、確定輸入數據集大小、分布式系統結點數量和各結點空閒資源情況，在後端分布式處理框架中進行設置； (4)將應用前端編程接口定義的處理方法及待處理數據上傳至後端分布式處理框架，其中數據存儲至分布式文件系統中； (5)後端分布式處理框架在主結點啟動作業調度器，分析用戶計算問題，自動生成相互獨立的子任務集並將任務分配至不同從結點；在各個從結點啟動任務執行器，從分布式文件系統中讀取相應數據，執行具體子任務；當所有子任務執行完成後，後端分布式處理框架結束計算任務，輸出最終結果並存入分布式文件系統中。
【文檔編號】G06F9/44GK103942235SQ201310178513
【公開日】2014年7月23日 申請日期:2013年5月15日 優先權日:2013年5月15日
【發明者】張一凡 申請人:張一凡