CN105739929A - 大数据向云端迁移时的数据中心的选择方法 - Google Patents

Abstract

本发明提出了一种大数据向云端迁移时的数据中心的选择方法，首先，考虑到因用户偏好和法律限制等因素导致DC不可用情况，进行了非完全图建模；采用激活级别的方式来描述用户的数据产生量；定义了公平数据放置FDP、优选数据放置PDP、传输成本最小化数据放置TCMDP和成本最小化数据放置CMDP等四种准则；基于上述准则进行DC的选择。本发明提出的方法针对BD向云端移动时的需求，从用户角度研究了移动机制，可以缩短数据接入时延，降低数据成本。本发明的方法可以反映DC的可用性以及用户的偏好。本发明的方法可以利用网络自动进行低成本，低延迟的数据迁移，避免采用硬件方式，有利于自动化管理的实施。

Description

大数据向云端迁移时的数据中心的选择方法

技术领域

本发明涉及云计算技术领域，尤其涉及一种大数据向云端迁移时的数据中心的选择方法。

背景技术

云计算已经成为了大数据(BD)分析的优选平台。特别的当数据时从多个跨地域分布的地点产生，而且本地用户需要经常用到本地数据，并且有时数据又需要进一步整合以进行进一步分析时，尤其如此。例如，对于一个具有很多遍布全球的子公司的跨国销售公司来说，每个国家的子公司为了商业目的需要及时对本土用户产生的数据进行分析。所有的数据又要被汇总分析以报给总部，或者支持跨国交易。一般来说，一个大型的云以分布式进行组网并具有多个跨地域分布的数据中心(DC，比如Amazon至少有遍布4个大洲的11个DC，Google至少有遍布4个洲的13个DC)。每个DC都已按需付费的方式配置有计算以及存储资源。这种基础设施能够提供就近服务，特别适合于跨地域分布。

为了在云中处理BD，前提条件是将BD迁移并存储到合适的DC上。直接移动硬件是移动大规模数据的一种可选方式。比如，AmazonImport/Export服务推荐用可移动存储设备来运送数据。有时，甚至有可能移动整个机器。但这只适合于间歇性的，或者一次性的大批量数据移动。这种方式有很大的延迟，不能满足不断增长的数据实时分析需求。而且它也和自动管理理念相矛盾，并且需要更多的变得越来越贵的劳动力参与。在Inter网上传数据非常昂贵，而且因为太大的延迟而不实用。据Amazon数据，通过10MBInter网传输1TB的数据大致需要13天时间。实时数据通常被建议用高速专用连接传送(如AWSdirectconnect)。这种方式能够加快传输速度。但即便依赖于高速专用连接，跨大洲进行数据传输仍然十分困难。例如，AWSdirectconnect不提供跨大洲的服务。而国际专线却太贵。这就限制了将通常遍布全球的大规模数据移动到一个DC上。而且，用一个DC来存储数据会导致更经常的本地数据分析延迟更大。

特别在一些区域，数据安全法律要求一些数据必须存储在本地(如欧盟的一些国家)。总而言之，用户有必要遵循一些规则来为他们的数据选择合适的存储地点。就像Amazon建议的那样：离用户更近以减少数据使用延迟，满足特定的法律规要求，或者减少成本等。

当前，一些基于MapReduce的框架，比如G-Hadoop和G-MR，已能够实现跨集群和DC的数据分析。和只用一个DC的机制相比，使用多个DC的机制不仅能满足综合分析的需求，而且能保证更快的数据使用和具有更低的成本。

将BD移动到云端时多个DC的选择问题和设施选择问题(facilitylocationproblem，FLP)以及k-中间点问题相关。FLP旨在基于不同准则选择设施来服务客户。DC可以被看做是设施，而本地数据用户即是客户。k-中间点问题试图找到不多于k个点，其余没有被选择的点将被指配到一个被选择的点，使得这些点对之间的边长和最小。

FLP问题的变种中，k-供应商问题需要从给定集合中选择至多k个供应商(对应DC)使得每个客户和离他最近的供应商之间的最大距离最小。一般的，供应商和客户网络被建模成一个完全图对于一个广义的k-供应商问题变种，每一个供应商被赋予一个权值，要求所有被选择的供应商权值不大于k。但是，受限于法规，一些DC可能不能用来服务某些数据，所以图不总是完全图。而且，数据是和用户相关的，而不是和DC(供应商)相关。

