基于ALAD算法的數(shù)據(jù)庫MAR均衡分配仿真

劉 平，宿敬肖*，張麗娟，李明亮

(1.河北工程技術(shù)學(xué)院，河北 石家莊 050000;2.河北地質(zhì)大學(xué)，河北 石家莊 050030)

1 引言

在信息化影響下，用戶的訪問需求逐漸增加，但由于大部分?jǐn)?shù)據(jù)庫中缺乏平衡功能，導(dǎo)致出現(xiàn)高負(fù)載問題，嚴(yán)重影響整體性能與用戶滿意度。而均衡分配策略能夠在數(shù)據(jù)庫高負(fù)載情況下，將任務(wù)從負(fù)載繁重的服務(wù)器轉(zhuǎn)移到?jīng)]有負(fù)載壓力的服務(wù)器中，有效控制系統(tǒng)負(fù)載情況，因此成為相關(guān)學(xué)者關(guān)注焦點(diǎn)，并研究出一些較好的方法。

文獻(xiàn)[1]提出基于主題相關(guān)特征挖掘的數(shù)據(jù)庫資源均衡分配方法。利用決策隨機(jī)變量建立多屬性資源關(guān)聯(lián)模型；根據(jù)皮爾遜有關(guān)系數(shù)完成資源間主題相似性度量，獲取多樣化的多屬性資源特性；通過二次聚類得到資源特性訓(xùn)練數(shù)據(jù)的原始聚類情況，定義神經(jīng)網(wǎng)絡(luò)隱含層分配節(jié)點(diǎn)，改善資源分配速度。文獻(xiàn)[2]利用數(shù)據(jù)庫信道屬性權(quán)重法實(shí)現(xiàn)資源均衡分配。構(gòu)建數(shù)據(jù)庫干擾模型，根據(jù)流量負(fù)載與干擾鏈路設(shè)計(jì)權(quán)重，將屬性權(quán)重作為判斷信道優(yōu)先級的依據(jù)，權(quán)重較高的鏈路具有優(yōu)先選擇權(quán)。在此過程中，如果獲得的權(quán)重是靜態(tài)的，為改善實(shí)用性與動態(tài)性，引入動態(tài)迭代學(xué)習(xí)算法，在原有算法上通過梯度下降完成權(quán)重調(diào)整，達(dá)到按權(quán)重分配目的。上述兩種方法雖然提高了資源分配的均衡度，但是當(dāng)服務(wù)器處于高負(fù)載情況時響應(yīng)延時較長，均衡誤差率高，無法實(shí)時反映系統(tǒng)真實(shí)運(yùn)行情況。

為解決上述傳統(tǒng)方法存在的問題，本文利用ALAD(Application Layer Adaptive Dynamic)算法對數(shù)據(jù)庫多屬性資源進(jìn)行均衡分配，收集服務(wù)器負(fù)載數(shù)據(jù)，對這些數(shù)據(jù)進(jìn)行計(jì)算得出每臺服務(wù)器負(fù)載權(quán)重，再結(jié)合權(quán)重信息實(shí)現(xiàn)資源均衡分配。仿真結(jié)果證明，該方法可提高數(shù)據(jù)庫資源利用率，有效改善響應(yīng)延時問題。

2 基于ALAD算法的服務(wù)器負(fù)載綜合權(quán)重計(jì)算

ALAD為應(yīng)用層自適應(yīng)動態(tài)負(fù)載均衡算法，該算法將不同服務(wù)器的響應(yīng)延時當(dāng)作參考，以請求處理成功率與運(yùn)行時間為輔助。在進(jìn)行分配過程中，使用ALAD方法計(jì)算服務(wù)器總體響應(yīng)延遲情況，以此信息作為數(shù)據(jù)庫高負(fù)載[3]的首要原因。并獲取服務(wù)器處理錯誤率與最大連續(xù)運(yùn)行時間，從而得出數(shù)據(jù)庫中不同服務(wù)器權(quán)重。詳細(xì)過程如下所述：

步驟一：計(jì)算響應(yīng)延時原因LatFact。

設(shè)定不同服務(wù)器處理請求的傳輸時間表示為rsent，處理時長為rproc，接收時間是rreci，通過式(1)計(jì)算所有服務(wù)器處理請求的整體延時[4]情況

lat=rsent+rproc+rreci

