プロンプトと適用範囲
インメモリの TaskScheduler を実装します。呼び出し元はタスクID、依存関係ID、および関数を送信します。スケジューラは、すべての依存関係が成功した後にのみタスクを取得（クレーム）できます。submit、ready、complete、fail、cancel などの操作を公開し、実行不可能な依存関係の循環を報告してください。重複送信、失敗の伝播、並行性制限、シャットダウン、および再起動の境界について説明してください。
この問題は、グラフ走査とライブ状態マシンを組み合わせたものです。優れた回答では、データ構造を選択する前に状態と失敗のセマンティクスを明確にし、その後に入次数（indegree）、逆方向エッジ、および実行可能キュー（ready queue）を維持します。Pythonの TopologicalSorter は、未完了の先行ノードがないノードを処理可能として扱い、検出された循環を診断データとして公開します。これらのセマンティクスはコントラクトの定義に役立ちますが、タスクは時間の経過とともに完了、失敗、キャンセルされるため、静的なトポロジカルソートだけでは不十分です。
面接官が評価しているポイント
pending、ready、running、succeeded、failed、blocked、およびcancelledの区別。- すべてのタスクを再走査するのではなく、入次数と逆方向隣接の不変条件を維持すること。
- 依存関係が完了した際に、影響を受ける依存先のみを解放すること。
- APIを選択する前に、循環、失敗、およびキャンセルの伝播を定義すること。
- ワーカー数を制限し、タスクバージョンごとに1回のクレームを保証し、重複送信を処理すること。
- 敵対的なインターリーブに対する計算量の制限とテストを提示すること。
確認すべき質問
- グラフは静的ですか、それとも動的にタスクを追加できますか？参照されるすべてのタスクはスケジューリング開始前に送信されると想定してください。実行中に送信できるのは新しいバージョンのみです。
- 依存関係が失敗した後、後続ノード（descendants）はどうなりますか？この回答では、それらに
blockedのマークを付けます。再試行には明示的な新しい世代（generation）が必要です。 - キャンセルはすべての後続ノードに連鎖しますか？そのタスクのみをキャンセルすると想定します。必須の依存関係がキャンセルされた場合、後続ノードは
blockedになります。 - 失敗は自動的に再試行されますか？いいえ。呼び出し元が新しい世代を送信し、副作用の冪等性を担保します。
ready()は1つのタスクを返しますか、それともバッチを返しますか？決定論的な順序で最大maxConcurrency - running個のタスクを返します。
30秒での回答
各タスクの状態、未完了の依存関係数、および逆方向の隣接リストを保持します。スケジューリングの前にKahnのアルゴリズムまたは3色DFSを実行し、循環が存在する場合はそのパスを返します。入次数がゼロのタスクを安定した実行可能キューに入れます。単一のロック下で、ready を running に変更してタスクを取得します。成功時には、各依存先ノードのカウントをデクリメントし、ゼロに達したノードをキューに追加します。失敗とキャンセルは、影響を受ける後続ノードに blocked のマークを付けます。古いワーカーが依存先を二重に解放しないよう、すべてのコールバックに世代番号を持たせます。固定ワーカープールまたはセマフォによって並行性を制御します。
ステップごとの解説
ステップ 1: 状態と境界の定義
状態は前進のみします：pending から ready、次に running、そして最後に succeeded または failed となります。キャンセルは pending または ready の間に発生する可能性があり、実行中関数のキャンセルは協調的（cooperative）に行われます。blocked は、必要な依存関係が成功しなくなったため関数が実行されなかったことを意味します。終端状態が ready に戻ることはなく、重複実行が防止されます。
タスクIDごとに generation を保持します。重複送信は拒否するか新しい世代を作成することができます。この回答では、古いバージョンが実行中でない場合にのみ置換を選択します。実行中のバージョンを暗黙的に上書きすることはできません。競合を返すか、その終端コールバックを待機します。
ステップ 2: 入次数と逆方向エッジの構築
タスクテーブルは remainingDeps を保持し、逆方向マップは dependents[dependencyId] を保持します。各エッジは1回だけ登録します。入次数がゼロのタスクは初期化中に実行可能キューに入り、その後の変更では影響を受けるカウントのみが更新されます。
Task:
id, generation, dependencies, dependents
remainingDeps, state, fn, error
submit(task):
validateUniqueDependencies(task)
registerEdges(task)
if task.remainingDeps == 0:
task.state = READY
readyQueue.push(task.id)未知の依存関係を完了済みとして扱ってはなりません。送信されるまで waiting 状態に保つか、コントラクトが閉じたグラフを要求する場合は UnknownDependency エラーで拒否します。
ステップ 3: 実行前の循環の報告
静的グラフの場合、Kahnのアルゴリズムは入次数をコピーし、入次数ゼロのノードを処理して、その出エッジを削除します。処理されたノードが全体のノード数より少ない場合、残りの部分に循環が含まれています。booleanだけでなく、A → B → C → A のような具体的なパスを返します。
あるいは、白・灰・黒のDFSを使用して灰から灰へのエッジを検出し、親ポインタを介して循環を再構築します。いずれかのタスクが running になる前に検出を実行します。コントラクトによって新しいグラフバージョンが作成されない限り、実行開始後にエッジを追加することは禁止します。
ステップ 4: タスクの取得と並行性の制御
ready() は利用可能なスロットを計算し、安定した送信順でタスクを取り出し、同一のクリティカルセクション内で各状態を running に変更します。一度返されたタスクを別の呼び出し元が取得することはできません。complete(id, generation) は世代と状態の両方を検証します。古いワーカーからの遅延コールバックは競合を返し、依存先を解放することはできません。
並行性制限には、固定ワーカー数またはセマフォを使用します。キューの長さはアクティブなタスク数ではありません。running のタスクのみがスロットを消費します。要求されたバッチが利用可能スロットを超える場合は、暗黙的に並行性を引き上げるのではなく、利用可能な数または CapacityExceeded を返します。
ステップ 5: 成功、失敗、キャンセルの伝播
成功時には、直接の依存先を走査します。まだ保留中（pending）のバージョンに対してのみ remainingDeps をデクリメントし、カウントがゼロになったノードをエンキューします。失敗時には、このコントラクトは直接および間接の後続ノードに blocked のマークを付け、最初のブロッキング要因を記録します。代替依存関係ポリシーは、明示的に指定されている場合にのみ有効です。
キャンセルはまだ開始されていないバージョンに影響します。実行中の関数は AbortSignal を受け取る場合がありますが、協調的な終了を確認できるのは関数自身のみです。必須の依存関係が失敗またはキャンセルされた場合、後続ノードは blocked になり、その依存関係が成功したかのように装うことは決してありません。
ステップ 6: 送信とコールバックの冪等性の確保
(taskId, generation) を冪等性キーとして使用します。complete、fail、または cancel の呼び出しが繰り返された場合、既知の終端状態を返し、依存先を二重にデクリメントすることはありません。保留中のバージョンを置き換えるときは、新しいエッジを登録する前に古い逆方向エッジを削除します。オブジェクトの上書きだけでは古いエッジが残り、依存先が永久に待機状態になる可能性があります。
更新が不要な場合は、重複IDを拒否する方がシンプルです。トレードオフを明確にしてください。静的なビルダーは重複を拒否できますが、長時間のワークフローでは通常、世代管理、監査記録、および明示的な再試行バージョンが必要です。
ステップ 7: シャットダウン、再試行、および復旧
close() は新しい送信を拒否し、ready() がこれ以上タスクを取得するのを停止し、実行中のコールバックまたは定義されたタイムアウトを待機します。キュー内のタスクは、コントラクトに従ってキャンセルされるか保持されます。理由を記録せずにメモリをクリアすると情報が失われます。再試行は、failed を ready に戻すのではなく、新しい世代を作成して依存関係のスナップショットを再チェックします。
インメモリスケジューラは、プロセスクラッシュ後に復旧できません。永続化にはタスク、バージョン、状態、依存関係、およびリースの保存が必要です。復旧ワーカーは条件付き書き込みでタスクを取得し、タスク関数は冪等である必要があります。復旧によって提供できるのは「少なくとも1回の実行（at-least-once execution）」であり、「正確に1回の副作用（exactly-once side effects）」ではありません。
ステップ 8: 計算量とテスト
グラフの初期化は O(V + E) です。各完了処理は出エッジのみを走査するため、全体の伝播パスは O(V + E) のままです。ヒープベースの実行可能キューは O(log V) で取得を行います。空間計算量は O(V + E) です。
空のグラフ、独立したブランチ、長いチェーン、循環、未知の依存関係、2つの依存関係の同時完了、失敗の伝播、後続ノードのキャンセル、重複コールバック、重複送信、キャパシティゼロ、シャットダウンの競合、古い世代からの遅延コールバックをテストします。小規模な状態モデルを使用して各実行可能セットを比較し、バージョンごとに最大1回の pending → running 遷移をアサートできます。
模範解答
私ならまずグラフを凍結し、次に各タスクの状態、世代、残りの依存関係数、および逆方向の隣接関係を保存します。親ポインタと組み合わせたKahnのアルゴリズムによって具体的な循環を報告します。依存関係のないタスクは安定した実行可能キューに入ります。ready() は、単一のロック下で残りの並行スロット上限までタスクを取得し、直ちにタスクに running のマークを付けます。完了コールバックは世代と一致する必要があり、遷移は1回のみ許可されます。成功時はダウンストリームのカウントをデクリメントし、ゼロに達したノードをキューに入れます。失敗とキャンセルは、成功を偽装するのではなく後続ノードを blocked にします。重複コールバックは冪等であり、再試行は新しい世代を作成し、シャットダウンは実行中コールバックをドレイン（排出）する前に新しい作業を拒否します。パス全体の計算量は O(V + E) であり、テストによって並行性と副作用の境界を検証します。
よくある落とし穴
- 実際の完了や失敗の遷移を定義せずに、単一のトポロジカルソートを実行してしまうこと。
- 各完了後に逆方向エッジを使用せず、すべてのノードを走査して実行可能かどうか確認すること。
- 診断用のパス情報なしで、循環の有無を示すboolean値のみを返すこと。
- 完了コールバックから世代情報を省略し、古いワーカーが依存先を解放できるようにしてしまうこと。
- 依存関係の失敗を成功として扱い、前提条件を満たさずに後続作業を実行してしまうこと。
- 協調的なシグナルコントラクトなしに、実行中の関数のキャンセルを強制的であると主張すること。
- バックログを隠すためにワーカー数を増やし、ダウンストリームのキャパシティを枯渇させること。
- 冪等性、副作用、またはリースのセマンティクスを考慮せずに、失敗した状態を再試行に再利用すること。
フォローアップ質問
メモリに収まらないほど巨大なグラフはどのように処理しますか？
タスクのメタデータとエッジを永続化ストレージに保存し、テナントまたはパーティションごとにアクティブなウィンドウのみをロードします。メモリ内にはカーソルを保持します。取得には条件付き書き込みまたは短いリースを使用し、完了時には依然として世代をチェックします。パーティション間の依存関係、ページネーションの一貫性、およびリース期限切れ後の重複実行について説明します。
失敗したブランチを継続しつつ、依存するノードのみを停止させるにはどうすればよいですか？
エッジに「必須」または「オプション」のラベルを付けます。タスクは、すべての必須依存関係が成功し、オプションの依存関係が終端状態に達した後にのみ実行可能になります。オプションの失敗を暗黙的に無視するのではなく、入力サマリーやメトリクスに記録します。これにより、状態マシンとテストが拡張されます。
依存関係を動的に追加するにはどうすればよいですか？
タスクが pending の間のみ新しいエッジを許可し、同一のクリティカルセクション内で入次数をインクリメントします。ready または running のタスクに対する変更は拒否します。実行中の変更が必要な場合は、新しい世代を作成し、古いバージョンが終端状態に達した後に新しいグラフに対して実行します。
関連のないブランチに影響を与えずに、共有依存関係をキャンセルするにはどうすればよいですか？
その依存関係の終端状態のみを変更し、逆方向エッジに沿って必須エッジの関係を検査します。その依存関係を持たないブランチは継続し、それを必要とするすべてのダウンストリームタスクは blocked になります。誰が、いつ、どの伝播パスに沿ってキャンセルしたかを監査記録に残します。
複数のワーカープロセスで二重実行を防ぐにはどうすればよいですか？
データベースのアトミック更新またはリースを使用してタスクを取得し、条件に世代を含めます。リースが期限切れになると別の取得が許可される可能性があるため、タスク関数は冪等であるか補償可能である必要があります。インメモリのロックは単一プロセスのみを保護します。
どのような可観測性（オブザーバビリティ）シグナルが重要ですか？
循環数、ブロック数、実行可能待ち時間、実行時間、取得競合、リース期限切れ、重複コールバック、およびエッジごとの伝播レイテンシを追跡します。平均値によって末尾のバックログが隠れないよう、タスクタイプやテナントごとにセグメント化し、グラフの設定エラーと関数の失敗を区別します。
タスクが2回取得されないことをどのように証明しますか？
状態チェック、スロットのデクリメント、および running の書き込みを単一のクリティカルセクションまたはアトミックな条件付き更新にまとめ、コールバックに世代を含めます。モデルテストで2つの ready() 呼び出しをインターリーブさせ、バージョンごとに最大1回の pending → running 遷移をアサートします。重複した完了処理は既知の終端状態を返します。