孟小燕，趙希武

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

1 引言

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

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

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

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

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

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

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

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

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

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

2.2 計算流程

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

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

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

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

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

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

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

3.1 均衡部署約束模型

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

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

(2)

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

(3)

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

(4)

因此有

(5)

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

(6)

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

(7)

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

(8)

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

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

假設(shè)某帶權(quán)拓?fù)鋄12]內(nèi)計算任務(wù)集合是T，nx表示眾多引擎中隨機一個，引擎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ù)載會隨任務(wù)數(shù)量的變化而改變，但OC保持不變

(12)

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

(13)

3)最優(yōu)部署開銷約束

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

(14)

還可表示為

(15)

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

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

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

(16)

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

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

(18)

(20)

(22)

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

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

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

1)響應(yīng)時長性能分析

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

圖2 不同算法部署響應(yīng)時長對比圖

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

2)引擎負(fù)載均衡評價

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

(23)

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

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

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

3)部署能耗分析

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

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

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

5 結(jié)論

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