丁建立　王斌強(qiáng)　張　超

1(中國(guó)民航大學(xué)中國(guó)民航信息技術(shù)科研基地　天津 300300)

2(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　天津 300300)

?

異地雙活數(shù)據(jù)中心服務(wù)區(qū)域劃分優(yōu)化

丁建立1,2王斌強(qiáng)2張超2

1(中國(guó)民航大學(xué)中國(guó)民航信息技術(shù)科研基地天津 300300)

2(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院天津 300300)

摘要異地雙活數(shù)據(jù)中心是現(xiàn)在傳統(tǒng)大型數(shù)據(jù)中心的發(fā)展趨勢(shì)。針對(duì)國(guó)內(nèi)某民航旅客服務(wù)信息系統(tǒng)高并發(fā)在線交易、大規(guī)模海量數(shù)據(jù)處理、應(yīng)急響應(yīng)和災(zāi)難快速恢復(fù)等要求，提出一種基于球面Voronoi圖的異地雙活數(shù)據(jù)中心服務(wù)區(qū)域劃分方法。該方法考慮了數(shù)據(jù)中心最大負(fù)載量的受限性和所有被分配用戶訪問到各自數(shù)據(jù)中心的總距離最小化，并在求解過程進(jìn)行了雙曲化優(yōu)化逼近和用戶分布估計(jì)。實(shí)驗(yàn)結(jié)果表明，在不同訪問用戶條件下，該方法都能重新調(diào)整用戶訪問數(shù)據(jù)中心的接入點(diǎn)，給出合理的區(qū)域劃分。該方法能均衡單數(shù)據(jù)中心的系統(tǒng)訪問壓力，為大數(shù)據(jù)時(shí)代數(shù)據(jù)中心建設(shè)和災(zāi)備系統(tǒng)建設(shè)提供技術(shù)支持。

關(guān)鍵詞球面Voronoi圖異地雙活數(shù)據(jù)中心民航最大負(fù)載服務(wù)區(qū)域劃分

OPTIMISING DIVISION OF SERVICE REGIONS OF DISTANT DOUBLE LIVE DATA CENTRE

Ding Jianli1,2Wang Binqiang2Zhang Chao21

(Information Technology Research Base,Civil Aviation Administration of China,Tianjin 300300,China)2(College of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)

AbstractDistant double live data centre is nowadays the development trend of traditional large data centres. According to the requirements of a certain China’s civil aviation passengers information service system, which includes highly concurrent online transactions, large-scale mass data processing, emergency response and quick disaster recovery, the paper presents a service region divistion solution for distant double live data centre, which is based on Voronoi diagram on the sphere. This solution takes into consideration the property of data centre’s peak load being constrained and the minimising of total distance that all the assigned users accessing to the data centre of each own, and makes hyperbolic optimised approximation and users’ distribution estimation in calculation process. Experimental results show that whatever the users’ access is, this scheme can all readjust the access points of users when accessing the data centre, and offers reasonable region division. The scheme can balance the system access pressure of single data centre, and provides technical support for the construction of data centre and disaster recovery system in big data era.

KeywordsVoronoi diagram on the sphereDistant double liveData centreCivil aviationPeak loadDivision of servant regions

0引言

隨著民航業(yè)的迅速發(fā)展，現(xiàn)有的民航旅客服務(wù)信息系統(tǒng)在存儲(chǔ)海量數(shù)據(jù)、進(jìn)行大規(guī)模數(shù)據(jù)分析處理、大并發(fā)在線交易快速響應(yīng)、容災(zāi)備份、應(yīng)急恢復(fù)等能力方面都逐漸顯現(xiàn)出了不足。因此，為了適應(yīng)民航業(yè)的發(fā)展需求，國(guó)內(nèi)某民航旅客服務(wù)信息提供商計(jì)劃建立異地雙活數(shù)據(jù)中心，以平衡系統(tǒng)訪問壓力、改善用戶體驗(yàn)，實(shí)現(xiàn)民航信息系統(tǒng)的高可靠性和高可用性。

