MapReduce的系统性能评估与Backup调度策略(一)

本论文在其他论文栏目，由论文格式网整理,转载请注明来源www.lwgsw.com,更多论文,请点论文格式范文查看

摘要
MapReduce是一个在海量数据上进行数据处理的并行编程模型，它特别适合于海量非结构化和结构化数据的搜索、分析和挖掘任务，已经开始被人们广泛使用。对于兴起的众多类似MapReduce系统来说，如何有效地评估和分析对比这些系统，成为当前一个需要解决的问题。
本文详细讨论了针对MapReduce运行系统的性能评估指标和方法，设计和选择一系列具有代表性的程序和数据作为基准，用来评估和分析MapReduce系统。在这一评估方法指导下，本文在我们自己实现的MapReduce运行系统——Tplatform平台上扩展了Profiling功能，然后进行了一系列评估实验，来分析和寻找系统性能瓶颈，为未来系统优化提供依据。通过实验我们发现了我们系统的一些可改进的问题如任务调度、落后者问题等等。我们选择了针对导致提交任务延迟增加的落后者问题，通过实现后备任务策略来尝试改进。经模拟实验结果显示，我们提出的改进策略能够有效地改进落后者问题的性能问题。

关键词：MapReduce，性能评估，落后者问题，后备任务策略

Abstract
MapReduce is becoming an important parallel programming paradigm for processing Internet scale data. It is widely used to process jobs such as searching, analyzing, and mining on large scale structured and semi-structured data. It is still a problem for the emerging MapReduce-like systems to analyze and eva luate systematically and efficiently.
This paper discussed the issues in performance eva luation for MapReduce runtime system. We designed and chose a series of representative programs and data as benchmark. And then we implement profiling in our homemade MapReduce system which named Tplatform. We did the eva luation experiment for finding the bottleneck of the system. Through the experiment, we found some performance problems such as scheduling and stragglers etc. We implemented backup tasks for improving the problems caused by stragglers. Our simulation results reveal that we improve the performance efficiently.

Keywords: MapReduce, Performance eva luation, Stragglers, Backup tasks
目录
第 1 章引言 4
第 2 章 MapReduce框架 6
2.1 MapReduce模型介绍 6
2.2 系统实现 6
2.3 Tplatform的实现 8
第 3 章系统评估 10
3.1 评估目标 10
3.2 基准程序和数据 10
3.2.1 基准程序集合 11
3.2.2 评估目标 13
第 4 章系统监控和程序概要分析 15
4.1 实现细节 15
第 5 章评估实验 17
5.1 机群配置 17
5.2 实验结果 17
5.2.1 单任务延迟和总机器时间 17
5.2.2 平均结束时间 18
5.2.3 加速比 18
5.2.4 公平性 20
5.2.5 故障恢复稳定性 20
5.3 实验结果和性能问题分析 20
5.4 开销分析 22
第 6 章后备任务调度策略 24
6.1 问题描述 24
6.2 相关工作 24
6.2.1 MapReduce 24
6.2.2 Hadoop 25
6.2.3 异构环境中后备任务调度 25
6.3 实现细节 26
6.3.1 整体框架 26
6.3.2 落后者判定策略 26
6.3.3 系统处理过程 28
6.3.4 数据结构细节 28
6.4 后备任务策略评估实验 29
6.4.1 机群配置和任务准备 29
6.4.2 任务耗时趋同性分析 29
6.4.3 后备任务策略评估 30
第 7 章系统优化方向 33
7.1 网络传输问题 33
7.2 增加用户和系统的交互 33
7.3 从数据库领域看系统性能的其他提升空间 34
7.4 系统易用性 34
第 8 章总结 35

