微软Dryad分布式并行计算平台解析

随着近几年云计算的飞速发展，“云”正在彻底改变用户现有的以桌面为核心的使用习惯，转向使用以Web为核心的存储与服务。对于准备提供云计算服务的企业来说，要使云计算真正地“落地”需要解决两个重要问题：如何构建与应用程序紧密结合的大规模底层基础设施？如何通过构建新型的云计算应用程序来提供更加丰富的用户体验？要解决这两个问题，采用专门的分布式并行计算平台是先决条件之一。

Dryad：MapReduce之外的新思路

目前各大软件巨头都搭建了自己的分布式平台解决方案，主要包括Dryad、Dynamo和MapReduce等框架。2010年12月21日，微软发布了Dryad的测试版本，成为谷歌MapReduce分布式并行计算平台的竞争对手。Dryad是微软构建云计算基础设施的重要核心技术之一，它可以让开发人员在Windows或者.NET平台上编写大规模的并行应用程序模型，并能够让在单机上编写的程序运行在分布式并行计算平台上。工程师可以利用数据中心的服务器集群对数据进行并行处理，当工程师在操作数千台计算机时，无需关心分布式并行计算系统方面的细节。

数据并行计算

Dryad和DryadLINQ是微软硅谷研究院创建的研究项目，主要用来提供一个分布式并行计算平台。DryadLINQ是分布式计算语言，能够将LINQ编写的程序转变为能够在Dryad上运行的程序，使普通程序员也可以轻易进行大规模的分布式计算。它结合了微软Dryad和LINQ两种关键技术，被用于在该平台上构建应用。Dryad构建在Cluster Service(集群服务)和分布式文件系统之上，可以处理任务的创建和管理、资源管理、任务监控和可视化、容错、重新执行和调度等工作。

Dryad在微软体系结构中的位置

Dryad同MapReduce一样，它不仅仅是一种编程模型，同时也是一种高效的任务调度模型。Dryad这种编程模型不仅适用于云计算，在多核和多处理器以及异构机群上同样有良好的性能。在Visual Studio 2010 C++有一套并行计算编程框架，支持常用的协同任务调度和硬件资源(例如CPU和内存等)管理，通过Work Stealing算法可以充分利用细颗粒度并行的优势，来保证空闲的线程依照一定的策略建模，从所有线程队列中“偷取”任务执行，所以能够让任务和数据粒度并行。Dryad与上述并行框架相似，同样可以对计算机和它们的CPU进行调度，不同的是Dryad被设计为伸缩于各种规模的集群计算平台，无论是单台多核计算机还是由多台计算机组成的集群，甚至拥有数千台计算机的数据中心，都能以从任务队列中创建的策略建模来实现分布式并行计算的编程框架。

Dryad系统架构

Dryad系统主要用来构建支持有向无环图(Directed Acycline Graph，DAG)类型数据流的并行程序，然后根据程序的要求进行任务调度，自动完成任务在各个节点上的运行。在Dryad平台上，每个任务或并行计算过程都可以被表示为一个有向无环图，图中的每个节点表示一个要执行的程序，节点之间的边表示数据通道中数据的传输方式，其可能是文件、TCP Pipe、共享内存等。

Dryad系统结构

用Dryad平台时，首先需要在任务管理(JM)节点上建立自己的任务，每一个任务由一些处理过程以及在这些处理过程间的数据传递组成。任务管理器(JM)获取无环图之后，便会在程序的输入通道准备，当有可用机器的时候便对它进行调度。JM从命名服务器(NS)那里获得一个可用的计算机列表，并通过一个维护进程(PD)来调度这个程序。

Dryad任务结构

Dryad的执行过程可以看做是一个二维管道流的处理过程，其中每个节点可以具有多个程序的执行，通过这种算法可以同时处理大规模数据。在每个节点进程(Vertices Processes)上都有一个处理程序在运行，并且通过数据管道(Channels)的方式在它们之间传送数据。二维的Dryad管道模型定义了一系列的操作，可以用来动态地建立并且改变这个有向无环图。这些操作包括建立新的节点，在节点之间加入边，合并两个图以及对任务的输入和输出进行处理等。

名词解释

任务管理器(Job Manager，JM)：每个Job的执行被一个Job Manager控制，该组件负责实例化这个Job的工作图；在计算机群上调度节点的执行；监控各个节点的执行情况并收集一些信息；通过重新执行来提供容错；根据用户配置的策略动态地调整工作图。

计算机群(Cluster)：用于执行工作图中的节点。

命名服务器(Name Server，NS)：负责维护Cluster中各个机器的信息。