存在多個(gè)生產(chǎn)數(shù)據(jù)中心時(shí)，一般是每個(gè)數(shù)據(jù)中心根據(jù)用戶自適應(yīng)接入機(jī)制，只為各自固定的區(qū)域用戶提供服務(wù)，通常是依靠全局負(fù)載均衡[1](GSLB)裝置。用戶在訪問多個(gè)數(shù)據(jù)中心時(shí)，GSLB根據(jù)DNS探測(cè)用戶位置，將用戶請(qǐng)求接入距離用戶最近的數(shù)據(jù)中心并返回結(jié)果，這種方式減少了網(wǎng)絡(luò)訪問延遲，改善了用戶體驗(yàn)。但這種方式?jīng)]有考慮到每個(gè)數(shù)據(jù)中心的最大負(fù)載量，當(dāng)訪問急劇攀升超過原來數(shù)據(jù)中心的最大閾值時(shí)，為減輕數(shù)據(jù)中心的負(fù)載壓力，就應(yīng)該將原來區(qū)域的部分用戶請(qǐng)求合理轉(zhuǎn)移到其他數(shù)據(jù)中心。由于地球本身近似球形，而球面Voronoi圖在全球數(shù)據(jù)的管理和球面空間關(guān)系的動(dòng)態(tài)維護(hù)具有優(yōu)秀的性質(zhì)[2]。所以，本文在基于球面Voronoi圖劃分的基礎(chǔ)上，結(jié)合各數(shù)據(jù)中心的最大負(fù)載量限制和用戶距離的最小化，給出了一種重新調(diào)整原有劃分的方法，以確定不同用戶訪問量下的服務(wù)區(qū)域。

1球面Voronoi圖的概念

Voronoi圖是分割空間的一種方法，和Delaunay多邊形呈對(duì)偶關(guān)系，Voronoi圖利用最近鄰近原則將空間劃分為多個(gè)區(qū)域，使得每個(gè)區(qū)域內(nèi)的點(diǎn)距離其所在空間的生長(zhǎng)點(diǎn)最近[3]。最早由俄國(guó)數(shù)學(xué)家M.G.Voronoi于1908年提出，并將其擴(kuò)展至高維空間。本文將Voronoi圖擴(kuò)展到球面進(jìn)行應(yīng)用。球面Voronoi圖[4]的數(shù)學(xué)定義:

球面R2為非歐式空間，設(shè)P={P1,P2,…,Pn}(2≤n≤∞)為球面R2上的對(duì)象點(diǎn)集，Xi和Xj分別為點(diǎn)Pi∈R2和Pj∈R2的位置矢量，點(diǎn)Pi和Pj之間的最短距離定義為通過兩點(diǎn)的大圓中較小弧段的長(zhǎng)。用公式表示為：

(1)

稱此距離為Pi和Pj之間的球面距離，稱：

V(Pi)={P|d(P,Pi)≤d(P,Pj),j≠i,P∈R2}

i=1,2,…,n

(2)

為關(guān)于Pi的球面的Voronoi多邊形，稱球面Voronoi多邊形的集合為球面R2上點(diǎn)P的球面Voronoi圖，P1,P2,…,Pn為生成點(diǎn)，如圖1、圖2所示。

圖1　半徑為1的球面Voronoi圖　　圖2　對(duì)應(yīng)的Delaunay三角網(wǎng)

2異地雙活數(shù)據(jù)中心服務(wù)區(qū)域劃分優(yōu)化

2.1異地雙活的概念

異地雙活[5]數(shù)據(jù)中心是現(xiàn)在傳統(tǒng)大型數(shù)據(jù)中心的發(fā)展趨勢(shì)?！爱惖亍毕鄬?duì)于同城而言，一般不在同一城域；“雙活”區(qū)別于一個(gè)數(shù)據(jù)中心、一個(gè)災(zāi)備中心的模式，前者兩個(gè)數(shù)據(jù)中心都處于運(yùn)行當(dāng)中，所以稱為“雙活”，且互為備份；后者是一個(gè)數(shù)據(jù)中心投入運(yùn)行，另外一個(gè)數(shù)據(jù)中心處在不工作狀態(tài)，只有當(dāng)災(zāi)難發(fā)生時(shí)，生產(chǎn)數(shù)據(jù)中心癱瘓，災(zāi)備中心才啟動(dòng)。圖3是國(guó)內(nèi)某民航旅客服務(wù)信息提供商異地雙活數(shù)據(jù)中心架構(gòu)示意圖。

