基于云計(jì)算平臺(tái)的多數(shù)據(jù)庫(kù)并行調(diào)度算法仿真

楊 毅,熊 鷹

(華中科技大學(xué)網(wǎng)絡(luò)與計(jì)算中心,湖北 武漢 430074)

1 引言

隨著信息技術(shù)的飛速發(fā)展,互聯(lián)網(wǎng)+、云計(jì)算平臺(tái)等陸續(xù)被開發(fā),在云平臺(tái)背景下保證多數(shù)據(jù)庫(kù)同時(shí)運(yùn)行且負(fù)載均衡是十分重要的[1]。數(shù)據(jù)庫(kù)的可靠調(diào)度關(guān)系到云計(jì)算的全局運(yùn)行速率,對(duì)多數(shù)據(jù)庫(kù)實(shí)施調(diào)度,不但要和多個(gè)服務(wù)器合作,也涉及多數(shù)據(jù)庫(kù)的信息篩查。但并行調(diào)度的難點(diǎn)在于不同數(shù)據(jù)庫(kù)的調(diào)度信息量過(guò)大[2]、數(shù)據(jù)庫(kù)的計(jì)算機(jī)語(yǔ)句設(shè)置各不相等、復(fù)雜性較高等,大大影響了數(shù)據(jù)庫(kù)之間的信息交互。

針對(duì)并行調(diào)度問(wèn)題,文獻(xiàn)[3]通過(guò)構(gòu)建多信道鏈路模型,求解均衡調(diào)度問(wèn)題,創(chuàng)建雙適應(yīng)度函數(shù)并進(jìn)行恰當(dāng)調(diào)整,完成調(diào)度目標(biāo)。但該方法沒(méi)有考慮節(jié)點(diǎn)的真實(shí)負(fù)載狀態(tài),致使節(jié)點(diǎn)負(fù)載不均。文獻(xiàn)[4]融合多核集群拓?fù)涮卣?綜合消息傳遞與共享存儲(chǔ)編程模型,使用作業(yè)優(yōu)先級(jí)編碼模式轉(zhuǎn)移鳥巢位置,并將位置信息作為作業(yè)調(diào)度序列排列優(yōu)先級(jí)求解,實(shí)現(xiàn)調(diào)度任務(wù)。但該方法無(wú)法自動(dòng)完成作業(yè)調(diào)度序列的隊(duì)列選擇與設(shè)定,數(shù)據(jù)庫(kù)調(diào)度效率較低,適用性不高。

本文吸取文獻(xiàn)方法的優(yōu)勢(shì),針對(duì)其不足提出一種基于云計(jì)算平臺(tái)的多數(shù)據(jù)庫(kù)并行調(diào)度算法,組建高可信度云計(jì)算平臺(tái),利用MapReduce編程得到多數(shù)據(jù)庫(kù)并行調(diào)度模型,運(yùn)用離散粒子群算法完成高效率并行調(diào)度目標(biāo)。仿真結(jié)果證明,經(jīng)所提算法調(diào)度后,實(shí)現(xiàn)了網(wǎng)絡(luò)負(fù)載均衡,可應(yīng)用于多種類數(shù)據(jù)庫(kù),適用范圍廣。

2 云計(jì)算平臺(tái)構(gòu)建

云計(jì)算平臺(tái)涵蓋應(yīng)用層、平臺(tái)層與基礎(chǔ)設(shè)施層三個(gè)層次,以基礎(chǔ)設(shè)施層為例,引入可信根與信任傳遞思維,面向虛擬層實(shí)際特征,給用戶提供一個(gè)高度安全的云計(jì)算平臺(tái)[5]。云計(jì)算平臺(tái)構(gòu)建技術(shù)中最關(guān)鍵的就是虛擬化技術(shù),虛擬化是一種從底層硬件或軟件抽象出應(yīng)用程序、用戶操作系統(tǒng)。虛擬化的核心是服務(wù)器虛擬化,主要?jiǎng)澐譃榈讓佑布碌奶摂M化、宿主操作系統(tǒng)下的虛擬化兩種模式。

