基于ALAD算法的數據庫MAR均衡分配仿真

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

(1.河北工程技術學院，河北 石家莊 050000;2.河北地質大學，河北 石家莊 050030)

1 引言

在信息化影響下，用戶的訪問需求逐漸增加，但由于大部分數據庫中缺乏平衡功能，導致出現高負載問題，嚴重影響整體性能與用戶滿意度。而均衡分配策略能夠在數據庫高負載情況下，將任務從負載繁重的服務器轉移到沒有負載壓力的服務器中，有效控制系統負載情況，因此成為相關學者關注焦點，并研究出一些較好的方法。

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

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

2 基于ALAD算法的服務器負載綜合權重計算

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

步驟一：計算響應延時原因LatFact。

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

lat=rsent+rproc+rreci

(1)

lat表示為服務器自身負載情況與各服務器之間的關系。如果lat值較低，則說明服務器處理能力強，結合lat可得到數據庫中所有影響服務器延時的因素LatEactK，通過下述公式表示

(2)

步驟二：計算服務器請求處理的成功率SuccFact。

在負載均衡處理器上記錄由elct表示的所有服務器處理請求的次數，假設fault為處理出錯的次數，結合采集數據，求出SuccFact

(3)

步驟三：計算影響連續服務時間的因素TimeFact。

采集每個服務器連續運行時間t，根據采集的數據計算全部服務器中持續運行時間的最高值tmax，計算公式如下

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

(4)

結合上述公式獲取TimeFact表達式

(5)

(6)

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

步驟四：計算每個服務器負載綜合權重LoadFact。

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

LoadFact=?LatEactK×SuccFact×Fact」

(7)

式中，LoadFact的值應和當前階段服務器與網絡負載性能相對應。

利用ALAD算法經過上述過程計算出數據庫中各服務器的負載綜合權重，為實現資源均衡分配奠定基礎。

3 數據庫多屬性資源均衡分配

3.1 特性提取

本文通過構建TG-LDA模型對多屬性資源進行特征提取，利用決策隨機變量挖掘多屬性資源間共有與獨有主題，同時結合皮爾遜相關系數獲取資源主題間相似性度量，以此提取資源的不同特性。

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

(8)

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

(9)

(10)

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

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

(11)

(12)

(13)

(14)

(15)

3.2 多屬性資源均衡分配的實現

傳統資源分配方式并沒有分析數據庫節點計算能力的區別，在對不同特征資源進行分配時，容易導致數據傾斜[7]，降低數據庫整體性能。本文綜合考慮上述問題，依據上述特征數據，利用改進的遺傳算法實現多屬性資源均衡分配。

3.2.1 數據分片

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

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

(16)

利用下述公式求導，確保T′具有最小值

(17)

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

(18)

只有滿足上述要求，才能實現數據最佳分片，提高資源利用效率。

3.2.2 選取分配屬性

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

1)獲取文本的相關連接屬性；

2)查找文本中groupby屬性或orderby屬性；

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

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

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

3.2.3 資源均衡分配

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

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

(19)

(20)

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

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

如果分配的信息片段符合U/Q<1，則需設置大量副本，若U/Q>1，應將副本數量控制在最小范圍內。

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

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

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

(21)

對比當前個體和下一代個體的最優適應度值，如果當前個體具有優勢，則利用該個體替換下一代個體。

步驟六：交叉計算，該過程表示基因重組。不同個體之間結合交叉幾率實現隨機匹配，概率值越高表示此個體更容易引進新的基因；反之，容易導致搜索停滯。本文利用自適應交叉算子來獲得適當的交叉概率：

(22)

式中，Fmax與Favg分別表示種群內個體最高與最低適應度值，Fe則是兩個交叉個體中較大的適應度值，本文取Pe1=0.8、Pe2=0.4。

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

(23)

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

4 仿真數據分析與研究

為驗證提出的基于ALAD算法的數據庫多屬性資源負載均衡分配方法的可行性，需設置仿真。在Cloud Sim2.0環境下搭建仿真平臺。假設所有資源節點均是隨機產生的，節點數量在20～100個之間，虛擬節點數量在5～30個之間，虛擬節點同樣是隨機產生的。

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

圖1 不同方法下數據庫資源利用率對比

圖2 不同方法下數據庫資源分配均衡度對比

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

此外，在仿真中通過計算機并發大量請求，使數據庫處于高負載狀態，對比三種方法的平均響應時間，對比結果如圖3所示。

圖3 不同方法并發響應時間對比圖

圖3所得實驗結果說明，當數據庫在較低的并發連接狀態下，負載很低，所提方法略高于文獻[1]與文獻[2]方法，隨著并發連接次數不斷增多，數據庫逐漸處在高負載狀態，本文方法響應時間明顯低于其它兩種方法。主要因為本文方法對不同服務器的負載權重進行計算，可以準確體現出系統運行狀況，減少均衡誤差，提高響應速度。

5 結論

為提高數據庫資源利用率，利用ALAD算法計算不同服務器負載綜合權重，再采用改進的遺傳算法確定最佳分配策略，實現數據庫多屬性資源均衡分配，仿真結果證明了該方法的優越性。但是在對數據庫的認知方面，本文并沒有研究數據庫真實架構。所以在下一步的研究中重點分析數據庫結構，結合數據庫特征進一步完善分配方法，以此滿足更多用戶需求。