丁建立　王斌强　张　超

1(中国民航大学中国民航信息技术科研基地　天津 300300)

2(中国民航大学计算机科学与技术学院　天津 300300)



异地双活数据中心服务区域划分优化

丁建立1,2王斌强2张超2

1(中国民航大学中国民航信息技术科研基地天津 300300)

2(中国民航大学计算机科学与技术学院天津 300300)

摘要异地双活数据中心是现在传统大型数据中心的发展趋势。针对国内某民航旅客服务信息系统高并发在线交易、大规模海量数据处理、应急响应和灾难快速恢复等要求，提出一种基于球面Voronoi图的异地双活数据中心服务区域划分方法。该方法考虑了数据中心最大负载量的受限性和所有被分配用户访问到各自数据中心的总距离最小化，并在求解过程进行了双曲化优化逼近和用户分布估计。实验结果表明，在不同访问用户条件下，该方法都能重新调整用户访问数据中心的接入点，给出合理的区域划分。该方法能均衡单数据中心的系统访问压力，为大数据时代数据中心建设和灾备系统建设提供技术支持。

关键词球面Voronoi图异地双活数据中心民航最大负载服务区域划分

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引言

随着民航业的迅速发展，现有的民航旅客服务信息系统在存储海量数据、进行大规模数据分析处理、大并发在线交易快速响应、容灾备份、应急恢复等能力方面都逐渐显现出了不足。因此，为了适应民航业的发展需求，国内某民航旅客服务信息提供商计划建立异地双活数据中心，以平衡系统访问压力、改善用户体验，实现民航信息系统的高可靠性和高可用性。

存在多个生产数据中心时，一般是每个数据中心根据用户自适应接入机制，只为各自固定的区域用户提供服务，通常是依靠全局负载均衡[1](GSLB)装置。用户在访问多个数据中心时，GSLB根据DNS探测用户位置，将用户请求接入距离用户最近的数据中心并返回结果，这种方式减少了网络访问延迟，改善了用户体验。但这种方式没有考虑到每个数据中心的最大负载量，当访问急剧攀升超过原来数据中心的最大阈值时，为减轻数据中心的负载压力，就应该将原来区域的部分用户请求合理转移到其他数据中心。由于地球本身近似球形，而球面Voronoi图在全球数据的管理和球面空间关系的动态维护具有优秀的性质[2]。所以，本文在基于球面Voronoi图划分的基础上，结合各数据中心的最大负载量限制和用户距离的最小化，给出了一种重新调整原有划分的方法，以确定不同用户访问量下的服务区域。

1球面Voronoi图的概念

Voronoi图是分割空间的一种方法，和Delaunay多边形呈对偶关系，Voronoi图利用最近邻近原则将空间划分为多个区域，使得每个区域内的点距离其所在空间的生长点最近[3]。最早由俄国数学家M.G.Voronoi于1908年提出，并将其扩展至高维空间。本文将Voronoi图扩展到球面进行应用。球面Voronoi图[4]的数学定义:

球面R2为非欧式空间，设P={P1,P2,…,Pn}(2≤n≤∞)为球面R2上的对象点集，Xi和Xj分别为点Pi∈R2和Pj∈R2的位置矢量，点Pi和Pj之间的最短距离定义为通过两点的大圆中较小弧段的长。用公式表示为：

(1)

称此距离为Pi和Pj之间的球面距离，称：

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

i=1,2,…,n

(2)

为关于Pi的球面的Voronoi多边形，称球面Voronoi多边形的集合为球面R2上点P的球面Voronoi图，P1,P2,…,Pn为生成点，如图1、图2所示。

图1　半径为1的球面Voronoi图　　图2　对应的Delaunay三角网

2异地双活数据中心服务区域划分优化

2.1异地双活的概念

异地双活[5]数据中心是现在传统大型数据中心的发展趋势。“异地”相对于同城而言，一般不在同一城域；“双活”区别于一个数据中心、一个灾备中心的模式，前者两个数据中心都处于运行当中，所以称为“双活”，且互为备份；后者是一个数据中心投入运行，另外一个数据中心处在不工作状态，只有当灾难发生时，生产数据中心瘫痪，灾备中心才启动。图3是国内某民航旅客服务信息提供商异地双活数据中心架构示意图。

图3　国内某民航旅客服务信息提供商异地双活数据中心架构示意

2.2基于球面Voronoi图的异地双活模型

为了科学合理的将多余的用户分配到新的数据中心，本文做了如下假设。第一，所有数据中心的位置都已确定，数据中心的最大负载量用能为多少用户量提供服务表示，总容量能容纳所有的用户，并且所有用户的请求都是平等的；第二，研究的空间区域是全国范围，区域内的访问用户分布和区域的人口分布成正比。

本文主要基于国内某民航旅客服务信息提供商的异地双活数据中心进行研究，仅生成两点的球面Voronoi图，将生成点P构成的集合P={P1,P2}当成数据中心，形成的区域记为ε1和ε2，U={U1,U2,…,UN}是当前存在的N个用户，由于各区域内的用户到各自生成点P的距离都是最短的，所以将ε1区域内的用户访问分配给P1，ε2区域内的用户访问分配给P2，各用户到其所分配的数据中心之间的总距离记为：

(3)

其中j=j(i)是第i个用户分配到第j(i)个数据中心的分配函数，d(Pj(i),Ui)表示球面上点Pj(i)和Ui之间的最短距离，可由式(1)得到。设Ci是数据中心Pi的最大负载量，最大负载量控制定义:Ni≤Ci，式中，Ni是分配到数据中心Pi的实际人数。

