* 介绍
这是一篇OSDI'08上的论文，该论文的标题是"DryadLINQ: A System for
General-Purpose Distributed Data-Parallel Computing using A High Level
Language"。我第一眼看上去的时候，觉得它的关键字有两个："General-Purpose"和
"Data-Parallel"。也就是说，作者在构造一个用于通用计算的、数据并行的分布式计算
系统。DryadLINQ系统从两个方面扩展之前的计算模型(如SQL、MapReduce、Dryad等)：
1. 基于.NET强类型对象的、表达力更强的数据模型；
2. 支持通用的命令式和声明式编程(混合编程)
DryadLINQ程序是一组顺序的LINQ代码，它们可以针对数据集做任何无副作用的操作，
DryadLINQ的编译器会自动将其中数据并行的部分翻译成并行执行的plan，并交由底层的
Dryad平台完成计算。作者的实验表明，该系统可以达到很高的性能和接近线性的可扩展
性。
DryadLINQ系统设计的关键点之一是：在分布式执行层采用了一种完全函数式的、声明
式的表述，用于表达数据并行计算中的计算。这种设计使得我们可以对计算进行复杂的重写
和优化，类似于传统的并行数据库。
传统分布式数据库的问题：1. SQL语句功能受限；2. 类型系统受限
MapReduce模型的问题：1. 计算模型受限；2. 没有系统级的自动优化
* 系统结构概览
在Dryad平台上，每个Dryad工作被表示为一个有向无环图。图中的每个节点表示一个
要执行的程序，节点之间的边表示数据通路(数据的传输方式可能是文件、TCP Pipe、
共享内存等，为了支持数据类型，需要针对每个类型有序列化代码)。从这里可以看到，
Dryad的计算模型是MapReduce的一种泛化。
系统组件：
1. Job Manager：每个Job的执行被一个Job Manager控制，该组件负责实例化这个Job
的工作图；在计算机群上调度节点的执行；监控各个节点的执行情况并收集一些
信息；通过重新执行来提供容错；根据用户配置的策略动态地调整工作图；
2. Cluster：计算机群，用于执行工作图中的节点；
3. Name Server：负责维护Cluster中各个机器的信息；
DryadLINQ建立在Dryad平台上。其核心工作是将用户程序中的LINQ表达式编译成Dryad
平台上的执行计划(计算描述)，包括将原表达式分解成子表达式，每个子表达式是一个节
点；生成每个节点要执行的代码和静态数据；为需要传输的数据类型生成序列化代码。
* 使用DryadLINQ
LINQ本身是.NET引入的一组编程结构，它用于像操作数据库中的表一样来操作内存中
的数据集合。这种类似与SQL的语句使得程序员可以表达对数据集合的复杂操作，同时又
为运行时系统对如何实现这种计算留下了很大的空间。每个支持LINQ的数据集合都是
IEmurable的子类。LINQ操作符和数据集构成的表达式一般会被表示成
IQueryble(它也是IEmurable的子类)。这种表达式并不会被立刻计算，
而是等到需要其结果的时候，才进行计算。IQueryable也可以用于其它LINQ表达式中的参数。
DryadLINQ使用和LINQ相同的编程模型，并扩展了少量操作符和数据类型以适用于数据
并行的分布式计算。DryadLINQ的数据模型其实就是LINQ数据集合的分布式实现。每个数据
集合可以包含.NET类型的对象，但是数据集合被分成了若干不相交的子集，分布在一个
Dryad机群的若干台机器上。划分的策略包括一些常见的如hash、区间、RR等。
DryadLINQ计算的输入和输出都是DryadTable类型，它是IQueryable的子类。
DryadLINQ为了做到自动化分布式计算，要求“在DryadLINQ表达式中调用的函数
必须都没有副作用”。所有的共享对象都可以任意的读取和引用，它们会被自动序列化
并传送到需要的地方。
* 系统实现
这里，主要描述的是前文提到的编译过程，这个是该系统的核心技术点。主要包括
分布式执行计划的生成、优化。后续还包括执行。这里使用的优化器与数据库的优化器
类似，包括两个组件：一个静态组件，用于在生成执行计划时优化；一个动态组件，作为
Dryad平台策略plug-in，在运行时动态地优化执行计划(重写/变换执行计划的数据流图)。
** EPG
1. 首先，LINQ表达式会被转化成EPG(Execution Plan Graph)，后者是一个有向无环
图。在这个图中，每个节点代表一个操作符，边代表操作符的输入和输出。(由于公共
子表达式和Apply、Fork的存在，不能用树来表示)。
2. 对EPG执行term-rewriting优化。
3. 事实上，EPG是Dryad执行的数据流图的“框架”，EPG中的每个节点在Dryad执行
时都可能被复制成多个，形成一个Dryad的stage(一组执行相同程序的节点，分别处理一个
数据集合的不同部分)。
4. 优化器会根据LINQ表达式在EPG上做一些注释，对于边，这些注释包括传输的数据
类型、压缩算法等；对于节点包括使用的分区策略、每个分区的排序方式等。这些注释是
优化和执行的重要信息，要在EPG上尽量传播下去(由于表达式的负责性，未必真能传播)。
** 静态优化
静态优化主要是一些EPG重写规则，由EPG节点上的属性触发。目前，优化的重点在于
最小化文件和网络IO。主要规则包括:
1. Pipelining：多个操作符可能被放到一个进程中执行；
2. Patition冗余消除：消除不必要的分区操作
3. 聚合前置：由于分区操作代价较大，如果可能，下游的聚合操作被提前到分区前
4. IO缩减：在可能的时候使用TCP FIFO或者内存Channel，避免读写临时文件
** 动态优化
主要利用Dryad的API。
** 代码生成
DryadLINQ使用动态的代码生成器，将DryadLINQ表达式编译成.NET字节码。这些编译
后的字节码会根据调度执行的需要被传输到执行它的机器上去。字节码中包含两类代码：
一、完成某个子表达式计算的代码；二、完成输入输出序列化的代码。
DryadLINQ表达式可能会引用主程序所在的执行环境：
1. 引用主代码上下文中的变量：如果是原子值，将其值放入资源文件中以备使用，
如果是对象，将其序列化后放入资源文件中以备使用。资源文件会被传递到需要的
计算节点上。
2. 表达式可能会引用.NET类库/函数：使用反射机制将对应的代码传递到需要的计算
节点上。
* 总结
在该文Related Work开头处，作者说了一个分层结构：分布式计算中的“存储”、
“执行(引擎)”、“应用”。这三部分相互独立。
我觉得这种分层是非常重要的。在我看来，存储和执行两个部分实际上构成了一个
完整的分布式计算平台，而应用部分仅仅负责具体应用的逻辑。本文中的作者将自己
开发的DryadLINQ应用框架和运行系统放到“应用”里面，我觉得有些不妥。这个部分
应该在“执行”部分，因为DryadLINQ提供的是一种通用的开发/运行支持，而不包含任何
与实际业务、算法相关的逻辑。DryadLINQ只是给应用开发使用而已，就像Dryad也有API
一样。
本文说出了另一个观点：声明式的语言更适合大规模的并行计算，例如Pallels
Haskell、Pig、Sawzall、HIVE等。
Dryad以及DryadLINQ系统也是有局限性的。它更适用于批处理任务，而不适用于需要
快速响应的任务；这个数据模型更适用于处理流式访问，而不是随机访问。
