MapReduce简介

Ch.2.MapReduce简介1.对付大数据处理-分而治之2.构建抽象模型-Map和Reduce3.上升到构架-自动并行化并隐藏低层细节4.MapReduce的主要设计思想和特征大规模数据处理时，MapReduce在三个层面上的基本构思如何对付大数据处理：分而治之对相互间不具有计算依赖关系的大数据，实现并行最自然的办法就是采取分而治之的策略上升到抽象模型：Mapper与ReducerMPI等并行计算方法缺少高层并行编程模型，为了克服这一缺陷，MapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型上升到构架：统一构架，为程序员隐藏系统层细节MPI等并行计算方法缺少统一的计算框架支持，程序员需要考虑数据存储、划分、分发、结果收集、错误恢复等诸多细节；为此，MapReduce设计并提供了统一的计算框架，为程序员隐藏了绝大多数系统层面的处理细节什么样的计算任务可进行并行化计算？并行计算的第一个重要问题是如何划分计算任务或者计算数据以便对划分的子任务或数据块同时进行计算。但一些计算问题恰恰无法进行这样的划分！Ninewomencannothaveababyinonemonth!例如：Fibonacci函数:Fk+2=Fk+Fk+1前后数据项之间存在很强的依赖关系！只能串行计算！结论：不可分拆的计算任务或相互间有依赖关系的数据无法进行并行计算！大数据的并行化计算一个大数据若可以分为具有同样计算过程的数据块，并且这些数据块之间不存在数据依赖关系，则提高处理速度的最好办法就是并行计算例如：假设有一个巨大的2维数据需要处理(比如求每个元素的开立方)，其中对每个元素的处理是相同的,并且数据元素间不存在数据依赖关系,可以考虑不同的划分方法将其划分为子数组,由一组处理器并行处理大数据的并行化计算合并Master：负责划分和分配任务Workder：负责数据块计算大数据任务划分和并行计算模型大数据计算任务子任务子任务子任务子任务……任务划分计算结果结果合并借鉴函数式设计语言Lisp的设计思想函数式程序设计(functionalprogramming)语言Lisp是一种列表处理语言(Listprocessing)，是一种应用于人工智能处理的符号式语言，由MIT的人工智能专家、图灵奖获得者JohnMcCarthy于1958年设计发明。Lisp定义了可对列表元素进行整体处理的各种操作，如：如：(add#(1234)#(4321))将产生结果：#(5555)Lisp中也提供了类似于Map和Reduce的操作如:(map‘vector#+#(12345)#(1011121314))通过定义加法map运算将2个向量相加产生结果#(1113151719)(reduce#’+#(1113151719))通过加法归并产生累加结果75Map:对一组数据元素进行某种重复式的处理Reduce:对Map的中间结果进行某种进一步的结果整理MPI中的数据规约操作ReduceMPI规约操作编程示例—计算积分(参见Ch.1)for(i=myid;iN;i=i+numprocs)/*根据节点数目将N个矩形分为图示的多个颜色组*/{/*每个节点计算一个颜色组的矩形面积并累加*/x=a+i*dx+dx/2;/*以每个矩形的中心点x值计算矩形高度*/local+=x*x*dx;/*矩形面积=高度x宽度=y*dx*/}MPI_Reduce(&local,&inte,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);if(myid==0)/*规约所有节点上的累加和并送到主节点0*/{/*主节点打印累加和*/printf(Theintegalofx*xinregion[%d,%d]=%16.15f\n,a,b,inte);}MPI_Finalize();}Theintegalofx*xinregion[0,10]=333.33345MPI中的数据规约操作Reduce将一组进程的数据按照指定的操作方式规约到一起并传送给一个进程MPI_Reduce(sendbuf,recvbuf,count,datatype,op,root,comm)其中规约操作op可设为下表定义的操作之一：MPI_MAX求最大值MPI_MIN求最小值MPI_SUM求和MPI_PROD求积MPI_LAND逻辑与MPI_BAND按位与MPI_LOR逻辑或MPI_BOR按位或MPI_LXOR逻辑异或MPI_BXOR按位异或MPI_MAXLOC最大值和位置MPI_MINLOC最小值和位置不足：仅能处理以上规定的规约操作，不能实现灵活复杂的规约操作！关系数据库中的聚合函数对一个查询操作的结果列表中的字段表达式进行聚合操作selectOrder_ID,Payment=SUM(Price*Quantity)groupbyOrder_IDSum()计算表达式所有值之和Avg()计算表达式的平均值Count(*)计算某字段中所有值的个数Min()计算表达式的最小值Max()计算表达式的最大值Order_IDItemPriceQuantity1电脑500021打印机400011硬盘80032电脑600012硬盘6002查询结果：Orde_IDPayment116400(5000*2+4000*1+800*3)27200(6000*1+600*2)数据库中的这些聚合函数类似于对表格数据进行的Reduce操作典型的流式大数据问题的特征大量数据记录/元素进行重复处理对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息排序和整理中间结果以利后续处理收集整理中间结果产生最终结果输出MapReduce关键思想：为大数据处理过程中的两个主要处理操作提供一种抽象机制MapReduce中的Map和Reduce操作的抽象描述MapReduce借鉴了函数式程序设计语言Lisp中的思想，定义了如下的Map和Reduce两个抽象的编程接口，由用户去编程实现:map:(k1;v1)[(k2;v2)]输入：键值对(k1;v1)表示的数据处理：文档数据记录(如文本文件中的行，或数据表格中的行)将以“键值对”形式传入map函数；map函数将处理这些键值对，并以另一种键值对形式输出处理的一组键值对中间结果[(k2;v2)]输出：键值对[(k2;v2)]表示的一组中间数据MapReduce中的Map和Reduce操作的抽象描述reduce:(k2;[v2])[(k3;v3)]输入：由map输出的一组键值对[(k2;v2)]将被进行合并处理将同样主键下的不同数值合并到一个列表[v2]中，故reduce的输入为(k2;[v2])处理：对传入的中间结果列表数据进行某种整理或进一步的处理,并产生最终的某种形式的结果输出[(k3;v3)]。输出：最终输出结果[(k3;v3)]Map和Reduce为程序员提供了一个清晰的操作接口抽象描述基于Map和Reduce的并行计算模型海量数据存储……数据划分MapMapMapMap初始kv键值对初始kv键值对初始kv键值对初始kv键值对中间结果(k1,val)(k2,val)(k3,val)(k1,val)(k3,val)(k2,val)(k3,val)(k1,val)(k2,val)(k3,val)Barrier：AggregationandShuffleReduceReduceReduce(k1,values)(k2,values)(k3,values)计算结果(K1,val)(K2,val)(K3,val)基于Map和Reduce的并行计算模型各个map函数对所划分的数据并行处理，从不同的输入数据产生不同的中间结果输出各个reduce也各自并行计算，各自负责处理不同的中间结果数据集合进行reduce处理之前,必须等到所有的map函数做完，因此,在进入reduce前需要有一个同步障(barrier);这个阶段也负责对map的中间结果数据进行收集整理(aggregation&shuffle)处理,以便reduce更有效地计算最终结果最终汇总所有reduce的输出结果即可获得最终结果基于MapReduce的处理过程示例--文档词频统计：WordCount设有4组原始文本数据：Text1:theweatherisgoodText2:todayisgoodText3:goodweatherisgoodText4:todayhasgoodweather传统的串行处理方式(Java)：String[]text=newString[]{“helloworld”,“helloeveryone”,“sayhellotoeveryoneintheworld”｝;HashTableht=newHashTable();for(i=0;i3;++i){StringTokenizerst=newStringTokenizer(text[i]);while(st.hasMoreTokens()){Stringword=st.nextToken();if(!ht.containsKey(word)){ht.put(word,newInteger(1));}else{intwc=((Integer)ht.get(word)).intValue()+1;//计数加1ht.put(word,newInteger(wc));}}}for(Iteratoritr=ht.KeySet().iterator();itr.hasNext();){Stringword=(String)itr.next();System.out.print(word+“:”+(Integer)ht.get(word)+“;”);}输出：good:5;has:1;is:3;the:1;today:2;weather:3基于MapReduce的处理过程示例--文档词频统计：WordCountMapReduce处理方式使用4个map节点：map节点1:输入：(text1,“theweatherisgood”)输出：(the,1),(weather,1),(is,1),(good,1)map节点2:输入：(text2,“todayisgood”)输出：(today,1),(is,1),(good,1)map节点3:输入：(text3,“goodweatherisgood”)输出：(good,1),(weather,1),(is,1),(good,1)map节点4:输入：(text3,“todayhasgoodweather”)输出：(today,1),(has,1),(good,1),(weather,1)基于MapReduce的处理过程示例--文档词频统计：WordCountMapReduce处理方式使用3个reduce节点：reduce节点1:输入：(good,1),(good,1),(good,1),(good,1),(good,1)输出：(good,5)reduce节点2:输入：(has,1),(is,1),(is,1),(is,1),输出：(has,1),(is,3)reduce节点3:输入：(the,1),(today,1),(today,1)(weather,1),(weather,1),(weather,1)输出：(the,1),(today,2),(weather,3)输出：good:5is:3has:1the:1today:2weather:3基于MapReduce的处理过程示例--文档词频统计：WordCountMapReduce处理方式MapReduce伪代码(实现Map和Reduce两个函数)：ClassMappermethodmap(Stringinput_key,Stringinput_value)://input_key:textdocumentname//input_value:documentcontentsforeachwordwininput_val