无容量限制的设施选择问题(Uncapacitatedfacilitylocation，UFL)是FLP的另一个变种，其中设施没有容量限制，而且每一个设施有一个固定的开设成本权重。问题目标是极小化总的固定成本和总的服务成本。目前所得到的算法都有一个常数的违约因子。即这意味着算法需要的设施个数不少于k的某个倍数。而k-中间点问题不考虑设施的权重，但是数据的移动是与数据的大小相关的。

发明内容

为了解决现有技术中的问题，本发明提出了一种大数据向云端迁移时的数据中心的选择方法，实现分布式云计算中BD向云端移动时的低成本、高速率的数据存取目标。

本发明通过以下技术方案实现：

一种大数据向云端迁移时的数据中心的选择方法，所述方法包括：构建底层非完全图，采用激活级别的方式来描述用户的数据产生量，定义公平数据放置FDP、优选数据放置PDP、传输成本最小化数据放置TCMDP和成本最小化数据放置CMDP等四种准则，以及基于上述准则之一进行DC的选择；其中，所述非完全图G＝(U,V,E)，U代表用户，V代表DC，边长e_ij∈E(i∈U,j∈V)满足三角不等式，正整数k(k≤|U|,k≤|V|)，对于任意i∈U以及j∈V，如果用户i的数据能够被移动到DCj，则它们之间存在一条边；所述方法旨在从可用的DC集合V中找到一个DC子集D(|D|≤k)来按照不同准则存储U中所有用户的数据；所述FDP准则为：最大的用户和被指配到的DC之间的距离极小化，使得每个本地用户可以以最小的时延接入数据：所述PDP准则为：最大的用户和被指配到的DC之间的加权距离极小化，使得具有更多数据的本地用户可以以最小的时延接入数据：所述TCMDP准则为：所有用户和其被指配到的DC之间的加权距离的和极小化：所述CMDP)准则为：所有用户的成本之和极小化：

本发明的有益效果是：本发明提出的方法针对BD向云端移动时的需求，从用户角度研究了移动机制，可以缩短数据接入时延，降低数据成本。本发明研究了四种准则：公平数据放置FDP，优选数据放置PDP，传输成本最小化数据放置TCMDP和成本最小化数据放置CMDP，本发明的方法可以反映DC的可用性以及用户的偏好，对于前两种准则，算法能够保证找到的解至少不差于3倍的最优解。本发明的方法可以利用网络自动进行低成本，低延迟的数据迁移，避免采用硬件方式，有利于自动化管理的实施。

附图说明

图1是本发明的分布式用户数据和数据中心的非完全二分图；

图2是门限图的示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

本发明考虑将跨地域分布的大数据移动到云端的可行性，研究了多个目标DC选择问题，用非完全二分图来表示底层设施，从而克服了已有问题都是完全二分图的局限。更加符合实际情况中由于用户偏好，或者是法律限制而导致的并不是每个DC都可用的情况。

附图1模拟了一个分布式用户数据和分布式云计算中的DC构成的非完全二分图，其中用户有所偏好或者受安全法律限制，并不是每个DC都能被每一个用户选择。有边连接表示本DC可用或者用户不排斥。

本发明是目的是寻求更快的数据接入和更低的成本。这个问题推广了传统的k-供应商问题、UFL和k-中间点问题。

考虑底层非完全图G＝(U,V,E)，其中U代表用户，V代表DC，边长e_ij∈E(i∈U,j∈V)满足三角不等式，正整数k(k≤|U|,k≤|V|)，本发明旨在从可用的DC集合V中找到一个DC子集D(|D|≤k)来按照不同准则存储U中所有用户的数据。对于任意i∈U以及j∈V，如果用户i的数据能够被移动到DCj(至少不被法规限制或者不被用户排除)，则它们之间存在一条边。假定所有的i都临近至少一个j，否则问题无解。假定|E|＝m，其中m≤|U|*|V|。

