Design Job Scheduler

Prompt latihan

1. Problem Statement, Functional Requirements, and Scale Assumptions

   Tentukan ruang lingkup distributed job scheduler: pengguna mengirim job satu-kali atau berulang (berbasis cron), job dapat mendefinisikan dependensi task berbasis DAG (task B berjalan setelah task A selesai), task dieksekusi pada pool worker terdistribusi, dan sistem menyediakan monitoring job serta alerting (job macet, kegagalan). Kecualikan secara eksplisit: orkestrasi training model ML (Kubernetes-native), pemrosesan stream real-time, eksekusi query interaktif, dan dashboard analitik untuk pengguna. Nyatakan asumsi skala: job yang dikirim per hari, task yang berjalan bersamaan, kedalaman DAG (maks task dalam rantai dependensi), lebar DAG (maks task paralel per level), distribusi durasi task, dan ukuran pool worker.

2. Non-Functional Requirements

   Tentukan NFR utama: keandalan eksekusi job (eksekusi at-least-once, tidak ada task yang di-drop diam-diam; sebuah task boleh di-retry saat gagal tetapi tidak boleh hilang permanen), latensi penjadwalan (waktu dari task menjadi eligible, dependensinya selesai, hingga task mulai dieksekusi pada worker; target < 1 menit untuk task non-prioritas, < 10 detik untuk job prioritas), kebenaran dependensi DAG (task B tidak boleh mulai sebelum task A selesai dengan sukses, race condition pada gerbang dependensi harus dicegah), efisiensi utilisasi worker (worker yang idle harus segera ditugaskan task; tidak ada starvation), dan visibilitas kegagalan (operator harus menerima alert dalam N menit dari job yang gagal atau macet).

3. Quantitative Analysis

   Estimasikan: laju pengiriman job (10 ribu job/hari = ~0,1 job/detik, rendah, tetapi setiap job mungkin memiliki 100 task = 1 ribu task/detik saat puncak), kapasitas eksekusi task bersamaan (10 ribu task bersamaan / 10 task per worker = 1 ribu worker), kedalaman antrian task (saat puncak: 10 ribu task bersamaan diantrikan sebelum worker mengambil = antrian menampung ~10 ribu entri), bandwidth heartbeat worker (1 ribu worker × 1 heartbeat/30s × 200 byte = 6,7KB/s, dapat diabaikan), dan storage riwayat job (10 ribu job/hari × 100 task × 1KB metadata/task = 1GB/hari, dapat dikelola di PostgreSQL).

4. API Design

   Tentukan operasi API untuk: mengirim job dengan definisi DAG (POST /jobs, body menyertakan task sebagai node, dependensi sebagai edge, priority, schedule/cron, retry policy), query status job (GET /jobs/{job_id}, mengembalikan state DAG dengan status dan log per-task), membatalkan job (POST /jobs/{job_id}/cancel), mendaftar riwayat job dengan filter (GET /jobs?status=failed&since=1h), me-retry job yang gagal (POST /jobs/{job_id}/retry, dapat menentukan retry parsial dari task sukses terakhir), dan format definisi DAG (adjacency list: [{task_id, command, depends_on: [task_ids], retry_count, timeout_s}]). Bahas idempotensi pengiriman job untuk mencegah job duplikat dari retry klien.

5. High-Level Design

   Usulkan komponen utama: scheduler service (mengevaluasi state DAG, menentukan task mana yang eligible, dependensinya selesai, dan mengantrikannya ke task queue), task queue (priority queue yang menampung task eligible menunggu diambil worker), worker pool (worker terdistribusi yang polling task queue, mengeksekusi task, dan melaporkan hasil), heartbeat monitor (mendeteksi worker yang tidak responsif via heartbeat yang terlewat dan mengklaim ulang task yang ditugaskan padanya), job store (PostgreSQL, mempersistensi definisi job, state DAG, hasil task), dan notification service (mengirim alert saat job gagal atau macet). Jelaskan loop penjadwalan: task selesai → scheduler memperbarui state DAG → memeriksa task mana yang kini eligible → mengantrikan task yang baru eligible.

