楊 毅,熊 鷹

(華中科技大學網絡與計算中心,湖北 武漢 430074)

1 引言

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

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

本文吸取文獻方法的優(yōu)勢,針對其不足提出一種基于云計算平臺的多數據庫并行調度算法,組建高可信度云計算平臺,利用MapReduce編程得到多數據庫并行調度模型,運用離散粒子群算法完成高效率并行調度目標。仿真結果證明,經所提算法調度后,實現了網絡負載均衡,可應用于多種類數據庫,適用范圍廣。

2 云計算平臺構建

云計算平臺涵蓋應用層、平臺層與基礎設施層三個層次,以基礎設施層為例,引入可信根與信任傳遞思維,面向虛擬層實際特征,給用戶提供一個高度安全的云計算平臺[5]。云計算平臺構建技術中最關鍵的就是虛擬化技術,虛擬化是一種從底層硬件或軟件抽象出應用程序、用戶操作系統。虛擬化的核心是服務器虛擬化,主要劃分為底層硬件下的虛擬化、宿主操作系統下的虛擬化兩種模式。

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

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

(1)

其中,Ii表示云平臺物理主機操作系統引導時第i個階段的完整性,如果第i個階段是完整的,那么Ii=1,反之Ii=0。Vi(Si+1)是第i個階段的度量控制組件,對引導序列內第i+1個階段實施度量的參數。

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

圖1 云計算平臺架構示意圖

3 基于離散粒子群的多數據庫并行調度算法

3.1 多數據庫并行調度模型

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

(2)

融合并行策略與混沌因子,計算調度時間順序適應值

(3)

最終將調度任務的效率描述成

φ=|θ-j|

(4)

其中,φ表示調度任務效率,θ表示遞增系數。

當前多數云計算平臺將MapReduce編程模型應用在海量數據庫的并行運算中。MapReduce操作融合Map與Reduce函數,將其傳輸至調度系統,分配到可用計算資源。綜合以上運算過程,將多數據庫并行調度模型表示成圖2。

圖2 并行調度模型

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

3.2 算法實現

并行調度模型構建完畢后,融合基于離散粒子群的并行調度算法,實現在保證負載均衡前提下的多數據庫高質量并行調度任務。利用離散粒子群法計算調度問題,組建有效的粒子編碼結構,使用間接編碼模式完成各子任務的資源編碼,編碼長度是當前子任務的數量,一個編碼對應一個并行調度方案[9]。

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

(5)

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

在式(3)基礎上,將適應度值的計算過程變換為

(6)

其中,F代表適應度函數,mintpi代表目標函數,λ為調度系數。

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

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

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

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

(7)

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

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

xi=xi+vi

(8)

(9)

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

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

ω′的取值有兩種模式:

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

(10)

通過以上過程,就能讓算法在全部搜尋過程表現出優(yōu)秀的尋優(yōu)效果,獲得高質量多數據庫并行調度性能,保證數據庫的資源調度及時性與準確性。

4 仿真研究

4.1 仿真環(huán)境

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

4.2 調度長度與迭代次數分析

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

表1 三種方法并行調度最優(yōu)解結果對比

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

圖3 三種算法數據庫任務調度長度對比

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

4.3 適應度值對比分析

圖4是三種方法基于不同任務個數的適應度值對比,適應度函數值越高,表明任務調度的適用性能越好。

圖4 三種方法不同任務數量下的適應度值對比

由圖4看出,任務個數較少狀態(tài)下,三種方法的適應度差距并不顯著,但伴隨任務數量的持續(xù)增多,本文方法的適應度函數值顯著高于文獻方法,且任務數量越多,此趨勢越明顯。這是因為該方法通過提取并行調度時間序列相關的混沌特征,優(yōu)化了調度整體速率,并采用Map與Reduce函數,創(chuàng)建多數據庫并行調度模型,有效提高了多數據庫并行調度性能。

4.4 隨任務量增加并行調度時間對比

依次設定多數據庫并行調度任務個數是30、60、90、120、150、180、210、240,各任務數量下每種算法均實驗5次,取結果平均值,獲得三種方法下任務數量與調度時間之間的關聯,如圖5所示。

圖5 并行調度時間對比示意圖

可以看到,本文方法相對文獻方法,在調度時間方面具有明顯優(yōu)勢,且隨著任務個數的不斷遞增,本文方法也能夠很好地完成高效率并行調度目標,能夠滿足云計算平臺需要處理大量事務的實際需要。

4.5 并行調度下物理機負載均衡分析

下面對比三種并行調度算法運行時,7臺物理機的帶寬利用率,明確執(zhí)行調度任務時對云計算平臺性能的影響,結果如圖6所示。

圖6 三種算法下云計算平臺帶寬利用率對比

從圖6中可知,本文方法沒有出現由于過度使用單一物理機、不使用空間物理機導致的負載不均情況,全部物理機都保持在70-80%的利用率,不會影響其它功能板塊的正常運行,最大限度地實現云計算平臺的負載均衡,提升其網絡數據處理能力。

5 結論

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