浅析云计算分布式并行计算：编程模型
【IT168?评论】MapReduce是由Google公司开发的一个针对大规模群组中的海量数据处理的分布式编程模型。它实现了两个功能：Map把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集。而Reduce是把从两个或更多个Map中，通过多个线程，进程或者独立系统并行执行处理的结果集进行分类和归纳。Map()和Reduce()两个函数可能会并行运行，即使不是在同一的系统的同一时刻。
系列文章：
浅析云计算分布式并行计算：系统架构
Dryad平台也是构建微软云计算基础设施重要核心技术之一。要使云计算真正的“落地”主要面临两个重要问题：如何构建与应用程序来紧密结合的大规模底层基础设施?目前构建分布式平台的基础设施主要包括Dryad、Dynamo和MapReduce等框架。
▲图1数据并行计算
另一个问题就是如何通过构建新型的云计算应用程序，能够在网络上提供更加丰富的用户体验?Yahoo扩展了MapReduce并提出了MapReduceMerge框架，并可以应用到多核处理器上。HP则将注意力关注于分布式共享内存的使用上，而不同于MapReduce编程方面。IBM主要使用Linux系统映像以及Hadoop软件(GoogleFileSystem以及MapReduce的开源实现)。微软则自主研发了Dryad和DryadLINQ，并可以用于辅助C#开发人员在计算机集群或数据中心里分布式并行处理大规模的数据，从而在程序执行性能与效率上提高数倍。
Dryad和DryadLINQ是微软硅谷研究院创建的研究项目，主要用来提供一个分布式并行计算平台，DryadLINQ提供一种高级语言接口，使普通程序员可以轻易进行大规模的分布式计算，它结合了微软Dryad和LINQ两种关键技术，被用于在该平台上构建应用。Dryad与微软体系结构中的位置关系，如图2所示。▲图2Dryad与微软体系结构的关系?
Dryad同MapReduce一样，它不仅仅是一种编程模型，同时也是一种高效的任务调度模型。Dryad这种编程模型并不仅适用于云计算，在多核和多处理器以及异构机群上同样有良好的性能。
我们知道在VisualStudio2010C++有一套并行计算编程框架，支持常用的协同任务调度和硬件资源(例如CPU和内存等)管理，通过Workstealing算法可以充分利用细颗粒度并行的优势，来保证空闲的线程依照一定的策略建模，从所有线程队列中“偷取”任务执行，所以能够让任务和数据粒度并行。如果一个耗时的任务只被粗略分割成四个子任务并发执行，即使是在四核心CPU的计算机上运行也无法做到实时动态的负载均衡，可能发生三个子任务很早就完成了，而另一个任务还在一个核上是等待状态。
Dryad与上述并行框架相似，同样可以对计算机和它们的CPU进行调度，不同的是Dryad被设计为伸缩于各种规模的集群计算平台，无论是单台多核计算机还是到由多台计算机组成的集群，甚至拥有数千台计算机的数据中心，可以从任务队列中创建的策略建模来实现分布式并行计算的编程框架。
浅析云计算分布式并行计算：系统架构
2011年03月21日00:05?it168网站原创作者：高阳编辑：胡铭娅?评论：0条
????【IT168?专稿】MapReduce是Google公司设计的分布式计算模型，作为Google公司的核心技术，MapReduce在处理T级别以上巨量数据的业务上有着明显的优势。Google公司MapReduce实现是该公司的保密技术，而来自开源社区Apache的Hadoop项目则是此思想的java克隆版本。微软则通过Dryad平台进行分布式系统应用搭建。上一篇文章中，我们浅析了云计算分布式并行计算的编程模型，由于MapReduce是目前比较流行流行的分布式系统平台，所以本文将重点讲述微软云计算Dryad和Google的MapReduce分布式系统结构。
系列文章：
浅析云计算分布式并行计算：编程模型
浅析云计算分布式并行计算：算法应用
Dryad系统的总体的构建用来支持有向无环图(DirectedAcyclineGraph，DAG)类型数据流的并行程序。Dryad的整体框架根据程序的要求完成调度工作，自动完成任务在各个节点上的运行。在Dryad平台上，每个Dryad工作或并行计算过程被表示为一个有向无环图。图中的每个节点表示一个要执行的程序，节点之间的边表示数据通道中数据的传输方式，其可能是文件、TCPPipe、共享内存等，为了支持数据类型需要针对每个类型有序列化代码。
▲图1Dryad系统结构
如图1所示，当用户使用Dryad平台时，首先是需要在任务管理(JM)节点上建立自己的任务。每一个任务由一些处理过程以及在这些处理过程数据传递组成。任务管理器(JM)获取无环图之后，便会在程序的输入通道准备，当有可用机器的时候便对它进行调度。JM从命名服务器(NS)那里获得一个可用的计算机列表，并通过一个维护进程(PD)来调度这个程序。
系统组件：
任务管理器(JobManager，JM)：每个Job的执行被一个JobManager控制，该组件负责实例化这个Job的工作图;在计算机群上调度节点的执行;监控各个节点的执行情况并收集一些信息;通过重新执行来提供容错;根据用户配置的策略动态地调整工作图;
计算机群(Cluster)：用于执行工作图中的节点;
命名服务器(NameServer，NS)：负责维护Cluster中各个机器的信息;
维护进程(PDaemon，PD)：进程监管与调度工作。
从总体来看，传统的Linux/Unix管道是一维管道，每个节点在管道中是单个的程序。而Dryad的执行过程就可以看做是一个二维的管道流的处理过程。其中，每个节点可以具有多个程序的执行，通过这种算法可以同时处理大规模数据。
▲图2Dryad任务结构
如图2所示，我们可以看到，在每个节点进程(VerticesProcesses)上都有一个处理程序在运行，并且通过数据管道(Channels)的方式在它们之间传送数据。二维的Dryad管道模型定义了一系列的操作，可以用来动态的建立并且改变这个有向无环图。这些操作包括建立新的节点，在节点之间加入边，合并两个图以及对任务的输入和输出进行处理等。
与微软Dryad相似，MapReduce编程模型可用于大规模数据集(大于1TB)的并行运算。概念“Map(映射)”和“Reduce(化简)”，它们的主要思想都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。MapReduce映射处理结构，如图3所示。
▲图3MapReduce映射处理结构
从上图可以看出，MapReduce极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。当前的软件实现是指定一个Map(映射)函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce(化简)函数，用来保证所有映射的键值对中的每一个共享相同的键组。微软Dryad与谷歌的MapReduc映射原理相似，但不同的是通过DryadLINQ来实现分布式程序编程设计。
浅析云计算分布式并行计算：算法应用
2011年03月27日00:05?it168网站原创作者：高阳编辑：胡铭娅?评论：0条
????【IT168?专稿】众所周知MapReduce模型是Google公司在多台普通机器，利用函数式的思想，提高程序执行的性能，而Stanford的Phoenix则是这一模型在多核时代的解决方案。作为GoogleMapReduce技术的开源实现，Hadoop借鉴了谷歌的GoogleFileSystem文件系统、MapReduce并行算法以及BigTable。因此，Hadoop也是一个能够分布式处理大规模海量数据的软件框架，也是一个开源的分布式并行计算平台，它主要由MapReduce的算法执行和一个分布式的文件系统等两部分组成。
系列文章：
浅析云计算分布式运算：编程模型
浅析云计算分布式运算：系统架构
Hadoop是并行工作的，以加快任务处理速度。Hadoop的可扩展依赖于部署Hadoop软件框架计算集群的规模，Hadoop的运算是可扩展的，具有处理PB级数据的能力。虽然Hadoop自身由Java语言开发，但它除了使用Java语言进行编程外，同样支持多种编程语言，如C++。
与Hadoop不同的是微软是通过DryadLINQ语言进行编程与设计，它可以根据程序员给出的LINQ查询生成可以在Dryad引擎上执行的分布式策略算法建模(运算规则)，并负责任务的自动并行处理及数据传递时所需要的序列化等操作。此外，它还提供了一系列易于使用的高级特性，如强类型数据，VisualStudio集成调试，以及丰富的任务优化策略(规则)算法等等。这种模型策略开发框架也比较适合采用领域驱动开发设计(DDD)来构建“云”平台应用，并能够较容易的做到自动化分布式计算。
并行算法分治策略
Y=(A+B(C+DEF))+G，串行计算需要6步。利用结合律和交换律，该式变为Y=Y+(分裂为两个问题)，其中Y=A+G，=B(C+DEF)，在两台处理机的系统上只需5步并行计算。在用分配率，Y=(A+B(C+DEF))+G可变为Y=+，其中=A+G+BC，=BDEF，在两台处理机的系统上并行计算只需4步。如四台处理机的系统，并行计算可进一步减少为3步。两台处理机下的运算分解树和四台处理机下的运算分解树，如图1所示。
图1DGA运算分解树
从上面分析我们可以看到，通过并行算法策略建模，可以有效的控制数据的颗粒度，当程序运行在Dryad分布式并行平台时候，可最大化的提高分布式并行运算效率。
分布式并行策略
在云计算的时代，Dynamo(Amazon公司的一个分布式存储引擎)可以说是一本实现分布式存储的红宝书，借鉴Dynamo实现的产品如雨后春笋般冒出。
我们经常会遇到所开发的网站/系统，无法承载大规模用户并发访问的问题。解决该问题的传统方法是使用数据库，通过数据库所提供的访问操作接口来保证处理复杂的查询能力。当访问量增大，单数据库处理不过来时便增加数据库服务器。如果增加了3台服务器，再把用户分成了三类(关注：策略建模、颗粒度和映射)：A(学生)，B(老师)，C(程序员)。每次访问的时候，Dryad会先查看用户属于哪一类，然后直接访问存储那类用户数据的数据库，可能处理能力增加了三倍。这时我们已经实现了一个分布式的存储引擎过程，而Dryad与Dynamo具有相似的功能。Dynamo分布式存储引擎，如图2所示。
▲图2Dynamo分布式存储引擎
▲图2Dryad与微软体系结构的关系?
Dryad同MapReduce一样，它不仅仅是一种编程模型，同时也是一种高效的任务调度模型。Dryad这种编程模型并不仅适用于云计算，在多核和多处理器以及异构机群上同样有良好的性能。
我们知道在VisualStudio2010C++有一套并行计算编程框架，支持常用的协同任务调度和硬件资源(例如CPU和内存等)管理，通过Workstealing算法可以充分利用细颗粒度并行的优势，来保证空闲的线程依照一定的策略建模，从所有线程队列中“偷取”任务执行，所以能够让任务和数据粒度并行。如果一个耗时的任务只被粗略分割成四个子任务并发执行，即使是在四核心CPU的计算机上运行也无法做到实时动态的负载均衡，可能发生三个子任务很早就完成了，而另一个任务还在一个核上是等待状态。
Dryad与上述并行框架相似，同样可以对计算机和它们的CPU进行调度，不同的是Dryad被设计为伸缩于各种规模的集群计算平台，无论是单台多核计算机还是到由多台计算机组成的集群，甚至拥有数千台计算机的数据中心，可以从任务队列中创建的策略建模来实现分布式并行计算的编程框架。
|
|
