
收稿日期:20180827;修回日期:20181011 基金项目:国家自然科学基金资助项目(61502224,61872175)
作者简介:徐超(1989),男,山东莱芜人,工程师,硕士,主要研究方向为分布式系统、大数据处理(mmxcan@163.com);吴波(1974),男,江苏
淮安人,工程师,学士,主要研究方向为分布式系统;姜丽丽(1989),女,天津人,工程师,硕士,主要研究方向为边缘计算;金熠波(1994),男,浙江
上虞人,博士研究生,主要研究方向为分布式大数据处理系统;张胜(1986),男,江苏镇江人,讲师,博士,主要研究方向为分布计算与并行处理.
云—边缘系统中跨域大数据作业调度技术研究
徐 超
1
,吴 波
1
,姜丽丽
2
,金熠波
3
,张 胜
3
(1.国网江苏省电力有限公司电力科学研究院,南京 210008;2.江苏方天电力技术有限公司,南京 211102;
3.南京大学 计算机科学与技术系,南京 210023)
摘 要:为了降低因处理这些跨域大数据带来的作业完成时延,首先提出了以最小化系列跨域作业平均完成时
间为优化目标的在线随机调度算法
ranTA。ranTA基于跨域资源的异构性在线地计算出各计算任务调度至不同
位置的偏好,并以此偏好作为概率调度每个计算任务;更进一步,为了避免将“热点”数据积压在边缘集群造成性
能瓶颈,提出基于
ranTA的捎带式数据重分布机制 ranTAdata,其将部分数据随任务执行留存至云数据中心。
ranTAdata不仅优化了当前作业的完成时间,也能证明在该机制下系列作业的平均完成时间以大概率汇聚于最
优解附近。大规模仿真实验表明,所提出的在线随机化算法与数据重部署机制相比传统方法,平均降低系列作
业完成时间近 30%。
关键词:跨域数据处理;云—边缘集群;任务调度
中图分类号:TP311 文献标志码:A 文章编号:10013695(2020)03025075405
doi
:10.19734/j.issn.10013695.2018.08.0629
Taskschedulingforgeodistributeddataanalyticsincloudedgesystem
XuChao
1
,WuBo
1
,JiangLili
2
,JinYibo
3
,ZhangSheng
3
(1.ResearchInstituteofStateGridJiangsuElectricPowerCo.Ltd.,Nanjing210008,China;2.JiangsuFrontierElectricTechnologyCo.
Ltd.
,Nanjing211102,China;3.Dept.ofComputerScience&Technology,NanjingUniversity,Nanjing210023,China)
Abstract:Inordertominimizetheaveragecompletiontimeofaseriesofgeodistributeddataanalyticaljobs,thispaperfirst
introducedonlinerandomschedulingalgorithmranTA.ranTAactuallyshowedthepreferenceonthetaskassignmentunderthe
considerationofbothcomputingcapacityofedgesandthenetworkbandwidth.Furthermore,inordertoavoidoverloadingthose
edgeswithlowcomputingcapacities,thispaperproposeddataredistributionmechanismranTAdatabasedonranTAbyredis
tributingsomedatatothecentraldatacenteralongwiththetasks.TheresultofranTAdatacouldbeprovedconcentratedonits
optimumwithhighprobability.ExtensivesimulationsshowthatranTAdataimprovesnearly30% performancecomparedwith
traditionalalgorithms.
Keywords:geodistributeddataanalytics;cloudedgesystem;taskscheduling
0 引言
谷歌和阿里巴巴等许多大型企业与组织已经在全球范围内
部署了多个数据中心以及大量跨地域分布的边缘集群
[1]
。利用
数据中心强大的处理能力与边缘集群低时延的优势,这样的
云—边缘系统为用户提供了高质量的业务,并且在各个边缘积
累了大量用户数据
[2]
。而许多商业决策或数据分析需要实时综
合处理这些跨域分布的数据
[3]
,因此如何在云—边缘系统中实
现低时延的跨域大数据处理作业已成为一个重要的研究问题。
由于广域网数据传输的局限,将大量边缘数据先汇聚到云
数据中心再处理的方式,不仅消耗带宽,也带来了较大的时延。
有不少工作考虑尽可能将任务本地化执行,以减少广域网数据
传输。Vulimiri等人
[4]
研究如何在跨域环境下进行最少数据
量的传输和快速任务执行。Pu等人
[5]
发现利用稀缺带宽进行
大规模数据传输容易造成各异的跨域传输时间,因此通过合理
任务调度最小化跨域数据传输时延。文献[6,7]在进行大数
据处理作业的执行模式选择上也将数据传输与带宽的使用考
虑在内,从而选出最优数据传输策略。然而,由于边缘集群在
计算能力上的异构,纯粹优化数据传输的任务调度也会导致负
载不均,造成一些任务在“热点”边缘积压。为此,文献[8,9]
针对跨域环境带宽与计算力的异构性,提出了利用空闲资源与
带宽进行批量任务调度,以减少批量任务的整体完成时间。但
是,一味地在本地计算资源被占用时将任务直接调度到远端云
数据中心使用空闲计算资源,会给跨域链路带宽造成极大的负
担。由于一些任务在本地进行适当的排队就能够获取到空闲
的计算资源,为此
Jin等人
[10]
针对空闲资源与占用资源使用不
均衡的问题,设计了支持任务本地排队的批量任务调度方案,
进一步降低批量任务的整体完成时延。
然而,所有这些研究工作都只针对当前提交的作业,通过
任务调度来降低该作业的完成时间。事实上,在云—边缘这样
的异构分布式系统中,数据分布是影响作业执行的关键。如果
能将“热点”数据尽可能转移到具有强大处理能力的数据中心,
那么后续相关作业就可以高效完成。现有工作虽然优化了当前
任务的完成时间,但并未考虑多个作业的平均完成时间,即没有
系统化研究由于当前任务调度引起的数据重部署对后续作业带
来的收益。为此,本文以优化系列作业平均完成时间为目标,深
入研究了跨域大数据作业的任务分配问题,提出了在线随机化
任务分配算法
ranTA与捎带式数据重部署策略 ranTAdata。不
仅优化了当前作业的完成时间,也能证明系列作业的平均完成
时间以大概率汇聚于最优解附近。大量模拟实验亦表明,在线
随机化任务调度算法与捎带式数据重部署策略具有良好性能,
第 37卷第 3期
2020年 3月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.37No.3
Mar.2020