基于加权V图的异地多活数据中心接入划分

曹卫东，周 原，孙晓君，王 静

(1.中国民航大学 天津市智能信号与图像处理重点实验室，天津 300300；2.中国民航大学 计算机科学与技术学院，天津 300300)

0 引 言

异地多活数据中心的建设模式是如今的发展趋势，诸多企业机构已经建设了多数据中心。Amadeus全球旅游分销公司已经在艾尔丁建立了两个数据中心，并规划在美国迈阿密、澳大利亚悉尼建立数据中心[1]；阿里巴巴目前在全球建立了9个数据中心，其中上海、杭州、青岛已经达到异地多活模式[2]；铁路12306售票系统日前建设成功同城双数据中心[3]；国家税务总局于北京建立主数据中心，并在广东南海成功建立异地数据中心[4]。异地多活数据中心的迅速发展，对平衡系统访问压力、在线交易快速响应有着更高的要求[5]。如何合理有效地将用户接入最佳的数据中心，从而使资源得以充分利用、平衡系统的访问压力、使用户具有更为良好的用户体验成为待为解决的问题[6]。

传统的用户接入的方法主要是基于DNS域名解析服务[7]，该方法考虑了用户与数据中心的距离，但没有考虑数据中心的最大负载情况。因此，提出一种基于常规Voronoi图(简称V图)的服务区域划分方法[8]，该方法在考虑距离的基础上考虑了数据中心的最大负载。然而，该方法并没有考虑数据中心自身的性能条件和当前负载情况，即数据中心的处理能力。为解决上述问题，本文提出了一种基于加权Voronoi图(简称加权V图)的用户接入划分方法，以确定在考虑数据中心性能条件和当前负载的综合条件下的用户接入划分。

1 V图的概念

1.1 常规Voronoi图

Voronoi图是分割空间的一种方法，它将空间划分为多个区域，使得每个区域内的点距离其所在空间的生长点最近。设平面上的一个控制点集P=(p1,p2,…,pn),其中任意两点都不共位，且任意4点都不共圆,则任意点pi的Voronoi图(以下简称V图)定义为[9]

(1)

V图的空间划分如图1所示。

图1 常规V图

1.2 加权Voronoi图

加权Voronoi图同样是空间分割的一种方法，它将空间划分为多个区域，使得每个区域内的点到其所在空间生长点的距离与该点到相邻区域生长点的距离之比，小于两个生长点的权重之比。因此，加权Voronoi图适用于各生长点的权重不一样的情况下的空间划分[10]。可以认为，在加权Voronoi图所划分出的每个区域内的所有点受该区域生长点的影响最大。设pi(i=1,2,…,n)为二维欧氏空间上的n个点，λi(i=1,2,…,n)是给定的n个正实数。则任意点pi的加权Voronoi图(以下简称加权V图)定义为[11]

(2)

加权V图的空间划分如图2所示。

图2 加权V图

2 异地多活用户接入划分算法

2.1 算法流程

异地多活数据中心旨在将业务分布到位于不同地方的多个数据中心，各个数据中心并行为用户提供服务。多数据中心共同承担业务，中心之间地位均等，协同工作。

为了科学合理地划分服务区域，做了如下假设。第一，研究的空间区域是全国范围，并且所有用户的请求都是平等的。第二，所有数据中心的位置都已确定，总容量能容纳所有的用户。

本文主要讨论由3个数据中心构成的异地多活模型，仅生成3点的加权V图。将生成点P构成的集合P={P1,P2,P3}表示数据中心，形成的区域记为ε1、ε2和ε3，U={U1,U2,…,Un}是当前存在的N个用户，由于各区域内的用户受各自生成点P的影响是最大的，所以将区域ε1内的用户访问分配给P1，ε2区域内的用户访问分配给P2，ε3区域内的用户访问分配给P3。算法流程如图3所示。

图3 基于加权V图的用户接入划分流程

2.2 算法描述

算法的具体过程如下：

(1)收集各个服务器的性能参数：选用W(si)这个参量表示服务器si的性能条件。性能条件W(si)由CPU核心数n(si)、CPU主频c(si)、磁盘容量d(si)、RAM大小r(si)、内存速度e(si)、L1缓存m(si)、L2缓存o(si)这几个因素决定

(3)

式中：αi表示各因素对数据中心性能条件的贡献度,αi的值越大表示对数据中心的处理能力影响程度越大。

