基于蟻群算法的計(jì)算引擎均衡部署數(shù)學(xué)建模

孟小燕，趙希武

(1.內(nèi)蒙古師范大學(xué)，內(nèi)蒙古 呼和浩特 010051；2.內(nèi)蒙古師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，內(nèi)蒙古 呼和浩特 010051)

1 引言

大數(shù)據(jù)是云計(jì)算發(fā)展的產(chǎn)物，不僅數(shù)量多，且還具有多樣化、復(fù)雜化等特性。計(jì)算分析大數(shù)據(jù)可獲得更多有用信息，有助于用戶(hù)更加全方位了解各類(lèi)業(yè)務(wù)流程，是促進(jìn)業(yè)務(wù)發(fā)展的必然要求。大數(shù)據(jù)的主要特征為規(guī)模大，用戶(hù)獲得數(shù)據(jù)的方式非常簡(jiǎn)單，且用戶(hù)在點(diǎn)擊和瀏覽過(guò)程中又會(huì)生成較多新的數(shù)據(jù)；種類(lèi)多，數(shù)據(jù)更新頻率很快，這是與傳統(tǒng)數(shù)據(jù)相比最明顯的特征；價(jià)值密度低，雖然數(shù)據(jù)量增長(zhǎng)速度飛快，但里面蘊(yùn)含的有用信息卻較少，必須通過(guò)計(jì)算來(lái)獲得有用數(shù)據(jù)。由于數(shù)據(jù)量巨大，對(duì)數(shù)據(jù)計(jì)算分析能力提出更高要求，單一引擎已經(jīng)不能滿(mǎn)足計(jì)算需求，為此，分布式計(jì)算引擎應(yīng)運(yùn)而生，充分使用單個(gè)引擎的計(jì)算能力實(shí)現(xiàn)大規(guī)模數(shù)據(jù)的處理。

但是分布式引擎的應(yīng)用還不夠成熟，常出現(xiàn)計(jì)算負(fù)載不均衡狀況，降低計(jì)算能力，影響工作效率。又因開(kāi)為不同引擎的硬件性能各不相同，進(jìn)一步加大部署難度。為此，一些學(xué)者針對(duì)這一問(wèn)題紛紛展了研究。

文獻(xiàn)[1]基于貪心啟發(fā)式算法建立計(jì)算引擎均衡部署框架，定義數(shù)據(jù)傳輸機(jī)制，利用限定范圍的可控參數(shù)約束傳輸過(guò)程，結(jié)合二次分拆原理，制定分拆計(jì)劃，通過(guò)貪心啟發(fā)式算法實(shí)現(xiàn)分拆結(jié)果的均衡部署。文獻(xiàn)[2]設(shè)計(jì)了一種適用于大數(shù)據(jù)計(jì)算的隨機(jī)樣本劃分模型。將大數(shù)據(jù)表示成數(shù)據(jù)塊集合形式，儲(chǔ)存在不同節(jié)點(diǎn)上；估計(jì)大數(shù)據(jù)的特征，建立回歸分析模型，利用Alpha計(jì)算架構(gòu)實(shí)現(xiàn)數(shù)據(jù)清洗，減輕計(jì)算量，再通過(guò)概率密度函數(shù)將計(jì)算引擎部署到最佳數(shù)據(jù)塊上。

上述算法雖然能夠?qū)崿F(xiàn)負(fù)載均衡，但會(huì)出現(xiàn)系統(tǒng)能耗較高、響應(yīng)時(shí)間長(zhǎng)等問(wèn)題。為此，本文設(shè)置了均衡部署的約束條件，在多方面約束下，利用蟻群算法建立部署數(shù)學(xué)模型。蟻群算法是根據(jù)螞蟻覓食設(shè)計(jì)的，可以不斷迭代尋優(yōu)[3]，使方法能夠根據(jù)約束條件實(shí)現(xiàn)動(dòng)態(tài)調(diào)節(jié)，最終獲得全局最優(yōu)解，即最優(yōu)部署方案。

2 大數(shù)據(jù)計(jì)算引擎工作模式與流程分析

2.1 計(jì)算模式架構(gòu)

大數(shù)據(jù)計(jì)算模式的選擇是數(shù)據(jù)處理過(guò)程中最為關(guān)鍵的環(huán)節(jié)。在數(shù)據(jù)產(chǎn)生前期，系統(tǒng)針對(duì)已經(jīng)存在的數(shù)據(jù)做簡(jiǎn)單處理，隨數(shù)據(jù)量的增加，處理速度顯得尤為重要，此時(shí)應(yīng)增加計(jì)算內(nèi)存，提高系統(tǒng)處理速度。

