層次化計算范式數據中心任務調度方法

胡 榮，馬軍生

(1.吉利學院 智能科技學院，四川 成都 641402；2.國防科技大學 信息通信學院，湖北 武漢 430000)

0 引 言

近年來，網絡帶寬不斷增長、通信成本不斷下降，分布式應用產生的數據量越來越大，這一現象開始得到研究人員的關注[1,2]。在這些應用中，如果源節點將原始數據直接發送給服務器，會給網絡基礎設施和服務器帶來極大壓力。為了緩解這一問題，一些研究[3-5]提出，可以在網絡中部署中間處理節點(intermediate processing nodes，IPNs)對原始數據做預處理，如壓縮、格式轉換、去噪等，再由中間處理節點將處理后的數據發送給服務器。在實際的大規模分布式應用中，出于分而治之或負載均衡等方面的考慮，也常常部署一些性能較高的中間處理節點，對源節點產生的原始數據進行預處理。本文將分布式應用的這種分層的處理模式命名為層次化計算范式。

需要注意的是，分布式應用中的一次任務通常包含多個子任務。比如，在層次化計算范式中，每個源節點產生數據并經由IPN中繼到目標節點的過程，都可以視為一個子任務。在分布式應用中，這些子任務的預期完成時長和截止時間可能各不相同[6]，也很難保證所有的子任務都可以在截止時間之前完成[7]。與已有的研究保持一致[8]，本文試圖通過最小化所有子任務的總延遲來優化分布式應用的響應時間。

如圖1所示，在層次化計算范式中，某個子任務的完成時長由3部分組成：子任務從源節點出發，經由IPN到達目標節點引入的路由時延；子任務在IPN上的處理時長；子任務在IPN上等待處理時，引入的排隊時長。為了簡便，本文將處理時長和排隊時長之和稱為處置時長。注意到，子任務的處理時長和路由時延依賴于子任務的分配策略，排隊時長則依賴于IPN的調度策略。子任務的分配策略和調度策略相互影響，導致路由時延、排隊時長和處理時長的聯合優化并非易事。

圖1 層次化計算范式下的子任務完成時長

大規模IDC在不同維度、不同層面上存在異構性。比如，為了滿足不同應用的資源需求，IDC中往往部署有不同配置的主機；同時，IDC往往是增量化建設的，不同批次主機的配置也有不同。虛擬化IDC中的混布技術將資源需求不同的應用(如在線應用和離線應用)部署在一起，因而應用之間也存在異構性。因此層次化計算范式中的中間處理節點往往是異構的，它們的資源總量和處理能力各不相同。這種配置異構性使得層次化計算范式中的總延遲最小化變得更加困難。比如，將子任務分配給處理能力最強的IPN，可以使得預期處理時長最小，但可能引入很大的路由時延；而將子任務分配給路由時延最小的IPN，則可能會引入較長的處理時長；此外，如果子任務在IPN節點之間分配不均，也可能導致高負載IPN上的排隊時長過大。

當前，針對路由策略的研究[9,10]和針對調度策略的研究[11]已有很多。廣義來說，路由策略研究的是數據(子任務)如何分配給服務節點；在子任務分配過程中，路由策略通常著眼于路由時延優化，而不關注子任務在服務節點上的處置時長。調度策略研究的是服務節點處理數據(執行子任務)的次序；在決定子任務的執行次序時，調度策略通常僅著眼于排隊時長優化，而不關注其它。近年來，越來越多的研究開始關注路由策略和調度策略之間的相互關系[12-14]。但是，極少有研究關注層次化計算范式下的路由策略和調度策略的相互影響。