用户权重定义：每个用户都被赋予一个权重w_i，表示当前或者可见的未来的数据产生的激活级别，或者本地用户的重要程度。w_i随着数据量或者重要程度的增加而增加。用激活级别而不是数据量可以容忍数据的动态变化同时提供对数据量的适度近似。激活级别可以根据每天上载数据量而定。例如对于一个典型的每天上载200GB的公司而言，10GB可以被用来作为激活级别的判断门限。如果一个子公司每天产生的数据小于10GB，可以赋予权值1。对于在20-30GB之间的子公司，则赋予权值3，以此类推。对于用户具有激活级别w_i的用户i，移动数据到DCj将需要支付费用w_ie_ij。

DC权重定义：每一个DC都具有不同的计算和存储资源价格。为了更经济的存储和处理数据，当然优选更低的价格。给定DCj，假定一个VM实例每小时处理数据的价格是a_j。平均来说，这种实例每小时能够分析b_jGB数据。则处理10GB数据的价格是p'_j＝10/b_j*a_j。如果10GB数据的存储费用是p”_j，那么，对于具有激活级别1的用户在DC侧的总费用是p_j＝p'_j+p”_j。对于具有激活级别w_i的用户i，如果它想在DCj存储和处理数据，它需要支付w_ip_j。

具有激活级别w_i的用户的总费用是w_i(p_j+e_ij。考虑到实际环境中e_ij(如几千公里)和p_j(Amazon的每小时几美金)的数量级别上的差异，我们采用标准化后的形式：c_ij＝w_i(p_j'+e_ij')，其中p_j'＝p_j/max_h∈V(p_h)，e_ij'＝e_ij/max_l∈U,h∈V(e_lh)。注意标准化后的边长e_ij'仍然满足三角不等式。

则目标具体可以表述为：

a)公平数据放置(FDP)。最大的用户和被指配到的DC之间的距离极小化，使得每个本地用户可以以最小的时延接入数据：

b)优选数据放置(PDP)。最大的用户和被指配到的DC之间的加权距离极小化，使得具有更多数据的本地用户可以以最小的时延接入数据：如果需要，我们也用w(i,j)＝w_ie_ij来表示加权距离。

c)传输成本最小化数据放置(TCMDP)。传输成本，被定义为所有用户和其被指配到的DC之间的加权距离的和极小化：

d)成本极小化(CMDP)。总成本，被定义为所有用户的成本之和极小化：

因为a)和c)分别是b)和d)的特殊形式，所以后续只给出b)和d)的算法。

优选数据放置(PDP)的算法基本思想

首先介绍几个概念，用于描述算法。

1)瓶颈图:注意到PDP问题的最优解一定在某一个用户加权边达到，所以我们应该从小到大逐一检查加权边，直至所有的约束都满足。瓶颈图的构建正是基于这以思想。m条用户加权边被按照非递减顺序排序，并记做w(1,j)≤w(2,g)≤…≤w(m,h)，其中j,g,h∈V且可能相同。瓶颈图G₁,G₂,…,G_m是G的边子图，且G_r＝(U,V,E_r)(r＝1,2,…,m)，其中E_r＝{e_ij|w_ie_ij≤w(r,g)}。即，G_r由所有G的顶点和不大于第r个最短加权边w(r,g)的边组成。

2)门限图：对于每一个G_r，其对应的门限图T_r在用户集合U上如下构建。对每两个点u,v∈U，边(u,v)在T_r中，当且仅当存在一个DCj∈V且(u,j)和(v,j)都在G_r中。例如，在图2中，边(5，6)不存在，因为在G_m中，用户5，6没有相邻的公共DC。

3)极大团：给定无向图H，H的团是一个完全子图。如果一个团不包含在其它团中，则称之为极大团，记做C(H)。很容易在多项式时间内找到C(H)。本文中用到的简单的方法如下，先将H的任意一个点加入C(H)，然后加入它的邻居点，这些邻居点和已经在C(H)中的所有点能够构成一个完全图。C(H)中所有点的邻居点都被逐一检查，知道没有点可以加入。这样就找到了一个极大团。现在，删除这个极大团的所有点，并在剩余点中重复这个过程，直到H变成空的。这样，就找到了一系列的极大团，且各极大团无交。