当没有最大负载量限制时，这种划分能很好地满足访问距离的最小化，但现实并非如此，由于原先数据中心设施设计不足或者短期内用户访问剧增，就需要采取措施对访问进行转移。如N1>C1时，必须将ε1区域内的部分用户从数据中心P1转移到数据中心P2，使得N1≤C1，此时距离将产生增量：

(4)

其中u12表示从数据中心P1转移到数据中心P2的用户的集合。

为了达到转移后距离最优，只需要找到一种使ΔD(j)最小的方法即可。

2.3双曲化优化逼近

在求解ΔD(j)最小化问题时，我们可以应用双曲线的性质进行求解。双曲线在Voronoi图上的性质和应用有很多的研究[6-8]，文献[9]指出，在有约束限制的最小化分配问题，可以通过双曲线的调整获得。所以本文在球面上基于点P1和P2构造双曲线，双曲线如下表示：

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

(5)

通过调整k值进行区域逼近，直到N1≤C1。

区域调整，导致P1数据中心区域内的用户数N1发生改变，所以程序中通过函数Get Curr User Nums()获得当前的用户数，具体是统计当前区域内的城市数，计算其人口总和，以一定比例的人口数作为当前区域内的访问用户数。

为防止过多用户从数据中心P1转移到P2，降低数据中心的利用率。本文假定，最终划分后，数据中心的负载量与最终分配到该中心的用户数量的差应小于1000，逐步逼近生成双曲线的伪代码表示如下，其中Xi是弧P1P2间上的点，借鉴取半查找的思想，通过ki×(1/2)×d(P1,P2)确定Xi的位置，进而应用式(5)生成当前ki条件下对应的双曲线。

begin

1⟹i

N1=GetCurrUserNums()

while N1>C1or(C1-N1)>1000

{

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

//GetCurrUserNums()函数获取当前区域内的用户数

N1=GetCurrUserNums()

if N1>C1

{

i+1⟹i

}

else

{

i+1⟹i

}

}

returnki

end

2.4用户分布估计

在每一次进行双曲划分后，都需要重新计算该区域内的用户数量，为使实验方便，选择了分布在全国的如北京、上海等77个百万级人口城市[10]，访问用户数将以一定比例从城市人口总数中提取。本文生成了包含人口、经度和纬度的城市kml文件，其中所有城市地理信息都包含在字段内，字段通过包含、、等子字段来表示单个城市具体信息，如字段中population属性表示城市人口数，字段表示城市名称，字段表示当前城市的经纬度。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模拟计算与结果分析

图4　未考虑负载时的初始划分

基于国内某民航旅客服务信息提供商的北方(116.46，39.92)和南方(120.76，30.77)两个数据中心，本节编写代码生成球面Voronoi图，并通过调用google maps API 生成可视化仿真演示系统。图4显示的就是在没有最大负载约束条件下基于球面Voronoi图的服务区域划分，粗弧线以上的区域都分配给北方数据中心，粗弧线以下的区域分配给南方数据中心。

在确定数据中心最大负载时，分析了全球其他三大民航旅客服务信息提供商数据中心的规模，针对提供商数据中心的每秒处理能力，以系统可承受一分钟持续访问处理量作为数据中心的可承受最大负载量，如表1所示。

表1　各提供商最大负载量

图5　以国外A系统最大负载量作为用户

由于南方数据中心规模很大，所以实验时我们只考虑北方数据中心的最大负载，并分别将其他三大GDS的最大负载量作为用户访问的最小量，对北方数据中心的服务区域分别进行划分。图5中细弧线是当有1 350 000用户访问，对北方数据中心所优化的服务区域，调整后，区域内用户的访问不超过数据中心的最大负载900 000，图6、图7分别表示当2 220 000和2 520 000用户访问时的划分。可以看出，随着访问量的增加，细弧线相应向北移动，使得北方数据中心的服务区域相应减少。

4结语

异地双活数据中心作为当前最先进的建设模式，国内外相关的研究还比较少，同时虽然对于Voronoi图，国内在地理[11]、气象等领域有较多的研究，但将其引入到异地双活数据中心的研究还没有。所以本文通过对球面Voronoi图的研究，结合国内某民航旅客服务信息系统数据中心的实际建设及应用背景，提出了一种服务区域优化的方法，考虑了数据中心最大负载的限

制和总距离的最优化，对不同用户访问量进行了仿真，能科学合理地均衡数据中心的大规模访问量。整体实验结果比较合理，有一定的实用价值。

参考文献

[1] 吕海燕,车晓伟,张杰.基于“伪HTTP Server”的CDN本地负载均衡实现方式[J].计算机技术与发展,2013,23(6):46-49.

[2] 赵学胜,陈军,王金庄.基于O-QTM的球面Voronoi图的生成算法[J].测绘学报,2002,31(2):157-163.

[3] 龚咏喜,刘瑜,邬伦,等.基于带权Voronoi图与地标的空间位置描述[J].地理与地理信息科学,2010,26(4):21-26.

[4] 张丽平,李松,郝忠孝.球面上的最近邻查询方法研究[J].计算机工程与应用,2011,47(5):126-129.

[5] TechTarget数据中心[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] 维基百科.中华人民共和国特大城市列表[OL].(2014-4-7).

[11] 李久刚,唐新明,刘正军,等.基于行程距离最优及容量受限的避难所分配算法研究[J].测绘学报,2011(4):489-494.

中图分类号TP309

文献标识码A

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

收稿日期：2014-07-11。国家科技支撑计划项目(2012BAH21 F02)；2013年民航科技创新引导资金重大专项(MHRD20130106)；中国民航大学中央高校基金项目(3122014C016)；中国民航大学预研重大项目(3122014P004)。丁建立，教授，主研领域：民航信息系统，航空物流。王斌强，硕士生。张超，硕士生。