標籤:

為什麼很多分散式系統都是以DAG(Directed acyclic graph )實現運算的?

比如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的設計思想來源於分治演算法,一個簡單的解決問題的模型。


推薦閱讀:

分散式系統工程如何搭建,有沒有一套完整的系統的實踐方法論,比如,存儲服務?
分散式系統工程師要不要轉行做機器學習?
一名分散式存儲工程師的技能樹是怎樣的?
如何的才能更好的學習MIT6.824分散式系統課程?

TAG:分散式系統 |