Wie würdest du einen Scheduler für 10 Mio. zeitgesteuerte Tasks entwerfen?

Question

IT Interview Practice · Accepted Answer

Speichere Tasks in einer **zeit-gebucketten / Priority Queue**, gekeyt nach Fälligkeitszeit, polle nur die *jetzt* fälligen Tasks und übergib sie idempotenten Workern mit **At-least-once**-Zustellung. Scanne niemals bei jedem Tick 10 Mio. Rows - indexiere nach Feuerzeit, sodass jeder Poll nur das Fällige berührt.

## Architektur

```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
```

## Komponenten und Ablauf

- **Task Store, indexiert nach Feuerzeit**: ein Redis Sorted Set (`ZADD tasks score=due_ts`) oder eine DB-Tabelle, indexiert auf `(run_at)`. `ZPOPMIN`/`ZRANGEBYSCORE now` zieht nur die in dieser Sekunde fälligen Tasks - O(log n), kein Table Scan. **Sharding/Partitionierung** nach Task-ID verteilt 10 Mio. Tasks über Nodes, sodass kein einzelner Store heiß wird.
- **Poller mit Leader Election**: Jede Partition hat einen aktiven Poller, gewählt über etcd/ZooKeeper; Standbys übernehmen bei Ausfall. Ein Leader pro Partition verhindert, dass zwei Poller denselben Task dispatchen, während die Partitionierung den Throughput hoch hält.
- **Ready Queue (Kafka)**: Fällige Tasks werden eingereiht, wodurch *Scheduling* von *Execution* entkoppelt wird. Worker skalieren unabhängig vom Poller.
- **Idempotente Worker** führen aus und **acken**. Da die Zustellung At-least-once ist, kann ein Task zweimal laufen (Poller crashte nach dem Dispatch, vor der Markierung als erledigt) - deshalb muss die Arbeit selbst idempotent sein, gekeyt auf `task_id`, sonst belastest du einen Kunden doppelt. Fehler werden mit Backoff wiederholt und landen dann in einer DLQ.

## Interview-Perspektive

Der Interviewer sondiert zwei Dinge: **effizientes Zeit-Lookup** und **exactly-once vs. at-least-once**. "Gut" ist eine Cron-Schleife über eine Tabelle; "hervorragend" ist der Sorted-Set-Index plus das ehrliche Eingeständnis, dass verteiltes Exactly-once unpraktikabel ist, weshalb du **At-least-once + idempotente Worker** wählst. Eine klassische Falle: sich auf einen einzelnen Scheduler-Node zu verlassen - er ist ein SPOF und eine Throughput-Obergrenze. Eine weitere: zu grob pollen (jede Minute), wenn Tasks Sekundengenauigkeit brauchen, oder zu fein und den Store zu hämmern.

## Trade-offs und Fehlerfälle

- **Präzision vs. Last**: Ein 1s-Tick liefert Sekundengenauigkeit, aber mehr Polls; buckete Tasks in Per-Minute- und dann Per-Second-Subqueues, um die Scankosten zu senken (der "Timing Wheel"-/Hashed-Wheel-Ansatz, den Kafka und Quartz nutzen).
- **At-least-once vs. exactly-once**: Über eine Crash-Grenze hinweg lässt sich echtes Exactly-once nicht erreichen; Idempotency Keys machen doppelte Ausführung harmlos - der richtige Trade.
- **Fehlerfall**: Stirbt ein Poller mitten im Dispatch, befördert die Leader Election einen Standby und un-ackte Tasks werden erneut zugestellt - nichts geht verloren, manches wiederholt sich. Achte auf **Clock Skew** über Nodes (NTP), sonst feuern Tasks zu früh/spät; und deckele Retries, damit ein dauerhaft fehlschlagender Task nicht ewig schleift - schicke ihn zur Inspektion in die DLQ.

Architektur

Komponenten und Ablauf

Interview-Perspektive

Trade-offs und Fehlerfälle

Ähnliche Fragen