圖3　國(guó)內(nèi)某民航旅客服務(wù)信息提供商異地雙活數(shù)據(jù)中心架構(gòu)示意

2.2基于球面Voronoi圖的異地雙活模型

為了科學(xué)合理的將多余的用戶分配到新的數(shù)據(jù)中心，本文做了如下假設(shè)。第一，所有數(shù)據(jù)中心的位置都已確定，數(shù)據(jù)中心的最大負(fù)載量用能為多少用戶量提供服務(wù)表示，總?cè)萘磕苋菁{所有的用戶，并且所有用戶的請(qǐng)求都是平等的；第二，研究的空間區(qū)域是全國(guó)范圍，區(qū)域內(nèi)的訪問用戶分布和區(qū)域的人口分布成正比。

本文主要基于國(guó)內(nèi)某民航旅客服務(wù)信息提供商的異地雙活數(shù)據(jù)中心進(jìn)行研究，僅生成兩點(diǎn)的球面Voronoi圖，將生成點(diǎn)P構(gòu)成的集合P={P1,P2}當(dāng)成數(shù)據(jù)中心，形成的區(qū)域記為ε1和ε2，U={U1,U2,…,UN}是當(dāng)前存在的N個(gè)用戶，由于各區(qū)域內(nèi)的用戶到各自生成點(diǎn)P的距離都是最短的，所以將ε1區(qū)域內(nèi)的用戶訪問分配給P1，ε2區(qū)域內(nèi)的用戶訪問分配給P2，各用戶到其所分配的數(shù)據(jù)中心之間的總距離記為：

(3)

其中j=j(i)是第i個(gè)用戶分配到第j(i)個(gè)數(shù)據(jù)中心的分配函數(shù)，d(Pj(i),Ui)表示球面上點(diǎn)Pj(i)和Ui之間的最短距離，可由式(1)得到。設(shè)Ci是數(shù)據(jù)中心Pi的最大負(fù)載量，最大負(fù)載量控制定義:Ni≤Ci，式中，Ni是分配到數(shù)據(jù)中心Pi的實(shí)際人數(shù)。

當(dāng)沒有最大負(fù)載量限制時(shí)，這種劃分能很好地滿足訪問距離的最小化，但現(xiàn)實(shí)并非如此，由于原先數(shù)據(jù)中心設(shè)施設(shè)計(jì)不足或者短期內(nèi)用戶訪問劇增，就需要采取措施對(duì)訪問進(jìn)行轉(zhuǎn)移。如N1>C1時(shí)，必須將ε1區(qū)域內(nèi)的部分用戶從數(shù)據(jù)中心P1轉(zhuǎn)移到數(shù)據(jù)中心P2，使得N1≤C1，此時(shí)距離將產(chǎn)生增量：

(4)

其中u12表示從數(shù)據(jù)中心P1轉(zhuǎn)移到數(shù)據(jù)中心P2的用戶的集合。

為了達(dá)到轉(zhuǎn)移后距離最優(yōu)，只需要找到一種使ΔD(j)最小的方法即可。

2.3雙曲化優(yōu)化逼近

在求解ΔD(j)最小化問題時(shí)，我們可以應(yīng)用雙曲線的性質(zhì)進(jìn)行求解。雙曲線在Voronoi圖上的性質(zhì)和應(yīng)用有很多的研究[6-8]，文獻(xiàn)[9]指出，在有約束限制的最小化分配問題，可以通過雙曲線的調(diào)整獲得。所以本文在球面上基于點(diǎn)P1和P2構(gòu)造雙曲線，雙曲線如下表示：

d(X,P2)-d(X,P1)=2k

(5)

通過調(diào)整k值進(jìn)行區(qū)域逼近，直到N1≤C1。

區(qū)域調(diào)整，導(dǎo)致P1數(shù)據(jù)中心區(qū)域內(nèi)的用戶數(shù)N1發(fā)生改變，所以程序中通過函數(shù)Get Curr User Nums()獲得當(dāng)前的用戶數(shù)，具體是統(tǒng)計(jì)當(dāng)前區(qū)域內(nèi)的城市數(shù)，計(jì)算其人口總和，以一定比例的人口數(shù)作為當(dāng)前區(qū)域內(nèi)的訪問用戶數(shù)。

為防止過多用戶從數(shù)據(jù)中心P1轉(zhuǎn)移到P2，降低數(shù)據(jù)中心的利用率。本文假定，最終劃分后，數(shù)據(jù)中心的負(fù)載量與最終分配到該中心的用戶數(shù)量的差應(yīng)小于1000，逐步逼近生成雙曲線的偽代碼表示如下，其中Xi是弧P1P2間上的點(diǎn)，借鑒取半查找的思想，通過ki×(1/2)×d(P1,P2)確定Xi的位置，進(jìn)而應(yīng)用式(5)生成當(dāng)前ki條件下對(duì)應(yīng)的雙曲線。

begin

1?i

N1=GetCurrUserNums()

while N1>C1or(C1-N1)>1000

{

d(Xi,P1)=ki×(1/2)×d(P1,P2)

//GetCurrUserNums()函數(shù)獲取當(dāng)前區(qū)域內(nèi)的用戶數(shù)

N1=GetCurrUserNums()

if N1>C1

{

i+1?i

}

else

{

i+1?i

}

}

returnki

end

2.4用戶分布估計(jì)

在每一次進(jìn)行雙曲劃分后，都需要重新計(jì)算該區(qū)域內(nèi)的用戶數(shù)量，為使實(shí)驗(yàn)方便，選擇了分布在全國(guó)的如北京、上海等77個(gè)百萬級(jí)人口城市[10]，訪問用戶數(shù)將以一定比例從城市人口總數(shù)中提取。本文生成了包含人口、經(jīng)度和緯度的城市kml文件，其中所有城市地理信息都包含在字段內(nèi)，字段通過包含、、等子字段來表示單個(gè)城市具體信息，如字段中population屬性表示城市人口數(shù)，字段表示城市名稱，字段表示當(dāng)前城市的經(jīng)緯度。kml文件格式示例如下：

xmlns:gx=″http://www.google.com/kml/ext/2.2″

xmlns:kml=″http://opengis.net/kml/2.2″

xmlns:atom=″http://www.w3.com.org/2005/Atom″>

population: 20217700

division: Shanghai

reference:

……

3模擬計(jì)算與結(jié)果分析

圖4　未考慮負(fù)載時(shí)的初始劃分

基于國(guó)內(nèi)某民航旅客服務(wù)信息提供商的北方(116.46，39.92)和南方(120.76，30.77)兩個(gè)數(shù)據(jù)中心，本節(jié)編寫代碼生成球面Voronoi圖，并通過調(diào)用google maps API 生成可視化仿真演示系統(tǒng)。圖4顯示的就是在沒有最大負(fù)載約束條件下基于球面Voronoi圖的服務(wù)區(qū)域劃分，粗弧線以上的區(qū)域都分配給北方數(shù)據(jù)中心，粗弧線以下的區(qū)域分配給南方數(shù)據(jù)中心。

在確定數(shù)據(jù)中心最大負(fù)載時(shí)，分析了全球其他三大民航旅客服務(wù)信息提供商數(shù)據(jù)中心的規(guī)模，針對(duì)提供商數(shù)據(jù)中心的每秒處理能力，以系統(tǒng)可承受一分鐘持續(xù)訪問處理量作為數(shù)據(jù)中心的可承受最大負(fù)載量，如表1所示。

表1　各提供商最大負(fù)載量

圖5　以國(guó)外A系統(tǒng)最大負(fù)載量作為用戶

由于南方數(shù)據(jù)中心規(guī)模很大，所以實(shí)驗(yàn)時(shí)我們只考慮北方數(shù)據(jù)中心的最大負(fù)載，并分別將其他三大GDS的最大負(fù)載量作為用戶訪問的最小量，對(duì)北方數(shù)據(jù)中心的服務(wù)區(qū)域分別進(jìn)行劃分。圖5中細(xì)弧線是當(dāng)有1 350 000用戶訪問，對(duì)北方數(shù)據(jù)中心所優(yōu)化的服務(wù)區(qū)域，調(diào)整后，區(qū)域內(nèi)用戶的訪問不超過數(shù)據(jù)中心的最大負(fù)載900 000，圖6、圖7分別表示當(dāng)2 220 000和2 520 000用戶訪問時(shí)的劃分。可以看出，隨著訪問量的增加，細(xì)弧線相應(yīng)向北移動(dòng)，使得北方數(shù)據(jù)中心的服務(wù)區(qū)域相應(yīng)減少。

4結(jié)語

異地雙活數(shù)據(jù)中心作為當(dāng)前最先進(jìn)的建設(shè)模式，國(guó)內(nèi)外相關(guān)的研究還比較少，同時(shí)雖然對(duì)于Voronoi圖，國(guó)內(nèi)在地理[11]、氣象等領(lǐng)域有較多的研究，但將其引入到異地雙活數(shù)據(jù)中心的研究還沒有。所以本文通過對(duì)球面Voronoi圖的研究，結(jié)合國(guó)內(nèi)某民航旅客服務(wù)信息系統(tǒng)數(shù)據(jù)中心的實(shí)際建設(shè)及應(yīng)用背景，提出了一種服務(wù)區(qū)域優(yōu)化的方法，考慮了數(shù)據(jù)中心最大負(fù)載的限

制和總距離的最優(yōu)化，對(duì)不同用戶訪問量進(jìn)行了仿真，能科學(xué)合理地均衡數(shù)據(jù)中心的大規(guī)模訪問量。整體實(shí)驗(yàn)結(jié)果比較合理，有一定的實(shí)用價(jià)值。

參考文獻(xiàn)

[1] 呂海燕,車曉偉,張杰.基于“偽HTTP Server”的CDN本地負(fù)載均衡實(shí)現(xiàn)方式[J].計(jì)算機(jī)技術(shù)與發(fā)展,2013,23(6):46-49.

[2] 趙學(xué)勝,陳軍,王金莊.基于O-QTM的球面Voronoi圖的生成算法[J].測(cè)繪學(xué)報(bào),2002,31(2):157-163.

[3] 龔詠喜,劉瑜,鄔倫,等.基于帶權(quán)Voronoi圖與地標(biāo)的空間位置描述[J].地理與地理信息科學(xué),2010,26(4):21-26.

[4] 張麗平,李松,郝忠孝.球面上的最近鄰查詢方法研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(5):126-129.

[5] TechTarget數(shù)據(jù)中心[OL].(2013-1-25).[2014-6-10].http://www.searchdatacenter.com.cn/shoontent_70148.htm.

[6] Nielsen F,Nock R.Hyperbolic Voronoi diagrams made easy[C]//Computational Science and Its Applications (ICCSA),2010 International Conference on.IEEE,2010:74-80.

[7] Bogdanov M,Devillers O,Teillaud M.Hyperbolic Delaunay complexes and Voronoi diagrams made practical[C]//Proceedings of the 29th annual symposium on Symposuim on computational geometry.ACM,2013:67-76.

[8] Barclay M,Galton A.Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams[J].Computers Environment and Urban Systems,2008,32(4):261-267.

[9] Shanmugam S,Shouraboura C.Finding Optimal Allocation of Constrained Cloud Capacity Using Hyperbolic Voronoi Diagrams on the Sphere[J].Intelligent Information Management,2012,4(5):239-250.

[10] 維基百科.中華人民共和國(guó)特大城市列表[OL].(2014-4-7).

[11] 李久剛,唐新明,劉正軍,等.基于行程距離最優(yōu)及容量受限的避難所分配算法研究[J].測(cè)繪學(xué)報(bào),2011(4):489-494.

中圖分類號(hào)TP309

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.007

收稿日期：2014-07-11。國(guó)家科技支撐計(jì)劃項(xiàng)目(2012BAH21 F02)；2013年民航科技創(chuàng)新引導(dǎo)資金重大專項(xiàng)(MHRD20130106)；中國(guó)民航大學(xué)中央高校基金項(xiàng)目(3122014C016)；中國(guó)民航大學(xué)預(yù)研重大項(xiàng)目(3122014P004)。丁建立，教授，主研領(lǐng)域：民航信息系統(tǒng)，航空物流。王斌強(qiáng)，碩士生。張超，碩士生。