一、引言

    随着信息技术的发展，人们对于大数据量的信息处理要求也越来越高，传统的基于单机数据库的处理方式已经无法承担大规模的数据量。尤其是手机产业的兴起，网络用户的数量巨增，对信息的响应速度和处理时间的要求也越来越苛刻。相比之下，对信息的准确性的要求不再那么严格，比如实时路况的处理等等。

    MapReduce框架是一种成功的想法，它被Google提出并已经被应用于多种运用，比如网页搜索和网页排序。它类似于现在的数据库系统，输入是key／value对，通过用户自定义一个map函数，将输人数据进行预处理，将相同的key的value发送到reduce端，然后这些value进行排序，由reduce函数进行处理，最后输出也是key／value对，这种编程模型现在很多应用中得以实现，而且很多传统的算法也可以通过变形在上面实现。

    MapReduce框架对处理传统的大数据量的信息很有优势，比如网页排序等。但随着网络用户的增加和对及时信息的需求，框架本身的局限性就显示出来，比如任务的准备时间和reduce阶段之前的排序时间太长等等，这些限制使得MapReduae不能够胜任流式信息的处理，对于MapReduce框架的这些短处，我们设计了一种新的FastMR，它对MapReudce框架做了一些改变，并用。语言实现了一个雏形，使它能够处理流式数据，性能优于现在的MapReudce框架。

    二、模型框架

    根据实际需要，我们设计了自己的MapReduce框架，即FasfMR。和Google的MapReduce框架类似，我们的从结点既是任务结点也是存储结点。我们的设计的目的是完成流式信息的处理，所以和传统的MapReduce框架有很大差别，主要体现在以下几个方面：

    1.任务获取方式

    在MapReduce模型中，采用的是主从式的任务获取方式。在一个集群中，有一个Master结点用来管理任务的执行，Master结点的负载相对较重，它需要负责接受客户端的任务、调度任务的执行。客户端将任务代码上传到分布式文件系统，然后通知Mater结点有任务到来。Master将任务信息加入等待任务列表。集群中的结点采用Slave方式运行，定期以心跳的方式连接Master，报告任务运行情况和请求任务。心跳的过程是通过RPC方式连接到Master，在报告的同时顺便请求任务。这种方式对于Slave来说，对任务的获取是有延迟的，不能够及时的得到任务执行。首先，这种方式会有任务获取的延迟。对于实时性要求非常苛刻的环境下，10秒种的获取任务延迟是不被允许的。其次，影响Map任务的本地化执行。例如，某一时刻，有一个Slave来请求任务，Master是不知道结点的情况的，只能根据这个结点的信息，给与该任务相应的输入数据，这个数据可能不在这个结点上，因为无法保证来请求的Slave结点都具有该任务的数据。

    FastMR的任务报告和任务获取是分开的，任务报告保留以前的RPC方式，而任务的获取采用阻塞方式，即Slave中有任务槽的结点与Master结点保持一个TCP连接，Master结点建立一个表，负责维护这些连接，当有客户端有作业提交的时候，Master结点通过配置的调度方式，分配任务给Slave结点。

    这种方式是FastMR针对云计算平台的改进，它可以减少任务获取的延迟和Map任务的本地化，因为在任务开始时，结点信息在Master中，Master对能够执行任务的结点不再是一无所知，它可以做到最大程度上的调度任务执行，来满足本地化要求。

    2.数据传递方式

    MapReduce模型中数据的传递有两种方式。首先在任务刚开始执行的时候，数据是通过分布式文件系统传递给Map任务，Map任务执行完以后，会将数据在本地执行Combine，在此过程中进行一个局部排序，然后保存到本地磁盘，等待其他Slave来取数据。当任务中所有的Map任务都执行完以后，Master统计任务中的执行情况然后进人Shuffle阶段，这时候Reduce任务的结点向Map任务结点获取数据。Shuffle阶段是MapReduce模型的核心，是保证并行性的关键。因为任务运行时，为了挖掘集群的潜力，需要将任务进行划分，获取最大程度上的并行眭。任务执行过程中有两次任务划分，在任务开始的时候，是通过对输入数据进行划分来分配任务，而在Map执行完以后reduce任务开始之前，是通过Shuffle方法进行划分，Shuffle阶段通常采用Hash的方式划分任务，或者客户端自己定义划分的方法。Shuffle阶段是Reduce任务结点向Map任务结点请求数据，采用Http请求的方式。这种方式对于注重吞吐率、稳定性和整体效率的后台是比较适宜的，但它不适合用于移动云计算平台。因为同步以及拉的方式在时间性能上都远不如推的方式。

    FastMR的改进是将Map端的数据在执行完以后直接推送出去，这种数据传递的方式可能要结合FastMR的另外两个改进才能做到，它们分别是流水式的任务执行方式和取消MapReduce中的排序阶段，采用推的方式结合和FastMR的特点能够很大程度上缩短任务的执行时间。