维护进程(PDaemon，PD)：进程监管与调度工作。

Dryad模型算法应用

DryadLINQ可以根据工程师给出的LINQ查询生成可以在Dryad引擎上执行的分布式策略算法建模(运算规则)，并负责任务的自动并行处理及数据传递时所需要的序列化等操作。此外，它还提供了一系列易于使用的高级特性，如强类型数据、Visual Studio集成调试以及丰富的任务优化策略(规则)算法等。这种模型策略开发框架也比较适合采用领域驱动开发设计(DDD)来构建“云”平台应用，并能够较容易地做到自动化分布式计算。

我们经常会遇到网站或系统无法承载大规模用户并发访问的问题，解决该问题的传统方法是使用数据库，通过数据库所提供的访问操作接口来保证处理复杂查询的能力。当访问量增大，单数据库处理不过来时便增加数据库服务器。如果增加了三台服务器，再把用户分成了三类：A(学生)、B(老师)、C(工程师)。每次访问时先查看用户属于哪一类，然后直接访问存储那类用户数据的数据库，则可将处理能力增加三倍，这时我们已经实现了一个分布式的存储引擎过程。

我们可以通过Dryad分布式平台来解决云存储扩容困难的问题。如果这三台服务器也承载不了更大的数据要求，需要增加到五台服务器，那必须更改分类方法把用户分成五类，然后重新迁移已经存在的数据，这时候就需要非常大的迁移工作，这种方法显然不可取。另外，当群集服务器进行分布式计算时，每个资源节点处理能力可能有所不同(例如采用不同硬件配置的服务器)，如果只是简单地把机器直接分布上去，性能高的机器得不到充分利用，性能低的机器处理不过来。Dryad解决此问题的方法是采用虚节点，把上面的A、B、C三类用户都想象成一个逻辑上的节点。一台真实的物理节点可能会包含一个或者几个虚节点(逻辑节点)，看机器的性能而定。我们可以把那任务程序分成Q等份(每一个等份就是一个虚节点)，这个Q要远大于我们的资源数。现在假设我们有S个资源，那么每个资源就承担Q/S个等份。当一个资源节点离开系统时，它所负责的等份要重新均分到其他资源节点上；当一个新节点加入时，要从其他的节点“偷取”一定数额的等份。

在这个策略建模算法下，当一个节点离开系统时，虽然需要影响到很多节点，但是迁移的数据总量只是离开那个节点的数据量。同样，一个新节点的加入，迁移的数据总量也只是一个新节点的数据量。之所以有这个效果是因为Q的存在，使得增加和减少节点的时候不需要对已有的数据做重新哈希(D)。这个策略的要求是Q>>S(存储备份上，假设每个数据存储N个备份则要满足Q>>S*N)。如果业务快速发展，使得不断地增加主机，从而导致Q不再满足Q>>S，那么这个策略将重新变化。

Dryad算法模型就是一种简化并行计算的编程模型，它向上层用户提供接口，屏蔽了并行计算特别是分布式处理的诸多细节问题，让那些没有多少并行计算经验的开发人员也可以很方便地开发并行应用，避免了很多重复工作。这也就是Dryad算法模型的价值所在，通过简化编程模型，降低了开发并行应用的入门门槛，并且能大大减轻了工程师在开发大规模数据应用时的负担。

通过上述的论述，我们可以看到Dryad通过一个有向无环图的策略建模算法，提供给用户一个比较清晰的编程框架。在这个编程框架下，用户需要将自己的应用程序表达为有向无环图的形式，节点程序则编写为串行程序的形式，而后用Dryad方法将程序组织起来。用户不需要考虑分布式系统中关于节点的选择，节点与通信的出错处理手段都简单明确，内建在Dryad框架内部，满足了分布式程序的可扩展性、可靠性和对性能的要求。

使用DryadLINQ

通过使用DryadLINQ编程，使工程师编写大型数据并行程序能够轻易地运行在大型计算机集群里。DryadLINQ开发的程序是一组顺序的LINQ代码，它们可以针对数据集做任何无副作用的操作，编译器会自动将其中数据并行的部分翻译成并行执行的计划，并交由底层的Dryad平台完成计算，从而生成每个节点要执行的代码和静态数据，并为所需要传输的数据类型生成序列化代码。

通过Dryad DAG排列的节点(程序)扩展性能

P：parses lines(解析线)

D：hash distribute(哈希分布)

S：quicksort(快速排序)

C：count occurrences(事件计算)

MS：merge sort(合并分类)

