1000万件のタイマータスクを処理するスケジューラをどのように設計しますか？

Question

IT Interview Practice · Accepted Answer

タスクを実行予定時刻をキーとする**タイムバケット化 / 優先度キュー**に保存し、*今*実行すべきタスクだけをポーリングし、**at-least-once**配信で冪等なworkerに渡します。ティックごとに1000万行をスキャンしてはいけません。実行時刻でインデックスを張り、各ポーリングが期限到来分のみに触れるようにします。

## アーキテクチャ

```text
API ─▶ Task store (DB/Redis ZSET, score = due_ts)  ── 10M tasks, sharded
             │
     Poller (leader per partition) ── ZPOPMIN due<=now ──▶ Ready queue (Kafka)
             │ leader election (etcd/ZK)                       │
             ▼                                                 ▼
     other pollers idle/standby                       Worker pool (idempotent)
                                                        └─ ack ✔ / retry ✖ ─▶ DLQ
```

## コンポーネントと処理の流れ

- **実行時刻でインデックスされたタスクストア**：Redisのsorted set（`ZADD tasks score=due_ts`）または `(run_at)` にインデックスを張ったDBテーブル。`ZPOPMIN`/`ZRANGEBYSCORE now` はこの秒に期限到来したタスクのみを取り出します。テーブルスキャンではなくO(log n)です。タスクIDによる**シャーディング / パーティショニング**が1000万タスクをノード間に分散し、単一のストアがホットにならないようにします。
- **リーダー選出を伴うポーラー**：各パーティションにはetcd/ZooKeeperで選出された1つのアクティブなポーラーがあり、障害時にはスタンバイが引き継ぎます。パーティションごとに1リーダーとすることで、2つのポーラーが同じタスクをディスパッチするのを避けつつ、パーティショニングでスループットを高く保ちます。
- **Readyキュー（Kafka）**：期限到来タスクはエンキューされ、*スケジューリング*と*実行*を分離します。workerはポーラーとは独立にスケールします。
- **冪等なworker**が実行し、**ack**します。配信がat-least-onceのため、タスクは二度実行される可能性があります（ポーラーがディスパッチ後、完了マーク前にクラッシュ）。したがって作業自体が `task_id` をキーとして冪等でなければ、顧客に二重課金してしまいます。失敗はバックオフでリトライし、その後DLQに入ります。

## 面接での観点

面接官は2点を探ります。**効率的な時刻ルックアップ**と、**exactly-once対at-least-once**です。「良い」回答はテーブルに対するcronループですが、「優れた」回答はsorted-setインデックスに加え、分散環境での真のexactly-onceは非現実的だという正直な認識で、**at-least-once + 冪等なworker**を選ぶことです。典型的な罠は、単一のスケジューラノードに依存することです。それはSPOFであり、スループットの上限です。もう一つは、秒精度が必要なのに粗く（毎分）ポーリングする、あるいは細かすぎてストアを叩き続けることです。

## トレードオフと障害

- **精度対負荷**：1秒ティックは秒レベルの精度を与えますがポーリングが増えます。タスクを分単位、次に秒単位のサブキューにバケット化してスキャンコストを削ります（KafkaやQuartzが使う「timing wheel」/ hashed-wheel方式）。
- **At-least-once対exactly-once**：クラッシュ境界をまたいで真のexactly-onceは得られません。冪等キーが二重実行を無害にします。これが正しいトレードです。
- **障害**：ポーラーがディスパッチ中に落ちると、リーダー選出がスタンバイを昇格させ、未ackのタスクが再配信されます。何も失われず、一部が繰り返されるだけです。ノード間の**クロックスキュー**（NTP）に注意しないとタスクが早発/遅発します。また、恒久的に失敗するタスクが永遠にループしないようリトライ回数を上限化し、検査のためDLQへ送ります。

アーキテクチャ

コンポーネントと処理の流れ

面接での観点

トレードオフと障害

関連する質問