云業(yè)務(wù)切割算法的研究

鄭小蘭

（福州理工學(xué)院實驗實訓(xùn)中心，福建福州 350506）

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

1 算法原理

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

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

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

同時要求云數(shù)據(jù)切割系數(shù)滿足χ=χ1+χ2+…+χm+…+χn=1。該優(yōu)化后的時間成本目標(biāo)函數(shù)的極優(yōu)值便是符合云用戶QoE 的最科學(xué)的云業(yè)務(wù)切割方案。當(dāng)采用基于最大熵函數(shù)法對該目標(biāo)函數(shù)求取極小極大極優(yōu)解時發(fā)現(xiàn)存在多個變量。故求解時把極優(yōu)目標(biāo)變換成KKT條件。

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

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

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

2 算法實施

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

3 方案測試

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

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

圖1 物理主機(jī)規(guī)模對算法的影響力

圖2 所示曲線描述的是在相同資源規(guī)模的前提下云用戶提請的云業(yè)務(wù)數(shù)據(jù)規(guī)模對兩種算法的影響力。顯而易見，兩種算法下的時延代價和云業(yè)務(wù)數(shù)據(jù)量呈正比。但總體而言TC 算法的時延代價依舊小于BD 算法。從曲線走勢可見時延代價的拐點在9 000。在拐點到來之前由于待處理的數(shù)據(jù)不多，數(shù)據(jù)子集被傳輸適配到物理主機(jī)上的規(guī)模也就很小，兩種算法下的時延成本接近。在此拐點之后TC 算法的優(yōu)勢得到發(fā)揮，該算法可以根據(jù)云系統(tǒng)中各個可用資源節(jié)點的開銷能力動態(tài)調(diào)整云數(shù)據(jù)切割機(jī)制并且能夠?qū)嵤﹥纱吻懈钤u估。進(jìn)一步增加了TC算法客觀性和動態(tài)適應(yīng)性[10]。

圖2 云業(yè)務(wù)數(shù)據(jù)規(guī)模對算法的影響力

4 結(jié)語

云業(yè)務(wù)切割策略的構(gòu)思是從全局角度出發(fā)以時延代價為目標(biāo)，為云用戶設(shè)計的一種適應(yīng)能力較強的算法方案。該方案通過引入切割系數(shù)為不同環(huán)境下的云業(yè)務(wù)提供數(shù)據(jù)處理機(jī)制。測試結(jié)果顯示，云業(yè)務(wù)切割算法表現(xiàn)出了明顯的相對優(yōu)勢。