(4)

式中：βi表示各因素对负载量的贡献度，βi的值越大表示该因素对数据中心的负载量影响越大。

(3)计算各个服务器处理能力得分值：选取影响服务器处理能力的14个指标作为确定权重值的指标体系，运用主成分分析法，根据特征值、累计贡献率选取主成分，得到系统中每个服务器的得分值。

首先根据特征值和累计贡献率确定主成分，按照累计贡献率大于80%，特征值大于1选取。其中，主成分Zi贡献率ωZi的计算公式为

(5)

前k个主成分的累计贡献率ω的计算公式为

(6)

然后，根据确定好的主成分得到因子得分系数，即可得到各个服务器处理能力得分值。

(4)数据变换得到各个服务器权重值：在计算各个服务器得分值的过程中，有些服务器的得分值可能为负值，这显然不满足加权V图的定义。为此，必须对各个服务器的综合得分值进行数据变换。常用的数据变换的方法有多种，文献[12]指出，最小-最大规范化方法是数据变换的一个重要方法，它可以对原始数据进行线性变换，使之落入一个特定的区间，同时保持了原始数据之间的关系。本文选取在[1,10]闭区间上对各个服务器得分值进行数据变化，使服务器得分值保持原始关系落入[1,10]这一特定区间。其公式为

(7)

其中，v′表示规范化处理后的数据；v表示原始数据；maxM和minM分别表示原始数据的最大值和最小值；new_maxM和new_minM分别表示新数列的最大值和最小值。

(5)计算数据中心权重：统计订票系统各个服务器的性能条件和负载情况，得到各个服务器的权重值λsi，则基于订票系统的数据中心的权重λj定义为

(8)

(6)得到用户划分结果：将得到的数据中心的权重值代入式(2)，即可得到基于加权V的用户接入划分方法。

3 实 验

3.1 实验介绍

旅客订票系统在民航旅客服务系统异地多活数据中心中占有举足轻重的地位，据统计，我国全年在线机票总出票量约为3.5亿张。因此，本文所做对异地多活数据中心的用户接入划分是基于旅客订票系统的用户接入的划分。民航旅客服务系统中3个数据中心的经纬度位置分别为：数据中心1(116.46，39.92)、数据中心2(120.76，30.77)和数据中心3(103.16，31.23)。研究以这3个数据中心为生长点建立的加权V图。

由于统计数据较多，仅列举数据中心1的旅客订票系统中各个服务器的指标记录值，也仅列举其中一部分服务器的记录值，其记录情况见表1、表2。

3.2 实验场景

为更好地分析比较各个情况下的用户接入划分，本实验设计了4个场景。

场景1：不考虑不同数据中心旅客订票系统的性能条件和负载情况，仅考虑用户到数据中心距离的基于常规V图的用户接入划分。

场景2：考虑用户到数据中心距离的基础上，又考虑到不同数据中心旅客订票系统的性能条件的情况下,做出的基于加权V图的用户接入划分,此种场景是考虑到资源的利用情况,尽量将用户接入到性能条件较好的数据中心来处理。

表2 数据中心1旅客订票系统部分服务器负载指标记录值

场景3：考虑用户到数据中心距离的基础上，又考虑到不同数据中心旅客订票系统的负载情况的条件下，做出的基于加权V图的用户接入划分，此种场景旨在平衡系统的访问压力，尽量将用户接入到负载较低的数据中心来处理。

场景4：综合考虑用户到数据中心的距离、不同数据中心旅客订票系统的性能条件、负载情况，做出的基于加权V图的用户接入划分，此种场景旨在让资源得以充分利用的同时，又能平衡系统的访问压力。

3.3 实验结果

权重计算实验由SPSS统计分析工具计算，根据数据计算得到各个场景中3个数据中心的权重值。计算结果见表3。

表3 不同场景3个数据中心权重值

接入划分实验由ArcGIS开发工具编程绘制，编写代码生成常规V图以及加权V图。实验结果如下：

场景1：基于国内某民航旅客服务信息提供商的数据中心1(116.46，39.92)、数据中心2(120.76，30.77)和数据中心3(103.16，31.23)这3个数据中心，编写代码生成常规V图的用户接入划分。

