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

(中國(guó)能源建設(shè)集團(tuán)廣東省電力設(shè)計(jì)研究院有限公司,廣東 廣州 510663)

0 引言

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

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

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

代理ai∈A的賦值是來(lái)自其域的值的每個(gè)外部變量的賦值。即,一個(gè)元組(〈Ei,Vi〉,ti),其中Vi∈×dj,Vi[xj]∈dj,并且ti是標(biāo)記值。比較兩個(gè)項(xiàng)目時(shí),最新的項(xiàng)目是標(biāo)記ti最大的值。

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

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

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

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

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

圖1 在同一24 h內(nèi)10個(gè)不同地點(diǎn)的實(shí)時(shí)價(jià)格樣本

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

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

(1)

容量。DCal運(yùn)行虛擬機(jī)所消耗總能量是有限的:

(2)

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

(3)

本文進(jìn)一步添加了以下移入/移出變量對(duì)的冗余約束,強(qiáng)制每個(gè)類(lèi)型在每個(gè)時(shí)間段的每個(gè)位置中至少有一個(gè)必須為0:

(4)

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

(5)

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

(6)

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

cl=rl+ml

(7)

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

(8)

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

(9)

3 實(shí)例分析

3.1 參數(shù)設(shè)置

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

3.2 搜索策略

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

3.3 結(jié)果分析

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

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

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

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

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

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

關(guān)于遷移限制,結(jié)果表明,對(duì)于消息交換數(shù)量的分布式解決過(guò)程,遷移限制越小越好,而遷移限制的變化對(duì)解決方案效果的影響較小。在分布式問(wèn)題中,當(dāng)過(guò)濾能力有限時(shí),具有較大域會(huì)導(dǎo)致更多信息。

4 結(jié)語(yǔ)

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