云平臺(tái)在創(chuàng)建過(guò)程中,需確保每個(gè)組件都能完整度量的同時(shí),得到系統(tǒng)控制權(quán)順序。構(gòu)建順序執(zhí)行信任鏈的過(guò)程為

Ii+1=Ii∧Vi(Si+1)

(1)

其中,Ii表示云平臺(tái)物理主機(jī)操作系統(tǒng)引導(dǎo)時(shí)第i個(gè)階段的完整性,如果第i個(gè)階段是完整的,那么Ii=1,反之Ii=0。Vi(Si+1)是第i個(gè)階段的度量控制組件,對(duì)引導(dǎo)序列內(nèi)第i+1個(gè)階段實(shí)施度量的參數(shù)。

以云計(jì)算設(shè)備Eucalyptus為基礎(chǔ),設(shè)計(jì)滿足多任務(wù)調(diào)度的可信云計(jì)算平臺(tái)結(jié)構(gòu)體系,如圖1所示。圖1內(nèi)的陰影部分代表云服務(wù)商對(duì)某些節(jié)點(diǎn)采取可信增強(qiáng)措施。交互接口是云計(jì)算平臺(tái)設(shè)計(jì)的用戶可見入口,是用戶開啟與停止運(yùn)作的服務(wù)接口[6]。云管理員利用集群控制器把虛擬機(jī)實(shí)例傳遞至不可信平臺(tái),實(shí)現(xiàn)云計(jì)算平臺(tái)最優(yōu)的存儲(chǔ)與計(jì)算效用。

圖1 云計(jì)算平臺(tái)架構(gòu)示意圖

3 基于離散粒子群的多數(shù)據(jù)庫(kù)并行調(diào)度算法

3.1 多數(shù)據(jù)庫(kù)并行調(diào)度模型

為實(shí)現(xiàn)多數(shù)據(jù)庫(kù)的有效調(diào)度,創(chuàng)建并行調(diào)度模型前,需要進(jìn)行如下優(yōu)化運(yùn)算。多數(shù)據(jù)并行調(diào)度時(shí)間序列擁有顯著的混沌特征,提取相關(guān)的混沌特征可以有效優(yōu)化模型的調(diào)度速率[7]。將數(shù)據(jù)庫(kù)調(diào)度的控制集合記作式(2)

(2)

融合并行策略與混沌因子,計(jì)算調(diào)度時(shí)間順序適應(yīng)值

(3)

最終將調(diào)度任務(wù)的效率描述成

φ=|θ-j|

(4)

其中,φ表示調(diào)度任務(wù)效率,θ表示遞增系數(shù)。

當(dāng)前多數(shù)云計(jì)算平臺(tái)將MapReduce編程模型應(yīng)用在海量數(shù)據(jù)庫(kù)的并行運(yùn)算中。MapReduce操作融合Map與Reduce函數(shù),將其傳輸至調(diào)度系統(tǒng),分配到可用計(jì)算資源。綜合以上運(yùn)算過(guò)程,將多數(shù)據(jù)庫(kù)并行調(diào)度模型表示成圖2。

圖2 并行調(diào)度模型

Map操作是把較大的任務(wù)劃分成若干子任務(wù),再把子任務(wù)分配至計(jì)算資源內(nèi)執(zhí)行運(yùn)作,利用Reduce操作獲得并行調(diào)度輸出結(jié)果[8]。把類資源均看作計(jì)算資源,設(shè)置運(yùn)行條件:已知子任務(wù)需要的計(jì)算量、計(jì)算速率和子任務(wù)在各計(jì)算資源內(nèi)運(yùn)行完畢的時(shí)間。如果子任務(wù)個(gè)數(shù)是M,計(jì)算資源個(gè)數(shù)是N,使用M×N矩陣描述每個(gè)計(jì)算資源內(nèi)任務(wù)運(yùn)行所需的時(shí)間。把多數(shù)據(jù)庫(kù)并行調(diào)度問(wèn)題簡(jiǎn)化成:怎樣把若干任務(wù)恰當(dāng)配發(fā)至計(jì)算資源,讓全部任務(wù)完成的總時(shí)間最小。