層次化計算范式近年來已經廣泛出現在大規模分布式應用中，比如分布式信息檢索或智慧城市。層次化計算范式是一個新興且重要的系統架構，異構層次化計算范式下分布式應用的延遲最小化問題很值得研究。本文試圖回答以下問題：如何在異構層次化計算范式下，最小化分布式應用的總延遲?針對層次化計算范式下路由時延和處置時長的聯合優化需求，并考慮了大規模應用在線運行時的實際情況，本文設計了一種延遲感知的Power-of-D任務調度算法(tardiness-aware power-of-dalgorithm，TPD)。最后，基于真實系統場景對上述算法進行了性能評估，評估結果肯定了其有效性。

1 初始方案及其啟示

本小節給出了層次化計算范式下總延遲最小化的問題定義。表1總結了問題定義中所使用的符號及含義。

表1 本文符號及定義

某個子任務m在源節點產生后，會被中繼到一個且僅被中繼到一個資源總量可以滿足此子任務的IPN節點k上，即Qk≥qm。 子任務到達IPN后，若該IPN的剩余資源充足，則可以并發處理多個子任務；若剩余資源不足，則到達的子任務會在優先級隊列中等候處理。這里假設IPN上的優先級隊列沒有長度限制。此外，本文考慮子任務級別的調度策略，所以假設子任務的執行過程不可被打斷。

基于上述描述，本問題可以定義如下

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

2 任務調度策略

在線運行階段，借鑒已有研究經驗，假設子任務按照泊松過程動態產生——這也是在線活動建模的常用方法。如算法1所示，在線任務調度是以事件驅動模式進行的。具體而言，定期采集分布式應用的狀態，并根據應用狀態進行任務調度。對于每個IPN節點k，子任務分發器(dispatcher)定期地采集系統中的傳輸時延ωik和ωkj(第4行)以及IPN的負載情況(第5行)。如果一個新的子任務m產生，分發器會選擇一個IPN節點k(第7行)，并將子任務m分發給k(第8行)。最后，IPN節點k按照一定的優先級對其上的子任務進行處理(第9行)。

算法1:在線任務調度流程

(1)repeat

(2) WaitForEvent(&event);

(3)ifevent isCollectInformationthen

(4) CollectLatency();

(5) CollectWorkload();

(6)elseifevent isSubTaskGenerationthen

(7) Select an IPNkto process the new sub-taskm;

(8) Dispatch sub-taskmto IPNk;

(9) IPNkschedules and processes sub-taskm;

(10)untilnomoresub-tasksaregenerated;

在實際的大規模分布式應用中，系統狀態通常是定期收集的，且將子任務從源節點路由到IPN節點也會引入時延。因而，采集到的系統狀態數據可能是過時的、近似的，甚至還會有錯誤存在。在這種情況下，不能假設在線運行過程中所采集到的系統狀態數據是實時的、準確的。已有研究人員發現，將任務直接分發給看起來負載最輕的服務器上，可能導致系統性能顯著下降。因而，不能僅僅基于采集到的系統狀態數據進行任務調度。本節將超市模型(supermarket model)中的Power-of-D范式擴展到異構層次化計算范式中，并設計了延遲感知的Power-of-D算法(tardiness-aware power-of-D，TPD)用于在線任務調度。

2.1 超市模型與Power-of-D范式

超市模型考慮的是這樣一個場景：顧客依次到達超市，而后加入到某個服務員前的隊列中；顧客的到達模型，是速率為n·λ(0<λ<1) 的泊松流，其中n是服務員的數量;所有服務員的服務速度相同；服務員按照先到先服務(first come first service，FCFS)的原則，依次服務其隊列中的顧客。超市模型旨在將顧客分配到最佳的服務員，使得顧客的期望滯留時長(expected sojourn time)最短。若將子任務視為顧客，將IPN視為服務員，子任務調度與超市模型非常類似。

超市模型的一個典型解決方案是Power-of-D范式。在Power-of-D范式中，每個新來的顧客按照均等概率隨機選取d個服務員，而后在選取的服務員中選擇顧客隊列最短的那個。有文獻[11]證明，d=2時用戶的平均滯留時間比起d=1時有指數級的改進，而d=3時則僅比d=2時有常數級的改進。因此，d通常取值為2，Power-of-D范式也通常被稱為Power-of-Two。Power-of-D在實際的大規模系統中成效顯著，是因為其在選擇服務員時引入了隨機性。這啟發作者在任務調度中也增加隨機因素。