注意到，如果用户可以被同一个DC服务，则相应的门限图是一个团。例如，在附图1中，用户6-9可以被共同的DC服务，因此其在T_m中的对应门限图就是附图2中包含6-9的团。在门限图中寻找极大团意味着将用户按照DC的可用性进行分组，其中每一组中的用户都可以用其中一个成员来代表。

4)最大权重优先算法(BWF)

输入G＝(U,V,E)：用户加权非完全二分图；k：正整数

输出D：所选的DC集合

将用户加权边按非递减顺序排序如下：w(1,j)≤w(2,g)≤…≤w(m,h)

对每一个G_r构建对应的门限图T_r。对每一个T_r找其极大团集合。假定有H个团。记对应于T_r的极大团集合是C_r＝C(T_r)_h，其中r＝1,2,…,m，h＝1,…,H

令t＝min{r||C_r|≤k}

For{h＝1,...,H}

{

令l是具有最大权重w_l＝max{w_j|j∈C(T_t)_h，j没有被指配点}。令C(T_t)_h的邻居DC是

e＝min_j∈N{e_lj|e_lj∈G_t}。令v是N中的点，且e_lv＝e。D＝D∪v

}

可以证明，BWF算法给出了PDP问题的一个3-近似解(即得到的解的值不大于最优解的值的3倍)，其中底层的二分图是非完全的。而且这个解是紧的(即不可能有比3更小的近似比)。

当底层图为完全二分图时，可以用独立集代替极大团，算法更快，解质量相同。算法BWF试图将最大规模的数据放置到最近的DC。它按照用户加权边从小到大的顺序逐一检查对应的瓶颈图，并构造对应的门限图。然后找到每个门限图的团集合。每一个团都代表了一组可以至少被一个相同DC服务的用户，且用户和共同DC之间的加权边不大于瓶颈图的最大加权边。所有团集合中团的个数不大于k的团集合下标被选中，以使得最大的用户加权边尽可能的小。当然可以用二分法查找来进一步加快速度。

对于每一个在门限图的团集合C_t中的用户，按照以下方法寻找目标DC。在每一个团中，从具有最大权重的用户开始，我们把它指配到G_t中最近的邻居DC。所有同一个团中的其余用户也被隐式的指配到这个DC。这个过程重复，直到所有C_t中的用户都被指配(for循环)。这样，算法在用户和DC之间建立了一个映射。映射将二分图划分成多个集群，每个集群的中心都是一个DC。

成本极小化数据放置(CMDP)算法基本思想

对CMDP问题，本发明给出了NPA-CMDP算法，它试图将每一个用户指配到最近(即用户和DC之间的成本最小)的DC。如果DC的个数超过了k，则某个DC将被去掉，相应的用户会被重新指配。这个过程重复直到约束满足。

算法2.CMDP最近优先算法(NPA-CMDP)。

输入G＝(U,V,E)：用户加权非完全二分图；k：正整数

输出D：所选的DC集合

将每个用户指配到最近的DC(用户和DC之间的加权距离(成本)定义为w_ie_ij+w_ip_j)。将选择的DC集合记为D

While{|D|>k}

{

在D找到DC，和D中其余DC相比，这个DC和指配到它的用户之间的距加权离是最小的。从D中删除这个DC。

并将原来指配到这个DC的用户重新指配到D中剩余的最近的DC

}

本发明考虑将跨地域分布的大数据移动到云端的可行性，研究了多个目标DC选择问题，用非完全二分图来表示底层设施，从而克服了已有问题都是完全二分图的局限。更加符合实际情况中由于用户偏好，或者是法律限制而导致的并不是每个DC都可用的情况。研究了四种准则，包括。公平数据放置(FDP)，优选数据放置(PDP)，传输成本最小化数据放置(TCMDP)和成本最小化数据放置(CMDP)，实际应用中，可以根据运营商和用户的需求进行选择。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。

Claims (7)

1.一种大数据向云端迁移时的数据中心的选择方法，其特征在于，所述方法包括：