图4给出了用户服务区域的划分。如果不考虑数据中心订票系统的处理能力，即系统的性能条件和负载情况，此中划分方法能够方便简洁地给出用户服务区域的划分，确定用户应该接入哪个数据中心。但是由于旅客订票系统在各个不同的数据中心有不同的处理能力，仅按用户与数据中心的距离来确定用户的接入显得不够合理。

图4 考虑距离的常规用户接入划分

场景2：考虑数据中心旅客订票系统的性能条件，由式(3)可知影响订票系统性能调节的指标有CPU核心数n(si)、CPU主频c(si)、磁盘容量d(si)、RAM大小r(si)、内存速度e(si)、L1缓存m(si)、L2缓存o(si)，结合表1中的数据，运用权重值确定算法，得到考虑性能条件下的3个数据中心旅客订票系统的权重，分别为λ1=6.9326，λ2=6.2543，λ3=2.5961。由此，得到考虑性能条件时的基于加权V图的用户接入划分。

由表3可见，此场景中数据中心1的权重值最大，即数据中心1的性能条件最好，而数据中心3的权重值最小，即说明数据中心3的性能条件较差。因此，如图5所示，数据中心1的用户接入划分范围明显较图4有所扩大，而数据中心3的用户接入划分范围较图4有所缩小。这是由于考虑了不同数据中心的旅客订票系统的系统性能,性能越好,用户接入范围越大,这样使资源得以充分利用，发挥其更大的作用。

图5 考虑性能条件的加权用户接入划分

场景3：考虑数据中心旅客订票系统的负载情况，由式(4)可知影响订票系统负载情况的指标有CPU利用率a(si)、磁盘I/O占用率b(si)、内存利用率g(si)、文件系统空间的占用比h(si)、磁盘平均响应时间k(si)、磁盘读取速度l(si)、磁盘写入速度q(si)，同样结合表1给出的数据，运用权重值确定算法，得到考虑负载情况下的3个数据中心旅客订票系统的权重，分别为λ1=3.2689，λ2=4.1292，λ3=6.2189。由此，得到考虑负载情况时的基于加权V图的用户接入划分。

由表3可见，此场景中数据中心3的权重值最大，即数据中心3的旅客订票系统负载最小，而数据中心2的权重值最小，即说明数据中心2的旅客订票系统负载最大。因此，如图6所示，数据中心3的用户接入划分范围较图4与图5明显有所扩大，而数据中心2的用户接入划分范围较图4和图5有所缩小。这是由于考虑了不同数据中心的旅客订票系统的负载情况，负载越小，用户接入范围越大，负载越大，用户接入范围越小，这样能更好平衡系统的访问压力，将用户接入到负载较小的数据中心的系统，使其有更为良好的用户体验。

图6 考虑负载情况的加权用户接入划分

场景4：综合考虑用户与数据中心的距离以及旅客订票系统在不同数据中心的处理能力和负载情况，即系统的处理能力，结合表1所给的旅客订票系统的服务器状态数据，由第2章所论述的求解加权值的算法，得到3个数据中心旅客订票系统的系统权重，分别为λ1=7.1685，λ2=4.1536，λ3=5.5985。由此，得到综合考虑多种条件下的基于加权V图的旅客订票系统的用户接入的划分。

由表3可见，对比3种场景下各个数据中心的权重，可见在场景1仅考虑数据中心性能条件时，数据中心1、2的权重值最大，即性能条件最好。但场景2中考虑数据中心负载情况时，数据中心1、2的权重值较小，说明此时数据中心1、2的负载较大。若仅考虑数据中心性能条件将更多用户接入到性能条件较好的数据中心1、2，则会造成数据中心1、2的负载越来越大，导致较差的用户体验。同理，若仅考虑数据中心负载将更多用户接入到负载较小的数据中心3，则不能充分利用性能条件较好的数据中心1、2，造成资源的浪费。因此，综合考虑用户到数据中心的距离以及数据中心性能条件和负载情况，则会使划分充分考虑各个因素，全面而合理。

由图7可见，订票用户的接入划分更为精确。仅考虑某一因素时被分配到某个数据中心的用户，在综合考虑到用户到数据中心的距离以及旅客订票系统的处理能力后，可能被分配到处理能力更好的系统。由此可以看到，在考虑了位于不同数据中心的订票系统的处理能力之后，用户接入的划分显得更为合理，在如今大并发在线交易形式下，能够保证更好的用户体验，同时对条件更好的资源予以了充分利用，避免了闲置资源的浪费。

