云業務切割算法的研究

鄭小蘭

（福州理工學院實驗實訓中心，福建福州 350506）

近年來隨著云計算技術的推行，數據中心網絡的服務能力得到了空前的發揮。究其原因，云技術可通過計算出離散分布的物理主機服務器的資源統一虛擬化后為云用戶提供良好的用戶體驗（QoE）。當然，此QoE還和其他諸多因素[1]有關。比如在云技術為用戶請求提供計算響應期間，數據中心資源的負載均衡程度、分布集中程度、以及異構資源整合度等都在一定程度上影響著云計算水平的發揮。為進一步發揮云計算技術服務潛能提高云用戶的響應率，業界從不同角度構思了云業務數據調度算法。該算法是將云用戶提交的業務適配到云系統中具有足夠計算開銷的物理服務器。可見算法的調度效率直接決定了算法的科學成效。其中衡量調度效率[2]的重要標準便是云用戶提交任務的響應時長。為提高調度效率，通常對云業務對應的數據實施切割后派發給那些尚有冗余資源的物理服務器來執行。雖然當前業界已有不少關于云調度策略的研究，然而卻未涉及云數據科學切割的討論。諸如，云數據需要被切割成多少個子集，每個子集的規模多大，以及每個子集的云數據應該適配給哪些具有冗余計算開銷的物理服務器等問題。基于此，以云用戶QoE為目標構思一種云業務切割算法，致力于最小化云數據切割和冗余資源適配對云業務執行的響應時長。

1 算法原理

在云用戶提交云業務后，云系統中的業務管理模塊將讀取云調度算法將該云業務分配給合適的資源開銷來執行該項任務。隨著大數據技術的融合應用以及云用戶對業務要求的增加，云調度算法往往忙碌于處理這些大規模數據。一旦遇到一些計算量較大的任務時可能令某個服務器為此付出很大的時延代價。面對這樣情形，云系統需首先組織各類閑置資源將待響應的云業務數據切割成多個子集。將此處的各類閑置資源設備定義為n個，最多可將云業務切割出n個子集。然后讀取云調度算法將此n個數據子集適配到n個資源節點處接受計算處理。n的取值是云業務數據切割算法要解決的問題所在。當然，在云環境下發起的業務請求無論在規模、時間、數據量方面均是呈現隨機突發[3]特征。

據此分析，可將待處理的云業務列表記作S=[S1,S2,…,Sm,…,Sn]，這些云業務所對應的數據量規模為D=[D1,D2,…,Dm,…,Dn]。考慮到并非所有云業務都可切割出一樣規模的數據子集，故將云業務Sm所能允許切割的最多數據子集記作Zm=Dm/Lm。其中Lm指云業務可被切割的最小粒度。將可用的n個資源設備中的第m個資源設備的數據傳輸能力Em(T)、內存大小Em(M)、計算能力Em(C)參量組合成衡量其資源大小的數組Em=[T,M,C]，則所有可用資源的集合形式化為E=[E1,E2,…,Em,…,En]。由前述可知在絕對理想部署云任務算法時云業務Sm最多可以被分配到Zm個資源設備上。然而并非m個資源設備均可用，故需增加后續資源節點一塊納入備選調度集合，也就是要使n=Zm。在進行數據切割時，數據子集均可能被派發到E=[E1,E2,…,Em,…,En]中的某一個設備；同樣地，對于E=[E1,E2,…,Em,…,En]在實施調度時，子集數量多達也可能達到n個。故，此處云業務Sm的數據子集參考Lm定義為n。若實際的數據子集規模并未超過n，則剩下的子集置零。令Dm被切割后的第k（n≥k）個數據子集為Amk，則云業務Sm的數 據切割方案集形式化為Am=[Am1,Am2,…,Amn,…,Amk]。再把Amk適配在Ek上并使其等同于Dmk。于是可得為使切割更加科學，現引入切割系數χk，則有

研究的云業務數據切割算法時延代價由云數據切割過程和數據子集傳輸過程兩部分構成。首先假設單位時間內E=[E1,E2,…,Em,…,En]處理數據子集的數量超過數據子集被適配[4]到E=[E1,E2,…,Em,…,En]的數量。設處理數據切割過程耗時dk,則Amk的傳輸時延代價為Dmk-F=dk+[(χk·Dm/Ek(T))]；Ek處理Amk的時間成本為Dmk-C=[(χk·Dm/Ek(C))]。于是將Amk派發到Ek的時長Dmk-P=Dmk-C+Dmk-F。受理云業務Sm的整個過程需要的時間成本決定于該業務的所有數據子集在E=[E1,E2,…,Em,…,En]上的最大時長。因此，將該時間成本記作在受理云業務過程中云數據切割算法需要結合E=[E1,E2,…,Em,…,En]的實際資源情況，因此將云業務切割算法時間成本的計算優化為：

同時要求云數據切割系數滿足χ=χ1+χ2+…+χm+…+χn=1。該優化后的時間成本目標函數的極優值便是符合云用戶QoE 的最科學的云業務切割方案。當采用基于最大熵函數法對該目標函數求取極小極大極優解時發現存在多個變量。故求解時把極優目標變換成KKT條件。

于是假設Dm-T是一個含χ變量的h(χ)函數，即h(χ)=Dm-T。令云業務Sm中數據子集的處理時延為D1P,D2P,…,DmP,…,DnP，若第f(n≥f)個子集處理時延Df最長，則Df-P≥Dm-P。將Dm-Df賦為δm(χ),則有不等式約束δm(χ) ≤0；將賦為Bm(χ)，則有不等式約束Bm(χ)=0。再將算法時間成本目標函數問題的求解變換為繼續構建基于約束[5]的拉格朗日式

