【作者】 王博；

【导师】 杨广文；

【作者基本信息】 清华大学 ， 计算机科学与技术， 2015， 博士

【摘要】 大数据时代的到来,向如何存储、管理、访问和处理这些巨量数据提出了新的挑战,目前人们普遍认同,并行化处理是在大数据时代中高效处理这些数据密集型应用的有效手段。Map Reduce的出现由于其高可扩展性及易于编程性,引起了工业界和学术界的广泛关注,并且产生了大量的优化研究工作。在众多研究工作的优化下,Map Reduce日趋完善,但是随着技术发展,新硬件平台新集群模式的出现,也向Map Reduce性能提出了新的挑战,比如异构集群的出现,众核集群的普及,高性能科学计算领域引入Map Reduce等场景,都使得之前在传统环境下性能良好的Map Reduce框架出现性能低下的问题。针对这些新出现的问题,本文重点针对Map Reduce在异构集群、倾斜数据和众核集群三种应用场景下的性能进行了优化,主要贡献及创新点如下:1)提出了Act Cap,一种根据节点计算能力进行数据分布以优化Map Reduce在日益增长的异构集群上运行时间的方法,其核心部分是使用马尔科夫链模型来实时预测节点的计算能力并且根据节点的计算能力对Map Reduce任务的输入数据进行分布。实验结果表明,Act Cap获得了相对于Hadoop49.8%的平均加速比,相对于Tarazu9.8%的平均加速比—目前最新的在异构集群上的Map Reduce优化工作。2)提出了Skew--,一种称之为“基于复杂度Key分布”的离线数据划分方法,并且使用三个称之为“本地感知Reducer选择”、“全Mapper执行”和“Shu ffl e感知调控”的组件进行智能调度。“基于复杂度Key分布”不仅考虑key记录的大小也考虑Reduce函数的复杂度,以更好地在各个Reduce子任务间平衡计算开销。“本地感知Reducer选择”、“全Mapper执行”和“Shu ffl e感知调控”分别利用数据本地性来减少数据传输,更加有效利用资源来减少离线Key分配带来的额外开销。实验结果表明,Skew--可以取得相对于Hadoop YARN1.98x倍的平均加速比,相对于Skew Tune1.65x倍的平均加速比,并且在Reduce阶段可以取得相对于Top Cluster1.25x倍的平均加速比。3)提出了mp Cache,一个基于SSD的面向Map Reduce的统一缓存系统,该系统缓存输入数据及本地数据来加速Map Reduce中所有IO开销大的阶段—“读入”、“溢出”和“合并”。为了更加高效地利用所有缓存空间,mp Cache动态地调整整个空间在输入缓存和本地缓存之间的配比,mp Cache对所有的节点进行统一管理并且使用针对Map Reduce任务“All-or-Nothing”特性的缓存替换策略来更加良好支持Map Reduce。实验结果表明,mp Cache可以得到相对于Hadoop2.09x倍的平均加速比,相对于PACMan1.79x倍的平均加速比。更多还原

【Abstract】 The era of big data presents many challenges and requires new ways to store, manage, access and process the colossal amount of available data. Map Reduce is a programming model and an associated implementation for parallel large data sets processing on clusters with hundreds or thousands of nodes. Due to its scalability and ease of programming, Map Reduce has been adopted by many companies and also optimized by many researchers. Due to the large quantities of research works, Map Reduce is becoming more and more e ffi cient. With the developing of both hardware and software technologies, new hardware platforms and new data clusters emerges, which also challenges the performance of Map Reduce, e.g., when Map Reduce running on heterogeneous clusters,many-core clusters, or computing high performance scientific applications, the performance degrades significantly. To solve these problems, this paper mainly optimizes the performance of Map Reduce when running on heterogeneous clusters, with skewed input data, and on many-core clusters. The main contributions and innovations of this paper are as following:1) This paper proposes Act Cap, a solution that uses a Markov chain based model to do node-capability-aware data placement for the continuously incoming data. To do so, Act Cap utilizes a two-state Markov chain to describe a node’s behavior, and devises a new algorithm to predict the nodes’ capabilities of data processing and to do data placement accordingly. The experimental results show that Act Cap can reduce the percentage of inter-node data transfer from 32.9% to 7.7% and gain an average speedup of 49.8% when compared with Hadoop, and achieve an average speedup of 9.8% when compared with Tarazu, the latest related work.2) This paper proposes Skew--, a coordinated systematic solution synthesizing various optimization techniques. The key contributions of Skew-- are: 1) it devises a new sampling-based automatic approach to determine the complexity of Reduce tasks and presents Complexity-Aware Keys Assignment, a post-Map keys allocation scheme that takes into account not only the number of keys, but also the Reduce task complexity and the key group size to balance the loads among Reducers;and 2) it proposes Locality-Aware Reducers Selection, Full Mappers Execution,and Shu ffl e-Type Identification, three mechanisms that guarantees the benefit of Complexity-Aware Keys Assignment by enhanced data locality and more e ffi cient resources scheduling. Experiments on a 7-node cluster with 13 benchmarks show that Skew-- can get an average speedup of 1.98 x, 1.63 x, and 1.77 x over YARN,Skew Tune, and Online Balancer respectively. In addition, it can achieve an average speedup of 1.41 x in the Reduce phase over Top Cluster, the latest work that is most similar to ours.3) This paper proposes mp Cache, a new approach to cache both Input Data and Localized Data to speedup the IO-intensive phases. An algorithm is used to dynamically tune the allocations between Input Cache and Localized Cache to make full use of the cache and provide better performance. We also propose an algorithm to replace Input Cache e ffi ciently, taking replacement cost, data set size, access frequency, all-or-nothing into consideration for better performance. The experiment results shows that mp Cache gets an average speedup of 2.09 x when compared with original Hadoop and achieves an average speedup of 1.68 x when compared with PACMan.更多还原