陳一航,李卓暉,李逸謙,楊子江,裴 歡

(中國能源建設集團廣東省電力設計研究院有限公司,廣東 廣州 510663)

0 引言

跨地理分布式數(shù)據(jù)中心可以通過分布式計算和并行處理的方式,將大規(guī)模數(shù)據(jù)分析任務劃分為多個子任務,并在不同數(shù)據(jù)中心中并行處理。這樣可以加快數(shù)據(jù)分析的速度,提高效率。大規(guī)模數(shù)據(jù)分析需要大量的計算和存儲資源,跨地理分布式數(shù)據(jù)中心可以集中利用全球的計算和存儲資源,提高資源利用效率。同時,跨地理分布式數(shù)據(jù)中心之間的數(shù)據(jù)交換,可以將分布在不同地域的數(shù)據(jù)整合起來進行分析,提高數(shù)據(jù)的全局視野[1-3]?？绲乩矸植际綌?shù)據(jù)中心的大規(guī)模數(shù)據(jù)分析研究需要在網(wǎng)絡架構和優(yōu)化方面進行支持。

1 分布式約束及數(shù)據(jù)中心分析

1.1 分布式約束優(yōu)化問題

代理ai∈A的賦值是來自其域的值的每個外部變量的賦值。即,一個元組(〈Ei,Vi〉,ti),其中Vi∈×dj,Vi[xj]∈dj,并且ti是標記值。比較兩個項目時,最新的項目是標記ti最大的值。

當前部分賦值(Current Partial Assignment,CPA)是外部變量[(〈E1,V1〉,t1),…,(〈Ek,Vk〉,tk)]的賦值的有序集合。如果兩個CPA中的每個公共變量的值相等,則這兩個CPA是兼容的。Ag-CPA(Agent-CPA)是指CPA中具有指定變量的所有代理的集合。

與CPA相關聯(lián)的時間戳是計數(shù)器[t1,…,tk]的有序列表,其中?j∈1,…,k,tj是代理aj的標簽。當比較兩個CPA時,最強的一個是與數(shù)據(jù)庫內(nèi)較大的時間戳相關聯(lián)的CPA。即,如果存在,則它們各自的第一個計數(shù)器上具有最大值的CPA,否則取賦值最長的一個。

在搜索過程中,代理可以推斷出不一致的分配集,稱為無效集(no-good)。無效集或沖突集是指任何解決方案中都不包含的變量賦值集。no-good是一個形式為[(xi=vi)^(xj=vj)^…^(xk=vk)]的子句,意味著此類分配不能擴展到解決方案。如果每個公共變量都被賦予相同的值,則 no-good 與CPA兼容。

1.2 地理分布的數(shù)據(jù)中心問題

本文考慮的地理分布數(shù)據(jù)中心(GDDC)問題可以定義如下:得到了一組數(shù)據(jù)中心位置L,以及一組必須在操作范圍T內(nèi)的每個時間段分配給物理服務器的虛擬機(Virtual Machine,VM)。每個位置在每個時間段都有自己的單位能源價格(示例實時價格如圖1所示)。在一個位置執(zhí)行VM的成本對于該位置的每個時間段或同一時間段中的每個區(qū)域可能不同。該成本不僅構成當?shù)毓彩聵I(yè)的電價,還受到室外溫度、設備質量等外部因素的影響。后者可以按照電力使用效率(Power Utilization Efficiency,PUE)來估計,PUE是直流電的總功耗與IT設備的功耗之比。

圖1 在同一24 h內(nèi)10個不同地點的實時價格樣本

2 分布式約束優(yōu)化的地理分布的數(shù)據(jù)中心

分配。在一段時間內(nèi)運行的給定類型的VM的數(shù)量等于在前一段時間運行的數(shù)量加上收入減去支出。

(1)

容量。DCal運行虛擬機所消耗總能量是有限的:

(2)

遷移。每個DC每個時間段的傳入/傳出VM數(shù)量受給定閾值的限制:

(3)

本文進一步添加了以下移入/移出變量對的冗余約束,強制每個類型在每個時間段的每個位置中至少有一個必須為0:

(4)

運行成本。在整個范圍內(nèi)運行虛擬機的總能源成本為:

(5)

遷移成本。在所有時間段內(nèi)以Rl遷移虛擬機的總能源成本為:

(6)

內(nèi)部成本。在所有時間段內(nèi),在Rl中運行和遷移VM的總能源成本為:

cl=rl+ml

(7)

代理間約束是所有擁有它所涉及的變量的代理都知道的。分配在v為Rl的每個時間段內(nèi),v類型的VM必須全部分配給DC:

(8)

全局目標是最大限度地減少在所有DC中運行VM的總能源成本與在整個范圍內(nèi)遷移VM的總能量成本之和:

