プロンプトとスコープ
schedule(taskId, runAt, priority, fn)、cancel(taskId)、および next() を備えた単一ノードの Scheduler を実装してください。最も早い runAt を選択し、次に最も高い priority、次に送信順序（sequence）を選択します。有効な taskId のバージョンは 1 つだけです。キャンセルされたタスクは開始してはなりません。実行すべきタスクがない場合、next() は待機ヒントまたは空の結果を返します。遅延削除、ワーカーの並行性、クロックの選択、およびシャットダウンの競合について説明してください。
公開されている面接資料では、タスクスケジューリングは優先度付きキュー、ワーカープール、キャンセル、障害処理を組み合わせた問題として提示されます。ヒープデータ構造そのものに加えて、ライフサイクルと並行性の契約がテストされます。
面接官がテストしていること
- 不正な遷移のない
pending、running、cancelled、およびcompletedの状態マシン。 - タスクオブジェクト同士を決して比較しない決定論的キー
(runAt, -priority, sequence)。 - 置換やキャンセルによって古い処理が漏れ出さないようにするための、バージョンチェックまたは遅延削除。
- キュー内の処理のキャンセルと、実行中の関数の停止との正確な区別。
- ワーカーの制限、シャットダウンの順序、およびクロックの選択が契約を維持することの証明。
最初に確認すべき明確化の質問
runAtは単調増加の相対期限ですか、それとも実時間（ウォールクロック時間）ですか？待機には単調増加クロックを仮定します。fnはキャンセル通知を受け取りますか？協調的停止のみを行うAbortSignalを仮定します。- 重複する
taskIdは置換されますか、それとも失敗しますか？このバージョンは古いバージョンを置換します。 cancelは実行中の関数を直ちに停止しますか？いいえ。まだ開始されていない実行を防止し、実行中の関数にシグナルを送ります。closeは実行中の処理を待機しますか？新しい処理を拒否し、ワーカーが終了するのを待機すると仮定します。
30秒の回答
(runAt, -priority, sequence, taskId, version) を最小ヒープに保持し、各タスク ID の最新バージョンをマップに格納します。スケジューリングまたはキャンセルを行うとマップが更新され、古いヒープエントリが無効化されます。next() は、期限が到来したタスクを running に移行する前に、バージョンと状態を繰り返し検証します。ディスパッチャは単調増加クロックを使用してヒープの先頭を待機し、固定サイズのワーカープールに処理を渡します。キューイングされたタスクのキャンセルは強力な保証であり、実行中のコードのキャンセルは協調的です。シャットダウンは新しい送信を拒否し、ディスパッチャを起こし、クリーンアップを待機します。
ステップごとの詳細解説
ステップ 1: キーと不変条件を定義する
ヒープキーとして (runAt, -priority, sequence) を使用します。単調増加する sequence により、等しいタイムスタンプと優先度が決定論的になります。current[taskId] は最新のバージョンのみを保存します。古いバージョンが一時的にヒープに残る場合がありますが、それらが pending から running に遷移することは決してありません。
ステップ 2: schedule における置換を定義する
各 schedule は新しいバージョンを作成し、それをマップに格納して、新しいヒープエントリをプッシュします。配列に対する線形探索は行いません。エントリがポップされた際、そのバージョンがマップと比較されます。挿入は O(log n) であり、重複する ID が 2 つの有効な実行を生成することはありません。
schedule(id, runAt, priority, fn):
version = nextVersion(id)
current[id] = {version, state: pending, fn, runAt, priority}
heappush(heap, (runAt, -priority, nextSequence(), id, version))ステップ 3: cancel と先頭のクリーンアップを実装する
キャンセルは現在の保留中タスクを cancelled としてマークし、待機者を起こします。next() が先頭をポップする際、マップが依然として同じバージョンを指しており、状態が pending であることを確認します。古いエントリ、キャンセルされたエントリ、置き換えられたエントリは破棄されます。遅延削除によって O(n) スキャンを回避しますが、古いエントリの比率を監視し、定期的に再構築する必要があります。
ステップ 4: ワーカー制限で期限到来タスクをゲートする
ディスパッチャは未来の処理をワーカーに渡してはなりません。単調増加クロックを使用してヒープ先頭までの遅延を計算します。期限が到来すると、アトミックに pending から running へ変更し、タスクを固定サイズのワーカーキューに投入します。ワーカー数またはセマフォによって並行性の上限が強制されます。
ステップ 5: キャンセルと関数の終了を分離する
キューイングされたタスクが状態遷移前にキャンセルされた場合、fn が呼び出されることはありません。実行中のタスクは AbortSignal を受け取ることしかできません。関数はそれを確認するか、キャンセル可能な I/O に渡す必要があります。cancelRequested を記録し、関数が実際にリターンするまで完了を報告しないでください。
ステップ 6: 競合を防ぐために close の順序を整える
close はまず closing に移行して新しいスケジュールを拒否し、次にタイマーをキャンセルしてディスパッチャを起こします。ディスパッチャは新しいタスクの取得を停止し、ワーカーは既に取得された処理を終了します。その後初めてスケジューラは closed になります。キューイングされた処理を直ちに破棄する必要がある場合は、単にヒープをクリアするのではなく、マップエントリをキャンセル済みとしてマークします。
ステップ 7: 計算量と空間境界を証明する
通常の schedule は O(log n)、cancel は O(1) の状態更新、next は O(log n) のヒープ処理を実行します。各古いエントリは最大 1 回しかポップされないため、クリーンアップはそれを作成した更新またはキャンセルに償却されます。ヒープサイズがアクティブなタスクの一定倍数を超えた場合、現在のマップエントリから再構築します。
ステップ 8: 重要なインターリービングをテストする
同一キーに対する安定した順序、古いエントリが先頭に達する前の置換、取得直前および直後のキャンセル、より早いタスクによる待機の割り込み、ワーカー制限、関数の失敗、close 中の送信、単調増加クロックのジャンプをテストします。ソートされた参照モデルに対して next() の差分テストを行い、ピーク時のアクティブワーカー数を記録します。
質の高い模範解答
状態をヒープから分離します。マップには各 taskId の最新バージョンを格納し、最小ヒープには (runAt, -priority, sequence, taskId, version) を格納します。置換は新しいバージョンを書き込み、キャンセルは状態をマークします。いずれもヒープ配列を変更しません。ディスパッチャは期限が到来したタスクのみを取得し、それらを固定サイズのワーカーキューに入れます。バージョン検証により、キャンセルされたエントリや古いエントリの実行が防止され、AbortSignal は実行中の関数に協調的キャンセルを提供します。シャットダウンは新しい処理を拒否し、タスクの取得を停止し、待機者を起こし、取得済みの処理が完了するのを待機します。メトリクスでアクティブなエントリとヒープサイズを追跡し、遅延削除が無制限に肥大化しないようにします。
よくある間違い
- 優先度のみでソートし、
runAtがまだ未来にあることを無視する。 - ヒープエントリをインプレースで変更し、ヒープの不変条件を破壊する。
- マップからのみ削除し、その後古いヒープエントリを実行してしまう。
cancel()の呼び出しの成功を、実行中のコードが停止した証拠として扱う。- 待機に実時間（ウォールクロック時間）を使用し、時刻補正の影響を受ける。
- タイマー、ディスパッチャ、またはワーカーを稼働させたまま、
closeでキューをクリアする。 - 無制限にワーカーを起動し、スケジューラを無制限のランチャーにしてしまう。
フォローアップの質問と回答
低優先度の処理の枯渇（スターベーション）をどのように防ぎますか？
厳格な優先度がデフォルトであり、低優先度タスクが枯渇する可能性があることを説明します。公平性が必要な場合は、待機時間に応じて実効優先度を上げるか、重み付けされたクォータを使用します。どちらの選択も順序付けキーとレイテンシの証明を変更するため、メトリクスとテストを追加します。
定期実行タスクの重複実行をどのように防ぎますか？
タスクの状態に実行中ロックまたは世代（generation）を追加します。実行中に次のトリガーが到着した場合は、スキップ、保留中の実行を 1 つに合体、または新しいバージョンのエンキューのいずれかを明示的に選択します。重複が禁止されている場合は、決して無条件に送信しないでください。
プロセスクラッシュ後はどのように復旧しますか？
メモリ内のヒープはプロセスのライフタイムのみをカバーします。バージョン、状態、および次回の実行時刻を永続化し、起動時にヒープを再構築して、条件付き更新またはリースを使用してタスクを取得します。通常、復旧では少なくとも1回の実行（at-least-once）が提供されるため、タスク関数は冪等である必要があります。
複数ノードへどのように拡張しますか？
ローカルヒープを永続化された時間インデックス付きキューに置き換え、所有権のためにリースまたは条件付き書き込みを使用します。ノード障害後は期限切れのリースを再試行可能にします。キャンセルや置換を通じてバージョンを引き継ぎ、コンシューマが古い処理を拒否できるようにし、ノード間ではストレージ時間または明示的な許容時間枠を使用します。