Πώς θα σχεδιάζατε έναν scheduler για 10 εκατομμύρια χρονισμένα tasks;

Question

IT Interview Practice · Accepted Answer

Αποθηκεύστε τα tasks σε μια **time-bucketed / priority queue** με κλειδί τον χρόνο εκτέλεσης, κάντε poll μόνο τα tasks που πρέπει να εκτελεστούν *τώρα*, και δώστε τα σε idempotent workers με **at-least-once** delivery. Μην κάνετε ποτέ scan 10 εκατομμύρια rows σε κάθε tick — κάντε index με βάση τον χρόνο εκτέλεσης ώστε κάθε poll να αγγίζει μόνο ό,τι είναι due.

## Αρχιτεκτονική

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

## Στοιχεία και ροή

- **Task store indexed by fire time**: ένα Redis sorted set (`ZADD tasks score=due_ts`) ή ένας DB πίνακας με index στο `(run_at)`. Το `ZPOPMIN`/`ZRANGEBYSCORE now` τραβάει μόνο τα tasks που είναι due αυτό το δευτερόλεπτο — O(log n), όχι table scan. Το **sharding/partitioning** με βάση το task-id απλώνει 10 εκατομμύρια tasks σε nodes ώστε κανένα store να μην είναι hot.
- **Poller με leader election**: κάθε partition έχει έναν ενεργό poller εκλεγμένο μέσω etcd/ZooKeeper· τα standbys αναλαμβάνουν σε αποτυχία. Ένας leader ανά partition αποφεύγει το να dispatch-άρουν δύο pollers το ίδιο task, ενώ το partitioning κρατά το throughput υψηλό.
- **Ready queue (Kafka)**: τα due tasks μπαίνουν στην ουρά, αποσυζευγνύοντας το *scheduling* από το *execution*. Οι workers κάνουν scale ανεξάρτητα από τον poller.
- **Idempotent workers** εκτελούν και κάνουν **ack**. Επειδή το delivery είναι at-least-once, ένα task μπορεί να τρέξει δύο φορές (ο poller έκανε crash μετά το dispatch, πριν το μαρκάρισμα ως done) — οπότε η ίδια η εργασία πρέπει να είναι idempotent, με κλειδί το `task_id`, αλλιώς χρεώνετε διπλά έναν πελάτη. Οι αποτυχίες κάνουν retry με backoff, και μετά καταλήγουν σε ένα DLQ.

## Οπτική συνέντευξης

Ο συνεντευκτής διερευνά δύο πράγματα: **efficient time lookup** και **exactly-once vs at-least-once**. Το "καλό" είναι ένα cron loop πάνω σε έναν πίνακα· το "εξαιρετικό" είναι το sorted-set index συν η ειλικρινής παραδοχή ότι το distributed exactly-once είναι μη πρακτικό, οπότε επιλέγετε **at-least-once + idempotent workers**. Μια κλασική παγίδα: η εξάρτηση από ένα μοναδικό scheduler node — είναι SPOF και ταβάνι throughput. Άλλη μία: υπερβολικά χονδρικό polling (κάθε λεπτό) όταν τα tasks χρειάζονται ακρίβεια δευτερολέπτου, ή υπερβολικά λεπτό και σφυροκόπημα του store.

## Trade-offs και αποτυχία

- **Ακρίβεια vs load**: ένα tick 1s δίνει ακρίβεια επιπέδου δευτερολέπτου αλλά περισσότερα polls· κάντε bucket τα tasks σε per-minute και μετά per-second υπο-ουρές για να μειώσετε το κόστος scan (η προσέγγιση "timing wheel" / hashed-wheel που χρησιμοποιούν τα Kafka και Quartz).
- **At-least-once vs exactly-once**: δεν μπορείτε να πετύχετε αληθινό exactly-once πέρα από ένα crash boundary· τα idempotency keys κάνουν τη διπλή εκτέλεση αβλαβή — το σωστό trade.
- **Αποτυχία**: αν ένας poller πεθάνει στη μέση ενός dispatch, το leader election προάγει ένα standby και τα μη-acked tasks ξανα-παραδίδονται — τίποτα δεν χάνεται, κάποια μπορεί να επαναληφθούν. Προσέξτε το **clock skew** μεταξύ nodes (NTP) αλλιώς τα tasks πυροδοτούνται νωρίς/αργά· και βάλτε πλαφόν στα retries ώστε ένα μόνιμα αποτυχημένο task να μην κάνει loop για πάντα — στείλτε το στο DLQ για επιθεώρηση.

Αρχιτεκτονική

Στοιχεία και ροή

Οπτική συνέντευξης

Trade-offs και αποτυχία

Σχετικές ερωτήσεις