(9)

3 實例分析

3.1 參數(shù)設置

本文為一個場景生成了實例,該場景在三大地區(qū)有10個數(shù)據(jù)中心,每個數(shù)據(jù)中心的容量定義為40 MW。在5天的時間里,每個地點每小時都會收集實時價格數(shù)據(jù)。每個DC的動態(tài)PUE值是作為整個樣品的溫度的函數(shù)生成的。選擇了5種VM,其相關功耗值分別為20 W、40 W、60 W、80 W和100 W。對于每個DC,VM創(chuàng)建請求都是隨機生成的,直到它們的消耗達到DC容量的40%的負載百分比。每個VM創(chuàng)建意愿都被進一步隨機分配一個“主權”,即DC所屬的整個集合。

3.2 搜索策略

提出了兩個代理模型,稱為o1和o2。在兩個模型中,代理ai使用相同的度量αi。對于每個ai,αi是代理ai表示的DC在所有時隙內(nèi)最昂貴和最便宜的價格之間的差。對于o2,使用αi上的遞增順序對試劑進行排序。對于o1,第一個代理被選擇為具有中值測度αi的代理,然后是與測度αi距離最小的代理,例如aj,即|αj-αi|。例如:設a1=22,a2=10,a3=44,a4=55,a5=30,因此o1=[a5,a1,a3,a2,a4]和o2=[a2,a1,a5,a3,a4]。

3.3 結果分析

通信負載和解決方案質量來評估算法的性能。通信負載是通過算法執(zhí)行時代理之間交換的消息總數(shù)來衡量的。結果如表1所示。解決方案質量通過兩個指標進行評估:(1)平均貨幣成本如表2所示。(2)基線的平均節(jié)省百分比如表3所示。對于所有實例,使用每個實例1 h的超時限制,并顯示每個價格遷移限制實例類型的平均成本。給出了3個指標表1至表3的兩個靜態(tài)代理排序的結果。

表1 分布式:代理DC在解決每個實例時交換的信息數(shù)

表2 分布式:遷移限制為5%和10%時的平均貨幣成本結果

表3 分布式:遷移限制為5%和10%時,相對于基線的平均節(jié)省百分比的結果

關于表1中所示的通信負載,代理在解決問題時交換了很少的信息。在最極端的情況下,AGAC-ng代理交換37 528條信息來解決問題。這代表了關于由完整DCOP算法解決的實例的復雜性和量值的重要結果。主要是由于每個局部解算器的局部過濾和搜索成本高昂,以及求解實例的拓撲結構:所有求解實例都有一個完整的約束網(wǎng)絡。因此,AGAC-ng產(chǎn)生的時間回溯比后跳更多。這可以通過算法的行為來解釋,其中只發(fā)現(xiàn)了對第一個解決方案的微小改進。在第一個解決方案之后,AGAC-ng算法主要從排序上的最后一個代理回溯到倒數(shù)第二個代理,后者將令牌返回給最后一個agent以尋求新的解決方案。

比較解決方案效果(表2和表3),例如情況5,與基線相比的改進是微不足道的。與基線相比,改善幅度在0.11%～0.27%,這意味著每天不到一元。在其他情況下,這種改善更為顯著,主要是在情況2,與基線相比,改善幅度在3.75%～5.75%,即每天7.32～11.27元。表明了有效性結果,主要是因為代理商只通過在他們之間傳遞消息來解決問題,而不分享他們的限制或價格,并保持信息隱私。比較兩種不同的代理模型,使用代理模型o2運行AGAC-ng總是可以改進使用o1定價的AGAC-ng。然而,對于解決問題的消息交換數(shù)量來說,情況并非總是如此。當使用o2運行AGAC-ng時,所有實例的平均成本分別為366元和369元。對于通信負載,AGAC-ng(o2)在所有實例中平均需要27 775條信息,而AGAC-ng(o2)需要26 661條信息。

關于遷移限制,結果表明,對于消息交換數(shù)量的分布式解決過程,遷移限制越小越好,而遷移限制的變化對解決方案效果的影響較小。在分布式問題中,當過濾能力有限時,具有較大域會導致更多信息。

4 結語

本文研究了地理分布的數(shù)據(jù)中心問題,其目標是優(yōu)化一組數(shù)據(jù)中心(DC)的工作負載分配,從而將能源成本降至最低。使用分布式約束優(yōu)化框架介紹了這個問題的模型。提出了一種新的基于AGAC-ng算法,該算法適用于每個代理具有多個變量、具有非二進制和硬約束的DCOP。AGAC-ng可以在每個代理上使用多項式空間找到最優(yōu)解,或者在用戶指定的距離內(nèi)找到最優(yōu)解。從實驗結果上展示了解決大規(guī)模DCOP的新方法的好處。