论文部分内容阅读
近年来,高速发展的计算机存储和网络技术产生了海量数据和大数据,云计算的兴起也为大数据的存储和计算提供了理想平台。分析这些数据可以更好地帮助人们了解用户行为和制定商业决策,而数据挖掘、机器学习、应用统计等数据分析技术通常包含迭代计算过程。对海量数据进行数次迭代计算是一个极其耗时的过程,并且将消耗大量云资源。加速大数据迭代计算的收敛速度,缩短运行时间,是当今云计算领域的研究热点,对现实生产有着重要意义。Google提出的MapReduce模型在批处理计算方面优势明显,而在处理迭代计算方面存在诸多不足。近年来不断有专门支持迭代处理的分布式计算框架出现,从优化系统和改进计算模型两个方面提高大数据迭代计算的性能。本文区别于这些已有工作,改进现有的MapReduce模型,并在迭代计算理论方面做出了创新。论文取得的主要研究成果总结如下：(1) iMapReduce:为了实现迭代计算,MapReduce模型需要处理一系列MapReduce作业,其中每次迭代对应一个或若干个MapReduce作业。这种批处理模型导致了反复多次的作业调度和数据加载开销,限制了MapReduce迭代处理的性能。本文针对MapReduce在迭代处理方面的不足,提出了一种基于MapReduce模型的迭代处理框架——iMapReduce。它只建立一个作业来避免反复作业调度的开销,维护本地静态数据来避免反复加载传输静态数据的开销,并在一次迭代内允许异步执行Map任务。通过这些对迭代处理系统优化,iMapReduce可以有效提升大数据迭代计算性能。Amazon EC2上的大规模实验显示,iMapReduce相比Hadoop (MapReduce模型的开源实现)在处理迭代计算方面可以减少高达5倍的运行时间。(2) PrIter:通过对大量迭代算法的研究,本文发现了可以提高迭代算法收敛速度的优先级处理技术。现有迭代计算不加区别地对所有数据单元执行迭代更新计算,而在实际中,广泛存在的数据幂率分布决定了这些数据存在较大差异。某些数据单元具有较强的代表性,对迭代计算收敛起着更重要的作用。利用这个特点,可以对数据单元加以区分,对那些对算法收敛作用更大的数据单元执行更频繁的更新计算,而忽略那些无关紧要的数据单元。本文从理论上证明了优先级迭代的正确性和收敛性,并设计实现了支持优先级迭代的分布式框架——PrIter。大规模实验结果显示PrIter可以加速Hadoop处理效率高达50倍,与iMapReduce相比也能得到5至10倍的性能提升。(3) Maiter:迭代计算模型中普遍采用的同步计算模式要求所有计算节点完成本次迭代的任务之后才可以开始下一次迭代,这要求首先完成分配任务的计算节点要等待未完成任务的节点。这在很大程度上限制了分布式系统的处理能力,尤其是在计算节点之间性能差异较大的分布式环境中。为了支持异步迭代,本文从理论上推导出累加迭代方法,并证明了异步累加迭代计算的正确性和收敛性,用抽象代数描述了异步累加迭代的计算模型,并基于此抽象模型设计实现了支持异步累加迭代的分布式框架——Maiter。大规模实验结果显示异步累加迭代模型相比较于同步模型可以获得5至10倍的性能提升,同时比Hadoop中的迭代计算快达80倍左右。上述成果的取得,大大提高了迭代计算在云环境下的收敛速度,减少了运行时间。本文部分研究成果已经被美国麻州大学(UMass Amherst)的图片搜索系统Million Book、卡内基梅隆大学(CMU)的机器学习项目GraphLab、微软研究院(Microsoft Research)的Daytona项目所采用。另外,为了有助于云环境下迭代计算的研究与应用,本文同时提供了iMapReduce、Pilter和Maiter三个分布式框架的源码下载。