आप 1 करोड़ timed tasks के लिए एक scheduler कैसे डिज़ाइन करेंगे?

Question

IT Interview Practice · Accepted Answer

tasks को due time से keyed एक **time-bucketed / priority queue** में स्टोर करें, केवल *अभी* due tasks को poll करें, और उन्हें **at-least-once** delivery के साथ idempotent workers को सौंपें। हर tick पर 1 करोड़ rows कभी scan न करें — fire time से 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
```

## कंपोनेंट्स और फ्लो

- **Fire time से indexed task store**: एक Redis sorted set (`ZADD tasks score=due_ts`) या `(run_at)` पर indexed एक DB table। `ZPOPMIN`/`ZRANGEBYSCORE now` केवल इस सेकंड due tasks खींचता है — O(log n), table scan नहीं। task-id से **Sharding/partitioning** 1 करोड़ tasks को nodes में फैलाता है ताकि कोई एक store hot न हो।
- **Leader election वाला Poller**: हर partition का एक active poller होता है जो etcd/ZooKeeper से elect होता है; failure पर standbys संभाल लेते हैं। प्रति partition एक leader दो pollers को एक ही task dispatch करने से रोकता है, जबकि partitioning throughput ऊंचा रखता है।
- **Ready queue (Kafka)**: due tasks enqueue होते हैं, *scheduling* को *execution* से decouple करते हुए। Workers poller से स्वतंत्र scale होते हैं।
- **Idempotent workers** execute करते हैं और **ack** करते हैं। चूंकि delivery at-least-once है, एक task दो बार चल सकता है (poller dispatch के बाद, done mark करने से पहले crash हुआ) — इसलिए काम स्वयं idempotent होना चाहिए, `task_id` पर keyed, वरना आप एक customer को दो बार charge कर देते हैं। Failures backoff के साथ retry होते हैं, फिर DLQ में जाते हैं।

## इंटरव्यू का नज़रिया

Interviewer दो चीज़ें परखता है: **efficient time lookup** और **exactly-once बनाम at-least-once**। "अच्छा" एक table पर cron loop है; "बढ़िया" sorted-set index plus यह ईमानदार स्वीकृति है कि distributed exactly-once अव्यावहारिक है, इसलिए आप **at-least-once + idempotent workers** चुनते हैं। एक क्लासिक जाल: एक अकेले scheduler node पर निर्भर रहना — यह एक SPOF और एक throughput छत है। एक और: बहुत मोटा poll करना (हर minute) जब tasks को second precision चाहिए, या बहुत महीन और store पर हथौड़ा मारना।

## ट्रेड-ऑफ़ और failure

- **Precision बनाम load**: 1s tick second-level accuracy देता है पर अधिक polls; tasks को per-minute फिर per-second sub-queues में bucket करें ताकि scan cost घटे (Kafka और Quartz द्वारा इस्तेमाल किया गया "timing wheel" / hashed-wheel तरीका)।
- **At-least-once बनाम exactly-once**: आप एक crash boundary के पार सच्चा exactly-once नहीं पा सकते; idempotency keys double execution को हानिरहित बनाती हैं — सही trade।
- **Failure**: अगर एक poller dispatch के बीच मर जाए, leader election एक standby को promote करता है और un-acked tasks redeliver होते हैं — कुछ भी नहीं खोता, कुछ दोहरा सकते हैं। nodes में **clock skew** पर नज़र रखें (NTP) वरना tasks जल्दी/देर से fire होते हैं; और retries cap करें ताकि एक स्थायी रूप से fail होने वाला task हमेशा loop न करे — इसे जांच के लिए DLQ में भेजें।

आर्किटेक्चर

कंपोनेंट्स और फ्लो

इंटरव्यू का नज़रिया

ट्रेड-ऑफ़ और failure

संबंधित प्रश्न