一種業務調度的方法、裝置及系統的製作方法
2023-12-07 01:41:36 2
一種業務調度的方法、裝置及系統的製作方法
【專利摘要】本發明公開了一種業務調度的方法，應用於流計算系統，所述流計算系統用於調度並處理業務，所述流計算系統包括主控節點與多個工作節點；所述主控節點用於將所述業務包含的各個子業務調度到所述多個工作節點進行處理，包括：獲取所述業務的流式計算應用圖，根據所述流式計算應用圖中算子的算子度和算子勢，以及對所述流式計算應用圖進行分割的分割數量，對所述流式計算應用圖進行分割，得到所述分割數量的分割子圖，將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對應的工作節點上進行處理。本發明實施例提供的方法，可以使業務均衡的得到物理資源和網絡資源，提高了物理資源和網絡資源的利用率。
【專利說明】
【技術領域】
[0001] 本發明涉及計算機【技術領域】，具體涉及一種業務調度的方法，裝置及系統。 -種業務調度的方法、裝置及系統
【背景技術】
[0002] 實時流計算是指數據出現時便立刻對其進行處理，發生一個事件進行一次處理， 而不是緩存起來成一批處理。例如商用搜尋引擎。
[0003] 流式計算應用模型由算子和流組成，其中算子（operator)是承載業務邏輯的數 據處理單元，可被流計算平臺分布式調度執行的最小單元，而流（stream)則是算子間交互 的數據。
[0004] 基於流式數據處理模型編寫的業務應用經過流計算系統的主控節點調度後，會在 流計算平臺上分布式運行，流計算平臺包括主控節點和運行業務的物理節點。
[0005] 流處理系統的調度主要圍繞三個核心要素：
[0006] 1、業務模型（運行在流計算平臺上的業務應用，拓撲圖）。
[0007] 2、物理資源（平臺集群中的物理節點內存、CPU等計算資源）。
[0008] 3、網絡傳輸資源（平臺集群中的網絡吞吐與帶寬資源）。
[0009] 以上三者會相互影響與幹涉，業務模型的分配會決定物理資源使用的多少；物理 資源使用的多少會影響網絡傳輸的時延；網絡傳輸的時延又會影響到任務執行的效率。 [0010] 當前業界已存在的流計算系統基本是隨機將任務調度到物理資源上，沒有兼顧以 上三要素進行流式應用的調度，導致業務部署到平臺上運行時存在資源使用不均衡。
【發明內容】
[0011] 本發明實施例提供一種業務調度的方法，可以使業務均衡的分布到工作節點上， 從而均衡的得到物理資源和網絡資源，提高了物理資源和網絡資源的利用率。本發明實施 例還提供了相應的裝置及系統。
[0012] 本發明第一方面提供一種業務調度的方法，應用於流計算系統，所述流計算系統 用於調度並處理業務，所述流計算系統包括主控節點與多個工作節點；所述主控節點用於 將所述業務包含的各個子業務調度到所述多個工作節點進行處理，包括 ：
[0013] 獲取所述業務的流式計算應用圖，所述流式計算應用圖為針對所述業務預先建立 的包含算子和算子間數據流走向的邏輯關係圖，所述流式計算應用圖中的算子承載有用於 處理所述業務中的與所述算子對應的子業務的計算邏輯；
[0014] 根據所述流式計算應用圖中算子的算子度和算子勢，以及對所述流式計算應用圖 進行分割的分割數量，對所述流式計算應用圖進行分割，得到所述分割數量的分割子圖，所 述算子度為所述算子進出流量的流量權值累加和，所述算子勢為所述算子在所述流式計算 應用圖中的負載度；
[0015] 將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對應的 工作節點上進行處理。
[0016] 結合第一方面，在第一種可能的實現方式中，所述根據所述流式計算應用圖中算 子的算子度和算子勢，以及對所述流式計算應用圖進行分割的分割數量，對所述流式計算 應用圖進行分割之前，所述方法還包括：
[0017] 確定處理所述流式計算應用圖所針對的業務所需要的工作節點的個數；
[0018] 根據處理所述業務所需要的工作節點的個數，確定所述分割數量。
[0019] 結合第一方面或第一方面第一種可能的實現方式，在第二種可能的實現方式中， 所述根據所述流式計算應用圖中算子的算子度和算子勢，以及對所述流式計算應用圖進行 分割的分割數量，對所述流式計算應用圖進行分割，包括：
[0020] 根據所述算子的算子度和所述分割數量，對所述流式計算應用圖進行第一次分 害!]，得到第一次分割圖；
[0021] 根據所述算子勢對所述第一次分割圖進行第二次分割，得到所述分割子圖。
[0022] 結合第一方面第二種可能的實現方式，在第三種可能的實現方式中，所述根據所 述算子的算子度和所述分割數量，對所述流式計算應用圖進行第一次分割，得到第一次分 割圖，包括：
[0023] 根據所述算子的算子度和所述分割數量，確定個數與所述分割數量相同的中心算 子，所述中心算子的算子度至少大於一個與之相連的算子的算子度；
[0024] 以各個所述中心算子作為遍歷的起點，逐層遍歷除所述中心算子之外的其他算 子，直到遍歷到除所述中心算子之外的其他中心算子或搖擺算子，所述搖擺算子為以相鄰 兩中心算子為起點遍歷時同時被遍歷到的算子；
[0025] 將從所述中心算子開始，到遍歷到所述其他中心算子或所述搖擺算子之前所遍歷 到的算子劃分到所述第一次分割圖。
[0026] 結合第一方面第三種可能的實現方式，在第四種可能的實現方式中，所述根據所 述算子的算子度和所述分割數量，確定個數與所述分割數量相同的中心算子，包括：
[0027] 根據所述算子的算子度確定所述流式計算應用圖中的核心算子和普通算子，所述 核心算子的算子度高於與之連接的算子的算子度，所述普通算子為所述流式計算應用圖中 除掉所述核心算子之外的算子；
[0028] 根據所述分割數量，從所述核心算子中確定個數與所述分割數量相同的中心算 子，或者，從所述核心算子與所述普通算子的組合中確定個數與所述分割數量相同的中心 算子。
[0029] 結合第一方面第四種可能的實現方式，在第五種可能的實現方式中，所述從所述 核心算子中確定個數與所述分割數量相同的中心算子，包括 ：
[0030] 當所述核心算子的數量不小於所述中心算子的數量時，選擇算子度最大的所述分 割數量的核心算子作為所述中心算子。
[0031] 結合第一方面第四種可能的實現方式，在第六種可能的實現方式中，所述從所述 核心算子與所述普通算子的組合中確定個數與所述分割數量相同的中心算子，包括 ：
[0032] 當所述核心算子的數量小於所述中心算子的數量時，選擇算子度最大的普通算子 作為所述核心算子提供不足部分的所述中心算子。
[0033] 結合第一方面第三至第六種可能的實現方式中的任意一種，在第七種可能的實現 方式中，所述根據所述算子勢對所述第一次分割圖進行第二次分割，得到所述分割子圖，包 括：
[0034] 確定所述第一次分割圖的圖分區勢，所述圖分區勢為所述第一次分割圖中算子的 算子勢的累加和；
[0035] 根據相鄰第一次分割圖之間的搖擺算子的算子勢和所述相鄰第一次分割圖的圖 分區勢，確定所述搖擺算子應劃入的第一次分割圖，得到所述分割子圖。
[0036] 結合第一方面、第一方面第一至第七種可能的實現方式中的任意一種，在第八種 可能的實現方式中，所述方法還包括：
[0037] 計算圖分區負載，所述圖分區負載為所述分割子圖中算子的負載之和；
[0038] 根據所述圖分區負載計算負載誤差值；
[0039] 在所述負載誤差值大於預置的第一檢驗閥值時，將所述分割子圖中的搖擺算子調 整到所述負載誤差值最小的分割子圖中，得到調整後的分割子圖；
[0040] 所述將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對 應的工作節點上進行處理，包括：
[0041] 將每個所述調整後的分割子圖中包含的算子對應的子業務，調度到與所述調整後 的分割子圖對應的工作節點上進行處理。
[0042] 結合第一方面、第一方面第一至第七種可能的實現方式中的任意一種，在第九種 可能的實現方式中，所述方法還包括：
[0043] 計算圖分區網絡入流、出流、入度和出度，所述圖分區網絡入流為所述分割子圖中 跨物理節點接收數據流的算子的入流，所述圖分區網絡出流為所述分割子圖中跨物理節點 發送數據流的算子的出流，所述圖分區網絡入度為所述分割子圖中跨物理節點接收數據流 的算子的接收數據流的路數，所述圖分區網絡出度為所述分割子圖中跨物理節點發送數據 流的算子的發送數據流的路數；
[0044] 根據所述圖分區網絡入流、出流、入度和出度，計算流量誤差值；
[0045] 在所述流量誤差值大於預置的第二檢驗閥值時，將所述分割子圖中的搖擺算子調 整到所述流量誤差值最小的分割子圖中，得到調整後的分割子圖；
[0046] 所述將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對 應的工作節點上進行處理，包括：
[0047] 將每個所述調整後的分割子圖中包含的算子對應的子業務，調度到與所述調整後 的分割子圖對應的工作節點上進行處理。
[0048] 本發明第二方面提供一種業務調度的裝置，應用於流計算系統，所述流計算系統 用於調度並處理業務，所述流計算系統包括主控節點與多個工作節點；所述主控節點用於 將所述業務包含的各個子業務調度到所述多個工作節點進行處理，所述裝置包括：
[0049] 獲取單元，用於獲取所述業務的流式計算應用圖，所述流式計算應用圖為針對所 述業務預先建立的包含算子和算子間數據流走向的邏輯關係圖，所述流式計算應用圖中的 算子承載有用於處理所述業務中的與所述算子對應的子業務的計算邏輯；
[0050] 分割單元，用於根據所述獲取單元獲取的所述流式計算應用圖中算子的算子度和 算子勢，以及對所述流式計算應用圖進行分割的分割數量，對所述流式計算應用圖進行分 害I]，得到所述分割數量的分割子圖，所述算子度為所述算子進出流量的流量權值累加和，所 述算子勢為所述算子在所述流式計算應用圖中的負載度；
[0051] 調度單元，用於將每個所述分割單元分割得到的分割子圖中包含的算子對應的子 業務，調度到與所述分割子圖對應的工作節點上進行處理。
[0052] 結合第二方面，在第一種可能的實現方式中，所述裝置還包括：
[0053] 確定單元，用於在所述分割單元對所述流式計算應用圖進行分割之前，確定處理 所述流式計算應用圖所針對的業務所需要的工作節點的個數，根據處理所述業務所需要的 工作節點的個數，確定所述分割數量。
[0054] 結合第二方面或第二方面第一種可能的實現方式，在第二種可能的實現方式中， 所述分割單元包括：
[0055] 第一分割子單元，用於根據所述算子的算子度和所述分割數量，對所述流式計算 應用圖進行第一次分割，得到第一次分割圖；
[0056] 第二分割子單元，用於根據所述算子勢對所述第一分割子單元分割得到的所述第 一次分割圖進行第二次分割，得到所述分割子圖。
[0057] 結合第二方面第二種可能的實現方式，在第三種可能的實現方式中，所述第一分 割子單元包括：
[0058] 確定子單元，用於根據所述算子的算子度和所述分割數量，確定個數與所述分割 數量相同的中心算子，所述中心算子的算子度至少大於一個與之相連的算子的算子度；
[0059] 遍歷子單元，用於以所述確定子單元確定的各個所述中心算子作為遍歷的起點， 逐層遍歷除所述中心算子之外的其他算子，直到遍歷到除所述中心算子之外的其他中心算 子或搖擺算子，所述搖擺算子為以相鄰兩中心算子為起點遍歷時同時被遍歷到的算子；
[0060] 劃分子單元，用於將從所述中心算子開始，到所述遍歷子單元遍歷到所述其他中 心算子或所述搖擺算子之前所遍歷到的算子劃分到所述第一次分割圖。
[0061] 結合第二方面第三種可能的實現方式，在第四種可能的實現方式中，
[0062] 所述確定子單元，具體用於：
[0063] 根據所述算子的算子度確定所述流式計算應用圖中的核心算子和普通算子，所述 核心算子的算子度高於與之連接的算子的算子度，所述普通算子為所述流式計算應用圖中 除掉所述核心算子之外的算子；
[0064] 根據所述分割數量，從所述核心算子中確定個數與所述分割數量相同的中心算 子，或者，從所述核心算子與所述普通算子的組合中確定個數與所述分割數量相同的中心 算子。
[0065] 結合第二方面第四種可能的實現方式，在第五種可能的實現方式中，
[0066] 所述確定子單元，具體用於當所述核心算子的數量不小於所述中心算子的數量 時，選擇算子度最大的所述分割數量的核心算子作為所述中心算子。
[0067] 結合第二方面第四種可能的實現方式，在第六種可能的實現方式中，
[0068] 所述確定子單元，具體用於當所述核心算子的數量小於所述中心算子的數量時， 選擇算子度最大的普通算子作為所述核心算子提供不足部分的所述中心算子。
[0069] 結合第二方面第三至第六種可能的實現方式中的任意一種，在第七種可能的實現 方式中，
[0070] 所述第二分割子單元，具體用於：
[0071] 確定所述第一次分割圖的圖分區勢，所述圖分區勢為所述第一次分割圖中算子的 算子勢的累加和；
[0072] 根據相鄰第一次分割圖之間的搖擺算子的算子勢和所述相鄰第一次分割圖的圖 分區勢，確定所述搖擺算子應劃入的第一次分割圖，得到所述分割子圖。
[0073] 結合第二方面、第二方面第一至第七種可能的實現方式中的任意一種，在第八種 可能的實現方式中，所述裝置還包括：第一計算單元和第一調整單元，
[0074] 所述第一計算單元，用於計算圖分區負載，所述圖分區負載為所述分割子圖中算 子的負載之和，根據所述圖分區負載計算負載誤差值；
[0075] 所述第一調整單元，用於在所述第一計算單元計算的所述負載誤差值大於預置的 第一檢驗閥值時，將所述分割子圖中的搖擺算子調整到所述負載誤差值最小的分割子圖 中，得到調整後的分割子圖；
[0076] 所述調度單元，用於將每個所述第一調整單元調整後的分割子圖中包含的算子對 應的子業務，調度到與所述調整後的分割子圖對應的工作節點上進行處理。
[0077] 結合第二方面、第二方面第一至第七種可能的實現方式中的任意一種，在第九種 可能的實現方式中，所述裝置還包括：第二計算單元和第二調整單元，
[0078] 所述第二計算單元，用於計算圖分區網絡入流、出流、入度和出度，所述圖分區網 絡入流為所述分割子圖中跨物理節點接收數據流的算子的入流，所述圖分區網絡出流為所 述分割子圖中跨物理節點發送數據流的算子的出流，所述圖分區網絡入度為所述分割子圖 中跨物理節點接收數據流的算子的接收數據流的路數，所述圖分區網絡出度為所述分割子 圖中跨物理節點發送數據流的算子的發送數據流的路數，根據所述圖分區網絡入流、出流、 入度和出度，計算流量誤差值；
[0079] 所述第二調整單元，用於在所述第二計算單元計算出的所述流量誤差值大於預置 的第二檢驗閥值時，將所述分割子圖中的搖擺算子調整到所述流量誤差值最小的分割子圖 中，得到調整後的分割子圖；
[0080] 所述調度單元，用於將每個所述第二調整單元調整後的分割子圖中包含的算子對 應的子業務，調度到與所述調整後的分割子圖對應的工作節點上進行處理。
[0081] 本發明第三方面提供一種流計算系統，所述流計算系統用於調度並處理業務，所 述流計算系統包括主控節點與多個工作節點；所述主控節點用於將所述業務包含的各個子 業務調度到所述多個工作節點進行處理，
[0082] 所述主控節點，用於：
[0083] 獲取所述業務的流式計算應用圖，所述流式計算應用圖為針對所述業務預先建立 的包含算子和算子間數據流走向的邏輯關係圖，所述流式計算應用圖中的算子承載有用於 處理所述業務中的與所述算子對應的子業務的計算邏輯；
[0084] 根據所述流式計算應用圖中算子的算子度和算子勢，以及對所述流式計算應用圖 進行分割的分割數量，對所述流式計算應用圖進行分割，得到所述分割數量的分割子圖，所 述算子度為所述算子進出流量的流量權值累加和，所述算子勢為所述算子在所述流式計算 應用圖中的負載度；
[0085] 將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對應的 工作節點上進行處理。
[0086] 本發明實施例提供的業務調度的方法，根據所述流式計算應用圖中算子的算子度 和算子勢，以及對所述流式計算應用圖進行分割的分割數量，對所述流式計算應用圖進行 分割，得到分割子圖，；將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分 割子圖對應的工作節點上進行處理。本發明實施例綜合調度過程中涉及的三要素進行平衡 圖分割，由於分割的過程中考慮了算子的算子度，因此能獲取儘可能小的網絡傳輸開銷，同 時，還考了了節點勢，因此能獲取儘可能優的節點負載配比，與現有技術中業務部署到流平 臺上運行時存在資源使用不均衡相比，本發明實施例提供的方法，可以使業務均衡的得到 物理資源和網絡資源，提高了物理資源和網絡資源的利用率。
【專利附圖】
【附圖說明】
[0087] 為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現 有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本 發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以 根據這些附圖獲得其他的附圖。
[0088] 圖1是本發明實施例中業務調度的方法的一實施例示意圖；
[0089] 圖2是本發明實施例中業務調度的方法的另一實施例示意圖；
[0090] 圖3是本發明實施例中業務調度的方法的另一實施例示意圖；
[0091] 圖4是本發明實施例中業務調度的方法的另一實施例示意圖；
[0092] 圖5是本發明實施例中業務調度的方法的另一實施例示意圖；
[0093] 圖6是本發明實施例中業務調度的方法的另一實施例示意圖；
[0094] 圖7是本發明實施例中業務調度的方法的另一實施例示意圖；
[0095] 圖8是本發明實施例中業務調度的裝置的一實施例示意圖；
[0096] 圖9是本發明實施例中業務調度的裝置的另一實施例示意圖；
[0097] 圖10是本發明實施例中業務調度的裝置的另一實施例示意圖；
[0098] 圖11是本發明實施例中業務調度的裝置的另一實施例示意圖；
[0099] 圖12是本發明實施例中業務調度的裝置的另一實施例示意圖；
[0100] 圖13是本發明實施例中業務調度的裝置的另一實施例示意圖；
[0101] 圖14是本發明實施例中業務調度的裝置的另一實施例示意圖；
[0102] 圖15是本發明實施例中流計算系統的一實施例示意圖。
【具體實施方式】
[0103] 本發明實施例提供一種業務調度的方法，可以使業務均衡的分布到工作節點上， 從而均衡的得到物理資源和網絡資源，提高了物理資源和網絡資源的利用率。本發明實施 例還提供了相應的裝置及系統。以下分別進行詳細說明。
[0104] 為了使本【技術領域】的人員更好地理解本發明方案，下面將結合本發明實施例中的 附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是 本發明一部分的實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術 人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都應當屬於本發明保護的範 圍。
[0105] 本發明實施例中的流計算系統包括：主控節點和工作節點，在集群部署時，所述主 控節點和工作節點都可以有一個或多個，主控節點可以是與工作節點分離的物理節點，在 單機部署時，主控節點和工作節點可以是部署在同一個物理節點上的主控邏輯單元。流計 算系統用於調度並處理業務，具體過程是，主控節點負責將業務調度到工作節點上進行處 理。一臺物理節點可以包括一個工作節點，也可以包括多個工作節點，一臺物理節點包括的 工作節點的數量取決於該物理節點的硬體物理資源。可以將一個工作節點理解為是一份硬 件物理資源。屬於同一臺物理節點中的工作節點間採用進程通信的方式進行通信，屬於不 同物理節點中的工作節點間採用網絡通信的方式進行通信。流計算系統可以將業務調度到 工作節點上進行處理。針對運行在流計算系統上的業務可以預先建立流式計算應用圖，所 述流式計算應用圖為針對所述業務預先建立的包含算子和算子間數據流走向的邏輯關係 圖，所述流式計算應用圖中的算子承載有用於處理所述業務中的與所述算子對應的子業務 的計算邏輯。本發明實施例中的物理節點指的是物理設備。
[0106] 如圖1所示，流計算系統包括主控節點、工作節點1、工作節點2和工作節點3。工 作節點1、工作節點2屬於物理節點1，工作節點3屬於物理節點2。
[0107] 主控節點將圖1所示的流式計算應用圖調度到工作節點1、工作節點2和工作節點 3這三個工作節點上進行業務處理。圖1所示的流式計算應用圖為包含P1至P9的九個算 子以及這九個算子之間的數據流走向的邏輯關係圖。
[0108] 被調度到工作節點1上的算子PI、P2和P3與被調度到工作節點2上的算子P4、 P7和P9之間通過進程方式通信，PI、P2和P3,以及P4、P7和P9與被調度到工作節點3上 的算子P5、P6、P8之間通過網絡通信。
[0109] 本發明實施例中的流式計算應用圖包括有向無環圖（Directed Acyclic Graph, DAG)、樹狀圖或者含有環的圖。
[0110] 在執行業務調度的過程中，主控節點獲取業務的流式計算應用圖，所述流式計算 應用圖為針對所述業務預先建立的包含算子和算子間數據流走向的邏輯關係圖，所述流式 計算應用圖中的算子承載有用於處理所述業務中的與所述算子對應的子業務的計算邏輯。 [0111] 所述流式計算應用圖為用戶或開發人員根據所述業務預先建立的數據流，流式計 算應用圖用於表示流式應用的邏輯模型，流式計算應用圖可以參閱圖2進行理解，如圖2所 示的流式計算應用圖包括13個算子，分別從nl到nl3,有13條數據流，分別從si到sl3。 圖2中明確標出了數據流的走向，例如：數據流si是從算子nl到算子n2,以及從算子nl到 算子n3的數據流，表示數據流經算子nl邏輯處理後，產生的兩條數據流sl，分別進入算子 n2和算子n3進行邏輯處理。其他數據流的流向所表達的意思與數據流si相同，只是所經 歷的算子不同，本處不做一一贅述。
[0112] 根據所述流式計算應用圖中算子的算子度和算子勢，以及對所述流式計算應用圖 進行分割的分割數量，對所述流式計算應用圖進行分割，得到所述分割數量的分割子圖，所 述算子度為所述算子進出流量的流量權值累加和，所述算子勢為所述算子在所述流式計算 應用圖中的負載度。
[0113] 本發明實施例中的算子為邏輯處理單元，算子有兩種描述參數，分別為算子負載 度和進出流，算子負載度可以反映業務部署到物理節點工作節點後，業務按照所述算子的 邏輯運行時所消耗的資源數，算子的負載度越高，業務運行時所消耗的資源數越多。算子進 出流是指算子的入流和出流，例如：算子n2的入流為sl，出流為s2。
[0114] 算子負載度中的系統算子的算子負載度是開發人員在開發時給出的，自定義算子 的算子負載度是用戶參考系統算子的算子負載度給出的。
[0115] 算子的負載度與算子的類型有關係，所以可以參考算子類型給出算子負載度，流 量權值與流派發策略有關係，所以可以參考流派發策略給出流量權值。例如，結合圖2的算 子和數據流，可以參閱表1和表2理解算子的負載度和數據流的流量權值。表1為算子負 載度表，表2為數據流的流量權值表。
[0116] 表1:算子負載度表
[0117]
[0118]
【權利要求】
1. 一種業務調度的方法，應用於流計算系統，所述流計算系統用於調度並處理業務，所 述流計算系統包括主控節點與多個工作節點；所述主控節點用於將所述業務包含的各個子 業務調度到所述多個工作節點進行處理，其特徵在於，包括 ： 獲取所述業務的流式計算應用圖，所述流式計算應用圖為針對所述業務預先建立的包 含算子和算子間數據流走向的邏輯關係圖，所述流式計算應用圖中的算子承載有用於處理 所述業務中的與所述算子對應的子業務的計算邏輯； 根據所述流式計算應用圖中算子的算子度和算子勢，以及對所述流式計算應用圖進行 分割的分割數量，對所述流式計算應用圖進行分割，得到所述分割數量的分割子圖，所述算 子度為所述算子進出流量的流量權值累加和，所述算子勢為所述算子在所述流式計算應用 圖中的負載度； 將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對應的工作 節點上進行處理。
2. 根據權利要求1所述的方法，其特徵在於，所述根據所述流式計算應用圖中算子的 算子度和算子勢，以及對所述流式計算應用圖進行分割的分割數量，對所述流式計算應用 圖進行分割之前，所述方法還包括： 確定處理所述流式計算應用圖所針對的業務所需要的工作節點的個數； 根據處理所述業務所需要的工作節點的個數，確定所述分割數量。
3. 根據權利要求1或2所述的方法，其特徵在於，所述根據所述流式計算應用圖中算子 的算子度和算子勢，以及對所述流式計算應用圖進行分割的分割數量，對所述流式計算應 用圖進行分割，包括： 根據所述算子的算子度和所述分割數量，對所述流式計算應用圖進行第一次分割，得 到第一次分割圖； 根據所述算子勢對所述第一次分割圖進行第二次分割，得到所述分割子圖。
4. 根據權利要求3所述的方法，其特徵在於，所述根據所述算子的算子度和所述分割 數量，對所述流式計算應用圖進行第一次分割，得到第一次分割圖，包括： 根據所述算子的算子度和所述分割數量，確定個數與所述分割數量相同的中心算子， 所述中心算子的算子度至少大於一個與之相連的算子的算子度； 以各個所述中心算子作為遍歷的起點，逐層遍歷除所述中心算子之外的其他算子，直 到遍歷到除所述中心算子之外的其他中心算子或搖擺算子，所述搖擺算子為以相鄰兩中心 算子為起點遍歷時同時被遍歷到的算子； 將從所述中心算子開始，到遍歷到所述其他中心算子或所述搖擺算子之前所遍歷到的 算子劃分到所述第一次分割圖。
5. 根據權利要求4所述的方法，其特徵在於，所述根據所述算子的算子度和所述分割 數量，確定個數與所述分割數量相同的中心算子，包括： 根據所述算子的算子度確定所述流式計算應用圖中的核心算子和普通算子，所述核心 算子的算子度高於與之連接的算子的算子度，所述普通算子為所述流式計算應用圖中除掉 所述核心算子之外的算子； 根據所述分割數量，從所述核心算子中確定個數與所述分割數量相同的中心算子，或 者，從所述核心算子與所述普通算子的組合中確定個數與所述分割數量相同的中心算子。
6. 根據權利要求5所述的方法，其特徵在於，所述從所述核心算子中確定個數與所述 分割數量相同的中心算子，包括： 當所述核心算子的數量不小於所述中心算子的數量時，選擇算子度最大的所述分割數 量的核心算子作為所述中心算子。
7. 根據權利要求5所述的方法，其特徵在於，所述從所述核心算子與所述普通算子的 組合中確定個數與所述分割數量相同的中心算子，包括： 當所述核心算子的數量小於所述中心算子的數量時，選擇算子度最大的普通算子作為 所述核心算子提供不足部分的所述中心算子。
8. 根據權利要求4-7任一所述的方法，其特徵在於，所述根據所述算子勢對所述第一 次分割圖進行第二次分割，得到所述分割子圖，包括： 確定所述第一次分割圖的圖分區勢，所述圖分區勢為所述第一次分割圖中算子的算子 勢的累加和； 根據相鄰第一次分割圖之間的搖擺算子的算子勢和所述相鄰第一次分割圖的圖分區 勢，確定所述搖擺算子應劃入的第一次分割圖，得到所述分割子圖。
9. 根據權利要求1-8任一所述的方法，其特徵在於，所述方法還包括： 計算圖分區負載，所述圖分區負載為所述分割子圖中算子的負載之和； 根據所述圖分區負載計算負載誤差值； 在所述負載誤差值大於預置的第一檢驗閥值時，將所述分割子圖中的搖擺算子調整到 所述負載誤差值最小的分割子圖中，得到調整後的分割子圖； 所述將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對應的 工作節點上進行處理，包括： 將每個所述調整後的分割子圖中包含的算子對應的子業務，調度到與所述調整後的分 割子圖對應的工作節點上進行處理。
10. 根據權利要求1-8任一所述的方法，其特徵在於，所述方法還包括： 計算圖分區網絡入流、出流、入度和出度，所述圖分區網絡入流為所述分割子圖中跨物 理節點接收數據流的算子的入流，所述圖分區網絡出流為所述分割子圖中跨物理節點發送 數據流的算子的出流，所述圖分區網絡入度為所述分割子圖中跨物理節點接收數據流的算 子的接收數據流的路數，所述圖分區網絡出度為所述分割子圖中跨物理節點發送數據流的 算子的發送數據流的路數； 根據所述圖分區網絡入流、出流、入度和出度，計算流量誤差值； 在所述流量誤差值大於預置的第二檢驗閥值時，將所述分割子圖中的搖擺算子調整到 所述流量誤差值最小的分割子圖中，得到調整後的分割子圖； 所述將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對應的 工作節點上進行處理，包括： 將每個所述調整後的分割子圖中包含的算子對應的子業務，調度到與所述調整後的分 割子圖對應的工作節點上進行處理。
11. 一種業務調度的裝置，應用於流計算系統，所述流計算系統用於調度並處理業務， 所述流計算系統包括主控節點與多個工作節點；所述主控節點用於將所述業務包含的各個 子業務調度到所述多個工作節點進行處理，其特徵在於，包括： 獲取單元，用於獲取所述業務的流式計算應用圖，所述流式計算應用圖為針對所述業 務預先建立的包含算子和算子間數據流走向的邏輯關係圖，所述流式計算應用圖中的算子 承載有用於處理所述業務中的與所述算子對應的子業務的計算邏輯； 分割單元，用於根據所述獲取單元獲取的所述流式計算應用圖中算子的算子度和算子 勢，以及對所述流式計算應用圖進行分割的分割數量，對所述流式計算應用圖進行分割，得 到所述分割數量的分割子圖，所述算子度為所述算子進出流量的流量權值累加和，所述算 子勢為所述算子在所述流式計算應用圖中的負載度； 調度單元，用於將每個所述分割單元分割得到的分割子圖中包含的算子對應的子業 務，調度到與所述分割子圖對應的工作節點上進行處理。
12. 根據權利要求11所述的裝置，其特徵在於，所述裝置還包括： 確定單元，用於在所述分割單元對所述流式計算應用圖進行分割之前，確定處理所述 流式計算應用圖所針對的業務所需要的工作節點的個數，根據處理所述業務所需要的工作 節點的個數，確定所述分割數量。
13. 根據權利要求11或12所述的裝置，其特徵在於，所述分割單元包括： 第一分割子單元，用於根據所述算子的算子度和所述分割數量，對所述流式計算應用 圖進行第一次分割，得到第一次分割圖； 第二分割子單元，用於根據所述算子勢對所述第一分割子單元分割得到的所述第一次 分割圖進行第二次分割，得到所述分割子圖。
14. 根據權利要求13所述的裝置，其特徵在於，所述第一分割子單元包括： 確定子單元，用於根據所述算子的算子度和所述分割數量，確定個數與所述分割數量 相同的中心算子，所述中心算子的算子度至少大於一個與之相連的算子的算子度； 遍歷子單元，用於以所述確定子單元確定的各個所述中心算子作為遍歷的起點，逐層 遍歷除所述中心算子之外的其他算子，直到遍歷到除所述中心算子之外的其他中心算子或 搖擺算子，所述搖擺算子為以相鄰兩中心算子為起點遍歷時同時被遍歷到的算子； 劃分子單元，用於將從所述中心算子開始，到所述遍歷子單元遍歷到所述其他中心算 子或所述搖擺算子之前所遍歷到的算子劃分到所述第一次分割圖。
15. 根據權利要求14所述的裝置，其特徵在於， 所述確定子單元，具體用於： 根據所述算子的算子度確定所述流式計算應用圖中的核心算子和普通算子，所述核心 算子的算子度高於與之連接的算子的算子度，所述普通算子為所述流式計算應用圖中除掉 所述核心算子之外的算子； 根據所述分割數量，從所述核心算子中確定個數與所述分割數量相同的中心算子，或 者，從所述核心算子與所述普通算子的組合中確定個數與所述分割數量相同的中心算子。
16. 根據權利要求15所述的裝置，其特徵在於， 所述確定子單元，具體用於當所述核心算子的數量不小於所述中心算子的數量時，選 擇算子度最大的所述分割數量的核心算子作為所述中心算子。
17. 根據權利要求15所述的裝置，其特徵在於， 所述確定子單元，具體用於當所述核心算子的數量小於所述中心算子的數量時，選擇 算子度最大的普通算子作為所述核心算子提供不足部分的所述中心算子。
18. 根據權利要求14-17任一所述的裝置，其特徵在於， 所述第二分割子單元，具體用於： 確定所述第一次分割圖的圖分區勢，所述圖分區勢為所述第一次分割圖中算子的算子 勢的累加和； 根據相鄰第一次分割圖之間的搖擺算子的算子勢和所述相鄰第一次分割圖的圖分區 勢，確定所述搖擺算子應劃入的第一次分割圖，得到所述分割子圖。
19. 根據權利要求11-18任一所述的裝置，其特徵在於，所述裝置還包括：第一計算單 元和第一調整單元， 所述第一計算單元，用於計算圖分區負載，所述圖分區負載為所述分割子圖中算子的 負載之和，根據所述圖分區負載計算負載誤差值； 所述第一調整單元，用於在所述第一計算單元計算的所述負載誤差值大於預置的第一 檢驗閥值時，將所述分割子圖中的搖擺算子調整到所述負載誤差值最小的分割子圖中，得 到調整後的分割子圖； 所述調度單元，用於將每個所述第一調整單元調整後的分割子圖中包含的算子對應的 子業務，調度到與所述調整後的分割子圖對應的工作節點上進行處理。
20. 根據權利要求11-18任一所述的裝置，其特徵在於，所述裝置還包括：第二計算單 元和第二調整單元， 所述第二計算單元，用於計算圖分區網絡入流、出流、入度和出度，所述圖分區網絡入 流為所述分割子圖中跨物理節點接收數據流的算子的入流，所述圖分區網絡出流為所述分 割子圖中跨物理節點發送數據流的算子的出流，所述圖分區網絡入度為所述分割子圖中跨 物理節點接收數據流的算子的接收數據流的路數，所述圖分區網絡出度為所述分割子圖中 跨物理節點發送數據流的算子的發送數據流的路數，根據所述圖分區網絡入流、出流、入度 和出度，計算流量誤差值； 所述第二調整單元，用於在所述第二計算單元計算出的所述流量誤差值大於預置的第 二檢驗閥值時，將所述分割子圖中的搖擺算子調整到所述流量誤差值最小的分割子圖中， 得到調整後的分割子圖； 所述調度單元，用於將每個所述第二調整單元調整後的分割子圖中包含的算子對應的 子業務，調度到與所述調整後的分割子圖對應的工作節點上進行處理。
21. -種流計算系統，所述流計算系統用於調度並處理業務，所述流計算系統包括主控 節點與多個工作節點；所述主控節點用於將所述業務包含的各個子業務調度到所述多個工 作節點進行處理，其特徵在於， 所述主控節點，用於： 獲取所述業務的流式計算應用圖，所述流式計算應用圖為針對所述業務預先建立的包 含算子和算子間數據流走向的邏輯關係圖，所述流式計算應用圖中的算子承載有用於處理 所述業務中的與所述算子對應的子業務的計算邏輯； 根據所述流式計算應用圖中算子的算子度和算子勢，以及對所述流式計算應用圖進行 分割的分割數量，對所述流式計算應用圖進行分割，得到所述分割數量的分割子圖，所述算 子度為所述算子進出流量的流量權值累加和，所述算子勢為所述算子在所述流式計算應用 圖中的負載度； 將每個所述分割子圖中包含的算子對應的子業務，調度到與所述分割子圖對應的工作 節點上進行處理。
【文檔編號】H04L29/08GK104052811SQ201410270392
【公開日】2014年9月17日 申請日期:2014年6月17日 優先權日:2014年6月17日
【發明者】張松山 申請人:華為技術有限公司