【毕业学位论文】（Word原稿）MapReduce的系统性能评估与Backup调度策略-计算机科学与技术网络与分布式系统

本科生毕业论文 题目： (中文 ) 系统性能评估与( 英文 ) 名： 学 号： 00548179 院 系： 信息科学技术学院 专 业： 计算机科学与技术 指导教师 ： 彭波 二一六年七月九日 北京大学本科生学位论文 2 北京大学本科毕业论文导师评阅表 学生姓名 陈日闪 学生学号 00548179 论文成绩 学院（系） 信息科学技术学院 学生所在专业 计算机 导师 姓名 彭波 导师单位 / 所在研究所 网络与信息系统 导师职称 讲师 论文题目 （中、英文） 系统性能评估与 度策略 师评语 （ 包含对论文的性质、难度、分量、综合训练等是否符合培养目标的目的等评价 ） 陈日闪同学的论文选题是海量数据处理基础设施中的 布式计算平台的性能评估和优化。这个方向是目前云计算热潮中重要的技术问题之一，也是本实验室在研究和开发 现环境 面临亟需解决的问题，是进一步工作的基础。其选题合理，是一个探索和工程结合的工作，其难度和工作量适中。 陈日闪以系统性能分析，寻找系统性能优化点为目标，讨论了 行系统的性能评估指标和方法，设计 了 基准 测试程序集 ， 在 统上开展了若干评估实验。通过实验结果分析，给出了若干系统改进的建议，并在落后者问题上，具体通过修改任务调度算法来实现了一个优化改进。这一系列工作连贯，工作内容包括论文阅读，查考文献，系统和算法设计，性能评估实验，编码调试，分布式系统运行和部署等。本论文工作，作为一个科研综合训练完成得很好，符合培养目标。同时，本论文工作也存在一些不足，在深度和系统性上还可以更加深入，比如加入相关系统的对比实验，扩展更多的实验设计和分析等，这些可以在 陈日闪同学进一步工作中来完善。 导师签名： 年 月 日 北京大学本科生学位论文 i 摘要 一个在海量数据上进行数据处理的并行编程模型，它特别适合于海量非结构化和结构化数据的搜索、分析和挖掘任务，已经开始被人们广泛使用。对于兴起的众多类似 统来说，如何有效地评估和分析对比这些系统，成为当前一个需要解决的问题。 本文详细讨论了针对 行系统的性能评估指标和方法，设计和选择一系列具有代表性的程序和数据作为基准，用来评估和分析 统。在这一评估方法指导下，本文在我们自己实现的 行系统 台上扩展了 能，然后进行了一系列评估实验，来分析和寻找系统性能瓶颈，为未来系统优化提供依据。通过实验我们发现了我们系统的一些可改进的问题如任务调度、落后者问题等等。我们选择了针对导致提交任务延迟增加的落后者问题，通过实现后备任务策略来尝试改进。经模 拟实验结果显示，我们提出的改进策略能够有效地改进落后者问题的性能问题。 关键词： 能评估， 落后者问题，后备任务策略 北京大学本科生学位论文 i is an It is to as on It is a to in We a of as we in We of we as We by we 京大学本科生学位论文 录 第 1 章 引言 . 4 第 2 章 架 . 6 型介绍 . 6 统实现 . 6 实现 . 8 第 3 章 系统评估 . 10 估目标 . 10 准程序和数据 . 10 准程序集合 . 11 估目标 . 13 第 4 章 系统监控和程序概要分析 . 15 现细节 . 15 第 5 章 评估实 验 . 17 群配置 . 17 验结果 . 17 任务延迟和总机器时间 . 17 均结束时间 . 18 速比 . 18 平性 . 20 障恢复稳定性 . 20 验结果和性能问题分析 . 20 销分析 . 22 第 6 章 后备任务调度策略 . 24 题描述 . 24 关工作 . 24 . 24 . 25 构环境中后备任务调度 . 25 现细节 . 26 体框架 . 26 后者判定策略 . 26 统处理过程 . 28 据结构细节 . 28 备任务策略评估实验 . 29 群配置和任务准备 . 29 务耗时趋同性分析 . 29 北京大学本科生学位论文 后备任务策略评估 . 30 第 7 章 系统优化方向 . 33 络传输问题 . 33 加用户和系统的交互 . 33 数据库领域看系统性能的其他提升空间 . 34 统易用性 . 34 第 8 章 总结 . 35 北京大学本科生学位论文 4 第 1 章 引言 在成为人们在海量数据上进行并行计算的重要编程模型，比如为大规模的网页做索引、在海量的数据中进行挖掘、庞大的科学计算任务等等。 人们开始关注在普通计算机上实现大规模的并行计算以提供各种服务，无疑是这 方面的先驱者。 用 为日常计算的引擎，将 每天处理 20数据 1存在底层的存储系统如 误 !未定义书签。 、误 !未定义书签。 中 。很多重要的搜索引擎服务，如索引、网页排序、网页消重与去噪、用户日志分析、用户行为预测等等，都可以使用 此外， 是一个如今很受欢迎的并行计算模型。 好的可扩展性使得并行处理变得很容易，人们可以很方便地把 署到大规模的廉价机群上使用。它的开源实现版本 今很多公司如 及部分研究机构和大学如 等都开始使用 行研究和开发。 为了更好和方便地让程序员使用 者类似的并行处理计算框架如 误 !未定义书签。 ，人们在其上架设了一系列的编译系统，并通过高层的语言把计算任务映射为底层的 务。这方面的工作如在 实现的 现的 类似系统的开发和研究也层出不穷，如微软有自己的 误 !未定义书签。 /统 。拥有这样的处理能力无疑成为一个互联网公司的核心竞争力，可以预见在未来的一段时间里面，还有类似的很多系统和研究出现。 人们在使用 者类似的其他并行处理计算框架及其上层语言时，众多的使用者对底层大规模并行处理计算框架有自己的需求。比如大学或研究机构使用此类框架进行科学计算时，系统的工作负载可能是偏向计算密集型，人们也关心系统对于计算任务的延迟反应；而大型因特网公司如 的数据中心中，有若干程序员在同时提交计算任务，程序员不但关心计算任务的延迟，还关心整个中心中负载的调度公平性；而对于此类系统的开发和研究人员来说，他们关心系统的吞吐量、系统中各机器的状态和使用情况等等。所以考虑此类并行处理计算框架特别是 统的各项系统指标，并确定评估的程序和方法，对评估类似系统、基于用户希望的系统设计折衷进行系统之间的比较、改进系统等等有很重要的意义。 在这个基础上如有一些系统测试的工作如分析网络的性能 ，以及对统和数据库系统性能评估的讨论 16。 我们基于 现了自己的并行处理计算框架，并在其之上进行了北京大学本科生学位论文 5 系统的测试和评估。我们提出了测试程序和数据，并基于此在系统中实现了监控和程序性能概要分析框架。通过测试和评估实验，我们总结了系统的性能指标和观察到的问题。我们针对其中的单机落后问题，实现并验证了 后备任务 策略，并基于此改进系统性能。最后，我们总结并给出了其他工作方向。 论文的剩余部分按如下方式进行组织。 第二章对 模型和体系结构进行概述 ， 而第三章列出了需要评估的系统目标和 我们设计的基准程序和数据集合。 为了分析和评估系统，我们在第四章阐述了系统监控框架和程序概要分析的设计和实现细节。 之后我们在第五章中列出了实验结果和给出了实验的分析，并在针对其中的落后者问题实现了后备任务策略，在第六章中详细阐述了后备任务策略的实现和实验评估。 我们在第七章中对 系统可能的优化方向进行了展望并在第八章中进行了总结 ， 最后是致谢 。 北京大学本科生学位论文 6 第 2 章 在这一章里面，我们将简单介绍 架的模型和 我们的系统实现。 研究人员受到函数式编程语言（ 启发，在总结大量的大规模分布式处理程序共同特征的基础上，提出了 行程序框架。 一大类大规模并行数据处理程序的抽象。这类计算的输入是一个（键，值）对的集合，输出也是一个（键，值）对的集合。用户只需要提供两个操作 实现， 行时库就可以自动把用户程序并行化。 用户提供 数的实现，它接收一个输入对，产生一组 中间结果对。他们传给 户提供的 数，接收中间结果的一个键和具有此键的一组值，处理这些值，产生若干个（键，值）对做为输出。它们的一般形式如下： 7 - - 型的最大好处是简便性，用户只需要提供这两个接口就可以处理大规模的数据，而不需要太多分布式计算的实现细节。 统 实现 实时运行主要是为并行化和并发执行服务的。 为了尽可能的并行化和扩展系统， 输入的数据分割到多个机器上。 中间数据的传输和序列化处理等由系统来控制。分割的数据由多个 处理。 这两个步骤中 务和 可以同时执行，且它们都具有良好的可扩展性，也即可以方便地增加机器增加并发度。 而在系统实现的层面上，系统需要决定底层的各个细节如数据单元的大小、中间数据的处理、内存的缓存多大、 排序的方式、 各个任务的调度、 机器的失败和容错处理等等。 系统自动的把这些细节都掩盖，所以对 程序员来说，他只需要知道这个编程模型并编写 程序即可。 论文中描述了他们在分布式机群系统上对 实现。系统把输入数据划分为 M 份数据片，这些输入数据片可以在不同的机器上并发的北京大学本科生学位论文 7 被 数处理。所有的中间结果对使用一个分区函数（ 为 R 份。然后，对于每个分区，通过排序把具有相同键的所有（键，值）对聚合到一起，用 数处理，最后产生 R 个输出文件。 R 的值和分区函数可以由用户指定，系统默认的分区函数是 1。 现是构建在 上的，所有的 序的输入和输出都是存储在 的文件。由于 的数据都有多个副本，当执行 机群和运行 机群是同一个时， 的调度模块会尽量把 务分配到存储数据的机器上本地运行，这样可以避免输入数据的网络传输，极大的提高性能。此外，用户可以指定函数用来把原始输入数据转换为 数 的输入，用户也可以指定函数用来把 输出结果序列化为输出数据。 体系结构图 1如下 ： 数据的流图 8如下， 别执行本地的任务，可能是 务、 务。整个过程由 制和协调调度。 图表 1 北京大学本科生学位论文 8 我们实现的类似平台是 我们 自己也实现了一个自制 的立在 似的 分布式文件 系统 9。 设计上与 小的设置 9。 与 供运行时库然后通过一个二进制程序的多个副本扮演不同角色的方式不同，我们的实现提供的是一个执行 业的服务，用户把编写好的实现指定接口的动态链接库用系统提供的 交上来， 统就会自动调度和运行相关的任务。服务由一台主控（ 器和若干台工作机（ 成， 责把用户提交的作业（ 分为若干个任务，然后调度他们在各台工作机上执行。相比提供运行时库由用户编译为一个程序的方式，这样做的好处是，系统的改进升级对用户是不可见的。如果系统的实现改变了，只要 改变，用户无需改变代码甚至不需要重新编译生成动态链接库就可以执行 给我们未来系统的升级优化带来了极大的便利。不仅如此，在 果同一个机群有多个作业在同时运行，因为作业由主控程序负责调度但一个作业的主控程序是不知道另一个作业的存在的，所以多个作业之 间可能产生资源的互相抢占。而在我们的系统中，一个机群只有一个主控程序，主控程序 可以综合各个作业的情况对所有任务整体进行调度。 这里需要详细说明我们任务设计的细节。 我们把 要做的任务分成三个类型： 们图表 2 北京大学本科生学位论文 9 把传输任务从原来的 在这里我们对此设计有如下的分析。 在原来的 务的执行流程和设计下，对于 行完生成的中间数据，是由 到 器上通过远程调用取得 。这些 有可能出现的场景是很多 时来一台 器上进行取数据操作，造成 器对硬盘的随机写，而随机写对性能的影响是很大的 ，这样的数据传输模型可以称之为 “拉 ”。 而我们把传输任务独立开来，由 度控制，可以控制 输的时间，同时 同时接到多个传输任务的数据时可以做缓存，避免随机写的出现。 此外，我们在 通过心跳线程和 信， 在执行分配的任务时用 式启动一个新的进程来执行具体的 务。而传输任务使用启动线程用 行传输。 我们 在此基础上， 实现了 系统 ，我们的设计在实现上有很多和 同之处，也不同于开源的 完成原型的开发和测试后，针对性能和系统的评估成为了我们亟待解决的关键问题。 我们由此开始系统地对类似相关系统进行分析和评估，我们相信对于 类似系统的研究 工作 的下一步 将 是对此类系统的优化。 所以对当前系统的分析和评估成为关键，找到系统使用中 的瓶颈所在，针对用户需求的目标进行改进，都是实际应用中的重要问题。我们在 实现基础上，开发了一系列的基准程序，细致地分析了系统中可能出现的问题。 北京大学本科生学位论文 10 第 3 章 系统评估 我们总结了如下的一系列标准，用以衡量并行计算框架系统的各方面性能表现。 估目标 1） 单任务延迟 2） 总机器时间 3） 平均结束时间 4） 加速比 5） 公平性 6） 故障恢复稳定性 单任务延迟主要衡量单个任务在提交到得到响应（成功、失败或者取消）的时间，考虑的是系统和用户的交互能力。低延迟可以提高系统和用户的交互能力，有利于用户更快地知道提交任务后的结果。 总机器 时间主要衡量在系统运行过程中所有机器的用时，考虑的是整个系统的计算能力。对于同样的任务和数据，更少的总机器时间说明了系统能有更少的计算资源（机器和时间）去完成同样的事情。 平均结束时间主要从多个任务的完成情况来考虑系统的性能。由于系统的目标在于统筹整个数据中心的计算资源，所以在多个任务的并行运行的情况下系统的吞吐量是值得关注的对象。 加速比考虑系统对计算任务的加速比，主要衡量系统的扩展性能力，计算不同规模的机群节点下对任务完成情况的提高比率。 公平性考虑在多任务同时运行的情况下，衡量系统对待各 个 任务的公平性 。对于一些任务系统理应优先执行，而对于一些任务系统应该延后执行。 由于公平性是一个比较宽泛且见仁见智的问题，我们只是针对此问题提出了一些基本的任务执行场景和评估方法。 故障恢复稳定性衡量的是系统的故障恢复能力和稳定性。众所周知的是，样的系统通常需要运行在超大规模的集群上，故障是同种类型的系统需要处理的正常问题，所以在故障下的恢复和稳定性应该成为此类系统的评估目标。 准程序和数据 数据库领域中设计了非常成功的 序作为测试和调优的基准程序，但北京大学本科生学位论文 11 是在分布式计算引擎中，并没有公认的代表程 序集作为基准程序。一个优秀的基准程序集合对于系统的性能调优、不同系统的对比、调度的决策、机群的管理和资源的利用等等都应该给出统一和明确有效的衡量标准。 基于如上考虑和系统调优的现实需求，同时考察了同类系统的测量程序集，我们初步给出如下程序集作为基准程序，并设计了一系列的指标作为衡量参数。 准程序集合 基准程序集合应该是以能够代表系统的应用程序为目标，最有代表性的是真正运行于实际系统的程序集合。但是选择基准程序集合却只能尽量挑选关键程序，使得它们在各方面的指标上都具有代表性。 我们选取了下列的程序作为基准程 序，它们主要涵盖了应用程序的关键领域：搜索引擎的重要应用（ 日常分析和统计（ 科学计算（矩阵乘法）、 卫星图像处理（ 及典型的 阶段处理的计算（ 同时我们使用不同大小的数据集 来考虑系统的数据局部性和扩展性的能力，并 考虑把单机的性能结果作为加速比测试的基准线。 是一个 典型处理过程，它对在一些数据中出现的词汇进行计数 。在我们的测试中，我们在 文网页数据集上做词频统计计算，此实验用来测试系统处理大规模数据时的可靠性和稳定性。 数分析每个 页，去除 签，进行中文分词，以每个中文词为键，值为 1 输出键值对。 数把聚合到一起的各个值加起来得到总的词频。程序允许是要做本地合并（ 这样可以极大的减少网络传输的数据量。 出来的一个 序 10。实验中随机生成长度为 100 字节的记录，要求对其进行排序。 用一个 完成，其程序的处理过程也是 典型处理。先由 数提取记录的前 10 个字节作为键，剩余记录作为值输出键值对。而 数接受分割后的数据作为输入，进行排序。而分区函数根据键的范围进行分区，可以进行区段分割，从而在各个 成后完成了整个数据的排序过程。 所以这个排序程序也可以作为 统的基准测试程序。 北京大学本科生学位论文 12 很多链接分析技术用来对 络结构进行分析。 其中最重要的一个，它描述了一个网页的重要程度 11，它被认为可以极大的提高搜索引擎检索结果的精度。一个网页的 计算公式如下： )=(1d(1)/C(.+n)/C( 其中，假设网页 A 有 n 个网页 向它， $C(A)$表示网页 A 向外的链接的数量。 d 是一个取值在 0 到 1 之间的阻尼因子，一般取 据这个公式，网页的 以通过若干轮迭代得到，并且可 以证明迭代会收敛。 使用 算 过程分为两个阶段。第一阶段，构建链接图。 数分析一个网页，把网页 为键，改网页初始 ，以及 它 所 包 含 所 有 指 出 的 为 值 输 出 ， 即 (.,这个过程可以和前面所述的任何网页分析的 程结合到一起进行。 数不做处理，把输入直接作为输出。 第二个阶段，以第一阶段得到的链接图作为输入，以下 算迭代若干次直到收敛。 数把 输入记录映射为 (., (C(, (C(等。在照公式把同一个 按照原输入的格式输出。之后，用一个串行程序比较上一轮得到的 果未收敛，则进入下一轮迭代。 在我们的实验中，我们使用的数据模拟 链接分布，我们生成若干个出 个数依 布。 序是数据挖掘中的基础算法。 它要求把一个点集聚合成若干个簇，簇间的点尽可能的聚合在一起。 对于是用 处理此程序，需要多次的迭代过程 ，所以 序也可以代表需要不断迭代的程序集合。 在每一次的迭代过程中， 务读入点集 数据中 的一个子集，并把中心点向量读入，以中心点向量来判断每一个点是否应该输入那个中心下的簇。 它计算出每个点和中心点向量中的距离并把点分派给最近的簇。 而 务把相同簇的点都聚合到一起，然后重新计算它们的中心点，然后更新中心点 向量。 一轮迭代结束后， 序会继续迭代直到满足收敛条件为止。收敛的条件一般为两轮对比各个簇没有大的变化就可以停止迭代。 北京大学本科生学位论文 13 阵乘法 是一个 计算密集型的任务。 务 计算输出矩阵中的一个行，然后对矩阵中的每个元素返回位置和值 。 集数据并输出。 估目标 对于 上述选定的基准程序集合，我们从 模型和系统实现出发，考虑它们的各项属性。从而可以通过这些属性来对基准程序进行评估，知道它们对 统的影响是什么类型的。 从另 一方面来说，如果有新的基准程序加入，同样考虑对这些数据属性进行评估，就可以知道此程序的性质，如是否是数据密集型，是否导致 我们考虑这些指标，如果有特殊领域的应用程序，那可以根据这些属性值 集合 建立对应的基准程序，从而 方便 地对系统进行评估。 基准程序的 衡量指标 如下 12： 1） 任务大小：输入的数据字节数， 务的数目。 2） 务的选择度：在平均的 务中，输出的字节数除以输入的字节数 3） 务的选择度：在平均的 务中，输出的字节数除以 输入的字节数 4） 务的平均字节计算时间 ： 在 务中计算一个字节需要的平均时间 5） 务的平均字节计算时间：在 务中计算一个字节需要的平均时间 6） 数据的压缩率 ： 分布式文件系统中该基准程序的数据压缩率。（注：在我们的实验中暂不考虑此项属性） 7） 方式： 是选择一部分数据还是对 所有数据进行顺序读 入 。 8） 传输的方式 ： 在进行传输任务时时候有偏移 ，对数据的分割状况是怎么样的 ，是否做到分割上的负债均衡。 9） 中间数据大小： 传输的时候中间数据的字节数。 10） 参数：是否需要数据做外 排。 11） 务的复杂度：比如，为 O(n) 12） 务的复杂度：比如，为 O(n) 我们选择能够代表典型 程的 实例说明基准程序在我们的实验系统上各指标的值。 实验数据是 50M 条记录的 据量为 北京大学本科生学位论文 14 表格 1任务大小 输入 务 75 个， 务的选择度 1 务的选择度 1 务的平均字节计算时间 务的平均字节计算时间 据的压缩率 暂不考虑 方式 对 有数据顺序读入 传输的 方式 均匀分布 中间数据大小 参数 不需要外排 务的复杂度 O(n) 务的复杂度 nO(我们说明和分析 表中的 数值。 首先， 任务的选择度都是 1，因为对于 说，的是把数据简单地读入，然后进行传输和分 割，而对 说，进行完数据的排序后也只需要把数据简单地输出，所以选择度都是 1. 然后，对于 传输 的方式，按记录的生成原则，可以均称地进行 割。中间数据比初始读入的数据反而小是因为很多数据 务做完后可以在本地直接进行 用的数据的空间数据性，所以传输数据变小。 最后 务需要进行排序，系统实现使用快排，复杂度为 nO( 北京大学本科生学位论文 15 第 4 章 系统监控和程序概要分析 更好地理解和监控云计算的基础设施系统如 一个烦人且亟待解决的问题。现有的实现都是比较简单地记录 系统的相关性能信息，而且并没有太多关于在此类系统中如何监控和评估的工作。但是在我们的开发和使用过程中，我们发现了系统的性能概要分析很重要，或者说通过更好地理解底层系统，能够更好地改善和优化现有的系统。例如如下的几个场景中，我们将说明这一点 : 数据中心中的一个程序员向系统提交了一个用高层语言如 述的任务后，他 /她可能想知道他的任务做到什么程度。从性能概要分析的角度来考虑任务监控这个问题，任务在多个机器上的性能分布很重要。这样可以知道任务中最耗时的函数，从来让程序员可以针对此考虑改进自己的程序 ，或者在系统对任务的编译中进行优化。 失效在数据中心里面是正常的 1。 样的系统对用户掩盖机器的失效，如果机器发生宕机，系统将处理并调度计算重执行；而对于计算任务的失效，处理方式是重新执行，如果多次失效超过一定次数，将放弃执行。这是因为在数据中心中， 很有可能是用户提交的任务的程序中存在 者是数据有不满足格式而导致无法读入等等。对于需要进行长任务处理的工作来说，在现有系统的实现下，可能是 一件极消耗用户程序员精力的事情。可能的情形是，执行了很久到快结束的时候由于 者存储的问题导致失败而最终放弃。 而实时的监控和交互可以部分地解决这个问题，让用户及时地知道系统里面发生的情况，对于系统无法做出判断的事情（程序有错），交给用户去解决不失为一个可行的方案。 分布式系统中的一个很重要的措施就是要保证负载均衡，这对于并行计算的框架来说，同样意义重大。在计算的过程中记录性能信息和进行监控，可以通知用户或者系统。通过重新的调度或者其他手段使得负载尽可能均衡。 总之，通过监控和程序的性能概要分析，我们可 以让系统和用户之间有更多交互。同时给出的数据可以帮助用以评估系统，提供给不同的人如用户或者系统开发人员分析。 现细节 我们需要记录一个子任务的运行时性能概要信息，通过以下的数据结构来实现。 / 京大学本科生学位论文 16 ; ; , by ; 对于 段，分别记录扇入扇出的数据大小、 记录个数；以及做扇入扇出、记录个数；对于 段，记录扇入扇出的数据大小、 记录个数；还有传输任务的传输数据量；最后是各个任务的花费时间。 通过在 执行任务后记录下任务的性能概要情况，然后通过文件管道传递给 心跳进程，然后通过心跳捎带给 供分析。 进行捎带处理的心跳使用 现，具体实现如下。 先使用 述 接口。 /* * to is * * ( 然后经过 编译后生成服务器端和客户端的 C+代码，然后把任务的性能概要信息发送给 。 北京大学本科生学位论文 17 第 5 章 评估实验 在这一章 中，我们将对上一章中设定的系统性能指标进行评估。 并阐述每一项实验的环境、应用程序和结果分析。 群配置 我们的机群配置如下。 我们在后