Dyrad

微软于 2010 年 12 月 21 日发布了分布式并行计算基础平台 Dryad 测试版，成为谷歌 MapReduce 分布式数据计算平台的竞争对手。它可以使开发人员能够在 Windows 或者 .Net 平台上编写大规模的并行应用程序模型，并能够在单机上所编写的程序很轻易的运行在分布式并行计算平台上，程序员可以利用数据中心的服务器集群对数据进行并行处理，当程序开发人员在操作数千台机器时，而无需关心分布式并行处理系统方面的细节。

Dryad 将具体计算组织成有向无环图，其中图节点代表用户写的表达式应用逻辑，图节点之间的边代表了数据流动通道。Dryad 在实时以共享内存，TCP 连接以及临时文件的方式来进行数据传递，绝大多数情况下采用临时文件的方式。

Dryad 系统架构（Dryad Architecture）

Dryad 系统的总体的构建用来支持有向无环图（Directed Acycline Graph，DAG）类型数据流的并行程序。Dryad 的整体框架根据程序的要求完成调度工作，自动完成任务在各个节点上的运行。在 Dryad 平台上，每个 Dryad 工作或并行计算过程被表示为一个有向无环图。图中的每个节点表示一个要执行的程序，节点之间的边表示数据通道中数据的传输方式，其可能是文件、TCP Pipe、共享内存等，为了支持数据类型需要针对每个类型有序列化代码。

Dryad 的作业管理模块（Job Manager）JM 在应用程序内部维护了一个基于 DAG 图模型的计算节点依赖关系图，作业管理模块通过命名服务器（Name Server）NS 来获取可用的服务器列表，而后通过在这些服务器上运行的守护进程 Daemon（图中 D）来调度和执行计算节点 Vertex（执行和监控）。各个计算节点之间通过例如文件，管道，网络等形式的数据通道交换数据。为了能方便地描述复杂任务，Dryad 采用了若干简单和 DAG 结构及其描述符的不断组合来构建复杂结构和方式。

从总体来看，传统的 Linux/Unix 管道是一维管道，每个节点在管道中是单个的程序。而 Dryad 的执行过程就可以看做是一个二维的管道流的处理过程。在每个节点进程（Vertices Processes）上都有一个处理程序在运行，并且通过数据管道（Channels）的方式在它们之间传送数据。二维的 Dryad 管道模型定义了一系列的操作，可以用来动态的建立并且改变这个有向无环图。这些操作包括建立新的节点，在节点之间加入边，合并两个图以及对任务的输入和输出进行处理等。

其中，每个节点可以具有多个程序的执行，通过这种算法可以同时处理大规模数据。Dryad 将图节点的可执行代码分发到可用机器节点上，同时将该图节点涉及的输入和输出数据路径地址发送给相应和工作机，这样该工作机就可执行计算任务。调度程序跟踪 DAG 图中节点和执行状态和执行历史，如果 JM 调度程序崩溃，则整个任务失败。如果工作节点发生故障，调度程序会将图中节点对应代码发送到其他可用节点重新执行图节点程序，以此来达到容错目的。

Dryad 模型算法应用（Computational Model）

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

并行算法分治策略

Y=（A+B（C+DEF））+G，串行计算需要 6 步。利用结合律和交换律，该式变为 Y1=Y2+（分裂为两个问题），其中 Y1=A+G，Y2=B（C+DEF），在两台处理机的系统上只需 5 步并行计算。在用分配率，Y=（A+B（C+DEF））+G 可变为 Y=Y3+Y4，其中 Y3=A+G+BC，Y4=BDEF，在两台处理机的系统上并行计算只需 4 步。如四台处理机的系统，并行计算可进一步减少为 3 步。两台处理机下的运算分解树和四台处理机下的运算分解树，如下图所示。

从上面分析我们可以看到，通过并行算法策略建模，可以有效的控制数据的颗粒度，当程序运行在 Dryad 分布式并行平台时候，可最大化的提高分布式并行运算效率。