現(xiàn)階段，大數(shù)據(jù)計(jì)算模式主要包括流式[4]和批量式[5]兩種。其中，流式計(jì)算利用Spark平臺(tái)[6]實(shí)現(xiàn)，在計(jì)算周期內(nèi)通過(guò)數(shù)據(jù)庫(kù)達(dá)到信息共享目的。數(shù)據(jù)計(jì)算采用引擎分布式并行處理方案，多個(gè)引擎節(jié)點(diǎn)采集來(lái)自不同數(shù)據(jù)源的數(shù)據(jù)，再進(jìn)行獨(dú)立計(jì)算，并將運(yùn)算結(jié)果保存到數(shù)據(jù)庫(kù)中。因此，需最大程度保證引擎部署負(fù)載均衡，以滿(mǎn)足系統(tǒng)快速、穩(wěn)定計(jì)算的要求。批量式計(jì)算利用的是分而治之思想，將待處理的數(shù)據(jù)劃分到多個(gè)節(jié)點(diǎn)上，減少計(jì)算開(kāi)銷(xiāo)，再匯總所用節(jié)點(diǎn)處理結(jié)果，反復(fù)操作上述過(guò)程，直至獲得理想結(jié)果。此種模式的發(fā)展時(shí)間很長(zhǎng)，在處理架構(gòu)、分析挖掘、可視化等方面均有應(yīng)用。但是，處理速度較慢，大多應(yīng)用在對(duì)計(jì)算時(shí)間要求不高的任務(wù)中，此外其處理結(jié)果精度較高。

綜合上述分析，兩種計(jì)算模式均有優(yōu)缺點(diǎn)。因此，本文將兩種方式相結(jié)合，設(shè)計(jì)了雙模式大數(shù)據(jù)計(jì)算架構(gòu)[7]，如圖1所示。

圖1 大數(shù)據(jù)計(jì)算模式架構(gòu)圖

2.2 計(jì)算流程

根據(jù)雙模式計(jì)算引擎架構(gòu)特征，設(shè)計(jì)計(jì)算流程，該流程共包括以下階段：

1)采集階段：是大數(shù)據(jù)計(jì)算的基礎(chǔ)，同時(shí)采集多個(gè)外部數(shù)據(jù)源，獲取實(shí)時(shí)數(shù)據(jù)，并統(tǒng)一數(shù)據(jù)格式[8]；

2)數(shù)據(jù)預(yù)處理：使用批量計(jì)算方法分析歷史數(shù)據(jù)，完成大數(shù)據(jù)基本處理，確定數(shù)據(jù)之間的關(guān)聯(lián)模型，為流式計(jì)算提供數(shù)據(jù)基礎(chǔ)。此階段數(shù)據(jù)的主要特征是數(shù)量大、多樣化且結(jié)構(gòu)復(fù)雜。

3)計(jì)算階段：使用分布式引擎實(shí)時(shí)計(jì)算處理后的數(shù)據(jù)，此階段數(shù)據(jù)突發(fā)性強(qiáng)且伴隨一定無(wú)序性特征。

4)操控階段：根據(jù)計(jì)算結(jié)果給出決策意見(jiàn)。

在雙模式計(jì)算架構(gòu)下，按照上述工作流程，即可通過(guò)分布式引擎實(shí)現(xiàn)大數(shù)據(jù)計(jì)算。但是在計(jì)算過(guò)程中，由于任務(wù)分配不均等導(dǎo)致負(fù)載不均衡，為此有必要對(duì)引擎部署進(jìn)行數(shù)學(xué)建模，平衡任務(wù)分配，提高計(jì)算效率。

3 大數(shù)據(jù)計(jì)算引擎均衡部署數(shù)學(xué)建模

3.1 均衡部署約束模型

1)計(jì)算任務(wù)數(shù)量約束

在上述計(jì)算環(huán)境下，分布式引擎的硬件配置往往存在差異，導(dǎo)致計(jì)算任務(wù)總量出現(xiàn)不均勻現(xiàn)象。假設(shè)引擎節(jié)點(diǎn)集合表示為N={n1，n2，…，n|N|}，任意一個(gè)節(jié)點(diǎn)中包含的數(shù)據(jù)總量是R={rn1，rn2，…，rn|N|}，拓?fù)渲写嬖诘挠?jì)算任務(wù)總量記作|T|，因此有

