最優化映射減少框架中數據處理的裝置和方法
2023-05-20 15:02:21 4
最優化映射減少框架中數據處理的裝置和方法
【專利摘要】由本發明的方法最優化、由主節點實現的用於大規模數據的映射減少框架。該方法包括在指向由工人節點執行的任務的輸入數據的讀取指針位置上的這些工人節點的數據的接收以及從這些任務接收工作，被竊取的該工作被應用於輸入數據，該輸入數據尚未被工作從其竊取的任務處理。
【專利說明】最優化映射減少框架中數據處理的裝置和方法
【技術領域】
[0001]當前發明涉及映射減少(MapReduce)框架中的數據處理。該映射減少模型在谷歌公司開發，作為使能大規模數據處理的方式。
【背景技術】
[0002]映射減少是用於處理大數據集合的編程模型，並且谷歌的該模型的實現的名字映射減少通常對計算機集群進行分布式計算。該模型受通常在功能編程中使用的「映射(map)」和「減少(reduce)」功能啟發。映射減少包括「映射」步驟，其中主節點在每一個均處理特定的子任務的映射任務中建立問題的分支，並且分配這些映射任務給工人節點(worker node)。這個主任務還稱作「安排(scheduling)」任務。對於此,主節點劃分問題輸入數據並且將每個輸入數據部分分配到映射任務。工人節點處理子問題，並在映射任務完成時通知主節點。映射減少還包括「減少」步驟，其中主節點向一些工人節點分配「減少」操作，其收集全部子問題的答案並且將它們以某種形式組合以形成輸出，即原始試圖解決的問題的答案。
[0003]映射減少允許映射和減少操作的分布式處理。所提供的每一個映射操作都獨立於其他映射操作，並且可以並行地進行映射。類似地，「減少器」的集合可以進行操作相。雖然此處理相比於更加順序的算法可能顯得不高效，但是映射減少可以應用於比商用伺服器可以處理的數據集合明顯更大的數據集合一大型伺服器公司可以使用映射減少來僅在若干小時內分類千兆字節(petabyte)的數據；映射減少通常適宜於處理「大數據」。並行化也提供在操作期間從伺服器或貯存的部分故障中恢復的一些可能性:如果一個映射器或減少器出現故障，則工作可以重安排一假定輸入數據仍然可用。映射減少的流行的開源實現是Apache Hadoop。(來源:維基百科)。
[0004]映射減少依賴於任務的「靜態」分割來易化主機的安排並且增加容錯。任務的靜態分割由主機節點「安排器」任務來處理。詞組「靜態」在上下文中意味著在執行之前將任務分割為同樣大小的較小任務。作為程序/功能和輸入數據分割任務的組合的任務由分割輸入數據為部分並且創建在各個所分割數據部分上應用程式的若干任務。
[0005]Blumofe等在他們的論文，在F0CS1994(Annual IEEE Symposium on Foundationsof Computer Science)上 的「Scheduling Multithreaded Computations by WorkStealing」中描述了處理器從其他處理器竊取工作的工作竊取的有益效果。此技術良好的適宜於處理異構任務。然而，它限於在相關任務之間竊取工作，例如，在線程之間的具有共享存儲器的單一機器上執行的任務。技術不能應用於映射減少，因為映射減少方式有賴於如下假設:任務是獨立的，而這允許了輸入數據的靜態分割以改進規模和容錯。
[0006]為了處理「離群者(straggler)」(即，緩慢地計算並且降低了數據處理系統的性能的機器)，映射減少包括公知為「推測執行」的機制，包括在任務的拷貝的同時執行中，期望任務的之一將比其他任務更快地執行。此改進允許了在使用異構資源的環境中的性能增益。不適宜於異構地處理任務，即一些任務可能要求比其他任務更多的計算能力。[0007]美國Indiana University of Bloomington 的 Guo 等人在他們的文章「ImprovingMapReduce Performance in Heterogenous Network Environments and ResourceUt i I i sat ion 」中描述了，在映射減少中，映射和減少任務被分配給由工人節點擁有的映射和減少「時隙(slot)」。每一個工人包括任務向其分配的用戶可配置數量的映射和減少時隙。對每一個時隙保留潛在資源的部分。當全部時隙同時使用時，資源使用率是最優的。然而，千節點的谷歌計算簇(production cluster)的收集的使用率數據示出CPU利用率在大多數時候遠不及最優。作者承認如同在Hadoop中應用的映射減少方式中的資源利用率在沒有足夠任務來填充全部任務時隙的時候是不高效的。每一個工人節點具有可以以每節點為基礎由用戶配置的映射和減少時隙。當不存在足夠的任務來填充全部任務時隙時，浪費了保留的資源。為了改進映射減少性能，Guo等人提出了資源竊取並使能允許的任務竊取保留的「空閒」資源用於「推測執行」(即，相同任務(「複製」，或「競爭」任務)的並行執行)以處理執行裝置的異構；對於一些任務Tl到Tn的每一個，重執行任務(之前提及的「推測執行」)以使得任務的總數變得等於時隙的數量。重執行任務使用為「空閒」時隙保留的資源。
[0008]改進處理速度的這些現有技術效果通過上述靜態分割始終受限。映射減少中的當前途徑是調諧與此靜態分割有關的參數以便於改進負載平衡並且最終改進數據處理的性能。然而，此策略要求技術人員的介入，因為它要求要處理輸入數據的正確了解。必須處理輸入在大小上太小的未被分割為塊的輸入數據，因為添加映射任務增加了對每一個分割任務要求的開銷。開銷的示例是:同步的時間，轉移和啟動任務、傳輸結果和合併全部結果的時間。
[0009]改進性能的再一策略是與Guo所討論的「資源竊取」相對的、稱為「工作竊取」的策略。Al-Obaidi等在他們的文章2012年7月3-5日的ICCCE2012的「A partial multistealing scheduling model for divide and conquer problems，，，中討論了工作竊取。然而，Al-Obaidi等討論的工作竊取目標在於多核處理器架構，並且討論了通過任務線程的竊取來將其給予未使用處理器核心的工作竊取。此工作竊取策略設計用於多線程任務和多核處理器，並且不能導致非多線程任務或在單一核心節點上的更快執行。此外，該策略受未使用處理器核心的數量限制。最終，Al-Obaidi等類似於Blumofe等。全部這些不利使得這些策略對於映射減少模型中的應用不是最優的。
[0010]現有技術涉及任務執行的最優化，已經提出了任務的靜態分割。這不是最優的，因為靜態分割不考慮不同分割任務之間以及不同執行節點之間的異構性。將會有利的是提出基於動態適應任務和節點異構性兩者的方法的映射減少。
[0011 ] 因此，需要現有技術解決方案的進一步最優化。
【發明內容】
[0012]本發明旨在減輕現有技術的一些不便。
[0013]為此，本發明包括用於在映射減少框架中的處理數據的方法，所述方法由主節點執行，並且包括將輸入數據分割為輸入數據片段；向工人節點分配用於處理輸入數據片段的任務，其中向每一個工人節點分配用於處理輸入數據片段的任務；根據從執行任務的工人節點接收的數據確定，指向由任務處理的輸入數據片段中的當前讀取位置的讀取指針是否尚未達到輸入數據片段結尾之前預定閾值；並且將新任務分配給空閒的工人節點，新任務被歸於由在尚未達到輸入數據片段結尾之前預定閾值的所述任務尚未處理的輸入數據片段的、稱為分割部分的部分，該分割部分是位於在當前讀取指針位置之後的輸入數據片段的一部分。
[0014]根據本發明的變形實施例，所述方法的最後步驟從屬於根據從任務接收的數據確定輸入每個任務的數據處理速度以及數據處理速度低於權利要求1的最後步驟的執行的數據處理速度閾值的每一個任務，該數據處理速度從根據從工人節點接收的數據獲得的後續讀取指針確定。
[0015]根據本發明的變形實施例，本發明進一步包括向執行尚未達到輸入數據片段結尾之前預定閾值的任務的工人節點傳輸消息的步驟，該消息包含了用於更新對由該消息向其傳輸的工人節點執行的任務的輸入數據片段的信息。
[0016]根據本發明的變形實施例，所述方法進一步包括在輸入數據流中插入End OfFile標記的步驟，向任務提供該輸入數據流用於將輸入數據的處理限制在位於分割部分之前的輸入數據片段的一部分。
[0017]根據本發明的變形實施例，所述方法進一步包括在主節點中更新安排表，所述安排表包括允許工人節點與分配給它的任務之間的關聯並且定義分配給它的任務的輸入數據片段部分開始和結束的信息。
[0018]根據本發明的變形實施例，所述方法進一步包括處理輸入數據片段的非重疊部分的任務的推測執行。
[0019]本發明還應用於用於處理映射減少框架中的數據的主裝置，該裝置包括用於將輸入數據分割為輸入數據片段的部件；用於向工人節點分配用於處理輸入數據片段的任務的部件，其中向每一個工人節點分配用於處理輸入數據片段的任務；用於根據從執行任務的工人節點接收的數據確定，指向由任務處理的輸入數據片段中的當前讀取位置的讀取指針是否尚未達到輸入數據片段結尾之前預定閾值的部件；以及將新任務分配給空閒的工人節點的部件，新任務被歸於由在尚未達到輸入數據片段結尾之前預定閾值的所述任務尚未處理的輸入數據片段的、稱為分割部分的部分，該分割部分是位於在當前讀取指針位置之後的輸入數據片段的一部分。
[0020]根據根據本發明的裝置的變形實施例，所述裝置進一步包括用於根據從任務接收的數據確定輸入每個任務的數據處理速度的部件，以及確定數據處理速度是否低於數據處理速度閾值的部件，該數據處理速度從根據從工人節點接收的數據獲得的後續讀取指針確定。
[0021]根據根據本發明的裝置的變形實施例，所述裝置進一步包括向執行尚未達到輸入數據片段結尾之前預定閾值的任務的工人節點傳輸消息的部件，該消息包含了用於更新對由該消息向其傳輸的工人節點執行的任務的輸入數據片段的信息。
[0022]根據根據本發明的裝置的變形實施例，所述裝置進一步包括在輸入數據流中插入End Of File標記的部件，向任務提供該輸入數據流用於將輸入數據的處理限制在位於分割部分之前的輸入數據片段的一部分。
[0023]根據根據本發明的裝置的變形實施例，所述裝置進一步包括用於在主節點中更新安排表的部件，所述安排表包括允許工人節點與分配給它的任務之間的關係並且定義分配給它的任務的輸入數據片段部分開始和結束的信息。
[0024]根據根據本發明的裝置的變形實施例，所述裝置進一步包括用於處理輸入數據片段的非重疊部分的任務的推測執行的部件。
【專利附圖】
【附圖說明】
[0025]通過本發明的特定、非限制實施例的描述，本發明的更多優勢將顯現。將參考以下附圖描述實施例:
[0026]圖1是示出現有技術映射減少方法的原理的框圖。
[0027]圖2是用於根據映射減少方式的數據處理的現有技術大規模數據處理系統的框圖。
[0028]圖3是根據映射減少方法的數據處理的現有技術方法的流程圖。
[0029]圖4是圖示由主節點完成的映射任務的圖3的流程圖的細節。
[0030]圖5是表示處理輸入數據的工人的框圖。
[0031]圖6是根據本發明的非限制性變型實施例的映射任務的流程圖。
[0032]圖7是圖示根據本發明的非限制性實施例的輸入數據文件的分割的框圖。
[0033]圖8是根據本發明的裝置的非限制性示例實施例的框圖。
[0034]圖9是圖示根據本發明的非限制性變型實施例的順序圖。
[0035]圖10是根據非限制性示例實施例的本發明的方法的流程圖。
[0036]為了促進理解，在可以指定對於示圖共同的一致的元素的地方使用一致的附圖編號。
【具體實施方式】
[0037]圖1是示出現有技術映射減少方法的原理的框圖(來源:維基百科)。
[0038]「主」節點101 (經由箭頭1000)獲得輸入數據(「問題數據」)100，並且在「映射」步驟1010中，將其劃分為較小的子問題，它們被分發給「工人」節點102-105 (箭頭1001、1003、1005)。工人節點處理該較小問題(箭頭1002、1004、1006)並且向主節點通知任務完成。在「減少」步驟1011，主節點將「減少」操作分配給一些工人節點，其收集全部子問題的答案並且將它們以某種形式組合以形成輸出(「解決方案數據」)106 (經由箭頭1007)。
[0039]圖2是根據映射減少方式的現有技術大規模數據處理系統的框圖。與圖1共同的元素已經對該圖解釋了，並且不在此再度解釋。主處理201分割在文件Fl到Fn (1000)中存儲的問題數據100，該問題數據100分發給分配給了工人節點202-205的任務。主處理還負責向工人節點(類似工人節點210-211)分配減少任務。節點202-205產生中間數據值2000，其被收集並且寫入中間文件a (206)、b (207)到η (209)。當向主節點通知中間結果被獲得時，主節點分配減少任務給工人節點210-211。這些處理從中間文件206-209取回輸入數據(2001)，合併並且組合數據，並且存儲(2002)產生的解決方案數據106。適於由映射減少處理的典型問題的示例是購物網站的客戶的性別和平均年齡的統計。輸入數據100則是購物網站的客戶購買資料庫。具有大量商業成功的網站，其客戶資料庫是龐大的一若干兆兆字節(terabyte)數據。數據存儲在文件Fl-Fn中。主進程以64M字節的片段分割每一個文件。藉助工人節點的列表，主節點建立了安排表，其將輸入數據的每一個片段歸於一個任務和一個工人節點。根據我們的情形，要由工人節點執行的任務是兩個:計算男性/女性買家的數量以及計算買家的平均年齡。每一個工人節點202到205存儲其中間結果在中間文件206-209的一個中。例如，中間文件「a」206包括來自第一文件片段Fl的女性客戶的數量和客戶的平均年齡，而中間文件「b」 207包括第二文件片段Fl的女性客戶的數量和平均年齡，而中間文件「η」 206包括通過第η文件片段「η」的女性客戶的數量和客戶平均年齡。當向主節點通知工人202-205已經完成它們的任務時，他分配減少任務給工人節點，諸如工人210-211.。這些工人執行減少任務，讀取中間文件「a」到「η」的內容，產生存儲在解決方案數據106中的兩個結果輸出，即女性客戶的數量和平均客戶年齡。
[0040]圖3是主進程的流程圖。
[0041]在初始化步驟301，進程需要的變量和參數被初始化。在步驟302，主節點將輸入文件分割為通常幾十兆字節的片段(例如，16或64Μ字節)，這個是由用戶經由可選參數可控制的。然後，在步驟303，主節點驗證是否存在空閒工人節點。如果沒有，則步驟循環。如果存在空閒(或「自由」)工人節點，則主節點在步驟305驗證對於空閒工人節點是否仍存在要完成的映射任務；如果存在，則主節點指令該空閒工人節點開始這些映射任務(箭頭3001和步驟304)，並且隨後經由箭頭3000返回步驟303。如果不存在要完成的映射任務了，則在步驟306開始減少任務。如果這些完成了，則以步驟307完成進程。
[0042]以下表1給出了由主節點保持的現有技術主節點任務安排表的示例。
[0043]
【權利要求】
1.一種用於處理映射減少框架中的數據的方法，其特徵在於所述方法由主裝置(800，900)執行，並且在於所述方法包括: 將輸入數據分割(10001)為輸入數據片段； 向工人節點分配(10002)用於處理所述輸入數據片段的任務，其中向每一個工人節點分配用於處理輸入數據片段的任務； 根據從執行所述任務的工人節點(901，902,903)接收的數據確定(10003)指向由任務處理的輸入數據片段中的當前讀取位置的讀取指針是否尚未達到輸入數據片段結尾之前的預定閾值；並且 將新任務分配(10004)給空閒的工人節點，新任務被歸於由在尚未達到輸入數據片段結尾之前預定閾值的所述任務尚未處理的輸入數據片段的、稱為分割部分的部分，所述分割部分是位於所述當前讀取指針位置之後的所述輸入數據片段的一部分。
2.根據權利要求1所述的方法，其中權利要求1的方法的最後步驟從屬於根據從所述任務接收的所述數據確定(3047)每個任務的輸入數據處理速度的步驟，並且對於數據處理速度低於數據處理速度閾值的每一個任務執行權利要求1的最後步驟，所述數據處理速度根據從工人 節點接收的數據獲得的後續讀取指針確定。
3.根據權利要求1或2所述的方法，包括向執行在尚未達到輸入數據片段結尾之前預定閾值的任務的工人節點傳輸消息的步驟，該消息包含了用於更新由向其傳輸該消息的工人節點執行的任務的輸入數據片段結尾的信息。
4.根據權利要求1或2所述的方法，包括在向任務提供的輸入數據流中插入EndOfFile標記，用於將輸入數據的處理限制在位於所述分割部分之前的輸入數據片段的部分。
5.根據權利要求1到2的任一所述的方法，包括在所述主節點中更新安排表，所述安排表包括允許工人節點與分配給它的任務之間的關聯並且定義分配給它的任務的輸入數據片段部分開始和結束的信息。
6.根據權利要求1到2的任一所述的方法，其中所述方法包括處理輸入數據片段的非重疊部分的任務的推測執行。
7.一種於用於處理映射減少框架中的數據的主裝置，其特徵在於所述主裝置包括: 用於將輸入數據分割為輸入數據片段的部件； 用於向工人節點分配用於處理輸入數據片段的任務的部件，其中向每一個工人節點分配用於處理輸入數據片段的任務； 用於根據從執行任務的工人節點接收的數據確定，指向由任務處理的輸入數據片段中的當前讀取位置的讀取指針是否尚未達到輸入數據片段結尾之前預定閾值的部件；以及 將新任務分配給空閒的工人節點的部件，新任務歸於由尚未達到輸入數據片段結尾之前預定閾值的任務尚未處理的輸入數據片段的、稱為分割部分的部分，所述分割部分是位於在當前讀取指針位置之後的輸入數據片段的一部分。
8.根據權利要求7所述的主裝置，其中所述主裝置進一步包括用於根據從任務接收的數據確定每個任務的數據輸入處理速度的部件，以及確定數據處理速度是否低於數據處理速度閾值的部件，所述數據處理速度根據從工人節點接收的數據獲得的後續讀取指針確定。
9.根據權利要求7或8所述的主裝置，包括向執行尚未達到輸入數據片段結尾之前預定閾值的任務的工人節點傳輸消息的部件，該消息包含了用於更新由向其傳輸該消息的工人節點執行的任務的輸入數據片段結尾的信息。
10.根據權利要求7或8所述的主裝置，包括在向任務提供的輸入數據流中插入EndOf File標記的部件，用於將輸入數據的處理限制在位於分割部分之前的輸入數據片段的部分。
11.根據權利要求7到8的任一所述的主裝置，包括用於在所述主節點中更新安排表的部件，所述安排表包括允許工人節點與分配給它的任務之間的關聯並且定義分配給它的任務的輸入數據片段部分開始和結束的信息。
12.根據權利要求7到8的任一所述的主裝置，其中所述主裝置包括用於處理輸入數據片段的非重疊部分的任務的推`測執行的部件。
【文檔編號】G06F9/48GK103885835SQ201310711298
【公開日】2014年6月25日 申請日期:2013年12月20日 優先權日:2012年12月20日
【發明者】N.勒斯庫阿內克, E.勒莫爾 申請人:湯姆遜許可公司