【摘 要】本论文在研究MapReduce编程模型的基础上，对Maper和Reducer函数的编程流程进行了深入的研究并在Hadoop框架的基础上，进行Kmeans聚类算法的并行设计。在充分熟悉软件工程中设计模式的基础上，结合MapReduce编程模型，在KmeansMapper、KmeansReducer和KmeansDriver的程序设计中分别应用了工厂方法模式、合成模式、代理模式、命令模式来提高软件工程中程序设计的效率。
【关键词】MapReduce编程模型；Kmeans聚类算法；设计模式
0.引言
在软件开发过程中，经常在某一特定场合中遇到某些以前经常出现或感觉似曾相识的问题，直截了当地解决方案就是套用原有的已经过证明的解决方案，或参考别人成熟的思路来解决，久而久之，通过不断完善并文档化就形成了针对这种问题的模式[1]。如今的软件开发对设计模式的依赖程度越来越大，而在研究软件设计模式的过程中，对软件程序设计的效率问题并没有给予足够的重视，本文通过对MapReduce编程模型的使用，将其应用到软件的设计模式当中，从而达到提高软件工程中程序设计的效率目的。
1.相关工作
1.1软件开发过程中的模式
根据软件开发过程[2]，模式又可分为分析模式和设计模式等，设计模式是当前面向对象领域研究的热点，在寻找合适的对象构造软件系统时，设计模式能帮助设计人员确定系统中不明显的对象和潜在有价值的对象，比如描述算法的对象在现实中并不存在，在分析阶段很难把它提取出来，但在特定场合下是实现可重用设计的关键，是使系统更具灵活性的关键，所以有必要提取出来；在设计对象所对应的类时，设计模式可以帮助权衡粒度、可重用性和封装等各种因素；在设计接口形式时，设计模式可以帮助定义好的接口和确定接口之间的关系；在设计可重用的软构件时，设计模式可以帮助确定可重用的类并尽可能地适应系统的变化，总之，各种各样的设计模式可以帮助设计出更加灵活、可重用和易理解的软件。
1.2 MapReduce编程模型过程
MapReduce是一个编程模型以及用来处理和生成大数据集的一个相关实现[3]。在MapReduce中，用户可以通过描述一个map函数，处理一组key/value对进而生成一组key/value对的中间结果，然后描述一个reduce函数，将具有相同key的中间结果进行归并。以这种函数式风格写出来的程序在一个由普通机器组成的集群上自动的进行并行化和执行。这就允许那些没有并行分布式系统编程经验的程序员很容易的使用大型分布式系统的资源。MapReduce操作在我们的实现中的整体流程图如下图1。当用户程序调用MapReduce函数时，将会产生如下的动作序列：
图1 MapReduce操作实现中的整体流程
1.3 K-means聚类算法的简介
K-means聚类算法，也被称为K-均值算法，是一种得到广泛应用的算法。它给定一个含有n个对象的数据集和聚类的个数K，算法将n个数据划分成K个子集，每个子集代表一个聚类，同一聚类中的数据间距较近，而不同聚类的数据间距较远，每个聚类由其中心值来表示[4]。
2.设计模式在MapReduce软件开发中的研究
2.1 Map/Reduce编程框架
MapReduce应用程序运行于Hadoop平台上，它的最基本的组成部分包括一个Mapper和一个Reducer类，以及一个创建JobConf的执行程序。MapReduce应用程序还包括JobTracker（属于master服务）和TaskTracker（属于slaver服务）两个服务类。master负责调度job的每一个子任务task运行于slaver上，并监控它们，如果发现有失败的task就重新运行它，slaver则负责直接执行每一个task。一个完整的job会自动依次执行Mapper、Combiner（在JobConf指定了Combiner时执行）和Reducer，其中Mapper和Combiner是由MapTask调用执行，Reducer则由ReduceTask调用，Combiner实际也是Reducer接口类的实现。图2描述了 Map/Reduce框架中主要组成和它们之间的关系。
图2 Map/Reduce框架中主要组成和它们之间的关系
如果一个类想要成为一个mapper，那么该类需要实现Mapper接口，同时继承自MapReduceBase。在MapReduceBase类中，两个方法是特别需要注意的：void configure（JobConf job）：这个方法是在任务被运行之前调用 void close（）：在任务运行完成之后调用剩下的工作就是编写map方法，这个方法根据
如果一个类想要成为Reducer的话，需要首先实现Reducer接口，然后需要继承自MapReduceBase。当reducer接收从mapper传递而来的key/value对，然后根据key来排序，分组，最终生成
2.2 Mapper和Reducer程序设计中所用的设计模式
工厂方法模式是类的创建模式，又叫做虚拟构造子模式或多态性工厂模式[5]。工厂方法模式的用意是定义一个创建产品对象的工厂接口，将实际创建过程推延到子类中去。
合成模式属于对象的结构模式，又叫部分-整体模式。本文中用到安全方式的合成模式。安全方式的合成模式在抽象树枝角色里声明所有的用来管理子类对象的方法，这样客户端如果使用枝叶来管理子对象程序在编译时就不会通过。不会出现运时期错误。缺点不够透明，树叶类和树枝类将具有不同的接口[6]。
代理模式[7]是对象的结构模式。代理模式给某一个对象提供一个代理对象，并由代理对象控制对原对象的引用。
命令模式是对象的行为模式，这种模式把一个请求或者操作封装到一个对象中，命令模式允许系统使用不同的请求把客户端参数化，对请求排队或者记录请求日志，可以提供命令的撤销和恢复功能。本文中的KeansDriver.java文件中的文件路径和Hadoop文件的配置使用了命令模式。
3.基于MapReduce的K-means聚类并行算法的设计
本论文的MapReduce编程的模型：一个Mapper类，一个Reducer类，一个Driver类，三者关系如图3所示。
图3 Mapper类、Reducer类、Driver类之间的关系
Mapper将输入键值对（key/value pair）映射到一组中间格式的键值对集合。Map是一类将输入记录集转换为中间格式记录集的独立任务。
这种转换的中间格式记录集不需要与输入记录集的类型一致。一个给定的输入键值对可以映射成0个或多个输出键值对。Hadoop Map/Reduce框架为每一个InputSplit产生一个map任务，而每个InputSplit是由该作业的InputFormat产生的。Reducer将与一个key关联的一组中间数值集归约（reduce）为一个更小的数值集。用可以通过 JobConf.setNumReduceTasks（int）设定一个作业中reduce任务的数目。Driver类主要起到文件路径的配置、作业的配置等，其关键的函数代码如下：public class KmeansDriver extends Configured implements Tool {
//number of clusters
private static int mk；
//is go on mapreduce？
private static boolean isGoOn=true；
//temp centoids of all clusters
static ArrayList
static int printUsage（）{
……
}
}
4.结论
面向对象领域取得的最大进展就是设计模式概念的提出和发展，设计模式由于其实用性而受到欢迎。而并行程序的可编程性是并行计算的难点之一，使用传统的方法对非数值问题进行并行求解则更加困难。本论文在对MapReduce的编程模型深入研究的基础上，对MapReducede 的并行程序的设计中采用了工厂方法模式、合成模式、代理模式、命令模式等，通过描述一个map函数，处理一组key/value对进而生成一组key/value对的中间结果，然后描述一个reduce函数，将具有相同key的中间结果进行归并，实现了对传统的编程模式的扩充。随着面向对象理论和并行程序设计的发展，设计模式会得到进一步的充实和发展。■
【参考文献】
[1]LerinaAversano，GerardoCanfora，LuigiCerulo，Concettina Del Grosso，Massimiliano Di Penta."An empirical studyonthe evolution of design patterns."ACM，September3-7，2007，Cavtat near Dubrovnik，Croatia.
[2]Claudia Iacob.A design pattern mining method for interaction design.EICS’11，June13-16，2011，Pisa， Italy.
[3]Linda DiGeronimo，Filomena Ferrucci，Alfonso Murolo，Federica Sarro."A Parallel Genetic Algorithm Based on Hadoop MapReduce for the Automatic Generation of JUnit Test Suites."IEEE，2011.
[4]Songqing Duan，Bin Wu，BaiWang，JuanYang."DESIGNAND IMPLEMENTATION OF PARALLEL STATIATICALALGORITHMBASEDON HADOOP"S MAPREDUCE MODEL."Proceedings of IEEE CCIS2011.
[5]李洋，张文博，魏峻，钟华，黄涛.基于序列模式的Servlet 容器缓存替换[J].软件学报，2007，07.
[6]李长云，阳爱民，满君丰，应晶.一种面向按需集成服务的业务模型构造方法[J].计算机学报，2006，07.
[7]李钢，李增智，王宇，王立.一组移动代理的行为设计模式[J].计算机学报，2002，12.