(2)

式中，Tni代表引擎ni上執(zhí)行的任務(wù)總數(shù)。為確保數(shù)量分配的公平性[9]，任務(wù)數(shù)量應(yīng)與擁有的資源總數(shù)之間呈正比，這對(duì)某引擎ni∈N而言，存在

(3)

式中，K屬于一個(gè)固定常數(shù)，根據(jù)式(2)和(3)能夠得出

(4)

因此有

(5)

將分配數(shù)量公平性作為約束條件，結(jié)合引擎配置情況，通過(guò)人工方式設(shè)定引擎節(jié)點(diǎn)可接收的最大任務(wù)數(shù)量。針對(duì)某引擎ni而言，其計(jì)算任務(wù)容量表達(dá)式如下

(6)

當(dāng)每個(gè)引擎的配置相同時(shí)，沒(méi)有異構(gòu)特征[10]，則各引擎具備相同數(shù)量資源。此時(shí)，式(6)可表示為

(7)

若t時(shí)間點(diǎn)引擎ni已經(jīng)被部署的計(jì)算任務(wù)數(shù)量是|Tii(t)|，則引擎剩余計(jì)算容量表示為

(8)

2)負(fù)載均衡約束

若引擎nk被部署到執(zhí)行計(jì)算任務(wù)tij的節(jié)點(diǎn)范圍內(nèi)，記作f(tij)=nk，其另一種形式為f-1(nk)=tij；若引擎nk被部署到執(zhí)行任務(wù)集合Tnk={t11，t12，…，tij}的節(jié)點(diǎn)上，此時(shí)記作f(Tnk)=nk或f-1(nk)=Tnk。上述的f即為部署法則[11]。

假設(shè)某帶權(quán)拓?fù)鋄12]內(nèi)計(jì)算任務(wù)集合是T，nx表示眾多引擎中隨機(jī)一個(gè)，引擎nk被部署到f-1(nk)任務(wù)中，引擎nl(l≠k)則被部署在f-1(nl)任務(wù)集合中，因此有

(9)

并且

f-1(nk)∩f-1(nl)=?(k≠l)

(10)

(11)

利用OC表示所有引擎的負(fù)載總和，在同構(gòu)情況下，各引擎的負(fù)載會(huì)隨任務(wù)數(shù)量的變化而改變，但OC保持不變

(12)

若將負(fù)載總和平均分配到各引擎上，則每個(gè)引擎需要承擔(dān)的負(fù)載表示為

(13)

3)最優(yōu)部署開(kāi)銷(xiāo)約束

部署開(kāi)銷(xiāo)與數(shù)據(jù)流大小相關(guān)，數(shù)據(jù)流越大，部署時(shí)間就越長(zhǎng)，系統(tǒng)能耗就越高。假設(shè)任務(wù)tij和tkl二者的數(shù)據(jù)流大小表示為vij，kl或vkl，ij，若要保證最優(yōu)部署開(kāi)銷(xiāo)，需最大程度減少待計(jì)算的數(shù)據(jù)流總量[13]，即

(14)

還可表示為

(15)

3.2 基于蟻群算法的均衡部署數(shù)學(xué)建模

在計(jì)算任務(wù)數(shù)量、負(fù)載均衡和最優(yōu)開(kāi)銷(xiāo)約束下，利用蟻群算法完成引擎均衡部署數(shù)學(xué)建模。

蟻群算法需先對(duì)信息素函數(shù)τij(t)做初始化處理，該函數(shù)代表引擎nx針對(duì)某任務(wù)Ti表現(xiàn)出的信息素濃度，結(jié)合引擎計(jì)算能力[14]MIPSj、通信帶寬Bandwidthj完成初始化操作

(16)

式中，D為常數(shù)。

實(shí)現(xiàn)函數(shù)初始化后，利用下述表達(dá)式得出引擎nx被部署到任務(wù)Ti處的幾率

(18)

(20)

(22)

式中，Dmax代表經(jīng)過(guò)多次迭代后得到的最優(yōu)解。

4 仿真設(shè)計(jì)與分析

為評(píng)估所建數(shù)學(xué)模型性能，設(shè)置仿真。仿真基于分布式服務(wù)器系統(tǒng)，該平臺(tái)可靠性高、具有較強(qiáng)的容錯(cuò)能力。為突出本文方法優(yōu)勢(shì)，利用貪心啟發(fā)式算法、隨機(jī)樣本劃分模型與所提方法的仿真結(jié)果進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如下。

