任務調度-DAG和Oozie基礎

本文主要內容

有向無環(huán)圖
拓撲排序
Oozie

有向無環(huán)圖

什么是有向無環(huán)圖

有向無環(huán)圖（Directed Acyclic Graph, DAG）是有向圖的一種改淑，特點是圖中沒有環(huán)传睹。常常被用來表示事件之間的驅動依賴關系焕窝，管理任務之間的調度死陆。拓撲排序是對DAG的頂點進行排序，使得對每一條有向邊(u, v)显拳，均有u（在排序記錄中）比v先出現窿克。亦可理解為對某點v而言，只有當v的所有源點均出現了髓涯，v才能出現袒啼。

image

為了描述一個Job內所有Task相互依賴關系，可以將Job中的每個Task對應為一個節(jié)點纬纪，將一個Job描述為一張有向無環(huán)圖DAG
有向無環(huán)圖對于構造一個任務必須發(fā)生在另一個任務之前的這種依賴模型特別有效蚓再。

度

入度：進入該頂點的邊的個數稱為該頂點的入度。
出度：從該頂點發(fā)出的邊的個數包各。

判斷一個圖是否有環(huán)：

任何一個有向無環(huán)圖中必定至少存在一個入度為0的頂點摘仅，至少存在一個出度為0的頂點，否則圖中必存在環(huán)问畅。

偏序和全序

偏序：圖中的任意一對頂點要么有先后關系娃属，要么沒有關系，不存在互相矛盾的關系（環(huán)路）
全序：圖中的任意一對頂點都有明確的關系

DAG的拓撲排序

由一個有向無環(huán)圖的頂點組成的序列护姆，當且僅當滿足下列條件時矾端，稱為該圖的一個拓撲排序（Topological sorting）。

image

拓撲排序的實現

算法實現片段：
<pre><code class="Python">
def kahn_topological(graphNodes):
"""
L← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
:return: L list
"""
L = []
S = []
S =getZeroIncomingDegreeNode(graphNodes,S)
while len(S)>0:
zeroNode = S.pop()
L.append(zeroNode)
S = getZeroIncomingDegreeNode(graphNodes,S,zeroNode=zeroNode)
return L
</code></pre>

Oozie

什么是Oozie

Cloudera公司開源卵皂，Oozie是一個基于工作流引擎的服務器秩铆，可以在上面運行Hadoop的Map Reduce和Pig任務。它其實就是一個運行在Java Servlet容器（比如Tomcat）中的Javas Web應用灯变。對于Oozie來說殴玛，工作流就是一系列的操作（比如Hadoop的MR，以及Pig的任務）柒凉，這些操作通過有向無環(huán)圖的機制控制族阅。這種控制依賴是說，一個操作的輸入依賴于前一個任務的輸出膝捞，只有前一個操作完全完成后坦刀，才能開始第二個愧沟。以xml的形式寫調度流程，可以調度mr鲤遥，pig沐寺，hive，shell盖奈，jar