刘帅
摘要：MpRdu编程模型是分布式计算中最常用的编程模型，其主要目的是将单个巨大计算任务分割成多个小计算任务，并分别交由不同的计算机去处理。MpRdu将任务分成p阶段和rdu阶段，每个阶段都是用y/vlu键值对作为输入和输出。针对MpRdu中Mp数量少，Rdu数量多的情况，文章将Mp阶段任务中的Ky值进行二次划分，提出一种MpRdu编程模型中Ky二次分类的方法。实验，证明该方法能够在原有基础上提高数据处理效率。
关键词：MpRdu；Ky/vlu；二次分类
中图分类号：TP30文献标志码：A文章编号：006-8228（208）03-58-02
TtslssftlrthfKyvluMpRduprrdl
LuShu
（DprttfCputrApplt，XzhuVtldThlCll，Xzhu，Shx034000，Ch）
Abstrt：MpRduprrdlsthstlyusdprrdlthdstrbutdputItdvdsslhuputtstultplsllputtss，hhrprssdbydffrtputrsrsptvlyMpRdudvdsthtstthMpphsdthRduphs，hfhhsusdsputdutputththy/vluyvluprIvfthftthtthubrfMpMpRdusslldthubrfRduslr，thKyvlufMpphstssdvddtts，dthdfttslssftfKyvluMpRduprrdlsprpsdExprtsshthtththdprvthffyfdtprssthrlbss
Kyrds：MpRdu；Ky/Vlu；ttslssft
0引言
MpRdu是由l公司提出的一種并行计算框架[-2]，其“分而治之”的思想被广泛用于Hdp与Spr分布式计算平台。MpRdu处理任务过程中，将任务分为Mp阶段与Rdu阶段，Mp阶段负责将数据按一定规则整理成键值对的形式，Rdu阶段负责将相同Ky值的键值对进行规约处理，从而使任务相对独立，方便于进行分布式处理[3-4]。
针对MpRdu编程模型，目前大多数的研究是在MpRdu编程思想结合现有分布式平台的使用。对于MpRdu自身思想的改进并不很多[5-6]。本文通过分析MpRdu编程模型中Mp阶段与Rdu阶段任务的处理过程，发现会存在Ky值数量少但Vlu值数量多的情况，针对此类任务处理的负载不均衡现象，给出一种MpRdu编程模型中y值二次分类的算法，通过增加Ky值的标记，使Vlu值能够更加均匀的分布在集群不同处理节点上，提高了集群节点的利用率与数据处理效率。
MpRdu模型
基本原理
MpRdu编程模型[7-8]是一个处理和生成超大数据集的算法模型的相关实现。此模型首先创建一个Mp函数处理一个基于键值对的数据集合，输出中间的基于键值对的数据集合；然后再创建一个Rdu函数用来合并所有的具有相同中间y值的中间vlu值。基于MpRdu架构所设计的程序能够在大量的普通配置的计算机上实现数据的并行化处理，并且处理过程着重于输入数据分割、任务调度、容错处理和计算机通信管理等。
2处理过程
图MpRdu处理过程
MpRdu编程模型中，Mp与Rdu处理过程如图所示。若有多个任务等待处理，Mp任务的主要功能是将数据处理成以“y=”为基础的键值对的形式（以y=和y=2为例），Rdu任务的主要功能是将不同Ky的键值对进行整合。则有如下定义。
定义若不同y值为基础的键值对数量相差不大，则执行Rdu任务的计算节点的负载相差不大，称为集群呈负载均衡状态（LBS状态），反之则称为集群呈负载不均衡状态（LIS状态）。
2y值二次分类
2y值传统分类（TC）
在传统MpRdu编程模型中，Mp任务是将待处理数据处理为为键值对的形式，而Rdu任务是收集具有相同y值的键值对，并对分别其进行处理。当不同y值对应的vlu值的个数相差很大时，会出现数据分布不均匀的情况。
{vlu，vlu2，vlu3，…vlu}&t;（为0^3数量级）
{vlu，vlu2，vlu3，…vlu}&t;
（为0^9数据量级）
明显地，y所对应的vlu数据量远小于y2所对应的vlu数据量。数据处理过程中，y值往往选择明显区分的标记，而不会对y的值进行改变，因此在分布式处理过程常存在LIS状态。
22二次分类（TTC）
虽然MpRdu框架只能机械地按y值对数据进行划分，然而，在Mp过程之后，检测到同一y值的vlu数据量（N）超过阈值ε，则对该y值添加二级标号（例如y，会转化为y，y2，…，y），进行二次分类，使得所有y值具有相似数量的vlu数据量，集群呈LBS状态。
其主要过程如下。
Stp：输入数据集DS，设计Mp函数，将数据集处理为键值对。
Stp2：设计Rdu函数，计算每个y值所对应的vlu值数据量；选出所有y值中，vlu数据量的最大值Mx所对应的y。
Stp3：设计Mp函数，将具有Mx的y值做二级标记，进行二次划分。
Stp4：若vlu数据量N&t;ε，返回Stp3。
3实验结果及分析
3实验准备
实验选用CtOS6系统，Hdp27作为实验平台，算法实现使用Jv语言编写。分别使用Abl数据集、Arrhyth数据集、Chss数据集、Multpl数据集作为处理对象，分别使用TC思想与TTC思想实现最大值算法。
32实验结果及分析
不同数据集在两种不同思想算法下的时间开销如表所示。
表时间开销
[数据集 时间开销T（s） TC TTC Abl292 203 Arrhyth 246 62 Chss 34 84 Multpl 006 764 ]
由实验结果可以得出，TTC算法比TC算法效率高，大约节省30%的时间。因此，TTC算法弥补了传统MpRdu编程模型中对y值分類的不足，使集群尽量趋于LBS状态，对于分布式计算性能的提升提供了一种较为有效的借鉴方案。
参考文献（Rfrs）：
[]KurR，MslyB，VsslvtsS，tlFstGrdy
AlrthsMpRdudStr[J]ATrstsPrlllCput，2052（3）：4
[2]张卫平，刘纪平，仇阿根等一种分布式计算的空间离群点挖
掘算法[J]测绘科学，20742（8）：85-90
[3]潘景昌，王杰，姜斌等一种基于Mp/Rdu分布式计算的
恒星光谱分类方法[J]光谱学与光谱分析，20636（8）：265-2654
[4]VrA，ChrsvL，CpbllRHRsur
PrvsrfrMpRduJbsthPrfrGls[J]LturNtsCputrS，2057049：65-86
[5]李成华，张新访，金海等MpRdu：新型的分布式并行计算
编程模型[J]计算机工程与科学，2033（3）：29-35
[6]卢鑫，陈华辉，董一鸿等MpRdu框架下的不确定数据
Tp-查询计算[J]模式识别与人工智能，20326（7）：688-694
[7]翟俊海，张明阳，王婷婷等基于哈希技术和MpRdu的大
数据集K-近邻算法[J]计算机科学，20744（7）：20-24
[8]毛典辉基于MpRdu的Cpy-Ks改进算法[J]
计算机工程与应用，20248（27）：22-26
文章来源于：计算机时代