MapReduce海量数据并行处理总结

MapReduce海量数据并行处理复习大纲Ch.1.并行计算技术简介1.为什么需要并行计算？提高计算机性能有哪些基本技术手段提高字长，流水线微体系结构技术，提高集成度，提升主频迫切需要发展并行计算技术的主要原因1)单处理器性能提升达到极限2)爆炸性增长的大规模数据量2)超大的计算量/计算复杂度2.并行计算技术的分类有哪些主要的并行计算分类方法？1)按数据和指令处理结构：弗林(Flynn)分类2)按并行类型3)按存储访问构架4)按系统类型5)按计算特征6)按并行程序设计模型/方法1)按数据和指令处理结构：弗林(Flynn)分类SISD：单指令单数据流传统的单处理器串行处理SIMD：单指令多数据流向量机，信号处理系统MISD：多指令单数据流很少使用MIMD：多指令多数据流最常用，TOP500高性能计算机基本都属于MIMD类型2)按并行类型分类位级并行（Bit-LevelParallelism）指令级并行（ILP：Instruction-LevelParallelism）线程级并行（Thread-LevelParallelism）数据级并行：一个大的数据块划分为小块，分别由不同的处理器/线程处理任务级并行：一个大的计算任务划分为子任务分别由不同的处理器/线程来处理3)按存储访问结构分类A.共享内存（SharedMemory)所有处理器通过总线共享内存多核处理器，SMP……也称为UMA结构(UniformMemoryAccess)B.分布共享存储体系结构各个处理器有本地存储器同时再共享一个全局的存储器C.分布式内存（DistributedMemory)各个处理器使用本地独立的存储器B和C也统称为NUMA结构(Non-UniformMemoryAccess)4)按系统类型分类多核/众核并行计算系统MC(Multicore/Manycore)或Chip-levelmultiprocessing,CMP对称多处理系统SMP(SymmetricMultiprocessing)多个相同类型处理器通过总线连接并共享存储器大规模并行处理MPP(MassiveParallelProcessing)专用内联网连接一组处理器形成的一个计算系统集群（Cluster）网络连接的一组商品计算机构成的计算系统网格（Grid）用网络连接远距离分布的一组异构计算机构成的计算系统5)按并行程序设计模型/方法分类共享内存变量(SharedMemoryVariables)消息传递方式(MessagePassing）MapReduce方式3.并行计算的主要技术问题并行计算有哪些方面的主要技术问题？多核/多处理器网络互连结构技术存储访问体系结构分布式数据与文件管理并行计算任务分解与算法设计并行程序设计模型和方法数据同步访问和通信控制可靠性设计与容错技术并行计算软件框架平台系统性能评价和程序并行度评估如何评估程序的可并行度(Amdahl定律)程序能得到多大并行加速依赖于该程序有多少可并行计算的比例。经典的程序并行加速评估公式Amdahl定律：NPPS)1(1其中，S是加速比，P是程序可并行比例，N是处理器数目根据Amdahl定律：一个并行程序可加速程度是有限制的，并非可无限加速，并非处理器越多越好并行比例vs加速比50%=最大2倍75%=最大4倍90%=最大10倍95%=最大20倍4.MPI并行程序设计MessagePassingInterface，基于消息传递的高性能并行计算编程接口5.什么是MapReduce概念MapReduce是面向大规模数据并行处理的：（1）基于集群的高性能并行计算平台(ClusterInfrastructure)，（硬件层）允许用市场上现成的普通PC或性能较高的刀架或机架式服务器，构成一个包含数千个节点的分布式并行计算集群（2）并行程序开发与运行框架(SoftwareFramework)（逻辑层）系统自动提供了一个庞大但设计精良的并行计算软件构架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行子任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算中的很多复杂细节交由系统负责处理，大大减少了软件开发人员的负担（3）并行程序设计模型与方法(ProgrammingModel&Methodology)（用户层）借助于函数式Lisp语言中的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了完整的并行编程接口，完成大规模数据处理6.为什么MapReduce如此重要？1)高效的大规模数据处理方法2)第一个不同于冯诺依曼结构的、基于集群而非单机的计算方式的重大突破3)目前为止最为成功的基于大规模计算资源的并行计算抽象方法CH.2.MapReduce简介1.MapReduce的基本模型和处理思想1）对大数据分而治之；2）构建抽象模型-Map和Reduce，用户仅需要描述做什么，不需要关心怎么做3）提供统一的构架并完成以下的主要功能·任务调度·数据/代码互定位·出错处理·分布式数据文件管理·Combiner和Partitioner（设计目的和作用）2.Combiner和Partitioner设计目的和作用带宽优化（Combiner的设计目的和作用），不会改变key-value的形式用数据分区解决数据相关性问题（Partitioner的设计目的和作用）例如：有一个巨大的数组,其最终结果需要排序,每个Map节点数据处理好后,为了避免在每个Reduce节点本地排序完成后还需要进行全局排序,我们可以使用一个分区策略如:(d%R),d为数据大小，R为Reduce节点的个数，则可根据数据的大小将其划分到指定数据范围的Reduce节点上,每个Reduce将本地数据拍好序后即为最终结果Ch.3.Google/HadoopMapReduce基本构架1.GoogleMapReduce的基本工作原理1）GoogleMapReduce并行处理的基本过程1.有一个待处理的大数据，被划分为大小相同的数据块(如64MB),及与此相应的用户作业程序2.系统中有一个负责调度的主节点(Master),以及数据Map和Reduce工作节点(Worker)3.用户作业程序提交给主节点4.主节点为作业程序寻找和配备可用的Map节点，并将程序传送给map节点5.主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点6.主节点启动每个Map节点执行程序，每个map节点尽可能读取本地或本机架的数据进行计算7.每个Map节点处理读取的数据块,并做一些数据整理工作(combining,sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置8.主节点等所有Map节点计算完成后，开始启动Reduce节点运行；Reduce节点从主节点所掌握的中间结果数据位置信息，远程读取这些数据9.Reduce节点计算结果汇总输出到一个结果文件即获得整个处理结果2）失效处理主节点失效主节点中会周期性地设置检查点(checkpoint)，检查整个计算作业的执行情况，一旦某个任务失效，可以从最近有效的检查点开始重新执行，避免从头开始计算的时间浪费，主节点采用热备。工作节点失效工作节点失效是很普遍发生的，主节点会周期性地给工作节点发送检测命令，如果工作节点没有回应，这认为该工作节点失效，主节点将终止该工作节点的任务并把失效的任务重新调度到其它工作节点上重新执行。3）计算优化问题如果有一个计算量大、或者由于某个问题导致很慢结束的Map节点，则会成为严重的“拖后腿者”。解决方案把一个Map计算任务让多个Map节点同时做，取最快完成者的计算结果2.分布式文件系统GFS的基本工作原理1）GoogleGFS的基本设计原则廉价本地磁盘分布存储多数据自动备份解决可靠性为上层的MapReduce计算框架提供支撑2）GoogleGFS的基本构架和工作原理GFSMasterMaster上保存了GFS文件系统的三种元数据：命名空间(NameSpace),即整个分布式文件系统的目录结构Chunk与文件名的映射表Chunk副本的位置信息，每一个Chunk默认有3个副本前两种元数据可通过操作日志提供容错处理能力；第3个元数据直接保存在ChunkServer上，Master启动或ChunkServer注册时自动完成在ChunkServer上元数据的生成；因此，当Master失效时，只要ChunkServer数据保存完好，可迅速恢复Master上的元数据。GFSChunkServer即用来保存大量实际数据的数据服务器。GFS中每个数据块划分默认为64MB，这是因为处理的文件都比较大，所以设置成64MB比较合理每个数据块会分别在3个(缺省情况下)不同的地方复制副本；对每一个数据块，仅当3个副本都更新成功时，才认为数据保存成功。当某个副本失效时，Master会自动将正确的副本数据进行复制以保证足够的副本数GFS上存储的数据块副本，在物理上以一个本地的Linux操作系统的文件形式存储，每一个数据块再划分为64KB的子块，每个子快有一个32位的校验和，读数据时会检查校验和以保证使用为有效的数据。数据访问工作过程1.在程序运行前，数据已经存储在GFS文件系统中；程序实行时应用程序会告诉GFSServer所要访问的文件名或者数据块索引是什么2.GFSServer根据文件名会数据块索引在其文件目录空间中查找和定位该文件或数据块，并找数据块在具体哪些ChunkServer上；将这些位置信息回送给应用程序3.应用程序根据GFSServer返回的具体Chunk数据块位置信息，直接访问相应的ChunkServer优点：并发访问，解决mater拥堵。3.分布式结构化数据表BigTable1)BigTable设计动机和目标需要存储管理海量的结构化半结构化数据海量的服务请求商用数据库无法适用2)目标广泛的适用性:为一系列服务和应用而设计的数据存储系统,可满足对不同类型数据的存储和操作需求很强的可扩展性:根据需要可随时自动加入或撤销服务器节点高吞吐量数据访问:提供P级数据存储能力，每秒数百万次的访问请求高可用性和容错性:保证系统在各种情况下度能正常运转，服务不中断自动管理能力：自动加入和撤销服务器，自动负载平衡简单性：系统设计尽量简单以减少复杂性和出错率2)BigTable数据模型—多维表通过行、列、时间戳一个行关键字(rowkey)一个列关键字(columnkey)一个时间戳(timestamp)进行索引和查询定位的。行：列：时间戳：3）BigTable基本构架主服务器新子表分配子表监控：通过Chubby完成。负债均衡：子表服务器负载均衡操作子表服务器BigTable中的数据都以子表形式保存在子表服务器上，客户端程序也直接和子表服务器通信。子表的基本存储结构SSTable，一个SSTable实际上对应于GFS中的一个64MB的数据块(Chunk)，SSTable中的数据进一步划分为64KB的子块。一个子表服务器上的子表将进一步由很多个SSTAble构成，每个SSTable构成最终的在底层GFS中的存储单位。一个SSTable还可以为不同的子表所共享，以避免同样数据的重复存储。子表寻址子表地址以3级B+树形式进行索引；首先从Chubby服务器中取得根子表，由根子表找到二级索引子表，最后获取最终的SSTable的位置Index64Kblock64Kblock64KblockSSTable4.Hadoop分布式文件系统HDFS1）HDFS基本构架2）HDFS数据分布设计多副本数据块形式存储，按照块的方式随机选择存储节点，默认副本数目是33）HDFS可靠性与出错恢复DataNode节点的检测心跳：NameNode不断检测DataNode是否有效若失效，则寻找新的节点替代，将失效节点数据重新分布集群负载均衡数据一致性:校验和checksum主节点元数据失效MultipleFsImageandEditLogCh