2.2 挑 戰

盡管在線任務調度與超市模型相似，兩者之間還是有一些關鍵性的區別。特別的，在層次化計算范式下應用Power-of-D范式面臨以下挑戰。

第一，是負載不均衡。在超市模型中，所有服務員的服務能力都是相同的，而IPN節點的資源總量和處理速度則各不相同。在異構系統中，Power-of-D的表現比在同構系統中的表現要差。這是因為，經典的Power-of-D總是按照均等概率選擇服務員，這會增加弱服務能力的IPN上子任務的排隊時長，進而增大異構系統中顧客的滯留時間。此外，Power-of-D在異構系統中對d的取值敏感，d取值不合適會導致顧客(負載)在服務員(服務節點)上分布不均衡，這也會增長顧客的滯留時間。

第二，是最優服務員的選取。經典的Power-of-D范式中，每個顧客選擇隊列最短的服務員，以最小化該顧客的期望滯留時間(即層次化計算范式場景中的處置時長)。然而在層次化計算范式中，較短的隊列并不一定意味著較短的排隊時長，因為少量的長子任務可以占用IPN的大量資源和處理能力。此外，層次化計算范式中，不僅關注處置時長還關注路由時延，而超市模型則不關注路由時延(即顧客加入某個服務員的隊列所需的開銷)。

第三，是子任務的調度策略。Power-of-D只關注如何將顧客分配給合適的服務員，服務員則簡單地按照FCFS的規則提供服務。因為FCFS規則中的優先級機制過于簡單(先到達的顧客的優先級總是比后到達的顧客要高)，所以在優化層次化計算范式中的子任務延遲時是低效的。比如，即使某個子任務馬上就要超過其截止時間了，它還是需要在隊列中等待它前面的子任務一一得到處理，這會增加任務的總延遲和分布式應用的響應時間。

2.3 應對挑戰

(10)

表象處理速度表征了這樣一種現象：由于路由時延的存在，IPN節點的處理速度看起來變得比其實際處理速度vk慢；某個IPN節點引入的路由時延越長，子任務經由該IPN處理并轉發所需的時間就越長，因而該節點的處理速度看起來就越慢。注意到，網絡中的路由時延會不斷變化，每個IPN節點的表象處理速度v′k也需要相應的不斷更新。

通過定義表象處理速度，IPN節點k的抽樣概率可以表達為

(11)

式中：IPN節點k的抽樣概率與其表象處理速度v′k成正比。這樣，具有較高處理速度和較低路由時延的IPN節點被選中的機會就越大，避免了在低配置IPN節點上發生擁塞。

此外，為了保證負載均衡，還需要仔細計算d值。異構超市模型中可以保證負載均衡的d值的緊下界(tight lower bound)和緊上界(tight upper bound)。其中，d值的下界表達為

dlower=(1-ε)·f(α,β)

(12)

上界表達為

dupper=(1+ε)·f(α,β)

(13)

在上述等式中，ε∈[0,1]

(14)

為了選擇最佳的IPN節點，在抽樣得到的d個候選IPN中，選擇符合如下條件的IPN節點k來服務子任務m

(15)

式中：Queuek表示IPN節點k上的優先級隊列中的子任務集合。這樣，某個IPN節點負載越輕、處理速度越快、傳輸時延越短，子任務就越傾向于選擇它。通過選擇這樣的IPN節點，子任務的預期完成時長最短。

至于子任務調度策略，IPN從其隊列中優先選擇處理符合如下條件的子任務i

(16)

2.4 算法流程

將前面的設計綜合起來，設計了延遲感知的Power-of-D算法(tardiness-aware power-of-D，TPD)。該算法的工作流程如算法2所示。