(1)

lat表示為服務(wù)器自身負(fù)載情況與各服務(wù)器之間的關(guān)系。如果lat值較低，則說明服務(wù)器處理能力強(qiáng)，結(jié)合lat可得到數(shù)據(jù)庫中所有影響服務(wù)器延時的因素LatEactK，通過下述公式表示

(2)

步驟二：計(jì)算服務(wù)器請求處理的成功率SuccFact。

在負(fù)載均衡處理器上記錄由elct表示的所有服務(wù)器處理請求的次數(shù)，假設(shè)fault為處理出錯的次數(shù)，結(jié)合采集數(shù)據(jù)，求出SuccFact

(3)

步驟三：計(jì)算影響連續(xù)服務(wù)時間的因素TimeFact。

采集每個服務(wù)器連續(xù)運(yùn)行時間t，根據(jù)采集的數(shù)據(jù)計(jì)算全部服務(wù)器中持續(xù)運(yùn)行時間的最高值tmax，計(jì)算公式如下

tmax=max(t1，t2，t3，…，tn)

(4)

結(jié)合上述公式獲取TimeFact表達(dá)式

(5)

(6)

式中，tdiff表示服務(wù)器受到的運(yùn)行壓力，此種壓力在服務(wù)器剛開始運(yùn)行時較低，隨著運(yùn)行時間推移壓力明顯增加。

步驟四：計(jì)算每個服務(wù)器負(fù)載綜合權(quán)重LoadFact。

利用式(6)獲取的三個因素值，對服務(wù)器負(fù)載綜合權(quán)重進(jìn)行計(jì)算，公式如下

LoadFact=?LatEactK×SuccFact×Fact」

(7)

式中，LoadFact的值應(yīng)和當(dāng)前階段服務(wù)器與網(wǎng)絡(luò)負(fù)載性能相對應(yīng)。

利用ALAD算法經(jīng)過上述過程計(jì)算出數(shù)據(jù)庫中各服務(wù)器的負(fù)載綜合權(quán)重，為實(shí)現(xiàn)資源均衡分配奠定基礎(chǔ)。

3 數(shù)據(jù)庫多屬性資源均衡分配

3.1 特性提取

本文通過構(gòu)建TG-LDA模型對多屬性資源進(jìn)行特征提取，利用決策隨機(jī)變量挖掘多屬性資源間共有與獨(dú)有主題，同時結(jié)合皮爾遜相關(guān)系數(shù)獲取資源主題間相似性度量，以此提取資源的不同特性。

設(shè)定θ代表對M個資源文本形成的主題分布，針對資源文本生成N′個特征詞，利用η描述某個參數(shù)，此參數(shù)可以調(diào)節(jié)決策隨機(jī)變量γ的取值。將決策變量引入到TG-LDA模型中，使不同種類的主題與資源生成過程相結(jié)合，則上述過程變換為概率模型[5]形式表示為

(8)

通過多次計(jì)算得到最終的資源文本主題分布θd與特征詞分布φz的后驗(yàn)預(yù)測值

(9)

(10)

式中，nd，ξ表示資源文本d分配到主題ξ的詞語數(shù)量，nd，g代表文本d全部被分配到主題g的詞語數(shù)量。α、β、T與V均屬于參數(shù)。

將JSD距離當(dāng)作多屬性資源共有和獨(dú)有主題間相似度信息，通過下述公式獲取兩種資源離散概率分布P和Q的JSD距離

(11)

(12)

(13)

(14)

(15)

3.2 多屬性資源均衡分配的實(shí)現(xiàn)

傳統(tǒng)資源分配方式并沒有分析數(shù)據(jù)庫節(jié)點(diǎn)計(jì)算能力的區(qū)別，在對不同特征資源進(jìn)行分配時，容易導(dǎo)致數(shù)據(jù)傾斜[7]，降低數(shù)據(jù)庫整體性能。本文綜合考慮上述問題，依據(jù)上述特征數(shù)據(jù)，利用改進(jìn)的遺傳算法實(shí)現(xiàn)多屬性資源均衡分配。

3.2.1 數(shù)據(jù)分片

