Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1081705
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类:

2010-09-14 18:56:33

* 介绍
    这是一篇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系统也是有局限性的。它更适用于批处理任务,而不适用于需要
快速响应的任务;这个数据模型更适用于处理流式访问,而不是随机访问。

阅读(1596) | 评论(0) | 转发(0) |
0

上一篇:scala还不错

下一篇:Duck Typing

给主人留下些什么吧!~~