基於MapReduce編程架構的任務分配方法及裝置的製作方法
2023-05-26 20:20:31
專利名稱：基於MapReduce編程架構的任務分配方法及裝置的製作方法
技術領域：
本發明涉及網絡通信領域，尤其涉及一種基於MapReduce編程架構的任務分配方 法及裝置。
背景技術：
隨著高性能應用和運算需求的迅猛發展，單臺高性能計算機已經不能解決一些超 大規模應用問題，這就需要將多臺計算機資源聯合起來，構成計算機集群，共同解決大規模 應用問題。並行編程技術可以有效地開發並行計算機尤其是集群計算機的計算能力，是硬 件和軟體之間的橋梁，是並行計算的低層實現與高層抽象的界面。 現有技術所提供的一種基於MapReduce編程架構的任務分配方法，該方法具體包 括，將對海量數據的計算任務分為K個子任務，然後一次性分配到各個節點(計算機)上進 行計算處理。 在實現本發明的過程中，發明人發現現有技術存在如下問題 由於現有技術提供的技術方案是一次性分配到各個節點(計算機)上進行計算處 理，其僅考慮了任務分配，並沒有考慮在任務執行過程中，由於節點(計算機)資源的動態 變化帶來的負載失衡的問題。
發明內容
本發明實施方式提供一種基於MapReduce編程架構的任務分配方法及裝置，所述 方法和系統具有負載均衡，避免任務重複轉移，防止系統抖動的優點。 本發明的具體實施方式
提供一種基於MapReduce編程架構的任務分配方法，所述 方法包括 在判斷出空閒時，發送空閒消息，並接收所述空閒消息的響應消息，所述響應消息 包括需要轉移的任務量和所述任務量所對應的節點地址；在判斷出所述需要轉移的任務量 小於剩餘能力時，將所述需要轉移的任務量對應的節點地址存儲在過載節點列表中，向所 述過載節點列表中的一個節點地址發送任務轉移請求消息，接收轉移的任務並進行計算處
理5或 在判斷出過載且未進行任務轉移時，回復所接收到的空閒消息的響應消息；在收 到任務轉移請求消息後，將轉移的任務發送給所述任務轉移請求消息所對應的節點。
本發明具體實施方式
還提供一種基於MapReduce編程架構的任務分配裝置，所述 裝置包括 判斷單元，用於判斷空閒或過載； 發送單元，用於在所述判斷單元判斷出空閒時，發送空閒消息； 接收單元，用於接收所述空閒消息的響應消息，所述響應消息包括需要轉移的任
務量和所述任務量所對應的節點地址； 存儲單元，用於在所述需要轉移的任務量小於剩餘能力時，將所述需要轉移的任務量對應的節點地址存儲在過載節點列表中， 所述發送單元還用於向所述過載節點列表中的一個節點地址發送任務轉移請求 消息， 所述接收單元還用於接收轉移的任務； 計算單元，用於對所述轉移的任務進行計算處理； 所述判斷單元判斷出過載且未進行任務轉移時；通知所述發送單元回復接收到的 空閒消息的響應消息； 任務轉移單元，用於在所述接收單元收到任務轉移請求消息後，將轉移的任務發 送給所述任務轉移請求消息所對應的節點。 由上述所提供的技術方案可以看出，本發明實施例的技術方案將過載節點的任務 轉移到空閒節點，從而實現了在任務執行的過程中，對任務的動態分配，從而達到了負載均 衡；上述方法轉移的任務不會大於接收節點的剩餘能力，所以該方法能夠避免由於任務轉 移而出現的接收節點過載的情況，從而避免了接收節點由於過載將轉移的任務再次轉移到 其他的節點，從而防止了系統的抖動；上述方法在過載情況進行任務轉移時，由於該過載節 點之前未進行任務轉移，所以其可以避免將需要轉移的任務重複轉移。
圖1為本發明具體實施方式
提供的一種並行計算中的任務分配方法的流程圖。
圖2為本發明一實施例提供的一種並行計算中的任務分配方法的流程圖。
圖3為本發明具體實施方式
提供的一種並行計算中的任務分配裝置的結構圖。
具體實施例方式
本發明實施方式提供了一種基於M即Reduce編程架構的任務分配方法，該方法包 括，在判斷出空閒時，發送空閒消息，並接收該空閒消息的響應消息，該響應消息包括需要 轉移的任務量和該任務量所對應的節點地址；在判斷出該需要轉移的任務量小於剩餘能力 時，將該需要轉移的任務量對應的節點地址存儲在過載節點列表中，向該過載節點列表中 的一個節點地址發送任務轉移請求消息，接收轉移的任務並進行計算處理；或，在判斷出過 載且未進行任務轉移時，回復接收到的空閒消息的響應消息，該響應消息包括需要轉移的 任務量和節點地址；在收到任務轉移請求消息後，將轉移的任務發送給該任務轉移請求消 息所對應的節點。上述方法均可以由節點(worker)完成。上述方法將過載節點的任務轉移 到空閒節點，從而實現了在任務執行的過程中，對任務的動態分配，從而達到了負載均衡； 上述方法轉移的任務不會大於接收節點的剩餘能力，所以該方法能夠避免由於任務轉移而 出現的接收節點過載的情況，從而避免了接收節點由於過載將轉移的任務再次轉移到其他 的節點，從而防止了系統的抖動；上述方法在過載情況進行任務轉移時，由於該過載節點之 前未進行任務轉移，所以其可以避免將需要轉移的任務重複轉移。 本發明具體實施方式
提供一種基於M即Reduce編程架構的任務分配方法，該方式
是基於M即Reduce編程架構來實現的，該方法如圖l所示，包括如下步驟 步驟11、判斷是否空閒，如是則進行步驟12 14，否則為過載，則進行步驟15 16。
實現該步驟的方法可以由節點完成，其實現的具體方法可以為，節點獲取自身的 負載值，然後計算出本節點的閥值，如負載值小於閥值則說明本節點空閒，否則為過載。計 算出本節點的閥值的具體方法可以為， 閾值TA= (utl+ e ) X(;，其中utl =系統內各個節點的負載值的和/系統內各個 節點的負載能力值的和，e為可調參數，(；為本節點的負載值。該系統可以為一個master 以及master下的所有節點。該負載值、負載能力值可以為節點中CPU或內存的使用情況。
步驟12、向物理位置相近的節點發送空閒消息，並接收該空閒消息的響應消息，該 響應消息包括需要轉移的任務量和該任務量所對應的節點地址。 該步驟中的物理位置相近的節點可以為，IP位址段相近，當然也可以通過網絡定 位或發PIN消息等方式來判斷物理位置相近的節點。 步驟13、如接收到的需要轉移的任務量小於剩餘能力，則將該需要轉移的任務量 對應的節點地址存儲在過載節點列表中。 該步驟中的剩餘能力的計算方法可以為，剩餘能力=本節點的閥值減去本節點自 身負載值。 步驟14、向該過載節點列表中的一個節點地址發送任務轉移請求消息，接收轉移 的任務並進行計算處理。 該步驟中的向該過載節點列表中的一個節點地址發送任務轉移請求消息的實現 方式可以為，在過載節點列表中任意選擇一個節點地址發送該任務轉移請求消息，也可以 在過載節點列表中選擇最近的節點地址發送該任務轉移請求消息。該節點地址可以為節點 的IP位址或節點的名稱，當然在實際情況中，也可以為其他的能區分節點的地址，本發明具體實施方式
並不局限該節點地址的具體表現方式。當將該消息選擇最近的節點地址發送 時，可以節約系統的帶寬，並能加快處理的速度。 該步驟中的接收轉移的任務並進行計算處理實現的方式具體可以為，如該轉移的 任務為未執行的任務，則直接計算處理該轉移的任務，如該轉移的任務是執行中的任務，則 獲取執行該任務時的中間數據後，再計算處理該轉移的任務。上述轉移的任務在MapReduce 編程架構中實際可以為map任務或reduce任務。 步驟15、在判斷出未進行任務轉移時，回復接收到的空閒消息的響應消息，該響應 消息包括需要轉移的任務量和節點地址。 步驟16、接收到任務轉移請求消息後，將轉移的任務發送給該任務轉移請求消息 所對應的節點。 可選的，在進行步驟16之後，該方法還可以包括，通知master回收垃圾空間。該
方法通過通知master回收垃圾空間，從而提高了節點存儲空間的利用率。 可選的，該方法在進行步驟11之前，還可以包括，將固定存儲的數據分塊邏輯分
片成多個邏輯小塊，並以邏輯小塊為任務執行和轉移的基本單元。其實現的方法可以為，在
Master中增加邏輯小塊索引數據結構，在需要執行該邏輯小塊的任務時，將該邏輯小塊的
索引發送給執行的節點，該節點根據該索引獲取該邏輯小塊後，進行任務執行，在需要進行
任務轉移時，只需將需要轉移的邏輯小塊的索引發送給接收任務轉移的節點進行執行操作即可。 可選的，該方法在進行計算處理後還可以包括，根據m即任務的個數自行設定多個reduce任務並進行reduce計算，將多個reduce任務的計算結果合併後輸出最終計算結 果。該方法的reduce任務可以由用戶自行設定，所以該reduce任務的個數不受用戶需要 輸出的文件數量的限制。 本發明具體實施方式
提供的方法將過載節點的任務轉移到空閒節點，從而實現了 在任務執行的過程中，對任務的動態分配，從而達到了負載均衡；上述方法轉移的任務不會 大於接收節點的剩餘能力，所以該方法能夠避免由於任務轉移而出現的接收節點過載的情 況，從而避免了接收節點由於過載將轉移的任務再次轉移到其他的節點，從而防止了系統 的抖動；上述方法在過載情況進行任務轉移時，由於是未進行任務轉移，所以其可以避免將 需要轉移的任務重複轉移。該方法在任務轉移後，還可以通知master回收垃圾空間，從而 提高了節點的存儲空間的利用率。並且該方法在進行計算之前，還可以將定存儲的數據分 塊邏輯分片分成更小的邏輯小片，並以邏輯小片為任務執行的基本單元，從而進一步提高 了系統的負載均衡。該方法還可以根據map任務的個數自行設定多個reduce任務並進行 reduce計算，從而使得該方法中reduce任務的個數不受用戶需要輸出的文件數量的限制。
為了更好的說明本發明，現結合具體實施例和附圖來說明本發明的實現方法。
本發明具體實施方式
提供一具體實施例，本實施例提供一種基於MapReduce編程 架構的任務分配方法，本實施例的技術場景為，本實施例中的方法是在MapReduce編程架 構下實現的，本實施例的M即Reduce編程架構假設為， 一個master,三個節點(worker)，為 了敘述的方便，這裡將三個節點分別定義為，worker 1、 worker 2、 worker 3，三個節點對 應的節點地址(這裡以IP位址為例)為IP 1、 IP 2、 IP 3，假設worker 1空閒，worker 2和worker 3過載且均未進行任務轉移，在進行本實施例的方法之前，master預先將 MapReduce編程架構下的底層存儲系統的數據分塊邏輯分片成多個邏輯小塊，並以邏輯小 塊為任務執行和轉移的基本單元，該方法如圖2所示包括如下步驟 步驟21、 worker 1判斷出自身處於空閒狀態，並向worker 2和worker 3發送空 閒消息。 步驟22、worker 2和worker 3在判斷出過載且均未進行任務轉移後，分別回復接 收到的空閒消息的響應消息。 該響應消息包括，worker 2回復的響應消息包括worker 2需要轉移的任務量和 IP 2 ;worker 3回復的響應消息包括worker 3需要轉移的任務量和IP 3。
步驟23、 worker 1接收該響應消息，並判斷需要轉移的任務量是否小於自身的剩 餘能力； 這裡假設worker 2和worker 3需要轉移的任務量均小於worker l的剩餘能力。
步驟24、 worker 1將IP 2和IP 3存儲在過載節點列表中，並在過載節點列表中 選擇最近的節點發送轉移任務請求消息； 假設離worker 1最近的節點為worker 2，則該方法實際為，向IP 2發送轉移任務 請求消息。 步驟25、 worker 2接收到該任務請求消息後，將需要轉移的任務發送給IP 1 ;
實現該步驟的方法可以為，worker 2優先選擇將未被執行的任務發送給IP1，當 然在實際情況中，也可以優選將正在執行中的最後一個任務發送給IP l，當然也可以為其 他的正在執行的任務，這裡假設發送的是正在執行中的最後一個任務發送給IP 1。
步驟26、 worker 1接收到轉移的任務後，判斷出該轉移的任務為執行中的任務， 則從worker 2獲取執行該轉移的任務的中間數據後，繼續計算處理該轉移的任務，並將IP 2從過載節點列表中刪除。 步驟27、 worker 2將轉移的任務和該中間數據發送後，通知master回收垃圾空 間。 可選的，worker 1在執行完步驟26以後，還可以進行下述操作 worker 1繼續判斷剩餘能力是否還大於worker 3需要轉移的任務量，如是則進
行步驟28 29，否則結束操作。 步驟28、 worker 1向IP 3發送轉移任務請求消息； 步驟29、 worker 3接收到該任務轉移請求消息後，向IP 1發送轉移任務，並通知 master回收垃圾空間； 步驟291、 worker 1接收到該轉移任務後，對該轉移任務進行計算處理。 可選的，該方法在執行完步驟291後，還可以包括如下操作，worker 1根據
MapReduce編程架構下的map任務的個數自行設定多個reduce任務並進行reduce計算，將
該多個reduce任務的計算結果根據用戶指定需要輸出的文件數量進行合併後輸出最終計
算結果。 本發明一實施例提供的方法中的worker 1可以根據負載的情況來接收worker 2 轉移的任務，從而達到了根據負載情況來動態轉移任務的目的，具有負載均衡的優點，並且 由於該轉移的任務是以分片後的邏輯小片為基本單元的，所以該轉移的任務的基本單元量 更小，進一步提高了系統的負載均衡的靈活性。並且該方法中worker 1接收該轉移的任務 後，在剩餘能力大於worker 3需要轉移的任務量的情況下，繼續接收worker 3需要轉移的 任務，從而使得系統的負載進一步的均衡和節約了負載均衡引起的資源消耗。該方法中的 worker 1接收該轉移的任務後，不會出現過載的情況，從而避免了由於worker 1過載將轉 移的任務再次轉移到其他的節點，從而防止了系統的抖動。該方法中的worker2和worker 3將轉移任務發送後，通知master回收垃圾空間，從而提高了 worker 2和worker 3的存儲 空間利用率。 本發明具體實施方式
還提供一種基於M即Reduce編程架構的任務分配裝置，該裝 置如圖3所示，包括判斷單元31，用於判斷空閒或過載；發送單元32，用於在判斷單元31 判斷出空閒時，發送空閒消息；接收單元33，用於接收該空閒消息的響應消息，該響應消息 包括需要轉移的任務量和所述任務量所對應的節點地址；存儲單元34，用於在該需要轉移 的任務量小於剩餘能力時，將該需要轉移的任務量對應的節點地址存儲在過載節點列表 中，該發送單元32還用於向該過載節點列表中的一個節點地址發送任務轉移請求消息，接 收單元33還用於接收轉移的任務；計算單元35，用於對該轉移的任務進行計算處理；該判 斷單元31還用於在判斷出過載且未進行任務轉移時，通知該發送單元32回復接收到的空 閒消息的響應消息；任務轉移單元39，用於接收單元33收到任務轉移請求消息後，將轉移 的任務發送給該任務轉移請求消息所對應的節點。
上述裝置還可以包括下述單元中的一種或多種。 可選的，該裝置還可以包括；分片單元36，用於預先將基於M即Reduce編程架構下 的底層存儲系統的數據分塊邏輯分片成多個邏輯小塊，並以邏輯小塊為任務執行和轉移的
8基本單元。 可選的，該裝置還可以包括回收單元37，用於在發送單元32將轉移的任務發送 給所述請求消息所對應的節點之後，通知M即Reduce編程架構下的master回收垃圾空間。
可選的，該裝置還可以包括合併單元38，用於在計算單元35計算處理完之後，根 據MapReduce編程架構下的map任務的個數自行設定多個reduce任務並進行reduce計算， 將所述多個reduce任務的計算結果根據用戶指定需要輸出的文件數量進行合併後輸出最 終計算結果。 可選的，該發送單元32還可以用於在判斷出剩餘能力還大於一個剩餘的需要轉 移的任務量時，向這個剩餘的需要轉移的任務量所對應的節點地址發送任務轉移請求消 息。 本發明具體實施方式
提供的裝置可以將過載節點的任務轉移到空閒節點，從而實 現了在任務執行的過程中，對任務的動態分配，從而達到了負載均衡；上述裝置中轉移的任 務不會大於接收節點的剩餘能力，所以該裝置能夠避免由於任務轉移而出現的接收節點過 載的情況，從而避免了接收節點由於過載將轉移的任務再次轉移到其他的節點，從而防止 了系統的抖動；上述裝置在過載情況進行任務轉移時，由於是未進行任務轉移，所以其可以 避免將需要轉移的任務重複轉移。該裝置在任務轉移後，還可以通過回收單元通知master 回收垃圾空間，從而提高了節點的存儲空間的利用率。並且該裝置在進行計算之前，還可以 通過分片單元將定存儲的數據分塊邏輯分片分成更小的邏輯小片，並以邏輯小片為任務執 行的基本單元，從而進一步提高了系統的負載均衡。該裝置還可以由合併單元根據m即任 務的個數自行設定多個reduce任務並進行reduce計算，從而使得該方法中reduce任務的 個數不受用戶需要輸出的文件數量的限制。 綜上所述，本發明具體實施方式
提供的技術方案，具有負載均衡，防止系統抖動和 避免轉移的任務重複轉移的優點。 以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並不局限於此， 任何熟悉本技術領域的技術人員在本發明實施例揭露的技術範圍內，可輕易想到的變化或 替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應該以權利要求的保護 範圍為準。
權利要求
一種基於MapReduce編程架構的任務分配方法，其特徵在於，所述方法包括在判斷出空閒時，發送空閒消息，並接收所述空閒消息的響應消息，所述響應消息包括需要轉移的任務量和所述任務量所對應的節點地址；在判斷出所述需要轉移的任務量小於剩餘能力時，將所述需要轉移的任務量對應的節點地址存儲在過載節點列表中，向所述過載節點列表中的一個節點地址發送任務轉移請求消息，接收轉移的任務並進行計算處理；或在判斷出過載且未進行任務轉移時，回復所接收到的空閒消息的響應消息；在收到任務轉移請求消息後，將轉移的任務發送給所述任務轉移請求消息所對應的節點。
2. 根據權利要求l所述的方法，其特徵在於，預先將基於M即Reduce編程架構下的底層存儲系統的數據分塊邏輯分片成多個邏輯小塊，並以所述邏輯小塊為任務執行和轉移的基 本單元。
3. 根據權利要求1所述的方法，其特徵在於，所述向所述過載節點列表中的一個節點 地址發送任務轉移請求消息包括在過載節點列表中選擇最近的節點地址發送所述任務轉移請求消息。
4. 根據權利要求1所述的方法，其特徵在於，所述接收轉移的任務並進行計算處理包括如判斷出所述轉移的任務為未執行的任務，則直接計算處理所述轉移的任務； 如判斷出所述轉移的任務是執行中的任務，則獲取執行所述轉移的任務時的中間數據 後，再計算處理所述轉移的任務。
5. 根據權利要求1所述的方法，其特徵在於，所述方法在進行計算處理後，還包括 如判斷出剩餘能力還大於剩餘的需要轉移的任務量時，向剩餘的需要轉移的任務量所對應的節點地址發送任務轉移請求消息。
6. 根據權利要求1所述的方法，其特徵在於，所述方法在將轉移的任務發送給所述任 務轉移請求消息所對應的節點之後，還包括通知MapReduce編程架構下的master回收垃圾空間。
7. 根據權利要求1所述的方法，其特徵在於，所述將轉移的任務發送給所述任務轉移 請求消息所對應的節點包括將未被執行的任務發送給所述任務轉移請求消息所對應的節點； 或將正在執行任務中的最後一個任務發送給所述任務轉移請求消息所對應的節點。
8. 根據權利要求1所述的方法，其特徵在於，所述方法在計算處理之後還包括根據 MapReduce編程架構下的map任務的個數自行設定多個reduce任務並進行reduce計算，將 所述多個reduce任務的計算結果根據用戶指定需要輸出的文件數量進行合併後輸出最終 計算結果。
9. 一種基於MapReduce編程架構的任務分配裝置，其特徵在於，所述裝置包括 判斷單元，用於判斷空閒或過載；發送單元，用於在所述判斷單元判斷出空閒時，發送空閒消息；接收單元，用於接收所述空閒消息的響應消息，所述響應消息包括需要轉移的任務量 和所述任務量所對應的節點地址；存儲單元，用於在所述需要轉移的任務量小於剩餘能力時，將所述需要轉移的任務量對應的節點地址存儲在過載節點列表中，所述發送單元還用於向所述過載節點列表中的一個節點地址發送任務轉移請求消息， 所述接收單元還用於接收轉移的任務； 計算單元，用於對所述轉移的任務進行計算處理；所述判斷單元判斷出過載且未進行任務轉移時；通知所述發送單元回復接收到的空閒 消息的響應消息；任務轉移單元，用於在所述接收單元收到任務轉移請求消息後，將轉移的任務發送給 所述任務轉移請求消息所對應的節點。
10. 根據權利要求9所述的裝置，其特徵在於，所述裝置還包括，分片單元，用於預先將 基於M即Reduce編程架構下的底層存儲系統的數據分塊邏輯分片成多個邏輯小塊，並以邏輯小塊為任務執行和轉移的基本單元。
11. 根據權利要求9所述的裝置，其特徵在於，所述發送單元還用於在判斷單元判斷出 剩餘能力還大於剩餘的需要轉移的任務量時，向剩餘的需要轉移的任務量所對應的節點地 址發送任務轉移請求消息。
12. 根據權利要求9所述的裝置，其特徵在於，所述裝置還包括回收單元，用於在所述 發送單元將轉移的任務發送給所述任務轉移請求消息所對應的節點之後，通知MapReduce 編程架構下的master回收垃圾空間。
13. 根據權利要求9所述的裝置，其特徵在於，所述裝置還包括合併單元，用於在所 述計算單元計算處理完之後，根據MapReduce編程架構下的map任務的個數自行設定多個 reduce任務並進行reduce計算，將所述多個reduce任務的計算結果根據用戶指定需要輸 出的文件數量進行合併後輸出最終計算結果。
全文摘要
本發明實施方式提供了一種基於MapReduce編程架構的任務分配方法及裝置，該方法及裝置屬於網絡通信領域，該方法包括預先將數據分塊邏輯分片成多個邏輯小塊，並以邏輯小塊為基本單元。在空閒時，發送空閒消息，並接收該空閒消息的響應消息，該響應消息包括需要轉移的任務量和該任務量所對應的節點地址；將該需要轉移的任務量對應的節點地址存儲在過載節點列表中，並發送任務轉移請求消息，接收轉移的任務並進行計算處理。多個Reduce任務處理完成後，將處理結果按用戶指定需要輸出的文件數量進行合併。本發明具體實施方式
提供的方法及裝置具有負載均衡，避免任務重複轉移，防止系統抖動的優點。
文檔編號H04L29/06GK101764835SQ200810241080
公開日2010年6月30日 申請日期2008年12月25日 優先權日2008年12月25日
發明者嚴哲峰, 李麗娟, 陳浩華 申請人:華為技術有限公司