引言
MapReduce正在成为人们在海量数据上进行并行计算的重要编程模型，比如为大规模的网页做索引、在海量的数据中进行挖掘、庞大的科学计算任务等等。
人们开始关注在普通计算机上实现大规模的并行计算以提供各种服务，Google则无疑是这方面的先驱者。Google使用MapReduce作为日常计算的引擎，将每天处理20PB的数据[ Dean, J. and Ghemawat, S. MapReduce: Simplified Data Processing on Large Clusters. proceedings of OSDI, 2004.]存在底层的存储系统如GFS6、BigTable7中。很多重要的搜索引擎服务，如索引、网页排序、网页消重与去噪、用户日志分析、用户行为预测等等，都可以使用MapReduce的框架来加快程序员在进行相关的处理。
此外，MapReduce也是一个如今很受欢迎的并行计算模型。MapReduce良好的可扩展性使得并行处理变得很容易，人们可以很方便地把MapReduce部署到大规模的廉价机群上使用。它的开源实现版本Hadoop[ Hadoop. The hadoop project. http://lucene.apache.org/hadoop/, 2006.]也得到了广泛的应用。如今很多公司如Yahoo!、FaceBook、Amazon、New York Times，以及部分研究机构和大学如CMU、Cornell等等都开始使用Hadoop进行研究和开发。
为了更好和方便地让程序员使用MapReduce或者类似的并行处理计算框架如Map/Reduce/Merge6，人们在其上架设了一系列的编译系统，并通过高层的语言把计算任务映射为底层的MapReduce任务。这方面的工作如Yahoo! 在Hadoop上实现的Pig[ C. Olston, B. Reed, U. Srivastava, R. Kumar and A. Tomkins. Pig Latin: A Not-So-Foreign Language for Data Processing. proceedings of SIGMOD, 2008.]、Google实现的Sawzall[ Pike, R., Dorward, S., Griesemer, R., and Quinlan, S. Interpreting the data: Parallel analysis with sawzall. Scientific Programming 13, 4 (2005), 277–298.]等等。
类似系统的开发和研究也层出不穷，如微软有自己的Dryad5/SCOPE7/DryadLINQ[ Isard, M., Budiu, M., Yu, Y., Birrell, A., and Fetterly, D. Dryad: distributed data-parallel programs from sequential building blocks. proceedings of the ACM SIGOPS, 2007]系列系统。拥有这样的处理能力无疑成为一个互联网公司的核心竞争力，可以预见在未来的一段时间里面，还有类似的很多系统和研究出现。
人们在使用Hadoop或者类似的其他并行处理计算框架及其上层语言时，众多的使用者对底层大规模并行处理计算框架有自己的需求。比如大学或研究机构使用此类框架进行科学计算时，系统的工作负载可能是偏向计算密集型，人们也关心系统对于计算任务的延迟反应；而大型因特网公司如Google、Yahoo!、Microsoft Live Search等的数据中心中，有若干程序员在同时提交计算任务，程序员不但关心计算任务的延迟，还关心整个中心中负载的调度公平性；而对于此类系统的开发和研究人员来说，他们关心系统的吞吐量、系统中各机器的状态和使用情况等等。所以考虑此类并行处理计算框架特别是MapReduce系统的各项系统指标，并确定评估的程序和方法，对评估类似系统、基于用户希望的系统设计折衷进行系统之间的比较、改进系统等等有很重要的意义。在这个基础上如Berkeley也有一些系统测试的工作如分析网络的性能X-Trace[ R Fonseca, G Porter, RH Katz, S Shenker, I Stoica. X-trace: A pervasive network tracing framework. proceedings of NSDI , 2007.]，以及对MapReduce系统和数据库系统性能评估的讨论15。
我们基于MapReduce实现了自己的并行处理计算框架，并在其之上进行了系统的测试和评估。我们提出了测试程序和数据，并基于此在系统中实现了监控和程序性能概要分析框架。通过测试和评估实验，我们总结了系统的性能指标和观察到的问题。我们针对其中的单机落后问题，实现并验证了后备任务策略，并基于此改进系统性能。最后，我们总结并给出了其他工作方向。
论文的剩余部分按如下方式进行组织。第二章对MapReduce的模型和体系结构进行概述，而第三章列出了需要评估的系统目标和我们设计的基准程序和数据集合。为了分析和评估系统，我们在第四章阐述了系统监控框架和程序概要分析的设计和实现细节。之后我们在第五章中列出了实验结果和给出了实验的分析，并在针对其中的落后者问题实现了后备任务策略，在第六章中详细阐述了后备任务策略的实现和实验评估。我们在第七章中对系统可能的优化方向进行了展望并在第八章中进行了总结，最后是致谢。

MapReduce框架
在这一章里面，我们将简单介绍MapReduce框架的模型和我们的系统实现。
MapReduce模型介绍
Google的研究人员受到函数式编程语言（functional language）的启发，在总结大量的大规模分布式处理程序共同特征的基础上，提出了MapReduce并行程序框架。
MapReduce是一大类大规模并行数据处理程序的抽象。这类计算的输入是一个（键，值）对的集合，输出也是一个（键，值）对的集合。用户只需要提供两个操作map和reduce的实现，MapReduce运行时库就可以自动把用户程序并行化。
用户提供Map函数的实现，它接收一个输入对，产生一组中间结果对。MapReduce库会把具有相同键的所有中间结果对聚合到一起，把他们传给Reduce函数。用户提供的Reduce函数，接收中间结果的一个键和具有此键的一组值，处理这些值，产生若干个（键，值）对做为输出。它们的一般形式如下：[ 杨志丰，GFS与MapReduce的实现研究及其应用，北京大学硕士论文，2008.]
Map (k1, v1) -> list (k2, v2)
Reduce (k2, list (v2)) -> list (v2)
MapReduce模型的最大好处是简便性，用户只需要提供这两个接口就可以处理大规模的数据，而不需要太多分布式计算的实现细节。
系统实现
MapReduce的实时运行主要是为并行化和并发执行服务的。为了尽可能的并行化和扩展系统，MapReduce把输入的数据分割到多个机器上。中间数据的传输和序列化处理等由系统来控制。分割的数据由多个Reduce来处理。这两个步骤中Map任务和Reduce都可以同时执行，且它们都具有良好的可扩展性，也即可以方便地增加机器增加并发度。
而在系统实现的层面上，系统需要决定底层的各个细节如数据单元的大小、中间数据的处理、内存的缓存多大、排序的方式、各个任务的调度、机器的失败和容错处理等等。系统自动的把这些细节都掩盖，所以对程序员来说，他只需要知道这个编程模型并编写MapReduce的程序即可。
Google的论文中描述了他们在分布式机群系统上对MapReduce的实现。系统把输入数据划分为M份数据片，这些输入数据片可以在不同的机器上并发的被Map函数处理。所有的中间结果对使用一个分区函数（partitioning function）分为R份。然后，对于每个分区，通过排序把具有相同键的所有（键，值）对聚合到一起，用Reduce函数处理，最后产生R个输出文件。R的值和分区函数可以由用户指定，系统默认的分区函数是hash(key) mod R1。
Google的MapReduce实现是构建在GFS之上的，所有的MapReduce程序的输入和输出都是存储在GFS中的文件。由于GFS中的数据都有多个副本，当执行MapReduce的机群和运行GFS的机群是同一个时，MapReduce库的调度模块会尽量把map任务分配到存储数据的机器上本地运行，这样可以避免输入数据的网络传输，极大的提高性能。此外，用户可以指定函数用来把原始输入数据转换为map函数的输入，用户也可以指定函数用来把reduce的输出结果序列化为输出数据。体系结构图1如下：

数据的流图[ Colby Ranger, Ramanan Raghuraman, A. P. G. B. C. K. eva luating mapreduce for multi-core and multiprocessor systems. proceedings of HPCA, 2007]如下，Worker分别执行本地的任务，可能是Map任务、Transfer任务和Reduce任务。整个过程由Master控制和协调调度。

Tplatform的实现
我们实现的类似平台是Tplatform。我们自己也实现了一个自制的MapReduce，建立在GFS类似的分布式文件系统TFS上[ Zhifeng Yang, Qichen Tu, K. F, L. Z, R. C, B.P. Performance gain with variable chunk size in gfs-like file systems. Journal of Computational Information System 3(2008), 1077-1084]。TFS在设计上与GFS的不同之处在于对底层Chunk大小的设置7。与Google提供运行时库然后通过一个二进制程序的多个副本扮演不同角色的方式不同，我们的实现提供的是一个执行MapReduce作业的服务，用户把编写好的实现指定接口的动态链接库用系统提供的API提交上来，MapReduce系统就会自动调度和运行相关的任务。服务由一台主控（Master）机器和若干台工作机（Worker）组成，Master负责把用户提交的作业（Job）切分为若干个任务，然后调度他们在各台工作机上执行。相比提供运行时库由用户编译为一个程序的方式，这样做的好处是，系统的改进升级对用户是不可见的。如果系统的实现改变了，只要MapReduce API不改变，用户无需改变代码甚至不需要重新编译生成动态链接库就可以执行MapReduce作业，这给我们未来系统的升级优化带来了极大的便利。不仅如此，在Google的原始实现中，如果同一个机群有多个作业在同时运行，因为作业由主控程序负责调度但一个作业的主控程序是不知道另一个作业的存在的，所以多个作业之间可能产生资源的互相抢占。而在我们的系统中，一个机群只有一个主控程序，主控程序可以综合各个作业的情况对所有任务整体进行调度。
这里需要详细说明我们任务设计的细节。
我们把Worker需要做的任务分成三个类型：Map、Transfer、Reduce，我们把传输任务从原来的Reduce中抽离出来并作为一个可以由Worker单独调度执行的任务。在这里我们对此设计有如下的分析。
在原来的Map、Reduce任务的执行流程和设计下，对于Map执行完生成的中间数据，是由Reduce来到Map机器上通过远程调用取得。这些有可能出现的场景是很多Reducer同时来一台Map机器上进行取数据操作，造成Map机器对硬盘的随机写，而随机写对性能的影响是很大的，这样的数据传输模型可以称之为“拉”。而我们把传输任务独立开来，由Master调度控制，可以控制Mapper传输的时间，同时Reducer在同时接到多个传输任务的数据时可以做缓存，避免随机写的出现。
此外，我们在Worker端通过心跳线程和Master通信，在执行分配的任务时用Exec方式启动一个新的进程来执行具体的Map和Reduce任务。而传输任务使用启动线程用Socket进行传输。
我们在此基础上，实现了MapReduce的系统，我们的设计在实现上有很多和Google不同之处，也不同于开源的Hadoop2。在完成原型的开发和测试后，针对性能和系统的评估成为了我们亟待解决的关键问题。我们由此开始系统地对MapReduce和类似相关系统进行分析和评估，我们相信对于MapReduce和类似系统的研究工作的下一步将是对此类系统的优化。
所以对当前系统的分析和评估成为关键，找到系统使用中的瓶颈所在，针对用户需求的目标进行改进，都是实际应用中的重要问题。我们在Tplatform的实现基础上，开发了一系列的基准程序，细致地分析了系统中可能出现的问题。

系统评估
我们总结了如下的一系列标准，用以衡量并行计算框架系统的各方面性能表现。
评估目标
单任务延迟
总机器时间
平均结束时间
加速比
公平性
故障恢复稳定性
单任务延迟主要衡量单个任务在提交到得到响应（成功、失败或者取消）的时间，考虑的是系统和用户的交互能力。低延迟可以提高系统和用户的交互能力，有利于用户更快地知道提交任务后的结果。
总机器时间主要衡量在系统运行过程中所有机器的用时，考虑的是整个系统的计算能力。对于同样的任务和数据，更少的总机器时间说明了系统能有更少的计算资源（机器和时间）去完成同样的事情。
平均结束时间主要从多个任务的完成情况来考虑系统的性能。由于系统的目标在于统筹整个数据中心的计算资源，所以在多个任务的并行运行的情况下系统的吞吐量是值得关注的对象。
加速比考虑系统对计算任务的加速比，主要衡量系统的扩展性能力，计算不同规模的机群节点下对任务完成情况的提高比率。
公平性考虑在多任务同时运行的情况下，衡量系统对待各个任务的公平性。对于一些任务系统理应优先执行，而对于一些任务系统应该延后执行。由于公平性是一个比较宽泛且见仁见智的问题，我们只是针对此问题提出了一些基本的任务执行场景和评估方法。
故障恢复稳定性衡量的是系统的故障恢复能力和稳定性。众所周知的是，MapReduce这样的系统通常需要运行在超大规模的集群上，故障是同种类型的系统需要处理的正常问题，所以在故障下的恢复和稳定性应该成为此类系统的评估目标。
基准程序和数据
数据库领域中设计了非常成功的TPC-*程序作为测试和调优的基准程序，但是在分布式计算引擎中，并没有公认的代表程序集作为基准程序。一个优秀的基准程序集合对于系统的性能调优、不同系统的对比、调度的决策、机群的管理和资源的利用等等都应该给出统一和明确有效的衡量标准。
基于如上考虑和系统调优的现实需求，同时考察了同类系统的测量程序集，我们初步给出如下程序集作为基准程序，并设计了一系列的指标作为衡量参数。
基准程序集合
基准程序集合应该是以能够代表系统的应用程序为目标，最有代表性的是真正运行于实际系统的程序集合。但是选择基准程序集合却只能尽量挑选关键程序，使得它们在各方面的指标上都具有代表性。
我们选取了下列的程序作为基准程序，它们主要涵盖了应用程序的关键领域：搜索引擎的重要应用（PageRank、 Reverse Index）、日常分析和统计（Word Count、 String Match）、科学计算（矩阵乘法）、Web Mining（Kmeans、 Linear Regression）、卫星图像处理（Histogram）以及典型的Map和Reduce两阶段处理的计算（PennySort）。同时我们使用不同大小的数据集来考虑系统的数据局部性和扩展性的能力，并考虑把单机的性能结果作为加速比测试的基准线。
Word Count
Word Count也是一个MapReduce的典型处理过程，它对在一些数据中出现的词汇进行计数。在我们的测试中，我们在CWT200G中文网页数据集上做词频统计计算，此实验用来测试系统处理大规模数据时的可靠性和稳定性。map函数分析每个HTML网页，去除HTML标签，进行中文分词，以每个中文词为键，值为1输出键值对。reduce函数把聚合到一起的各个值加起来得到总的词频。程序允许是要做本地合并（local combine），这样可以极大的减少网络传输的数据量。
PennySort
PennySort是Jim Gray提出来的一个benchmark程序[ Gray, J. Sort benchmark home page. http://research.microsoft.com/ research/barc/SortBenchmark/default.htm. ]。实验中随机生成长度为100字节的记录，要求对其进行排序。PennySort使用一个MapReduce来完成，其程序的处理过程也是MapReduce的典型处理。先由Map函数提取记录的前10个字节作为键，剩余记录作为值输出键值对。而Reduce函数接受分割后的数据作为输入，进行排序。而分区函数根据键的范围进行分区，可以进行区段分割，从而在各个Reduce完成后完成了整个数据的排序过程。所以这个排序程序也可以作为MapReduce系统的基准测试程序。
PageRank
有很多链接分析技术用来对Web网络结构进行分析。Pagerank是其中最重要的一个，它描述了一个网页的重要程度[ Brin, S., and Page, L. The anatomy of a large-scale hypertextual (Web) search engine. proceedings of WWW, 1998.]，它被认为可以极大的提高搜索引擎检索结果的精度。一个网页的PageRank的计算公式如下：
PR(A)=(1-d)+d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))
其中，假设网页A有n个网页T1...Tn指向它，$C(A)$表示网页A向外的链接的数量。d是一个取值在0到1之间的阻尼因子，一般取0.85。根据这个公式，网页的PageRank可以通过若干轮迭代得到，并且可以证明迭代会收敛。
使用MapReduce计算PageRank的过程分为两个阶段。第一阶段，构建链接图。map函数分析一个网页，把网页URL作为键，改网页初始PageRank值，以及它所包含所有指出的URL作为值输出，即URL -> (PR(URL),URL_1,URL_2,...,URL_n)。这个过程可以和前面所述的任何网页分析的map过程结合到一起进行。reduce函数不做处理，把输入直接作为输出。
第二个阶段，以第一阶段得到的链接图作为输入，以下MapReduce计算迭代若干次直到收敛。map函数把输入记录映射为(URL-> URL_1, URL_2, ..., URL_n)和 (URL_1-> PR(URL)/C(URL)), (URL_2-> PR(URL)/C(URL))等。在reduce阶段，按照公式把同一个URL的各个值求和得到网页的新的PageRank值，在按照原输入的格式输出。之后，用一个串行程序比较上一轮得到的PageRank值和本轮得到的值是否已经收敛，如果未收敛，则进入下一轮迭代。
在我们的实验中，我们使用的数据模拟Web的链接分布，我们生成若干个URL，链出URL的个数依Zip-f分布。
KMeans
KMeans程序是数据挖掘中的基础算法。它要求把一个点集聚合成若干个簇，簇间的点尽可能的聚合在一起。对于是用MapReduce来处理此程序，需要多次的迭代过程，所以KMeans程序也可以代表需要不断迭代的程序集合。
在每一次的迭代过程中，Map任务读入点集数据中的一个子集，并把中心点向量读入，以中心点向量来判断每一个点是否应该输入那个中心下的簇。它计算出每个点和中心点向量中的距离并把点分派给最近的簇。而Reduce任务把相同簇的点都聚合到一起，然后重新计算它们的中心点，然后更新中心点向量。
一轮迭代结束后，KMeans程序会继续迭代直到满足收敛条件为止。收敛的条件一般为两轮对比各个簇没有大的变化就可以停止迭代。
Matrix Multiplication
矩阵乘法是一个计算密集型的任务。Map任务计算输出矩阵中的一个行，然后对矩阵中的每个元素返回位置和值。Reduce收集数据并输出。
评估目标
对于上述选定的基准程序集合，我们从MapReduce的模型和系统实现出发，考虑它们的各项属性。从而可以通过这些属性来对基准程序进行评估，知道它们对MapReduce系统的影响是什么类型的。
从另一方面来说，如果有新的基准程序加入，同样考虑对这些数据属性进行评估，就可以知道此程序的性质，如是否是数据密集型，是否导致MapReduce系统的传输成为瓶颈等等。
我们考虑这些指标，如果有特殊领域的应用程序，那可以根据这些属性值集合建立对应的基准程序，从而方便地对系统进行评估。
基准程序的衡量指标如下[ Berkeley, Hadoop Benchmark. http://radlab.cs.berkeley.edu/wiki/Projects/Hadoop_Benchmark/Data]：
任务大小：输入的数据字节数，Map和Reduce任务的数目。
Map任务的选择度：在平均的Map任务中，输出的字节数除以输入的字节数
Reduce任务的选择度：在平均的Reduce任务中，输出的字节数除以输入的字节数
Map任务的平均字节计算时间：在Map任务中计算一个字节需要的平均时间
Reduce任务的平均字节计算时间：在Reduce任务中计算一个字节需要的平均时间
数据的压缩率：分布式文件系统中该基准程序的数据压缩率。（注：在我们的实验中暂不考虑此项属性）
Map的方式：是选择一部分数据还是对Chunk中所有数据进行顺序读入。
传输的方式：在进行传输任务时时候有偏移，对数据的分割状况是怎么样的，是否做到分割上的负债均衡。
中间数据大小：传输的时候中间数据的字节数。
Reduce的参数：是否需要数据做外排。
Map任务的复杂度：比如，为O(n)
Reduce任务的复杂度：比如，为O(n)
我们选择能够代表典型MapReduce过程的PennySort，来实例说明基准程序在我们的实验系统上各指标的值。
实验数据是50M条记录的PennySort，数据量为4.8G。

表格 1-50M PennySort系统评估
任务大小输入4.8G，Map任务75个，Reduce14个
Map任务的选择度 1
Reduce任务的选择度 1
Map任务的平均字节计算时间 1.72621E-06 Seconds
Reduce任务的平均字节计算时间 7.63296E-07 Seconds
数据的压缩率暂不考虑
Map的方式对Chunk所有数据顺序读入
传输的方式均匀分布
中间数据大小 4.23G
Reduce的参数不需要外排
Map任务的复杂度 O(n)
Reduce任务的复杂度 nO(logn)

我们说明和分析表中的数值。
首先，Map和Reduce的任务的选择度都是1，因为对于PennySort来说，Map做的是把数据简单地读入，然后进行传输和分割，而对Reduce来说，进行完数据的排序后也只需要把数据简单地输出，所以选择度都是1.
然后，对于传输的方式，按记录的生成原则，可以均称地进行hash分割。中间数据比初始读入的数据反而小是因为很多数据Map任务做完后可以在本地直接进行Reduce，利用的数据的空间数据性，所以传输数据变小。
最后Reduce任务需要进行排序，系统实现使用快排，复杂度为nO(logn).
系统监控和程序概要分析
更好地理解和监控云计算的基础设施系统如MapReduce是一个烦人且亟待解决的问题。现有的实现都是比较简单地记录系统的相关性能信息，而且并没有太多关于在此类系统中如何监控和评估的工作。但是在我们的开发和使用过程中，我们发现了系统的性能概要分析很重要，或者说通过更好地理解底层系统，能够更好地改善和优化现有的系统。例如如下的几个场景中，我们将说明这一点:
数据中心中的一个程序员向系统提交了一个用高层语言如Pig Latin描述的任务后，他/她可能想知道他的任务做到什么程度。从性能概要分析的角度来考虑任务监控这个问题，任务在多个机器上的性能分布很重要。这样可以知道任务中最耗时的函数，从来让程序员可以针对此考虑改进自己的程序，或者在系统对任务的编译中进行优化。
失效在数据中心里面是正常的1。MapReduce这样的系统对用户掩盖机器的失效，如果机器发生宕机，系统将处理并调度计算重执行；而对于计算任务的失效，处理方式是重新执行，如果多次失效超过一定次数，将放弃执行。这是因为在数据中心中，很有可能是用户提交的任务的程序中存在BUG，或者是数据有不满足格式而导致无法读入等等。对于需要进行长任务处理的工作来说，在现有系统的实现下，可能是一件极消耗用户程序员精力的事情。可能的情形是，执行了很久到快结束的时候由于BUG或者存储的问题导致失败而最终放弃。而实时的监控和交互可以部分地解决这个问题，让用户及时地知道系统里面发生的情况，对于系统无法做出判断的事情（程序有错），交给用户去解决不失为一个可行的方案。
分布式系统中的一个很重要的措施就是要保证负载均衡，这对于并行计算的框架来说，同样意义重大。在计算的过程中记录性能信息和进行监控，可以通知用户或者系统。通过重新的调度或者其他手段使得负载尽可能均衡。
总之，通过监控和程序的性能概要分析，我们可以让系统和用户之间有更多交互。同时给出的数据可以帮助用以评估系统，提供给不同的人如用户或者系统开发人员分析。
实现细节
我们需要记录一个子任务的运行时性能概要信息，通过以下的数据结构来实现。
         struct ProfileInfo
         {
             // for map task
             int mapFanIn;
             int mapFanOut;
             int mapRecordNumber;
             int localCombineFanIn;
             int localCombineFanOut;
             int localCombineRecordNumber;
             // for reduce task
             int reduceFanIn;
             int reduceFanOut;
             int reduceRecordNumber
             // for transfer task
             int transferIO;
             int transferRecordNumber;
             // cost time, by seconds
             int taskCostTime;
         };
对于Map阶段，分别记录扇入扇出的数据大小、map的记录个数；以及做localcombine的扇入扇出、记录个数；对于Reduce阶段，记录扇入扇出的数据大小、reduce的记录个数；还有传输任务的传输数据量；最后是各个任务的花费时间。
通过在Worker端执行任务后记录下任务的性能概要情况，然后通过文件管道传递给Worker的心跳进程，然后通过心跳捎带给Master以供分析。
进行捎带处理的心跳使用rpc实现，具体实现如下。
先使用ICE的slice描述rpc的接口。
             /**
              * report to the master the task is successfully completed.
              *
              * @param taskID
              * @param profileInfo, send the profileInfo piggybackly
              */
             idempotent void completeTask(Address workerAddress, int taskID, ProfileInfo taskProfile);

然后经过ICE的编译后生成服务器端和客户端的C++代码，然后把任务的性能概要信息发送给Master端。

评估实验
在这一章中，我们将对上一章中设定的系统性能指标进行评估。并阐述每一项实验的环境、应用程序和结果分析。
机群配置
我们的机群配置如下。
我们在后备任务策略的评估实验中使用了一台Master、十四台Worker组成的MapReduce系统集群。所有的机器都是Dell 2850服务器，每台机器配置为2颗Intel Xeon处理器，2GB内存，6个7200 rpm SCSI硬盘组成一个RAID-0的逻辑卷。这些机器存放在两个机架中，各有一台Dell 2748 1Gbps交换机，机器通过一个1Gbps的全双工以太网卡与交换机相连接，两个机架通过一个Cisco千兆路由器链接。
实验结果
单任务延迟和总机器时间
我们使用的工作负载的数据规模如下：
WordCount，1.2G大小的数据，使用LocalCombine。
PennySort，50M条记录共4.8G大小的数据。
PageRank，150W条URL共1.5G大小的数据。
我们实验所得到的单任务延迟和总机器时间如下：
表格 2-延迟和总机器时间
Type/Time secs Latency Total Machine
WordCount 132 2013
PennySort 270 4789
PageRank 140 727
其中，单任务延迟为用户提交任务到任务完全结束所用时间。而总机器时间为提交任务的各个子任务（包括Map、Reduce、Transfer三种任务）的完成时间之和，度量的是对于整个机群来说的总机器时间。
平均结束时间
我们使用上一节中的三个评估任务，同时提交给系统，并得到平均的结束时间。用以衡量在一段时间内，系统对多个任务的吞吐量。我们以平均结束时间来进行评估。
经过实验得到三个任务的平均结束时间为212秒，而由上一节数据可知三任务的平均延迟为180.6秒，所以我们可以通过此项评估来考虑系统是否能够对一批任务进行优化处理。我们对我们的系统进行分析和实时监控，发现之所以慢于平均延迟，是因为对于Word Count和PageRank的一些Map被安排到比较靠后的位置执行，虽然机群中有空闲的机器，但是整个系统需要等待这些Map任务执行完后才能执行Reduce任务，从而增加了延迟。
这也使得我们考虑后备任务的策略和更加合理的调度，使得空闲的资源能够充分被利用，改善这些系统的评估目标。
加速比
加速比和系统的可扩展性是MapReduce和类似系统的一个很重要的特性，正是因为非常良好的可扩展性，才使得MapReduce和其他的分布式系统区别开来，因为MapReduce系统可以很好地部署在超大规模的机群上。
在本节的实验里面，我们从两方面来考察系统的可扩展性。
第一个实验测试在同一个规模的输入数据和相同的配置下，Worker的增加对提交任务的延迟的影响。我们限制每台机器可以同时运行的任务是3，传输任务的限制是2。我们针对5.2.1中的工作负载进行实验，从图中可以看到，运行的任务延迟随Worker的增加而降低，说明此系统有良好的加速比。

第二个实验测试在不同的规模和相同的配置下进行，Worker的增加和数据规模成同样的比例。从图中可以看到，运行的任务延迟基本保持同样的水平，表明此系统有良好的可扩展性。我们的数据规模分别为：
WordCount，1.2G、2.4G、3.6G
PennySort，50M条记录共4.8G、100M条记录共9.6G、150M条记录共14.5G。
PageRank，150W条URL共1.5G、300W条URL共3.4G、450W条URL共6G。
注意PageRank由于相互间链接增加的原因数据规模增加斜率大于线性增加。这三个不同大小的数据集合分别在5、10、14台机器上运行。
实验结果如下：
公平性
对于公平的定义，在不同的应用场合有不同的评估方法，我们在这一节的评估中，简单地先考虑一种场景，并评估我们系统的公平性。
我们进行如下的实验：先提交一个长任务，然后过一段时间提交一个短任务。评估系统的调度对此短任务来说是否公平。
我们准备的长任务是500M条记录的PennySort，数据规模为50G，在我们以前的实验中，我们的系统大约需要2900秒才能完成此任务，它属于长任务。同时我们准备了一个短任务，是10M条记录的PennySort，数据规模是960M，在我们以前的实验中大约只需要50秒就能完成。这里我们使用的任务类型是一样的，都是做排序，我们仅仅考虑任务的完成时间对公平性的影响，在实际应用中可能还会考虑提交任务的权重等等，这些具体的应用不是我们考虑的范围。这里长任务我们记为L（long）任务，短任务我们记为S（short）任务。
通过实验我们发现，由于S任务的很多子任务没有得到及时调度，在S任务提交后，经过356秒才完成了S任务，而最后L任务的延迟为2791秒，基本没有受到短任务的影响。但是由于调度的不合理，对于S任务来说调度是不公平的，它提交了很长一段时间后部分子任务才得到处理。
故障恢复稳定性
在分析和测试评估MapReduce和类似系统时，一个重要的方面就是这些系统的容错性，因为各种故障在这样的系统中是属于正常情况的。
我们通过实验模拟各种故障的发生：如杀死Worker进程模拟宕机、硬盘写满或其他模拟硬盘出错、突然中断一些Worker之间的网络通信等等。利用这些模拟的实验来评估系统的稳定性。
实验表明，一个高稳定性的系统才能在这样的环境中良好地工作。我们系统的稳定性也是未来工作的一个方向。
实验结果和性能问题分析
我们通过实验和分析系统，发现了一些系统的性能问题。列举一些我们觉得目前可能成为瓶颈的如下：
一些机器相较别的机器的慢速，成为落后者，会极大地增加任务完成的延迟。
由下图可以看到，大部分的任务完成时间趋同，而个别任务显著地比其他任务慢，导致最终的延迟降低，成为落后者。这就是落后者的问题表现。

首页上一页 1 2 下一页尾页 1/2/2