AI解説

情報源：arXiv 全文（ar5iv HTML 版 arxiv.org/abs/2010.07268）を WebFetch で精読（手法・数式・結果・図の構成を確認）。 原論文の図は本ノートに転載していない（arXiv HTML 画像が取得できなかったため）。核心はAI生成SVGで補足し、図番号は本文の対応箇所で言及する。

一言で

DAG 並列ジョブをサーバレス（AWS Lambda）で実行する際、集中スケジューラのボトルネックと stateless 実行による過剰なデータ移動を、「スケジューラの仕事を多数の Lambda Executor に分散する」ことで解消するフレームワーク Wukong の提案。各 Executor が DAG の自分の経路を自律的に進め、fan-out で新しい Lambda を起動し、fan-in を KVS カウンタで調停する。Dask の DAG をそのまま使え、TSQR で numpywren 比 最大 68.17×高速、SVD1 で numpywren 比 92.96% 安価などを達成。

背景・問題

サーバレス（Lambda 等）は弾力的オートスケールと細粒度従量課金が魅力で、データ分析・ML・最適化のようなバースト並列ワークロードに向く。しかし従来の並列フレームワーク（MapReduce・Spark・Dask）は中央スケジューラ前提で、サーバレスの制約と相性が悪い。本研究が指す問題は 2 つ。

• スケジューラがボトルネック：PyWren は中央スケジューラ（64スレッド）で、1万 Lambda へのスケールに約2分かかる。1回の関数呼び出しに約50msのオーバーヘッドがあり、中央スケジューラが全タスクの完了追跡・依存更新・投入を一手に担うため詰まる。
• データ局所性の崩壊：numpywren の stateless Executor は「各タスクが S3 から入力を読み→計算→S3 へ出力を書く」設計。25k×25k GEMM では読み込みが入力の25倍・書き込みが出力の20倍、8,192k×128 TSQR では書き込みが出力の6,500万倍にも達し、ネットワーク I/O が桁違いに膨らむ。

→ 課題（やること）：DAG ジョブを Lambda 上で、スケジューリングを並列化し、データ局所性を活かして安く速く実行するフレームワークを設計・実装する。著者はこれを Wukong として作る（約12,000行のPython：Executor Runtime 5,349／Storage Manager 3,057／Static Scheduler 3,577）。

提案手法：Wukong

中核の洞察は「中央スケジューラの仕事（完了追跡・ready タスクの特定と投入）を多数の Lambda Executor に分割すれば、タスクを並列にスケジュールでき、競合が減り、スケジューリングを局所性考慮にできる」こと。

補足図（AI生成）：(a) 集中スケジューラはスケールするとボトルネック化し、stateless 実行で I/O が爆発する（Fig.1–4 に対応）。(b) Wukong は葉ノードごとの静的スケジュールを Executor が自律実行し、fan-out で新 Lambda を起動、fan-in を KVS カウンタで調停する（Fig.5–6 に対応）。

静的スケジューリング（Static Scheduling）

ユーザの Python ジョブを Dask が DAG に変換する。n 個の葉ノードを持つ DAG に対し、葉ノードごとに n 個の静的スケジュールを生成する（各葉から DFS で到達するタスク群＋エッジを束ねたもの）。各静的スケジュールは、タスクコードと入力データの KVS キー、そして task execution / fan-in / fan-out の3種の操作からなる（Fig.6）。

タスク実行と動的スケジューリング（Dynamic Scheduling）

• Initial-Executor Invoker が各静的スケジュールを別々の Lambda Executor に並列割り当てする。各 Executor は自分の葉ノードから始め、スケジュール上の1経路を辿って実行する。
• fan-out も fan-in も無い直列区間では、中間出力を Executor のメモリにローカルキャッシュして進む（＝ネットワーク I/O なし）。先読みして不要になったキャッシュは破棄する。
• fan-out（出次数 n>1）：(Case1) どの出力辺も fan-in でないなら、Executor は1つの fan-out タスクを自分で継続実行し、残り n−1 個は新しい Executor を起動して割り当てる。(Case2) 出力辺の一部が fan-in でもある場合、即座に実行可能なタスクを基準に「自分が継続する辺（becomes edge）」を選ぶ。大きな fan-out は Executor が直接呼ぶのではなく Static Scheduler にメッセージを出し、そこに同居する Executor-Invoker が並列に Lambda を起動する。
• fan-in：タスク T の入次数 n について、n 個の Executor が KVS 上のカウンタを原子的に get-and-update して「満たした依存の数」を数え、全依存が揃った Executor だけが T を続行する。揃っていない側は中間オブジェクトを Storage Manager に退避して停止する。