1)響應(yīng)時(shí)長(zhǎng)性能分析

部署響應(yīng)時(shí)間影響著大數(shù)據(jù)計(jì)算效率，與用戶(hù)滿(mǎn)意度密切相關(guān)。隨著用戶(hù)并發(fā)請(qǐng)求的增加，三種算法的平均響應(yīng)時(shí)間仿真結(jié)果如圖2所示。

圖2 不同算法部署響應(yīng)時(shí)長(zhǎng)對(duì)比圖

分析圖2得出：隨著用戶(hù)并發(fā)數(shù)量不斷增加，所提方法的響應(yīng)時(shí)長(zhǎng)稍有上升趨勢(shì)，待并發(fā)請(qǐng)求量達(dá)到200個(gè)時(shí)，響應(yīng)時(shí)間不再上升，達(dá)到平穩(wěn)趨勢(shì)，而隨機(jī)樣本劃分模型起初的響應(yīng)時(shí)長(zhǎng)與所提方法接近，但后續(xù)上升速度較快。整體而言本文方法能夠快速部署計(jì)算引擎，減少用戶(hù)等待時(shí)長(zhǎng)，這是因?yàn)橄伻核惴ň哂休^強(qiáng)的尋優(yōu)能力，可以快速找到部署最優(yōu)解。

2)引擎負(fù)載均衡評(píng)價(jià)

計(jì)算引擎部署最重要的就是負(fù)載均衡，本文利用下述評(píng)價(jià)函數(shù)判斷負(fù)載均衡情況。

(23)

式中，finishTime(I)表示使用某種部署方案完成全部計(jì)算任務(wù)所需時(shí)間，即max(VMTime(VMi))，M為計(jì)算引擎數(shù)量。能夠看出DLB(I)值越高，引擎利用效率也越高，表明負(fù)載更加均衡。三種算法的負(fù)載均衡對(duì)比結(jié)果如圖3所示。

圖3 不同方法負(fù)載均衡對(duì)比圖

圖3顯示，隨著大數(shù)據(jù)計(jì)算任務(wù)的增多，在引擎數(shù)量相同條件下，本文算法的負(fù)載均衡函數(shù)值始終處于較高水平，沒(méi)有顯著變化趨勢(shì)。表明該部署方法的負(fù)載均衡情況不會(huì)受到計(jì)算任務(wù)量的影響，而其它兩種方法受其影響較大，當(dāng)計(jì)算任務(wù)過(guò)多時(shí)，無(wú)法保證部署均衡。

3)部署能耗分析

計(jì)算能耗是引擎部署方案實(shí)用性的體現(xiàn)，若能耗低，系統(tǒng)能承載的計(jì)算任務(wù)量就可以加大，本次實(shí)驗(yàn)分別從系統(tǒng)整體能耗和單位計(jì)算量能耗兩方面比較三種算法性能，仿真結(jié)果分別如圖4所示。

圖4 不同方法下系統(tǒng)整體能耗圖

由圖4看出，三種部署方法消耗的系統(tǒng)能量變化趨勢(shì)基本相同，其中本文模型消耗的能量最低，可保證系統(tǒng)穩(wěn)定運(yùn)行。這是因?yàn)楫?dāng)計(jì)算任務(wù)量相等時(shí)，引擎數(shù)量增加會(huì)減少單位計(jì)算量，因此單個(gè)引擎的所需能耗會(huì)下降。

5 結(jié)論

現(xiàn)階段，分布式系統(tǒng)廣泛應(yīng)用在大數(shù)據(jù)處理領(lǐng)域，但計(jì)算引擎均衡部署影響著其應(yīng)用效果。為此，本文利用蟻群算法建立均衡部署模型。仿真結(jié)果表明，所建模型在實(shí)現(xiàn)負(fù)載均衡的同時(shí)還能減少計(jì)算時(shí)間，有助于提高用戶(hù)滿(mǎn)意度。但該模型的研究還有進(jìn)一步優(yōu)化的空間，例如增加負(fù)荷約束向量，驗(yàn)證此模型下的大數(shù)據(jù)計(jì)算質(zhì)量。此外，考慮到大數(shù)據(jù)的動(dòng)態(tài)性與靈活性，還需優(yōu)化蟻群算法，避免因歷史信息累計(jì)而無(wú)法構(gòu)建新路徑的問(wèn)題。