[page]    3.流水式的任务执行

    MapReduce任务中的Map阶段执行完以后会有一段同步时间，同步完以后Map任务将开启一个http端口供Reduce任务读取数据， 同步在MapReduce任务中是必须的，因为Reduce任务在运行前有排序阶段，需要得到完整的数据，这里就需要所有的map任务都运行结束才能得到。当一个任务出现错误的时候，MapReduce模型需要将任务进行重新调度运行，其他结点需要等待这个任务运行完成才能再运行，这个作业就阻塞在这个需要重新运行的结点上，这样非常影响作业的运行时间。

    FastMR的设想是将任务的运行看成是流水的方式，任务执行的过程中没有明的同步障。这种运行方式带来的好处是提高了单一任务的执行速度，符合移动云计算的需求。这种任务的运行类似与MapReduce Online的管道式的运行方式，在前一个任务还没有运行完的时候后一个任务就开始运行，事前可以根据集群的具体情况配置流水线的级数，然后集群根据这个参数执行，随着流水线级数的增加，任务的执行速度会提高很多，因为多级流水更加适合集群的任务调度，不过集群对任务的管理会增加复杂性。

    4.取消排序阶段

    MapReduce模型在Map任务执行完以后会在Map任务端执行排序，然后传到RedLIce任务端再进行归并排序，这个阶段对于Google的很多后台应用是非常有用的。同时，这个阶段也是相当耗时的，尤其是在超大规模的数据处理过程中更是如此。我们设想了很多移动云计算的应用，发现较多的移动云计算的应用对数据的排序基本没有要求。于是基于这个设想，可以将复杂费时的排序选用或者取消（如果保留，需要改变先前的排序方式，因为任务是流水的方式运行，任务之间没有同步）。我们的设想是如果保留排序，则进行局部排序，而且我们发现多数作业如果是由多个任务构成，那么一个任务产生的中间结果不会影响最终结果（中间会产生一些没有的输出）。当然也有例外的情况，所以流水线的方式不适合多有的应用。

    5.细粒度的任务设定

    MapReduce编程模型中的错误恢复机制继承了Google的一贯简单高效的作风，采用了最简单的方式，如果错误发生，则重新运行作业的机制。这种错误恢复机制非常简单，然而一旦发生错误，作业的执行时间将会非常长。

    FastMR采用的方式是细化一个任务的颗粒度，划分方式是通过输入数据进行块划分和记录数据偏移的方式。如果任务运行的结点出现异常，则错误恢复时只是将未处理的数据进行恢复。因为数据处理量不是实时记录的，所以可能出现已经处理过的数据重新处理一遍的情况，对于这种情况，对于集群来说并没有太大的影响，因为在Reduce任务端对这种冗余的数据可以简单的合并掉。

    三、设计细节

    为了提高系统的运行效率，采用e语言来实现设计，采用主结点管理名字空间，数据结点采用redis数据库模拟的方式，redis是一个高性能的数据库，吞吐率较高，尽管redis的数据本身没有标签，对于实验环境，将不同的标签的数据作为不同的值存储，能够满足实验的要求。

    FastMR中的通信均采用了redis数据传输协议，比如“*3 $3 SET $5＼nmykey $8 ＼nmyvalue＼ne 其中每个参数用＼r＼n分割，第一个 3说明有3个参数，后面一个$3说明这个参数有3个字节，这种通信协议容易实现并且易于解析。

    Master为Slave提供了多个远程调用的接口，比如SubmiOob，GetNewTask等等，这些接口均采用remote procedure calls的方式。利用redis通信协议，易于实现传输数据的序列化，每次RPC返回的数据也很容易实现反序列化。

[page]    四、性能分析

    为测试FastMR的性能，采用求无向图中一个点到其他点最短路径的算法。这个算法满足编程模型的需要，有多轮并且每一轮的map和reduce函数是一样的。

    算法设计思想

    该算法是Belman—F0rd算法的一种变形，在每轮开始信息的保存方式是这样的：

    Key=结点，Value=距离+当前最短路径（没有则为空）+邻接点及距离列表

    系统运行的过程

    map端：对于每个邻接点，最短路径上添加一个边，并修改最短路径的距离值为其自反加距离，发送出去。

    Reduce端：收集相同Key的Value，获取一个距离值最小的Value做为Reduce的结果，然后结束本轮。

    每轮总的时间复杂度是O（E），分布在多台机器上执行，要求有多少个结点就要运行多少轮，所以不同量级的结点数和边数将可能导致效率差别很大。

    五、结论和未来工作

    我们设计并简单实现了FastMR，通过实验，发现FastMR对采用的算法的实现性能是高效的，认为它可以满足流式计算的需求。

    我们已经证实了设想的正确性，现在开始实现完整的内存文件系统，包括实现其动态扩展性、容错性以及高吞吐率，下一步将改进FastMR的作业管理机制和实现错误恢复机制，准备将调度从代码中独立出来，使多种应用实现不同的任务和作业调度算法，类似Hadoop的那种由用户自己配置调度策略等，进而实现由数据改变而触发任务执行的方式，类似与Google的Percolator。

免责声明：本网站（http://www.ciotimes.com/）内容主要来自原创、合作媒体供稿和第三方投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。
本网站刊载的所有内容（包括但不仅限文字、图片、LOGO、音频、视频、软件、程序等）版权归原作者所有。任何单位或个人认为本网站中的内容可能涉嫌侵犯其知识产权或存在不实内容时，请及时通知本站，予以删除。