Hvordan ville du designet en scheduler for 10M tidsstyrte oppgaver?

Question

IT Interview Practice · Accepted Answer

Lagre oppgaver i en **tidsbøttet / prioritetskø** nøklet på forfallstid, poll kun oppgavene som forfaller *nå*, og gi dem til idempotente workere med **at-least-once** levering. Aldri skann 10M rader hvert tick — indekser på fire-tid slik at hver poll berører kun det som forfaller.

## Arkitektur

```text
API ─▶ Task store (DB/Redis ZSET, score = due_ts)  ── 10M oppgaver, sharded
             │
     Poller (leder per partisjon) ── ZPOPMIN due<=now ──▶ Ready-kø (Kafka)
             │ ledervalg (etcd/ZK)                            │
             ▼                                                 ▼
     andre pollere idle/standby                       Worker-pool (idempotent)
                                                        └─ ack ✔ / retry ✖ ─▶ DLQ
```

## Komponenter og flyt

- **Task store indeksert på fire-tid**: et Redis sorted set (`ZADD tasks score=due_ts`) eller en DB-tabell indeksert på `(run_at)`. `ZPOPMIN`/`ZRANGEBYSCORE now` trekker kun oppgaver som forfaller dette sekundet — O(log n), ikke en table scan. **Sharding/partisjonering** på task-id sprer 10M oppgaver over noder slik at ingen enkelt store er hot.
- **Poller med ledervalg**: hver partisjon har én aktiv poller valgt via etcd/ZooKeeper; standbys tar over ved feil. Én leder per partisjon unngår at to pollere dispatcher samme oppgave, mens partisjonering holder throughput høy.
- **Ready-kø (Kafka)**: forfalte oppgaver legges i kø, og avkobler *scheduling* fra *execution*. Workere skalerer uavhengig av polleren.
- **Idempotente workere** kjører og **ack-er**. Fordi levering er at-least-once, kan en oppgave kjøre to ganger (poller krasjet etter dispatch, før markering ferdig) — så selve arbeidet må være idempotent, nøklet på `task_id`, ellers dobbeltbelaster du en kunde. Feil retryes med backoff, og lander så i en DLQ.

## Intervjuperspektiv

Intervjueren undersøker to ting: **effektiv tidsoppslag** og **exactly-once vs at-least-once**. "Bra" er en cron-loop over en tabell; "utmerket" er sorted-set-indeksen pluss den ærlige innrømmelsen at distribuert exactly-once er upraktisk, så du velger **at-least-once + idempotente workere**. En klassisk felle: å stole på én enkelt scheduler-node — den er en SPOF og et throughput-tak. En annen: å polle for grovt (hvert minutt) når oppgaver trenger sekundpresisjon, eller for fint og hamre løs på store-en.

## Avveininger og feil

- **Presisjon vs belastning**: 1s tick gir sekundnøyaktighet men flere polls; bøtt oppgaver inn i per-minutt så per-sekund sub-køer for å kutte scan-kostnad ("timing wheel" / hashed-wheel-tilnærmingen brukt av Kafka og Quartz).
- **At-least-once vs exactly-once**: du kan ikke få ekte exactly-once over en krasjgrense; idempotensnøkler gjør dobbel kjøring uskadelig — den rette avveiningen.
- **Feil**: hvis en poller dør midt i dispatch, promoterer ledervalg en standby og u-ack-ede oppgaver leveres på nytt — ingenting går tapt, noe kan gjentas. Følg med på **clock skew** på tvers av noder (NTP) ellers fyrer oppgaver tidlig/sent; og cap retries slik at en permanent feilende oppgave ikke looper for alltid — send den til DLQ-en for inspeksjon.

Arkitektur

Komponenter og flyt

Intervjuperspektiv

Avveininger og feil

Relaterte spørsmål