构建底层非完全图，采用激活级别w_i的方式来描述用户的数据产生量，定义公平数据放置FDP、优选数据放置PDP、传输成本最小化数据放置TCMDP和成本最小化数据放置CMDP等四种准则，以及基于上述准则之一进行DC的选择；

其中，所述非完全图G＝(U,V,E)，U代表用户，V代表DC，边长e_ij∈E(i∈U,j∈V)满足三角不等式，正整数k(k≤|U|,k≤|V|)，对于任意i∈U以及j∈V，如果用户i的数据能够被移动到DC_j，则它们之间存在一条边；所述方法旨在从可用的DC集合V中找到一个DC子集D(|D|≤k)来按照不同准则存储U中所有用户的数据；

所述FDP准则为：最大的用户和被指配到的DC之间的距离极小化，使得每个本地用户可以以最小的时延接入数据：

所述PDP准则为：最大的用户和被指配到的DC之间的加权距离极小化，使得具有更多数据的本地用户可以以最小的时延接入数据： ${\min }_{D\⊆V,\left|D\right|\≤k}{\max }_{i\∈U,j\∈D}\left(w_i{e}_{ij}\right);$

所述TCMDP准则为：所有用户和其被指配到的DC之间的加权距离的和极小化： ${\min }_{D\⊆V,\left|D\right|\≤k}\left({\mathrm{\Σ}}_{i\∈U,j\∈D}{w}_i{e}_{ij}\right);$

所述CMDP准则为：所有用户的成本之和极小化：c_ij为具有激活级别w_i的用户的总费用。

2.根据权利要求1所述的方法，其特征在于：所述非完全图为加权非完全图，边长为w_ie_ij，其中w_i为用户具有激活级别，w_ie_ij为移动数据到DC_j将需要支付费用。

3.根据权利要求1所述的方法，其特征在于：所述激活级别w_i根据每天上载的载数据量决定。

4.根据权利要求1所述的方法，其特征在于：对于具有激活级别w_i的用户i，如果它想在DC_j存储和处理数据，它需要支付w_ip_j，其中，p_j＝p'_j+p”_j，p'_j为DC处理单位容量数据的价格，p”_j为DC存储单位容量数据的存储费用。

5.根据权利要求1所述的方法，其特征在于：基于PDP准则进行DC的选择采用最大权重优先BWF算法，所述BWF算法包括如下步骤：

将用户加权边按非递减顺序排序，记做w(1,j)≤w(2,g)≤…≤w(m,h)，其中j,g,h∈V，瓶颈图G₁,G₂,…,G_m是G的边子图，且G_r＝(U,V,E_r)(r＝1,2,…,m)，E_r＝{e_ij|w_ie_ij≤w(r,g)}；

对每一个G_r构建对应的门限图T_r，对每两个点u,v∈U，边(u,v)在T_r中，当且仅当存在一个DCj∈V且(u,j)和(v,j)都在G_r中；

对每一个T_r找其极大团集合，如果一个团不包含在其它团中，则称之为极大团；假定有H个团，记对应于T_r的极大团集合是C_r＝C(T_r)_h，其中r＝1,2,…,m，h＝1,…,H，令t＝min{r||C_r|≤k}

for(h＝1,...,H)

{令l是具有最大权重w_l＝max{w_j|j∈C(T_t)_h，j没有被指配点}；

令C(T_t)_h的邻居DC是e＝min_j∈N{e_lj|e_lj∈G_t}；

令v是N中的点，且e_lv＝e。D＝D∪v}。

6.根据权利要求5所述的方法，其特征在于：当底层图为完全二分图时，用独立集代替极大团，加速BWF算法。

7.根据权利要求1所述的方法，其特征在于：基于CMDP准则进行DC的选择采用CMDP最近优先NPA-CMDP算法，所述NPA-CMDP算法包括如下步骤：

将每个用户指配到最近的DC，用户和DC之间的加权距离定义为w_ie_ij+w_ip_j，将选择的DC集合记为D；

While{|D|>k}

{在D找到DC，和D中其余DC相比，这个DC和指配到它的用户之间的距加权离是最小的；

从D中删除这个DC；

并将原来指配到这个DC的用户重新指配到D中剩余的最近的DC}。