Data Driven Workflow Planning in Cluster Management Systems

My Reserches

INDEX †

著者 †

• Deportment of Computer Sciences University of Wisconsin Madison, WI 53706-1685
  • Srinath Sankar
  • David J DeWitt?

目的、問題 †

• Data-intensive Workflowのレスポンスを軽減するための枠踏みを提供

動機、背景 †

• 近年、ATLAS,SDSS,BIRN,BLASTなどの科学分野での情報爆発により効率的なクラスタ上でのData Managementの効率性が重要視されている
• 使用できるディスク領域の増加
  • 既存のCondorでは、ディスク領域の乏しい環境のための実装であるため、効率が悪い

貢献 †

• ディスクの大容量化にふさわしいCondorの設計
  • あるマシンのoutputをしばらく取っておく
  • 他のマシンがそのデータを利用できるかもしれない
• memoization
  • 実行ファイルとそのinput fileがまったく同じなら計算せずとも、以前のoutput fileを出力すればいいのではないのか？
• ジョブの依存関係を意識したスケジューリング
  • ユーザデータのlocationに応じたスケジューリング

提案手法、アイディア、システム †

キャッシュの利用 †

既存のConderではjob1とjob2を行うとき

1. submit machine(S)がjob1(with file1)をスケジューリングによりAに依頼
2. Aがfile2(output)をSに返す
3. Aはfile2を削除
4. Sがjob2(with file2)をスケジューリングによりBに依頼

もしAとBが同じマシンだったら手順2、3は無駄

• そのためにキャッシュを利用し、file2をA上でキャッシュしておく

DATA-AWARE PLANNING †

• 以下のようなトレードオフがある
  • 同一マシン上で複数のjobを実行：結果の受け渡しにネットワークを必要とせず、次のジョブを実行できるが、jobを並列に処理できない
  • 複数のマシン上で複数のjobを実行：依存性のないjobを並列に処理できるが、結果の受け渡しにネットワーク転送を必要とする。
• どちら最適化をきめるアルゴリズムを提案

The Planning algorithm　(単純なアルゴリズム) †

1. DAGを一つもJobと考えDAGの最適な割り当てを考える(Figure4(a))
2. 飛び出たやつ(下の段の二つのA-B-C)をM2、M4などに分散させる(Figure4(b))
   1. このとき、分散させることによるオーバヘッド(M1からM2へのinputやoutputの転送時間など)があるがそれでも実行時間が短縮される場合分散させる
   2. この場合AとBは並列できかつ、オーバヘッドが好ましいのでFigure4(b)のようになった アルゴリズム
      

Replanning Jobs †

• planningアルゴリズムを複数のサイクルに分割

scheduling horizon(SH)

1サイクルでのworkflowスケジュールはscheduling horizon時間で行われる。SHはworkloadやマシンやユーザの数やジョブsubmissionの頻度などに依存する。

• マシンの障害など、実環境に適用できるための改良

1. AssignDAGフェーズにおいて、DAGを割り当てることによってそのマシンの推測runtime時間(ERT)がSHを超えたら以後そのマシンにDAGを割り当てない
2. もし、全てのマシンのERTがSHを超えたらそのサイクルでのplanningは完了
3. ParallelizeフェーズはSHを超えていないマシンがいたら行う
4. もしマシンが追加されたら、そのマシンのERTがSHを超えるまでDAGを割り当てる
5. もしマシンが取り除かれたら、そのマシンからDAGを取り除き次のサイクルに割り当てる

Memoization †

inputやexecutable fileがsubmitされたらそれらのversionを調べ(checksumを用いる)、以前実行したものと同じversionであったら、そのoutputファイルを探しそれを出力する。このとき、要求された処理は実行しない。（パラメータを設定することによってその機能を使用しないこともできる）

CACHE AND REPLICA MAINTENANCE †

ジョブ実行が完了すると、input, output, executableファイルは以下のポリシーによってマシンのディスクキャッシュ上に保存される。この容量上限は管理者が自由に設定できる

Cache Maintenance †

• 上限を超えたらその上限以下になるまでファイルを削除
• worth値が低いものから削除
• worth = (prob_use × filesize) / num_copies
  • prob_use：Σi(1/2)^(λ×ti)
    • i：jobの番号(1〜)
    • λ：パラメータ(c.f.λ=0[LFU], λ=1[LRU]となる)
    • ti：i番目のjobをsubmitしてからの経過時間
  • filesize：ファイルサイズ
  • num_copies：クラスタ上のコピーの数

