论文部分内容阅读
互联网时代的快速发展带来了大数据时代,大规模数据的高效处理对生产和实践意义重大,传统的计算模式已无法满足海量数据的处理需求。2004年,在Google发表了GFS和MapReduce的论文后,Hadoop开源项目应运而生。Hadoop由HDFS和MapReduce构成,MapReduce作为其核心组件,主要负责海量数据的分布式处理,其计算性能是一个备受关注的热点问题。通过大量的调研和实验分析发现,数据本地化是影响MapReduce计算框架性能的一个重要因素,它对集群网络带宽的消耗和节点的计算效率都构成影响。本文以MapReduce数据本地化为切入点,旨在通过提升MapReduce数据本地化来提升作业的执行效率。数据本地化即数据源在计算本地,本文深入剖析了MapReduce任务调度机制,发现MapReduce选择数据块和计算节点时的粗糙性是其数据本地化程度不高的主要原因。为了解决这个问题,本文对任务调度和资源分布进行了高度抽象并建模,提出了Bolas和Bolas+两个高效的任务调度算法,解决了MapReduce数据本地化的问题,也提升了作业执行效率。在MapReduce调度优化方面,本文有很好的创新性。Bolas创新性的将MapReduce的任务调度抽象为带权二分图的最优匹配问题,并创新性的解决了二分图匹配过程中计算节点和数据块的不匹配问题。Bolas+创新性的提出基于数据块标记的轻量级调度策略,在调度中,对数据块和节点进行了更加精细化的考虑。通过大量实验证明,Bolas可以将作业的数据本地化程度提升到100%,作业的执行效率能平均提升25%,Bolas+的数据本地化程度平均能保持在95%以上,随着作业规模变大,本地化趋于100%,作业执行效率能平均提升15%。基于图匹配Bolas虽然能取得很好的调度结果,但其算法复杂度为O(n3),随着作业规模的增大大,响应时间增速变快;基于数据块标记的Bolas+的算法复杂度为O(n/m),其响应时间随着作业规模的增大是线性增长的,n代表数据块的数量,m代表计算节点的数量。