6. Additional High-Level Design Prompts

   Bahas tiga area lanjutan: (1) Deteksi siklus DAG saat pengiriman, pengguna mengirim DAG di mana task A bergantung pada task B dan task B bergantung pada task A (siklus); scheduler harus mendeteksi ini saat pengiriman sebelum mempersistensi job; gunakan topological sort (algoritma Kahn) selama validasi: jika sort tidak dapat memproses semua node, terdapat siklus; kembalikan error 400 dengan deskripsi siklus; (2) HA scheduler, jika scheduler adalah single point of failure (ia menyimpan state evaluasi DAG di memori), restart menyebabkan semua evaluasi DAG yang sedang berlangsung hilang; strategi: persistensikan semua state DAG ke job store (PostgreSQL), jalankan beberapa instance scheduler dalam mode active-passive (leader election via distributed lock); saat leader failover, leader baru membaca state DAG dari job store dan melanjutkan evaluasi; (3) Pemicu job berulang, dukungan ekspresi cron: pada setiap waktu terjadwal, scheduler membuat instance job baru dari template; risiko: jika scheduler mati saat pemicu berbunyi, pemicu mungkin terlewat; solusi: tabel pemicu di job store mencatat kapan setiap job berulang harus berbunyi berikutnya; scheduler mengambil pemicu yang terlewat saat restart dalam window backfill.

7. Deep Dives

   Deep dive ke tiga area: (1) Pemulihan kegagalan, retry task dengan backoff: saat task gagal, naikkan retry_count; antrikan ulang dengan exponential backoff (2^n × base_delay); setelah max_retries, tandai task FAILED dan propagasikan kegagalan ke atas di DAG (gagalkan task dependen); deteksi poison pill: task yang gagal konsisten setelah max_retries adalah poison pill, rutekan ke dead letter queue untuk inspeksi manual; eksekusi ulang DAG parsial: saat retry job, tentukan checkpoint sukses terakhir (task terakhir yang selesai sebelum kegagalan); eksekusi ulang hanya sub-DAG di hilir task yang gagal, bukan DAG penuh; deteksi crash worker: timeout heartbeat (worker gagal heartbeat dalam 30s); scheduler mengklaim ulang task: UPDATE tasks SET status='queued' WHERE worker_id=X AND heartbeat_at < NOW()-30s; klaim ulang orphan bersifat idempoten, jika worker pulih dan mencoba menyelesaikan task, ia mendapat error konflik dan membuang hasilnya; (2) Penjadwalan prioritas, priority queue multi-level: P0 (kritis), P1 (tinggi), P2 (normal), P3 (background); scheduler selalu mengirim P0 sebelum P1 dst.; pencegahan starvation: task yang telah diantrikan > T menit dinaikkan prioritasnya satu level (aging); preemption: untuk task P0, scheduler dapat memberi sinyal worker untuk melakukan checkpoint dan menjeda task P3 saat ini guna memulai task P0 segera (preemption kooperatif via perintah heartbeat); (3) Kebenaran eksekusi DAG, gerbang dependensi: sebelum menandai task sebagai eligible, verifikasi semua task induk dalam state COMPLETED (read-modify atomik di PostgreSQL: SELECT FOR UPDATE pada baris task induk); race condition: dua task selesai bersamaan dan keduanya memicu task anak yang sama, cegah double-enqueue via constraint database (unique index pada (job_id, task_id, status='queued')).

8. Final Review Handoff Readiness

   Ringkas keputusan desain utama: deteksi siklus DAG saat pengiriman (topological sort), PostgreSQL sebagai job store dengan persistensi state DAG, HA scheduler via leader election active-passive, kesehatan worker berbasis heartbeat dengan klaim ulang task orphan, penjadwalan prioritas dengan aging dan preemption kooperatif, dan eksekusi ulang DAG parsial dari checkpoint sukses terakhir. Soroti dua pertanyaan terbuka terbesar yang tersisa (batas skalabilitas scheduler, pada laju pengiriman job berapa satu instance scheduler menjadi bottleneck, dan percabangan kondisional, bagaimana menangani DAG di mana task berikutnya bergantung pada output task sebelumnya saat runtime) dan usulkan rollout bertahap: antrian job flat (non-DAG) dulu, lalu eksekusi DAG, lalu penjadwalan prioritas, lalu HA leader election.

Preview solusi

Solusi: Merancang Job Scheduler Pembingkaian Problem Sebuah distributed job scheduler menerima submission job (one-time atau recurring), mengeksekusi task dengan dependency berbasis DAG pada distributed worker pool, dan menyediakan monitoring serta alerting untuk job yang macet (stuck) atau gagal. Dalam scope: Submission job dengan DAG, recurring job berbasi…