Jak byste navrhli scheduler pro 10 milionů časovaných úloh?

Question

IT Interview Practice · Accepted Answer

Ukládejte úlohy do **time-bucketed / prioritní fronty** klíčované časem splatnosti, pollujte jen úlohy splatné *teď* a předávejte je idempotentním workerům s doručením **at-least-once**. Nikdy neskenujte 10 milionů řádků při každém ticku — indexujte podle času vypálení, aby každý poll sáhl jen na to, co je splatné.

## Architektura

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

## Komponenty a tok

- **Task store indexovaný časem vypálení**: Redis sorted set (`ZADD tasks score=due_ts`) nebo DB tabulka s indexem na `(run_at)`. `ZPOPMIN`/`ZRANGEBYSCORE now` vytáhne jen úlohy splatné v této sekundě — O(log n), ne table scan. **Sharding/partitioning** podle task-id rozprostře 10 milionů úloh napříč nodes, takže žádný jeden store není hot.
- **Poller s leader election**: každá partition má jeden aktivní poller zvolený přes etcd/ZooKeeper; standby jej při selhání převezmou. Jeden leader na partition brání tomu, aby dva pollery dispatchovaly stejnou úlohu, a partitioning zároveň udržuje vysoký throughput.
- **Ready queue (Kafka)**: splatné úlohy jsou zařazeny do fronty, čímž se *plánování* oddělí od *provádění*. Workery škálují nezávisle na pollerech.
- **Idempotentní workery** provádějí a **ackují**. Protože doručení je at-least-once, úloha může proběhnout dvakrát (poller spadl po dispatchi, před označením hotovo) — takže samotná práce musí být idempotentní, klíčovaná na `task_id`, jinak zákazníka strhnete dvakrát. Selhání retryují s backoffem a poté padnou do DLQ.

## Pohled z pohovoru

Tazatel zkoumá dvě věci: **efektivní vyhledávání podle času** a **exactly-once vs at-least-once**. „Dobré“ je cron smyčka nad tabulkou; „skvělé“ je index se sorted setem plus poctivé přiznání, že distribuované exactly-once je nepraktické, takže volíte **at-least-once + idempotentní workery**. Klasická past: spoléhat na jeden schedulerový node — je to SPOF a strop throughputu. Další: pollovat příliš hrubě (každou minutu), když úlohy potřebují sekundovou přesnost, nebo příliš jemně a bombardovat store.

## Kompromisy a selhání

- **Přesnost vs zátěž**: 1s tick dá přesnost na sekundu, ale víc pollů; roztřiďte úlohy do per-minute a poté per-second podfront, abyste snížili náklady na skenování (přístup „timing wheel“ / hashed-wheel, který používá Kafka a Quartz).
- **At-least-once vs exactly-once**: skutečné exactly-once přes hranici pádu nezískáte; idempotenční klíče činí dvojí provedení neškodným — správný kompromis.
- **Selhání**: pokud poller zemře uprostřed dispatche, leader election povýší standby a neacknuté úlohy se znovudoručí — nic se neztratí, něco se může zopakovat. Hlídejte **clock skew** napříč nodes (NTP), jinak úlohy vypálí brzy/pozdě; a omezte retry, aby trvale selhávající úloha necyklila donekonečna — pošlete ji do DLQ ke kontrole.

Architektura

Komponenty a tok

Pohled z pohovoru

Kompromisy a selhání

Související otázky