鄭小蘭

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

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

1 算法原理

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

據(jù)此分析，可將待處理的云業(yè)務(wù)列表記作S=[S1,S2,…,Sm,…,Sn]，這些云業(yè)務(wù)所對(duì)應(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個(gè)資源設(shè)備中的第m個(gè)資源設(shè)備的數(shù)據(jù)傳輸能力Em(T)、內(nèi)存大小Em(M)、計(jì)算能力Em(C)參量組合成衡量其資源大小的數(shù)組Em=[T,M,C]，則所有可用資源的集合形式化為E=[E1,E2,…,Em,…,En]。由前述可知在絕對(duì)理想部署云任務(wù)算法時(shí)云業(yè)務(wù)Sm最多可以被分配到Zm個(gè)資源設(shè)備上。然而并非m個(gè)資源設(shè)備均可用，故需增加后續(xù)資源節(jié)點(diǎn)一塊納入備選調(diào)度集合，也就是要使n=Zm。在進(jìn)行數(shù)據(jù)切割時(shí)，數(shù)據(jù)子集均可能被派發(fā)到E=[E1,E2,…,Em,…,En]中的某一個(gè)設(shè)備；同樣地，對(duì)于E=[E1,E2,…,Em,…,En]在實(shí)施調(diào)度時(shí)，子集數(shù)量多達(dá)也可能達(dá)到n個(gè)。故，此處云業(yè)務(wù)Sm的數(shù)據(jù)子集參考Lm定義為n。若實(shí)際的數(shù)據(jù)子集規(guī)模并未超過(guò)n，則剩下的子集置零。令Dm被切割后的第k（n≥k）個(gè)數(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í)延代價(jià)由云數(shù)據(jù)切割過(guò)程和數(shù)據(jù)子集傳輸過(guò)程兩部分構(gòu)成。首先假設(shè)單位時(shí)間內(nèi)E=[E1,E2,…,Em,…,En]處理數(shù)據(jù)子集的數(shù)量超過(guò)數(shù)據(jù)子集被適配[4]到E=[E1,E2,…,Em,…,En]的數(shù)量。設(shè)處理數(shù)據(jù)切割過(guò)程耗時(shí)dk,則Amk的傳輸時(shí)延代價(jià)為Dmk-F=dk+[(χk·Dm/Ek(T))]；Ek處理Amk的時(shí)間成本為Dmk-C=[(χk·Dm/Ek(C))]。于是將Amk派發(fā)到Ek的時(shí)長(zhǎng)Dmk-P=Dmk-C+Dmk-F。受理云業(yè)務(wù)Sm的整個(gè)過(guò)程需要的時(shí)間成本決定于該業(yè)務(wù)的所有數(shù)據(jù)子集在E=[E1,E2,…,Em,…,En]上的最大時(shí)長(zhǎng)。因此，將該時(shí)間成本記作在受理云業(yè)務(wù)過(guò)程中云數(shù)據(jù)切割算法需要結(jié)合E=[E1,E2,…,Em,…,En]的實(shí)際資源情況，因此將云業(yè)務(wù)切割算法時(shí)間成本的計(jì)算優(yōu)化為：

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

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

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

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

2 算法實(shí)施

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

3 方案測(cè)試

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

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

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

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

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

4 結(jié)語(yǔ)

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