局所性最適化：Task Clustering と Delayed I/O

• Task Clustering：fan-out タスクの出力がしきい値 t（例 200MB）を超える場合、新 Executor を起動せず依存タスクを手元で実行する。巨大中間オブジェクトの保存／取得のコスト・時間を避けるため。
• Delayed I/O：ready な fan-out タスクを実行した後、まだ揃っていなかった fan-in 依存が満たされたか再チェックし、揃ったものを続けて実行する（反復回数は設定可能）。「巨大オブジェクトの同時書き込み＋読み出し」が観測されるパターンでは、全部 ready になるまで待った方が良いため。

ストレージ層とプログラミングモデル

ストレージは AWS Fargate 上の複数 Redis インスタンスで構成（高帯域＝大オブジェクト、高 IOPS＝小オブジェクトの双方に対応。S3 は IOPS が絞られるため不採用）。プログラミングは Dask のインタフェースをそのまま再利用するので、Dask 互換コードは Wukong 上で動く。耐障害性は Lambda の自動リトライ（最大2回）に依存し、より良い耐障害性は将来課題としている。

主なパラメータ：Lambda 3GB／最長7分、Task Clustering しきい値 t=200MB、Storage は Fargate 75ノード（各30GB・4 vCPU）、Static Scheduler は r5n.16xlarge。

評価

ベンチマークは Tree Reduction (TR)・SVD・SVC・GEMM・TSQR。比較対象は numpywren（S3 版／単一 Redis 版）・PyWren・Dask（1,000 worker 構成と 125 worker 構成）。指標は end-to-end 時間（10回平均）・ネットワーク I/O・CPU 時間・金額コスト。

• TSQR（4.1M×128）：Wukong（単一 Redis）は numpywren（単一 Redis）比 68.17×高速（98.53%減）。Fargate 版でも numpywren（S3）比 9.19×高速。numpywren は大サイズで失敗。16.7M×128 でも 13.36×高速。numpywren は 15,631–16,027 倍多くデータを書いていた。
• GEMM（25k×25k）：Wukong（単一 Redis）は numpywren（単一 Redis）比 89.76%高速、読み込み45–49%減・書き込み最大85%減。
• SVD1/SVD2：1,000-worker Dask 比 62–69%高速。ただし潤沢な 125-worker Dask（局所性・帯域が高い）には負ける一方、Wukong は 1,000-worker Dask が扱えない大サイズまでスケールした。
• コスト：TSQR で numpywren 比 7.94×高速・14.22×安価、92.96%のコスト削減。GEMM で best numpywren 比 33.47%安・77.57%速。
• スケーリング（Fig.21）：強スケール・弱スケールとも near-ideal。サーバレススケールで numpywren が1万タスクに約2分かかるのに対し Wukong は数秒で omniscient 挙動に近づく。
• 最適化の寄与（Fig.22-23）：SVD2 50k×50k で Task Clustering＋Delayed I/O により Redis I/O を 565.21s→20.36s（27.76×減）、タスク起動を 14.80s→2.05s（7.21×減）、全体で約4.6×高速化。内訳は Fargate 複数Redis 20.85%／Clustering 48.82%／Delayed I/O 46.21%。

関連研究との関係（本リポジトリ内）

Wukong は本リポジトリでは「サーバレス並列実行」という周辺文脈の参照。著者陣（Carver, Cheng ら）は後の NotebookOS（GPU を実行中セルだけに束縛する設計）にも連なり、「実行中だけ資源を握り、状態/データをストアに逃がす」発想が共通する。状態を外部 KVS に置いて関数実行を軽くする方向は Cloudburst（stateful FaaS）と対になる（Wukong は DAG 並列のスケジューリング、Cloudburst は状態共有・一貫性が主眼）。

将来課題：Lambda の2回リトライ依存を超える耐障害性、設定ノブ（パーティションサイズ・Fargateノード数）の感度分析、AWS 以外（OpenWhisk・Azure・GCP）への移植。

Q&A

自分のコメント