Kaip suprojektuotumėte planuoklį (scheduler) 10 mln. laiku suplanuotų užduočių?

Question

IT Interview Practice · Accepted Answer

Saugokite užduotis **pagal laiką suskaidytoje / prioritetinėje eilėje**, indeksuotoje pagal terminą, apklauskite tik užduotis, kurių terminas *dabar*, ir perduokite jas idempotentiškiems workeriams su **at-least-once** pristatymu. Niekada neskenuokite 10 mln. eilučių kiekvieną tiką — indeksuokite pagal suveikimo laiką, kad kiekviena apklausa liestų tik tai, kam atėjo terminas.

## Architektūra

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

## Komponentai ir eiga

- **Užduočių saugykla, indeksuota pagal suveikimo laiką**: Redis sorted set (`ZADD tasks score=due_ts`) arba DB lentelė, indeksuota pagal `(run_at)`. `ZPOPMIN`/`ZRANGEBYSCORE now` ištraukia tik šią sekundę suplanuotas užduotis — O(log n), o ne lentelės skenavimas. **Sharding/partitioning** pagal task-id paskleidžia 10 mln. užduočių per mazgus, kad nė viena saugykla nebūtų karšta.
- **Poller su leader election**: kiekviena partition turi vieną aktyvų poller, išrinktą per etcd/ZooKeeper; atsarginiai perima gedimo atveju. Vienas lyderis vienai partition neleidžia dviem polleriams siųsti tą pačią užduotį, o partitioning palaiko aukštą throughput.
- **Paruošta eilė (Ready queue, Kafka)**: suplanuotos užduotys įdedamos į eilę, atsiejant *planavimą* nuo *vykdymo*. Workeriai keičia mastą nepriklausomai nuo poller.
- **Idempotentiški workeriai** vykdo ir **ack**. Kadangi pristatymas yra at-least-once, užduotis gali įvykti dukart (poller nulūžo po siuntimo, prieš pažymint atlikta) — tad pats darbas privalo būti idempotentiškas, raktuotas pagal `task_id`, kitaip du kartus apmokestinsite klientą. Klaidos kartojamos su backoff, tada patenka į DLQ.

## Interviu perspektyva

Interviuotojas tiria du dalykus: **efektyvią laiko paiešką** ir **exactly-once vs at-least-once**. „Gerai" yra cron ciklas per lentelę; „puikiai" yra sorted-set indeksas plius sąžiningas pripažinimas, kad paskirstytas exactly-once nepraktiškas, tad renkatės **at-least-once + idempotentiškus workerius**. Klasikiniai spąstai: pasikliauti vienu planuoklio mazgu — tai SPOF ir throughput lubos. Kiti: apklausti per retai (kas minutę), kai užduotims reikia sekundės tikslumo, arba per dažnai ir daužyti saugyklą.

## Kompromisai ir gedimai

- **Tikslumas vs apkrova**: 1s tikas suteikia sekundės tikslumą, bet daugiau apklausų; grupuokite užduotis į per-minute, tada per-second sub-eiles, kad sumažintumėte skenavimo kaštus („timing wheel" / hashed-wheel metodas, naudojamas Kafka ir Quartz).
- **At-least-once vs exactly-once**: negalite pasiekti tikro exactly-once per gedimo ribą; idempotentiškumo raktai daro dvigubą vykdymą nekenksmingu — teisingas kompromisas.
- **Gedimas**: jei poller nulūžta siuntimo metu, leader election paaukština atsarginį, o nepatvirtintos užduotys pristatomos iš naujo — niekas neprarandama, kai kurios gali pasikartoti. Stebėkite **clock skew** tarp mazgų (NTP), kitaip užduotys suveikia anksti/vėlai; ir apribokite pakartojimus, kad nuolat gendanti užduotis nesisuktų amžinai — siųskite ją į DLQ patikrinimui.

Architektūra

Komponentai ir eiga

Interviu perspektyva

Kompromisai ir gedimai

Susiję klausimai