论文部分内容阅读
近年来,数据呈指数级增长趋势使得大数据问题受到广泛关注。与传统的海量数据相比,大数据更强调数据的潜在价值,需要强有力的分析挖掘技术才能有效获取这种价值。大数据分析挖掘对大规模并行数据处理技术提出了高性能、高可扩展、高可靠等要求。Map Reduce支持大规模自动化并行、高度自动化扩展、细粒度透明容错,非常适合大数据分析挖掘。目前,Map Reduce技术已经成为大数据分析挖掘的核心技术。Map Reduce应用大量出现,很多机构都在使用Map Reduce来解决他们的应用需求,例如:卫星图像数据清洗、生成倒排索引、用户点击流分析等。然而,Map Reduce最初用于大规模批处理领域,最近才开始转向大规模交互式应用领域。与批处理应用相比,交互式应用有很多不同,这使得最初的Map Reduce系统不能很好地适应。对于交互式应用优化,传统数据库研究领域已积累了大量成熟技术,但数据库的扩展性和可靠性受限。本文的研究动机是利用传统数据管理技术扩展Map Reduce技术,使之更加适合交互式应用需求。本文从Map Reduce框架的执行流程入手,分析了每个执行阶段的优化机会,结合交互式应用的特点,做出了四个方面的优化研究工作,将其总结如下。(1)基于全局索引的Map Reduce作业调度执行优化。优化对象是大规模交互式分析挖掘应用中一类常见的作业类型-条件类作业。原始Map Reduce系统没有针对条件类作业的语义特点进行优化。在已有研究工作基础上,提出了一种基于全局索引的作业调度执行优化策略。优化目标是作业的执行开销和调度开销。前提假设是数据分区全局有序,有针对数据分区的全局索引知识。方法是在Map Reduce处理流程中增加条件分析阶段,并基于全局索引减少需要调度执行的任务规模。实验结果表明我们的策略对条件类作业具有更好的调度开销和执行开销。(2)关注数据本地性的公平任务调度算法。在大规模普通网络集群环境进行数据密集型计算,网络带宽是最稀缺的系统资源。使任务靠近数据执行是非常重要的性能优化原则,该原则在Map Reduce环境下被称为数据本地性原则。数据本地性直接影响着计算效率。交互式计算平台由大量用户共享,需要公平共享资源。在交互式环境下绝对公平对数据本地性影响较大。为此,本文提出一种灵活的公平调度策略,称为K%-公平调度。首先考虑数据本地性,进而考虑公平性。通过调整参数K,可使数据本地性和公平性都得到较好的优化。(3)关注数据本地性的任务调度框架。任务调度阶段,数据本地性是必须要考虑的指标。此外,可能还需要考虑其他因素(如作业长度、作业类型、数据共享、等待时间等)。因此,有必要设计一个关注综合指标的任务调度框架。该框架优先考虑数据本地性,基于数据本地性对任务执行位置进行规划。任务调度阶段若有多个候选任务,基于综合指标函数对候选任务排序,调度最靠前的任务。(4)关注集群计算效率的作业调度算法。作业调度算法规定了所有提交作业的执行顺序。研究主要针对大量突发性负载模式。这种负载模式下,影响机群计算效率的因素主要包括三个方面:数据本地性、负载均衡性、资源使用的流水并行性。若没有作业调度,使全部作业都可获得资源,数据本地性和负载均衡性很容易保证。这将导致大量作业恶意争用共享资源,影响不同类型资源之间的流水并行性。作业调度控制了作业的并行度,进而控制了可调度的任务规模,这种情况下很难同时保证数据本地性和负载均衡性。针对这种情况,本文首先限制任务调度遵循严格数据本地性原则。进而,以负载均衡性为标准优化作业选择算法。