為什麼很多分散式系統都是以DAG（Directed acyclic graph ）實現運算的？

01-13

比如Tez, 比如Spark，還有一大堆實驗室里產生的framework 和system。
我能想到的和DAG並列的只有Flink的stream運算了……大家還能列舉下其他以不同方式實現分散式計算的系統/框架么？？
我的理解是，基於DAG來跑分散式程序實現起來的確比較有邏輯性，而且比較容易為大眾所接受，並且設計成什麼樣子也可能是基於系統的設計機理和目的的。
那麼，要是做某個系統的拓展（比如添加『其他』支持的內容），在原有的DAG基礎上，做系統的大佬們一般會往那個方向考慮？

不是說分散式系統的計算要用 DAG 來實現，而是數據的處理流程本來就是這樣的，我們抽象了一下，發現可以他總是可以描述為一個 DAG。

早期只有 MapReduce 的時候，Hive 就是把一個計算任務分解成若干級聯的 Map-Reduce ，後來大家發現這種模型太低效，把沒有的分支去掉，最後又變成 DAG 了。因此也會說 MapReduce 是 DAG 的一種特殊形式。

至於 Streaming ，跟 DAG 不是一個領域的概念。Streaming 更多的描述的是數據源的輸入方式，是一種批處理模型還是流，後面真正計算的邏輯還是一個 DAG 。不信你看Spark Streaming

從並行化來說，DAG的每個節點都是一個pure function，沒有副作用，依賴關係就是節點的輸入輸出，也就是dag的edge。這樣依賴關係明顯，容易並行。個人認為這是最主要的原因。不同的框架也用了dag的其他性質來做其他一些事情。

一句話：是抽象和實現上的一個折中考慮。

數據流上像MapReduce顯然表達能力有限，表達能力更強的應該是一個沒有限制的graph，但是graph顯然可操作的空間太大了，從設計和實現上scope都太大了，DAG就是最佳的選擇，需要其他更加複雜表達形式也可以通過DAG組合。

如果你去看其他領域，比如database，最開始就是有graph model，但是逐漸被relational database取代了。其實是同樣一個道理。

如果要找一個graph model的處理框架，可以看一下naiad這篇paper，這篇paper也非常大的影響了TensorFlow的設計。

分散式系統最重要的應該是Failover, 下面是數據的一致性。至於DAG,那是數據流程的抽象。

15年前，谷歌剛出來Map-Reduce的時候，可以很自然的想成是多線程模型在分散式上面的擴展。這種模型天然容易做出來Failover。後來發現這種模型太簡單，也積累了一些經驗，就擴展到DAG的方式。其實MR也只是DAG的一個特例而已。

我覺得今後的DAG的發展，一是DAG的流處理(就像flink這樣batch 和 stream 一起的)，二是優化這一塊，不一樣的數據導致不一樣的DAG圖，可以優化執行的地方還是很多的，特別是考慮的網路通信和數據準確性等等指標。

我覺得用dag表示 (過程或數據的) 依賴關係是個很自然且合適的抽象.

在大部分時候程序代碼是指令, 表達的是 "過程的" 依賴關係. 比如下面的代碼暗示了 "先計算foo1再計算foo2".

```c

int a = foo1();

int b = foo2();

int c = bar(a, b);

```

表達式間的DAG:

a &<- foo1()

b &<- foo2()

bar(a, b) &<- a

bar(a, b) &<- b

c &<- bar(a, b

但人想要的往往只是 "數據的" 依賴關係:　計算foo1()和foo2() , 把結果喂給bar

如果foo1和foo2能被同時執行, 只要數據的依賴關係仍然正確 (和源代碼一致), 人們一般不介意過程的依賴關係被打破. 這也是單機計算時編譯器和cpu實際在做的事 (指令重排序).

分佈式計算時下面的依賴關係模型是一樣的, 區別在於 foo1 foo2 可能由不同的機器計算.

這些任務計算的數據流，控制依賴關係本身就是一個DAG圖。

很好奇，如果不用DAG，還有其他方式嗎？

題主問反了，不是框架只有DAG。而是人們的思維模式是DAG，然後才有編程思維和實現，最後才有一個框架。

此外，不是所有的計算框架都只有DAG，Flink等就支持迭代計算（因此有環）。

這個只是計算圖而已

查詢什麼的可以分解為dag描述的計算圖。並不是計算本身。

單向無環圖依賴關係簡單，是概率圖模型的一種。其他模型:雙向…、有環…，依賴關係複雜，很難滿足並行運行的條件（結合律，交換律）

stream運算不lazy?對大數據運算不友好？

這和我們解決問題的方式有關。當出現一個複雜問題的時候，比較常見的方式就是把大的問題分成小的問題，各個擊破，然後整合。

這其實就是我們常見的分治演算法，如merge sort。分治演算法，恰好就是MapReduce的基礎。它的誕生，讓Google很多產品煥發了青春，比如pagerank，廣告推廣，垃圾郵件，新聞分類等等。因為這些演算法，都需要大量的數據對模型進行訓練，計算量很大，MapReduce讓之前不可能的變成了現實。

Spark框架，是對MapReduce的優化，基本思路還是一樣的。所以dag的設計思想來源於分治演算法，一個簡單的解決問題的模型。