Kako bi zasnovali razvrščevalnik (scheduler) za 10 milijonov časovno določenih opravil?

Question

IT Interview Practice · Accepted Answer

Shranite opravila v **časovno segmentirano (time-bucketed) / prioritetno vrsto**, ključeno po času zapadlosti, poizvedujte le opravila, ki zapadejo *zdaj*, in jih predajte idempotentnim delavcem z **at-least-once** dostavo. Nikoli ne skenirajte 10M vrstic ob vsakem tiku — indeksirajte po času proženja (fire time), tako da vsaka poizvedba dotakne le tisto, kar zapade.

## Arhitektura

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

## Komponente in potek

- **Shramba opravil, indeksirana po času proženja**: Redis sorted set (`ZADD tasks score=due_ts`) ali DB tabela, indeksirana na `(run_at)`. `ZPOPMIN`/`ZRANGEBYSCORE now` potegne le opravila, ki zapadejo to sekundo — O(log n), ne skeniranje tabele. **Sharding/particioniranje** po task-id razporedi 10M opravil po vozliščih, tako da nobena posamezna shramba ni vroča.
- **Poller z izbiro voditelja (leader election)**: vsaka particija ima enega aktivnega pollerja, izvoljenega prek etcd/ZooKeeper; rezervni (standby) prevzamejo ob odpovedi. En voditelj na particijo prepreči, da bi dva pollerja odpošiljala isto opravilo, particioniranje pa ohranja visok throughput.
- **Vrsta pripravljenih (Kafka)**: zapadla opravila se uvrstijo v vrsto in razklopijo *razvrščanje* od *izvajanja*. Delavci skalirajo neodvisno od pollerja.
- **Idempotentni delavci** izvedejo in **potrdijo (ack)**. Ker je dostava at-least-once, se opravilo lahko izvede dvakrat (poller se je sesul po odpošiljanju, pred označitvijo kot opravljeno) — zato mora biti delo samo idempotentno, ključeno na `task_id`, sicer stranki dvakrat zaračunate. Napake se ponavljajo z odmikom (backoff), nato pristanejo v DLQ.

## Pogled s stališča razgovora

Izpraševalec preverja dve stvari: **učinkovito iskanje po času** in **exactly-once proti at-least-once**. "Dobro" je cron zanka čez tabelo; "odlično" je indeks s sorted set plus poštena priznava, da je porazdeljeni exactly-once neizvedljiv, zato izberete **at-least-once + idempotentne delavce**. Klasična past: zanašanje na eno samo vozlišče razvrščevalnika — to je SPOF in strop throughputa. Druga: pregrobo poizvedovanje (vsako minuto), ko opravila potrebujejo sekundno natančnost, ali prefino in tolčenje po shrambi.

## Kompromisi in odpovedi

- **Natančnost proti obremenitvi**: 1s tik daje sekundno natančnost, a več poizvedb; segmentirajte opravila v per-minutne, nato per-sekundne pod-vrste, da zmanjšate stroške skeniranja (pristop "timing wheel" / hashed-wheel, ki ga uporabljata Kafka in Quartz).
- **At-least-once proti exactly-once**: pravega exactly-once čez mejo sesutja ne morete doseči; idempotenčni ključi naredijo dvojno izvedbo neškodljivo — pravi kompromis.
- **Odpoved**: če poller odmre sredi odpošiljanja, izbira voditelja povzdigne rezervnega in nepotrjena opravila se ponovno dostavijo — nič ni izgubljeno, nekaj se lahko ponovi. Pazite na **zamik ure (clock skew)** med vozlišči (NTP), sicer se opravila prožijo prezgodaj/prepozno; in omejite ponovne poskuse, da se trajno odpovedujoče opravilo ne zavrti v neskončno zanko — pošljite ga v DLQ za pregled.

Arhitektura

Komponente in potek

Pogled s stališča razgovora

Kompromisi in odpovedi

Povezana vprašanja