在資源分配過程中，通常是針對數(shù)據(jù)片進(jìn)行，結(jié)合上述資源特征確定數(shù)據(jù)分片[8]情況。每片中的信息既要符合完全性又要確保一致性。另外在分片時還需分析分片大小，如果分片太大，則不能很好體現(xiàn)數(shù)據(jù)庫集群性能；反之，分片太小，會導(dǎo)致單個節(jié)點(diǎn)啟動與終止時間過大。

假設(shè)n′個處理器同時對群表進(jìn)行掃描所需要的時間計(jì)算公式表示為

(16)

利用下述公式求導(dǎo)，確保T′具有最小值

(17)

因此n′成為了數(shù)據(jù)分片的最佳并行度，如果某個關(guān)系被劃分成多個處理器，這時閾值B(R)必須符合下述條件

(18)

只有滿足上述要求，才能實(shí)現(xiàn)數(shù)據(jù)最佳分片，提高資源利用效率。

3.2.2 選取分配屬性

在資源分配過程中，需要利用多種屬性進(jìn)行選取。分配屬性的選取影響著數(shù)據(jù)庫查詢成本，本文按照以下過程進(jìn)行分配屬性選擇：

1)獲取文本的相關(guān)連接屬性；

2)查找文本中g(shù)roupby屬性或orderby屬性；

3)詳細(xì)的劃分屬性選擇法表示為：輸入關(guān)系集合R1，R2，…，R7，連接圖G=(V，E)，輸出屬性集合；

4)計(jì)算連接圖G=(V，E)的連接屬性收益，獲取收益值最高的屬性A′與其關(guān)系集合；

5)不斷更新收益值，經(jīng)過上述過程即可確定最佳劃分屬性。

3.2.3 資源均衡分配

根據(jù)代價最低原則，使用改進(jìn)的遺傳算法對所有待分配的數(shù)據(jù)片進(jìn)行分配，以此獲得數(shù)據(jù)庫多屬性資源均衡分配策略。具體步驟如下：

步驟一：資源編碼[9]。將資源分配方法當(dāng)作遺傳種群的某個個體，利用二進(jìn)制編碼方式對其編碼，保證編碼長度和數(shù)據(jù)庫中站點(diǎn)個數(shù)相同。假設(shè)1表示待分配信息片段被分配的站點(diǎn)位置，0代表某編碼個體與一個信息片段分配方法相對應(yīng)。

(19)

(20)

由此可知，待分配信息片段的更新與檢索訪問量的比值就是信息片段的更新檢索比[10]。

步驟三：種群初始化。種群規(guī)模過大或過小均無法獲得最優(yōu)解，所以結(jié)合更新檢索比完成種群初始化操作。

如果分配的信息片段符合U/Q<1，則需設(shè)置大量副本，若U/Q>1，應(yīng)將副本數(shù)量控制在最小范圍內(nèi)。

步驟四：個體評判。利用有關(guān)公式獲取種群個體適應(yīng)度，在分配過程中，該值體現(xiàn)分配方法的性能，和總代價之間具有反比關(guān)系。代價越大適應(yīng)度值越小，此個體被留下的可能性就越低；反之，此個體有可能遺傳到下一代。

步驟五：選取優(yōu)良基因。該過程遵循“優(yōu)勝劣汰”準(zhǔn)則，將具有優(yōu)良基因的個體遺傳到下一代。

選取優(yōu)良基因后，獲得個體適應(yīng)度和種群適應(yīng)度二者的比值，計(jì)算此個體被遺傳給下一代的幾率，則個體被挑選的概率值表示為

(21)

對比當(dāng)前個體和下一代個體的最優(yōu)適應(yīng)度值，如果當(dāng)前個體具有優(yōu)勢，則利用該個體替換下一代個體。

步驟六：交叉計(jì)算，該過程表示基因重組。不同個體之間結(jié)合交叉幾率實(shí)現(xiàn)隨機(jī)匹配，概率值越高表示此個體更容易引進(jìn)新的基因；反之，容易導(dǎo)致搜索停滯。本文利用自適應(yīng)交叉算子來獲得適當(dāng)?shù)慕徊娓怕剩?/p>

(22)

式中，F(xiàn)max與Favg分別表示種群內(nèi)個體最高與最低適應(yīng)度值，F(xiàn)e則是兩個交叉?zhèn)€體中較大的適應(yīng)度值，本文取Pe1=0.8、Pe2=0.4。