M：non-deterministic merge(未确定合并）

LINQ本身是.NET引入的一组编程结构，它用于像操作数据库中的表一样来操作内存中的数据集合。DryadLINQ提供的是一种通用的开发/运行支持，而不包含任何与实际业务、算法相关的逻辑，Dryad和DryadLINQ都提供有API。DryadLINQ使用和LINQ相同的编程模型，并扩展了少量操作符和数据类型以适用于数据并行的分布式计算。并从两方面扩展了以前的计算模型(SQL、MapReduce、Dryad等)：它是基于.NET强类型对象的、表达力更强的数据模型和支持通用的命令式和声明式编程(混合编程)，从而延续了LINQ代码即数据(treat code as data)的特性。

DryadLINQ使用动态的代码生成器，将DryadLINQ表达式编译成.NET字节码。这些编译后的字节码会根据调度执行的需要，被传输到执行它的机器上去。字节码中包含两类代码：完成某个子表达式计算的代码和完成输入输出序列化的代码。这种表达式并不会被立刻计算，而是等到需要其结果的时候才进行计算。DryadLINQ设计的核心是在分布式执行层采用了一种完全函数式的、声明式的表述，用于表达数据并行计算中的计算。这种设计使得我们可以对计算进行复杂的重写和优化，类似于传统的并行数据库。从而解决了传统分布式数据库SQL语句功能受限与类型系统受限问题，以及MapReduce模型中的计算模型受限和没有系统级的自动优化等问题。

DryadLINQ=LINQ＋Dryad

在Dryad编程模式中，应用程序的大规模数据处理被分解为多个步骤，并构成有向无环图形式的任务组织，由执行引擎去执行。这两种模式都提供了简单明了的编程方式，使得工程师能够很好地驾驭云计算处理平台，对大规模数据进行处理。Dryad的编程方式可适应的应用也更加广泛，通过DryadLINQ所提供的高级语言接口，使工程师可以快速进行大规模的分布式计算应用程序的编写。

Dryad技术的应用

云计算重要的概念之一就是可伸缩性，实现它的关键是虚拟化。通过虚拟化可以在一台共享计算机上聚集多个操作系统和应用程序，以便更好地利用服务器。当一个服务器负载超荷时，可以将其中一个操作系统的一个实例(以及它的应用程序)迁移到一个新的、相对闲置的服务器上。虚拟化(Virtualization)是云计算的基石，企业实现私有云的第一步就是服务器基础架构进行虚拟化。基础设施虚拟化之后，接下来就是要将现有应用迁移到虚拟环境中。

Dryad结合Hyper-V(Windows Server 2008的一个关键组成部分)虚拟化技术，可以实现TB级别数据的在线迁移。中小型企业也可以针对企业内部小型集群服务器进行分布式应用系统编程，以及制定私有云开发与应用解决方案等设计。Windows Azure是微软的公有云解决方案，但是目前要大规模应用还为时过早。使用现有Windows第三方产品实现私有云，花费成本却很大。然而Dryad技术给我们带来了不错的折中选择，当我们基于Windows Server平台运行应用系统或者网站时，便可以基于Dryad分布式架构来开发与设计实现。当公有云时机成熟和各种条件完备时，系统可以很轻易地升级到公有云，企业而无需花费太多成本。

写在后

云计算可以看成是网络计算与虚拟化技术的结合，利用网络的分布式计算能力将各种IT资源筑成一个资源池，然后结合成熟的存储虚拟化和服务虚拟化技术，让用户实时透明地监控和调配资源。Dryad是实现构建微软云计算基础设施的重要核心技术之一，其具有诸多优点，如DryadLINQ具有声明式编程并将操作的对象封装为.NET类数据，方便数据操作、自动并行化、Visual Studio IDE和.NET类库集成、自动序列化和任务图的优化(静态和动态(主要通过Dryad API实现))、对Join进行了优化，得到了比BigTable+MapReduee更快的Join速率和更易用的数据操作方式等。

不过，Dryad和DryadLINQ也同样具有局限性。其一，它更适用于批处理任务，而不适用于需要快速响应的任务；这个数据模型更适用于处理流式访问，而不是随机访问。其二，DryadLINQ使用的是.NET的LINQ查询语言模型，针对运行Windows HPC Server的计算机集群设计，而目前高性能计算市场被Linux所占领。此外，和MapReduce的应用时间和实践相比，Dryad的可靠性还明显不足，据了解除了微软AdCenter中的数据分析和Trident项目之外，其它应用Dryad的地方还很少。不过总的来看，Dryad平台在将来仍具有很广泛的发展前景，尤其对.NET开发人员来说是一次很重要的技术革新机遇。