Why does Dryad use a DAG? – Dryad & DryadLINQ Team Blog
http://blogs.msdn.com/b/dryad/archive/2010/07/23/why-does-dryad-use-a-dag.aspx
The basic computational model we decided to adopt for Dryad is the directed-acyclic graph (DAG). Each node in the graph is a computation, and each edge in the graph is a stream of data traveling in the direction of the edge. The amount of data on any given edge is assumed to be finite, the computations are assumed to be deterministic, and the inputs are assumed to be immutable. This isn’t by any means a new way of structuring a distributed computation (for example Condor had DAGMan long before Dryad came along), but it seemed like a sweet spot in the design space given our other constraints.
私たちが Dryad に適用することに決めた基本的な計算モデルは、DAG（directed-acyclic graph：有向非巡回グラフ）である。 このグラフにおける個々のノードで計算が行われ、また、グラフにおける個々のエッジが、その方向をデータを送り出すストリームとなる。 あらゆるエッジ上のデータ量は有限と想定され、また、その計算は決定論的なものと想定され、入力は不変であると想定されるべきである。 それは、分散された計算を構成するための新しい方法ではないが（たとえば Dryad が登場するずっと以前に、Condor は DAGMan を有している）、他の制約を持つデザイン･スペースにおけるスイート･スポットだと想定される。
So, why is this a sweet spot? A DAG is very convenient because it induces an ordering on the nodes in the graph. That makes it easy to design scheduling policies, since you can define a node to be ready when its inputs are available, and at any time you can choose to schedule as many ready nodes as you like in whatever order you like, and as long as you always have at least one scheduled you will continue to make progress and never deadlock. It also makes fault-tolerance easy, since given our determinism and immutability assumptions you can backtrack as far as you want in the DAG and re-execute as many nodes as you like to regenerate intermediate data that has been lost or is unavailable due to cluster failures.
それは、なぜ、スイート･スポットになるのだろうか？ DAG の利便性の高さは、グラフ内にノードの順序を取り込んでいる点にある。 そのため、入力に際してノードが行うべきことを定義できるようになるため、スケジューリング･ポリシーのデザインが容易になる。そして、準備が済んでいる大量のノードを、どんな時にでも希望する順序のとおりに選択して、スケジューリングすることが可能となる。さらに、少なくとも 1つのスケジュールされたノードがある限り、その処理は継続され、また、デッドロックが起こることはないだろう。また、私たちの決定性と普遍性の仮説を前提として、DAG 内の任意の場所をバックトラックできるため、フォールト･トレランスも容易になる。なお、クラスタの失敗などにより、消失あるいは利用不能になってしまった中間データを再生したいする場合には、それに見合うだけのノードを再実行できる。
クリックで拡大 ⇒
https://nosqleast.com/2009/slides/yu-dryad.pdf より
The obvious way to generalize the DAG model would be to allow cycles in the graph, but that makes both scheduling and fault-tolerance more complicated. They are still possible, but we decided to go with the simpler approach and see what we ended up being able to do with it; and leave as a research question the extent to which adding cycles would be useful.
DAG モデルを普及させるには、そのグラフでの巡回を許す方式が明らかに有効だろうが、ケジューリングとフォールト･トレランスがさらに複雑になってしまう。それを実現する可能性も残されているが、私たちの決定においては、より単純なアプローチを選択し、その結果を見届けることになった。つまり、巡回を追加する有用性については、研究課題として残すことに決定した。
On the other hand, there’s no obvious way to restrict the DAG model that makes the underlying system any simpler. Although MapReduce is I think a simpler programming model than Dryad, arguably the system itself is, at least conceptually, more complicated, since the Map nodes and the Reduce nodes have different scheduling and fault-tolerance properties and implementations. In addition when the system wants to optimize some data transfer, e.g. building an aggregation tree or sampling a dataset to find a balanced range partition, the optimization can usually be expressed as a subgraph of a DAG, and doesn’t need to be “hand-rolled” the way it would if you wanted to add it to a system like Hadoop. So the big advantage of adopting a general DAG as the low-level computational abstraction is that there’s just one state machine that handles all computation nodes. Of course, any real implementation of MapReduce or a DAG-driven system like Dryad can get complicated, but the topology of the data flow is not in itself a source of complexity in Dryad.
その一方で、基本的なシステムをシンプルにするために、DAG モデルを制約していく明白な方法は存在しない。 おそらく、MapReduce は Dryad よりも単純なプログラミング･モデルだと思われるが異なるスケジューリングとフォールト･トレランスのプロパティおよび実装を、Map ノードと Reduce ノードが有するため、少なくともシステム自身は、概念的に複雑なものとなる。 それに加えて、たとえば、アグリゲーション･ツリーの構築や、バランスのとれたレンジのパーティションを見つけるためのデータセットのサンプリングといった、データ転送に関する最適化をシステムが要求することがある、そのときに、この最適化は DAG のサブ･グラフとして表現できるが、たとえば Hadoop のようなシステムに加えようとするなら、そこで望まれる “hand-rolled” の方式を取り入れる必要がなくなってしまう。したがって、一般的な DAG を低レベルの計算抽象概念として採用する大きいアドバンテージは、すべての計算ノードを取り扱う 1つのステート･マシンが、そこに存在するという点に集約される。 もちろん、 現実に実装するとき、MapReduce や、Dryad などの DAG 駆動システムは、複雑なものになり得る。 しかし、データフロー･トポロジーが、Dryad の複雑さ自身の根本に含まれることはない。
One thing we learned fairly early in the Dryad project was that people don’t want to build DAGs by hand: it’s too low-level, and people don’t want to have to learn to think about how to think about their algorithms in terms of dataflow graphs. So this seems like it might be a disadvantage of something like Dryad compared with MapReduce, whose simple programming model is often touted as its big advantage. But with a couple of years of experience, and having talked to a lot of people in academia and industry who have been using Hadoop, I’m not sure that’s really true. In practice, once you get beyond a coursework assignment, most interesting computations cannot be expressed purely as a single Map followed by a single Reduce. Instead, it turns out, you typically need to take the output of the first Reduce and do another round of Map and another round of Reduce, and so on. Often you are trying to write an iterative algorithm (e.g. something like k-means) or very commonly you need to do something like a Join that combines information from two input sets. Join is the basic construct that is used for most graph traversal algorithms (you are combining data at the nodes with an edge map), and it is also used all over the place when there are common subexpressions in a computation: the common result is computed once and then “joined” with other data several times as necessary.
Dryad プロジェクトの早期において、私たちが正しく学んだ 1つに、人々が手作業で DAG を構築したがらないという事があった。 つまり、あまりにも低レベル過ぎるという事であり、データフロー･グラフの観点で、そのアルゴリズムについて学習しようと望まないことであった。 その単純なプログラミング･モデルが、大半のケースでアドバンテージとして推奨される MapReduce との比較において、そのことが Dryad のようなテクノロジーの、ディスアドバンテージになっているのかも知れない。 ただし、この 2年間のエクスペリエンスにおいて、そして Hadoop を使用している学界と業界とのディスカッションにおいて、それが本当に本当であるとは確信していない。 実際のところ、教科書的なレベルを超えると、大半の興味深い処理が、単一の Map と Reduce の組み合わせでは、表現できなくなるだろう。 それに換えて、最初の Reduce の出力を取得し、別の Map と Reduce へと展開していく必要性が導かれる。 大半のケースにおいて、反復性のアルゴリズム（たとえば k-means など）の記述や、きわめて一般的な Join のようなものを用いた、2つの入力セットに基づく情報の結合などが必要となる。 Join は、大半のグラフ横断型アルゴリズム（データ･ノードにおいてデータとエッジ･マップを結合）において用いられる、基本的な概念である。 そして、計算における共通の副次式が存在する場合にも、園周辺で使用される。つまり、共通の結果は一度だけ計算された後に、必要に応じて何度でも、他のデータと " Join " される。
In other words, MapReduce is really too low level for most programming tasks as well; programmers don’t want to have to break up a complicated algorithm into a set of Maps and Reductions, and manually manage all the types and manually write a script to sequentially execute a series of MapReduce jobs. Good evidence for this comes from the proliferation of higher-level language layers that have been built on MapReduce and Hadoop, including Sawzall, PigLatin, HIVE, Cloudbase, and Yahoo!’s Hadoop SQL.
言い換えれば、大半のプログラミング･タスクに対して、MapReduce はあまりにも低レベルすぎる。つまり、プログラマー Map と Reduuce のセットの中に、複雑なアルゴリズムを分解し、また、それらすべての手作業で管理し、一連の MapReduce ジョブを連続して実行するスクリプトを、手作業を書こうとは思わない。その良い証拠が、MapReduce と Hadoop の上に構築された Sawzall／PigLatin／HIVE／Cloudbase／Yahoo! Hadoop SQL などを含む、高レベルい言語レイヤへの拡散である。
So: if programmers aren’t actually directly writing Map and Reduce functions but instead using a higher-level language; and the MapReduce system isn’t easier to implement than a general DAG model (especially once you have added optimizations for things like sorting and hierarchical aggregation and distribution); and the high-level language you write can generate better-performing execution plans when it has access to a general DAG rather than a limited set of constructs such as Map and Reduce, then why would you choose to implement MapReduce over something like Dryad? We don’t think you would, but then we are biased 
そうだとすると、もしもプログラマーがMapReduce を書きたがらず代わりに高レベルの言語を使うのであれば、また、MapReduceがDAGモデルよりも簡単に書けるのではなければ（とくにひとたびソートや階層的な集約・分散に関しての最適化を加えてしまったりしたときに）、さらには汎用のDAGにアクセスできる高レベルの言語がMapReduceのような限定された構造よりよい性能の実行プランを作れるのであれば、Dryadのようなものの上にMapReduceを実装しようとするだろうか？そうは思えないが考え方が偏っているのかもしれない。
Michael Isard
ーーーーー
コメント欄にあるように、最後の段落ですが、上田さんに校正していただきました訳文に、差し替えました。 おかげさまで、とても読みやすくなりました。 有難うございます。 ーーー A.C.
ーーーーー
これがウワサの、DAG（directed-acyclic graph）ですね。 日本語にすると、有向非巡回グラフ となるのでしょうか？ たしかに、たとえば Hadoop などを活用していくと、その Map/Reduce が多段化してくることになり、そのフローを簡潔かつ確実に制御するための仕組みが必要になると思われます。
そのため、Apache は Zookeeper などに取り組むという構図になっているのでしょうが、あくまでも Hadoop の利用を前提としています。 その点、この記事でいうノードの中身なのですが、そこが、どのように考えられているのか、とても興味がありますね。
それと、訳に自身のないところが多々ありで、なにか変なところなど見つかりましたら、ぜひ、お知らせくださ～～～い！ーーー A.C.
ーーーーー
＜関連＞
MapReduce in DryadLINQ
Windows Azure MapReduce Demo
Hadoop が Microsoft の教材に？
教育機関への Dryad 提供が始まる
Apache ZooKeeper による分散並列キューの構築
Observers と ZooKeeper
Hadoop による Web 広告システムの構築と運用 ：ヨーロッパでの事例
Gridmix3 ： Apache Hadoop の実運用負荷をエミュレート
Microsoft readying Hadoop for Windows Azure の対訳