算法2：算法流程

(6) Calculatedaccording to Formula (12) and (13);

(7) Sampledcandidates with probability distribution F;

(8) Routemto the IPNksatisfying Formula (15);

(9) IPNkschedules and processes sub-taskmaccording to Formula (16);

可以看到，算法2是一個線性時間算法，算法的時間復雜度與IPN節點的數量成正比，即O(|K|)。 注意到，在實際系統中，IPN節點的數量通常較小，所以TPD算法可以高效工作。

3 性能評估

前面提到，層次化計算范式已經出現在諸多應用場景中，如分布式檢索、智慧城市等。本節在平安校園場景中對設計的方案進行評估。平安校園場景的傳輸時延相對較小且較穩定，因此子任務的處置時長占據了絕大部分完成時長。

本節在實際場景中對本文提出的解決方案進行評估，并將其與其它3種算法進行了對比。在評估過程中，試圖回答以下問題：第一，TPD能否有效優化分布式應用的總延遲？第二，TPD的性能與理論上的最優方案之間的差距有多大？

性能評估的主要結果總結如下。

延遲優化：評估結果表明，TPD可以顯著降低不同模式的子任務的平均路由時延、平均處置時長及總延遲。因而，TPD可以有效降低分布式應用的響應時間。

最優性差距：為了明確TPD與理論上的最優性能之間的差距，將其與離線最優結果進行對比，并定義了最優性差距指標。在實際場景下，TPD的最優性差距比其它策略要小。上述結果肯定了TPD在在線調度場景中的有效性。

3.1 實驗設定

某平安校園系統部署在某大型校園中，該校園面積超過3 000 000平方米。校園中共部署有超過600個攝像頭(源節點)、12個監控點(IPN節點)以及1個指揮中心(目標節點)。如圖2所示，校園中共有12個重點部位，如博物館、圖書館、教學樓等。為了更好監控這些重點部位的情況，每個重點部位都部署有一個監控點。特別的，編號為12的位置為該校主樓，主樓也是指揮中心所在的位置。每個監控點都部署有一臺網絡視頻錄像機(network video recorder)。攝像頭將視頻片段和照片等發送到其中一臺網絡視頻錄像機上，網絡視頻錄像機則將這些視頻片段和照片進行轉碼，并轉發給指揮中心。在指揮中心，這些視頻將被展示在大屏幕上，并被進一步分析(比如火情監控或入侵檢測等)。

圖2 平安校園系統平面圖

在該平安校園系統中，具體考慮一個入侵檢測應用。攝像頭會自動檢測并拍攝移動物體，拍攝的視頻幀率為30 fps。根據大型的視頻分析數據集可知，時長為5 s到15 s之間的視頻片段足以檢測入侵。因此，在實驗中，假設視頻片段的長度為5 s到15 s之間(即150幀到450幀之間)。由于增量化部署策略，平安校園系統中的網絡視頻錄像機共有兩代，其中有8臺為高性能網絡視頻錄像機，4臺為低性能網絡視頻錄像機。高性能網絡視頻錄像機可以最多并行轉碼64路視頻片段，每路的平均轉碼速率為1200 fps；低性能網絡視頻錄像機可以最多并行轉碼32路視頻片段，每路的平均轉碼速率為600 fps。經過實地測量，該平安校園中，任意兩個地點之間的路由時延在0.005 s到0.015 s之間。因此，在實驗中，將路由時延設定為lmk∈[0.005,0.03] s， 并假設路由時延與轉發路徑的長度成正比。

3.2 算法性能

接下來驗證TPD方法的有效性。

在平安校園場景中，考慮兩種子任務產生模式：穩定模式和突發模式。穩定模式描述了子任務產生的通常狀態，即子任務以穩定地低速率產生。突發模式則描述了一些突發的子任務，即子任務的產生速率突然增大，但僅持續了較短時間。在穩定模式下，設定：子任務數M=10000，子任務產生速率λ=0.7。在突發模式下，設定：子任務數M=600，子任務產生速率λ=5。每種子任務產生模式均運行100次。