步驟七：變異操作，該操作能確保個體遺傳具有多樣性。遺傳過程根據(jù)自適應(yīng)變異算子完成變異，維持遺傳搜索和多樣性之間的平衡。變異操作可利用如下公式表示

(23)

步驟八：通過上述交叉變異等操作形成下一代新種群，根據(jù)計(jì)算得出的各服務(wù)器負(fù)載情況，設(shè)置最大迭代次數(shù)，如果低于設(shè)定值，則需返回步驟四重新進(jìn)行；反之輸出結(jié)果，在最新種群內(nèi)，最優(yōu)個體就是資源最優(yōu)分配方案。重復(fù)以上過程，直到全部待分配資源片段均找到最佳分配方案為止。利用該方法即可實(shí)現(xiàn)數(shù)據(jù)庫多屬性資源均衡分配。

4 仿真數(shù)據(jù)分析與研究

為驗(yàn)證提出的基于ALAD算法的數(shù)據(jù)庫多屬性資源負(fù)載均衡分配方法的可行性，需設(shè)置仿真。在Cloud Sim2.0環(huán)境下搭建仿真平臺。假設(shè)所有資源節(jié)點(diǎn)均是隨機(jī)產(chǎn)生的，節(jié)點(diǎn)數(shù)量在20～100個之間，虛擬節(jié)點(diǎn)數(shù)量在5～30個之間，虛擬節(jié)點(diǎn)同樣是隨機(jī)產(chǎn)生的。

為更好體現(xiàn)本文方法的優(yōu)勢，彰顯仿真的公平性與全面性，將實(shí)驗(yàn)分為兩個不同階段，并分別利用文獻(xiàn)[1]方法、文獻(xiàn)[2]方法與本文方法進(jìn)行對比。首先對三種方法資源利用率與分配均衡程度進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果分別如圖1和圖2所示。

圖1 不同方法下數(shù)據(jù)庫資源利用率對比

圖2 不同方法下數(shù)據(jù)庫資源分配均衡度對比

由圖1和圖2可知，隨著用戶數(shù)量不斷增加，所提方法的資源利用率持續(xù)提高，分配均衡度較為穩(wěn)定，表現(xiàn)出良好的資源分配能力，這是因?yàn)楦倪M(jìn)的遺傳算法可以獲得最佳資源分配策略；文獻(xiàn)[1]方法雖然資源利用率也有所提高，但與本文方法相比提高速度較慢；而文獻(xiàn)[2]方法由于用戶增加，負(fù)載過大，均衡度明顯下降，因此無法保證資源被有效利用。

此外，在仿真中通過計(jì)算機(jī)并發(fā)大量請求，使數(shù)據(jù)庫處于高負(fù)載狀態(tài)，對比三種方法的平均響應(yīng)時間，對比結(jié)果如圖3所示。

圖3 不同方法并發(fā)響應(yīng)時間對比圖

圖3所得實(shí)驗(yàn)結(jié)果說明，當(dāng)數(shù)據(jù)庫在較低的并發(fā)連接狀態(tài)下，負(fù)載很低，所提方法略高于文獻(xiàn)[1]與文獻(xiàn)[2]方法，隨著并發(fā)連接次數(shù)不斷增多，數(shù)據(jù)庫逐漸處在高負(fù)載狀態(tài)，本文方法響應(yīng)時間明顯低于其它兩種方法。主要因?yàn)楸疚姆椒▽Σ煌?wù)器的負(fù)載權(quán)重進(jìn)行計(jì)算，可以準(zhǔn)確體現(xiàn)出系統(tǒng)運(yùn)行狀況，減少均衡誤差，提高響應(yīng)速度。

5 結(jié)論

為提高數(shù)據(jù)庫資源利用率，利用ALAD算法計(jì)算不同服務(wù)器負(fù)載綜合權(quán)重，再采用改進(jìn)的遺傳算法確定最佳分配策略，實(shí)現(xiàn)數(shù)據(jù)庫多屬性資源均衡分配，仿真結(jié)果證明了該方法的優(yōu)越性。但是在對數(shù)據(jù)庫的認(rèn)知方面，本文并沒有研究數(shù)據(jù)庫真實(shí)架構(gòu)。所以在下一步的研究中重點(diǎn)分析數(shù)據(jù)庫結(jié)構(gòu)，結(jié)合數(shù)據(jù)庫特征進(jìn)一步完善分配方法，以此滿足更多用戶需求。