3.2 算法實(shí)現(xiàn)

并行調(diào)度模型構(gòu)建完畢后,融合基于離散粒子群的并行調(diào)度算法,實(shí)現(xiàn)在保證負(fù)載均衡前提下的多數(shù)據(jù)庫(kù)高質(zhì)量并行調(diào)度任務(wù)。利用離散粒子群法計(jì)算調(diào)度問(wèn)題,組建有效的粒子編碼結(jié)構(gòu),使用間接編碼模式完成各子任務(wù)的資源編碼,編碼長(zhǎng)度是當(dāng)前子任務(wù)的數(shù)量,一個(gè)編碼對(duì)應(yīng)一個(gè)并行調(diào)度方案[9]。

本文使用可靠性來(lái)定義離散粒子群算法中的實(shí)用度函數(shù),經(jīng)過(guò)不斷上升的迭代數(shù)量,完成高可靠性數(shù)據(jù)庫(kù)并行調(diào)度目標(biāo)。適應(yīng)度函數(shù)值可以準(zhǔn)確評(píng)估調(diào)度任務(wù)策略的優(yōu)劣,適應(yīng)度函數(shù)值越高,表明任務(wù)調(diào)度性能越好。假設(shè)隨機(jī)一個(gè)任務(wù)ti調(diào)度至某個(gè)云計(jì)算資源,調(diào)度執(zhí)行時(shí)間一定要處于截止時(shí)間之內(nèi),若超出該時(shí)間,則說(shuō)明調(diào)度任務(wù)失效[10]。把具備截止時(shí)間的任務(wù)調(diào)度問(wèn)題約束公式記作

(5)

其中,eij為執(zhí)行時(shí)間,di為時(shí)間閾值。

在式(3)基礎(chǔ)上,將適應(yīng)度值的計(jì)算過(guò)程變換為

(6)

其中,F代表適應(yīng)度函數(shù),mintpi代表目標(biāo)函數(shù),λ為調(diào)度系數(shù)。

粒子群算法為一種隨機(jī)優(yōu)化控制策略,算法中粒子m進(jìn)化時(shí)具備兩個(gè)矢量,依次為方位矢量xm=[xm,1,xm,2,…,xm,D]與速率矢量vm=[vm,1,vm,2,…,vm,D],D是空間維度。

云計(jì)算平臺(tái)環(huán)境下,把多數(shù)據(jù)庫(kù)并行調(diào)度問(wèn)題擬作一個(gè)離散優(yōu)化問(wèn)題,把離散粒子群算法代入并行調(diào)度中,數(shù)學(xué)的加減乘除計(jì)算不再適用,要對(duì)其重新定義。將粒子的方位描述成一個(gè)S維矢量,即x=[x1,x2,…,xj,…,xs],粒子的速率是粒子方位改變的幾率,也是一個(gè)S維矢量,記作v=[v1,v2,…,vj,…,vs]。方位和速率的加法運(yùn)算可以完成粒子位置的變動(dòng)。

每個(gè)粒子均擁有速率與方位兩個(gè)特征,利用更新粒子速率與方位獲得全新的粒子。與傳統(tǒng)粒子群算法的速率更新解析式相比,本文在速率更新中添加一個(gè)調(diào)整因子,用來(lái)操控粒子的搜尋方向。將粒子速率更新解析式表示成

vi=ωvi+c1r1(pbesti-xi)+c2r2(gbesti-xi)

(7)

式中,ω為慣性權(quán)重,c1、c2均為學(xué)習(xí)因子,分別代表粒子向局部最優(yōu)解pbest與全局最優(yōu)解gbest的靠近水準(zhǔn),r1、r2是處于[0,1]之間的任意數(shù)值,vi的取值范圍是vi∈[-vmax,vmax],這樣可以避免粒子超過(guò)搜尋范圍,提高并行調(diào)度的準(zhǔn)確性。

由于粒子的搜尋空間具有不連貫性,采用下面兩個(gè)公式完成粒子方位更新

xi=xi+vi

(8)

(9)

