プロンプトとコンテキスト
この質問は、多数の近似タイマーに対して適切なデータ構造を選択できるかをテストするものです。バイナリヒープは締切（deadline）を順序付けるため、挿入と削除でヒープの順序を維持します。一方、タイミングホイールは締切をバケットにマッピングし、正確なタイミングが不要なネットワークタイムアウト、リトライ、コネクションキープアライブなどに適しています。精度、計算量、キャンセルのセマンティクス、長期遅延、および実行スレッドの境界について説明してください。
面接官が評価している点
- ティック、バケット数、カバーされる期間、およびタスクの締切を正確に関連付けられているか。
- 周回をまたぐタスク、現在のバケット内の処理、ティックの遅延、および早期実行を適切に処理できるか。
- キャンセルが低コストであり、キャンセルされたノードが誤って実行されないようになっているか。
- スレッドセーフ、コールバックの分離、クロックの選択、および過負荷時の挙動を説明できるか。
最初に確認すべき明確化のための質問
タスク量、許容される最小・最大の誤差、最小・最大の遅延、キャンセル率、およびコールバックの実行時間を確認します。タスクは永続化が必要で、プロセスの再起動後も維持されるべきですか？複数のスレッドが schedule や cancel を呼び出す可能性がありますか？コールバックはブロックする処理を含みますか？1つのティックに期日を迎えたタスクが多すぎる場合、実行を遅延させるべきか、優先度の低い処理を破棄すべきか、それともバックプレッシャーを適用すべきですか？これらの回答によって、1つのホイールで十分か、あるいは階層型ホイールや外部永続化が必要かが決まります。
30秒の回答フレームワーク
モノトニッククロック（単調増加クロック）で相対的な締切を計算し、固定ティックでカーソルを進めます。タスクごとにバケットインデックスと残りラウンド数を計算し、双方向連結リストに格納します。各ティックでは現在のバケットのみを走査します。残りラウンド数があるタスクはデクリメントして保持し、ラウンド数がゼロになった期日到来タスクを取り出して実行します。ハンドルを使用することで、cancel がノードをマークしてリストから切り離すことができます。ホイールは処理をスケジュールしますが、ティックスレッド上でユーザーコールバックを実行することはありません。精度、並行性、および過負荷時の挙動は、テストとメトリクスで検証します。
ステップバイステップの詳細解説
1. ホイールのパラメータと誤差を定義する
tickDuration をティック、wheelSize をバケット数とすると、1周で tickDuration × wheelSize をカバーします。締切を相対ティックに変換し、(currentTick + remainingTicks) mod wheelSize を計算します。ティックは最小分解能を決定し、1周の期間はどの遅延が直接収まるかを決定します。より広い範囲に対応するには、階層型ホイールを使用するか、タスクをより正確に配置できるようになるまで残りラウンド数の値を保持します。
2. タスクノードとバケット構造を選択する
各ノードには、締切、remainingRounds、コールバック、キャンセルフラグ、ならびに前後のポインタを格納します。双方向連結リストを使用すると、ノードが既知である場合に定数時間での挿入と削除が可能になります。ハンドルがノードを直接指すことができるため、cancel が検索を行う必要はありません。すべてのタスクを配列に保持してティックごとに全件走査することは避けてください。コストがタスクの総数に比例して増大するためです。
3. ティックの進行と周回の処理
モノトニッククロックとカーソルを進め、現在のバケットを切り離します。remainingRounds が正の値である場合は、それをデクリメントしてノードを再挿入します。それ以外の場合は実際の締切を比較します。まだ早いタスクは再度バケットに入れ直し、期日に達したタスクのみを投入します。スレッドの一時停止によって多数のティックがスキップされた場合は、キャッチアップ処理に上限を設け、遅延を記録して、復元処理が無制限にブロックされないようにします。
4. schedule、cancel、および競合の処理
プロデューサーキューを使用して schedule と cancel のリクエストを単一のティックスレッドに送信することで、バケットロックの競合を減らすことができます。cancel は切り離しを試みる前にフラグを設定します。ティックスレッドがバケットからノードを取り出した後、フラグを再確認するため、競合によってキャンセルされたコールバックが実行されることはありません。現在時刻より前の締切は、負の剰余で任意の将来のバケットに変換するのではなく、「次に利用可能なティックで実行」と定義する必要があります。
5. コールバックの分離と過負荷対策
ティックスレッドはノードの移動と処理の投入のみを行い、有界なエグゼキュータ（bounded executor）がユーザーコールバックを実行します。エグゼキュータが満杯の場合は、キュー制限、優先度に応じた破棄可能な処理のドロップ、非クリティカルな処理の遅延、過負荷エラーの返却などのポリシーを定義します。期限切れの遅延、バケット走査時間、キャンセル数、エグゼキュータのキュー長、およびコールバックの失敗を追跡し、ホイールまたは下流のエグゼキュータのどちらがボトルネックになっているかを特定します。
6. 疑似コードでコアの不変条件を固定する
コアのループは次のように表現できます。ロックとスレッドの所有権は実装言語によって異なります。
schedule(task, deadline):
ticks = ceil((deadline - now) / tickDuration)
ticks = max(ticks, 0)
node.rounds = ticks / wheelSize
node.bucket = (currentTick + ticks) % wheelSize
buckets[node.bucket].append(node)
return node.handle
advance(now):
while currentTick <= floor(now / tickDuration):
bucket = buckets[currentTick % wheelSize]
for node in bucket.detachAll():
if node.cancelled: continue
if node.rounds > 0:
node.rounds -= 1
bucket.append(node)
elif node.deadline <= now:
executor.submit(node.callback)
else:
schedule(node, node.deadline)
currentTick += 1模範的な高評価の回答
まず、誤差の許容範囲、遅延範囲、キャンセル率、永続性、およびコールバックのブロッキング有無を確認します。モノトニッククロックと固定ティックを使用し、締切、残りラウンド数、キャンセルフラグ、およびハンドルをノードに格納する双方向連結リストのバケットを採用します。schedule はバケットとラウンド数を計算し、cancel はハンドル経由でノードを切り離してフラグを設定します。ティックスレッドは現在のバケットのみを処理し、将来の周回のためにラウンド数を減らし、期日の到来したコールバックを有界なエグゼキュータに投入します。スキップされたティック後のキャッチアップは上限を設けて測定します。エグゼキュータの過負荷に対してはキュー、優先度、および障害のポリシーを設定します。テストでは、境界となる締切、長期遅延、繰り返しのキャンセル、並行した schedule/cancel、クロックジャンプ、コールバックの例外、および数百万ノードでの走査コストをカバーします。より厳しい誤差やより広い範囲が必要な場合は、ホイールが常に高速であると主張するのではなく、階層型ホイールやヒープを追加します。
よくある間違い
- 相対的な遅延にウォールクロック時刻（実時間）を使用し、システムクロックの調整を無視すること。
remainingRoundsを忘れ、タスクが最初の周回で発火してしまうこと。- まだ期日に達していない現在のバケット内のタスクを実行してしまう、あるいは暗黙のうちに消失させてしまうこと。
- ノードを取り出した後に再確認することなくキャンセルのブール値を設定すること。
- ティックスレッド上でユーザーコールバックを同期的に実行し、ホイールを失速させること。
- すべてのタスクの固定配列を走査し、スパースなスケジューリングの効率性を失うこと。
- スキップされたティック、過負荷、再起動時の復元、およびコールバックの失敗に対する挙動を省略すること。
フォローアップの質問と回答
なぜ min-heap を使用しないのですか？
min-heap は、より小規模なワークロードや厳密な締切順序付けには適していますが、挿入や削除ごとにヒープ順序を維持する必要があります。タイミングホイールは精度と引き換えに定数時間でのバケット配置と削除を実現するため、多数の近似タイマーに適しています。ホイールが常に高速であると主張するのではなく、許容誤差のバジェットと操作の分布に基づいて選択します。
ティックスレッドが数秒間停止した場合はどうなりますか？
モノトニック時間を使用して経過したはずのティック数を計算し、1回のキャッチアップパスで処理するバケットまたはタスクの数に上限を設け、残りは後回しにします。スケジューリングの遅延を測定し、突発的なバーストが許容できない場合は、復元中にすべてのコールバックを同期実行するのではなく、バッチ処理とバックプレッシャーを組み合わせます。
cancel がタスクを実行させないことをどのように保証しますか？
ハンドルがノードを指します。cancel は切り離す前にアトミックにフラグをマークし、ティックスレッドはノードを切り離した後にフラグを再確認します。コールバックがすでに投入されている場合は、キャンセルの線形化ポイントを定義し、コールバックの開始前にタスクの状態を確認させます。
階層型タイミングホイールが必要になるのはどのような場合ですか？
単一の周回で最大の締切をカバーできない場合や、タスクの遅延が数桁に及ぶ場合に使用します。より粒度の粗い上位レベルを追加してタスクを下方へカスケードさせつつ、各レベルの精度、劣化、および移行コストを定義します。永続性とクラッシュ復旧のためには、ホイールを信頼性の高いストレージやメッセージングから分離することが依然として必要です。