Hvordan ville du designe en scheduler til 10M tidsstyrede tasks?

Question

IT Interview Practice · Accepted Answer

Gem tasks i en **tids-bucketet / priority queue** nøglet på forfaldstidspunkt, poll kun de tasks der forfalder *nu*, og aflever dem til idempotente workers med **at-least-once** delivery. Scan aldrig 10M rows hvert tick — indeksér på fire time, så hver poll kun rører det, der forfalder.

## Arkitektur

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

## Komponenter og flow

- **Task store indekseret på fire time**: et Redis sorted set (`ZADD tasks score=due_ts`) eller en DB-tabel indekseret på `(run_at)`. `ZPOPMIN`/`ZRANGEBYSCORE now` trækker kun tasks der forfalder dette sekund — O(log n), ikke en table scan. **Sharding/partitionering** efter task-id spreder 10M tasks over noder, så ingen enkelt store er hot.
- **Poller med leader election**: hver partition har én aktiv poller valgt via etcd/ZooKeeper; standbys overtager ved fejl. Én leader pr. partition undgår, at to pollers dispatcher samme task, mens partitionering holder throughput høj.
- **Ready queue (Kafka)**: forfaldne tasks enqueues, hvilket decoupler *scheduling* fra *eksekvering*. Workers skalerer uafhængigt af polleren.
- **Idempotente workers** eksekverer og **ack'er**. Fordi delivery er at-least-once, kan en task køre to gange (poller crashede efter dispatch, før den blev markeret som done) — så selve arbejdet skal være idempotent, nøglet på `task_id`, ellers dobbeltopkræver du en kunde. Fejl retries med backoff og lander derefter i en DLQ.

## Interview-perspektiv

Intervieweren undersøger to ting: **effektivt tidsopslag** og **exactly-once vs at-least-once**. "Godt" er et cron-loop over en tabel; "fremragende" er sorted-set-indekset plus den ærlige indrømmelse, at distribueret exactly-once er upraktisk, så du vælger **at-least-once + idempotente workers**. En klassisk fælde: at forlade sig på én enkelt scheduler-node — den er et SPOF og et throughput-loft. En anden: at polle for groft (hvert minut), når tasks kræver sekundpræcision, eller for fint og hamre storen.

## Trade-offs og fejl

- **Præcision vs belastning**: et 1s tick giver sekund-nøjagtighed men flere polls; buck tasks i per-minut og derefter per-sekund sub-queues for at reducere scan-omkostningen ("timing wheel" / hashed-wheel-tilgangen brugt af Kafka og Quartz).
- **At-least-once vs exactly-once**: du kan ikke få ægte exactly-once på tværs af en crash-grænse; idempotency keys gør dobbelt eksekvering harmløs — det rigtige trade-off.
- **Fejl**: hvis en poller dør midt i dispatch, promoverer leader election en standby, og ikke-ackede tasks genleveres — intet går tabt, nogle kan gentages. Hold øje med **clock skew** på tværs af noder (NTP), ellers fyrer tasks tidligt/sent; og begræns retries, så en permanent fejlende task ikke looper for evigt — send den til DLQ'en til inspektion.

Arkitektur

Komponenter og flow

Interview-perspektiv

Trade-offs og fejl

Relaterede spørgsmål