首先利用式(8)實(shí)施方位更新,但在獲得的編碼序列內(nèi)包含不合規(guī)編碼,這時(shí)要使用式(9)把不合規(guī)編碼變換成合規(guī)編碼,得到更新后的粒子具體方位。

粒子搜尋時(shí)為了控制并行調(diào)度算法的運(yùn)算能力,引入權(quán)重影響因子ω′,ω′較大時(shí)可以實(shí)現(xiàn)全局查找,相反ω′較小時(shí)容易陷入局部查找,所以調(diào)節(jié)ω′值能夠顯著提升算法的搜尋成效,優(yōu)化并行調(diào)度算法的整體性能。

ω′的取值有兩種模式:

一是挑選一個(gè)常數(shù),設(shè)置該常數(shù)是ω′,優(yōu)勢(shì)是方便計(jì)算,缺陷在于不能在所有迭代流程中發(fā)揮優(yōu)秀的搜尋能力;另一個(gè)模式是設(shè)定動(dòng)態(tài)ω′值,本文采用動(dòng)態(tài)ω′值模式,通過(guò)線性變化調(diào)節(jié)在減少計(jì)算量的同時(shí),保證調(diào)度全局最優(yōu)效果。

(10)

通過(guò)以上過(guò)程,就能讓算法在全部搜尋過(guò)程表現(xiàn)出優(yōu)秀的尋優(yōu)效果,獲得高質(zhì)量多數(shù)據(jù)庫(kù)并行調(diào)度性能,保證數(shù)據(jù)庫(kù)的資源調(diào)度及時(shí)性與準(zhǔn)確性。

4 仿真研究

4.1 仿真環(huán)境

為檢測(cè)本文方法在云計(jì)算平臺(tái)多數(shù)據(jù)庫(kù)并行調(diào)度的實(shí)際應(yīng)用效果,使用CloudSim平臺(tái)完成仿真任務(wù)。實(shí)驗(yàn)包含10個(gè)虛擬資源,7臺(tái)物理機(jī)。在實(shí)驗(yàn)環(huán)境下對(duì)本文方法、多信道聯(lián)合法和布谷鳥搜索法進(jìn)行仿真分析。實(shí)驗(yàn)參數(shù)設(shè)定為:種群規(guī)模是400,最高迭代次數(shù)是300,慣性權(quán)重最高值與最低值依次是0.94和0.34,學(xué)習(xí)因子c1=0.2、c2=0.4。

4.2 調(diào)度長(zhǎng)度與迭代次數(shù)分析

在不同迭代次數(shù)下反復(fù)執(zhí)行30次并行調(diào)度任務(wù),記錄不同方法下調(diào)度最優(yōu)解、最差解以及迭代均值,結(jié)果如表1所示。

表1 三種方法并行調(diào)度最優(yōu)解結(jié)果對(duì)比

最優(yōu)解表示算法獲得的最佳調(diào)度次數(shù),數(shù)值越小,表示云計(jì)算平臺(tái)需要執(zhí)行的次數(shù)越少,更方便操作和減少調(diào)度誤差。從表1中能夠看出,所提算法調(diào)度最優(yōu)解、最差解都遠(yuǎn)小于文獻(xiàn)方法,但是迭代次數(shù)相對(duì)較大。為此,分析算法獲得最優(yōu)調(diào)度解的迭代過(guò)程,如圖3所示。

圖3 三種算法數(shù)據(jù)庫(kù)任務(wù)調(diào)度長(zhǎng)度對(duì)比

圖3中可知,多信道聯(lián)合法在計(jì)算中丟失了一些潛在的優(yōu)秀粒子,很快陷入局部最優(yōu)并呈現(xiàn)出收斂狀態(tài);布谷鳥搜索法在融合消息傳遞編程模型與共享存儲(chǔ)編程模型時(shí),算法的計(jì)算量過(guò)高,也很快地出現(xiàn)了局部最優(yōu)情況。本文方法在迭代次數(shù)低于40時(shí),粒子均處在搜索狀況,多次跳出局部最優(yōu),證明方法在迭代初期就擁有優(yōu)質(zhì)的全局搜索能力;之后粒子逐步開始局部搜尋,直至找到全局最優(yōu)解。綜合表1與圖3的數(shù)據(jù),充分證明了本文方法在收斂性、全局搜索能力與局部搜索能力都優(yōu)于兩個(gè)對(duì)比方法。

