2. Department of Mathematics and Statistics, York University, M3J1P3, Canada
2. Department of Mathematics and Statistics, York University, M3J1P3, Canada
当前,人类社会数据产生模式呈现出高速、大容量的特性.例如,Youtube每天产生近40亿条的视频查看记录以及近43万小时的新视频[1],天文望远镜项目SKA(square kilometer array)每秒产生近40GB的数据量[2].随着社会各行各业数据量的快速增长,其蕴含的巨大潜在价值可以通过大数据挖掘和处理提取利用.数据分析已逐步在各行业发挥着越来越重要的作用,比如金融分析、社交网站、天文望远镜服务等.就社交网站来讲,其可以通过分析网站历史记录(如点击记录、活动记录等)揭示用户使用模式以及潜在的关系,以检测社会热点事件或为其市场决策服务.对于如此大规模数据,将其长时间存储成本巨大,因此,进行高效的、近实时的数据处理必不可少.然而,由于数据呈现出地理分散性、容量巨大性以及结构复杂性等特点,利用普通机器对其进行近实时处理和分析往往不可行.
云计算按照即付即用的模式运行,使得用户能够根据自身所需动态调整租用的资源,并且具有高性能以及高容错特性,为大数据处理提供了一种高效而经济的解决方案.在云计算模式下,如何对数据与云资源进行有效管理,为数据管理者降低数据处理成本至关重要.其中,最为重要的问题是:
(1) 如何动态地将不同位置的实时产生的大规模数据分配至地理分布的数据中心?
(2) 需要在这些数据中心中提供多少计算资源以保证服务质量,同时又最小化运行费用?
由于数据产生的动态性、多源性以及资源价格的动态性,使得上述问题变得极具挑战.
当前,对大数据的研究主要集中在不同类型数据的高速并行处理(如针对批量数据处理的MapReduce[3]框架、针对交互式数据的Spark[4]系统、针对流式数据处理的Dremel[5]系统以及针对图数据的Pregel[6]系统)、大数据分析应用(如个性化推荐[7]、软件分类[8]、基因选择[9])以及大数据处理基础技术[10-14]等方面,但将大规模数据传输到云端并对其数据与资源进行管理的研究很少.目前,为了解决数据迁移问题,常常采用一些简单低效的方法.例如,将数据拷贝至大容量的硬盘中再进行物理运输, 甚至直接将整台机器搬运到数据中心等[15, 16].这些方法不仅会产生不可容忍的数据处理延迟,而且在运输过程中硬盘会毁坏,具有极大的安全隐患.也有实际项目实现了在数据中心之间根据需要自动复制和传送数据[17, 18],但主要聚焦数据的业务需求,未考虑数据处理所需要的资源.
为此,本文对多源大数据云端处理的数据和资源管理问题进行研究,以优化大数据云端处理的成本,提高服务质量.基于此,首先将大数据云端处理的数据迁移和资源供给问题转化为联合随机优化问题;然后,应用李雅普诺夫(Lyapunov)优化技术对模型进行求解并设计相应的在线决策算法.该算法不需要预测系统的未来状态,仅仅基于系统的当前状态做出决定.本文的主要贡献如下:
(1) 提出了一种跨数据中心联合优化数据迁移以及资源供给统一模型,考虑了多数据源数据产生的动态性以及云端不同虚拟机类型及其价格的动态性;
(2) 通过利用李雅普诺夫优化技术解决联合随机优化问题.基于所推导的解析解设计了相应的高效在线决策算法,该算法能够同时做出数据迁移以及资源供给决策并能分布式实现;
(3) 通过理论推导和大量实验对算法性能进行了分析和评估.理论结果表明:该算法可通过调整参数不断趋近于理论最优解,并且能在预设的延迟内完成数据处理任务.实验结果验证了理论分析结果的正确性,并显示了算法的优越性.
本文第1节介绍相关研究工作.第2节对问题进行描述和形式化建模.第3节采用李雅普诺夫优化理论设计在线求解算法.第4节对所提算法的性能进行理论分析.第5节通过大量实验验证算法的有效性和优越性.最后一节对全文进行总结.
1 相关工作目前,利用多数据中心进行数据处理和存储日趋流行.就实际系统来讲,当前已有多个商业公司如Facebook,Google,HP,Cisco开始管理多个地理分布的数据中心,以支持其数据处理业务.为了使Hadoop支持地理分布的数据存储,Facebook开发了一项Prism项目[17],其在Hadoop集群中增加一层抽象逻辑,聚焦于容错与负载均衡.Google以一种分布式方式部署了其数据库系统Spanner[18],使得数据能在多数据中心之间自动迁移.HP[19]与Cisco[20]也在管理其地理分布的数据中心上付诸实践,主要通过优化数据中心之间的数据链路层实现.然而,当前方法受限于其传输依赖,具有复杂性高而弹性 缺失的缺点.
就具体技术来讲,已经有学者研究过将大规模数据集迁移至云中.Cho等人研究了多数据源向单点数据汇传输的问题,采用网络与物理运输结合的方式,当网络带宽不足时,可以将部分数据通过物理运输方式转移.文献[2]研究了延迟截止期内如何寻找最佳传输策略以最小化传输花费的问题,作者将问题建模成网络流图模型,然后基于整数规划算法求解.文献[21]研究的问题背景与文献[22]相同,但将问题目标转换为在花费预算一定的情况下,如何寻找最优决策以最小化延迟.然而,这些研究将物理传输作为数据转移的一种重要方式,无法避免可能带来的数据损坏和安全性问题.另外,所研究的问题属于静态问题(各数据源数据量固定、网络环境稳定以及物理传输链路固定),不同于本文研究的数据以及资源的动态性.文献[23]研究了如何将不同位置动态产生的数据传输至云中的问题,考虑迁移代价、计算以及存储费用,并以最小化花费为目标提出了在线算法.针对可延迟的数据处理,文献[24]在考虑百分比流量收费模型(percentile charge model)的基础上又研究了在保证数据处理截止期的前提下,如何最小化费用的问题.这些工作的共同点在于主要关注数据的迁移,且假设处理中心的资源无限且稳定.不同于这些工作,本文认为数据和数据中心资源都处于动态变化状态,且数据中心资源有限,因此在研究数据迁移的同时还考虑资源动态供给,并且利用优化方法设计在线算法,在保证延迟的前提下,又能最小化费用.
基于资源虚拟化技术,许多学者对云中资源动态供给问题进行了研究.为降低能耗,Liu等人提出了支持虚拟机迁移和虚拟机放置优化的调度策略,且能够实现系统更高的自治程度[25].Petrucci等人考虑了开启和关闭服务器的费用消耗,利用虚拟化技术进行资源整合,并基于此提出了动态调度算法以优化集群能耗[26].为应对突发闪聚请求,文献[27]提出了多媒体云中自适应请求分配和服务能力缩放机制.然而,这些研究往往需要确定的机制来预测未来的工作负载.与此不同,我们采用了李雅普诺夫优化框架,所设计的在线算法不依赖于任何未来数据处理的负载信息.
李雅普诺夫优化技术是近年发展起来的新兴优化技术,其主要思想是将长时间序列内的复杂优化问题转化为单时间序列内的漂移-惩罚最小化问题以获得次优解,其独特的优势就是不需要关于未来的任何信息.文献[28]首次提出应用李雅普诺夫优化技术解决网络的稳定性问题,然后被广泛引入到云计算中以解决系统长时间运行下的优化问题(如负载均衡问题[29, 30]、效能权衡问题[31, 32]、成本优化问题[33]、节能问题[29, 30, 34]、定价问题[35]),从而达到降低运营成本、节省能耗、提高服务质量的目的.Urgaonkar等人首先将此技术应用于云计算中,并利用此方法以解决虚拟化数据中心的请求准许和动态资源分配问题[29].Yao等人利用此技术优化分布式数据中心的负载分配以及计算资源的供给问题,以减小数据中心的用电消耗[34],而且将传统李雅普诺夫模型由单时间尺度拓展至双时间尺度.Wu等人将此技术应用于云视频流服务中的请求分配与计算资源缩放问题,在降低运营成本的同时,保证用户请求的低延迟响应[31].Zhao等人考虑到云中多数据中心常常需要根据用户需求和资源状态提供动态定价的机制以最大化其利润,利用此技术解决云资源的动态定价问题[35].Zhu等人通过建立效用与能耗模型,以权衡系统效用与能耗为目标,利用此方法动态决定各数据中心的虚拟机开启量以及请求准入量以解决效用与能耗的权衡问题[32].Niu等人针对大型网站存在的请求闪聚问题提出利用私有云和公有云的混合策略,在负载大时,通过租借公有云的资源满足用户需求,并通过李雅普诺夫技术解决如何根据负载变化动态地向公有云租借合适的资源以应对请求闪聚问题[33].考虑到不同区域碳排放标准以及速率的不同,文献[30]通过此优化方法对负载分配、数据中心容量缩放以及CPU速率调整问题同时进行决策,在降低能耗的同时,保证碳排放量满足当地要求.这些工作之所以取得很好的效果,主要在于李雅普诺夫优化框架具有对未知状态不敏感的特性.然而,这些工作采用传统的李雅普诺夫框架,主要在目标函数和惩罚函数之间进行权衡,在任务处理时效性上表现出一种尽力而为的特性,因而算法不能保证特定的处理延时.不同于以上研究,本文聚焦的是多源大数据云端实时处理的数据迁移和资源管理优化问题.据我们所知,还尚未有利用李雅普诺夫解决大数据云中处理相关问题的文献.而且,通过引入延迟容忍队列设计在线算法,使得数据能在预设的延迟内完成,从而保证数据处理的实效性.
总之,与已有研究相比,本文创新性表现在以下方面:
1) 面向动态多源大数据云端近实时、高效、低成本处理,在考虑数据动态、资源价格动态以及延迟保证的情况下,以最小化带宽费用、存储费用、计算费用以及延迟费用为目标,对其中的动态数据迁移和资源供给的问题,建模成长时间运行的联合随机整数优化问题,设计了可分布式执行的在线算法;
2) 采用李雅普诺夫框架解决长时间内数据迁移和资源供给联合优化问题,其不需要对未来数据量进行预测,这与需要特定预测机制的传统方法(如文献[22-24])有显著不同.利用此方法,虽然数学形式复杂,但最终决策时能够获得解析解,保证系统具有实时性.理论分析显示:该算法在提高求解效率的同时,可无限趋近于线下最优解;
3) 本文通过引入延迟容忍队列,保证了数据在特定的延迟内完成处理,克服了大多数基于李雅普诺夫的工作对延迟仅仅尽力而为的缺点.
2 问题建模本节首先对问题进行了描述,然后将问题形式化为数学优化模型.
2.1 问题描述本文所考虑的系统架构如图 1所示:数据管理者(例如社交网站Facebook)管理着多个分布在各地的不断产生海量数据的数据节点,为充分挖掘数据的价值,管理者需将这些地理分散的数据进行实时处理.为避免大量建设基础设施所需的成本,数据管理者通过租用公有云资源(如Amazon EC2) 处理数据,然后将数据处理结果形成各种应用向用户提供服务(如热点事件监测、用户行为分析、广告投放等).
具体来讲,数据管理者将数据源与数据中心相连并将数据分析应用部署在云端.各数据源一旦产生数据,就被迁移到相应的数据中心并进行处理.各数据中心采用分布式的处理模型(如MapReduce)进行数据处理,因而所租用的每个虚拟机就可当做MapReduce中的一个节点.在此背景下,数据管理者面临的问题是:如何决策各数据源到各数据中心的大规模数据迁移以及在各数据中心租用多少量的虚拟机资源,从而在保证数据高效处理的同时最小化系统总成本.显然,由于数据的动态性、资源价格在不同数据中心的异构性以及各链路带宽资源以及各数据中心负载的波动性,采用简单的规则(如将数据仅迁移至最近的数据中心或迁移至价格最小的数据中心)往往不是最优的决策(对比实验部分会验证).针对此问题,本文致力于在优化系统长时间运行下,数据处理和资源供给在各数据中心的安排.在系统运行过程中,数据管理者监视着数据中心的状态(比如虚拟机的价格、数据中心的负载状态、网络状态),并以此为知识,决定转移到每个数据中心的数据量以及从每个数据中心租用的资源量,从而达到运行成本最小化的目的.最后,数据中心在数据运行和分析后,将分析结果形成大数据应用向用户提供服务.
形式化地,本问题考虑地理分布的数据中心集合D,其总数为D=|D|,取值为d(1≤d≤D).各数据中心配置有不同类型的虚拟机K(具有大小K=|K|),每类虚拟机有不同的CPU和内存配置,并设k类虚拟机的能力为vk,表示该类虚拟机处理数据的速率.数据处理速度与MapReduce具体应用有关,不同的数据处理具有不同的速率.数据管理者管理着R=|R|个数据源(表示为集合R),且各数据源(取值为r,1≤r≤R)动态产生需要处理的数据.为此,任何数据源的数据可通过虚拟专用网(virtual private network,简称VPN)移动到其所租用的数据中心来进行分析.为模拟真实场景,我们假设从数据源r到数据中心d上的VPN连接(r,d)的带宽Brd是有限的,并且是系统瓶颈之一.此外,每个地理位置生成的数据量是独立的,每个数据中心的资源价格(例如虚拟机、存储)是不同的,并且随时间变化.
该系统依照时间序列运行,划分为t=0,1,…,T.在每个时间序列中,数据管理者需要决定从数据源r移动多少数据到数据中心d以及每个数据中心租用多少资源来支持数据处理.所优化的目标为最小化云端对大数据分析的总成本,并且能够保证在长时间运行中数据处理的延迟.为了便于参考,一些重要的符号在表 1中列出.
2.2 问题形式化
本节首先公式化系统所需的费用,然后对所优化的问题进行数据建模.
如前所述,系统以时隙方式运行,不同数据源、不同时隙的数据动态地生成.设ar(t)为t时刻数据源r生成的数据量.由于从任意数据源生成的数据可移动到任意数据中心进行处理,我们设
${{a}_{r}}(t)\le A_{r}^{\max },\forall r,t\in [1,T]$ | (1) |
${{a}_{r}}(t)=\sum\limits_{d\in \mathcal{D}}{\lambda _{r}^{d}(t)},\forall r,t\in [1,T]$ | (2) |
数据管理者的目标是:通过优化分配给不同数据中心的数据量和数据中心所需的资源,以使系统中产生的总成本最小化.基于此,本文主要考虑以下成本要素:带宽成本、延迟成本、储存成本和计算成本,各成本详细定义如下:
(1) 一般情况下,由于不同VPN属于不同的互联网服务提供商,其带宽价格各不相同.令
${{C}_{b}}(t)\triangleq \sum\limits_{d\in \mathcal{D}}{\sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d}(t)\cdot b_{r}^{d}}}$ | (3) |
(2) 由于数据规模的庞大,数据的存储成本也是影响数据中心选择的重要因素之一.令sd为单时隙内数据中心d∈D上储存1GB数据所需要的成本,则t时刻系统产生的储存总成本为
${{C}_{s}}(t)\triangleq \sum\limits_{d\in \mathcal{D}}{\sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d}(t)\cdot {{s}_{d}}}}$ | (4) |
(3) 由于各云服务提供商通常采用动态定价机制,虚拟机价格往往随着时间不断变化(如Amazon EC2虚拟机实例),因而,从数据中心租用的虚拟机数量对系统的总成本和服务质量有重要影响.令
${{C}_{p}}(t)\triangleq \sum\limits_{d\in \mathcal{D}}{\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t)\cdot p_{d}^{k}(t)}}$ | (5) |
(4) 考虑到数据源与数据中心分布在不同地理位置,本文将延迟作为数据处理需要考虑的重要性能指标,数据迁移时要尽可能减小延迟造成的影响.由于数据传输的距离较长且传输量很大,本文主要考虑传输数据到数据中心所造成的延迟.令
${{C}_{l}}(t)\triangleq \sum\limits_{d\in \mathcal{D}}{\sum\limits_{r\in \mathcal{R}}{\alpha \cdot \lambda _{r}^{d}(t)\cdot L_{r}^{d}}}$ | (6) |
其中,a是将延迟转换为经济成本的权重系数.基于以上的成本公式,可以导出系统中产生的总成本为
$C\left( t \right)={{C}_{p}}\left( t \right)+{{C}_{s}}\left( t \right)+{{C}_{b}}\left( t \right)+{{C}_{l}}\left( t \right)$ | (7) |
基于以上各费用成本的定义,根据本文所研究的目标,最小化时间段[0,T]内数据迁移和处理的时间平均成本可以形式化为
$P1.\min :\underset{T\to \infty }{\mathop{\lim }}\,\frac{1}{T}\sum\limits_{t=1}^{T-1}{\mathbb{E}\{C(t)\}}$ | (8) |
$\text{s}\text{.t}\text{. }{{a}_{r}}(t)\le A_{r}^{\max },\forall r,t\in [1,T]$ | (9) |
$\text{ }{{a}_{r}}(t)=\sum\limits_{d\in \mathcal{D}}{\lambda _{r}^{d}(t)},\forall r,t\in [1,T]$ | (10) |
$0\le n_{d}^{k}(t)\le N_{d}^{k,\max },\forall d,\forall k,t\in [1,T]$ | (11) |
$n_{d}^{k}(t)\in {{Z}^{+}}\cup 0,\forall d,\forall k,t\in [1,T]$ | (12) |
其中,约束(10) 是为了确保在单时隙内分配给各数据中心数据的总和等于在该时刻产生的总数据量,约束(11) 确保了所需的虚拟机数量不超过数据中心可以提供的范围.从问题P1表达来看,由于数据生成是未知且动态的,资源变量
本节利用李雅普诺夫优化理论来设计在线控制算法.该方法的突出特点是不需要有关未来负载的任何信息,通过贪婪地最小化在每个时间序列中的漂移惩罚,理论上可得到一个任意接近线下最优解的次优方案.根据标准的李雅普诺夫优化框架理论[36],我们首先将问题P1变换为最小化李雅普诺夫漂移惩罚项的优化问题,然后设计相应的在线算法.
1) 问题转换.
令Hd(t)为t时间序列上数据中心d中未处理的数据量.首先,我们定义Hd(t)=0,则队列Hd(t)的演化可以描述如下:
${{H}_{d}}(t+1)=\max \left[ {{H}_{d}}(t)-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t)\cdot {{v}_{k}}},0 \right]+\sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d}(t)}$ | (13) |
上述队列的更新规则意味着所处理的数据量为
${{Z}_{d}}(t+1)=\max \left[ {{Z}_{d}}(t)+{{1}_{{{H}_{d}}(t)>0}}\left( {{\varepsilon }_{d}}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t)\cdot {{v}_{k}}} \right)-{{1}_{{{H}_{d}}(t)=0}}\sum\limits_{k\in \mathcal{K}}{N_{d}^{k,\max }\cdot {{v}_{k}}},0 \right]$ | (14) |
其中,指示函数
令Z(t)=(Zd(t)),H(t)=(Hd(t)),∀d∈D分别表示虚拟队列和实际队列的矩阵,可以用Q(t)=[H(t),Z(t)]来表示实
际队列和虚拟队列的联合矩阵.据李雅普诺夫框架[36],我们定义李雅普诺夫函数如下:
$L(\Theta (t))=\frac{1}{2}\sum\limits_{d\in \mathcal{D}}{\{{{Z}_{d}}{{(t)}^{2}}+{{H}_{d}}{{(t)}^{2}}\}}$ | (15) |
其中,L(Q(t))为系统中负载积压的度量,则单时隙的李雅普诺夫漂移函数则可定义为
$\mathsf{\Delta }(\mathsf{\Theta }\left( t \right))=\mathbb{E}\{L(\mathsf{\Theta }\left( t+1 \right))-L(\mathsf{\Theta }\left( t \right))|\mathsf{\Theta }\left( t \right)\}$ | (16) |
为在保证系统队列稳定的同时还最小化系统所产生的花费,则李雅普诺夫漂移-惩罚项可以在公式(16) 漂移函数中增加系统总成本函数获得,即:
$\mathsf{\Delta }(\mathsf{\Theta }\left( t \right))+V\cdot \mathbb{E}\{C\left( t \right)|\mathsf{\Theta }\left( t \right)\}$ | (17) |
其中,V为非负参数,它可以在系统稳定性和成本之间进行折衷.V越大,系统产生的成本就越小;反之,成本就越大.因此,原来的问题P1就变成了下面的问题P2:
$\bf{P2}.\rm{min }\left( 17 \right)$ | (18) |
$\text{s}\text{.t}\text{. }\!\!~\!\!\text{ }\left( \text{9} \right)\left( \text{10} \right)\left( \text{11} \right)\left( \text{12} \right)$ | (19) |
为了解决P2,本文不直接最小化漂移-惩罚函数,而是致力于最小化它的上界.然而,理论证明,此方式并不破坏算法的最优性和性能[36].因此,求解P2的关键是找到其上界.通过理论推导可证明,公式(17) 的界为:
$\begin{align} & \Delta (\Theta (t))+V\cdot \mathbb{E}\left\{ \left. \underset{T\to \infty }{\mathop{\lim }}\,\frac{1}{T}\sum\limits_{t=1}^{T-1}{C(t)} \right|\Theta (t) \right\}\le B+\mathbb{E}\left\{ \left. \sum\limits_{d\in \mathcal{D}}{\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t)}}\cdot (Vp_{d}^{k}(t)-H_{d}^{k}(t){{v}_{k}}-Z_{d}^{k}(t){{v}_{k}}) \right|\Theta (t) \right\}+ \\ & \text{ }\mathbb{E}\left\{ \left. \sum\limits_{d\in \mathcal{D}}{\sum\limits_{r\in \mathcal{R}}{\lambda _{d}^{r}(t)}}\cdot (V{{s}_{d}}+Vb_{r}^{d}+VL_{r}^{d}+{{H}_{d}}(t)) \right|\Theta (t) \right\} \\ \end{align}$ | (20) |
其中,
2) 在线算法的设计.
通过仔细研究不等式(20) 的右边,发现该优化问题可以等价地分解成两个子问题,即数据分配问题和资源供应问题.求解以上两个子问题的细节如下所述.
(1) 数据迁移
为最小化公式(20) 的右边,通过观察变量之间的关系,其中与数据分配相关的部分可被提取为
$\min \text{ }\mathbb{E}\left\{ \left. \sum\limits_{d\in \mathcal{D}}{\sum\limits_{r\in \mathcal{R}}{\lambda _{d}^{r}(t)}}\cdot (V{{s}_{d}}+Vb_{r}^{d}+V\alpha L_{r}^{d}+{{H}_{d}}(t)) \right|\Theta (t) \right\}$ | (21) |
此外,由于各数据源的数据是独立生成的,公式(21) 所述的多数据源整体优化方式可以分别在各数据源独立执行.考虑t时刻数据源r上数据分配,则问题转化为解决如下问题:
$\begin{align} & \min \text{ }\sum\limits_{d\in \mathcal{D}}{\lambda _{d}^{r}(t)}[V{{s}_{d}}+Vb_{r}^{d}+V\alpha L_{r}^{d}+{{H}_{d}}(t)] \\ & \text{s}\text{.t}\text{. }(9)(10) \\ \end{align}$ | (22) |
事实上,上述问题是一个广义的最小权重问题,从数据源r迁移到数据中心d的权重为
$\lambda _{r}^{d}(t)=\left\{ \begin{array}{*{35}{l}} {{a}_{r}}(t),\text{ }d={{d}^{*}} \\ 0,\text{ else} \\ \end{array} \right.$ | (23) |
其中,
(2) 资源配置
若去掉公式(20) 右边的常数项B,则与变量
过解决如下问题得到虚拟机最优供应策略:
$\begin{align} & \min \text{ }\mathbb{E}\left\{ \left. \sum\limits_{d\in \mathcal{D}}{\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t)}}\cdot (Vp_{d}^{k}(t)-{{H}_{d}}(t){{v}_{k}}-{{Z}_{d}}(t){{v}_{k}}) \right|\Theta (t) \right\} \\ & \text{s}\text{.t}\text{. }(11)(12) \\ \end{align}$ | (24) |
同理,由于各数据中心中的资源供给是独立的,与数据分配问题相似,公式(23) 可以在每个数据中心间分布地求解.因而对于单个数据中心d,资源供应问题可以进一步改写为
$\begin{align} & \min \text{ }\mathbb{E}\left\{ \left. \sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t)}\cdot (Vp_{d}^{k}(t)-{{H}_{d}}(t){{v}_{k}}-{{Z}_{d}}(t){{v}_{k}}) \right|\Theta (t) \right\} \\ & \text{s}\text{.t}\text{. }(11)(12) \\ \end{align}$ | (25) |
易得上述线性问题的解为
$n_{d}^{k}(t)=\left\{ \begin{array}{*{35}{l}} N_{d}^{k,\max },\text{ if }{{H}_{d}}(t)+{{Z}_{d}}(t)>\frac{Vp_{d}^{k}(t)}{{{v}_{k}}} \\ 0,\text{ if }{{H}_{d}}(t)+{{Z}_{d}}(t)\le \frac{Vp_{d}^{k}(t)}{{{v}_{k}}} \\ \end{array} \right.$ | (26) |
上述解决方案表明:当t时刻k类虚拟机的价格
至此,通过利用李雅普诺夫框架对原问题进行转化,长时间内数据迁移和资源供给的成本最小化问题得到有效求解.以上简单解决方案有助于在真实系统中在线部署所提算法,其在线算法的细节见算法1.
算法1. 在线算法程序.
1 Input:
2
3 Output:
4
5 资源供给:
6 for each数据中心d∈D,虚拟机类型k∈K do
7 通过应用公式(26) 解决问题(24) 得到虚拟机供给策略
8 数据分配:
9 for each数据源r∈R,数据中心d∈D do
10 通过应用公式(23) 解决问题(21) 得到数据分配策略(
11 根据队列动态等式(13) 、等式(14) 分别更新队列Hd(t),Zd(t).
4 算法性能分析本节从成本最优性、队列负载上界、数据处理最差延迟及算法复杂度方面对算法1进行了理论分析.
定理1(成本最优). 假设数据生成的速率ar(t),∀r∈R在任意时刻是独立同分布的,对于任意控制参数V>0,所提算法产生的系统费用与最优解产生的费用关系为
$\underset{T\to \infty }{\mathop{\lim \sup }}\,\frac{1}{T}\sum\limits_{t=0}^{T-1}{\mathbb{E}\{C(t)\}}\le {{C}^{*}}+\frac{B}{V}$ | (27) |
其中,C*表示平均时间成本的下确界,代表着理论上最佳方案所得费用;常数B与公式(20) 中的定义相同.证明请见附录B.
该定理表明,本文算法获得的时间平均成本与线下得到的最优成本的差呈现O(1/V)的关系.特别地,通过控制变量V,时间平均成本C可以任意地接近最优解C*.
定理2(队列负载上界). 假设ed满足
$Z_{d}^{\max }=\frac{Vp_{d}^{\max }}{{{v}_{\min }}}+{{\varepsilon }_{d}}$ | (28) |
$H_{d}^{\max }=\frac{Vp_{d}^{\max }}{{{v}_{\min }}}+\sum\limits_{r\in \mathcal{R}}{A_{\max }^{r}}$ | (29) |
其中,
此定理说明,队列的负载大小呈现出O(V)关系.这意味着:为保持队列负载的稳定性,应该选择较小的V.然而,当减小参数V,又会导致成本的增大(见公式(26) ),因此,系统成本和稳定性具有[O(1/V),O(V)]的折衷关系.在实际应用中,在给定成本预算情况下,我们可以选择合适的V以使系统的稳定性最大化;反之亦然.
定理3(最差情况延迟). 假设系统以先到先出的机制运行,那么队列d中数据运行的最差延迟为
$l=[H_{d}^{\max }+Z_{d}^{\max }/{{\varepsilon }_{d}}]$ | (30) |
其中,[x]表示在那些大于或等于x的数中最小的数.
此定理说明:无论数据任何时间到达队列Hd,都可以在l个时隙内处理完成.这表明本文所提算法能够保证
数据处理的服务质量.此外,在给定系统参数的情况下,由于
定理4(算法复杂度). 若假设系统中包含的数据源个数、数据中心个数和虚拟机类型数分别为R,D,K,则算法1的复杂度为O(DxK+DxR+D).
证明:算法1主要由3部分组成:资源配置问题求解部分、数据迁移求解部分和队列更新部分.据算法1易
得,资源配置问题部分算法复杂度为O(DxK),数据迁移部分算法复杂度为O(DxR)以及队列更新部分算法复杂度为O(D).因此,算法1的总复杂度是O(DxK+DxR+D).
5 实验及结果分析本节利用真实数据集对本文所提算法的有效性进行评估.
5.1 数据集描述鉴于大规模数据分析对全球性大规模网站(例如Google,Youtube,Facebook等)市场决策来说越来越重要,我们采用1998年世界杯网站真实数据集Worldcup98[38]和Youtube网站记录数据集[39]来评估本文算法性能.
1998年世界杯网站在地理分布的4个位置部署30台服务器(巴黎的4台服务器、赫恩登的10台服务器、普莱诺的10台服务器以及圣克拉拉的6台服务器)为全球用户提供服务,Worldcup98数据集记录了该网站从4月30日~7月26日的用户访问数据,每次访问的记录都存储在处理请求的服务器上,期间总共产生大约有10亿条记录.每条记录包含的详细信息如请求时间、用户ID、请求内容以及处理请求的服务器ID.我们提取了6月21~27日共一周的数据进行实验.为仿真大规模的网站,我们将原始的网站请求量扩大1 000倍.每隔30分钟对请数进行汇总,并假设每次请求的记录内容为100KB,则可得如图 2所示的数据变化图.图中的尖峰部分为晚间比赛阶段;而白天网站访问量则较小,整体呈现出周期变化模式.
Youtube数据集收集了马萨诸塞大学各分区校园的Youtube访问数据,记录内容包含访问时间、用户IP、访问的Youtube服务器、访问内容、内容服务器等信息.本文选取2008年1月1日和1月31日共两天的数据.数据集中有3个Youtube服务器IP,因此,我们设置数据源数量为3,其他设置与以上相同.图 3为其数据变化情况.
5.2 实验设置
在实验中,针对Worldcup98数据集,假设模型包含4个数据源(与Worldcup98数据集中的4个数据位置,即位于美国的圣克拉拉、普莱诺、赫恩登以及位于法国的巴黎对应),针对Youtube数据集,由于数据集只包含3个服务器IP,假设模型包含3个数据源.其他共同设置如下:12个数据中心(与亚马逊在欧洲和美洲的服务器,即阿什本、达拉斯、洛杉矶、迈阿密、纽瓦克、帕洛阿尔托、西雅图、圣路易斯、阿姆斯特丹、都伯林、法兰克福以及伦敦相对应)[40].虚拟机方面,考虑Amazon EC2所提供的5种类型的虚拟机实例(即c3.large,c3.xlarge,c3.2xlarge,c3.4xlarge,c3.8xlarge).数据中心与数据源之间的距离通过在线工具[41]获得,其距离矩阵图详见后文图 6所示.
为更好发挥模型性能,我们建议模型的一些参数设置如下:与文献[23]相同,采用RTT(round trip time)测度测量数据源与数据中心的链路延迟,即RTT(ms)=0.02xdistance(km)+5.虚拟机价格与存储价格分别采用亚马逊Spot instance价格和S3的价格(可以从其网站获取),而通过链路<r,d>上传数据的单位价格服从[0.1,0.25]美元/ GB的均匀分布.对于某一具体应用来说(如MapReduce应用为分年龄段统计每时段用户访问数),由于Map与Reduce过程相对固定,数据在不同类型的虚拟机中的处理速度也相对稳定,可设其对应的单位核数据处理速率为100MB/slot(即c3.large,c3.xlarge,c3.2xlarge,c3.4xlarge,c3.8xlarge的处理速度分别为100MB/slot,200MB/slot,400MB/slot,800MB/slot,1600MB/slot).为简单起见,设置数据迁移代价为与数据相关的线性函数.除非特别指出,其他参数默认设置为V=20,a=0.01,ed=1.
基于所提算法及以上参数设置,在Matlab中实现并进行仿真实验.以Worldcup98和Youtube数据集每时刻放大的数据量作为输入,通过所提算法均衡计算成本、存储成本、带宽成本以及延迟成本,做出数据迁移决策以及虚拟机资源的租赁决策,即:根据各个数据源每时刻产生的数据决定每时刻往各个数据中心迁移多少,并提供合适量的不同能力大小的虚拟机数.以此按时隙运行,则产生了一段时间内处理该数据的数据迁移决策和资源供给(购买)决策,从而使得整个时间内的总成本最小.实验均在配置为Intel i3-3240 CPU,4G RAM的戴尔PC机上进行.为方便读者更深入研究或工程化,本文提供了实验源代码(https://www.researchgate.net/publication/308721003_Cost-aware_Multi-source_Big_Data_Processing_on_Clouds_using_Lyapunov_Technique)作为参考.
5.3 算法的有效性为验证算法的有效性,本节主要在参数固定情况下,利用Worldcup98数据集进行了实验.图 4显示了系统总花费随时间的变化情况,从图 4可知,总花费随着数据量的大小而变化(可参考图 2的数据变化).这说明本文算法能够在没有预测未来负载的情况下自适应动态地调整虚拟机的供给量,以满足不断变化的数据处理需求.图 5显示了各种虚拟机(即c3.large,c3.xlarge,c3.2xlarge,c3.4xlarge以及c3.8xlarge)费用比随时间变化的对比情况,结果显示:虚拟机性能越强,其花费更高.这是因为我们采取了价格策略为:性能越强的虚拟机单位计算能力价格越低,因此性能越强的虚拟机性价比越高,从而算法会优先选择性能越强的虚拟机(如c3.8xlarge)进行数据处理.并且在数据处理量比较小的情况下(如时隙120~140,150~170,200~230等),性能较大的虚拟机比例会更高.这是因为此时各类型的虚拟机资源充足,性价比高的大容量虚拟机则会优先选择.然而在负载较大情况下,由于资源的缺乏,会租用单位价格高的低性能虚拟机进行补充.
更进一步地,为深入剖析算法的特性,对数据分配详细结果进行了展示.结合图 6和图 7可知:本文算法结果表现出数据本地化的特性,因为数据倾向于转移至数据源附近的数据中心处理.
特别地,巴黎产生的数据较少转移至北美的数据中心(即阿什本、达拉斯、洛杉矶、迈阿密、纽瓦克、帕洛阿尔托、西雅图、圣路易斯)进行处理,即使北美的价格比欧洲的价格要低.这意味着算法具有避免过大延迟,从而保证数据按时处理的能力.
5.4 参数对性能的影响本节在Worldcup98数据集上通过实验分析了参数V对算法性能的影响.图 8显示了平均花费与队列长度随着参数V的变化情况,从图可知:系统产生的时间平均花费随着V的递增而降低;并且当V足够大时,系统平均费用趋近于稳定最小值.这一结果为我们在部署真实系统时降低费用提供了理论指导.然而随着V的增长,负载队列长度也随之增长,队列的增长又会导致数据处理的时延.因此,如何选择合适的V以平衡系统总费用以及延迟非常重要.另外,本实验结果还与算法的理论分析结果一致,因而验证了定理1推导的正确性.图 9显示了参数e对平均花费和队列长度的影响,系统产生的费用随着参数e的增大而增大,队列负载呈现出不断递减的趋势.这可能是因为随着e的不断增大,延迟l不断减小,因而需要租用更多的资源以更快地进行数据处理,这必然导致系统费用的增加.同理,随着资源的增加,队列负载也会不断减小以降低延迟.
图 10和图 11显示了传输延迟代价转换因子a对性能的影响,随着a的增大,平均花费不断递增,而队列负载不断降低.这是因为a增大,意味系统对延迟更敏感,反过来算法能够调整数据迁移以及资源分配使得队列延迟减小.图 11说明增加a基本不影响其他类型花费,进一步说明算法能够优化决策从而最小化各类花费.因而选择这一参数时只要给定了费用的上限,则可以选择合适的参数a.事实上,由于系统中通常会考虑多目标(比如花费、队列延迟),以上参数仅是权衡各目标的因子,因此在确定某一目标的情况下,则可选择合适的参数使得各目标能够权衡.通常,我们选择曲线交汇点为权衡点,如图 7中V=20、图 8中e=4以及图 9中a=0.02.
5.5 对比实验
本节将本文算法与其他算法进行对比,包括文献[23]中的OLM算法以及一些传统算法.OLM算法为文献[2]设计的启发式策略在线算法,由于本文未考虑数据中心间迁移的费用,为公平起见,我们将OLM算法产生总费用减去数据中心间数据迁移费用作为比较对象.其他算法由不同的数据分配策略以及资源供给策略组合而成.在数据分配部分,主要考虑3种代表性策略:
1) 就近分配原则(proximity-aware data allocation,简称PDA),将各数据源产生的数据分配至离其最近的数据中心中.显然,此策略具有最小的延迟,适合对于延迟敏感的场景;
2) 负载均衡分配原则(load balancing data allocation,简称LBDA),将数据分配至具有最小负载的数据中心.此策略能够保持各数据中心的负载均衡;
3) 价格最低分配原则(minimal price data allocation),将数据分配至当前时刻资源价格最低的数据中心,以降低费用.
至于资源供给部分,主要考虑了两种简单策略:
1) 启发式策略(heuristic vm provisioning,简称HVP),此策略基于历史时刻的资源需求决定当前时刻虚拟机资源供给量.为应对负载的波动性强的问题,我们在前一时刻所需要的资源量上增加50%作为当前时刻的资源需求量;
2) 固定式策略(stable VM provisioning,简称SVP),即,每种类型虚拟机保持固定供给量.为便于比较,我们将这一固定值设置为本文算法所得结果的平均值.显然,此策略在T时刻内的总量与本文算法所供给的总量相等.
另外,将以上各策略进行组合,可形成以下的不同方案:本文算法、OLM、SVP+PDA、SVP+LBDA、SVP+ MPDA、HVP+PDA、HVP+LBDA、HVP+MPDA.本文在Worldcup数据集和Youtube数据集上进行了对比.
(a) Worldcup数据集.
图 12展现了不同方案的时间平均费用对比,仔细分析该图,可得出以下结论:
1) 除了方案SVP+PDA之外,本文算法比其他算法在费用上都更优.因为这种方案将数据分配至距数据源最近的数据中心进行处理,必然导致最小的延迟费用.然而,由于方案SVP+PDA所对应的队列负载随着时间递增而递增(如图 13所示),意味着不能保证系统的长时间运行,因此从实际情况来讲,方案SVP+PDA是不可行的.又如第5.3节所分析,本文算法具有保持数据本地化的特性.因此,考虑到以上结果,本文算法能够在数据本地化以及系统稳定性之间进行平衡;
2) 资源供给量相同情况下(如SVP),LBDA数据分配策略产生了最高的花费.我们认为:这主要是因为在负载均衡的数据分配策略情况下,数据分配至各数据中心是均等的,因而不计成本地远距离迁移数据.例如,从美国迁移大规模数据至巴黎,必然导致高昂的延迟代价以及计算费用.值得注意的是,文献[23]算法OLM费用高于本文算法甚至简单资源供给策略SVP.这是因为算法OLM未考虑资源供给策略,对所有的数据按需及时处理(每时刻到达数据不累积至下一时刻),而其他算法则允许一定的队列延迟,因而OLM侧重时效性更强的应用.
结合图 7中结论,本文算法能够通过调节参数V以适应不同的队列延迟,能够适应不同时效性的应用,因此相比OLM灵活性更强.
图 13展示了各方案长时间运行的队列变化情况.显然,在长时间运行后,本文算法与方案OLM,HVP+PDA,HVP+LBDA,HVP+MPDA都能保持稳定.然而,其他策略的队列长度随着时间的增长而增长,长时间后必然导致系统的瘫痪.又注意到:SVP资源供给策略与本文策略所供给的资源量是相同的,却比本文算法产生更高的费用以及更低的系统稳定性,因此,本文算法能够在数据分配和资源供给决策之间进行优化以降低总体费用并提高系统稳定性.如前文所述,HVP所供给的虚拟机资源量是在前一个时隙所需的基础上增加额外50%.尽管利用了这些策略能够保持很好的稳定性,但却以增加过高的费用为代价.而算法OLM平均队列负载为0,这是因为该算法采用按需供给虚拟机资源,在每时刻都能将达到的数据处理完毕.
(b) Youtube数据集.
图 14和图 15展示了不同算法在Youtube数据集上的对比,对比结果与数据集Worldcup相似,说明本文算法能够适应不同数据集,更进一步证明了算法的有效性.
5.6 算法实时性
为验证算法的实时性,本文在实验中记录每次算法CPU运行时间.通过算法1可知,算法的运行时间主要与问题规模(即数据源数R、数据中心数D以及虚拟机类型数K)有关.实验中对不同问题规模进行了记录,所得运行时间见表 2.
实验结果表明,算法能在毫秒级的时间内运行完成.尽管在实际系统中情况会有所不同,但算法的在线实现是可期的.另外,通过问题规模各参数的变化情况可知,算法的复杂度主要由数据中心D决定,这与上文的算法复杂度分析结果相一致.
6 结 论随着地理分散的数据源源不断产生并需要处理,采用跨区域、分布式数据中心进行大数据处理已经成为许多公司和机构关注的解决方案.如何高效地对此模式下的数据与资源进行管理成为亟待解决的问题.为此,本文设计了一种面向云端大数据处理、集数据迁移和资源供给为一体的成本最小化理论框架.通过平衡跨数据中心数据处理产生的带宽费用、存储费用、计算费用以及延迟费用等4种费用,该文将成本最优化问题建模成联合的随机整数优化问题.通过利用李雅普诺夫优化理论,我们将原问题转化为两个可在线解决的子问题,每个子问题又恰好对应数据分配和资源供给问题.理论分析表明:该算法能够达到较低的费用,并确保数据处理在一定的时间序列内完成.通过大量的实验,进一步验证了该算法的有效性以及相比其他典型算法的优越性.
附录A:漂移惩罚上界推导证明:根据(max[x-y,0]+z)2≤x2+y2+z2+x(z-y),对向量Q(t)=[Z(t),H(t)]则有:
$\begin{align} & {{Z}_{d}}{{(t+1)}^{2}}-{{Z}_{d}}{{(t)}^{2}}\le \left\{ {{1}_{(H(t)>0)}}\left( {{\varepsilon }_{d}}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t){{v}_{k}}} \right)-{{1}_{(H(t)=0)}}\sum\limits_{k\in \mathcal{K}}{n_{d}^{k,\max }{{v}_{k}}} \right\}+ \\ & \text{ }2{{Z}_{d}}(t)\left\{ {{1}_{(H(t)>0)}}\left( {{\varepsilon }_{d}}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t){{v}_{k}}} \right)-{{1}_{(H(t)=0)}}\sum\limits_{k\in \mathcal{K}}{n_{d}^{k,\max }{{v}_{k}}} \right\} \\ & \text{ }\le {{({{\varepsilon }_{d}})}^{2}}+{{\left( \sum\limits_{k\in \mathcal{K}}{n_{d}^{k,\max }{{v}_{k}}} \right)}^{2}}+2{{Z}_{d}}(t)\left( {{\varepsilon }_{d}}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t){{v}_{k}}} \right) \\ \end{align}$ | (A.1) |
${{H}_{d}}{{(t+1)}^{2}}-{{H}_{d}}{{(t)}^{2}}\le {{\left( \sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t){{v}_{k}}} \right)}^{2}}+{{\left( \sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d}(t)} \right)}^{2}}+2{{H}_{d}}(t)\left( \sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d}(t)}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t){{v}_{k}}} \right)$ | (A.2) |
由于
$\begin{align} & \Delta (\Theta (t))=\frac{1}{2}\sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{H}_{d}}{{(t+1)}^{2}}-{{H}_{d}}{{(t)}^{2}}|\Theta (t)\}}+\frac{1}{2}\sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{Z}_{d}}{{(t+1)}^{2}}-{{Z}_{d}}{{(t)}^{2}}|\Theta (t)\}} \\ & \rm{ }\le B+\sum\limits_{d\in \mathcal{D}}{\mathbb{E}\left\{ \left. {{H}_{d}}(t)\left( \sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d}(t)}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t){{v}_{k}}} \right) \right|\Theta (t) \right\}}+\sum\limits_{d\in \mathcal{D}}{\mathbb{E}\left\{ \left. {{Z}_{d}}(t)\left( {{\varepsilon }_{d}}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(t){{v}_{k}}} \right) \right|\Theta (t) \right\}} \\ \end{align}$ | (A.3) |
通过在上述表达中加上V×E{C(t)},我们得到了公式(20) 中的漂移惩罚界限.
附录B:定理1的证明为证明定理1,我们首先给出如下引理.
引理B.1(最优随机稳定策略的存在性). 至少存在一个策略π,使其选择的可行解
$\begin{align} & \mathbb{E}\{C(t)\}={{C}^{*}} \\ & \mathbb{E}\left\{ \sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d,\pi }(t)} \right\}\le \mathbb{E}\left\{ \sum\limits_{k\in \mathcal{K}}{n_{d}^{k,\pi }(t){{v}_{k}}} \right\} \\ & {{\varepsilon }_{d}}\le \mathbb{E}\left\{ \sum\limits_{k\in \mathcal{K}}{n_{d}^{k,\pi }(t){{v}_{k}}} \right\} \\ \end{align}$ | (A.4) |
其中,C是理论成本下界.该引理可利用卡拉特欧多定理证明,详细见文献[36].
根据引理B.1,我们可如下证明公式(27) .
证明:从引理B.1可知,必然存在一个常数d>0,满足:
$\mathbb{E}\left\{ \sum\limits_{r\in \mathcal{R}}{\lambda _{r}^{d,\pi }(t)} \right\}\le \mathbb{E}\left\{ \sum\limits_{k\in \mathcal{K}}{n_{d}^{k,\pi }(t){{v}_{k}}} \right\}-\delta $ | (A.5) |
以及
${{\varepsilon }_{d}}\le \mathbb{E}\left\{ \sum\limits_{k\in \mathcal{K}}{n_{d}^{k,\pi }(t){{v}_{k}}} \right\}-\delta $ | (A.6) |
由本文算法力求最小化不平等公式(20) 的右半部分,通过在各时隙所有可行的决策中选择最优决策,应用引理B.1,将公式(A.5) 和公式(A.6) 代入公式(20) ,我们可得:
$\Delta (\Theta (t))+V\cdot \mathbb{E}\{C(t)|\Theta (t)\}\le B+V{{C}^{*}}-\delta \sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{H}_{d}}(t)\}}-\delta \sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{Z}_{d}}(t)\}}$ | (A.7) |
取公式(A.7) 的期望,并应用
$\mathbb{E}\{L(\Theta (t+1))-L(\Theta (t))|\Theta (t)\}+V\cdot \mathbb{E}\{C(t)|\Theta (t)\}\le B+V{{C}^{*}}-\delta \sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{H}_{d}}(t)\}}-\delta \sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{Z}_{d}}(t)\}}$ | (A.8) |
在时隙t=1,…,T-1上应用伸缩和定理(telescoping sum law),并将结果除以T,可得:
$\frac{\mathbb{E}\{L(\Theta (T))-L(\Theta (0))\}}{T}+\frac{V}{T}\cdot \sum\limits_{t=0}^{T-1}{\mathbb{E}\{C(t)|\Theta (t)\}}\le B+V{{C}^{*}}-\frac{\delta }{T}\sum\limits_{t=0}^{T-1}{\sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{H}_{d}}(t)\}}}-\frac{\delta }{T}\sum\limits_{t=0}^{T-1}{\sum\limits_{d\in \mathcal{D}}{\mathbb{E}\{{{Z}_{d}}(t)\}}}$ | (A.9) |
对上述公式进行整理,并考虑约束:L(Q(0) )=0,Hd(t)≥0,Zd(t)≥0,得:
$\frac{1}{T}\sum\limits_{t=0}^{T-1}{\mathbb{E}\{C(t)\}}\le {{C}^{*}}+\frac{B}{V}$ | (A.10) |
对公式(A.10) 求极限T→~,可得公式(26) .
附录C:定理2的证明
证明:对于Zd(t),已知
· 若
· 若
而
类似地,对于队列Hd(t),
· 若
· 若
而
因此,队列Hd(t)的界限得证.
附录D:定理3的证明证明:若存在t∈[t+1,t+l]满足Hd(t)=0,则在t时刻到达的数据将在l个时间序列内被处理.若Hd(t)>0,t∈[t+1,t+l],根据公式(14) ,可得:
${{Z}_{d}}(\tau +1)=\max \left[ {{Z}_{d}}(\tau )+{{\varepsilon }_{d}}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(\tau )}{{v}_{k}},0 \right]\ge {{Z}_{d}}(\tau )+{{\varepsilon }_{d}}-\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(\tau )}{{v}_{k}}$ | (A.11) |
在时间序列t∈[t+1,t+l]内对以上的不等式求和,可得:
${{Z}_{d}}(t+l+1)\ge {{Z}_{d}}(t+1)+l\cdot {{\varepsilon }_{d}}-\sum\limits_{\tau =t+1}^{t+l+1}{\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}(\tau )}}\cdot {{v}_{k}}$ | (A.12) |
因此,可以推导出
$\sum\limits_{\tau =t+1}^{t+l+1}{\sum\limits_{k\in \mathcal{K}}{n_{d}^{k}}(\tau )}\cdot {{v}_{k}}\ge H_{d}^{\max }\ge {{H}_{d}}(t)$ | (A.13) |
由于队列系统以先进先出方式运行,在t时刻到达的数据将比在t时刻之后到达的数据先处理.既然l个时间序列被处理的总数据量大于Hd(t),那么所有在t时刻到达的数据都将在l个时间序列中被处理,即最差的延迟为l个时隙.
[1] | 145 Amazing YouTube statistics. http://expandedramblings.com/index.php/youtube-statistics/ |
[2] | Dewdney PE, Hall PJ, Schilizzi RT, Lazio TJLW. The square kilometre Array. The square kilometre Array. Proc. of the IEEE, 2009, 97(8): 1482–1496 . [doi:10.1109/JPROC.2009.2021005] |
[3] | Dean J and Ghemawat S. MapReduce:Simplified data processing on large clusters. Communications of the ACM, 2008, 51: 107–113 . [doi:10.1145/1327452.1327492] |
[4] | Zaharia M, Chowdhury M, Franklin MJ, Shenker S, Stoica I. Spark:Cluster computing with working sets. In:Proc. of the 2nd USENIX Conf. on Hot Topics in Cloud Computing (HotCloud 2010). 2010. |
[5] | Melnik S, Gubarev A, Long JJ, Romer G. Dremel:Interactive analysis of Web-scale datasets. Proc. of the VLDB Endowmenet, 2010, 3(1-2): 330–339 . [doi:10.14778/1920841.1920886] |
[6] | Pregel. http://kowshik.github.io/JPregel |
[7] | Yin J, Wang ZS, Li Q, Su WJ. Personalized recommendation based on large-scale implicit feedback. Ruan Jian Xue Bao/Journal of Software, 2014, 25(9): 1953–1966 (in Chinese with English abstract). [doi:10.13328/j.cnki.jos.004648] |
[8] | Han L, Li M. Open source software classification using cost-sensitive multi-label learning. Ruan Jian Xue Bao/Journal of Software, 2014, 25(9): 1982–1991 (in Chinese with English abstract). [doi:10.13328/j.cnki.jos.004639] |
[9] | Xie JY, Gao HC. Statistical correlation and K-means based distinguishable gene subset selection algorithms. Ruan Jian Xue Bao/Journal of Software, 2014, 25(9): 2050–2075 (in Chinese with English abstract). [doi:10.13328/j.cnki.jos.004644] |
[10] | Vlachou A, Doulkeridis C, Nørvåg K, Vazirgiannis M. On efficient top-k query processing in highly distributed environments. Distributed and Parallel Databases, 2012, 30(3-4): 239–271 . [doi:10.1007/s10619-012-7094-2] |
[11] | Xu J, Wang GY, Yu H. Review of big data processing based on granular computing. Chinese Journal of Computers, 2015, 38(8): 1497–1517 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201508001.htm |
[12] | Ding YW, Qin XL, Liu L, Wang TC. An energy efficient algorithm for big data processing in heterogeneous cluster. Journal of Computer Research and Development, 2015, 52(2): 377–390 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201502011.htm |
[13] | Li W, Zhang DF, Huang K, Xie K. Accurate multi-dimension counting bloom filter for big data processing. Acta Electronica Sinica, 2015, 43(4): 752–657 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201504005.htm |
[14] | Lu ZM, Feng JG, Fan DM, Yang P, Tian Y. Novel partitional clustering algorithm for large data processing. System Engineering and Electronics, 2014, 36(5): 1010–1015 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-SJSM201701073.htm |
[15] | Moving an elephant:Large scalehadoop data migration at Facebook. 2016. http://www.facebook.com/notes/paul-yang/moving-anelephant-large-scale-hadoop-data-migration-at-facebook/10150246275318920 |
[16] | Schadt EE, Linderman MD, Sorenson J, Lee L, Nolan GP. Computational solutions to large-scale data management and analysis. Nat Rev Genet, 2010, 11: 647–657 . [doi:10.1038/nrg2857.] |
[17] | Facebook's prism project. 2016. http://www.wired.com/wiredenterprise/2012/08/facebook-prism/ |
[18] | Corbett JC, Dean J, Epstein M, et al. Spanner:Google's globally-distributed database. In:Proc of the OSDI 2012. 2012. |
[19] | Connecting Geographically Dispersed Data Centers. HP FlexFabric Interconnect, Fact Sheet, 2015. |
[20] | Interconnecting Geographically Dispersed Data Centers Using VPLS-Design and System Assurance Guide. Cisco Systems, Inc., 2009. |
[21] | Cho B, Gupta I. Budget-constrained bulk data transfer via internet and shipping networks. In:Proc. of the ACM ICAC. 2011. 71-80.[doi:10.1145/1998582.1998595] |
[22] | Cho B, Gupta I. New algorithms for planning bulk transfer via internet and shipping networks. In:Proc. of the IEEE ICDCS. IEEE, 2010. 305-314.[doi:10.1109/ICDCS.2010.59] |
[23] | Zhang LQ, Wu C, Li ZP, Guo CX, Chen MH, Lau Francis CM. Moving big data to the cloud:An online cost-minimizing approach. IEEE Journal on Selected Areas in Communications, 2013,31(12):2710-2721.[doi:10.1109/JSAC.2013.131211] |
[24] | Zhang LQ, Li ZP, Wu C, Chen MH. Online algorithms for uploading deferrable big data to the cloud. In:Proc. of the IEEE INFOCOM. 2014. 2022-2030.[doi:10.1109/INFOCOM.2014.6848143] |
[25] | Liu L, Wang H, Liu X, Jin X, He WB, Wang QB, Chen Y. GreenCloud:A new architecture for green data center. In:Proc. of the 6th Int'l Conf. on Industry Session on Autonomic Computing and Communications Industry Session. 2009.[doi:10.1145/1555312.1555319] |
[26] | Petrucci V, Loques O, Mosse D. A dynamic configuration model for power-efficient virtualized server clusters. In:Proc. of the 11th Brazillian Workshop on Real-Time and Embedded Systems. 2009. |
[27] | Tang JH, Tay WP, Wen YG. Dynamic request redirection and elastic service scaling in cloud-centric media networks. IEEE Trans. on Multimedia, 2014, 16(5): 1434–1445 . [doi:10.1109/TMM.2014.2308726] |
[28] | Tassiulas L, Ephremides A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. on Automatic Control, 1992, 37(12): 1936–1948 . [doi:10.1109/9.182479] |
[29] | Urgaonkar R, Kozat U, Igarashi K, Neely MG. Dynamic resource allocation and power management in virtualized data centers. In:Proc. of the IEEE Network Operations and Management Symp. (NOMS 2010), 2010: 479–486 . [doi:10.1109/NOMS.2010.5488484] |
[30] | Zhou Z, Liu FM, Xu Y, Zou R, Xu H, Lui JCS, Jin H. Carbon-Aware load balancing for geo-distributed cloud services. In:Proc. of the IEEE 21st Int'l Symp. on Modelling, Analysis and Simulation of Computer and Telecommunication Systems, 2013: 232–241 . [doi:10.1109/MASCOTS.2013.31] |
[31] | Wu D, Xue Z, He J. iCloudAccess:Cost-Effective streaming of video games from the cloud with low latency. IEEE Trans. on Circuits and Systems for Video Technology, 2014, 24(8): 1405–1416 . [doi:10.1109/TCSVT.2014.2302543] |
[32] | Zhou Z, Liu FM, Jin H, Li B, Li BC, Jiang HB. On arbitrating the power-performance tradeoff in SaaS clouds. In:Proc. of the IEEE INFOCOM. 2013.[doi:10.1109/INFCOM.2013.6566875] |
[33] | Niu YP, Luo B, Liu FM, Liu JC, Li B. When hybirid cloud meeets flash crowd:Towards cost-effective service provisioning. In:Proc. of the IEEE INFOCOM. 2015.[doi:10.1109/INFOCOM.2015.7218477] |
[34] | Yao Y, Huang LB, Sharma A, Golubchik L, Neely MJ. Power cost reduction in distributed data centers:A two-time-scale approach for delay tolerant workloads. IEEE Trans. on Parallel and Distributed Systems, 2014, 25(1): 200–211 . [doi:10.1109/TPDS.2012.341] |
[36] | Neely MJ. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan and Claypool, 2010. |
[37] | Neely MJ. Opportunistic scheduling with worst case delay guarantees in single and multi-hop networks. In:Proc. of the INFOCOM. IEEE, 2011: 1728–1736 . [doi:10.1109/INFCOM.2011.5934971] |
[38] | Arlitt M, Jin T. A workload characterization study of the 1998 world cup Web site. IEEE Network, 2000, 14(3): 30–37 . [doi:10.1109/65.844498] |
[39] | Umasstracerepository. 2014. http://traces.cs.umass.edu/index.php/Network/Network |
[40] | Where Amazon's data centers are located. http://www.datacenterknowledge.com/archives/2008/11/18/where-amazons-data-centersare-located/ |
[41] | Gpsspg. http://www.gpsspg.com/distance.htm |
[7] | 印鉴, 王智圣, 李琪, 苏伟杰. 基于大规模隐式反馈的个性化推荐. 软件学报, 2014 , 25(9) : 1953 –1966. [doi:10.13328/j.cnki.jos.004648] |
[8] | 韩乐, 黎铭. 基于代价敏感多标记学习的开源软件分类. 软件学报, 2014 , 25(9) : 1982 –1991. [doi:10.13328/j.cnki.jos.004639] |
[9] | 谢娟英, 高红超. 基于统计相关性与K-means的区分基因子集选择算法. 软件学报, 2014 , 25(9) : 2050 –2075. [doi:10.13328/j.cnki.jos.004644] |
[11] | 徐计, 王国胤, 于洪. 基于粒计算的大数据处理. 计算机学报, 2015 , 38(8) : 1497 –1517. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201508001.htm |
[12] | 丁有伟, 秦小麟, 刘亮, 王涛春. 一种异构集群中能量高效的大数据处理算法. 计算机研究与发展, 2015 , 52(2) : 377 –390. http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201502011.htm |
[13] | 李玮, 张大方, 黄昆, 谢鲲. 面向大数据处理的高精度多维计数布鲁姆过滤器. 电子学报, 2015 , 43(4) : 752 –657. http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201504005.htm |
[14] | 卢志茂, 冯进玫, 范冬梅, 杨朋, 田野. 面向大数据处理的划分聚类新方法. 系统工程与电子技术, 2014 , 36(5) : 1010 –1015. http://www.cnki.com.cn/Article/CJFDTOTAL-SJSM201701073.htm |
[35] | Zhao J, Li HX, Wu C, Li ZP, Zhang ZZ, Lau Francis CM. Dynamic pricing and profit maximization for clouds with geo-distributed datacenters. In:Proc. of the IEEE INFOCOM. 2014.[doi:10.1109/INFOCOM.2014.6847931] 560 Journal of Software软件学报Vol.28, No.3, March 2017 |