图7 考虑综合因素的加权用户接入划分

4 结束语

本文提出一种基于加权V图的异地多活数据中心用户接入划分方法。该方法虽在地理、气象领域有较成熟的研究，但鲜有将该方法用于用户接入划分。因此，本文以民航旅客服务系统为应用背景，将加权V图的方法应用到用户接入划分。该方法能够在距离的基础上，同时考虑数据中心的性能条件和负载情况，给出更为合理的用户接入划分，避免了资源浪费，同时能保障较好的用户体验。

[1]TravelDaily.TheAmadeusdecidedtosetupadatacenterintheunitedstates[EB/OL].[2016-12-02].http://www.traveldaily.cn/article/44955(inChinese).[环球旅讯.Amadeus决定在美国设立数据中心[EB/OL].[2016-12-02].http://www.traveldaily.cn/article/44955.]

[2]Yuntoutiao.AninterviewwithAlibabaBiXuan:Thecauseandeffectoftheprojectoflongdistancemultidatacenters[EB/OL].[2016-12-02].http://www.yuntoutiao.com/dongtai/2646.html(inChinese).[云头条.专访阿里巴巴毕玄:异地多活数据中心项目的来龙去脉[EB/OL].[2016-12-02].http://www.yuntoutiao.com/dongtai/2646.html.]

[3]Ctiforum.Anewgenerationofrailwaydatacenterconstructionscheme[EB/OL].[2016-12-02].http://www.ctiforum.com/news/guandian/394319_3.html(inChinese).[CTI论坛.新一代铁路数据中心建设方案[EB/OL].[2016-12-02].http://www.ctiforum.com/news/guandian/394319_3.html.]

[4]ZHAOWei.ThedesignandimplementationofthedisasterrecoverysystemofShaQnxitaxation[D].Xi’an:XidianUniversity,2013:17-29(inChinese).[赵玮.陕西地税容灾备份系统的设计与实现[D].西安:西安电子科技大学,2013:17-29.]

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

[6]SUNYang,HEJianzhong.Adaptiveload-balancingclusteringhierarchicalroutingprotocolforWSN[J].ComputerEngineeringandDesign,2013,34(2):423-427(inChinese).[孙扬,何建忠.WSN自适应负载均衡集簇分层路由协议[J].计算机工程与设计,2013,34(2):423-427.]

[7]LIUMei,ZHANGYongbin,RANChongshan,etal.ResearchonthemechanismofparkeddomainsrecognitionbasedonauthoritativeDNSservers[J].JournalofComputerApplications,2016,36(12):3311-3316(inChinese).[刘梅,张永斌,冉崇善,等.基于权威DNS服务器的停靠域名识别机制研究.计算机应用,2016,36(12):3311-3316.]

[8]DINGJianli,WANGBinqiang,ZHANGChao.Aserviceregionsegmentationofdistantdoublelivedatacenter[J].ComputerApplicationsandSoftware,2016,33(2):30-32(inChinese).[丁建立,王斌强,张超.异地双活数据中心服务区域划分优化[J].计算机应用与软件,2016,33(2):30-32.]

[9]ChengR,XieX,ManLY,etal.AVoronoidiagramforuncertaindata[J].VldbJournal,2012,22(3):796-807.

[10]MENGQibin.Substationmulti-stageplanningbasedonimprovedweightedVoronoidiagram[D].Hebei:NorthChinaElectricPowerUniversity,2015:16-27(inChinese).[孟琦斌.基于改进加权Voronoi图的变电站多期规划[D].河北:华北电力大学,2015:16-27.]

[11]TANGDuoyu,CAOHan.ParallelalgorithmdesigningandapplicationofweightedVoronoidiagramusingMapReduceprogrammingmode[J].ApplicationResearchofComputers,2013,30(5):1410-1412(inChinese).[唐多余,曹菡.基于MapReduce的加权Voronoi图并行算法设计及应用[J].计算机应用研究,2013,30(5):1410-1412.]

[12]ZHANGXiaoyan,MENGXiangfu,MAZongmin,etal.Attributeweightevaluationapproachbasedonapproximatefunctionaldependencies[J].ComputerScience,2013,40(2):172-176(inChinese).[张霄雁,孟祥福,马宗民,等.基于近似函数依赖的关系数据属性权重评估方法[J].计算机科学,2013,40(2):172-176.]