4.3 適應(yīng)度值對(duì)比分析

圖4是三種方法基于不同任務(wù)個(gè)數(shù)的適應(yīng)度值對(duì)比,適應(yīng)度函數(shù)值越高,表明任務(wù)調(diào)度的適用性能越好。

圖4 三種方法不同任務(wù)數(shù)量下的適應(yīng)度值對(duì)比

由圖4看出,任務(wù)個(gè)數(shù)較少狀態(tài)下,三種方法的適應(yīng)度差距并不顯著,但伴隨任務(wù)數(shù)量的持續(xù)增多,本文方法的適應(yīng)度函數(shù)值顯著高于文獻(xiàn)方法,且任務(wù)數(shù)量越多,此趨勢(shì)越明顯。這是因?yàn)樵摲椒ㄍㄟ^(guò)提取并行調(diào)度時(shí)間序列相關(guān)的混沌特征,優(yōu)化了調(diào)度整體速率,并采用Map與Reduce函數(shù),創(chuàng)建多數(shù)據(jù)庫(kù)并行調(diào)度模型,有效提高了多數(shù)據(jù)庫(kù)并行調(diào)度性能。

4.4 隨任務(wù)量增加并行調(diào)度時(shí)間對(duì)比

依次設(shè)定多數(shù)據(jù)庫(kù)并行調(diào)度任務(wù)個(gè)數(shù)是30、60、90、120、150、180、210、240,各任務(wù)數(shù)量下每種算法均實(shí)驗(yàn)5次,取結(jié)果平均值,獲得三種方法下任務(wù)數(shù)量與調(diào)度時(shí)間之間的關(guān)聯(lián),如圖5所示。

圖5 并行調(diào)度時(shí)間對(duì)比示意圖

可以看到,本文方法相對(duì)文獻(xiàn)方法,在調(diào)度時(shí)間方面具有明顯優(yōu)勢(shì),且隨著任務(wù)個(gè)數(shù)的不斷遞增,本文方法也能夠很好地完成高效率并行調(diào)度目標(biāo),能夠滿足云計(jì)算平臺(tái)需要處理大量事務(wù)的實(shí)際需要。

4.5 并行調(diào)度下物理機(jī)負(fù)載均衡分析

下面對(duì)比三種并行調(diào)度算法運(yùn)行時(shí),7臺(tái)物理機(jī)的帶寬利用率,明確執(zhí)行調(diào)度任務(wù)時(shí)對(duì)云計(jì)算平臺(tái)性能的影響,結(jié)果如圖6所示。

圖6 三種算法下云計(jì)算平臺(tái)帶寬利用率對(duì)比

從圖6中可知,本文方法沒(méi)有出現(xiàn)由于過(guò)度使用單一物理機(jī)、不使用空間物理機(jī)導(dǎo)致的負(fù)載不均情況,全部物理機(jī)都保持在70-80%的利用率,不會(huì)影響其它功能板塊的正常運(yùn)行,最大限度地實(shí)現(xiàn)云計(jì)算平臺(tái)的負(fù)載均衡,提升其網(wǎng)絡(luò)數(shù)據(jù)處理能力。

5 結(jié)論

面向傳統(tǒng)多數(shù)據(jù)庫(kù)并行調(diào)度的不足,以云計(jì)算平臺(tái)為現(xiàn)實(shí)背景,提出一種多數(shù)據(jù)庫(kù)并行調(diào)度算法。該算法充分研究云計(jì)算平臺(tái)特征,將并行調(diào)度效率作為突破口,有效改進(jìn)以往調(diào)度方法效率低下的問(wèn)題,使之適應(yīng)云計(jì)算平臺(tái)的虛擬化與商業(yè)化形態(tài),提升云平臺(tái)數(shù)據(jù)庫(kù)工作效率。