Hoe zou je een scheduler ontwerpen voor 10 miljoen getimede taken?

Question

IT Interview Practice · Accepted Answer

Sla taken op in een **time-bucketed / priority queue** op sleutel van de vervaltijd, poll alleen de taken die *nu* aan de beurt zijn, en geef ze door aan idempotente workers met **at-least-once** bezorging. Scan nooit 10 miljoen rows per tick — indexeer op vuurtijd zodat elke poll alleen raakt wat aan de beurt is.

## Architectuur

```text
API ─▶ Task store (DB/Redis ZSET, score = due_ts)  ── 10M taken, gesharded
             │
     Poller (leider per partitie) ── ZPOPMIN due<=now ──▶ Ready queue (Kafka)
             │ leiderverkiezing (etcd/ZK)                     │
             ▼                                                 ▼
     andere pollers idle/standby                       Worker pool (idempotent)
                                                        └─ ack ✔ / retry ✖ ─▶ DLQ
```

## Componenten en flow

- **Task store geïndexeerd op vuurtijd**: een Redis sorted set (`ZADD tasks score=due_ts`) of een DB-tabel geïndexeerd op `(run_at)`. `ZPOPMIN`/`ZRANGEBYSCORE now` haalt alleen de taken op die deze seconde aan de beurt zijn — O(log n), geen table scan. **Sharding/partitionering** op task-id spreidt 10 miljoen taken over nodes zodat geen enkele store hot is.
- **Poller met leiderverkiezing**: elke partitie heeft één actieve poller die via etcd/ZooKeeper wordt verkozen; standbys nemen over bij falen. Eén leider per partitie voorkomt dat twee pollers dezelfde taak dispatchen, terwijl partitionering de throughput hoog houdt.
- **Ready queue (Kafka)**: taken die aan de beurt zijn worden in de queue gezet, wat *scheduling* van *executie* ontkoppelt. Workers schalen onafhankelijk van de poller.
- **Idempotente workers** voeren uit en **ack'en**. Omdat bezorging at-least-once is, kan een taak twee keer draaien (poller crashte na dispatch, vóór het markeren als klaar) — dus het werk zelf moet idempotent zijn, op sleutel van `task_id`, anders belast je een klant dubbel. Mislukkingen retryen met backoff en landen daarna in een DLQ.

## Interviewperspectief

De interviewer peilt twee dingen: **efficiënte tijdlookup** en **exactly-once versus at-least-once**. "Goed" is een cron-loop over een tabel; "uitstekend" is de sorted-set-index plus de eerlijke erkenning dat gedistribueerde exactly-once onpraktisch is, zodat je kiest voor **at-least-once + idempotente workers**. Een klassieke valkuil: leunen op één enkele scheduler-node — dat is een SPOF en een throughput-plafond. Nog een: te grof pollen (elke minuut) terwijl taken secondeprecisie nodig hebben, of te fijn en de store hameren.

## Afwegingen en faalmodi

- **Precisie versus belasting**: een tick van 1s geeft nauwkeurigheid op secondeniveau maar meer polls; bucket taken in per-minuut- en dan per-seconde-subqueues om scan-kosten te beperken (de "timing wheel" / hashed-wheel-aanpak van Kafka en Quartz).
- **At-least-once versus exactly-once**: je kunt over een crash-grens geen echte exactly-once krijgen; idempotency keys maken dubbele executie onschadelijk — de juiste afweging.
- **Faalmodus**: als een poller midden in een dispatch sterft, promoveert leiderverkiezing een standby en worden niet-ge-ack'te taken opnieuw bezorgd — niets gaat verloren, sommige kunnen herhalen. Let op **clock skew** tussen nodes (NTP), anders vuren taken te vroeg of te laat; en begrens retries zodat een permanent falende taak niet eeuwig loopt — stuur hem naar de DLQ voor inspectie.

Architectuur

Componenten en flow

Interviewperspectief

Afwegingen en faalmodi

Gerelateerde vragen