Replica maintenance †

• 目的のデータが使用できないことがある
  • マシンの障害、マシンビジー、他のジョブが使用中
• そのためデータのレプリカを複数用意する必要がある
• k-replicationを行う
  • 前章のアルゴリズムでファイルが削除されたらk以下になってしまったら、そのレプリカがないディスクのうち最大の空き容量があるマシンを新しいレプリカの保存先として採用
  • 保存先が見つからなければ単に削除される

THE CONDOR DAEMON FRAMEWORK †

• 概要
  • ○＝User Job以外デーモン
  • モクモク＝関数
    
• データベースのスケーマ
  

Job submission †

• ユーザは全てのジョブとその依存関係を記述したDAG-descriptionファイルを作成しなくてはならない。
• condor_submit_dagで送信
• SUBMIT MACHINE上でDAGManデーモンが動く
  • DAG-descroptionをparsingする
  • その後、condor_submitで親プロセスのない全てのジョブを送信

Storage and file transfer †

• starterは必要なデータを取り寄せてくる役割がある
  • 既存のCondor：すべてファイルは実行前に送信される
  • DAG-Condro：必要なファイルのみExecute Machineによって検索され取り寄せる
    • 必要なファイルの場所をデータベースのfile_locationから検索
    • そのマシンにリクエスト。リクエストが返って来なかったら別のマシンにする
• 実行が終了したら、実行時間などを更新する
• また前章(CACHE AND REPLICA MAINTENANCE)の処理も行う

Planning †

• 前章(DATA-AWARE PLANNING)で紹介したアルゴリズムはnegotiatorで行われる

提案したものの評価 †

• 実行環境
  • # of execute machines：25
  • # of submit machines： 2
  • # of matchmaker ： 1
  • # of database ： 1
  • これらを100Mbpsで連結
• 比較するもの
  • ORIG：分散ディスクストレージを使用しないCondor。つまり、Data Driven Schedulingは行わない
  • Job-C：分散ディスクキャッシングを使用しているがDAG-orientedスケジューリングは行わない(Job-oriented)。また、ORIGと同様に全ての親jobが完了したときのみ、jobがスケジューリングされる
  • DAG-C：提案したもの（DAG-Condorファイルキャッシング、DAG-orientedスケジューリング）。しかしstatic version（Replanning Jobsで紹介したことは行わない）
• 注
  • Job-orientedスケジューリング(Job-C)
    • matchmakerはその親のjobが終了してから、初めてその子のjobの情報のplanningを行う
  • DAG-orientedスケジューリング(DAG-C)
    • あらかじめworkflow上の全てのjobの情報を得て、そこからplanningを行う

BLAST †

• 新しい配列のacidから似た遺伝子、たんぱく質を検索
  • ORIG
    • 毎回必要なファイルを転送しているため遅い
    • 必要なファイルはsubmit machineだけが検索するからそこでボトルネックとなる
  • DAG-CやJob-C
    • ファイルの転送はスケジューリングされたマシンに一度だけ転送されいごそれらのマシンをスケジュールするから速い
    • 必要なファイルの検索はsubmit machineだけでなくexecute machineでもできる

Sensitivity to pipeline I/O †

• 50DAGs
  
  
• 実行時間の差異はBLASTと同様
• Job-CとDAG-Cについて
  • Job-CではB1とB2が別のマシンにスケジューリングされたためファイルの転送にオーバヘッドがかかった。

Sensitivity to DAG breadth †

• 50DAGs
  
  
• Job-CではB1-Bnを異なるマシン上で処理したために、転送時間の影響でDAG-Cより遅い

Sensitivity to DAG depth †

Sensitivity to job running time †

• 50DAGs
  
  

Keywords †

Condor(コンドア)

計算機の空き時間を利用することを目的としたジョブスケジューリングシステムである (http://www.gsic.titech.ac.jp/TITechGrid/condor-manual.pdf)

Zoo

GridDB

その他 †

• Memoizationのもとで、もし内部で乱数を使用するような実行ファイルを実行したいとき毎回同じ結果になってしまうのではないか？もちろんオプションなどでオフにすることができるかと思うが。。。
• matchmakerやdatabaseを複数用意できるか？