分布式并行策略

我们经常会遇到所开发的网站/系统，无法承载大规模用户并发访问的问题。解决该问题的传统方法是使用数据库，通过数据库所提供的访问操作接口来保证处理复杂的查询能力。当访问量增大，单数据库处理不过来时便增加数据库服务器。如果增加了 3 台服务器，再把用户分成了三类（关注：策略建模、颗粒度和映射）：A（学生），B（老师），C（程序员）。每次访问的时候，Dryad 会先查看用户属于哪一类，然后直接访问存储那类用户数据的数据库，可能处理能力增加了三倍。这时我们已经实现了一个分布式的存储引擎过程，而 Dryad 与 Dynamo 具有相似的功能。

我们可以通过 Dryad 分布式平台来解决云存储扩容困难问题。如果这 3 台服务器也承载不了更大的数据要求时，需要增加到 5 台服务器，那必须更改分类方法把用户分成 5 类，然后重新迁移已经存在的数据，这时候就需要非常大的迁移工作，这种方法显然不可取。另外，当群集服务器进行分布式计算运行的时候，每个资源节点处理能力可能有所不同（例如不同硬件配置的服务器等等），如果只是简单的把机器直接分布上去，性能高的机器得不到充分利用，性能低的机器处理不过来。

• 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）。这个策略的要求是 Q»S（存储备份上，假设每个数据存储 N 个备份则要满足 Q»S*N）。如果业务快速发展，使得不断的增加主机，从而导致 Q 不再满足 Q»S，那么这个策略将重新变化。

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

DryadLINQ

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

DryadLINQ 使用和 LINQ 相同的编程模型，并扩展了少量操作符和数据类型以适用于数据并行的分布式计算。并从两方面扩展了以前的计算模型（SQL、MapReduce、Dryad 等）：它是基于 .NET 强类型对象的、表达力更强的数据模型和支持通用的命令式和声明式编程（混合编程），从而延续了 LINQ 代码即数据（treat code as data）的特性。

LINQ 本身是 .NET 引入的一组编程结构，它用于像操作数据库中的表一样来操作内存中的数据集合。DryadLINQ 提供的是一种通用的开发/运行支持，而不包含任何与实际业务、算法相关的逻辑，Dryad 和 DryadLINQ 都提供有 API。DryadLINQ 使用动态的代码生成器，将 DryadLINQ 表达式编译成.NET 字节码。这些编译后的字节码会根据调度执行的需要，被传输到执行它的机器上去。字节码中包含两类代码：完成某个子表达式计算的代码和完成输入输出序列化的代码。DryadLINQ 表达式代码示例片段如下：

Collection<T> collection;

bool IsLegal(Key k);

string Hash(Key);

var results = from c in collection
where IsLegal(c.key)
select new { Hash(c.key), c.value};

这种表达式并不会被立刻计算，而是等到需要其结果的时候才进行计算。DryadLINQ 设计的核心是在分布式执行层采用了一种完全函数式的、声明式的表述，用于表达数据并行计算中的计算。这种设计使得我们可以对计算进行复杂的重写和优化，类似于传统的并行数据库。从而解决了传统分布式数据库 SQL 语句功能受限与类型系统受限问题，以及 MapReduce 模型中的计算模型受限和没有系统级的自动优化等问题。另外，在 MapReduce 编程方式下，应用程序编写人员需要关注与自己的应用逻辑如何使用 Map 函数以及 Reduce 函数进行表达。在 Dryad 编程模式中，应用程序的大规模数据处理被分解为多个步骤，并构成有向无环图形式的任务组织，由执行引擎去执行。这两种模式都提供了简单明了的编程方式，使得应用程序开发人员能够很好的驾驭云计算处理平台，对大规模数据进行处理。Dryad 的编程方式可适应的应用也更加广泛，通过 DryadLinq 所提供的高级语言接口，使应用程序员可以快速进行大规模的分布式计算应用程序的编写。