其中αm和βm代表約束參數。針對基于約束的極優化問題的求解可通過KKT 條件來解決。將式L的KKT條件表示為?L(α,β,χ)/??χ=同時有：αm·δm(χ)=0；αm≥0;βm≠0。所以當算得極優值[6]的時候δm(χ)必定為零。因此對于云業務Sm的n個數據子集而言，滿足

如果當前可供切割的子集規模是Yn，首次切割后的數據余量是YDm，對云業務進行再度切割的方案集合記作YAm=[YAm1,YAm2,YAm3,…,YAmn],YAmk相應的規模為YDmk。再度切割的過程為：首先從χ=χ1+χ2+…+χm+…+χn=1 中找出系數最大的χQ，求出子集AmQ的規模此時可供切割的子集數量和剩下的數據量依次是和YDm-YDmQ。若兩者中的一者為零，則YAm剩下的待分配的數據子集規模為零，不在進行切割。反之繼續下一步操作。其次，將χQ賦值零，繼續進行AmQ的規模YDmQ的計算。然后得到[YAm=[YAm1,YAm2,YAm3,…,YAmn]同時按照YAmk的規模YDmk對云業務的相關數據執行切割。當YDmk為零時說明此時已沒有YAmk可供適配；反之，將YAmk適配到Ek。

2 算法實施

首先，初始化云業務數據切割算法各參量并根據云業務Sm對應的數據規模及其可被切割的最小粒度Lm算出該業務可被切割的數據子集數n，進而選出n可用的資源設備納入備選調度[7]集合。其次，結合切割系數計算式為n個子集算出理想狀態下的數據切割比例。接下來開始執行云數據子集的再度切割。首先將上一步驟所算得切割比例中最大值χQ代入計算式算出AmQ的規模其次算出切割后余下的尚未切割的數據量規模并判斷能夠可以被繼續切割。若是可以，將當前已被切割的子集的系數置零然后繼續執行χQ的選擇工作一直到余下的數據量等于零為止。最后將n個預切割的數據子集中尚未適配數據的子集置零，從而算得云業務Sm數據子集再度被切割的調度方案集YAm=[YAm1,YAm2,YAm3,…,YAmn]。

3 方案測試

傳統上對于云用戶提交的云業務進行分解的方法主要傾向于采用基于均分的思想。此類基于均衡分解的算法（BD 算法）易實現且效率高，但部署在云業務量很大的情形下將因欠缺考慮算法對云系統硬件的依賴性而使可行性顯著下降。反之，基于兩度考量的云業務切割算法（TC算法）不僅考慮到了云數據切割可行性因云業務數據規模而異，也考慮到了方案部署效力因資源設備性能[8]而異。兩種算法方案將被部署在Cloudsim 平臺上接受和對比。設定Cloudsim 平臺上的云業務規模300 個，物理主機規模300個，云業務數據規模最多有30000個，云業務可被切割的最小粒度是200個，云業務對網絡資源的要求200Mb/s。收集的數據均在每組開展50 次測試后取均值統計而來。所開展的實驗主要通過時延代價指標考察云用戶的QoE 進而驗證算法的科學性，且測試期間暫不考慮多個云業務因排隊規則[9]的不同對算法造成的影響。

圖1 所示曲線描述的是物理主機規模的變化對兩種算法的時延代價造成的影響力。從曲線走勢不難觀察到TC 算法的時延代價總體比BD 算法要低。尤其在物理主機規模低于160 個的時候這種優勢表現的更加明顯。究其原因，TC 算法在可供調度的物理資源不多的情形下能夠根據物理主機設備性能差異性適時科學地制定云數據切割系數和比例，這使得云業務對應的數據能夠在較短的時間內處理完畢，算法優勢得到明顯發揮。而BD 算法卻未能為不同硬件環境下云業務量身制定科學的數據切割系數。當物理主機規模超過160 個意味著此時可用物理資源充裕，因此兩種算法下的云業務均可被切割成很小的數據子集，這些子集被適配到資源節點上時其對應的數據量很小，處理該任務的時間成本就很低。因此兩種算法下的時延代價較此前有明顯的回落。即便如此，TC 算法始終因其科學的切割機制而稍顯優勢。

圖1 物理主機規模對算法的影響力

圖2 所示曲線描述的是在相同資源規模的前提下云用戶提請的云業務數據規模對兩種算法的影響力。顯而易見，兩種算法下的時延代價和云業務數據量呈正比。但總體而言TC 算法的時延代價依舊小于BD 算法。從曲線走勢可見時延代價的拐點在9 000。在拐點到來之前由于待處理的數據不多，數據子集被傳輸適配到物理主機上的規模也就很小，兩種算法下的時延成本接近。在此拐點之后TC 算法的優勢得到發揮，該算法可以根據云系統中各個可用資源節點的開銷能力動態調整云數據切割機制并且能夠實施兩次切割評估。進一步增加了TC算法客觀性和動態適應性[10]。

圖2 云業務數據規模對算法的影響力

4 結語

云業務切割策略的構思是從全局角度出發以時延代價為目標，為云用戶設計的一種適應能力較強的算法方案。該方案通過引入切割系數為不同環境下的云業務提供數據處理機制。測試結果顯示，云業務切割算法表現出了明顯的相對優勢。