微软于2010年12月21日发布了分布式并行计算基础平台——Dryad测试版成为谷歌MapReduce分布式数据计算平台的竞争对手。它可以使开发人员能够在Windows或者.Net平台上编写大规模的并行应用程序模型并能够在单机上所编写的程序很轻易的运行在分布式并行计算平台上程序员可以利用数据中心的服务器集群对数据进行并行处理当程序开发人员在操作数千台机器时而无需关心分布式并行处理系统方面的细节。本文将重点讲述微软最新Dryad平台方面的功能原理以及应用。Dryad平台也是构建微软云计算基础设施重要核心技术之一。要使云计算真正的“落地”主要面临两个重要问题如何构建与应用程序来紧密结合的大规模底层基础设施目前构建分布式平台的基础设施主要包括Dryad、Dynamo和MapReduce等框架。图1 数据并行计算另一个问题就是如何通过构建新型的云计算应用程序能够在网络上提供更加丰富的用户体验Yahoo扩展了MapReduce并提出了MapReduceMerge框架并可以应用到多核处理器上。HP则将注意力关注于分布式共享内存的使用上而不同于MapReduce编程方面。IBM主要使用Linux系统映像以及Hadoop软件(Google File System以及MapReduce的开源实现)。微软则自主研发了Dryad和DryadLINQ并可以用于辅助C#开发人员在计算机集群或数据中心里分布式并行处理大规模的数据从而在程序执行性能与效率上提高数倍。Dryad概述Dryad和DryadLINQ是微软硅谷研究院创建的研究项目主要用来提供一个分布式并行计算平台DryadLINQ提供一种高级语言接口使普通程序员可以轻易进行大规模的分布式计算它结合了微软Dryad和LINQ两种关键技术被用于在该平台上构建应用。Dryad与微软体系结构中的位置关系如图2所示。图2 Dryad与微软体系结构的关系Dryad同MapReduce一样它不仅仅是一种编程模型同时也是一种高效的任务调度模型。Dryad这种编程模型并不仅适用于云计算在多核和多处理器以及异构机群上同样有良好的性能。我们知道在Visual Studio 2010 C有一套并行计算编程框架支持常用的协同任务调度和硬件资源例如CPU和内存等管理通过Work stealing算法可以充分利用细颗粒度并行的优势来保证空闲的线程依照一定的策略建模从所有线程队列中“偷取”任务执行所以能够让任务和数据粒度并行。如果一个耗时的任务只被粗略分割成四个子任务并发执行即使是在四核心CPU的计算机上运行也无法做到实时动态的负载均衡可能发生三个子任务很早就完成了而另一个任务还在一个核上是等待状态。Dryad与上述并行框架相似同样可以对计算机和它们的CPU进行调度不同的是Dryad被设计为伸缩于各种规模的集群计算平台无论是单台多核计算机还是到由多台计算机组成的集群甚至拥有数千台计算机的数据中心可以从任务队列中创建的策略建模来实现分布式并行计算的编程框架。Dryad系统架构Dryad architectureDryad系统的总体的构建用来支持有向无环图Directed Acycline GraphDAG类型数据流的并行程序。Dryad的整体框架根据程序的要求完成调度工作自动完成任务在各个节点上的运行。在Dryad平台上每个Dryad工作或并行计算过程被表示为一个有向无环图。图中的每个节点表示一个要执行的程序节点之间的边表示数据通道中数据的传输方式其可能是文件、TCP Pipe、共享内存等为了支持数据类型需要针对每个类型有序列化代码。图3 Dryad系统结构如图3所示当用户使用Dryad平台时首先是需要在任务管理JM节点上建立自己的任务。每一个任务由一些处理过程以及在这些处理过程数据传递组成。任务管理器JM获取无环图之后便会在程序的输入通道准备当有可用机器的时候便对它进行调度。JM从命名服务器NS那里获得一个可用的计算机列表并通过一个维护进程PD来调度这个程序。系统组件任务管理器Job ManagerJM每个Job的执行被一个Job Manager控制该组件负责实例化这个Job的工作图在计算机群上调度节点的执行监控各个节点的执行情况并收集一些信息通过重新执行来提供容错根据用户配置的策略动态地调整工作图计算机群Cluster用于执行工作图中的节点命名服务器Name ServerNS负责维护Cluster中各个机器的信息维护进程PDaemonPD进程监管与调度工作。从总体来看传统的Linux/Unix管道是一维管道每个节点在管道中是单个的程序。而Dryad的执行过程就可以看做是一个二维的管道流的处理过程。其中每个节点可以具有多个程序的执行通过这种算法可以同时处理大规模数据。图4 Dryad任务结构如图4所示我们可以看到在每个节点进程Vertices Processes上都有一个处理程序在运行并且通过数据管道Channels的方式在它们之间传送数据。二维的Dryad管道模型定义了一系列的操作可以用来动态的建立并且改变这个有向无环图。这些操作包括建立新的节点在节点之间加入边合并两个图以及对任务的输入和输出进行处理等。与微软Dryad相似MapReduce编程模型可用于大规模数据集(大于1TB)的并行运算。概念“Map(映射)”和“Reduce(化简)”它们的主要思想都是从函数式编程语言里借来的还有从矢量编程语言里借来的特性。MapReduce映射处理结构如图5所示。▲图5 MapReduce映射处理结构从上图可以看出MapReduce极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。当前的软件实现是指定一个 Map(映射)函数用来把一组键值对映射成一组新的键值对指定并发的Reduce(化简)函数用来保证所有映射的键值对中的每一个共享相同的键组。微软Dryad与谷歌的MapReduc映射原理相似但不同的是通过DryadLINQ来实现分布式程序编程设计。Dryad模型算法应用Computational modelDryadLINQ可以根据程序员给出的LINQ查询生成可以在Dryad引擎上执行的分布式策略算法建模运算规则并负责任务的自动并行处理及数据传递时所需要的序列化等操作。此外它还提供了一系列易于使用的高级特性如强类型数据Visual Studio集成调试以及丰富的任务优化策略规则算法等等。这种模型策略开发框架也比较适合采用领域驱动开发设计DDD来构建“云”平台应用并能够较容易的做到自动化分布式计算。并行算法分治策略。YABCDEFG串行计算需要6步。利用结合律和交换律该式变为Y1Y2分裂为两个问题其中Y1AGY2B CDEF在两台处理机的系统上只需5步并行计算。在用分配率YABCDEFG可变为YY3Y4其中Y3AGBCY4BDEF在两台处理机的系统上并行计算只需4步。如四台处理机的系统并行计算可进一步减少为3步。两台处理机下的运算分解树和四台处理机下的运算分解树如图6所示。图6 DGA运算分解树从上面分析我们可以看到通过并行算法策略建模可以有效的控制数据的颗粒度当程序运行在Dryad分布式并行平台时候可最大化的提高分布式并行运算效率。分布式并行策略我们经常会遇到所开发的网站/系统无法承载大规模用户并发访问的问题。解决该问题的传统方法是使用数据库通过数据库所提供的访问操作接口来保证处理复杂的查询能力。当访问量增大单数据库处理不过来时便增加数据库服务器。如果增加了3台服务器再把用户分成了三类关注策略建模、颗粒度和映射A学生B老师C程序员。每次访问的时候Dryad会先查看用户属于哪一类然后直接访问存储那类用户数据的数据库可能处理能力增加了三倍。这时我们已经实现了一个分布式的存储引擎过程而Dryad与Dynamo具有相似的功能。我们可以通过Dryad分布式平台来解决云存储扩容困难问题。如果这3台服务器也承载不了更大的数据要求时需要增加到5台服务器那必须更改分类方法把用户分成5类然后重新迁移已经存在的数据这时候就需要非常大的迁移工作这种方法显然不可取。另外当群集服务器进行分布式计算运行的时候每个资源节点处理能力可能有所不同例如不同硬件配置的服务器等等如果只是简单的把机器直接分布上去性能高的机器得不到充分利用性能低的机器处理不过来。图7 通过Dryad DAG排列的节点(程序)扩展性能P parses lines解析线D hash distribute哈希分布S quicksort快速排序C count occurrences事件计算MS merge sort合并分类M non-deterministic merge未确定合并Dryad解决此问题的方法是采用虚节点。把上面的A B C三类等用户都想象成一个逻辑上的节点。一台真实的物理节点可能会包含一个或者几个虚节点(逻辑节点)看机器的性能而定。我们可以把那任务程序分成Q等份(每一个等份就是一个虚节点)这个Q要远大于我们的资源数。现在假设我们有S个资源那么每个资源就承担Q/S个等份。 当一个资源节点离开系统的时候它所负责的等份要重新均分到其他资源节点上一个新节点加入的时候要从其他的节点“偷取”到一定数额的等份。在这个策略建模算法下当一个节点离开系统的时候虽然需要影响到很多节点但是迁移的数据总量只是离开那个节点的数据量。同样一个新节点的加入迁移的数据总量也只是一个新节点的数据量。之所以有这个效果是因为Q的存在使得增加和减少机器的时候不需要对已有的数据做重新哈希D。这个策略的要求是QS存储备份上假设每个数据存储N个备份则要满足QS*N。如果业务快速发展使得不断的增加主机从而导致Q不再满足QS那么这个策略将重新变化。通过上述的论述我们可以看到Dryad通过一个有向无环图的策略建模算法提供给用户一个比较清晰的编程框架。在这个编程框架下用户需要将自己的应用程序表达为有向无环图的形式节点程序则编写为串行程序的形式而后用Dryad方法将程序组织起来。用户不需要考虑分布式系统中关于节点的选择节点与通信的出错处理手段都简单明确内建在Dryad框架内部满足了分布式程序的可扩展性、可靠性和性能的要求。