性能評估中，參與比較的算法如下所列。特別的，PoD、CRO和RND這3種算法中，IPN按照EDD(earliest due date first)策略調度其上的子任務。為了充分驗證算法性能，性能評估中，每種算法分別模擬運行100次。

TPD：第3節設計的延遲感知的Power-of-D算法。

僅考慮處置時間優化(Power-of-D，PoD)：經典的Power-of-Two策略，即以均等概率隨機選取兩個IPN，而后將新的子任務分配給隊列較短的IPN上。Power-of-Two是一個典型的以最小化處置時間為目標的策略。

僅考慮路由時延優化(consider routing only，CRO)：一個在線版本的僅考慮路由時延優化策略，先以均等概率隨機選取兩個IPN節點，而后將新子任務分發到具有較短路由時延的IPN上。

隨機(Random，RND)：每次將新子任務分發到一個隨機的IPN。

首先比較了處置時長。平安校園場景下，圖3和圖4分別比較了不同算法在入侵檢測應用中，穩定模式和突發模式下的子任務的平均處置時長?？梢钥吹?，TPD明顯優于其它算法，因為TPD在任務調度中考慮了處置時長優化。然而，PoD盡管也考慮了處置時長的因素，但是其表現與CRO相差無幾。這肯定了第2.2節的討論，Power-of-D范式在異構系統中是低效的。

圖3 穩定模式下的平均處置時長

圖4 突發模式下的平均處置時長

其次比較了路由時延。圖5及圖6分別展示了平安校園場景中不同模式下的子任務的平均路由時延。可以看到，TPD和CRO在兩種子任務模式下均優于其它方案。這是因為在選擇最優的IPN時，由于方程式(12)和方程式(13)，TPD通常會抽樣到多于2個備選IPN。因而，TPD比CRO更有可能找到更短的路由路徑，進而產生更短的路由時延。

圖5 穩定模式下的平均路由時延

圖6 突發模式下的平均路由時延

最后比較了總延遲及與最優性差距。如圖7和圖8所示，TPD下子任務的總延遲最小。這說明TPD擅長調度不同模式的子任務。特別的，為了驗證TPD算法能否有效優化分布式應用的總延遲，還定義了最優性差距Gap來量化算法的最優性

(17)

式中：T是使用上述算法進行任務調度時的總延遲，TLB是總延遲的下界。在線場景中，對于產生的每個子任務，都遍歷所有的IPN以確定全局最優的IPN和全局最優的子任務處理順序，進而得到總延遲的下界TLB。如圖9和圖10所示，TPD的最優性差距在任何情況下都比其它策略要小。上述結果肯定了TPD在在線調度場景中的有效性。

圖7 穩定模式下的總延遲

圖8 突發模式下的總延遲

圖9 穩定模式下的最優性差距

圖10 突發模式下的最優性差距

4 結束語

本文研究了分布式應用中的任務調度問題。近年來，互聯網、移動互聯網、物聯網飛速發展，分布式應用產生的數據體量越來越大、異構性越來越強。所以，原始數據從源節點發出后，需要在中間處理節點上進行預處理，再由中間處理節點將整合處理后的數據轉發給目標節點。在這種層次化計算范式下，任務完成時間受到網絡資源(路由時延)和計算資源(中間節點的計算能力、處理能力)的雙重約束，受到子任務的分配策略和調度策略的雙重影響。

本文致力于在異構層次化計算范式下，優化分布式應用的總延遲。具體地，設計了延遲感知的Power-of-D算法用于子任務的在線分發及調度，該算法將經典的Power-of-D范式擴展到了層次化計算范式中，可以實現任務路由時延、處理時長和排隊時長的聯合優化。最后，基于真實系統場景，對本文提出的解決方案進行了評估，評估結果肯定了本方案的有效性。